582363: Mathematical Modelling for Computer Networks - Part II

582363: Mathematical Modelling for Computer Networks - Part II

Autumn 2013 (29.10.2013 to 06.12.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: Tue 14-16, B119
Exercise class: Fri 12-14, B119

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.

The course focusses on two topics, Network coding and Large Deviation analysis, of active current interest in networking in which mathematical modelling and analysis plays a crucial role. Modelled along the lines of an earlier course, Mathematical Modelling of Computer Networks offered in Spring 2013, it develops the mathematical tools in conjunction with their applications in networking. However, the previous course (Mathematical Modelling of Computer Networks Part I) is not a prerequisite for taking this course. We focus on a couple of key results in each topic and build up the mathematical background to the extent needed to understand these results.

Course Audience

Prerequisites

Course Structure

The course has two modules.

  • Module 1: Network coding and TCP
  • Module 2: Large Deviations and Wireless Scheduling

    • 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.

    Course Contents

  • Module 1: Network Coding and TCP

    • Network coding, a nascent branch of networking, has made rapid strides from theory to practice in the recent years. Among other applications of network coding, we discuss how TCP can be enhanced with Network Coding (without any changes to the network routers) to improve its performance in wireless networking.
    References
  • P11. T. Ho, R. Koetter, M. Medard, M. Effros, J. Shi, and D. Karger. A Random Linear Network Coding Approach to Multicast. IEEE Transactions on Information Theory, Volume 52 Issue 10, October 2006, Page 4413-4430
  • P12. J. K. Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher and J. Barros. Network Coding Meets TCP: Theory and Implementation, Proceedings of the IEEE , vol.99, no.3, pp.490-512, March 2011.
  • P13. C. Fragouli, J.-Y. Le Boudec and J. Widmer. Network coding: an instant primer
  • P14. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft. XORs in the Air: Practical Wireless Network Coding. IEEE/ACM Transactions on Networking, Vol. 16, No. 3, June 2008. 497-510
  • P15. R.W. Yeung, S.-Y.R. Li, N. Cai, and. Z. Zhang. Network Coding Theory, Foundation and Trends.
  • P16. R. Bassoli, H. Marques, J. Rodriguez, K. W. Shum and R. Tafazolli. Network Coding Theory: A Survey. IEEE Communications Surveys & Tutorials, 2013.

  • Module 2: Large Deviations and Wireless Scheduling

    • Large deviations, an active modern research topic in probability, has found many uses in networking such as assessing the qualitative behaviour of scaling effects and determining (and controlling) the asymptotic decay rates probabilities of overflow events in wireless networks to provide QoS guarantees for delay sensitive traffic. We present informally the basic concepts of this theory and show how this theory can be applied to get interesting results in wireless scheduling
    References
  • P21. Ying , R. Srikant , A. Eryilmaz , G. E. Dullerud. A Large Deviations Analysis of Scheduling in Wireless Networks. IEEE Transactions on Information Theory, Vol. 52, no. 11 (2006): 5088-5098.
  • B21. L. Jiang and J. Walrand. Scheduling and Congestion Control for Wireless and Processing Networks. Morgan \& Claypool publishers, 2010

  • Useful Mathematical References

  • V. Shoup. A Computational Introduction to Number Theory and Algebra
  • Sage: Open Source Mathematics Software
  • R.A. Beezer. Sage for Linear Algebra. A Supplement to A First Course in Linear Algebra
  • S. Gao and D. Panario. Irreducibility test for polynomials over finite fields.
  • J.T. Lewis and R. Raymond. An elementary introduction to the Large Deviations Theory.

    • Passing the Course

  • Taking the course exam (25 points) at the end of the course and preparing a term paper (4-5 pages) on a suitably chosen topic and presenting it (25 points).
  • Active participation in the weekly exercises (max. 10 points).
  • A passing grade requires at least 30 points in total.

    • Course Slides

  • Introduction to the course

    • Network Coding

  • Lecture 1: Introduction to Network Coding
  • Lecture 2: Linear Network Coding and Multicast Capacity
  • Lecture 3: Network Coding and TCP

    • Wireless Scheduling

  • Lecture 1: Wireless Scheduling
  • Lecture 2: Maximum Weighted Matching scheduling algorithm
  • Lecture 3: Large Deviations and Wireless Scheduling

    • Exercises

    Network Coding

  • Exercise 1
  • Exercise 2
  • Exercise 3

    • Wireless Scheduling

  • Exercise 4
  • Exercise 5

    • Announcements