582363: Mathematical Modelling for Computer Networks

582363: Mathematical Modelling for Computer Networks

Spring 2013 (11.03.2013 to 26.04.2013)


Contents:


General Info

The course is a 2 credit advanced level module optional course.
Instructors: Laila Daniel and Krishnan Narayanan
Email: {ldaniel, narayana}@cs.helsinki.fi
Office hours: C 213, Thursday 12:00 - 13:00 or by appointment.

Class Timings and Location.
Lecture class: Mon 14-16, C222
Exercise class: Fri 12-14, C222

Course Description

As networking systems such as the Internet, wireless and mobile networks are becoming increasingly versatile and complex, mathematical methods for modelling, analysis and design of computer networks and their protocols have become important.

A wide variety of mathematical tools and techniques drawn from the areas of convex optimization, stochastic modelling and control theory help to unify and to understand the key concepts of protocol design for optimum performance in computer networks. Concern for optimal operation of networks is quite often of crucial importance in protocol design due to the scarcity of resources such as wireless spectrum and battery lifetime.

In this course some of the major mathematical concepts and techniques underlying modern network design are described in the setting of concrete examples drawn from network design problems such as congestion control, wireless scheduling and multiaccess protocols. The significance of these concepts and tools go far beyond the setting of the specific examples in which they are presented. As the mathematical topics we use here are quite vast and varied fields by themselves, we focus on how these different tools are often brought together to provide an understanding of the given problem in network design. We do not develop the mathematics beyond what is necessary to understand the networking examples we consider.

Much of this material is scattered in journal articles and is fairly recent. Self-contained lecture notes will be provided to follow the lectures. The course intends to build the background and knowledge to be able to understand the key ideas described in the cited papers in each module. The books/papers that are cited here are invaluable sources to learn the material at an advanced/research level and they contain a lot more material than we need in the course. We hope the students will be inspired to look at them.

The course aims to give an application-oriented network engineer a structured introduction to these concepts and tools and the motivation for further study in this direction.

Course Audience

Prerequisites


Course Structure

The course has two modules.

  • Module 1: Convex Optimization and Congestion Control
  • Module 2: Markov Chains and Multiaccess Protocols
  • Three lecture classes and three exercise classes are devoted to each module. Lecture notes will be provided for each of the modules adapted from the original papers/books that are given in the reference section of each module. The papers and books are labelled as Pxx - Paper xx, and Bxx - Book xx. A sequel to this course is being planned for Autumn 2013.

    Course Contents

  • Module 1: Convex Optimization and Congestion Control

  • Insight into the congestion control protocol TCP has led to the discovery that the protocol can be viewed as a distributed solution to a network-wide global optimization problem. This point of view has brought forth a unified understanding of the various versions of TCP as well as a framework for network protocol design in general. In this module we present an overview of this modelling and its consequences by introducing some key papers on the topic.
    References
  • P11. D-M. Chiu and R. Jain Analysis of the Increase and Decrease. Algorithms for Congestion Avoidance in Computer Networks. Journal of Computer Networks and ISDN Systems, Volume 17, Issue 1, 1989, pages 1 - 14.
  • P12. V. Jacobson Congestion avoidance and control. Proceeding SIGCOMM '88 Symposium proceedings on Communications architectures and protocols, 1988, pages 314-329
  • P13. F. Kelly, A. Maulloo and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49, 1998, pages 237-252
  • P14. S. Shakkottai and R. Srikant. Network Optimization and Control. Now publishers, 2007
  • P15. S. Low. A Duality Model of TCP and Queue Management Algorithms. IEEE/ACM Transactions on Networking (TON), Volume 11 Issue 4, August 2003, pages 525 - 536
  • P16. M. Chiang, S. H. Low, A. R. Calderbank, J C Doyle. Layering As Optimization Decomposition: A Mathematical Theory of Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures. Proceedings of the IEEE, vol. 95, no. 1, pages 255-312, January 2007
  • B11 R. Srikant. The Mathematics of Internet Congestion Control. Birkhauser, 2004. One book is available in the Reference section of the Kumpula Library
  • B12. S. Boyd and L. Vandenbergh. Convex Optimization. Cambridge University Press, 2004
  • Module 2: Markov Chains and Multiaccess Protocols

  • The stability analysis of Markov chains and the rapidly mixing property of Markov chains describe the convergence of the Markov chain to the equilibrium distribution and the speed of convergence to the equilibrium distribution. These issues are of prime importance in numerous settings in wireless networks. The focus of this module is the study of these concepts in the context of multiaccess protocols.
    References
  • B21. A.S. Tanenbaum. Computer Networks. Prentice Hall
  • B22. D. Bertsekas and R. Gallager. Data Networks
  • B23. P. Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer 2008
  • B24. S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability, Springer, 1993
  • B25. D. Levin, Y. Peres and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008
  • Useful Mathematical References

  • Grimmett and Stirzaker. Probability and Random Processes. 3rd edition. Oxford University Press, 2001.
  • Grimmett and Stirzaker. Probability and Random Processes: Problems and Solutions. 3rd Edition. Oxford University Press, 2001.
  • S.M. Ross. Stochastic Processes. Wiley, Second Edition, 1996.
  • C.M. Grinstead and J.L. Snell. Introduction to Probability, American Mathematical Society, 1997.
  • J.R. Norris. Markov Chains. Cambridge University Press, 1998.
  • G. Strang. Introduction to Linear Algebra, 4th edition. Wellesley-Cambridge Press and SIAM, 2009.
  • Further reading on Local-Global Principle

  • R. Feynman. Principle of Least Action. Physics Lectures Vol. 2 Chapter 19.
  • L. Susskind. Lectures on Classical Mechanics

  • Passing the Course

  • Taking the course exam (max. 50 points available, min. 25 points required for passing)
  • Participating actively in the weekly exercises that may give max. 10 points.
  • A passing grade requires at least 30 points in total.

  • Lecture Notes and Slides

  • Introduction to the course
  • Congestion Control

  • Chiu-Jain Model of Congestion Control.      Slides
  • Utility, Fairness and Optimization in Resource Allocation.      Slides
  • Optimization Framework for Congestion Control Algorithms - I       Slides
  • Optimization Framework for Congestion Control Algorithms - II      Slides

  • Multiaccess Protocols

  • Introduction to Multiaccess protocols      Slides
  • Markov Chain model for ALOHA protocol      Slides

  • Math Refresher

  • Convex Optimization
  • Vectors-Matrices-Linear Algebra
  • Calculus


  • Exercises

    Congestion Control

  • Exercise 1    Solutions
  • Exercise 2    Solutions
  • Exercise 3    Solutions
  • Markov Chains

  • Exercise 4    Solutions
  • Exercise 5    Solutions
  • Exercise 6    Solutions

  • Announcements