1 Winter 2008 CS244a Handout 14 1 CS244a: An Introduction to Computer Networks Final Review Nick McKeown Professor of Electrical Engineering and Computer Science, Stanford University [email protected] http://www.stanford.edu/~nickm Winter 2008 CS244a Handout 14 2 Outline  The Basics  Where next?  Classes to take2 Winter 2008 CS244a Handout 14 3 Packet Switching Breaking message into packets allows parallel transmission across all links, reducing end to end latency. It also prevents a link from being “hogged” for a long time by one message. Host A Host B R1 R2 R3 M/R Host A Host B R1 R2 R3 M/R Winter 2008 CS244a Handout 14 4 Packet Switching Queueing Delay Host A Host B R1 R2 R3 TRANSP1 TRANSP2 TRANSP3 TRANSP4 PROP1 PROP2 PROP3 PROP4 Q2 Because the egress link is not necessarily free when a packet arrives, it may be queued in a buffer. If the network is busy, packets might have to wait a long time.3 Winter 2008 CS244a Handout 14 5 D(t) A(t) time Q(t) d(t) Queue occupancy: Q(t) = A(t) - D(t). Queueing delay, d(t), is the time spent in the queue by a bit that arrived at time t, and if the queue is served first-come-first-served (FCFS or FIFO) Simple Deterministic Model Cumulative number of bits Winter 2008 CS244a Handout 14 6 D(t) A(t) time Q(t) d(t) Example Cumulative number of bits Example: Every second, a train of 100 bits arrive at rate 1000b/s. The maximum departure rate is 500b/s. What is the average queue occupancy? 0.1s 0.2s 1.0s 1004 Winter 2008 CS244a Handout 14 7 Review of Basic Principles  Basic ideas:  Packet switching, statistical multiplexing, deterministic models of queues.  Physical Layer:  Channel capacity, encoding and clock recovery, elasticity buffers.  Link Layer:  CSMA/CD  Ethernet switching  Network Layer:  Routing: Bellman-Ford, Dijkstra and multicast  Addresses and lookups Winter 2008 CS244a Handout 14 8 Review of Basic Principles (2)  Transport Layer:  Flow control, congestion control, retransmissions and sliding windows, congestion avoidance (RED).  Quality of Service:  Fairness  Guarantees, WFQ and leaky-buckets.5 Winter 2008 CS244a Handout 14 9 Outline  The Basics  Where next?  Classes to take Winter 2008 CS244a Handout 14 10 Classes to take  Networking classes (not all offered every year)  CS244b: Distributed Systems  CS155: Computer and Network Security (Spring)  EE384a: Network Protocols and Standards (Winter)  EE384b: Multimedia Networking (Spring)  EE384c: Wireless LANs (Spring)  EE384m: Network Algorithms (Spring)  EE384s: Network Arch. and Performance Engineering (Spring)  EE384x,y: Packet Switch Architectures (Winter,Spring)  CS344: Build an Internet Router - Design Project (Spring)  Related  CS255: Cryptography and Computer Security (Winter)  Stats 116, EE178, EE278: Probability and random processes  CS249: Object Oriented Modeling (Winter)  EE376A: Information theory  Seminars  Stanford Networking Seminar