Spatial Load Balancing in Wide-Area Wireless Networks

1 Introduction
    Demand for data in wireless networks is spatially non-uniform, which leads to chokepoint sectors, and it is also time-varying, which means that chokepoint sector locations change. Chokepoint sectors operate at or close to the maximum load; therefore, they determine network performance, user perception of network performance and, ultimately, user experience. In a network with fixed assets and unbalanced loading, spatial load balancing uses network resources from neighbors of chokepoint sectors to serve users in the chokepoint sector. This increases the capacity of the network.

    Field data collected from commercially deployed networks shows that only a small fraction of sectors are chokepoints at any given time and that chokepoint sectors typically have several lightly loaded neighbor sectors. Fig. 1 shows the distribution of sector loading (per-sector forward link (FL) slot use) during peak hour in a metropolitan commercial EV-DO network where sectors with low slot use are lightly loaded. Operators add hardware by splitting cells near the chokepoint sectors or increase bandwidth by adding carriers to the chokepoint sectors. Such actions lead to networks that are designed for worst-case scenarios and are therefore underused most of the time.

    The spatial load-balancing techniques discussed in this paper are network load balancing (NLB) and single-carrier multilink (SCML).

    In NLB, a device is opportunistically reassigned from a heavily loaded sector to a lightly loaded sector, even if the channel quality of the heavily loaded sector is better. The end result is increased capacity for the chokepoint sector from offloading the most expensive users (poor channel quality means that the network has to allocate more resources for a given amount of traffic) to the neighbor sector.

    With SCML, any device that can simultaneously process two or more independent data streams can achieve the benefits of a multicarrier network, even though the device may be in the hand-off region of a single-carrier deployment.

    With multicarrier EV-DO, the EV-DO carriers that serve a mobile device use different carrier frequencies and may originate from the same cell or different cells. With SCML, the same carrier frequency serves the mobile device with independent data streams and from different sectors. NLB improves performance when the chokepoint sector is loaded, and SCML improves performance at all load levels. In this paper, we describe how these techniques augment load-balancing in the frequency domain.

    In Section 2, we provide necessary background information. In sections 3 and 4, we discuss the concepts, algorithms, and implementations of NLB and SCML. In section 5, we perform simulations to determine the performance of NLB and SCML. In section 6, we make concluding remarks and discuss future work.

2 Background

2.1 Server Selection
    When the access terminal (AT) in a wireless network has a choice of serving sectors, it typically selects the server with the best channel quality. (Here, hysteresis based on channel quality and time is not discussed for the sake of simplicity.) In EV-DO, the AT selects the best forward layer (FL) server from the candidate servers that have a corresponding reverse link (RL) of acceptable quality.  If the DRCLock bit on, the RL quality is acceptable; if the DRCLock bit is off, the RL quality is unacceptable. The DRCLock bit itself is set according to the quality of the RL overhead channels received at the base station.

2.2 Multicarrier Operation
    When an AT in EV-DO is assigned multiple carriers, those carriers may originate from the same sector or different sectors (one forward-link serving sector for each carrier) [1], [2]. Commercial EV-DO uses independent schedulers on each sector carrier, and multicarrier EV-DO uses multilink radio link protocol (RLP) on each sector carrier. Multilink RLP enables the network to split a data stream at the transmitter across multiple independent schedulers and to combine the data stream at the receiver while ensuring early detection of packet loss and in-order delivery of RLP packets [3]. When multiple links (or carriers) are assigned to an AT, the network distributes forward-link data across available links. Data throughput on each link can be different, and the throughput varies over time. Enhanced flow control (EFC) ensures FL data is distributed across links according to link throughput and that the data distribution adapts to changes in link throughputs.

    Each forward link in EV-DO requires reverse-link feedback to indicate FL channel quality and acknowledgements (ACK/NACK) for physical-layer HARQ. EV-DO supports multiple feedback multiplexing modes. RL overhead of multiple FL carriers can be transmitted over a single RL carrier to minimize the RL pilot overhead.

