Load Balancing Technologies in WLAN

      In a wired distribution system, load balancing refers to a method used to uniformly distribute external service requests to multiple back-end servers to improve the quality of network services. Since tasks arrive randomly and node processing capability may be various from each other in a distribution system, some nodes may have too many tasks to be processed (called over-load), while others may be idling (called light-load). For over-load nodes, how to finish the tasks as soon as possible is an urgent affair; however, for light-load nodes it is actually a waste of resources. How to avoid the situation that busy nodes and idling nodes coexist in order to effectively improve resources usage and shorten average task response time? Load balancing is the answer to the problem.

      In a wired distribution system, a task is the operation object adopted in a load balancing method. The basic approach is to collect load information, make decisions with relevant algorithms, and reschedule allocated tasks by means of moving processes or tasks. In fact, the problem that is faced by load balancing is an issue of combinatorial optimization of tasks.

      However, when the technology of load balancing is applied to a wireless system, several new features appear. The load balancing technology encounters more problems than in a wired system. Due to mobility of STAs (stations) and time-variability of wireless channels in an Extended Service Set (ESS) of Wireless Local Area Network (WLAN) system, the Access Point (AP) load may be different from each other. The purpose of load balancing technology is to balance the load difference among APs so that network resources can be efficiently utilized. Since load balancing plays an important role in wireless resource management, IEEE 802.11 Working Group—Task Group v  (TGv) is especially focusing on the solution of load balancing problems in a WLAN system.

1 Load Balancing in a Wired Distribution System

1.1 Technical Difficulties of Load Balancing
The load balancing has to solve two main problems: when to move tasks; how to move tasks. To implement load balancing, the difficulties are explained from the following aspects:

• Precisely evaluate the load situation of a system.
• Load balancing requires extra processing capability, for example, to collect and save load information of nodes, make decisions, and move tasks. The extra processing capability brings more network and host overhead, therefore, system performance is impaired.
• Avoid the case of load jitter, that is, a task is frequently moved among nodes without being executed.
• Nodes are configured differently from the view of hardware or software. The matter of difference must be solved.
  

      In a wired network, currently the load balancing technology is mainly applied to service servers such as Web server, mail server, and E-business server.

1.2 Classification of Load Balancing Algorithms
There are different ways to classify the load balancing algorithms. In general, it may be divided into load status independent balancing and load status correlated balancing, according to the relation between balancing algorithm and load status. The former is called static balancing, and the latter is called dynamic balancing. The static algorithm of load balancing mechanically allocates requests from clients according to the fixed and regular mode without considering the running state of servers. However, the dynamic algorithm of load balancing is intelligent, which properly allocates the requests according to real load situations of servers.

      The load status independent balancing algorithm is based on previous experience or system collected information to distribute external tasks among nodes or to reallocate the existing tasks on some nodes. Because decision is made blindly without considering the current state of a system, this algorithm has very low accuracy and poor generality. Sometimes, opposite consequence may happen than expected, which makes the system more unbalanced, even deteriorating system performance.

      However, the load status correlated balancing algorithm is based on the current state of a system. It works in this way: according to the current load distribution situation, the algorithm can dynamically adjust tasks among nodes so that some tasks, having been allocated to an overload node, are moved to light-load nodes through communication equipment. By doing this, the system resource usage is improved and average task response time is shortened. The dynamic balancing algorithm usually contains 3 parts:
      (1) Collect load information of nodes. There are 3 methods to collect information: periodical collection strategy, command driven strategy, and changing status driven strategy.

      (2) Make decision based on collected load information. According to collected load information, a node will decide which pair of nodes (sending node and receiving node) needs load moving. In real situation, one or multiple pairs of nodes may need load moving.

      (3) Implement task moving among nodes. When load balancing is adopted, there are two task moving methods: preemptive task moving and non-preemptive task moving.

2 Load Balancing in WLAN System
Load balancing in a WLAN system is different from that in a wired distribution system at two aspects: control object and control mode. Due to the mobility of STAs and time-variability of wireless channels, the load balancing technology is more complicated in a WLAN system.

