05-07-2013, 12:23 PM
Dynamic network load balancing
Dynamic network.docx (Size: 628.42 KB / Downloads: 20)
Overview
Distributed System
The computing power of any distributed system can be realized by allowing its constituent computational elements (CEs), or nodes, to work cooperatively so that large loads are allocated among them in a fair and effective manner. Any strategy for load distribution among CEs is called load balancing (LB). An effective LB policy ensures optimal use of the distributed resources whereby no CE remains in an idle state while any other CE is being utilized. In many of today’s distributed-computing environments, the CEs are linked by a delay-limited and bandwidth limited communication medium that inherently inflicts tangible delays on internode communications and load exchange. Examples include distributed systems over wireless local-area networks (WLANs) as well as clusters of geographically distant CEs connected over the Internet, such as Planet Lab . Although the majority of LB policies developed heretofore take account of such time delays, they are predicated on the assumption that delays are deterministic
In actuality, delays are random in such communication media, especially in the case of WLANs. This is attributable to uncertainties associated with the amount of traffic, congestion, and other unpredictable factors within the network. Furthermore, unknown characteristics (e.g., type of application and load size) of the incoming loads cause the CEs to exhibit fluctuations in runtime processing speeds. Earlier work by our group has shown that LB policies that do not account for the delay randomness may perform poorly in practical distributed computing settings where random delays are present. For example, if nodes have dated, inaccurate information about the state of other nodes, due to random communication delays between nodes, then this could result in unnecessary periodic exchange of loads among them.
Load Balancing
Load balancing is defined as the allocation of the work of a single application to Processors at run-time so that the execution time of the application is minimized. Since the speed at which a NOW-based parallel application can be completed depends on the computation time of the slowest workstation, efficient load balancing can clearly provide major performance benefits. The two major categories for load-balancing algorithms are static and dynamic.
Static Load Balancing
Static load balancing algorithms allocate the tasks of a parallel program to workstations based on either the load at the time nodes are allocated to some task, or based on an average load of our workstation cluster. The advantage in this sort of algorithm is the simplicity in terms of both implementation as well as overhead, since there is no need to constantly monitor the workstations for performance statistics. However, static algorithms only work well when there is not much variation in the load on the workstations. Clearly, static load balancing algorithms aren’t well suited to a NOW environment, where loads may vary significantly at various times in the day, based on the issues discussed earlier.
Dynamic Load Balancing
Dynamic load balancing algorithms make changes to the distribution of work among workstations at run-time; they use current or recent load information when making distribution decisions .As a result, dynamic load balancing algorithms can provide a significant improvement in performance over static algorithms. However, this comes at the additional cost of collecting and maintaining load information, so it is important to keep these overheads within reasonable limits. The remainder of this report will focus on such dynamic load balancing algorithms.
Existing System:
Many efforts have already been made to provide a more efficient GGSN selection and anchor relocation in 3G/UMTS architectures. In this section we give a short overview of the different approaches, in particular the ones which try to present a practically applicable dynamic solution for GGSN load balancing and load sharing.
The method called “GPRS-Subscriber selection of multiple internet service providers” was developed by Ericsson in order to allow mobile users to connect to multiple different Packet Data Communication networks (PDNs). The selection of the PDN is based on the transmission of a specific Network Indication Parameter (NIP). This parameter is sent to the Serving GPRS Support Node (SGSN) as a parameter in the PDP context activation procedure. The PDP type parameter (a two bytes long field) is used to set up the connection to the chosen PDN. Based on this method, mobile operators can distribute traffic load towards gateways of different networks, and can also assign the GGSN with the lowest load to the new entrant MNs or using other selection policies
Proposed System:
This was the motivation of Shiao-Li Tsao who presented the basics of a dynamic GGSN load balancing and load sharing scheme. The author introduces a new device called the GGSN Controller, which is responsible for monitoring the load of the GGSNs and adjusting the GGSN load dynamically by transferring PDP contexts between GGSNs. The initiation and the process of the PDP transfers are monitored and controlled by the centralized GGSN controller. The GGSNs sending their load information periodically to the GGSN Controller and the Controller decides whether a PDP context transfer is necessary. Shiao-Li Tsao also defines novel protocol messages that make the PDP context transfer available, and gives detailed description of various cases that can occur during the context transfers, but unfortunately no performance evaluation or any kind of analysis was provided in this work.
Comparison:
In order to evaluate our implementation and to analyze the performance characteristics of the concept of dynamic GGSN load balancing in our testbed, we decided to execute measurements with various number of active PDP contexts. We examined the average latency of the packets, which passed through the GGSNs in order to benchmark the throughput of the anchoring gateway node(s) in the 3G/UMTS network. The tests we performed were based on artificial UDP streams synthesized per PDP context by our GTP traffic generator applying packet size of 125 bytes at each stream and using packet sending frequencies between 2400–4000 packet/s. The maximum number of transferred contexts was limited to 10. The results are shown on the following graphs. As it can be seen, the average packet latencies were significantly lower, when dynamic PDP context transfer was enabled. Our results are proving that transferring PDP contexts, thereby achieving dynamic load balancing between GGSNs, can be implemented in real-life environments with substantial gains . With dynamic load balancing, lower packet latencies at gateway anchor nodes are achievable, thus the overall throughput of the network can be increased significantly.
Load Balancing Algorithm
Most load balancing algorithms are designed based on the performance requirements of some specific application domain. For example, applications that exhibit lengthy parallel jobs usually benefit in the presence of a job migration system. However, applications with shorter tasks usually don’t warrant the expense of job migration and thus are better handled with clever loop scheduling algorithms where the task granularity changes dynamically, as defined in. As a result, only one algorithm will be described here in order to provide an overview of the various issues that a typical algorithm must take into consideration. However, all algorithms closely follow the four basic load balancing steps outlined at the beginning of Implementation
Global vs. Local Strategies
Global or local policies answer the question of what information will be used to make a load balancing decision In global policies, the load balancer uses the performance profiles of all available workstations. In local policies workstations are partitioned into different groups. In a heterogeneous NOW, the partitioning is usually done such that each group has nearly equal aggregate computational power. The benefit in a local scheme is that performance profile information is only exchanged within the group.
The choice of a global or local policy depends on the behavior an applicationwill exhibit. For global schemes, balanced load convergence is faster compared to a local scheme since all workstations are considered at the same time. However, this requires additional communication and synchronization between the various workstations; the local schemes minimize this extra overhead. But the reduced synchronization between workstations is also a downfall of the local schemes if the various groups exhibit major differences in performance. notes that if one group has processors with poor performance (high load), and another group has very fast processors (little or no load), the latter will finish quite early while the former group is overloaded.