Universal-stability results and performance bounds for greedy contention-resolution protocols

In this paper, we analyze the behavior of packer-switched communication net works in which packets arrive dynamically at the nodes and are routed in di screte time steps across the edges. We focus on a basic adversarial model o f 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 netw orks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolut ion protocols. A crucial issue that arises in such a setting is that of sta bility--will the number of packets in the system remain bounded, as the sys tem runs for an arbitrarily long period of time? We study the universal sta bility of networks (i.e., stability under all greedy protocols) and univers al stability of protocols (i.e., stability in all networks). Once the stabi lity of a system is granted, we focus on the two main parameters that chara cterize 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 n-node ring is stable for all greedy routing protocols (with maxi mum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is s table for all networks and requires only polynomial queue size and polynomi al 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.