Fairness and Load Balancing in Wireless LANs Using Association Control

The traffic load of wireless LANs is often unevenly distributed among the access points (APs), which results in unfair bandwidth allocation among users. We argue that the load imbalance and consequent unfair bandwidth allocation can be greatly reduced by intelligent association control. In this paper, we present an efficient solution to determine the user-AP associations for max-min fair bandwidth allocation. We show the strong correlation between fairness and load balancing, which enables us to use load balancing techniques for obtaining optimal max-min fair bandwidth allocation. As this problem is NP-hard, we devise algorithms that achieve constant-factor approximation. In our algorithms, we first compute a fractional association solution, in which users can be associated with multiple APs simultaneously. This solution guarantees the fairest bandwidth allocation in terms of max-min fairness. Then, by utilizing a rounding method, we obtain the integral solution from the fractional solution. We also consider time fairness and present a polynomial-time algorithm for optimal integral solution. We further extend our schemes for the on-line case where users may join and leave dynamically. Our simulations demonstrate that the proposed algorithms achieve close to optimal load balancing (i.e., max-min fairness) and they outperform commonly used heuristics.     

Computing Optimal Max-Min Fair Resource Allocation for Elastic Flows

In this paper, we consider the max-min fair resource allocation problem as applied to elastic flows. We are interested in computing the optimal max-min fair rate allocation. The proposed approach is a linear programming based one and allows the computation of optimal routing paths with regard to max-min fairness, in stable and known traffic conditions. We consider non-bounded access rates, but we show how the proposed approach can handle the case of upper-bounded access rates. A proof of optimality and some computational results are also presented     

Utility Max-Min Flow Control Using Slope-Restricted Utility Functions

We present a network architecture for the distributed utility max-min flow control of elastic and nonelastic flows where utility values of users (rather than data rates of users) are enforced to achieve max-min fairness. The proposed link algorithm converges to utility max-min fair bandwidth allocation in the presence of round-trip delays without using the information of users' utility functions. To show that the proposed algorithm can be stabilized not locally but globally, we found that the use of nonlinear control theory is inevitable. Even though we use a distributed flow-control algorithm, it is shown that any kind of utility function can be used as long as the minimum slopes of the functions are greater than a certain positive value. Though our analysis is limited to the single-bottleneck and homogeneous-delay case, we believe that the proposed algorithm is the first to achieve utility max-min fairness with guaranteed stability in a distributed manner     

Distributed Transmit Power Control for Maximizing End-to-End Throughput in Wireless Multi-hop Networks

Wireless multi-hop networks have a solidarity property, in which each multi-hop link interferes mutually and so an increase in one link’s rate results in a decrease of the other links’ rate. In a multi-hop link, the end-to-end throughput between a source and destination is restricted by the lowest link rate, so the max-min fair allocation on the link rates is an optimal strategy to maximize the end-to-end throughput. In this paper, we verify that if the wireless links have a solidarity property, the max-min fair allocation has all link rates equal, so we propose a transmit power control (TPC) algorithm that decides the transmit power of multi-hop nodes to equalize all link rates. The proposed algorithm operates in a distributed manner, where each node averages the recognized link rates around itself, allocates its transmit power to achieve this average rate, and iterates this operation until all link rates become equal. Intensive simulation shows that the proposed TPC algorithm enables all link rates to converge on the same value, and thus maximizes the multi-hop end-to-end throughput while decreasing the power consumption of multi-hop nodes.     

Application-Oriented Flow Control: Fundamentals, Algorithms and Fairness

