Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines
Title | Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines |
Publication Type | Journal Article |
Year of Publication | 1995 |
Authors | Shenker, S. J. |
Published in | IEEE/ACM Transactions on Networking |
Volume | 3 |
Issue | 6 |
Page(s) | 819-831 |
Other Numbers | 3504 |
Abstract | 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 |