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
This course is an advanced-level course and is offered in the stream
of Computer networks for students at the masters and research level in
Computer Science, Communications Engineering and Applied
Mathematics. This course can also be taken by anyone interested in the
mathematical principles/theory of computer networking.
Prerequisites
The participants are expected to have taken a first course in Data
communications and (or) Computer networks. A basic familiarity with
calculus, probability and linear algebra (matrices) is assumed. The
first exercise class in the first week of the course will provide a
concise review of the mathematical background in calculus, probability
and linear algebra.
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
- There will be a separate exam for this course on 04.06.2013 TUE 16-20 A111.
- Please fill in the teaching evaluation form. Thank you.
- Exam results are announced.
- Exercise 6 is online.
- Exercise 5 is online.
- Exercise 4 is online.
- Exercise 3 is online.
- Exam: Tuesday, 7th May 2013 at 16:00 in B123.
- Exercise 2 is online.
- Lecture class on Convex optimization on 22nd March 2013. Please bring a copy of the lecture notes on Convex Optimization.
- Slides of the lecture class on 18th March is online.
- Exercise 1 is online.
- Lecture notes for 11th March is online. Please bring a copy of the lecture notes so that you can add your own notes in the margins during the lecture.
- Lecture notes - Math refresher online.
- The first lecture class is on Mon., March. 11th, 2013.
- The first exercise class is on Fri., March. 15th, 2013.
- Welcome!