This paper is concerned with flow control and resource allocation problems in computer networks in which real-time applications may have hard quality of service (QoS) requirements. Recent optimal flow control approaches are unable to deal with these problems since QoS utility functions generally do not satisfy the strict concavity condition in real-time applications. For elastic traffic, we show that bandwidth allocations using the existing optimal flow control strategy can be quite unfair. If we consider different QoS requirements among network users, it may be undesirable to allocate bandwidth simply according to the traditional max-min fairness or proportional fairness. Instead, a network should have the ability to allocate bandwidth resources to various users, addressing their real utility requirements. For these reasons, this paper proposes a new distributed flow control algorithm for multiservice networks, where the application's utility is only assumed to be continuously increasing over the available bandwidth. In this, we show that the algorithm converges, and that at convergence, the utility achieved by each application is well balanced in a proportionally (or max-min) fair manner     

Cross-Layer Design for End-to-End Throughput and Fairness Enhancement in Multi-Channel Wireless Mesh Networks

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.     

Outage Minimization and Rate Allocation for the Multiuser Gaussian Interference Channels With Successive Group Decoding

We consider a memoryless Gaussian interference channel (GIC) where $K$ single-antenna users communicate with their respective receivers using Gaussian codebooks. Each receiver employs a successive group decoder with a specified complexity constraint, to decode its designated user. It is aware of the coding schemes employed by all other users and may choose to decode some or all of them only if it deems that doing so will aid the decoding of its desired user. For a GIC with predetermined rates for all transmitters, we obtain the minimum outage probability decoding strategy at each receiver which satisfies the imposed complexity constraint and reveals the optimal subset of interferers that must be decoded along with the desired user. We then consider the rate allocation problem over the GIC under successive group decoding and design a sequential rate allocation algorithm which yields a pareto-optimal rate allocation, and two parallel rate allocation algorithms which yield the symmetric fair rate allocation and the max-min fair rate allocation, respectively. Remarkably, even though the proposed decoding and rate allocation algorithms use “greedy” or myopic subroutines, they achieve globally optimal solutions. Finally, we also propose rate allocation algorithms for a cognitive radio system.      

OFDMA系统基于QoS保证和最大最小公平性准则下的动态资源分配

正交频分多址(OFDMA)技术以其更高的频谱效率和抗多径衰落特性成为高速无线通信网络的候选标准。兼顾效率和公平性是OFDMA系统资源分配亟待解决的问题。本文研究了OFDMA系统中的无线资源分配问题,既要保证QoS用户的最小速率要求,同时“尽力而为”用户之间必须满足最小速率最大化公平性(max-min fairness)准则;该资源分配问题可以表述为一个系统总功率约束下的子载波分配和功率控制的混合离散型优化模型,这是难解的NP-hard问题,穷举搜索的代价是极其巨大的。针对该非凸模型,本文设计一个拉格朗日松弛的优化算法,该算法中采用修正的椭球算法求解对偶问题。算法具有多项式时间复杂度,且与子载波数目呈线性增长关系。仿真结果表明,该算法能近似最优地满足用户QoS及最大最小公平性要求。      

The impact of multicast layering on network fairness

Many definitions of fairness for multicast networks assume that sessions are single rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multirate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multirate sessions, and show that all four fairness properties hold in a multirate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multirate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multirate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks     

基于PII控制器的XCP带宽补偿算法

 XCP在多瓶颈网络中存在缺陷,利用率和公平性显著下降.本文根据控制论中的反馈补偿原理,提出一个基于PII控制器的XCP带宽补偿算法.仿真实验表明该带宽补偿算法能够有效消除XCP在多瓶颈网络中的缺陷,各条链路都能够获得100％的利用率,各条瓶颈流都能够获得最大最小公平带宽.     

基于分段线性函数的广义效用max-min公平分配算法研究

提出了一种基于分段线性函数的广义效用max-min（UMM）公平分配算法，可支持资源分配的上下限以及各种严格单调增和连续的效用函数。该算法避免了迭代计算，复杂度低于UMM公平的注水法。简化后的算法的复杂度与现有的基于分段线性函数的狭义UMM公平分配算法相同。该算法可应用于计算机和通信领域中的各种资源分配问题中。     

A game theoretic framework for bandwidth allocation and pricing inbroadband networks

