Integration of synchronous and asynchronous traffic on the MetaRingand its performance study

The main motivation for developing the MetaRing architecture was to increase the throughput of a ring-based local area network beyond its single link capacity by means of spatial bandwidth reuse. We describe and evaluate a protocol for integrating two types of traffic on the MetaRing architecture. Synchronous (reserved or real-time) traffic which is periodic and requires a connection set-up and will have guaranteed bandwidth and bounded delay, and asynchronous or bursty traffic with no real-time constraints that can use the remainder of the bandwidth in a fair manner. The integration mechanism is functionally equivalent to the timed-token function in FDDI, which is a shared media ring protocol. Simulation results are also presented to show the effects of the fairness and flow control signals on the performance of the network     

MetaRing-a full-duplex ring with fairness and spatial reuse

The design principles of a ring network with spatial bandwidth reuse are described. A distributed fairness mechanism for this architecture, which uses low latency hardware control signals, is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integration of asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: buffer insertion mode for variable-size packets and slotted mode for fixed-size packets or cells. Concurrent access and spatial reuse allow simultaneous transmissions over disjoint segments of a bidirectional ring and can increase the effective throughput by a factor of four or more. The combination of a full-duplex ring, spatial reuse, a reliable fairness mechanism, and the exploitation of advent in fiber-optic technology are the basis for the MetaRing network architecture     

RED分组丢弃算法性能研究

 本文研究了在ATM交换机上实现的RED算法的性能.在固定有效带宽、时变有效带宽情况下和同种、异种业务环境下,研究了RED算法的通过率、公平性和时延等性能.经研究表明:RED算法有必要与EPD算法相结合,构成RED+EPD算法.采用RED+EPD算法的ATM交换机通过控制平均排队长度,有效地减小了交换机的平均排队时延.通过与其他分组丢弃算法进行性能比较表明:采用RED+EPD算法的ATM交换机,可提供比EPD算法略高的通过率,更好的公平性和更低的排队时延,能较好地支持具有时延要求的业务.     

RPR环网中的一种带宽公平分配算法

首先讨论了RPR网络中的公平性原则,然后结合该原则引入了一种适合于RPR网络的公平分配方案,基于该方案提出了一种能满足RPR环网性能要求的公平分配算法。该算法通过采用控制的方法为共享某链路的各数据流合理地分配带宽资源,从而达到:(1)各流的速率达到稳定;(2)链路缓存的占有量稳定到一个目标值;(3)链路带宽得到充分利用且实现公平分配。同时该算法能顺次协同地处理完网络中的各个链路,从而能够实现整个RPR环网的公平性与高的链路带宽利用率,达到RPR协议所要求的目标。给出了该算法的代码描述并对其作出稳定性分析,然后通过仿真对其性能进行了验证。     

The no slot wasting bandwidth balancing mechanism for dual busarchitectures

A bandwidth balancing (BWB) mechanism has been added to the distributed queueing algorithm of the distributed-queue dual bus (DQDB) network. BWB can provide the requested throughputs by lightly loaded stations and evenly distribute the remaining channel bandwidth among overloaded stations. However, its operation requires the wastage of channel slots. The authors introduce a new bandwidth balancing mechanism for DQDB. The operation of the new mechanism requires one additional bit in the access control field (ACF) of the slot but has the advantage of exhibiting a similar behavior with the current BWB mechanism of DQDB without wasting any channel slots. For this reason, it can converge faster to the steady state in which fair bandwidth allocation is achieved. The authors investigate the throughput and delay performance of the proposed mechanism under one traffic class and examine its capacity to support multiple priority classes of traffic. They also compare its performance with the corresponding performance of the BWB mechanism of DQDB     

Analysis of fair rate calculations in resilient packet ring aggressive mode

Resilient packet ring (RPR) standardized as IEEE 802.17 is a new medium access control (MAC) protocol for metro-ring networks. RPR supports spatial reuse which increases the achieved throughput but it can also result in congestion and starvation of nodes on the ring. Therefore, it is necessary to employ mechanisms to enforce a fair allocation of the ring bandwidth in RPR. In order to maintain fairness among nodes, a fairness algorithm is deployed at each RPR node. When a node detects congestion, it calculates a fair rate which is advertised to all upstream nodes contributing to congestion. Upon receiving the fair rate, the upstream nodes limit the rate of their injected traffic to the advertised fair rate. Consequently, the congested node can utilize the unused capacity and add its local traffic to the ring. In this paper, we develop an analytical model for fair rate calculation in the RPR aggressive mode fairness algorithm in the parking-lot scenario. This model provides an insight on dynamics of the RPR fairness algorithm and can be used to evaluate its performance. We investigate this problem in two cases. First, we assume that the link propagation delay is zero and derive the fair rate equations for this ideal case. We then consider the link propagation delay and develop a more realistic model. We verify the accuracy of our model by simulation results. Furthermore, we use the developed model to study the impact of various parameters on convergence of the fair rate.     

