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     

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.     

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.

     

WCDMA下行链路分级SIR和速率指配算法研究

研究一种针对WCDMA数据用户的下行链路分级SIR和速率指配算法，其中数据用户的QoS通过时延、误码率以及描述吞吐量和数据用户之间公平性的一族效用函数来表示。算法具有分级控制结构，容易以分布式的形式实现。移动台根据用户特定的本地信息独立地调整SIR目标，而基站根据来自各移动台的有限的反馈信息，同时调整各用户的数据速率。仿真结果表明，通过选择适当的效用函数可以在系统的总吞吐量和公平性之间得到一个灵活的折衷。     

基于效用函数簇的效用类服务分层调度模型

针对基于效用的单层调度模型对网络流划分粒度较粗,难以实现服务间效用公平和总效用最大化的问题,提出了U-S两层调度模型,设计了高效求解算法USMS,为提高求解精度,进一步提出了USIM算法.仿真实验结果显示:USMS和USIM算法具有良好的求解有效性和效率;与单层模型相比,U-S模型具有更高的总效用值.     

多媒体DS-CDMA系统中基于效用函数的 无线资源优化策略

本文提出了一种DS-CDMA系统上行链路中基于效用函数(utility function)的无线资源分配策略.在该模型的框架下,我们提出了两种基于效用函数的无线资源分配算法:URRA-EA (Utility-based Radio Resource Allocation-Efficiency Focused)和URRA-UF (Utility-based Radio Resource Allocation-User Focused).URRA-EF旨在追求系统资源的全局最优化,而相比之下URRA-UF在用户公平性方面更有优势.为避免非线性优化带来的过高的计算复杂度,我们将基于效用函数的无线资源分配问题转换为一个市场模型,这样资源的最优配置将以分布式的模式获得,因此计算复杂度将大大降低.仿真结果表明,该策略与传统方式相比能够更灵活有效的配置无线多媒体DS-CDMA系统中的无线资源,其性能提高是显著的.     

效用max—min公平准则及其在ABR业务中的应用