2.1 Features of WLAN
WLAN refers to a network comprising of inter-connected computers by using radio communication technology to implement intercommunication and resources sharing. WLAN Media Access Control (MAC) and Physical Layer (PHY) Specifications, ANSI/IEEE Std 802.11, 1999 Edition  [1] is developed by IEEE802.11 WLAN work group, helping WLAN and wireless equipment manufacturers to produce inter-working network equipment. At the physical layer, signal characteristics and modulation modes for data transmission are defined. The MAC layer provides a series of services, including information switching, power control, association management, synchronization management, and procedure management.

      A WLAN system has two network elements: AP and STA. APs, are fixed infrastructure equipment and interconnected through a wired distribution system. STAs, are mobile terminals and accessed to APs.

      A WLAN system has two types of network organizations: Independent Basic Service Set (IBSS) and Basic Service Set (BSS)[2]. The IBSS type of network is also referred to as Ad hoc network. In such a network, STAs are independently deployed to form a network element. In an ad-hoc network, there is no fixed infrastructure. All STAs are directly interconnected with each other, featuring independent. However, BSS type of network is called infrastructure mode. In such a network, at least one AP is used as network management device to manage all STAs, providing access and transmission services. In order to enlarge WLAN´s coverage and enhance STA´s mobility, number of BSSes may be combined together to build an Extended Service Set (ESS). Each ESS is identified by its ESS id (ESSID). The AP is distinguished by BSS id (BSSID). Multiple APs work in different wireless channels that are interconnected within a wired distribution system. One STA can move around freely in the ESS coverage are, even can be handed over from one AP to another AP within the ESS. Figure 1 shows the WLAN network architecture.

      Via a scanning channel, the STA can obtain ESS and BSS information in its surrounding WLAN system. Based on the information, the STA can choose a suitable BSS to join in. Load balancing technology is applied to a WLAN system in such a way that multiple APs provide accessing service for multiple mobile terminals. Each AP provides site management functions by using network information so that network resources can be efficiently utilized.

      As shown in Figure 1, more STAs are accessed to the center AP than other APs. The center AP services are so saturated due to supporting many STAs that QoS cannot be well guaranteed. However, the services of surrounding APs are not saturated yet. This phenomenon is called load difference. Load balancing technology is the answer to solve the problem to improve network capacity and QoS of the center AP by moving partial services from the center AP to its surrounding APs.

      When a STA enters a network, it must select an AP to connect. This is called the procedure of station accessing. An ordinary accessing procedure will pass through several steps: scanning, authentication, and connection. Generally, a STA can obtain several APs information by scanning an ESS. However, only the AP with the strongest signals will be selected. Due to the mobility of STAs and time-variability of wireless channels in a WLAN system, a STA may be handed over from one BSS to another BSS. This phenomenon is called handover in a WLAN, which will cause delay, even interruption of higher-layer services. Sometimes, handover may create "ping-pong effect", that is, STA may be frequently handed over between two APs or among multiple APs like ping-pong. Once a "ping-pong effect" occurs, load jitter may happen and network resources will be largely consumed.