2.3 FL Load Metrics
    We introduce a new metric for the loading at each sector. This metric is the average number of non-empty queues at the sector carrier. It is calculated for each slot (which takes 1.66 ms) and is fed to a filter with a time-constant of a few seconds to generate the Neff metric.

    Networks are at times backhaul-limited, and this leads to the air link at the BTS being underused. A backhaul-limited sector-carrier may not appear to be loaded because of queue under-run. Therefore, backhaul limit must be accounted for when calculating loading level at each sector-carrier. A metric for backhaul limit is the number of unfilled flow control requests for a sector-carrier that has non-empty AT queues at the BSC.

2.4 Operator Deployments
    Operators deploy wireless data networks according to data demand. Hence, operator deployments are not uniform and have spatial variations in the number of carriers deployed. Typically, a large area in an operator network has three or less deployed carriers. In regions of the network with just one carrier, multicarrier EV-DO cannot improve performance of ATs with multicarrier capability.

2.5 Smart Carrier Management
    EV-DO access networks (ANs) assign the best-available carrier to an AT by transporting the load levels across carriers (on the forward and reverse links) and the channel quality from the ATs to each of the candidate carriers.

3 Network Load Balancing
    NLB is shown in Fig. 2. PN (b) is the best FL sector for the user; however,
PN (b) is heavily loaded and the neighboring sector, PN (a), is lightly loaded. If PN (b) is selected as the serving sector, it has better signal-to-interference plus noise ratio (SINR) than PN (a) but is scheduled much less time than in PN (a) because of heavy loading. Thus, even at the cost of FL SINR degradation, the AT’s throughput can increase when the FL loading differential is sufficient to offset the SINR degradation.

    An important consideration in NLB is its interaction with the partial loading of neighboring sectors. The SINR of the traffic channel in the chokepoint sector is higher than the SINR of the pilot channel (only applicable to EV-DO) because of lesser interference from the lightly loaded neighboring sector. If the AT is served by the lightly loaded neighbor, then the chokepoint sector with high neighbor loading gives strong interference. If a network has a large number of ATs with the ability to spatially null the strong interferer, the network can gain more from NLB. In addition, offloading users to lightly loaded neighboring sectors drives those sectors towards higher slot use, and these sectors then cause more interference to the chokepoint sector. This effect limits the loading differential across sectors where NLB is beneficial. The NLB algorithms also specify minimum FL channel quality to ensure the AT does not choose an extremely weak FL server, regardless of the load difference between neighboring sectors. This allows the AT to continue to receive the FL control channels with the desired performance. There are two types of NLB algorithm: one for existing ATs deployed by operators and another for new ATs.

3.1 Network Load Balancing for Legacy ATs 
    Implementation of the NLB algorithm for legacy ATs does not require the AT to have any additional capability. Each sector-carrier periodically provides its load information (Neff) to the BSC. The BSC also receives FL pilot strength information from ATs via a RouteUpdateRequest in EV-DO every 2 to 4 seconds. With this information, the BSC can select suitable legacy ATs and induce them to change serving sectors by setting the DRCLock bit (RL quality indicator) that corresponds to the chokepoint sector to off (indicating poor RL quality).

3.2 Network Load Balancing for New ATs
    The AN assists NLB for new ATs. Each sector-carrier periodically provides its Neff to the BSC. The BSC propagates this to all members in the neighbor list of each sector-carrier. Each sector-carrier periodically broadcasts its load level — as well as the load level for all sector-carriers in its neighbor list — on the synchronous control channel. The server selection algorithm at the access terminal then uses not only FL channel quality and RL channel quality (DRCLock bit) but also the FL load level from the candidate serving sectors on each carrier. The server selection metric is modified to use the FL channel quality and the FL load level, and the constraint whereby the AT selects a serving sector from sectors with acceptable RL quality is maintained.

4 Single-Carrier Multilink
    EV-DO ATs are multicarrier enabled, which means they can receive data on multiple links regardless of whether these links are from the same sectors on the same carrier. This capability can be harnessed with SCML to allow multicarrier-enabled ATs to have improved performance even in regions of the network with less than three carriers. Because SCML is beneficial only in handoff regions (typically characterized by lower SINR and less-than-ideal performance), it delivers gains where they are needed most. With SCML, the network can serve the AT using multiple servers on a carrier. Each FL server creates a link between the AN and AT. SCML allows multiple links on a single carrier, and that is why it is called single-carrier multilink. An AT’s active set are those sectors that control the power of the AT on the RL and can serve the AT on the FL. SCML enhances FL data rate when all sectors in the AT’s active set are lightly loaded, and it balances the load when some chokepoint sectors are in the AT’s active set.  For an AT that can receive FL data from n links simultaneously, SCML allows the AN to assign additional links and enhance FL throughput when the number of carriers assigned to AT is < n  and the AT has multiple sectors in the active set. SCML leverages the advantages of EV-DO, and in the following, we explain some changes to existing EV-DO.

