TCOM 501: Networking Theory & Fundamentals

Spring 2003
University of Pennsylvania

Professor Yannis A. Korilis

Course Information

Description

The course introduces analytical models and methodologies for modern networking, with focus on congestion control and routing. Topics from queueing theory, optimization, graph theory, distributed and asynchronous algorithms and their application to networking will be studied.

Textbook

Data Networks, Dimitri Bertsekas and Robert Gallager, Prentice Hall, 2nd Edition

Administrative

Instructor: Prof. Yannis A. Korilis

*     Office: 276 Towne Building

*     Office hours: Wednesday 2:30-4:00pm

*     Email: korilis@seas.upenn.edu

*     Tel: 215-898-3966; Fax: 215-898-5020

TA: Mr. Shu Tao

*     Office: 306 Moore Building

*     Office hours: Tuesday 2:00-4:00pm

*     Email: shutao@seas.upenn.edu

*     Tel: 215-573-8815/8816

Grading

Assignments: 10%
Midterm: 40%
Final: 50%

Homework & Exam Policies

*     Homework: Solutions for each assignment will be posted the day after each assignment is due; any assignments handed in after that point will not be graded

*     Exams: Closed book midterm and final exams; there will be no make up exams

Syllabus

[Tentative subject to revision]

Introduction

1.    Course Introduction

2.    OSI-7 Layered Architecture

3.    Data Link Layer (brief)

Queueing Models

1.    Probability and Stochastic Processes, Markov Chains

2.    Delay Models & Introduction to Queueing Theory

3.    Little's Theorem

4.    M/M/. Systems

5.    M/G/. Systems

6.    Reversibility

7.    Networks of Queues

8.    Multiclass Networks

9.    Product-Forms and Norton's Equivalent

Flow Control

1.    Window-Based Algorithms

2.    Rate-Based Algorithms

Routing

1.    Shortest-Path Routing

2.    Optimal Routing

 

Course Schedule

[Tentative subject to revision]

 

 

Date

Topics

Reading

Homework

1

January 15

*      Course Outline

*      Introduction

*      OSI 7-Layer Architecture

Browse through ch. 2 (optional)

 

2

January 22

*      Introduction to Queueing Theory

*      The Poisson Process

*      Little's Theorem & Applications

Sec. 3.1, 3.2, 3.3 (up to p. 166)

HW #1

3

January 29

*      Markov Chains

*      Discrete & Continuous Time Chains

*      Stationary Distributions

Sec. 3.A (Appendix), class notes

 

4

February 5

*      The M/M/1 Queue

*      PASTA Theorem

Sec. 3.3

 

5

February 12

*      Other M/M/* Queues

*      Sojourn times

*      Multidimensional Markov Chains

Sec. 3.4

HW #2

6

February 19

*      Time-Reversed Markov Chains

*      Reversibility

*      Truncation of Markov Chains

Sec. 3.7, class notes

HW #3

7

February 25

*      Burke's Theorem

*      Open Jackson Networks

*      Network Flows

*      Kleinrock Independence Assumption

Sec 3.6

Sec. 3.8, class notes

HW #4

 

March 5

Midterm [in class]

 

 

 

March 12

Spring break

 

 

8

March 19

*      Closed Jackson Networks

*      Arrival Theorem for Closed Networks

*      Mean-Value Analysis

*      State-Dependent Service Rates

Sec. 3.8, class notes

 

 

9

April 2

*      Discussion if midterm

*      M/G/1 Systems

*      Pollaczeck-Kinhitchin Formula

Sec. 3.5

Except 3.5.2 and 3.5.4

HW #5

10

April 9

*      M/G/1: Embedded Markov chain

*      P-K Transform Equation

*      Calculating the stationary distribution

*      Priority Queueing

Sec. 3.5

Class notes

HW #6

11

April 16

*      Topics on M/G/1

*      Introduction to Routing

*      Shortest-Path Algorithms: Bellman-Ford, Dijkstra

Sec. 5.1, 5.2

 

12

April 23

*      Asynchronous Bellman-Ford Algorithm

*      Flow Models for Optimal Routing

Sec. 5.2, 5.4

 

 

 

Semester Ends

 

 

 

 

 

 

 

 

Lecture Notes

*     Lecture 2 [ppt][pdf]

*     Lecture 3 [ppt][pdf]

*     Lectures 4&5 [ppt][pdf]

*     Lecture 6 [ppt][pdf]

*     Lecture 7 [ppt][pdf]

*     Lecture 8 [ppt][pdf]

*     Lecture 9 [ppt][pdf]

*     Lecture 10 [ppt][pdf]

*     Lecture 11 [ppt][pdf]

 

 

Homework Assignments

  1. Problems: 3.1, 3, 4, 6, 7, 10, 11(a), 12
    [solutions]
  2. Problems: 3.11(b), 14, 15, 16, 21
    [solutions]
  3. Problems: click here
    [solutions]
  4. Problems: 3.53, 54, 55, 57, 58
    [solutions]
  5. Problems: 3.30, 31, 32, 36, 37, 40
    [solutions]
  6. Problems: click here
    [solutions]

 

 

Exams

  1. Midterm [exam][solutions]
  2. Final [exam][solutions]

Homework & Exam Statistics

 

Points

Max

Min

Mean

SD

HW 1

 

 

 

 

 

HW 2

 

 

 

 

 

HW 3

 

 

 

 

 

HW 4

 

 

 

 

 

HW5

 

 

 

 

 

HW6

 

 

 

 

 

Midterm

 

 

 

 

 

Final

 

 

 

 

 

 

Miscellaneous

Past Exams

*     Midterm [exam][solutions]

*     Final [exam][solutions]

Recommended Books

1.    Introduction to Probability Models, Sheldon Ross, Harcourt / Academic Press

2.    Stochastic Modeling and the Theory of Queues, Ronald W. Wolff, Prentice Hall

3.    Introduction to Queueing Networks, Jean Warland, Prentice-Hall, 1988

4.    Reversibility and Stochastic Networks, Frank P. Kelly, John Willey and Sons, 1979

 

 

Last revised: 4/25/2003