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 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 2 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 3 Layering The Problem Application Telnet Transmission Media Re implement FTP Coaxial cable NFS Fiber optic HTTP Packet radio every application for every technology No But how does the Internet architecture avoid this 4 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 Application SMTP SSH NFS HTTP Intermediate layer Transmission Media Coaxial cable Fiber optic Packet radio 5 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 6 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 Application Transport Internet Net access Physical Telnet FTP TCP DNS UDP IP LAN Packet radio 7 Hourglass 8 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 9 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 10 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 11 Overview Layering and e2e Argument Little Theorem Packet delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding CSMA CD Ethernet 12 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 system 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 13 Example Arrival rate 1 delay 4 Time 0 14 Example Arrival rate 1 delay 4 delay 1 Time 1 15 Example Arrival rate 1 delay 4 delay 2 delay 1 Time 2 16 Example Arrival rate 1 delay 4 delay 3 delay 2 delay 1 Time 3 17 Example Arrival rate 1 delay 4 delay 4 delay 3 delay 2 delay 1 Time 4 18 Example Arrival rate 1 delay 4 delay 3 delay 2 delay 1 Time 4 Q What is the average number of packets in system A number of packets in system avg arrival rate x avg delay 19 Overview Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding CSMA CD Ethernet 20 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 21 Sending One Packet R bits per second bps Bandwidth R bps Propagation delay T sec T seconds P bits Transmission time P R T time Propagation delay T Length speed 1m speed 3 3 usec in free space 4 usec in copper 5 usec in fiber 22 Queueing 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 Q bits Propagation delay T sec Queueing delay Q R P R T time 23 Store Forward Host 2 Node 2 propagation delay between Host 1 and Node 1 Packet 1 Packet 1 transmission time of Packet 1 at Host 1 Node 1 Queuing processing delay of Packet 1 at Node 2 Packet 1 Host 1 24 Store Forward Various Capacities Example A packet is stored enqueued before being forwarded sent 10 Mbps Sender time 5 Mbps 100 Mbps 10 Mbps Receiver 25 Store Forward Multiple Packet Example 10 Mbps Sender time 5 Mbps 100 Mbps 10 Mbps Receiver 26 Overview Layering and e2e Argument Little Theorem Packet Delays IP Forwarding and Addressing Stop and Wait and Sliding Window Bit encoding 27 Packet Forwarding 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 1 2 3 4 1 1 2 3 5 2 28 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 host 1 2 3 5 5 6 7 9 host host 2 4 6 9 host LAN 2 LAN 1 router WAN router WAN router 1 2 3 4 1 2 3 5 forwarding table 29 Solution Hierarchical Addressing IP Prefixes Divided into network left host portions right 12 34 158 0 24 is a 24 bit prefix with 29 addresses Terminology Slash 24 12 34 158 5 00001100 00100010 10011110 00000101 Network 24 bits Host 8 bits 30 Scalability Improved Number related hosts from a common subnet 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 5 6 7 8 5 6 7 9 5 6 7 212 host host host host LAN 2 LAN 1 router WAN router WAN router 1 2 3 0 24 5 6 7 0 24 forwarding table 31 Easy to Add New Hosts …
View Full Document
Unlocking...