Modern Foundations of Computer Networks

Fall 2008

Motivation:

Computer networks are everywhere these days. A recent field in the intersection of Electrical Engineering and Computer Science, Computer Networking is now a scholarly subject substantiated on a body of fundamental results which shed light on the operation of current networks and guide the design of next-generation ones. This course provides a gentle introduction to some of the modern foundations of Computer Networking, including: basic network algorithms; an algebraic theory of optimal paths; an algebraic theory of routing; network calculus; and network coding. These topics have an algorithmic and abstract algebra backdrop which confers unity to the course. Their beauty and relevance is illustrated with a number of applications concerning the Internet, notwithstanding their applicability reaching far beyond Computer Networking.

Prerequisites:

This is an entry-level graduate course on the fundamentals of Computer Networking. It has as prerequisites undergraduate-level courses on linear algebra, calculus, algorithms and data structures, and computer networks. Previous knowledge of abstract algebra is not assumed.

Instructor: João Luís Sobrinho

Classes: Thursday from 17:00 to 18:30, and Friday from 9:30 to 11:00, room LT5, 4th floor of the North Tower.

Grading: Each student is expected to write a 8-pages essay and give a 40-minutes presentation on a topic related to the course. Grading will be based on homeworks (50%), and the written essay and the oral presentation (50%).

Syllabus:

· Basic algorithms on directed graphs

o Digraphs, paths, cycles, and arborescences

o Breadth-first search and depth first-search algorithms

· Weighted shortest paths

o Fixed-point equations: existence and uniqueness

o Bellman-Ford-Moore, Dijkstra’s, and Floyd-Warshall algorithms

o Going from a sequential to a distributed algorithm: distance-vector routing protocols and variants, and link-state routing protocols

o Applications to intra-domain routing in the Internet

· Networks and dioids

o Four less-than-classical network problems: a flow problem; 2th-shortest-paths; widest paths; enumeration of paths

o Orders and algebras: monoids, semi-rings, and dioids

o Fixed-point equations on dioids: existence and least solution

o Generalized Jacobi, Gauss-Seidel, Dijkstra’s, and Gauss-Jordan algorithms

o Tons of applications

· Networks and routing algebras

o Fixed-point equations: existence and uniqueness

o A sequential algorithm to solve the fixed-point equations

o Generalized distance-vector and link-state routing protocols

o Applications to quality-of-service intra-domain routing and to policy-based inter-domain routing in the Internet

· Network flows

o Flows and residual networks

o Max-flow Min-cut theorem

o Ford-Fulkerson method and Edmonds-Karp algorithm

· Connectivity

o Directed multigraphs

o Disjoint paths and trees: Menger’s and Edmonds’ theorems

o Algorithms for disjoint paths and trees

o Applications to video broadcast in the Internet

· Network calculus

o Min-plus calculus: integrals and convolutions

o Arrival curves and token buckets; service curves and schedulers

o Applications to integrated and differentiated services in the Internet

· Network coding

o More on algebras: rings, fields, finite fields, and vector spaces

o Linear network codes: existence and construction

o Applications to video multicast in the Internet

Lectures Schedule:

Bibliography:

Notes will be prepared by the instructor during the course. The following additional references are helpful.

· Basic algorithms

o Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms, 2th edition. The MIT Press 2001 [Part VI, Chapter 22]

· Weighted shortest-paths

o Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms, 2th edition. The MIT Press 2001 [Part VI, Chapter 24 and 25]

o Leslie Lamport, “An assertional correctness proof of a distributed algorithm,” Science of Computer Programming, 2(3) December 1992

o Jeffrey Jaffe and Franklin Moss, “A responsive distributed routing algorithm for computer networks,” IEEE Transactions on Communications, 30(7) July 1982

· Networks and dioids

o Michel Gondran and Michel Minoux. Graphes, dioides et semi-anneaux, Editions Tec & Doc, Paris, France, 2001 [Chapters 1 and 4] (There is a 2008 English translation)

· Networks and routing algebras

o João L. Sobrinho, “An algebraic theory of dynamic network routing,” IEEE/ACM Transactions on Networking, 13(5), October 2005

· Network flows

o Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms, 2th edition. The MIT Press 2001 [Part VI, Chapter 26]

· Connectivity

o Jorgen Bang-Jensen and Gregory Gutin. Digraphs: theory, algorithms and applications. Springer, 2002 [Section 7.3 and 9.5]

· Network calculus

o Cheng-Shang Chang. Performance guarantees in communication networks. Springer 2000 [Chapters 1 and 2]

o Jean-Yves Le Boudec and Patrick Thiran, “A short tutorial on Network Calculus I: fundamental bounds,” in Proc. ISCAS 2000

· Network coding

o Christina Fragouli, Jean-Yves Le Boudec, and Jorg Widmar, “Network coding: an instant primer,” ACM SIGCOMM Computer Communication Review, 36(1), January 2006

o Sidharth Jaggi, Peter Sanders, Philip A. Chou, Kamal Jain, Ludo Tolhuizen, “Polynomial-time algorithms for multicast network code construction,” IEEE Transactions on Information Theory, 51(6), June 2005

## Leave a Reply