Matching the demand for resources ("load") with the supply of resources ("capacity") is a basic problem occurring across many fields of engineering, logistics, and economics, and has been considered extensively both in the Internet and in wireless networks. The ongoing evolution of cellular communication networks into dense, organic, and irregular heterogeneous networks ("HetNets") has elevated load-awareness to a central problem, and introduces many new subtleties. This paper explains how several long-standing assumptions about cellular networks need to be rethought in the context of a load-balanced HetNet: we highlight these as three deeply entrenched myths that we then dispel. We survey and compare the primary technical approaches to HetNet load balancing: (centralized) optimization, game theory, Markov decision processes, and the newly popular cell range expansion (a.k.a. "biasing"), and draw design lessons for OFDMA-based cellular systems. We also identify several open areas for future exploration. Mobile networks are becoming increasingly complicated, with heterogeneity in many different design dimensions. For example, a typical smart phone can connect to the Internet via several different radio technologies, including 3G cellular (e.g. HSPA or EVDO), LTE, and several types of WiFi (e.g. 802.11g, n, or ac), with each of these utilizing several non-overlapping frequency bands. Cellular base stations (BSs) are also becoming increasingly diverse, with traditional macrocells often being shrunk to microcells, and further supplemented with picocells, distributed antennas, and femtocells. This myth is deeply entrenched in the fields of communication and information theory, and indeed, even in the "five bars" display on virtually every mobile phone in existence. It was true conventionally, and still is "instantaneously". For example, the probability of correct detection for a given constellation is monotonically related to the detection-time SINR (i.e. any residual interference not removed by the receiver is treated as noise), as any communication theory text confirms. Outage is also usually thought of in terms of a target SINR, namely the probability of being below it. Further, information theory tells us that achievable data rate follows B log(1 + SNR), or B log(1 + SINR) if the interference is modeled as Gaussian noise, where B is the bandwidth. Thus, increasing the data rate seems to come down to increasing SNR (or SINR) -which yields diminishing returns due to the log -or acquiring more bandwidth. The critical missing piece is the load on the BS, which provides a view of resource allocation over time. Modern wireless systems dynamically allocate resources on the timescale of a millisecond, so even a 100 msec window (about the minimum perceptual time window of a human) provides considerable averaging. In contrast, classical communication and information theory as in the previous paragraph provide only a "snapshot" of rate and reliability. But the user-perceived rate is their instantaneous rate multiplied by the fraction of resources (time/frequency slots) they are allowed to use, which for a typical scheduling regime (e.g. proportional fair or round robin) is about 1/K, where K is the number of other active users on that BS in that band. This is pretty intuitive: everyone has experienced large drops in throughput due to congestion at peak times or in crowded events, irrespective of signal quality, e.g. "I have five 1 Henceforth, we shall include WiFi APs as a type of BS: one using unlicensed spectrum and a contention-based 3 bars, why can't I send this text message?!" The technical challenge is that the load K varies both spatially and temporally and is thus impossible to determine a priori for a particular base station. It is often hard even to find a good model for the load K: it is clearly related to coverage area, as larger cells will typically have more active users, but also depends on other factors like the user distribution, traffic models, and other extrinsic factors. A main goal of this paper is to introduce some recent approaches to load-aware cellular network models, along with an appreciation for the limitations of load-blind models. 2 Myth 2: The "Spectrum Crunch" It is a nearly universal article of faith that the amount of electromagnetic spectrum allocated to wireless broadband applications is woefully inadequate. Rather, what we have is an infrastructure shortage, not a spectrum shortage. Nearly everyone agrees that small cells should be added at a rapid pace to ease network congestion, and that this will be the key element to moving towards 1000x. However, the small cells (micro, pico, femto) will be deployed opportunistically, irregularly, and in fixed locations, and have a certain amount of resources they can provide (i.e. spectrum and backhaul). In stark contrast, the devices they serve move around, and sporadically request extensive resources from the network, while at other times are dormant. Thus, the load offered to each base station varies dramatically over time and space. Thus, a small cell network will require much more proactive load balancing in order to make good use of the newly deployed infrastructure. Of course, despite the above myths, many others in both industry and academia have recognized the importance of including load in the analysis of rate. The unifying point is that the modeling and optimization of load should be elevated to have a similar status as the amount of spectrum or the SINR. However, doing so in a technically rigorous manner is not straightforward. Outside of communication systems, load balancing has long been studied as an approach to balance the workload across various servers (in networks) and machines (in manufacturing) in order to optimize quantities like resource utilization, fairness, waiting/processing delays, or throughput. In emerging wireless networks, due to the disparate transmit powers and base station capabilities, even with a fairly uniform user distribution, "natural" user association metrics like SINR or RSSI can lead to a major load imbalance. As an example, the disparity between a max SINR and an optimal (sum log rate wise) association in a three tier HetNet is illustrated in Figure 1 Fundamentally, rate-optimized communication comes down to a large system-level optimization, where decisions like user scheduling and cell association are coupled due to the load and interference in the network. In general, finding the truly optimal user-server association is a combinatorial optimization problem and the complexity grows exponentially with the scale of the network, which is a dead end. We briefly overview a few key technical approaches for load balancing in HetNets. Since a general utility maximization of (load-weighted) rate, subject to a resource or/and power constraint, results in a coupled relationship between the users' association and scheduling, this approach is NP hard and not computable even for modest-sized cellular networks. Dynamic traffic makes the problem even more challenging, leading to a long-standing problem that has been studied extensively in queuing theory, with only marginal progress made, known as the coupled queues problem. One way to make the problem convex is by assuming a fully loaded model (i.e. all BS's always transmitting) and allowing users to associate with multiple BSs, which upper bounds the performance versus a binary association [3] . A basic form is to maximize the utility of loadweighted rate, subject to a resource or/and power constraint, where the binary association indicator is relaxed to a real number between 0 and 1. Following standard optimization tools, namely dual decomposition, a low-complexity distributed algorithm, which converges to a nearoptimal solution, can then be developed. As it can be observed in Figure 2 , there is a large (3.5x) 6 rate gain for "cell-edge" users (bottom 5-10%) and a 2x rate gain for "median" users, compared to a maximum received power based association.  Markov Decision Processes (MDPs) provide a framework for studying the sequential optimization of discrete time stochastic systems in the presence of uncertainty. The objective is to perform actions in the current state to maximize the future expected reward. In the context of HetNets, MDPs have been used to study handoff between different radio access technologies 7 provides a possible approach for self-organizing HetNets to combine the benefits of both centralized and distributed design. Game theory, as a discipline allows analysis of interactive decision-making processes, and provides tractable methods for the investigation of very large decentralized optimization problems. For example, a user-centric approach, without requiring any signaling overhead or coordination among different access networks, is analyzed in [6] . Another example is the study of dynamics of network selection in [7] , where users in different service areas compete for bandwidth from different wireless networks. Although game theory is a useful tool, especially for applications in self-organizing/dynamic networks, the convergence of the resulting algorithms is, in general, not guaranteed. Even if the algorithms converge, they do not necessarily provide an optimal solution, which along with large overhead may lead to inefficient utilization. Further, since the main focus of game theory is on strategic decision-making, there is no closed-form expression to characterize the relationship between a performance metric and the network parameters. Thus, although we are not convinced that game theory is the best analysis or design tool for HetNet load balancing, it could provide some insight on how uncoordinated UEs and BSs should associate. Biased received power based user association control is a popular suboptimum technique for proactively offloading users to lower power base stations and is part of 3GPP standardization efforts [8] [9] . In this technique, users are offloaded to smaller cells using an association bias. Formally, if there are K candidate tiers available for a user to associate, then the index of the chosen tier is (1) where B i is the bias for tier i and P rx,i is the received power from tier i. By convention, tier 1 is the macrocell tier and has a bias of 1 (0 dB). For example a small cell bias of 10 dB means a UE would associate with the small cell up until its received power was more than 10 dB less than the A natural question concerns the optimality gap between CRE and the more theoretically grounded solutions previously discussed. It is somewhat surprising and reassuring that a simple per-tier biasing nearly achieves the optimal load-aware performance, if the bias values are chosen carefully [3] (see Fig. 2 ). However, in general, it is difficult to prescribe the optimal biases leveraging optimization techniques. The previous tools and techniques seek to maximize a utility function U for the current network configuration, for which we characterized the gain in average performance as (2) where Ω is the set of solution space. However, alternatively assuming an underlying distribution for the network configuration, another problem can be posed instead as in (3), where the optimization is over the averaged utility. (3) The latter formulation falls under the realm of stochastic optimization, i.e. the involved variables are random. The solution to (3) would certainly be suboptimal for (2) -and already we observed the gap between an optimized but static CRE and the globally optimal solution in the last section -but has the advantage of offering much lower complexity and overhead (both computational and messaging) versus re-optimizing the associations for each network realization. Stochastic geometry as a branch of applied probability can be used for endowing base station and user locations in the network by a point process. By using Poisson point process (PPP) to model user and base station locations, in particular, tractable expressions can be obtained for key metrics like SINR and rate [11] , which then can be used for optimization. This approach also has the benefit of giving insights on the impact of key system-level parameters like transmit powers, densities and bandwidths of different tiers on the design of load balancing algorithms. As an example of the applicability of this framework, cell range expansion has been analyzed using stochastic geometry in [12] by averaging over all the potential network configurations, revealing the effect of important network parameters in a concise form. Modeling base stations as random locations in HetNets makes the precise association region and load distribution intractable. An analytical approximation for the association area was proposed in [12] , which was then used for load distribution (assuming uniform user distribution) and consequently the rate distribution in terms of the per tier bias parameters can be found [12] [13]. The derived rate distribution can then used to find the optimal biases simply by maximizing the biased rate distribution as a function of the bias value. We now explore several design questions that are introduced with load balancing. How much to bias? Can interference management help, how can it be done, and how much is the gain? As small cells will be continually rolled out over time, how (or does) the load balancing change as the small cell density increases? In this section we answer these questions, with the findings summarized in Table 1 . Bias Values. There are two major cases to consider for biasing: co-channel deployments (macro
The importance of load-balancing mechanisms in wireless networks has been discussed in detail in REF .
An Overview of Load Balancing in HetNets: Old Myths and Open Problems
ArXiv
ArXiv
Computer Science Mathematics