Modern Foundations of Computer Networks
Fall 2009
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; 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.
Instructor:
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,
Dijkstras, 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, Dijkstras, 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: Mengers 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
Bibliography:
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.
Calendar:
The course is planned for a 14 weeks semester
according to the schedule below.
|
Topic |
Duration (weeks) |
|
Basic algorithms on directed graphs |
2 |
|
Weighted shortest
paths |
2 |
|
Networks and dioids |
3 |
|
Networks and
routing algebras |
2 |
|
Network flows |
1 |
|
Connectivity |
2 |
|
Network calculus |
2 |
Grading:
A research project to be presented to the class
on one of the topics addressed in the course (50%) and an exam (50%).
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.