Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines

TitleMaking Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines
Publication TypeJournal Article
Year of Publication1995
AuthorsShenker, S.
Published inIEEE/ACM Transactions on Networking
Other Numbers3504

This paper discusses congestion control from a game-theoretic perspective. There are two basic premises: 1) Users are assumed to be independent and selfish. 2) Central administrative control is exercised only at the network switches. The operating points resulting from selfish user behavior depend crucially on the service disciplines implemented in network switches. This effect is investigated in a simple model consisting of a single exponential server shared by many Poisson sources. We discuss the extent to which one can guarantee, through the choice of switch service disciplines, that these selfish operating points will be efficient and fair. We also discuss to what extent the choice of switch service disciplines can ensure that these selfish operating points are unique and are easily and rapidly accessible by simple self optimization techniques. We show that no service discipline can guarantee optimal efficiency. As for the other properties, we show that the traditional FIFO service discipline guarantees none of these properties, but that a service discipline called fair share guarantees all of them. While the treatment utilizes game-theoretic concepts, no previous knowledge of game theory is assumed

Bibliographic Notes

IEEE/ACM Transactions on Networking, Vol. 3, Issue 6, pp. 819-831. An earlier version of this paper appeared in the proceedings of ACM Special Interest Group on Data Communications Conference (SIGCOMM 1994), London, UK, August 1994.

Abbreviated Authors

S. Shenker

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in journal or magazine