In this paper, we present a game theoretic framework for bandwidth allocation for elastic services in high-speed networks. The framework is based on the idea of the Nash bargaining solution from cooperative game theory, which not only provides the rate settings of users that are Pareto optimal from the point of view of the whole system, but are also consistent with the fairness axioms of game theory. We first consider the centralized problem and then show that this procedure can be decentralized so that greedy optimization by users yields the system optimal bandwidth allocations. We propose a distributed algorithm for implementing the optimal and fair bandwidth allocation and provide conditions for its convergence. The paper concludes with the pricing of elastic connections based on users' bandwidth requirements and users' budget. We show that the above bargaining framework can be used to characterize a rate allocation and a pricing policy which takes into account users' budget in a fair way and such that the total network revenue is maximized     

Bandwidth sharing: objectives and algorithms

This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is the so-called max-min fairness. The alternative proportional fairness criterion has recently been introduced by F. Kelly (see Eur. Trans. Telecommun., vol.8, p.33-7, 1997); we introduce a third criterion, which is naturally interpreted in terms of the delays experienced by ongoing transfers. We prove that fixed-size window control can achieve fair bandwidth sharing according to any of these criteria, provided scheduling at each link is performed in an appropriate manner. We then consider a distributed random scheme where each traffic source varies its sending rate randomly, based on binary feedback information from the network. We show how to select the source behavior so as to achieve an equilibrium distribution concentrated around the considered fair rate allocations. This stochastic analysis is then used to assess the asymptotic behavior of deterministic rate adaption procedures     

Fair Coalitions for Power-Aware Routing in Wireless Networks

Several power-aware routing schemes have been developed for wireless networks under the assumption that nodes are willing to sacrifice their power reserves in the interest of the network as a whole. But, in several applications of practical utility, nodes are organized in groups, and as a result, a node is willing to sacrifice in the interest of other nodes in its group but not necessarily for nodes outside its group. Such groups arise naturally as sets of nodes associated with a single owner or task. We consider the premise that groups will share resources with other groups only if each group experiences a reduction in power consumption. Then, the groups may form a coalition in which they route each other's packets. We demonstrate that sharing between groups has different properties from sharing between individuals and investigate fair, mutually beneficial sharing between groups. In particular, we propose a Pareto-efficient condition for group sharing based on max-min fairness called fair coalition routing. We propose distributed algorithms for computing the fair coalition routing. Using these algorithms, we demonstrate that fair coalition routing allows different groups to mutually beneficially share their resources     

An Upward Max-Min Fairness Multipath Flow Control

Many rate allocation algorithms for multipath flows which satisfy max-min fairness are centralized and not scalable. Upward max-min fairness is a well-known relaxation of max-min fairness and can be achieved by an algorithm extended from water-filling algorithm. In this paper, we propose a price-based multipath congestion control protocol whose equilibrium point satisfies upward max-min fairness. Our protocol is derived from a network utility maximization model for multipath flows.

     

Intra-Session Fairness in Multicast Communications

Multicast communication achieves scalability by sending data to multiple receivers at the same time. Receivers in a multicast session usually share the fate with each other, even though their processing speed and the capacity of the path they use can be quite different. A conventional multicast session usually consists of a single multicast group and the problem is how to set the group rate so that it is fair to both fast and slow receivers, to some extent. In a replicated multicast service, receivers are divided into groups based on their capacities and a multicast session can consist of multiple multicast groups. The question is how to divide receivers into groups exactly and set appropriate group rates so that it is fair to all the receivers. Most of current work focuses on optimizing the social welfare represented as a sum of some performance measures of receivers [Kar et al., 2002; Stoenescu et al., 2003]. In this paper, we define a new concept called intra-session fairness and give an optimal solution that can achieve fairness among receivers in the same session. The goal is to maximize the minimum fairness value of the receivers. The novelty of the framework is that it is independent of the specific definition of the fairness function on individual receivers. We illustrate a layering method to implement the max-min intra-session fair allocation and demonstrate the significant difference in fairness achieved by the maximal social welfare algorithm and the max-min intra-session fairness algorithm.     

