Fast, Fair and Frugal Bandwidth Allocation in ATM Networks

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 all the sessions, and so some fair allocation scheme must be devised. The ATM Forum, the standards setting body for ATM networks, has specified that the fairness criterion for ABR traffic should be Max-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 protocol 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 O(1) computation on each RM Cell it receives, and it has O(1) local space for each session through it.