Architecture for dynamic and fair distribution of bandwidth

The problem of fair distribution of available bandwidth among traffic flows or aggregates remains an essential issue in computer networks. This paper introduces a novel approach, called the E x act B andwidth D istribution S cheme (X‐BDS), for dynamic and fair distribution of available bandwidth among individual flows. In this approach, the edge routers keep per‐flow information, while the core routers maintain the aggregate flow requirements. The X‐BDS approach employs a distributed message exchange protocol for providing network feedback and for distributing aggregate flow requirements among the nodes in the network. Based on the obtained feedback, the edge routers employ the X‐BDS resource management unit to dynamically distribute available bandwidth among individual flows. The X‐BDS admission control and resource management units are responsible for fair resource allocation that supports minimum bandwidth guarantees of individual flows. This paper evaluates the Bandwidth Distribution Scheme through simulation and shows that the X‐BDS is capable of supporting per‐flow bandwidth guarantees in a dynamically changing network environment. Copyright © 2006 John Wiley & Sons, Ltd.     

Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

ORCA-MRT: an optimization-based approach for fair scheduling in multirate TDMA wireless networks

This paper presents an optimization-based approach to solve the wireless fair scheduling problem under a multirate time division multiple access (TDMA)-based medium access control (MAC) framework. By formulating the fair scheduling problem as an assignment problem, the authors propose the optimal radio channel allocation for multirate transmission (ORCA-MRT) algorithm for fair bandwidth allocation in wireless data networks that support MRT at the radio link level. The key feature of ORCA-MRT is that while allocating transmission rate to each flow fairly, it keeps the interaccess delay bounded under a certain limit. The authors investigate the performance of the proposed ORCA-MRT scheduler in comparison to another recently proposed multirate fair scheduling algorithm. They also propose two channel prediction models and perform extensive simulations to investigate the performance of ORCA-MRT for different system parameters such as channel state correlation, number of flows, etc.     

无线Ad Hoc网络中动态的带宽管理

基于已有的带宽管理机制,采用加权公平对竞争的流分配带宽,不仅可以对流实现准入控制,以保证每条流的最低信道时间需求,同时也能动态地调节流所分配的信道时间。另外,我们的方案,也适用于多跳的情况,通过例子说明,在考虑到用户需求的同时,也提高了网络的吞吐量。     

Improving Quality of Service and Assuring Fairness in WLAN Access Networks

As public deployment of wireless local area networks (WLANs) has increased and various applications with different service requirements have emerged, fairness and quality of service (QoS) are two imperative issues in allocating wireless channels. This study proposes a fair QoS agent (FQA) to simultaneously provide per-class QoS enhancement and per-station fair channel sharing in WLAN access networks. FQA implements two additional components above the 802.11 MAC: a dual service differentiator and a service level manager. The former is intended to improve QoS for different service classes by differentiating service with appropriate scheduling and queue management algorithms, while the latter is to assure fair channel sharing by estimating the fair share for each station and dynamically adjusting the service levels of packets. FQA assures (weighted) fairness among stations in terms of channel access time without decreasing channel utilization. Furthermore, it can provide quantitative service assurance in terms of queuing delay and packet loss rate. FQA neither resorts to any complex fair scheduling algorithm nor requires maintaining per-station queues. Since the FQA algorithm is an add-on scheme above the 802.11 MAC, it does not require any modification of the standard MAC protocol. Extensive ns-2 simulations confirm the effectiveness of the FQA algorithm with respect to the per class QoS enhancement and per-station fair channel sharing     

Core‐stateless fair rate estimation fair queuing

Core‐stateless mechanisms, such as core‐stateless fair queuing (CSFQ), reduce the complexity of fair queuing, which usually need to maintain states, manage buffers, and perform flow scheduling on a per‐flow basis. However, they require executing label rewriting and dropping decision on a per‐packet basis, thus preventing them from being widely deployed. In this paper, we propose a novel architecture based on CSFQ without per‐packet labelling. Similarly, we distinguish between edge routers and core routers. Edge routers maintain the per‐flow state by employing a fair queuing mechanism to allocate each flow a fair bandwidth share locally and a token bucket mechanism to regulate those flows with feedback packets sent from egress edge routers. Core routers do not maintain per‐flow state; they use FIFO packet scheduling extended by a fare rate alarm mechanism by estimating the arrival rate and the number of flows using a matching–mismatching algorithm. The novel scheme is called core‐stateless fair rate estimation fair queuing (CSFREFQ). CSFREFQ is proven to be capable of achieving max–min fairness. Furthermore, we present and discuss simulations and experiments on the performance under different traffic scenarios. Copyright © 2005 John Wiley & Sons, Ltd.     

EPON中保证QoS的动态带宽分配算法

作为一种新技术，EPON系统采取在下行信道使用广播方式而在上行信道使用时分多址(TDMA)方式，为用户提供共享传输介质的接入方式，因此就需要一种接入控制机制来为用户分配带宽。为了使EPON系统更好地支持QoS并且进一步提高带宽利用率，提出了一种新的固定周期轮询动态带宽分配算法，针对不同时延特性业务采用不同的授权分配算法。算法包括两部分：OLT时ONU的调度以及ONU内部不同优先级的队列之间的调度。最后讨论了包时延、系统吞吐量等仿真结果和性能分析。     

