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.     

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.      

Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation

Given a set of demands between pairs of nodes, we examine the traffic engineering problem of flow routing and fair bandwidth allocation where flows can be split to multiple paths (e.g., MPLS tunnels). This paper presents an algorithm for finding an optimal and global per-commodity max-min fair rate vector in a polynomial number of steps. In addition, we present a fast and novel distributed algorithm where each source router can find the routing and the fair rate allocation for its commodities while keeping the locally optimal max-min fair allocation criteria. The distributed algorithm is a fully polynomial epsilon-approximation (FPTAS) algorithm and is based on a primal-dual alternation technique. We implemented these algorithms to demonstrate its correctness, efficiency, and accuracy.      

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     

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     

Price-based max-min fair rate allocation in wireless multi-hop networks

The interaction between links in wireless multihop networks introduces extra constraints on the combinations of achievable flow rates. Algorithms have been proposed to achieve max-min fairness under these additional constraints. This letter provides a simple price-based max-min fair rate allocation scheme, building on a utility maximization scheme recently proposed for such networks.     

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.     

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.     

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     

基于EPON的公平带宽分享算法及其应用

考虑光学开放接入网（optical open access network）中的公平性,将最大最小公平算法用到双向服务等级协议（D-SLA）中,提出了一种基于以太无源光学网络（EPON）的易于实现的双向服务等级协议公平带宽分配算法。算法使用了两轮分配,通过分级管理确定首要SLA和次要SLA,对业务提供商和用户进行分级区...     

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.     

QoS aware adaptive resource allocation techniques for fair scheduling in OFDMA based broadband wireless access systems

A system based on orthogonal frequency division multiple access (OFDMA) has been developed to deliver mobile broadband data service at data rates comparable to those of wired services, such as DSL and cable modems. We consider the resource allocation problem of assigning a set of subcarriers and determining the number of bits to be transmitted for each subcarrier in OFDMA systems. We compare simplicity, fairness and efficiency of our algorithm with the optimal and proposed suboptimal algorithms for varying values of delay spread, number of users and total power constraint. The results show that the performance of our approach is appealing and can be close to optimal. We also consider another resource allocation scheme in which there is no fixed QoS requirements per symbol but capacity is maximized.     

The Achievable Rate Region of 802.11-Scheduled Multihop Networks

In this paper, we characterize the achievable rate region for any IEEE 802.11-scheduled static multihop network. To do so, we first characterize the achievable edge-rate region, that is, the set of edge rates that are achievable on the given topology. This requires a careful consideration of the interdependence among edges since neighboring edges collide with and affect the idle time perceived by the edge under study. We approach this problem in two steps. First, we consider two-edge topologies and study the fundamental ways they interact. Then, we consider arbitrary multihop topologies, compute the effect that each neighboring edge has on the edge under study in isolation, and combine to get the aggregate effect. We then use the characterization of the achievable edge-rate region to characterize the achievable rate region. We verify the accuracy of our analysis by comparing the achievable rate region derived from simulations with the one derived analytically. We make a couple of interesting and somewhat surprising observations while deriving the rate regions. First, the achievable rate region with 802.11 scheduling is not necessarily convex. Second, the performance of 802.11 is surprisingly good. For example, in all the topologies used for model verification, the max-min allocation under 802.11 is at least 64% of the max-min allocation under a perfect scheduler.      

Fair Bandwidth Allocation in Optical Burst Switching Networks

Optical burst switching (OBS) is a promising switching technology for next-generation Internet backbone networks. One of the design challenges is how to provide fair bandwidth allocation in OBS networks; the schemes proposed for general store-and-forward IP switching networks can not be used because of the non-buffering and un-fully utilized bandwidth characteristics of OBS networks. We propose a rate fairness preemption (RFP) scheme to achieve approximately weighted max-min fair bandwidth allocation in OBS networks. We present an analysis of the burst loss probability in RFP-based OBS networks. The analysis and simulation results show that the RFP scheme provides fair bandwidth allocation in OBS networks.      

Evaluation of channel dependent bandwidth allocation in wireless access networks: centralized and distributed approach

The problem of bandwidth allocation in wireless access networks is studied in this paper, investigating the performance of two approaches. Firstly, we use centralized algorithms, such as bankruptcy division rules and Nash bargaining. Secondly, a distributed algorithm is proposed in order to find the optimal solution of the bandwidth allocation problem. In both approaches, the allocation rules are properly modified to incorporate the influence of the channel state resulting in a more efficient and fair bandwidth allocation. The channel dependent centralized and distributed schemes are compared in terms of efficiency and fairness with a view to highlighting the advantages and disadvantages of every approach.     

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

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

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

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

Existence and uniqueness of fair rate allocations in lossy wireless networks

To extend established concepts of fair resource allocation in wired networks to wireless networks, wired model assumptions must be adapted to be relevant for wireless networks as for example, in wireless networks losses due to environmental conditions may occur even in the absence of queueing congestion. Thus fundamental questions of the existence and uniqueness of fair rate allocations must be reconsidered. We treat wireless networks characterized by lossy channels, spatial channel reuse, multiple routes and multiple frequencies. We establish the existence and uniqueness of utility fair and max-min fair solutions and that, as loss rates decrease, fair allocations converge to the loss-less ones.     

Cross-layer optimization of wireless networks using nonlinear column generation

We consider the problem of finding the jointly optimal end-to-end communication rates, routing, power allocation and transmission scheduling for wireless networks. In particular, we focus on finding the resource allocation that achieves fair end-to-end communication rates. Using realistic models of several rate and power adaption schemes, we show how this cross-layer optimization problem can be formulated as a nonlinear mathematical program. We develop a specialized solution method, based on a nonlinear column generation technique, and prove that it converges to the globally optimal solution. We present computational results from a large set of networks and discuss the insight that can be gained about the influence of power control, spatial reuse, routing strategies and variable transmission rates on network performance.     

On achieving fairness in the joint allocation of processing and bandwidth resources: principles and algorithms

The problem of achieving fairness in the allocation of the bandwidth resource on a link shared by multiple flows of traffic has been extensively researched over the last decade. However, with the increasing pervasiveness of optical networking and the occasional trend toward using over-provisioning as the solution to bandwidth congestion, a router's processor also becomes a critical resource to which, ideally speaking, all competing flows should have fair access. For example, achieving fairness in the allocation of processing resources can be part of an overall strategy of countering certain kinds of denial of service attacks (such as those based on an excessive use of the router processor by using unnecessary optional headers). In this paper, we investigate the issue of achieving fairness in the joint allocation of the processing and bandwidth resources. We first present a simple but powerful general principle for defining fairness in such systems based on any of the classic notions of fairness such as max-min fairness, proportional fairness, and utility max-min fairness defined for a single resource. We apply our principle to a system with a shared processor and a shared link with max-min fairness as the desired goal. We then propose a practical and provably fair packet-by-packet algorithm for the joint allocation of processing and bandwidth resources. We demonstrate the fairness achieved by our algorithm through simulation results using both synthetic and real gateway traffic traces. The principles and the algorithm detailed in this paper may also be applied in the allocation of other kinds of resources such as power, which is a critical resource in mobile systems.