Resource Allocation and Networking Games

Lectures:
Wednesday 5:00-7:00pm
Room 102 WWH

Office hours:
Wednesday 7:00-8:00pm
Room 401 WWH

Lucent Technologies, Bell Labs
101 Crawfords Corner Rd., Rm. 4G-602
Holmdel, NJ 07733
Tel: 732-949-6723 Fax: 732-949-0399

Final Examination: Get the postscipt file here. Click on this link to download an article you need for question 5.
No class on 3/11/98, 4/1/98.
Take some time to familiarize yourself with MReX.

Introduction	Future broadband/multimedia networks will support a wide variety of service classes, each with its own traffic characteristics and quality of service requirements. Efficient allocation of network resources will be one of the most crucial factors in such networking environments. Allocation of resources is determined by the interaction among various controllers (e.g., flow controllers, routers) that are distributed along the network. This interaction can be modeled as game. The goal of the course is to present the state of the art in resource allocation with emphasis on networking games.
Course Outline	Resource allocation in single-class networks: flow control, routing. Multi-class networks: classification of network control algorithms, motivation of the game-theoretic formulation, the greedy algorithm; Network control games: flow control, routing, virtual path bandwidth reservation; Applications to network design and management: motivation, the Braess paradox, architecting network resources and user flows; Network pricing: pricing of congestible network resources, economics of the Internet.
Prerequisites	A course on computer communication networks, or stochastic processes, or instructor's approval.
Reading material	No required textbook. A selection of articles will be distributed in class (hard copies and through this web page.
Homework	All homework assignments are optional, but strongly recommended.
Exams	Midterm; Final (24-hour take home exam).

Related Reading:

Optimal Control in Single-Class Networks

A. A. Lazar, "The Throughput Time Delay Function of an M/M/1 queue," IEEE Transactions on Information Theory, vol. 29, pp. 914-918, November 1983.
Aurel A. Lazar, "Optimal Control of a Class of Queueing Networks in Equilibrium," IEEE Transactions on Automatic Control, vol. 28, no. 11, pp. 1001-1007, November 1983.
D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, Second edition, 1992. [ Sections 5.3-5.4]

The Game of Networking: Motivation and Game-Theory Fundamentals

K. Bharath-Kumar and J. M. Jaffe, "A New Approach to Performance Oriented Flow Control," IEEE Transactions on Communications, vol. 29, pp. 427-435, April 1981.
J. M. Jaffe, "Flow Control Power is Nondecentralizable," IEEE Transactions on Communications, vol. 29, pp. 1301-1306, September 1981.
Roger B. Myerson, Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, MA, 1991.

Network Control Games

Christos Douligeris and Ravi Mazumdar, "A Game-Theoretic Approach to Flow Control in an Integrated Environment," Journal of the Franklin Institute, pp. 383-402, March 1992.
Zhensheng Zhang and Christos Douligeris, "Convergence of Synchronous and Asynchronous Greedy Algorithms in a Multiclass Telecommunications Environment," IEEE Transactions on Communications, vol. 40, no. 8, pp. 1277-1281, August 1992.
M.-T. T. Hsiao and Aurel A. Lazar, "Bottleneck Modeling and Decentralized Optimal Flow Control," in Proceedings of the 18th Conference on Information Sciences and Systems, pp. 169-173, Princeton, NJ, March 1984.
M.-T. T. Hsiao and Aurel A. Lazar, "Optimal Decentralized Flow Control of Markovian Queueing Networks with Multiple Controllers," Performance Evaluation, vol. 13, no. 3, pp. 181-204, 1991.
Yannis A. Korilis and Aurel A. Lazar, "On the Existence of Equilibria in Noncooperative Optimal Flow Control," Journal of the ACM, vol. 42, No. 3, pp. 584-613, May 1995.
Ariel Orda, Raphael Rom, and Nahum Shimkin, "Competitive Routing in Multiuser Communication Networks," IEEE/ACM Transactions on Networking, vol. 1, pp. 510-521, October 1993.

Architecting Noncooperative Networks: Applications to Network Design and Management

Yannis A. Korilis, Aurel A. Lazar and Ariel Orda, "Architecting Noncooperative Networks," in IEEE Journal in Selected Areas on Communications, vol. 13, no. 7, pp. 1241-1251, September 1995.
Yannis A. Korilis, Aurel A. Lazar and Ariel Orda, "Capacity Allocation under Noncooperative Routing," IEEE Transactions on Automatic Control, vol. 42, no. 3, pp. 309-325, March 1997.
Yannis A. Korilis, Aurel A. Lazar, and Ariel Orda, "Achieving Network Optima Using Stackelberg Routing Strategies," IEEE/ACM Transactions on Networking, vol. 5, no. 1, pp. 161-173, February 1997.
Yannis A. Korilis, Aurel A. Lazar, and Ariel Orda, "Avoiding the Braess Paradox in Noncooperative Networks," Bell Laboratories Technical Memorandum, December 1996. Under revision for the Journal of Applied Probability.

Scott Shenker, "Making greed work in networks: A game-theoretic analysis of switch service disciplines," in IEEE/ACM Transactions on Networking, vol. 3, pp. 819-831, December 1995.

Network Pricing

Jeffrey K. MacKie-Mason and Hal R. Varian, "Pricing Congestible Network Resources," IEEE Journal on Selected Areas in Communications, vol. 13, no. 7, pp. 1141-1149, September 1995.
R. Cocchi, S. Shenker, D. Estrin, and L. Zhang, "Pricing in Computer Networks: Motivation, Formulation and Example," IEEE/ACM Transactions on Networking, vol.1, pp. 617-627, October 1993.
Ariel Orda and Nahum Shimkin, "Incentive Pricing in Multi-Class Communication Networks," in Proceeding of the IEEE INFOCOM'97, Kobe, Japan, April 1997.
Yannis A. Korilis, Theodora A. Varvarigou, and Sudhir R. Ahuja, " Pricing Noncooperative Networks," Bell Laboratories Technical Memorandum, May 1997. Submitted to the IEEE/ACM Transactions on Networking.

To be added.