2.2 Technical Difficulties of Load Balancing in a WLAN
Presently, IEEE802.11 standard doesn´t give description and requirements for load balancing. Network load distribution is entirely determined by STAs services, where STAs can randomly hand over. The disadvantages of a

      WLAN system without load balancing are explained below:
      (1) Reduced Wireless Network Efficiency and Performance
      As a whole, an ESS provides services for STAs. When a hotspot occurs, an AP load may exceed its upper limit. Because much traffic and many users compete for resources of the AP, causing its QoS deteriorated. This busy state may last for a long time. By contrast, its adjacent AP load is relatively low. Without load balancing, the entire network will be unstable. Therefore, the wireless network efficiency and performance are affected.

      (2) More Risk of Network Congestion
      Without load balancing, STAs will be handed over randomly and freely. When a hotspot occurs, many STAs may leave its original AP and swarm into the hotspot AP. In this case, handover is not guaranteed, that is, a STA may be unsuccessful to be handed over to a target AP. Once the services of the hotspot AP are saturated, no new STA can be accessed. Although the new STA can be accessed, congestion will be inevitable and all services will be interrupted.

      (3) Reduction of Network Tolerance
      Similarly, when the load of an AP is saturated, serious consequence may happen if a new STA is accessed. However, at the same time, other not-saturated APs are potentially capable of accessing new STAs and providing more services. If load balancing is adopted, it will be helpful to share the load of saturated AP. Finally, the load of all APs in the entire ESS may keep relatively stable and balanced so as to endure fluctuant and changing environment.

      (4) Poor Resources Usage
      Without load balancing, it is impossible for a network to make plans and schedule load distribution. As the load of one or several APs is saturated, other resources of not-saturated APs cannot be used.

      To sum up, if a network does not adopt load balancing, the network will be badly unstable due to random and uncontrollable features of services. When a hotspot occurs, it is very easy to see the congestion of STA. Therefore, the network will be partially paralyzed or QoS of STAs will be degraded.

      In a WLAN, the object of load balancing adjustment is different from a wired distribution system, where the objects in a wired system are tasks in queue. However, in a WLAN, tasks are undertaken by portable STAs. Although one STA can undertake multiple tasks, it is unable to segment the tasks. Hence, in a WLAN, it is STA that acts as an object to be controlled by load balancing algorithm, that means, the sum of all tasks of one STA are controlled by load balancing algorithm. Even during task moving, all tasks in one STA must be moved together. Therefore, STA is the minimum unit adjusted by load balancing algorithm in a WLAN. Task moving covers two aspects: handover and access control.

      A WLAN actually is a burst system, based on Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA). The WLAN system faces further technical difficulties in addition to that in the wired distribution system, such as time-variability of wireless channels, radio interference and mobility of STAs.

      (1) Difficult to Collect Load Information
      In an ESS, multiple APs work in different channels. Signals can be transmitted among APs in a Distribution System（DS）where private protocol is adopted. The IEEE802.11k aims at radio resource measurement. As for load information, it´s better to be measured by AP. However, there is no good method to exchange load information. Furthermore, another difficulty is how to quantify load information. For a packet-switching based WLAN, several factors must be considered in order to evaluate AP load level: traffic, QoS, number of STAs, transmit power, channel selection, and more. The reason to consider the number of STAs is that it will impact on the overhead of network management.

      (2) Difficult to Make a Decision
      Because of the mobility of STAs as well as the random and burst characteristics of tasks, something needs to be evaluated. At one time, load information is collected. The collected load information will be used later in a load balancing strategy. However, will it be effective to better adjust load? This needs to be fully considered to make a good decision. In addition, it is difficult to select a good adjustment target during load balancing. When a target participant is selected by load balancing algorithm, the participant will move the load through handover. It usually takes a STA above 100 ms to implement handover. Even in a case of fast handover, it still takes around 60 ms. Moreover, more than one object may be adjusted at a time. Therefore, after a period, network state is likely changed. Another problem is how to cut down the number of participants in order to reduce management overhead and avoid big fluctuation of the entire network.

      (3) Difficult to Move Tasks
      Task moving is accomplished through STA handover. Unfortunately, firstly, handover delay is generated, which may affect the other services of a STA. Secondly, network management overhead is introduced, which will not only burden AP, but also affect the performance of the entire network. In addition, in a WLAN network, the algorithm of load balancing must consider the risk of STA handover failure. Although AP can make a decision to move task or handover, the STA may be impossible to be accessed to light-load BSS. Therefore, the STA has to search a new AP after it disconnects from the old AP. Finally, the result of STA handover also determines if load balancing is convergent or not.

      Load balancing has become main concern by IEEE802.11v, that is dedicated to stipulate standard. Fast handover is the main content of IEEE802.11r. Actually, fast handover is tightly related to load balancing.

2.3 Classification of Load Balancing in a WLAN
In a WLAN, the technology of load balancing may be classified from two aspects. By load balancing originator, it may be classified into STA controlled load balancing and AP controlled load balancing. By load balancing solving mode, it may be classified into access-type load balancing and handover-type load balancing. The relevant classification diagram is illustrated in Figure 2.

2.3.1 STA Controlled Load Balancing
It is a fact that STA controlled load balancing is a self-motivated load balancing strategy. This is one characteristic of STA in a WLAN. Once handover is complete, network load is also transferred.

      It will be unilateral if only quality of signal is considered as STA handover condition. Presently, much research focuses on how to improve handover opportunity to precisely change load as expected. For instance, UT Starcom applied for a patent on April 27, 2004, named Load Balancing Method for Wireless Access Point (patent No. CN200410017978). In this patent, STA handover condition was extended. The number of accessed users or data throughput of all APs in an ESS must be compared before a STA is accessed to an AP.  Based on the comparison result, the STA will be accessed to the AP, which has either the smallest number of accessed users or the lowest data throughput. In this way, load balancing for APs in a WLAN is achieved. To sum up, in addition to the intensity of AP signal, number of accessed users and throughput can be considered in order to increase the precision of the target AP selection. However, the shortcoming of this method is that STA must check the status of AP in the process of handover or access. Because handover steps are added, handover time is prolonged. This is in breach of fast handover rule. To be delightful, research on the improvement of this method can be found, that is, AP periodically broadcasts its throughput and number of access users. By doing this, the quality of signal and load situation can be obtained through background scanning but the network overhead is unfortunately increased.

      The advantages of STA controlled load balancing are:

