Making greed work in networks: a game-theoretic analysis of switch service disciplines

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, and (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.

REFERENCES

• 1: A. Bovopoulos and A. Lazar, "Decentralized Algorithms for Flow Control", Proceedings of the 25th Allerton Conference on Communication, Control, and Computing, University of Illinois at Urbana-Champaign, October 1987.
• 2: E. Coffman Jr. and I. Mitrani, "A Characterization of Waiting Time Performance Realizable by Single Server Queues", Operations Research, Vol. 28, No. 3 part II , May-June 1980.
• 3: A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm", Internetworking: Research and Experience, Vol. 1, pp. 3-26, 1990.
• 4: C. Douligeris and R. Mazumdar, "A Game Theoretic Approach to Flow Control in an Integrated Environment", Journal of the Franklin institute, Vol. 329, No. 3, pp. 383-402, March 1992.
• 5: C. Douligeris and R. Mazumdar, "On Pareto Optimal Flow Control in a Multiclass Environment", Proceedings of the 25th Allerton Conference on Communication, Control, and Computing, University of Illinois at Urba.na-Champaign, October 1987.
• 6: C. Douligeris and R. Mazumdax, "More on Pareto Optimal Flow Control", Proceedings of the 25th Allerton Conference on Communication, Control, and Computing, University of Illinois at Urbana-Champaign, October 1988.
• 7: D. Ferguson, C. Nikolaou, and Y. Yemini, "An Economy for Flow Control in Computer Networks", IEEE Infocom, 1989.
• 8: E. Friedman and S. Shenker, "Learning by Distributed Automata", preprint, 1993. (available from parcftp. parc.xerox.com as pub/net-research/learning.ps)
• 9: E. Hahne, "Round-Robin Scheduling for Max-Min Fairness in Data Networks", IEEE JSAC, Vol. 9, pp. 1024- 1039, 1991.
• 10: Man-tung T. Hsiao , Aurel A. Lazar, A Game Theoretic Approach to Decentralized Flow Control of Markovian Queueing Networks, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.55-73, December 07-09, 1987
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: J. Ja.ffe, "Bottleneck Flow Control". iEEE Transactions on Communications, Vol. 29, No. 7, pp. 954-962, July 1981.
• 13: R. Jain and K. K. Ramakrishnan, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals, and Alternatives", Proceedings of the Computer Networking Symposium, pp. 134-143, 1988.
• 14: R. Jain, A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks, ACM SIGCOMM Computer Communication Review, v.19 n.5, p.56-71, Oct. 1989 [doi>10.1145/74681.74686]
• 15: M. Katevenis, "Fast Switching and Fair Control of Congested Flow in Broadband Networks", IEEE JSA C, Vol. 5, pp. 1315-1326, 1987.
• 16: S. Keshav, "A Mechanism for Congestion Control in Computer Networks", preprint, 1989. (available from research.att.com as dist/qos/mechanism.ps)
• 17: Y. Korilis and A. Lazar, "Why is Flow Control Hard: Optimality, Fairness, Partial and Delayed Information", preprint, 1992. (available from ftp.ctr.columbia.edu as CTR-Research/comet/public/ papers/92/KOR92.ps.z)
• 18: Y. Korilis and A. Lazar, "On the Existence of Equilibria in Noncooperative Optimal Flow Control", Proceedings of ITC Workshop (Bangalore, India), pp. 243-251, 1993. (also available from ftp.ctr.columbia.edu as CTR- Research/comet/public/papers/93/KOR93.ps.gz)
• 19: E. Masldn, "The Theory of Implementation in Nash Equilibrium", in Social Goals and Organization: Essays in Memory of Elisha Pazner, Hurwicz, Schmeidler, and Sonnenschein eds., Cambridge University Press, 1985.
• 20: M. Miller and K. Drexler, "Markets and Computation: Agoric Open Systems", in The Ecology of Computation, B. Huberman editor., North Holland, 1988.
• 21: H. Moulin, "Joint Ownership of a Convex Technology: Comparison of Three Solutions", Review of Economic Studies, Vol. 57, pp. 439-452, 1990.
• 22: H. Moulin, "Uniform Externalities: Two Axioms for Uniform Allocation", Journal of Public Economics, Vol. 43, pp. 305-326, 1990.
• 23: H. Moulin and S. Shenker, "Serial Cost Sharing", Econometrica, Vol. 60, pp. 1009-1037.
• 24: H. Moulin and S. Shenker, "Average Cost Pricing versus Serial Cost Sharing: An Axiomatic Comparison", Journal of Economic Theory, forthcoming.
• 25: H. Moulin, "Cost Sharing under Increasing Returns", Games and Economic Behavior, forthcoming.
• 26: J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Vol. 35, pp. 435-438, 1987.
• 27: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• 28: J. Regnier, "Priority Assignment in Integrated Services Networks", Report LIDS-TH-1565, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, December, 1986.
• 29: R. Rob, "A Condition Guaranteeing the Optimality of Public Choice", Econometrica, Vol. 49, No. 6, pp. 1605- 1613, November 1981.
• 30: Berverly A. Sanders, An Asynchronous, Distributed Flow Control Algorithm for Rate Allocation in Computer Networks, IEEE Transactions on Computers, v.37 n.7, p.779-787, July 1988 [doi>10.1109/12.2223]
• 31: B. A. Sanders, An Incentive Compatible Flow Control Algorithm for Rate Allocation in Computer Networks, IEEE Transactions on Computers, v.37 n.9, p.1067-1072, September 1988 [doi>10.1109/12.2257]
• 32: M. SatterthwaJte and H. Sonnenschein, "Strategy-Proof Allocation Mechanisms at Differentiable Points", Re. view of Economic Studies, Vol. 48 , pp. 587-597, 1981.
• 33: S. Shenker, A theoretical analysis of feedback flow control, Proceedings of the ACM symposium on Communications architectures & protocols, p.156-165, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 34: Scott Shenker, Efficient Network Allocations with Selfish Users, Proceedings of the 14th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.279-285, September 12-14, 1990
• 35: S. Shenker, "On the Strategy-Proof and Smooth Allocation o~ Private Goods in a Production Economy", preprint, 1993. (available from parcftp.parc.xerox.com as pub/net-research/otss.ps)
• 36: S. Shenker, "Some Technical Results on Continuity, Strategy-Proofness, and Related Strategic Concepts", preprint, 1993. (available from parcftp.parc.xerox.com as pub/net-research/str.ps)
• 37: W. Thomson and H. Varian, "Theories of Justice Based on Symmetry", in Social Goals and Organization: Essays in Memory of Elisha Pazner, Hurwicz, Schmeidler, and Sonnenschein eds., Cambridge University Press, 1985.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.m MISCELLANEOUS

General Terms:
Algorithms, Management, Performance, Theory