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