11Network Performance: QueuingEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Next Wednesday’s lecture (wireless) will begiven by Jorge• I will be away next Wednesday and won’t haveoffice hours that day– But will have my usual Friday office hour• Reminder:– Phase 1 of Project #2 due Tuesday @ 11PM23Goals of Today’s Lecture• Finish discussion of TCP performance:– Window Scaling• TCP Throughput Equation– Computes approximate long-running TCP performancefor a given packet loss probability p• Relationship between performance and queuing– Router architecture– FIFO queuing– Active Queue Management - RED– Explicit Congestion Notification - ECN– Modeling of queuing systems & Little’s Law4Going Fast• Q: on a path with RTT = 100 msec, what’s theabsolute fastest rate that TCP can achieve?• Q: what’s the absolute largest sliding window thatTCP can use?– A: advertised window is 16 bits ⇒ 65,535 bytes– Thus: max speed = 65,535 bytes / 100 msec = 655 KB/s• Q: how can we fix this problem?– A: we need a larger window• Q: how do we make the window larger?– A: using a TCP option35Window Scaling Option (RFC 1323)Source port Destination portSequence numberAcknowledgmentAdvertised windowLen=6Flags0Checksum Urgent pointerDataHdrLen specifies4 bytes of options.Kind=3 indicates“Window Scaling”.Kind=0 indicates“end of options”.+---------+---------+---------+---------+| Kind=3 |Length=3 |shift.cnt| Kind=0 |+---------+---------+---------+---------+6Window Scaling, con’t• Sent in initial SYN• If server’s SYN-ACK also includes a WindowScaling option, then scaling is in effect– The server including the option confirms its use•shift.cnt specifies scaling factor for units usedin window advertisement– E.g., shift.cnt = 5 ⇒advertised window is 25 = 32-byte units47Window 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 ≤ 148Window Scaling, con’t• Now we can go fast. Suppose high-speed LAN,RTT = 1 msec. How fast can we transmit?– 1 GB/msec = 1 TB/sec.• 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)59Relationship of Performance & Loss• For packets of B bytes and packet loss rate p,throughput is:• 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 p10Where Does Loss (= p) Come From,Anyway?Routers & Queuing611Generic Router Architecture• Input and output interfacesare connected through aninterconnect• Interconnect can beimplemented by– Shared memoryo Low capacity routers (e.g.,PC-based routers)– Shared buso Medium capacity routers– Point-to-point (switched) buso High capacity routerso Packets fragmented intocellso Essentially a network insidethe router!input interface output interfaceInter-connect12Shared Memory (1st Generation)RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically < 0.5Gbps aggregate capacityLimited by rate of shared memoryShared BackplaneLineInterfaceCPUMemory(* Slide by Nick McKeown)713Shared Bus (2nd Generation)RouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemoryTypically < 5Gb/s aggregatecapacity; Limited by shared bus(* Slide by Nick McKeown)14Point-to-Point Switch (3rd Generation)LineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemorySwitched BackplaneLineInterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically ~ 100Gbps aggregate capacity(*Slide by Nick McKeown)815What 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 McKeown16Input Interface• Packet forwarding: decide to which output interface to forward eachpacket based on the information in packet header– Examine packet header– Lookup in forwarding table– Update packet header• Question: do we send thepacket to the outputinterface immediately?input interface output interfaceInter-connect917Output Functions• Buffer management: decide when and which packet to drop• Scheduler: decide when and which packet to transmit12SchedulerBuffer18Output Queued Routers• Only output interfaces storepackets• Advantages– Easy to design algorithms:only one congestion point• Disadvantages– Requires an output speedupRo = C•N, where N is thenumber of interfaces ⇒ notfeasibleinput interface output interfaceBackplaneCRo1019Input 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 interfaceBackplaneCR20Head-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”11215 Minute BreakQuestions Before We Proceed?22Simple 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 packet1223Refinements to FIFORandom Early Detection (RED)Explicit Congestion Notification (ECN)24Bursty Loss From Drop-Tail
View Full Document
Unlocking...