Performance analysis and design of CQBT algorithm for a ringnetwork with spatial reuse

A full-duplex ring network combined with destination removal can achieve a network throughput level much higher than the channel's data rate. However, such a network exhibits fairness problems, particularly under asymmetric-loading conditions. We propose and study a local regulation protocol, the check-quota-before-transmission (CQBT) algorithm, to effectively reduce the unfairness features associated with such a network. Under this algorithm, each heavily loaded node monitors its local traffic conditions to determine the access opportunities provided to its downstream neighboring nodes. A procedure to determine the value of the regulation parameters associated with such an algorithm is also presented. Illustrative performance examples are shown to demonstrate the effectiveness of this algorithm. In addition, through the use of analytical approximations, we present a discrete time vector Markov chain model to analyze the queueing behavior of such a full-duplex slotted ring. The analytical performance results are shown to be close to those obtained by simulations     

The IEEE 802.17 media access protocol for high-speed metropolitan-area resilient packet rings

The resilient packet ring (RPR) IEEE 802.17 standards is under development as a new high-speed technology for metropolitan backbone networks. A key performance objective of PRP is to simultaneously achieve high utilization, spatial reuse, and fairness, an objective not achieved by current technologies such as SONET and Gigabit Ethernet or legacy ring technologies, such as FDDI. The core technical challenge for RPR is the design of a fairness algorithm that dynamically throttles traffic to achieve these properties. The difficulty is in the distributed nature of the problem, that upstream ring nodes must inject traffic at a rate according to congestion and fairness criteria downstream. This article provides an overview of the RPR protocol with a focus on medium access and fairness.     

一种基于高速弹性分组环的线性逼近公平算法

弹性分组环(RPR)中最关键的技术之一是环路分布式公平算法.IEEE802.17工作组制定的RPR草案中关于公平算法存在一些待完善的问题,比如在高速的网络中存在较长的收敛时间,同时对于非平衡流带来的永久性震荡现象也无法消除.本文针对上述这些问题提出了一种新的公平算法.仿真结果表明算法不仅能够消除非平衡流问题,而且能够公平地控制站点之间带宽的分配.     

Design and evaluation of an efficient traffic control scheme for integrated voice,video, and data over asynchronous transfer mode networks: Explicit allowed rate algorithm

Asychronous transfer mode (ATM) networks are high‐speed networks with guaranteed quality of service. The main cause of congestion in ATM networks is over utilization of physical bandwidth. Unlike constant bit‐rate (CBR) traffic, the bandwidth reserved by variable bit‐rate (VBR) traffic is not fully utilized at all instances. Hence, this unused bandwidth is allocated to available bit‐rate (ABR) traffic. As the bandwidth used by VBR traffic changes, available bandwidth for ABR traffic varies; i.e., available bandwidth for ABR traffic is inversely proportional to the bandwidth used by the VBR traffic. Based on this fact, a rate‐based congestion control algorithm, Explicit Allowed Rate Algorithm (EARA), is presented in this paper. EARA is compared with Proportional Rate Control Algorithm (PRCA) and Explicit Rate Indication Congestion Avoidance Algorithm (ERICA), in both LAN and WAN environments. Simulations of all three algorithms are conducted under both congestion and fairness configurations with simultaneous generation of CBR, rt‐VBR, nrt‐VBR and ABR traffic. The results show that, with very small over‐head on the switch, EARA significantly decreases the required buffer space and improves the network throughput. Copyright © 1999 John Wiley & Sons, Ltd.     

Local and congestion-driven fairness algorithm in arbitrarytopology networks

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm: i) locality and congestion-driven-only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by “the maximal clique in what we call the conflict graph to which a node belongs,” and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes)     

弹性分组环基于流的公平算法的研究

IEEE802．17弹性分组环是宽带城域网的新型技术。凭着本地公平算法、空间重利用、带宽统计复用、正常状态双环均传输业务等特点从而和传统环网相比,弹性分组环在带宽利用方面具有较大的优势。公平算法对弹性分组环发挥其带宽利用优势具有极其重要的作用,而目前的基于节点公平算法不能完全发挥弹性分组环的优势。文章在更能发挥弹性分组环带宽利用优势的基于流的公平策略的基础上,建立相应的算法方案,并进行计算机仿真验证。实验结果验证了理论分析。     

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.     

