Back to Courses Catalog CDS 270 Syllabus

CDS 270 -- Fall 2006 First Term Optimization, Game and Layering in Communication Networks Prerequisites: Basic optimization theory, basic knowledge in communication networks. Course Description This course discusses various equilibrium solution concepts and convergent algorithms in optimization and game theory, and their applications to network design and control. The underlying theme is “network protocols as distributed algorithms achieving various equilibria”. The objective is to introduce mathematically rigorous tools for analyzing current network protocols and designing new ones. Topics will include: Equilibrium solution concepts and convergent algorithms in optimization and game theory, the utility maximization framework of TCP congestion control, layering as optimization decomposition, path algebra and routing, contention control, power control, and distributed mechanism design for network problems. Units and Grading 6 units (2-0-4); pass/fail, or letter grade. Lectures Wednesday 4 PM - 6 PM; 114 Steele Instructor Lijun Chen (chen@cds.caltech.edu) Office hours: by appointment Office: room 5 Steele; Ext. 3367 Announcements 01 Dec: The report will be due Monday, December 11th, if you take letter grade. 15 Nov: We will add a class this Friday, November 17th in 110 Steele at 4:00pm. 07 Nov: We will move this week's class to this Thursday, November 9th. 30 Oct: There will be no class this Wednesday, November 1st. We will re-schedule this class to another time. 27 Sep: I've requested the library to reserve the reference texts for the course. 23 Sep: Syllabus is posted. 21 Sep: The organizing meeting will be on Wednesday, September 27, 2006 in 114 Steele at 4:00 PM. The lectures will begin in the second week. 21 Sep: The course announcement. Course Material Overview Lecture 1: Static Games and Classical Mechanism Design (Lecture Notes) Readings: Drew Fudenberg and Jean Tirole, Game Theory, MIT Press, 1991, pp.3--44. Classic Mechanism Design, D. C. Parkes, Chapter 2 in PhD thesis, Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency, University of Pennsylvania, 2001. Mechanism Theory, M. Jackson, Encyclopedia of Life Support Systems, 2003. Lecture 2: Convex Optimization and Duality (Lecture Notes, guest lecture by Dr. Maryam Fazel) Readings: S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004, pp.215-258. This book is available on-line at http://www.stanford.edu/~boyd/cvxbook/ Lecture 3: Duality Model of TCP/AQM and Market Mechanism for Resource Allocation (Lecture Notes) Readings: Rate control in communication networks: shadow prices, proportional fairness and stability, F. P. Kelly, A.K. Maulloo and D. K. H. Tan, Journal of the Operational Research Society 49 (1998), 237-252. Optimization Flow Control, I: Basic Algorithm and Convergence, S. H. Low and D. E. Lapsley, IEEE/ACM Transactions on Networking, 7(6):861-75, December 1999. A Duality Model of TCP and Queue Management Algorithms, S. H. Low, IEEE/ACM Trans. on Networking, 11(4):525-536, August 2003. Lecture 4: Layering as Optimization Decomposition (Lecture Notes) Readings: Layering as optimization decomposition, M. Chiang, S. H. Low, A. R. Calderbank and J. C. Doyle, to appear in Proceedings of IEEE, January 2007. Lecture 5: Potential Games and the Inefficiency of Equilibria (Lecture Notes) Readings: Potential games, D. Monderer and L. S. Shapley, Games and Economic Behaviors, 14(1):124-143, 1996. Potential functions and the inefficiency of equilibria, T. Roughgarden, ICM, 2006. How bad is selfish routing?, T. Roughgarden and E. Tardos,Journal of the ACM, 2002.. Efficiency loss in a network resource allocation Game, R. Johari and J. N. Tsitsiklis, Mathematics of Operations Research, 2004. The price of stability for network design with fair cost allocation, E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler and T. Roughgarden, FOCS, 2004. Lectures 6-7: Network Routing and Path Algebra (Lecture Notes) Readings: Stable Internet routing without global coordination, L. Gao, J. Rexford, IEEE/ACM Trans. on Networking, 2001. The stable paths problem and interdomain routing, T. Griffin, F. Shepherd and G. Wilfong, IEEE/ACM Trans. on Networking, 2002. An algebraic theory of dynamic network routing, J. Sobrinho, IEEE/ACM Trans. on Networking, 2005. Lecture 8: S-modular Games and Power Control (Lecture Notes) Readings: Supermodular Games, J. Levin, 2003. A framework for uplink power control in cellular radio systems, R. D. Yates, IEEE Journal of Selected Areas in Communications, 1995. Efficient power control via pricing in wireless data networks, C. Saraydar, N. Mandayam and D. Goodman, IEEE Trans. on Communications, 2002. S-modular games and power control in wireless networks, E. Altman and Z. Altman, IEEE Trans. on Automatic Control, 2003. Lecture 9: Random Access Games and Medium Access Control Design (Lecture Notes) Readings: Random access games and medium access control design, L. Chen, S. Low and J. Doyle, 2006. Lecture 10: Distributed Mechanism Design Readings: Distributed algorithmic mechanism design: recent results and future directions, J. Feigenbaum and S. Shenker, Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2002. Sharing the cost of multicast transmissions, J. Feigenbaum, C. Papadimitriou and S. Shenker, Journal of Computer and System Sciences, 2001. A BGP-based mechanism for lowest-cost routing, J. Feigenbaum, C. Papadimitriou, R. Sami and S. Shenker, Distributed Computing, 2005. Incentive-compatible interdomain routing, J. Feigenbaum, V. Ramachandran and M. Schapira, Proceedings of the 7th Conference on Electronic Commerce, 2006. Useful Links Dr. Maryam Fazel's course on Convex Optimization and Applications. Acknowledgements Thanks to Prof. John Doyle and Dr. Maryam Fazel for their support and help. Many thanks also go to Prof. Steven Low for letting me to use and modify some of his lecture slides on congestion control, and Prof. Jennifer Rexford for letting me use and modify some of her lecture slides on routing.