ALCOMFT-TR-02-74

Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris Nikoletseas and Paul Spirakis
On the Stability of Compositions of Universally Stable, Greedy Contention-Resolution Protocols
Patras and Cyprus. Work packages 2 and 4. May 2002.

Abstract: \beginabstract A distinguishing feature of today's large-scale platforms for distributed computation and communication, such as the Internet, is their heterogeneity, predominantly manifested by the fact that a wide variety of communication protocols are simultaneously running over different distributed hosts. A fundamental question that naturally poses itself for such common settings of heterogeneous distributed systems concerns the preservation (or loss) of important correctness and performance properties of the individual protocols when they are composed in a large network. In this work, we address this foundational question for the specific case of stability properties of greedy, contention-resolution protocols operating over a packet-switched communication network.

We focus on a basic adversarial model for packet arrival and path determination for which the time-averaged arrival rate of packets requiring a single edge is no more than 1. Roughly speaking, a contention-resolution protocol arbitrates the cases where more than one packet wants to advance over a given queue in a single time step. Stability requires that the number of packets in the system remains bounded, as the system runs for an arbitrarily long period of time. It is known that several commonly used contention-resolution protocols, such as LIS ( Longest-in-System), SIS ( Shortest-in-System), NTS ( Nearest-to-Source), and FTG ( Furthest-to-Go) are universally stable in this setting - that is, they are stable over all networks. We investigate the preservation of universal stability under compositions for these four greedy, contention-resolution protocols. We discover:

• The composition of any two policies among SIS, NTS and FTG is universally stable.

• The composition of LIS with any of SIS, NTS and FTG is not universally stable: we provide interesting combinatorial constructions of networks over which the composition is unstable when the adversary's injection rate is at least 0.519.

• Through an involved combinatorial construction, we significantly improve the current state-of-the-art record for the adversary's injection rate that implies instability for the FIFO ( First-In-First-Out) protocol to 0.749. Since 0.519 is significantly below 0.749, this last result suggests that the potential for instability incurred by the composition of two universally stable protocols may be worse than that of some single protocol that is not universally stable.

\endabstract

Postscript file: ALCOMFT-TR-02-74.ps.gz (304 kb).