Announcements Next Wednesday s lecture wireless will be given by Jorge Network Performance Queuing I will be away next Wednesday and won t have office hours that day EE 122 Intro to Communication Networks Fall 2007 WF 4 5 30 in Cory 277 But will have my usual Friday office hour Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley Reminder Phase 1 of Project 2 due Tuesday 11PM 1 Goals of Today s Lecture Going Fast Finish discussion of TCP performance Q on a path with RTT 100 msec what s the absolute fastest rate that TCP can achieve Window Scaling TCP Throughput Equation Q what s the absolute largest sliding window that TCP can use Computes approximate long running TCP performance for a given packet loss probability p A advertised window is 16 bits 65 535 bytes Thus max speed 65 535 bytes 100 msec 655 KB s Relationship between performance and queuing Router architecture FIFO queuing Active Queue Management RED Explicit Congestion Notification ECN Modeling of queuing systems Little s Law 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 option 3 Window Scaling Option RFC 1323 Source port Kind 3 indicates Window Scaling Sent in initial SYN Destination port Kind 0 indicates end of options If server s SYN ACK also includes a Window Scaling option then scaling is in effect Acknowledgment Len 6 0 Flags Advertised window Checksum 4 Window Scaling con t Sequence number HdrLen specifies 4 bytes of options 2 The server including the option confirms its use Urgent pointer shift cnt specifies scaling factor for units used in window advertisement Kind 3 Length 3 shift cnt Kind 0 E g shift cnt 5 advertised window is 25 32 byte units Data 5 6 1 Window Scaling con t Window Scaling con t Now we can go fast Suppose high speed LAN RTT 1 msec How fast can we transmit Q Now how large can the window be 1 GB msec 1 TB sec A Clearly must not exceed 232 What problem arises if packets are occasionally delayed in the network for 10 msec If it does then can t disambiguate data in flight So scaling 16 In fact somewhat subtle requirements limit window to 230 to allow receiver to determine whether data fits in the offered window So scaling 14 7 Sequence number wrap can t tell earlier delayed segments 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 restriction not to compute RTT for ACKs of retransmitted packets 8 Relationship of Performance Loss For packets of B bytes and packet loss rate p throughput is 1 5B T RTT p Where Does Loss p Come From Anyway Implications Long term throughput falls as 1 RTT throughput falls as 1 sqrt p Long term Routers Queuing Non TCP transport can use equation to provide TCP friendly congestion control 10 9 Shared Memory 1st Generation Generic Router Architecture Input and output interfaces are connected through an interconnect Interconnect can be implemented by Shared memory Shared Backplane input interface CPU output interface CP I Line U nte rfa ce M em or y Interconnect o Low capacity routers e g PC based routers Shared bus Route Table Buffer Memory Line Interface Line Interface Line Interface MAC MAC MAC o Medium capacity routers Point to point switched bus o High capacity routers o Packets fragmented into cells o Essentially a network inside the router 11 Typically 0 5Gbps aggregate capacity Limited by rate of shared memory Slide by Nick McKeown 12 2 Shared Bus 2nd Generation Buffer Memory Route Table CPU Typically 5Gb s aggregate capacity Limited by shared bus Point to Point Switch 3rd Generation Switched Backplane Line Card Line Card Line Card Buffer Memory Buffer Memory Buffer Memory Fwding Cache Fwding Cache Fwding Cache MAC MAC MAC Slide by Nick McKeown Li CPIn ne Uterf ac e M em or y 13 What a Router Looks Like Cisco GSR 12416 CPU Card Line Card Local Buffer Memory Routing Table Local Buffer Memory Fwding Table Fwding Table MAC MAC Typically 100Gbps aggregate capacity Slide by Nick McKeown 14 Input Interface Packet forwarding decide to which output interface to forward each packet based on the information in packet header Juniper M160 19 Line Card Examine packet header Lookup in forwarding table Update packet header 19 Capacity 160Gb s Power 4 2kW Lines of Code 8M circa year 2000 Capacity 80Gb s Power 2 6kW Question do we send the packet to the output interface immediately input interface output interface 3ft 6ft Interconnect 2ft 2 5ft Slide courtesy Nick McKeown 15 Output Functions 16 Output Queued Routers Buffer management decide when and which packet to drop Only output interfaces store packets Scheduler decide when and which packet to transmit Advantages Easy to design algorithms only one congestion point Buffer Scheduler input interface output interface Backplane Disadvantages Requires an output speedup Ro C N where N is the number of interfaces not feasible 1 2 17 Ro C 18 3 Input Queued Routers Input interfaces store packets Head of line Blocking input interface Easier to build since only need R C Cell at head of an input queue cannot be transferred thus blocking the following cells output interface Cannot be transferred because is blocked by orange cell Backplane Though need to implement back pressure to know when to send But harder to build efficiently due to contention and head of line blocking Input 1 Output 1 Input 2 C R Input 3 19 Output 2 Cannot be transferred because output buffer overflow Output 3 Modern high speed routers use combination of input output queuing with flow control multiple virtual queues 20 Simple 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 5 Minute Break Questions Before We Proceed Buffer management drop tail If the queue is full drop the incoming packet 21 22 Bursty Loss From Drop Tail Queuing TCP depends on packet loss Packet loss is the indication of congestion In fact TCP drives the network into packet loss by continuing to increase the sending rate Refinements to FIFO Drop tail queuing leads to bursty loss When a link becomes congested many arriving packets encounter a full queue And as a result many flows perceive congestion and in fact tend to become synchronized by nearsimultaneous loss Random Early
View Full Document
Unlocking...