• STA knows its service demand and environment very well;
• After background scanning, STA can obtain a highly precise and available BSS;
• Handover loss is undertaken by STA because it is the STA that is handed over or accessed and the services are carried on STA.
  

      The disadvantages are:

• STA only knows the situation of terminal side;
• STA is not clear about the whole network environment;
• If STA is randomly handed over, the whole ESS may be disturbed so that the entire network cannot gain excellent effect of load balancing.

2.3.2 AP Controlled Load Balancing
The start points of AP controlled load balancing are: AP is located at network side; wired cables are used to connect APs so that load balancing related information can be transferred among APs without affecting STA services.

      According to the load balancing information, ESS can find out which AP is loaded heavily, which AP is loaded lightly. Based on the obtained information, it is possible the ESS makes decisions to fulfill the purpose of intra-ESS load balancing. For example, because many STAs are accessed to heavy-load AP, partial STAs may be handed over to less-loaded AP; or a restriction is given to prohibit a new STA from being accessed to heavy-load AP. In this case, the new STA is only allowed to accessed to less-loaded AP.

      Many research efforts are put into AP controlled load balancing method now. Lenovo (Beijing) Corp. applied for a patent on September 24, 2003, named One AP-based Load Balancing Method (patent No.: CN200303134660). In the patent, the load balancing method is explained as: each wireless AP can determine whether to allow new STA be accessed or not according to the current network situation of load distribution, obtained through the communication among APs. If the AP load is high, it will refuse new STA to be accessed, thereby, the load balancing is achieved. IBM applied for a patent on June 26, 2002, named Access Point Initiated Forced Roaming Based upon Bandwidth (patent No. US20040001467). In this patent, a load balancing method is mentioned, which is achieved by controlling STA from moving and roaming. A wireless AP monitors the bandwidth utilization of all STAs accessing to the AP. If the AP load is abnormal, a STA will be selected and forced to roam to another AP. Therefore, the load balancing is achieved.

      ZTE has carried deep research in this area and has gained many achievements. For example, Wang Zhanli applied for a patent on March 10, 2004, named A Method to Implement Load Balancing Among AP Equipment in a WLAN (patent No.: CN200410008410). The following method is adopted to implement load balancing. One AP is selected as main control point by means of interactive messages among multiple APs. The main control AP allows mobile wireless terminals to be accessed. While, other APs are called standby access points so that they will refuse any accessing request from mobile wireless terminals. Generally, the load balancing method must depend on external service controller of AP, or is only applicable of a specific group of STA users. This method has overcome the weak point. Meanwhile, it provides a way to effectively utilize network resources to implement dynamic load balancing among APs.

      The advantages of AP controlled load balancing are:

• Through a wired distribution system, the overall network situation may be precisely and timely collected;
• It is convenient from the aspect of resources coordination and scheduling;
• An overall strategy is easy to be carried out;
  

      The entire network will be quickly adjusted through the load balancing method.

      Just like one coin has two sides, this method has its own weak point: STA position, STA surrounding network environment and STA scanned AP situations are blind to network side. Therefore, this method has a risk of wrong handover decision.

2.3.3 Access-type Load Balancing
The principle of access-type load balancing is to control the accessing of STA to achieve load balancing. When the load of an AP exceeds a threshold, it will refuse any accessing request from new STA. In this case, the STA has to search a less-loaded AP to access. By using this method, the load balancing is achieved to some extend.

      Since the access-type load balancing is to control new STA from being accessed or to control STA from being reconnected after handover, it belongs to passive load balancing method. The convergence rate of load balancing adjustment will be low. In extreme case, the network will remain unbalanced all along if there is no new STA to be accessed and all accessed STAs keep the existing connections.