Explicit rate allocation algorithm of generalised max-min fairnessfor ATM ABR services

A distributed explicit rate allocation algorithm based on the generalised max-min (GMM) fairness principle is proposed for the available bit rate (ABR) ATM services. Compared with a similar algorithm for GMM, it employs fewer fields in an RM cell and imposes lower requirements on the computational capability of the switches     

Proportional-fair power allocation with CDF-based scheduling for fair and efficient multiuser OFDM systems

In this paper we investigate adaptive resource allocation schemes in multiuser OFDM systems for fair share of resources and efficient operation. We employ the CDF-based scheduling (CS) algorithm for the subcarrier allocation, taking advantage of its distinctive feature of analyzability and multiuser diversity. Noting that conventional power allocation schemes do not exhibit efficient and fair operations in heterogeneous user channel environment, we present a new algorithm called proportional-fair power allocation (PFPA). This algorithm is designed to allocate transmission power in such a way that the resulting relative throughput-increment is identical for all subcarriers. The PFPA algorithm is shown to be equivalent to the power allocation of the asymptotically optimal algorithm, which exhibits the largest achievable region in the asymptotic case. Numerical results reveal that the combined CS-PFPA algorithm improves the overall system capacity in terms of time-average throughput and provides efficient estimation of user performances. Further, the CS-PFPA algorithm can meet each user's requirements using a minimum amount of resources, so it renders an efficient and fair means for resource allocation in multiuser OFDM systems.     

Fair Multiuser Channel Allocation for OFDMA Networks Using Nash Bargaining Solutions and Coalitions

In this paper, a fair scheme to allocate subcarrier, rate, and power for multiuser orthogonal frequency-division multiple-access systems is proposed. The problem is to maximize the overall system rate, under each user's maximal power and minimal rate constraints, while considering the fairness among users. The approach considers a new fairness criterion, which is a generalized proportional fairness based on Nash bargaining solutions and coalitions. First, a two-user algorithm is developed to bargain subcarrier usage between two users. Then a multiuser bargaining algorithm is developed based on optimal coalition pairs among users. The simulation results show that the proposed algorithms not only provide fair resource allocation among users, but also have a comparable overall system rate with the scheme maximizing the total rate without considering fairness. They also have much higher rates than that of the scheme with max-min fairness. Moreover, the proposed iterative fast implementation has the complexity for each iteration of only$O(K^2Nlog_2 N+K^4)$, where$N$is the number of subcarriers and$K$is the number of users.     

A new approach for asynchronous distributed rate control of elasticsessions in integrated packet networks

We develop a new class of asynchronous distributed algorithms for the explicit rate control of elastic sessions in an integrated packet network. Sessions can request for minimum guaranteed rate allocations (e.g., minimum cell rates in the ATM context), and, under this constraint, we seek to allocate the max-min fair rates to the sessions. We capture the integrated network context by permitting the link bandwidths available to elastic sessions to be stochastically time varying. The available capacity of each link is viewed as some statistic of this stochastic process [e.g., a fraction of the mean, or a large deviations-based equivalent service capacity (ESC)]. The ESC is obtained so as to satisfy an overflow probability constraint on the buffer length. For fixed available capacity at each link, we show that the vector of max-min fair rates can be computed from the root of a certain vector equation. A distributed asynchronous stochastic approximation technique is then used to develop a provably convergent distributed algorithm for obtaining the root of the equation, even when the link flows and the available capacities are obtained from on-line measurements. The switch algorithm does not require per connection monitoring, nor does it require per connection marking of control packets. A virtual buffer based approach for on-line estimation of the ESC is utilized. We also propose techniques for handling large variations in the available capacity owing to the arrivals or departures of CBR/VBR sessions. Finally, simulation results are provided to demonstrate the performance of this class of algorithms in the local and wide area network context