4.1 Reverse Link Feedback Multiplexing
    For each additional link assigned using SCML, an additional set of RL feedback channels is required. This is sent over a single RL carrier using reverse link feedback multiplexing. The multiplexing is supported by methods such as basic feedback multiplexing (BFM) and enhanced feedback multiplexing (EFM).

4.2 Distributed Network Scheduling
    The network can more flexibly schedule FL data when an AT is served on multiple links. Distributed network scheduling (DNS) improves network efficiency by biasing FL data delivery towards a better link [4]. When FL slot use is 100%, DNS fairly schedules across all ATs regardless of the number of links assigned. When FL slot use is less than 100%, DNS allows SCML ATs to achieve some trunking gain by using free slots on each link, which results in a higher FL data rate for SCML ATs.

4.3 Receiving Diversity and Interference Nulling
    An SCML AT may be simultaneously served from multiple links on same carrier, resulting in self interference. The AT is simultaneously served from two sectors that interfere with each other. Even if no other AT is present in the system, each link assigned to the SCML AT receives interference from another link(s). To achieve gains from multiple links, the AT must overcome the interference. Some EV-DO receiving diversity implementations can spatially null a strong interferer, and this is the key to SCML. The network should limit SCML assignment to receiving diversity ATs with spatial nulling capabilities. ATs with more Rx antennas are typically capable of superior spatial nulling of strong interferers, and therefore, SCML performance improves with an increase in number of AT Rx antennas.

4.4 Smart Carrier Management
    The smart carrier management algorithm can be modified to take the SCML capability of a device into account. The network allocates and removes SCML based on signal conditions, and this ensures that additional links can provide reasonable throughput. Links across carriers are preferred because they are orthogonal and provide trunking (multiplexing) gain. If the AT can support more links than assigned carriers, AN uses SCML to assign additional links on a carrier according to available FL control resources and RL load on that carrier. The additional links provide trunking gain in the spatial dimension. Once the AT server selection algorithm has been assigned multiple links by the smart-carrier management algorithm, the AT server-selection algorithm chooses the best link(s) by using the FL channel quality and FL load. This is similar to the NLB algorithm for new ATs. The AN has multiple paths that it can use to serve FL data, and DNS allows network throughput to be optimized.

5 Performance
    Simulations reveal the performance gained using NLB and SCML. The performance results are valid for a seven-cell layout with a center-cell demand model; that is, the center cell has multiple times the number of users of neighboring cells. The ratio of the number of users in the center cell to users in the neighboring cell is the demand ratio. Except for Fig. 3, which shows load-balancing gain as a function of demand ratio, all other figures are valid for a demand ratio of three. Users have an http traffic model; that is, they repeat downloading a sample http webpage according to a random arrival process with a fixed rate. To determine performance in a particular scenario, for example, dual-antenna or dual-carrier devices with load balancing enabled, simulations are performed for a range of download rates. Each simulation is then characterized in terms of download rate (the average number of webpages downloaded per minute per high-demand sector-carrier) and the tail of the page delay. The tail of the page delay is defined as follows: The delay for each downloaded http page is the time between when the first byte of the page is queued in the BSC to the time the last byte is downloaded by the user. Then, the page delay CDF (across all users and all webpages) is formed, and the ninety percentile delay is chosen as the tail page delay. The tail page delay versus rate curve for the scenario is then formed from all such rate-delay pairs. Both single and dual-antenna devices are simulated. Single and multicarrier devices are also simulated.