2.3.4 Handover-type Load Balancing
The principle of handover-type load balancing is to control the handover of STA to achieve the load balancing. In an ESS, if one AP is overloaded, ESS or a terminal will control the STAs connecting to the AP to be handed over to another AP so that load sharing is achieved. However, if the load of one AP is minimal, ESS or a terminal will control the STAs connecting to other APs to be handed over to the less-loaded AP. This handover-type load balancing ensures a load balanced ESS.

      One feature of handover-type load balancing is the quick response. Once a load difference occurs, it can be quickly adjusted through handover. One disadvantage of handover-type load balancing is that handover may bring loss to STAs. The possible risks are that the handover may be failed and high layer service may be interrupted. Furthermore, the handover-type load balancing must rely on fast handover technology. If the effect of fast handover is bad, more losses will be after load balancing adjustment.

      Presently, how to combine AP controlled method and handover-type load balancing method becomes a hot topic for research. With the combined method, not only precise information can be collected, but also it is possible to make quick response. Finally, the ESS load distribution can be actively adjusted.

      The original purpose of the load balancing is to optimize network operation, uniformly distribute network load, increase network resource usage as high as possible, and improve network performance. But as network management behavior, the load balancing brings extra overhead, for instance, network overhead caused by load information interaction, network management overhead caused by load balancing adjustment. Even STA handover needs network overhead. As the numbers of APs and STAs increase in an ESS, more network resources have to be spent to maintain a balanced load. Therefore, the network performance will be influenced and degraded.

      The load balancing has a risk of failure to adjust load. Handover may be failed and an isolated node may exist. Once the handover of a STA is failed, it has to search for a new AP. In this case, high layer service is inevitably interrupted. Moreover, the handover is interference to the reliable network environment. Too frequent handover may cause jittered network performance, possibly creating "ping-pang effect". If this happens, the entire network will be turbulent and unstable for a long time.

3 Load Balancing Technology in TD-SCDMA
The TD-SCDMA is a Time Division Synchronous Code Division Multiple Access system. Load balancing plays an important role in Radio Resource Control (RRC) of UMTS Terrestrial Radio Access Network (UTRAN). In a TD-SCDMA system, time and code channel resources are very limited. Large traffic is circuit switching services, which demand high QoS. Therefore, the load balancing is very important in a time-division system.

      In a time-division system, load balancing has multiple granules. In addition to UE handover, the load balancing can control load distribution based on each slot. Different from a WLAN, some load balancing methods in a time-division system sacrifice UE services as cost, for example, stop packet data service for a while, force a user to drop a call or interrupt circuit switching service. By doing this, UE resources are forcedly released.
Generally, in a TD system, the feasible load-control measures are: 

• Force some users to drop calls.
• Implement load balancing among different slots of the same Node B.
• Control downlink fast load power: refuse downlink fast power adding command from UE.
• Control uplink fast load power: decrease uplink targets used in the uplink fast power control.
• Reduce packet data throughput.
• If multiple carriers are supported, hand over to another TD-SCDMA carrier.
• Hand over to GSM or other mobile communication system.
• Reduce bit transmission rate of Mobile Station (MS), that is, Adaptive Multi Rate (AMR) voice service.
• Reduce Node B transmittal power to lessen its coverage. Therefore, some UEs are forcedly handed over to other cells.
  

      To be mentioned that the first 4 measures can be carried out in one Node B. Fast speed is its feature. The measures are taken into effect even within one slot. Because QoS guaranteed services cannot tolerate delay caused by retransmission, measures should be taken to ensure the demand of QoS. It may be achieved by increasing the FER (Frame Error Rate) of those links, which are insensitive to delay. By doing this, on one hand, packet-based data service will have longer delay. On the other hand, the quality of circuit switching based services (e.g. voice and videophone) will be ensured.

      In a TD-SCDMA system, the load balancing methods are varied because of the difference of system granules. In general, any load balancing method must contain three steps: load information collection, load assessment, and task transition. However, it has another two features in TD-SCDMA system: CDMA and TDD.

4 Conclusion
Research on load balancing technology in a WLAN system is a new topic. The WLAN application environment is different from a wired distribution system, therefore, the load balancing in WLAN faces problems that are more complicated. A good load balancing method can effectively improve the network efficiency and resources usage, reduce the system congestion probability, increase the system capability to counteract the changing of load and enhance system tolerance. The load balancing in a WLAN must follow the following rules:

• Precisely assess load status of each AP, and exchange load information as soon as possible. The exchanging of load information should not have influence on QoS.
• A high efficient balancing algorithm can precisely select the executor that will execute the load balancing adjustment. Meanwhile, handover and access modes shall be adopted. How to quicken convergent speed of load balancing adjustment is an issue that balancing algorithm must pay more attention to.
• Combine fast handover management and control to avoid handover competition and congestion among multiple STAs under the same AP.
• Reduce negative influence caused by load balancing, reduce network overhead and take effective measures to avoid frequent handover and handover failure.

References
[1] IEEE 802.11b. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. 1999.
[2] GEIER J. 无线局域网[M]. 北京:人民邮电出版社, 2003.

Manuscript received: 2005-12-27