Thumbnail
Access Restriction
Open

Author Bartal, Yair ♦ Farach-Coltont, Martin ♦ Yoosepht, Shibu ♦ Zhangs, Lisa
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Atm Forum ♦ Minimum Amount ♦ Rm Cell Mechanism ♦ Rm Cell ♦ Protocol Frugal ♦ Particular Available Bit Rate ♦ Frugal Rm Cell Protocol ♦ Important Part ♦ Cell Mechanism ♦ Rm Cell Processing ♦ Resource Management ♦ Maz-min Fairness ♦ Constant Fraction ♦ Max-m Fair State ♦ Atm Network ♦ Maximum Round-trip Time ♦ Second Type ♦ Convergence Time ♦ Fair Allocation Scheme ♦ Local Space ♦ Mcr Request ♦ Abr Trafhc ♦ First Frugal Rm Cell Protocol ♦ Linear Number ♦ Non-frugal Protocol ♦ Quadratic Convergence Rate ♦ Fast Fair ♦ Minimum Cell Rate ♦ Abr Traffic ♦ Max-min Fair Allocation ♦ Fairness Criterion ♦ Network Design ♦ Frugal Bandwidth Allocation ♦ Several Frugal Rm-cell Protocol ♦ Reasonable Protoc61 ♦ Max-min Fair Manner
Description Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms
ATM networks are used to carry a variety of types of traffic. For some types of traffic, in particular Available Bit Rate (ABR) traffic, the bandwidth of a network is typically insufficient to satisfy the requests of al1 the sessions, and so some fair allocation scheme must be devised. The ATM Forum, the standards setting body for ATM networks, has snecified that the fairness criterion for ABR trafhc should 6e Maz-Min Fairness, which intuitively means that raising the bandwidth of any session comes at the expense of some other session of no greater bandwidth. Protocols to allocate bandwidth to sessions in a max-min fair manner are an important part of a network design. For a protocol to be realistic, it must conform to the Resource Management (RM) Cell mechanism specified by the ATM Forum. Such RM Cells get sent as a constant fraction of all cells sent by the source, however they have only a few fields. RM Cells are the only means of communication allowed between switches so any reasonable protoc61 is totally distributed and asynchronous, since the RM Cell mechanism does not easily lend itself to synchronization. Finally, RM Cells must be handled very quickly at the switches. We call a protocol frugal if the switch spends 0 computation on each RM Cell it receives, and it has 0 local space for each session through it. Recently, several frugal RM-Cell protocols have been VroDosed for ABR traffic. but none have been shown to conkrge to the max-m & fair state. Protocols that are known to converge in a linear number of maximum round-trip times require RM Cell processing that is linear in the number of sessions at a switch. In this paper, we give a frugal RM Cell protocol for ABR that matches the convergence time of the fastest known non-frugal protocol. A second type of ABR traffic is the Minimum Cell Rate (MCR) type, where every session can specify a minimum amount of bandwidth. The max-min fair allocation should then respect these MCR requests. We extend our results to give the first frugal RM Cell protocol for MCR and achieve a quadratic convergence rate. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1999-01-01