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 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 1 Overview 2 Layering The Problem Layering and e2e Argument Little Theorem Packet delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding CSMA CD Ethernet Ethernet Application Transmission Media Telnet FTP Coaxial cable NFS Fiber optic HTTP Packet radio Re implement every application for every technology No But how does the Internet architecture avoid this 3 4 1 Layering Solution Layering 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 Application SMTP SSH NFS HTTP 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 Intermediate layer Transmission Media Coaxial cable Fiber optic Packet radio 5 Layering Internet 6 Hourglass Universal Internet layer Internet has only IP at the Internet layer Many options for modules above IP Many options for modules below IP Application Transport Internet Net access Physical Telnet FTP TCP DNS UDP IP LAN Packet radio 7 8 2 E2E Arguments Where to Place Functionality Implications of Hourglass Single Internet layer module Allows networks to interoperate Most influential paper about placing functionality is End to End Arguments in System Design by Saltzer Reed and Clark Sacred Text of the Internet 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 Endless disputes about what it means Everyone cites it as supporting their position Simultaneous developments above and below IP 9 E2E Arguments Moderate Interpretation 10 Overview 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 11 Layering and e2e Argument Little Theorem Packet delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding CSMA CD Ethernet 12 3 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 d i delay of packet i a t arrival rate Example Arrival rate 1 delay 4 system Intuition Time 0 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 13 Example 14 Example Arrival rate 1 delay 4 delay 1 Time 1 Arrival rate 1 delay 4 delay 2 delay 1 Time 2 15 16 4 Example Example Arrival rate 1 delay 4 Arrival rate 1 delay 4 delay 3 delay 4 delay 2 delay 3 delay 1 delay 2 delay 1 Time 3 Time 4 17 Example 18 Overview Arrival rate 1 delay 4 delay 3 delay 2 delay 1 Time 4 Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding CSMA CD Ethernet Q What is the average number of packets in system A number of packets in system avg arrival rate x avg delay 19 20 5 Definitions Sending One Packet 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 21 The queue has Q bits when packet arrives packet has to wait for the queue to drain before being transmitted Capacity R bps P bits T seconds P bits T Transmission time P R time Propagation delay T Length speed 1m speed 3 3 usec in free space 4 usec in copper 5 usec in fiber 22 Store Forward Queueing R bits per second bps Bandwidth R bps Propagation delay T sec Q bits Host 1 Node 1 Propagation delay T sec transmission time of Packet 1 at Host 1 Queueing delay Q R Packet 1 propagation delay between Host 1 and Node 1 Packet 1 P R Host 2 Node 2 T Queuing processing delay of Packet 1 at Node 2 Packet 1 time 23 24 6 Store Forward Various Capacities Example Store Forward Multiple Packet Example 10 Mbps A packet is stored enqueued before being forwarded sent 10 Mbps 5 Mbps 100 Mbps time 10 Mbps Receiver Sender Receiver time 25 Overview 100 Mbps 10 Mbps Sender 5 Mbps 26 Packet Forwarding Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding Store a mapping between IP addresses and output interfaces Forward an incoming packet based on its destination address 1 2 3 5 1 2 3 6 1 2 3 4 1 3 2 27 1 2 3 4 1 1 2 3 5 2 28 7 Solution Hierarchical Addressing IP Prefixes Scalability Challenge Suppose hosts had arbitrary addresses Then every router would need a lot of information to know how to direct packets toward the host 1 2 3 4 5 6 7 8 host host 2 4 6 8 1 2 3 5 5 6 7 9 host host host Divided into network left host portions right 12 34 158 0 24 is a 24 bit prefix with 29 addresses Terminology Slash 24 2 4 6 9 12 host 34 158 5 LAN 2 LAN 1 router WAN router WAN router 00001100 00100010 10011110 00000101 1 2 3 4 1 2 3 5 Network 24 bits 29 forwarding table Scalability Improved 1 2 3 0 24 on the left LAN 5 6 7 0 24 on the right LAN 1 2 3 4 1 2 3 7 1 2 3 156 host host host host host WAN router WAN E g adding a new host 5 6 7 213 on the right Doesn t require adding a new forwarding entry 1 2 3 4 1 2 3 7 1 2 3 156 host host LAN 2 LAN 1 router No …
View Full Document
Unlocking...