Access Restriction

Author Andrews, Matthew ♦ Awerbuch, Baruch ♦ Fernndez, Antonio ♦ Leighton, Tom ♦ Liu, Zhiyong ♦ Kleinberg, Jon
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Adversarial queuing theory ♦ End-to-end delay ♦ Network stability ♦ Packet scheduling
Abstract In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of $\textit{stability}—will$ the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks.(ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable.(iii) The $\textit{n}-node$ ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in $\textit{n}).(iv)$ There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay.Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 1
Page Count 31
Starting Page 39
Ending Page 69

Open content in new tab

   Open content in new tab
Source: ACM Digital Library