Announcements Additional reading for today s lecture Peterson Davie 3 4 Network Performance Queuing EE 122 Intro to Communication Networks Fall 2006 MW 4 5 30 in Donner 155 Vern Paxson TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 2 Goals of Today s Lecture Window Scaling Finish discussion of Window Scaling Problem 16 bits of advertised window only allows 65 535 bytes in flight TCP Throughput Equation Can significantly restrict throughput Computes approximate long running TCP performance for a given packet loss probability p Relationship between performance and queuing Solution TCP window scaling option negotiated in initial SYN exchange Router architecture Modeling of queuing systems Little s Law FIFO queuing Active Queue Management RED Explicit Congestion Notification ECN shift cnt specifies scaling factor for units used in window advertisement E g shift cnt 5 advertised window is 25 32 byte units 3 Window Scaling con t 4 Window Scaling con t Now we can go fast Suppose in a high speed LAN with RTT 1 msec we can transmit at 1 GB s Q Now how large can the window be What problem arises if packets are occasionally delayed in the network for 10 msec 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 window to 230 to allow receiver to determine whether data fits in the offered window So scaling 14 5 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 6 1 TCP Throughput Equation TCP Throughput Equation con t Consider a network path for which packets are lost with probability p independently Suppose a TCP connection achieves a maximum window 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 Given 3W2 8 1 p then in terms of the average window 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 Total number of packets in the sawtooth T Implications 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 1 5B RTT p Long term throughput falls as 1 RTT Long term throughput falls as 1 sqrt p Therefore 3W2 8 1 p 7 Non TCP transport can use equation to provide TCP friendly congestion control 8 Generic Router Architecture Input and output interfaces are connected through an interconnect Where Does Loss p Come From Anyway input interface Interconnect can be implemented by output interface Interconnect Shared memory Low capacity routers e g PC based routers Shared bus Routers Queuing Medium capacity routers Point to point switched bus High capacity routers Packets fragmented into cells Essentially a network inside the router 9 Shared Memory 1st Generation Shared Backplane CP I Line U nte rfa ce M em or y CPU Route Table Shared Bus 2nd Generation Buffer Memory CPU Line Interface Line Interface Line Interface MAC MAC MAC Typically 0 5Gbps aggregate capacity Limited by rate of shared memory 10 Slide by Nick McKeown 11 Typically 5Gb s aggregate capacity Limited by shared bus Route Table Buffer Memory 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 12 2 What a Router Looks Like Point to Point Switch 3rd Generation Cisco GSR 12416 Line Card Li CPIn ne Uterf ac e M em or y Juniper M160 19 Switched Backplane Local Buffer Memory CPU Card Line Card Routing Table Local Buffer Memory Fwding Table Fwding Table MAC MAC 19 Capacity 160Gb s Power 4 2kW Lines of Code 8M circa year 2000 3ft 6ft 2ft Typically 100Gbps aggregate capacity Slide by Nick McKeown 13 Input Interface Capacity 80Gb s Power 2 6kW 2 5ft Slide courtesy Nick McKeown 14 Output Functions Packet forwarding decide to which output interface to forward each packet based on the information in packet header Buffer management decide when and which packet to drop Scheduler decide when and which packet to transmit Examine packet header Lookup in forwarding table Update packet header Buffer Scheduler Question do we send the packet to the output interface immediately input interface output interface 1 Interconnect 2 15 Output Queued Routers Only output interfaces store packets Advantages Easy to design algorithms only one congestion point Input Queued Routers input interface Input interfaces store packets output interface input interface Easier to build since only need R C Backplane output interface Backplane Though need to implement back pressure to know when to send Disadvantages Requires an output speedup Ro C of N where N is the number of interfaces not feasible 16 RO But harder to build efficiently due to contention and head of line blocking C 17 C R 18 3 Head of line Blocking Cell at head of an input queue cannot be transferred thus blocking the following cells Cannot be transferred because is blocked by orange cell Input 1 Output 1 Input 2 Input 3 5 Minute Break Output 2 Cannot be transferred because output buffer overflow Questions Before We Proceed Output 3 Modern high speed routers use combination of input output queuing with flow control multiple virtual queues 19 Simple Queuing FIFO and Drop Tail 20 Queuing Example Most of today s routers P bits Transmission via FIFO scheduling Q bits P 1 Kbit R 1 Mbps P R 1 ms First in first out queue Packets transmitted in the order they arrive Packet arrival Q t Time ms 0 0 5 1 7 7 5 Delay for packet that arrives at time t d t Q t R P R 2 Kb 1 5 Kb 1 Kb 0 5 Kb Buffer management drop tail If the queue is full drop the incoming packet Time packet 1 d 0 1ms packet 2 d 0 5 1 5ms 21 Queuing Theory Generalized Delay Diagram Enormous literature exists on mathematical modeling of queues Abstractions Arrivals customers comes to the system according to some probability distribution F of interarrival times 22 packet 3 d 1 2ms 1 2 Sender Latest bit seen by time t Receiver Arrival rate is designated e g packets sec System has a set of servers 1 Each arrival has a service time taken from another probability distribution G at point 1 at point 2 Questions Given F G how much delay do customers
View Full Document
Unlocking...