本文提出一种新的基于效用函数的max-min(UMM）公平准则,它实现的是用户效用之间的公平分配。在ABR业务下,本文提出UMM公平性的另外两个等价定义,考察了用户的最小需求和最大需求。为了求解UMM公平分配,文中给出集中式的UMM公平分配算法及其数学证明。文章从保证分配效率的角度出发赋予峰值信元位率PCR以新的含义。UMM公平性不仅是对以往ABR业务中max-min公平性的概括,还具有很好的推广前景,特别适用于多应用类型的网络资源分配。     

Hierarchical SIR and rate control on the forward link for CDMA datausers under delay and error constraints

We study the signal-to-interference ratio (SIR) and rate control for code division multiple access (CDMA) data users on the forward link under average or peak power constraints. The quality of service (QoS) for data users is specified by delay and error rate constraints as well as a family of utility functions representing the throughput and fairness among the data users. It is found that the optimal SIR and rate control algorithm has a hierarchical structure which can be easily implemented in a distributed manner. The SIR targets can be adjusted independently by the mobiles using information specific to the individual users. The data rates can be adjusted jointly by the base station based on limited feedback from the mobiles. We also propose a two-level iteration algorithm for both the mobile and the base station to efficiently compute the SIR and data rates. Our results show that a flexible tradeoff between total system throughput (sum of rates achieved) and fairness (similarity in data rates) can be achieved by choosing appropriate utility functions used in this scheme     

基于服务等级的效用函数和公平性评价方法

本文介绍了QoS和BE两种业务类型并分别在S型函数和上凸函数基础上提出两种业务的效用函数,从用户角度出发,以提高用户间公平性作为研究目标。然后在两种不同的业务下,将不同服务水平的用户进行区分,得到基于服务等级的用户效用函数。最后,以综合效用比值的方式提出了基于服务等级的公平性评价标准。     

一种新的适用于多种公平准则的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.     

Is max-min fairness achievable in the presence of insubordinateusers?

Enforcement of max-min fairness encourages end users to implement adaptive end-to-end flow control. Unfortunately, there can be insubordinate users who ignore congestion and cause performance degradation to others. The commonly used max-min fairness definition that treats insubordinate users fairly causes inefficiency. We demonstrate that a strict priority regime can protect the cooperative users so that they enjoy fair and efficient service. We also demonstrate that this cannot be achieved by weighted class fairness     

多用户多服务无线网络中感知用户体验的比例公平调度

The effective radio resource allocation algorithms, which satisfy diversiform requirements of mobile multimedia services in wireless cellular networks, have recently attracted more and more attention. This paper proposes a service-aware scheduling algorithm, in which the Mean Opinion Score (MOS) is chosen as the unified metric of the Quality of Experience (QoE). As the network needs to provide satisfactory services to all the users, the fairness of QoE should be considered. The Proportional Fair (PF) principle is adopted to achieve the trade-off between the network performance and user fairness. Then, an integer programming problem is formed and the QoE-aware PF scheduling principle is derived by solving the relaxed problem. Simulation results show that the proposed scheduling principle can perform better in terms of user fairness than the previous principle maximizing the sum of MOS. It also outperforms the max-min scheduling principle in terms of average MOS.     

Super-Fast Delay Tradeoffs for Utility Optimal Fair Scheduling in Wireless Networks

We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within$O(1/V)$of the utility-optimal operating point, for any control parameter$V≫0$, with a corresponding end-to-end network delay that grows only logarithmically in$V$. This is the first algorithm to achieve such “super-fast” performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffs.     

Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints

Multiuser orthogonal frequency division multiplexing (MU-OFDM) is a promising technique for achieving high downlink capacities in future cellular and wireless local area network (LAN) systems. The sum capacity of MU-OFDM is maximized when each subchannel is assigned to the user with the best channel-to-noise ratio for that subchannel, with power subsequently distributed by water-filling. However, fairness among the users cannot generally be achieved with such a scheme. In this paper, a set of proportional fairness constraints is imposed to assure that each user can achieve a required data rate, as in a system with quality of service guarantees. Since the optimal solution to the constrained fairness problem is extremely computationally complex to obtain, a low-complexity suboptimal algorithm that separates subchannel allocation and power allocation is proposed. In the proposed algorithm, subchannel allocation is first performed by assuming an equal power distribution. An optimal power allocation algorithm then maximizes the sum capacity while maintaining proportional fairness. The proposed algorithm is shown to achieve about 95% of the optimal capacity in a two-user system, while reducing the complexity from exponential to linear in the number of subchannels. It is also shown that with the proposed resource allocation algorithm, the sum capacity is distributed more fairly and flexibly among users than the sum capacity maximization method.     

多无人机辅助通信中用户匹配与频谱资源联合优化方法

针对多无人机作为空中基站为地面设备提供临时服务的动态频谱分配问题，主要考虑无人机与地面用户匹配、子信道分配和功率分配三个方面。为了保证用户通信的公平性，在考虑频谱复用和共信道干扰的情况下，以最大化地面用户最小传输速率为目标，提出了一种用户匹配与频谱资源联合优化算法来解决上述混合整数非线性优化问题，通过聚类算法优化无人机与地面用户的最佳匹配，通过块坐标下降法迭代优化子信道分配和功率分配。仿真实验分析表明，提出的求解方法可以有效提升用户的传输速率，保证用户通信公平性。     

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.     

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

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

Resource Allocation for Decode-and-Forward Relaying Assisted Multi-cell Orthogonal Frequency Division Multiplexing Systems with Frequency Planning

In this paper we apply frequency planning to the resource allocation of multi-cell and multi-user relay enhanced orthogonal frequency division multiplexing systems and propose a low-complexity algorithm taking into account of interference coordination, subcarrier and power allocation. We divide each cell into three sectors and allow different subcarrier set that can be used by the users of one sector. Such a method can help to increase the distance among users that use the same subcarriers of adjacent cells, which can reduce the impact of co-channel interference to a certain extent. Therefore, the original problem can be decoupled into three independent sub-problems by means of frequency dividing and adaptive power allocation at base station nodes which can reduce the computing complexity greatly. In the process of resource allocation for single sector, the relationship of transmission power between base station and relay node is used to transform the max-min problem into standard closed expression. With the help of dual decomposition approach, water-filling theorem and iterative power allocation algorithm, the suboptimal solution of the primal problem can be achieved finally. Simulation results illustrate that our proposed algorithm achieves almost the same performance as the optimal resource allocation and reduce the computing complexity greatly. In addition, the proposed algorithm can ensure the users fairness of different sectors.     

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.