5.1 Load-Balancing Gain for Single-Carrier Devices
    Fig. 4 shows the tail page delay versus rate curves for single-carrier devices with one or two antennas. Load balancing provides significant gain only when the load level is sufficiently large, that is, when the solid red and blue curves (which represent the baseline and new NLB cases for two-antenna devices, respectively) fall on top of each other at low rates. Because of the low load differential at low load levels, no user is offloaded to another sector and there is no load balancing gain. Also in Fig. 4, the load-balancing gains for single-antenna devices (new or legacy) are not as large as those for dual-antenna devices. Once a user is offloaded from a heavily loaded sector to a lightly loaded one, the heavily loaded sector appears as a strong interferer. This occurs because the user receives a stronger signal from the heavily loaded sector than from the lightly loaded one. Dual-antenna devices can spatially null some of the interference. Single-antenna devices lack such capability and thus achieve lower load balancing gains. Multiple receiving antennas and special null of a strong interferer becomes even more important for SCML because users usually suffer self-interference. Consequently, NLB and SCML are recommended only for dual-antenna devices.
Fig. 4 also shows that although the load-balancing gain for legacy devices is not as large as the gain for new devices, they are comparable. The gain is reduced because the BSC, which induces load balancing for legacy terminals, does not have accurate information about user SINR.

    Fig. 3 shows that the load-balancing gain increases with the demand ratio, that is, the ratio of users in the center cell to users in the neighbor cell. This is a result of more users being offloaded from the heavily loaded center cell to the lightly loaded neighboring cells as the demand differential increases. Load balancing provides substantial gains over a wide range of demand ratios.

5.2 Load-Balancing Gain for Multicarrier Devices
    Fig. 5 shows the tail page delay versus rate curves for single and multicarrier devices (the maximum number of assigned carriers is two). The single and multicarrier devices have two antennas. Load-balancing gain improves when a second carrier is added. As carriers are added, users experience trunking (multiplexing) gain. The horizontal distance between the magenta and red curves in Fig. 5 represents the trunking gain of dual-antenna devices when a second carrier is added. Trunking gain is also a function of load level. As the load level increases, the trunking gain decreases. The magenta and red curves in Fig. 5 merge as rate is sufficiently increased. Both baseline and NLB cases achieve trunking gain when a second carrier is added; the trunking gain achieved in the latter case is more substantial because some users hand off to lightly loaded neighbors.

    In these cases, there is a dual benefit from NLB—spatial load-balancing combined with load-balancing in the frequency domain—and this magnifies the gains from spatial load balancing. NLB combined with multicarrier deployments increases network capacity when the network is loaded and also substantially improves UE. This means faster web-page downloads when the network is not as loaded.

    Fig. 6 and Fig. 7 show the relationship between load balancing and trunking gains for two-antenna devices at low (7 second tail page delay) and high (13 second tail page delay) load levels. Specifically, X in Fig. 6 denotes the network capacity for a single-carrier deployment with dual-antenna devices were the tail page delay does not exceed 7 seconds. The coefficients in Fig. 6 represent the per-carrier network capacity gain when load balancing is enabled or additional carriers are added. At low load levels, per-carrier trunking gain (63%) created by adding a second carrier is much larger than the gain from load balancing (5%). NLB provides significant gain when sectors are sufficiently loaded; trunking gain is greater when load level is smaller. In contrast, Fig. 7 shows that at high load levels, load balancing provides the same gain (26%) as adding the second carrier. Thus, combining multicarrier deployments with per-carrier load balancing provides substantial gain over a wide range of load levels.

5.3 SCML Performance
    Fig. 8 shows FL burst rate as a single-carrier user moves between two neighboring cells. With no SCML, a user’s burst rate reduces as the AT moves away from the center of the cell and approaches the cell edge. The burst rate starts increasing again as the AT approaches the center of the neighboring cell. With SCML, a user’s burst rate is significantly improved near the cell edge because the user is served by two sectors at the cell edge. Thus SCML can provide ATs with a more uniform UE as the user moves within the network.

    Fig. 9 shows the tail page delay versus rate curves for dual-antenna single-carrier devices. The cluster consists of seven sectors, and the center sector has three times the number of users of its neighboring sectors. Load balancing provides substantial gains only when load level is high, whereas SCML provides substantial gains at all load levels. At low load levels, SCML exploits spatial trunking across sectors, whereas at high load levels, SCML asymptotes to NLB where the AT is effectively served by one sector only. Single-carrier multilink is therefore a form of soft-network load balancing.

