11Network Performance: QueuingEE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Additional reading for today’s lecture: Peterson & Davie 3.423Goals of Today’s Lecture• Finish discussion of Window Scaling• TCP Throughput Equation– Computes approximate long-running TCP performancefor a given packet loss probability p• Relationship between performance and queuing– Router architecture– Modeling of queuing systems & Little’s Law– FIFO queuing– Active Queue Management - RED– Explicit Congestion Notification (ECN)4Window Scaling• Problem: 16 bits of advertised window only allows65,535 bytes in flight– Can significantly restrict throughput• Solution: TCP window scaling option negotiated ininitial SYN exchange•shift.cnt specifies scaling factor for units usedin window advertisement– E.g., shift.cnt = 5 ⇒advertised window is 25 = 32-byte units35Window Scaling, con’t• Q: Now how large can the window be?• A: Clearly, must not exceed 232 …– If it does, then can’t disambiguate data in flight– So, scaling ≤ 16• In fact, somewhat subtle requirements limit windowto 230 to allow receiver to determine whether datafits in the offered window– So, scaling ≤ 146Window Scaling, con’t• Now we can go fast. Suppose in a high-speedLAN with RTT = 1 msec we can transmit at 1 GB/s.• What problem arises if packets are occasionallydelayed in the network for 10 msec?• Sequence number wrap: can’t tell earlier, delayedsegments from later instances.• Fix: another TCP option to associate (high-res)timestamps with TCP segments– Essentially, adds more bits to sequence space– (Side effect: no more need for Karn/Partridge restrictionnot to compute RTT for ACKs of retransmitted packets)47TCP Throughput Equation• Consider a network path for which packets are lostwith probability p (independently).• Suppose a TCP connection achieves a maximumwindow size of W packets when using the path.– On AIMD cut due to packet loss, window goes to W/2– Thus, average window is w = 3/4 W• Total number of packets in the “sawtooth”:– W/2 + (W/2 + 1) + (W/2 + 2) + … + W– Sawtooth spans about W/2 RTT’s– Total # packets ≈ (3/4 W) · (W/2) = 3W2/8• Therefore: 3W2/8 ≈ 1/p8TCP Throughput Equation, con’t• Given 3W2/8 ≈ 1/p, then in terms of the averagewindow w:– 3·(4/3 w)2/8 = 1/p (since w = 3/4 W)– 16/9 w2 = 8/3p ⇒ w2 = 3/2p– w = sqrt(3/2) / sqrt(p)• For packets of B bytes, throughput is– T = w·B/RTT = sqrt(1.5)·B/(RTT·sqrt(p))• Implications:– Long-term throughput falls as 1/RTT– Long-term throughput falls as 1/sqrt(p)• Non-TCP transport can use equation to provideTCP-friendly congestion control! T =1.5BRTT p59Where Does Loss (= p) Come From,Anyway?Routers & Queuing10Generic Router Architecture• Input and output interfacesare connected through aninterconnect• Interconnect can beimplemented by– Shared memory Low capacity routers (e.g.,PC-based routers)– Shared bus Medium capacity routers– Point-to-point (switched) bus High capacity routers Packets fragmented intocells Essentially a network insidethe router!input interface output interfaceInter-connect611Shared Memory (1st Generation)RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically < 0.5Gbps aggregate capacityLimited by rate of shared memoryShared BackplaneLineInterfaceCPUMemory(* Slide by Nick McKeown)12Shared Bus (2nd Generation)RouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemoryTypically < 5Gb/s aggregatecapacity; Limited by shared bus(* Slide by Nick McKeown)713Point-to-Point Switch (3rd Generation)LineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemorySwitched BackplaneLineInterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically ~ 100Gbps aggregate capacity(*Slide by Nick McKeown)14What a Router Looks LikeCisco GSR 12416 Juniper M1606ft19”2ftCapacity: 160Gb/sPower: 4.2kWLines of Code: 8M (!) (circa year 2000)3ft2.5ft19”Capacity: 80Gb/sPower: 2.6kWSlide courtesy Nick McKeown815Input Interface• Packet forwarding: decide to which output interface toforward each packet based on the information in packetheader– Examine packet header– Lookup in forwarding table– Update packet header• Question: do we send thepacket to the outputinterface immediately?input interface output interfaceInter-connect16Output Functions• Buffer management: decide when and which packet to drop• Scheduler: decide when and which packet to transmit12SchedulerBuffer917Output Queued Routers• Only output interfaces storepackets• Advantages– Easy to design algorithms:only one congestion point• Disadvantages– Requires an output speedup(Ro/C) of N, where N is thenumber of interfaces notfeasibleinput interface output interfaceBackplaneCRO18Input Queued Routers• Input interfaces storepackets• Easier to build sinceonly need R ≈ C– Though need toimplement “backpressure” to know whento send• But harder to buildefficiently due tocontention andhead-of-line blockinginput interface output interfaceBackplaneCR1019Head-of-line Blocking• Cell at head of an input queue cannot betransferred, thus blocking the following cellsCannot betransferred because output buffer overflowCannot be transferred because is blocked by orange cell Output 1Output 2Output 3Input 1Input 2Input 3• Modern high-speed routers use combination of input &output queuing, with flow control & multiple “virtual queues”205 Minute BreakQuestions Before We Proceed?1121Simple Queuing - FIFO and Drop Tail• Most of today’s routers• Transmission via FIFO scheduling– First-in first-out queue– Packets transmitted in the order they arrive• Buffer management: drop-tail– If the queue is full, drop the incoming packet22Queuing ExampleP = 1 Kbit; R = 1 Mbps P/R = 1 msPacket arrivalTime (ms)TimeDelay for packet that arrives at time t, d(t) = Q(t)/R + P/RQ(t)1 KbP bits Q bits00.517 7.50.5 Kb1.5 Kb2 Kbpacket 1, d(0) = 1mspacket 2, d(0.5) = 1.5mspacket 3, d(1) = 2ms1223Queuing Theory• Enormous literature exists on mathematicalmodeling of queues• Abstractions:– Arrivals (“customers”) comes to the system
View Full Document
Unlocking...