Grading Scheme

• 3  Assignments: 15% each
• 1  Final Project: 55%

Lecture Topics

• Basic concepts of layering:
• the OSI reference model vs. Padlipsky's view of the ARPAnet reference model
• the IEEE 802-2001 "Overview and Architecture" Standard
  
• Saltzer et al's classic paper on the importance End-to-End protocols for correctness
• Metcalfe's lessons learned from network interface design
• What you should remember from these readings
• How to read standards documents and understand of the process by which they are created
• Specifies behavior, but NOT how to implement it. Tutorial not included.
  
• Layering and/or modularity are very important concepts but...
• The number layers and placement of functions is not based on some universal law
• Things change over time (e.g., disappearance of "true" OSI Network Layer and its replacement by IP)
  
• For some functions (e.g., link aggregation), it is provably impossible to assign it to the "correct" layer
• Not everyone is working from the same high-level picture of what a network is supposed to "do"
• Generations of people with a classical telecommunications / telephony background have tried to recreate the public telephone network to handle "data calls" between computers and/or terminals. (X.25, ISDN, ATM)
• Internet is about "always on" connectivity to everyone and everything using message passing abstraction
• Has anyone noticed what is happening to "smart phones" and their effect on cellular carriers?
  
• The "KISS" principle (Keep It Simple, Stupid!):
• A key design principle for both Ethernet and IP has been to aim for "best effort" service
  
• Many alternatives offering "better service" (reliable, flow controlled, bandwidth / delay guarantees, etc) have tried and failed to displace them. Why is this?
  
• The importance of the "End-to-End Argument":
• Why didn't anyone care about Token Ring's link-layer acknowledgements?
• Why should the standards for layer-2 bridge/switches care about the Ethernet CRC?
  
• The Binary Exponential Backoff (originally from Ethernet) and Additive-Increase/Multiplicative-Decrease (from TCP) Algorithms:
• how (and why) a transmitter can use them to avoid overloading some scarce network resource, and hence hurting themselves and others
• single-use-at-a-time resource for BEB (e.g., shared broadcast channel with collisions)
• sharable resource that may degrade/collapse under excessive load for AIMD (e.g., buffer space at an IP router)
• how both algorithms produce unstable, chaotic behavior rather than "converging" to a "nice" pattern
• See this report for information about BEB:
• Section II.a and Figure 6 show it reacts much slower than expected (linear, not exponential)
• Section I.b explains the capture effect
• See this paper for the derivation of an analytical model of TCP congetion control
• See Figure 3 from this paper to see an example of chaotically varying traffic levels from the router's viewpoint.
  
• See figures 1 and 2 from this paper to see that the chaos looks even worse from the viewpoint of the users.
  
• Modelling traffic
• Abstract graph-theorectic model
• trivial fluid-flow model of communications
• calculation of link flows from end-to-end demands and routing tables
  
• calculation of average path length
• associated Excel spreadsheet with sample calculations
• For recent developments related to this subject, look for network tomography
• Poisson traffic
• Simple average-case delay analysis for an M/M/1 queue
  
• Kleinrock's Independence assumption
• Operational Analysis
• Operationally testable system behavior based on finite measurements
• Here is my example spreadsheet to show the operational laws hold without Kleinrock's Independence assumption. (Try changing packet sizes, arrival times, or link speeds and see that everything still works)
  
• Little's Law
• Flow balance, visit ratios, bottleneck analysis
• MVA algorithm
• An interesting perspective on the topic by one of its inventors
  
• An Excel spreadsheet showing how to MVA to model file transfer with sliding window
  
• Cruz's deterministic network calculus (see pages 1-26 of this document provides more than enough detail)
• Why look at cumulative arrivals? 6 minutes of Etherent traffic presented as incremental data vs. cumulative data
  
• Long-range dependence and heavy-tailed distributions (this is the classic reference)
• Convergence between the Poisson and LRD traffic models