Delay guaranteed MDP scheduling scheme for HCCA based on 802.11p protocol in V2R environments

In recent years, the vehicular ad hoc network has attracted worldwide attention from academe and industry. Many researches have been executed to improve the quality of services (QoS) of the intelligent transportation system. However, current existing channel access schemes at the medium access control layer specified in 802.11 protocol, including hybrid coordination function control channel access (HCCA) and enhanced distributed channel access, could not efficiently achieve the QoS requirements in some special situations. This paper proposes a delay guaranteed HCCA (DG‐HCCA) scheduling scheme, which works based on a Markov decision process model and the measurement of historic performance, to guarantee the QoS enhanced data transmission for vehicles to roadside unit. Besides, this paper also presents a performance analysis model to systematically evaluate the system performance of the channel utility and the average delay. The performance of the proposed delay guaranteed HCCA scheduling scheme is compared with that of original HCCA scheme specified in 802.11p standard and other 2 HCCA improved schemes by the simulation experiments. The simulation results demonstrate that the proposed solution could highly fulfill the transmission delay requirements with a better channel utility and less loss rates than those by the standard HCCA scheme and other 2 schemes.     

A survey of dynamic bandwidth allocation algorithms for Ethernet Passive Optical Networks

Ethernet Passive Optical Network (EPON) has been widely considered as a promising technology for implementing the FTTx solutions to the “last mile” bandwidth bottleneck problem. Bandwidth allocation is one of the critical issues in the design of EPON systems. In an EPON system, multiple optical network units (ONUs) share a common upstream channel for data transmission. To efficiently utilize the limited bandwidth of the upstream channel, an EPON system must dynamically allocate the upstream bandwidth among multiple ONUs based on the instantaneous bandwidth demands and quality of service requirements of end users. This paper introduces the fundamental concepts on EPONs, discusses the major issues related to bandwidth allocation in EPON systems, and presents a survey of the state-of-the-art dynamic bandwidth allocation (DBA) algorithms for EPONs.     

Flow rank based probabilistic fair scheduling for wireless ad hoc networks

Fair scheduling is an ideal candidate for fair bandwidth sharing and thereby achieving fairness among the contending flows in a network. It is particularly challenging for ad hoc networks due to infrastructure free operation and location dependent contentions. As there is no entity to serve coordination among nodes, we need a mechanism to overcome inherent unreliability of the network to provide reduced collision and thereby higher throughput and adequate fair allocation of the shared medium among different contending flows. This paper proposes a flow rank based probabilistic fair scheduling technique. The main focus is to reduce the collision probability among the contending flows while maintaining the prioritized medium access for those flows, which ensures a weighted medium access control mechanism based on probabilistic round robin scheduling. Each flow maintains a flow-table upon which the rank is calculated and backoff value is assigned according to the rank of the flow, i.e., lower backoff interval to lower ranked flow. However, flow-table instability due to joining of a new flow, partially backlogged flow, hidden terminal and partially overlapped region exhibits a challenging problem that needs to be mitigated for our mechanism to work properly. We take appropriate measures to make the flow-table stabilized under such scenarios. Results show that our mechanism achieves better throughput and fairness compared to IEEE 802.11 MAC and existing ones.     

Distributed fair scheduling in a wireless LAN

Fairness is an important issue when accessing a shared wireless channel. With fair scheduling, it is possible to allocate bandwidth in proportion to weights of the packet flows sharing the channel. This paper presents a fully distributed algorithm for fair scheduling in a wireless LAN. The algorithm can be implemented without using a centralized coordinator to arbitrate medium access. The proposed protocol is derived from the Distributed Coordination Function in the IEEE 802.11 standard. Simulation results show that the proposed algorithm is able to schedule transmissions such that the bandwidth allocated to different flows is proportional to their weights. An attractive feature of the proposed approach is that it can be implemented with simple modifications to the IEEE 802.11 standard.     

区分服务网络中自适应加权调度方案的研究

针对现有区分服务网络中多服务间带宽公平性问题，提出了一种自适应加权调度方案。该方案通过对本地节点缓存区指标的定期测量，计算得到在各队列间公平分配剩余带宽的调度权值。仿真结果表明，该方案可以在网络负载变化时自适应的快速调整到理想调度值，有效改进了带宽分配的公平性。     

An active queue management scheme based on a capture-recapture model

