1 1 EE 122: Midterm Review Ion Stoica TAs: Junda Liu, DK Moon, David Zats http://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford, and colleagues at UC Berkeley) 2 Announcements Midterm Information Date: 19 October 2008 Time: 4:00 PM to 5:30 PM Closed book, open 8.5” x 11” crib sheet (both sides) No Blue Books; all answers on exam sheets we hand out No calculators, PDAs, cell phones with cameras, etc. Please use PENCIL and bring ERASER Ion, one additional office hour on Monday: 1-3pm 3 Overview Layering and e2e Argument Little Theorem Packet delays IP Forwarding and Addressing Stop-and-Wait and Sliding Window Bit encoding CSMA/CD & Ethernet & Ethernet 4 Layering: The Problem Re-implement every application for every technology? No! But how does the Internet architecture avoid this? Telnet FTP NFS Packet radio Coaxial cable Fiber optic Application Transmission Media HTTP2 5 Layering: Solution Introduce an intermediate layer that provides a single abstraction for various network technologies New application just need to be written for intermediate layer New transmission media just need to provide abstraction of intermediate layer SMTP SSH NFS Packet radio Coaxial cable Fiber optic Application Transmission Media HTTP Intermediate layer 6 Layering Layering is a particular form of modularization System is broken into a vertical hierarchy of logically distinct entities (layers) Service provided by one layer is based solely on the service provided by layer below Rigid structure: easy reuse, performance suffers 7 Layering: Internet Universal Internet layer: Internet has only IP at the Internet layer Many options for modules above IP Many options for modules below IP Internet Net access/ Physical Transport Application IP LAN Packet radio TCP UDP Telnet FTP DNS 8 Hourglass3 9 Implications of Hourglass Single Internet layer module: Allows networks to interoperate Any network technology that supports IP can exchange packets Allows applications to function on all networks Applications that can run on IP can use any network Simultaneous developments above and below IP 10 E2E Arguments: Where to Place Functionality? Most influential paper about placing functionality is “End-to-End Arguments in System Design” by Saltzer, Reed, and Clark “Sacred Text” of the Internet Endless disputes about what it means Everyone cites it as supporting their position 11 E2E Arguments: Moderate Interpretation Think twice before implementing functionality in the network If hosts can implement functionality correctly, implement it a lower layer only as a performance enhancement But do so only if it does not impose burden on applications that do not require that functionality 12 Overview Layering and e2e Argument Little Theorem Packet delays IP Forwarding and Addressing Stop-and-Wait and Sliding Window Bit encoding CSMA/CD & Ethernet4 13 Little’s Theorem Assume a system (e.g., router, network, checkout line in a supermarket) at which packets arrive at rate a(t) Let d(i) be the delay or service time of packet i , i.e., time packet i spends in the system What is the average number of packets in the system? system a(t) – arrival rate d(i) = delay of packet i Intuition: Assume arrival rate is a = 1 packet per second and the delay of each packet is s = 4 seconds What is the average number of packets in the system? 14 Example Arrival rate = 1; delay = 4 Time = 0 15 Example Arrival rate = 1; delay = 4 Time = 1 delay = 1 16 Example Arrival rate = 1; delay = 4 Time = 2 delay = 1 delay = 25 17 Example Arrival rate = 1; delay = 4 Time = 3 delay = 2 delay = 3 delay = 1 18 Example Arrival rate = 1; delay = 4 Time = 4 delay = 3 delay = 4 delay = 2 delay = 1 19 Example Arrival rate = 1; delay = 4 Time = 4 delay = 3 delay = 2 delay = 1 Q: What is the average number of packets in system? A: number_of_packets_in_system = avg_arrival_rate x avg_delay 20 Overview Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop-and-Wait and Sliding Window Bit encoding CSMA/CD & Ethernet6 21 Definitions Link bandwidth (capacity): maximum rate (in bps) at which the sender can send data along the link Propagation delay: time it takes the signal to travel from source to destination Packet transmission time: time it takes the sender to transmit all bits of the packet Queuing delay: time the packet need to wait before being transmitted because the queue was not empty when it arrived Processing Time: time it takes a router/switch to process the packet header, manage memory, etc 22 Sending One Packet R bits per second (bps) T seconds P bits Bandwidth: R bps Propagation delay: T sec time Transmission time = P/R T Propagation delay =T = Length/speed 1m/speed = 3.3 usec in free space 4 usec in copper 5 usec in fiber 23 Queueing The queue has Q bits when packet arrives packet has to wait for the queue to drain before being transmitted P bits time P/R T Q bits Queueing delay = Q/R Capacity = R bps Propagation delay = T sec 24 Packet 1 Packet 1 Store & Forward Packet 1 Queuing & processing delay of Packet 1 at Node 2 Host 1 Host 2 Node 1 Node 2 propagation delay between Host 1 and Node 1 transmission time of Packet 1 at Host 17 25 Store & Forward: Various Capacities Example A packet is stored (enqueued) before being forwarded (sent) Sender Receiver 10 Mbps 5 Mbps 100 Mbps 10 Mbps time 26 Store & Forward: Multiple Packet Example Sender Receiver 10 Mbps 5 Mbps 100 Mbps 10 Mbps time 27 Overview Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop-and-Wait and Sliding Window Bit encoding 28 Packet Forwarding Store a mapping between IP addresses and output interfaces Forward an incoming packet based on its destination address … … 3 1.2.3.6 1 1.2.3.5 1 2 1.2.3.5 1.2.3.4 1.2.3.4 28 29 Scalability Challenge
View Full Document
Unlocking...