弹性分组环中的公平算法浅析

弹性分组环（RPR,Resilient Packet Ring）作为下一代高速城域网的核心技术,具有高的带宽利用率、空间再利用和公平性等优良的特性。但要动态地获得这些特性,必须设计合理的带宽分配算法。文章指出了目前所采用的公平算法中存在的一些问题,探讨了一种更新的带宽分配算法;分布式虚拟时间调度（DVSR,Distributed Virtual-time Scheduling in Rings）算法。     

A Novel Bandwidth Allocation Algorithm for IEEE 802.16 TDD Mode Wireless Access Networks

In this paper, we propose a novel bandwidth allocation algorithm for a two-tier hierarchy in IEEE 802.16 time division duplex mode wireless access networks under symmetric and/or asymmetric uplink and downlink traffic input. We demonstrate the performance of the new bandwidth allocation algorithm in terms of accumulated throughput (cumulative bandwidth) and fairness in both infinite and finite buffer cases compared with others by simulations. The simulation results show that the proposed algorithm not only can provide much better fairness and maintain satisfactory QoS support and high cumulative bandwidth but also in the case of finite buffer depth is less buffer-consuming than the others, meaning that the hardware cost can be reduced by employing the proposed algorithm.     

On the cost of fairness in ring networks

The impact of fairness on the throughput of ring networks with spatial reuse is investigated. A model for a slotted ring with spatial reuse that employs a simple fairness mechanism is presented. An exact expression for the expected time taken to evacuate this ring when each node initially contains one packet is derived. The expected evacuation time is used to obtain an exact expression for the throughput of the ring. It is shown that as the number of nodes on the ring increases, the penalty for fairness in terms of throughput becomes negligible     

RPR公平算法的实现及其在MSTP环网中的应用

在将RPR内嵌入MSTP并应用于城域环网时,公平算法(FA)无疑是最重要的RPR特性之一.本文首先介绍RPR公平算法的基本原理,并在此基础上,进一步分析了公平算法在不同层次城域环网应用中的公平使用带宽特性,及其对空间再利用特性的支持.     

A study of slot reuse in dual bus multiple access networks

In dual unidirectional bus networks, packets usually occupy fixed-length slots form the sending station to the end of the network. An erasure node is a specialized station which recognizes packets which have passed their destination stations and releases the slots for subsequent use. The authors derive the optimal locations for erasure nodes and show analytically, for uniform traffic, that only several erasure nodes are needed to achieve throughput close to twice the nominal network bandwidth. The results are tested by simulation of the DQDB (distributed queue dual bus) protocol, which demonstrates a realistic improvement of 40% with only three erasure nodes. Fair access among the stations is improved as well. The authors generalize the analytic results by providing an algorithm for determining the optimal erasure node locations and the throughput improvement, given any arbitrary traffic pattern. The application of this methodology to the related problem of bridged subnetworks is briefly discussed     

Randomly Ranked Mini Slots for Fair and Efficient Medium Access Control in Ad Hoc Networks

Ad hoc networks offer infrastructure-free operation, where no entity can provide reliable coordination among nodes. Medium access Control (MAC) protocols in such a network must overcome the inherent unreliability of the network and provide high throughput and adequate fairness to the different flows of traffic. In this paper, we propose a MAC protocol that can achieve an excellent balance between throughput and fairness. Our protocol has two versions: randomly ranked mini slots (RRMS) utilizes control-message handshakes similar to IEEE 802.11. Randomly ranked mini slots with busy tone (RRMS-BT) is the better performer of the two, but requires a receiver busy tone. The protocol makes use of granule time slots and sequences of pseudorandom numbers to maximize spatial reuse and divide the throughput fairly among nodes. We demonstrate the performance of this protocol using simulation with fixed and random topologies and show that these results are robust to difficult network configurations and unsynchronized clocks. We further develop novel metrics of long-term and short-term fairness for rigorous performance evaluation. Our simulation results include a detailed comparison between the proposed protocol and existing protocols that have been shown to excel in terms of throughput or fairness     

A two-layer window-based fairness control scheme for rings withspatial reuse

Quota-based fairness control on a ring with spatial reuse inherently brings about bandwidth waste due to a nature of fairness control. This paper suggests a cycle window and proposes a fairness control scheme based on a two-layer window composed of cycle and packet windows, under which the otherwise wasted bandwidth can be reused to carry, in advance, packets allocated to future fairness cycles