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     

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     

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.      

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     

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.     

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.     

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.      

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     

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     

A low-state packet marking framework for approximate fair bandwidth allocation

Misbehaving, non-congestion-reactive traffic is on the rise in the Internet. One way to control misbehaving traffic is to enforce local fairness among flows. Locally fair policies, such as fair-queueing and other fair AQM schemes, are inadequate to simultaneously control misbehaving traffic and provide high network utilization. We thus need to enforce globally fair bandwidth allocations. However, such schemes have typically been stateful and complex to implement and deploy. In this letter, we present a low state, lightweight scheme based on stateless fair packet marking at network edges followed by RIO queueing at core nodes, to control misbehaving flows with more efficient utilization of network bandwidth. Additionally, with low-state feedback from bottleneck routers, we show that, in practice, we can approximate global max-min fairness within an island of routers. We show, using simulations, that we can indeed control misbehaving flows and provide more globally fair bandwidth allocation.     

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     

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

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

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.      

Fair TDMA scheduling in wireless multihop networks

In wireless multihop networks, communication between two end-nodes is carried out by hopping over multiple wireless links. However, the fact that each node has to transmit not only its own traffic, but also traffic on behalf of other nodes, leads to unfairness among the communication rates of the nodes. Traditional Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) based media access control does not work satisfactory in a multihop scenario, since an intended target of a communication may be subject to mutual interference imposed by concurrent transmissions from nodes, which cannot directly sense each other, thus causing unfair throughput allocation. Although Time Division Multiple Access (TDMA) seems to be a more promising solution, careful transmission scheduling is needed in order to achieve error-free communication and fairness. Several algorithms may be found in the literature for scheduling TDMA transmissions in wireless multihop networks. Their main goal is to determine the optimal scheduling, in order to increase the capacity and reduce the delay for a given network topology, though they do not consider the traffic requirements of the active flows of the multihop network or fairness issues. In this paper, we propose a joint TDMA scheduling/load balancing algorithm, called Load-Balanced-Fair Flow Vector Scheduling Algorithm (LB-FFVSA). This algorithm schedules the transmissions in a fair manner, in terms of throughput per connection, taking into account the communication requirements of the active flows of the network. Simulation results show that the proposed algorithm achieves improved performance compared to other solutions, not only in terms of fairness, but also in terms of throughput. Moreover, it was proved that when a load balancing technique is used, the performance of the scheduling algorithm is further improved.     

一种新的基于认购速率和QoS等级的动态带宽分配算法

为了实现吉比特无源光网络带宽分配的公平性,降低网络的传输延时,设计了一种新的媒质访问控制协议,提出了一种新的动态带宽分配算法.其基本思想是:在保证拥有不同QoS业务的用户得到认购速率的基础上,根据网络负载的大小,动态地将某些用户未使用的带宽分配给其他带宽需求大的用户,以提高网络的带宽利用率.仿真结果表明,这种新的算法在严格控制数据传输延时的前提下,能够保证多用户之间带宽分配的公平性.     

Cell Breathing Techniques for Load Balancing in Wireless LANs

Maximizing network throughput while providing fairness is one of the key challenges in wireless LANs (WLANs). This goal is typically achieved when the load of access points (APs) is balanced. Recent studies on operational WLANs, however, have shown that AP load is often substantially uneven. To alleviate such imbalance of load, several load balancing schemes have been proposed. These schemes commonly require proprietary software or hardware at the user side for controlling the user-AP association. In this paper we present a new load balancing technique by controlling the size of WLAN cells (i.e., AP's coverage range), which is conceptually similar to cell breathing in cellular networks. The proposed scheme does not require any modification to the users neither the IEEE 802.11 standard. It only requires the ability of dynamically changing the transmission power of the AP beacon messages. We develop a set of polynomial time algorithms that find the optimal beacon power settings which minimize the load of the most congested AP. We also consider the problem of network-wide min-max load balancing. Simulation results show that the performance of the proposed method is comparable with or superior to the best existing association-based methods.     

Proportional Fairness in Multi?Carrier System with Multi?Slot Frames: Upper Bound and User Multiplexing Algorithms

Optimal Proportional Fair Scheduling (PFS) in a multi-carrier system is a prohibitively complex combinatorial problem. In this paper we consider practical time frames with multiple time slots, where this optimal allocation becomes even more complex. Therefore, we derive bounds for the optimal proportional fair allocation, by means of convex optimization, and propose approximation algorithms where several users can be time-multiplexed on a same subchannel. With a much lower complexity than the optimal allocation, these algorithms achieve an excellent tradeoff between throughput and proportional fairness, even with the increased signaling overhead.     

一种新的适用于多种公平准则的ABR流控算法的设计和研究

现有的各种ABR拥塞控制算法都只能实现最大最小准则下的公平性。本文提出了一种称为动态带宽分配(DBA)的控制算法,在该算法框架内可以方便地实现ATM论坛定义的任一准则下的公平性。仿真实验结果表明,新算法性能良好。     

A NEW ABR CONGESTION CONTROL ALGORITHM ACHIEVING FAIRNESS UNDER SEVERAL CRITERIA

All ABR congestion control algorithms reported are designed to achieve max-min fairness. In this paper, a new algorithm named dynamic bandwidth allocation algorithm is presented. Under the same framework, the algorithm can achieve fairness under several given criteria. Simulation result shows that the new algorithm works well under various network configurations, various traffic classes, and scale well to LANs or WANs.     

Adaptive opportunistic fair scheduling over multiuser spatial channels

We consider the problem of opportunistic fair scheduling (OFS) of multiple users in downlink time-division multiple-access (TDMA) systems employing multiple transmit antennas and beamforming. OFS is an important technique in wireless networks to achieve fair bandwidth usage among users, which is performed on a per-frame basis at the media access control layer. Multiple-transmit-antenna beamforming provides TDMA systems with the capability of supporting multiple concurrent transmissions, i.e., multiple spatial channels at the physical layer. Given a particular subset of users and their channel conditions, the optimal beamforming scheme can be calculated. The multiuser opportunistic scheduling problem then refers to the selection of the optimal subset of users for transmission at each time instant to maximize the total throughput of the system subject to a certain fairness constraint on each individual user's throughput. We propose discrete stochastic approximation algorithms to adaptively select a better subset of users. We also consider scenarios of time-varying channels for which the scheduling algorithm can track the time-varying optimal user subset. We present simulation results to demonstrate the performance of the proposed scheduling algorithms in terms of both throughput and fairness, their fast convergence, and the excellent tracking capability in time-varying environments.