Slide 1AnnouncementsOverviewLayering: The ProblemLayering: SolutionLayeringLayering: InternetHourglassImplications of HourglassE2E Arguments: Where to Place Functionality?E2E Arguments: Moderate InterpretationOverviewLittle’s TheoremExampleExampleExampleExampleExampleExampleOverviewDefinitionsSending One PacketQueueingStore & ForwardStore & Forward: Various Capacities ExampleStore & Forward: Multiple Packet ExampleOverviewPacket ForwardingScalability ChallengeSolution: Hierarchical Addressing (IP Prefixes)Scalability ImprovedEasy to Add New HostsClassful AddressingClassful Addressing (cont’d)Classless Inter-Domain Routing (CIDR)Scalability: Address AggregationSlide 37OverviewAutomatic Repeat reQuest (ARQ)How Fast Can Stop-and-Wait Go?Allowing Multiple Packets in FlightSliding Window Example (This is NOT TCP !)Sliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleSliding Window ExampleWhat If Sending & Delivey Rates are 2 pkt/s?Performance with Sliding WindowOverviewEncodingNon-Return to Zero (NRZ)Clock CoordinationClock RecoveryNon-Return to Zero Inverted (NRZI)Manchester Encoding4-bit/5-bit (100Mb/s Ethernet)OverviewEthernet: CSMA/CD ProtocolMinimum Packet SizeMinimum Packet SizeMidterm Information1EE 122: Midterm ReviewIon StoicaTAs: Junda Liu, DK Moon, David Zatshttp://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford,and colleagues at UC Berkeley)2AnnouncementsMidterm InformationDate: 19 October 2008Time: 4:00 PM to 5:30 PMClosed book, open 8.5” x 11” crib sheet (both sides)No Blue Books; all answers on exam sheets we hand outNo calculators, PDAs, cell phones with cameras, etc.Please use PENCIL and bring ERASERIon, one additional office hour on Monday: 1-3pm3OverviewLayering and e2e ArgumentLittle TheoremPacket delaysIP Forwarding and AddressingStop-and-Wait and Sliding WindowBit encodingCSMA/CD & Ethernet & Ethernet4Layering: The ProblemRe-implement every application for every technology?No! But how does the Internet architecture avoid this?Telnet FTP NFSPacketradioCoaxial cableFiberopticApplicationTransmissionMediaHTTP5Layering: SolutionIntroduce an intermediate layer that provides a single abstraction for various network technologiesNew application just need to be written for intermediate layerNew transmission media just need to provide abstraction of intermediate layerSMTP SSH NFSPacketradioCoaxial cableFiberopticApplicationTransmissionMediaHTTPIntermediate layer6LayeringLayering is a particular form of modularizationSystem 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 belowRigid structure: easy reuse, performance suffers7Layering: InternetUniversal Internet layer:Internet has only IP at the Internet layerMany options for modules above IPMany options for modules below IPInternetNet access/PhysicalTransportApplicationIPLANPacketradioTCP UDPTelnet FTP DNS8Hourglass9Implications of HourglassSingle Internet layer module:Allows networks to interoperateAny network technology that supports IP can exchange packetsAllows applications to function on all networksApplications that can run on IP can use any networkSimultaneous developments above and below IP10E2E 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 InternetEndless disputes about what it meansEveryone cites it as supporting their position11E2E Arguments: Moderate InterpretationThink twice before implementing functionality in the networkIf hosts can implement functionality correctly, implement it a lower layer only as a performance enhancementBut do so only if it does not impose burden on applications that do not require that functionality12OverviewLayering and e2e ArgumentLittle TheoremPacket delaysIP Forwarding and AddressingStop-and-Wait and Sliding WindowBit encodingCSMA/CD & Ethernet13Little’s TheoremAssume 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 systemWhat is the average number of packets in the system? systema(t) – arrival rated(i) = delay of packet iIntuition:Assume arrival rate is a = 1 packet per second and the delay of each packet is s = 4 secondsWhat is the average number of packets in the system?14ExampleArrival rate = 1; delay = 4Time = 015ExampleArrival rate = 1; delay = 4Time = 1delay = 116ExampleArrival rate = 1; delay = 4Time = 2delay = 1delay = 217ExampleArrival rate = 1; delay = 4Time = 3delay = 2delay = 3delay = 118ExampleArrival rate = 1; delay = 4Time = 4delay = 3delay = 4delay = 2delay = 119ExampleArrival rate = 1; delay = 4Time = 4delay = 3delay = 2delay = 1Q: What is the average number of packets in system?A: number_of_packets_in_system = avg_arrival_rate x avg_delay20OverviewLayering and e2e ArgumentLittle TheoremPacket DelaysIP Forwarding and AddressingStop-and-Wait and Sliding WindowBit encodingCSMA/CD & Ethernet21DefinitionsLink 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 destinationPacket transmission time: time it takes the sender to transmit all bits of the packetQueuing delay: time the packet need to wait before being transmitted because the queue was not empty when it arrivedProcessing Time: time it takes a router/switch to process the packet header, manage memory, etc22Sending One PacketR bits per second (bps)T secondsP bitsBandwidth: R bpsPropagation delay: T sectimeTransmission time = P/RTPropagation delay =T = Length/speed1m/speed = 3.3 usec in free space 4 usec in copper 5 usec in fiber23QueueingThe queue has Q bits when packet arrives packet has to wait for the queue to drain before being transmittedP bitstimeP/RTQ bitsQueueing delay = Q/RCapacity = R bpsPropagation delay = T sec24Packet 1Packet 1Store & ForwardPacket 1Queuing & processing delay of Packet 1 at Node 2Host 1 Host 2Node 1
View Full Document
Unlocking...