Modern Foundations of Computer Networks

Fall 2009






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; and network calculus. 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.





Joćo Luķs Sobrinho





·        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




A text for the course has been prepared by the instructor and is available at the institutional web page, under the tab “text” on the bottom left-hand side. The following additional references are helpful.






The course is planned for a 14 weeks semester according to the schedule below.





Basic algorithms on directed graphs


Weighted shortest paths


Networks and dioids


Networks and routing algebras


Network flows




Network calculus

















A research project to be presented to the class on one of the topics addressed in the course (50%) and an exam (50%).





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.