One of the challenges in the design of switches/routers is the efficient and fair use of the shared bottleneck bandwidth among different Internet flows. In particular, various active queue management (AQM) schemes have been developed to regulate transmission control protocol traffic in response to router congestion. In addition, in order to provide fair bandwidth sharing, these AQM must protect the well-behaved flows from the misbehaving flows. However, most of the existing AQM schemes cannot provide accurate fair bandwidth sharing while being scalable. The key to the scalability and fairness of the AQM schemes is the accurate estimation of certain network resources without keeping too much state information. We propose a novel technique to estimate two network resource parameters: the number of flows in the buffer and the data source rate of a flow by using a capture-recapture (CR) model. The CR model depends on simply the random capturing/recapturing of the incoming packets, and as a result, it provides a good approximation tool with low time/space complexity. These network resource parameters are then used to provide fair bandwidth sharing among the Internet flows. Our experiments and analysis will demonstrate that this new technique outperforms the existing mechanisms and closely approximates the "ideal" case, where full state information is needed.     

用户系统基于流的QoS调度

Diff-Serv网与用户系统之间有服务等级协议，有必要对用户系统的分组流进行合理调度，以确保定购的服务等级上速率、突发比特量等符合协议要求。进行合理调度还有有效分配带宽好处。基于流的排队(FBQ)在加权公平分享带宽的同时起到流量整形(traffic shaping)的作用，比较适合这种调度要求。但FBQ对带宽利用率不够高，本文在FBQ分类结构基础上通过新颖的分配令牌参数和虚拟时钟的方法构建新的分级调度算法，保留FBQ优点但提高带宽利用率。     

On Supporting Weighted Service Differentiation in Multi-Packet Reception Wireless Networks: A Distributed Tree-Based Approach

The conventional medium access control (MAC) protocols assume that only one packet (frame) can be received at a given time. However, with the advent of spread spectrum, antenna arrays, and sophisticated signal processing techniques, it is now possible to achieve multiple-packet reception (MPR) in wireless networks. With MPR, the network capacity can be remarkably increased, but so far, how to achieve fair bandwidth allocation for the stations with different quality of service (QoS) requirements in such networks is still a problem. To solve this problem, we propose a distributed method that can support multiple priority classes in the MPR-capable wireless networks with weighted fair share. In particular, this method assigns each class a frame transmission probability to reflect its relative weight among the different data traffic flows. A closed-form expression of system throughput is derived for each class in the environment, and it is numerically evaluated with different simulation scenarios. The results show that the method can achieve the weighted fairness under different numbers of priority classes and different numbers of stations in the networks.     

基于收入值的IP网络带宽分配研究

现有IP网络采用尽力而为的方式传送数据,存在可运营性和可管理性差的问题.未来的IP网络必须能够对带宽进行有效的分配,保证对用户的服务质量,并实现运营商利益的最大化.本文提出一种基于收入值的通用带宽分配模型,将基于收入值的带宽分配问题分为完全满足带宽需求的严格带宽分配问题和部分满足带宽需求的灵活带宽分配问题,并证明其等效于背包问题.由于现有算法无法应用于实际的嵌入式系统,本文提出了一种改进贪婪算法(EGA)对基于收入值的带宽分配问题进行求解.在交换容量为128Gbps的分布式路由器上的实验结果表明,EGA是一种兼顾公平性和有效性的算法,能够在确定性时间内执行完毕.采用EGA的网络设备已运行于实际的运营商网络中.     

支持优先级与公平策略的队列规程

首先介绍了队列调度算法在流量控制中的关键地位,然后讨论了现有队列调度算法,如基于优先级的调度算法、轮询调度算法与公平队列调度算法,最后提出了一种新的队列规程,该队列规程融合了优先级调度算法与DRR调度算法。在网络正常情况下,不同业务流公平地共享网络带宽,在网络出现拥塞的情况下,高优先级业务流能够抢占带宽,保证其较低的丢包率,并能够实现两种调度算法的快速切换。     

An optimized scheduling scheme in OFDMA WiMax networks

This paper proposes an optimized scheduling scheme in OFDMA‐based WiMax networks to achieve both optimized system throughput and a complete QoS implementation for various types of traffic flows. Our scheduling scheme includes two components, one is the resource allocation for each user; the other is the QoS scheduling for various traffic sessions. Specifically an optimization problem is formulated to distribute all OFDMA channel resource among different competing users by exploiting the transmission adaption and multiuser diversity on each traffic channel. The optimized resource allocation can also be processed under different constraints to achieve different performance metrics. To ensure the WiMax QoS performance, we perform the resource allocation in a priority manner with respect to the different types of QoS requirements and get a desired transmission bandwidth for each user. Based on it we further schedule different traffic sessions at each user with respect to a proper admission control mechanism. The relevant solution and algorithms for our proposed scheduling scheme are presented in detail. Both the theoretical analysis and simulation results show that our scheme can achieve the key performance objectives such as complete QoS requirements, high channel transmission efficiency and optimal throughput over the whole OFDMA WiMax system. Copyright © 2009 John Wiley & Sons, Ltd.     

Wireless-adaptive fair scheduling for multimedia stream

As packet cellular networks are expected to support multimedia services, the authors incorporate the multimedia QoS requirements into the design of a new scheduling algorithm. The proposed wireless-adaptive fair scheduling tries to allocate time slots for each user with fair share by considering the varying channel condition while reflecting the stream requirements and achieving high throughput.