6 Conclusions
    This paper gives an overview of load balancing in the spatial dimension. NLB and SCML are introduced, and related algorithms, implementation, and performance are presented. We also show that load balancing in the spatial dimension and frequency dimension can be combined to amplify gains in networks where capacity is constrained. The proposed methods are fully backward compatible and leverage the advantages of EV-DO networks thus increasing the return on investment for these networks. NLB, in particular, is applicable to legacy devices.  These techniques improve user experience when the sector is not operating at load.
Further improvements to NLB and SCML can be made with higher-order receiving diversity at the device. This enables further improvements in spatial nulling, which allows the device to be simultaneously served by even more sectors on the same carrier.

    Similar techniques, such as single-frequency dual cell (SFDC), are being developed for UMTS networks and are applicable to LTE networks as well. NLB and SCML are both applicable to local-area wireless networks.

References
[1] CDMA2000 High Rate Packet Data Air Interface Specification, 3GPP2 C.S0024-C version 1.0, April 2010.
[2] R. Attar, D. Ghosh, C. Lott, Mingxi Fan, P. Black, R. Rezalifar and P. Agashe, “Evolution of CDMA2000 cellular networks: multicarrier EV-DO,” IEEE Commun. Mag., vol. 44, Issue 3, pp. 46-53, Mar. 2006.
[3] CDMA 2000 High Rate Packet Data Supplemental Services, 3GPP2 C.S0063-B version 1.0, May 2010.
[4] R. Gowaikar, C Lott, A. Jafarian, D. Ghosh, K. Azarian and R. Attar, “Distributed Scheduling for Wireless Networks,” in Proc. IEEE ISIT, 2011.

Kambiz Azarian (kambiza@qualcomm.com) received his Ph.D. in electrical engineering from Ohio State University. He joined Qualcomm in 2007 and has since been working on 3G and 4G cellular systems.
 
Ravindra Patwardhan joined Qualcomm in 1998. He has worked on ISDN, Globalstar, Telematics, 1xRTT, 1xEV-DO, and UMB.
 
Christopher Lott received his Ph.D. in control theory from the University of Michigan. He has worked on 1xEV-DO systems design for more than 10 years and is currently the DO systems lead at Qualcomm. He has designed aspects of communications systems, including LTE, GPS, and Inmarsat.
 
Donna Ghosh received her M.S. and Ph.D. degrees from Pennsylvania State University. She joined Qualcomm in 2003 and has been working on 1xEV-DO system design and standardization with an emphasis on MAC design. Her research interests include resource allocation, distributed algorithms, and wireless systems.
 
Radhika Gowaikar received her M.S. and Ph.D. degrees in electrical engineering from California Institute of Technology. She joined Qualcomm in 2006 and is interested in distributed algorithms for resource allocation in wireless networks. She has worked on these for the 1xEV-DO system.

Rashid Attar received his B.E. in electronics from Bombay University in 1994 and his MSEE from Syracuse University in 1996. He is a senior director of engineering in Corporate Research and Development (CR&D), Qualcomm. He joined Qualcomm in 1996 and was first engaged in the integration of IS-95 systems. Since 1998, he has worked on the system design, prototype, development, standardization, and commercialization of 1xEV-DO (Rev0, RevA, RevB, and DO-Adv) and 1x-Adv. He is currently co-lead of the CR&D DO-Advanced effort and acting lead of the Qualcomm CDMA Technologies (QCT) CDMA2000 modem systems team.

[Abstract] Load balancing is typically used in the frequency domain of cellular wireless networks to balance paging, access, and traffic load across the available bandwidth. In this paper, we extend load balancing into the spatial domain, and we develop two
approaches—network load balancing and single-carrier multilink—for spatial load balancing. Although these techniques are mostly applied to cellular wireless networks and Wi-Fi networks, we show how they can be applied to EV-DO, a 3G cellular data network. When a device has more than one candidate server, these techniques can be used to determine the quality of the channel between a server and the device and to determine the load on each server. The proposed techniques leverage the advantages of existing EV-DO network architecture and are fully backward compatible. Network operators can substantially increase network capacity and improve user experience by using these techniques. Combining load balancing in the frequency and spatial domains improves connectivity within a network and allows resources to be optimally allocated according to the p-fair criterion. Combined load balancing further improves performance.

[Keywords] CDMA 2000; EV-DO; DO-RevC; high rate packet data (HRPD); network load balancing (NLB); single-carrier multilink (SCML)