115-441 Computer NetworkingLecture 19 – TCP & RoutersLecture 19: 04-25-2004 2Overview• TCP modeling• TCP & router queuing• TCP detailsLecture 19: 04-25-2004 3TCP Performance• Can TCP saturate a link?• Congestion control• Increase utilization until… link becomes congested• React by decreasing window by 50%• Window is proportional to rate * RTT• Doesn’t this mean that the network oscillates between 50 and 100% utilization?• Average utilization = 75%??• No…this is *not* right!Lecture 19: 04-25-2004 4TCP Performance• In the real world, router queues play important role• Window is proportional to rate * RTT• But, RTT changes as well the window• Window to fill links = propagation RTT * bottleneck bandwidth• If window is larger, packets sit in queue on bottleneck link2Lecture 19: 04-25-2004 5TCP Performance• If we have a large router queue Æ can get 100% utilization• But, router queues can cause large delays• How big does the queue need to be?• Windows vary from W Æ W/2• Must make sure that link is always full• W/2 > RTT * BW• W = RTT * BW + Qsize• Therefore, Qsize > RTT * BW• Ensures 100% utilization• Delay?• Varies between RTT and 2 * RTTLecture 19: 04-25-2004 6TCP Modeling• Given the congestion behavior of TCP can we predict what type of performance we should get?• What are the important factors• Loss rate: Affects how often window is reduced• RTT: Affects increase rate and relates BW to window• RTO: Affects performance during loss recovery• MSS: Affects increase rateLecture 19: 04-25-2004 7Overall TCP BehaviorTimeWindow• Let’s concentrate on steady state behavior with no timeouts and perfect loss recovery• Packets transferred = area under curveLecture 19: 04-25-2004 8Transmission Rate• What is area under curve?• W = pkts/RTT, T = RTTs• A = avg window * time = ¾W * T• What was bandwidth?• BW = A / T = ¾ W• In packets per RTT• Need to convert to bytes per second• BW = ¾ W * MSS / RTT• What is W?• Depends on loss rateTimeWW/23Lecture 19: 04-25-2004 9Simple TCP Model• Some additional assumptions• Fixed RTT• No delayed ACKs• In steady state, TCP losses packet each time window reaches W packets• Window drops to W/2 packets• Each RTT window increases by 1 packetÆW/2 * RTT before next lossLecture 19: 04-25-2004 10Simple Loss Model• What was the loss rate?• Packets transferred = (¾ W/RTT) * (W/2 * RTT) = 3W2/8• 1 packet lost Æ loss rate = p = 8/3W2•• BW = ¾ * W * MSS / RTT••32pRTTMSSBW×=pW38=ppW233438×==Lecture 19: 04-25-2004 11Fairness• BW proportional to 1/RTT?• Do flows sharing a bottleneck get the same bandwidth?• NO!• TCP is RTT fair• If flows share a bottleneck and have the same RTTsthen they get same bandwidth• Otherwise, in inverse proportion to the RTTLecture 19: 04-25-2004 12TCP Friendliness• What does it mean to be TCP friendly?• TCP is not going away• Any new congestion control must compete with TCP flows• Should not clobber TCP flows and grab bulk of link• Should also be able to hold its own, i.e. grab its fair share, or it will never become popular• How is this quantified/shown?• Has evolved into evaluating loss/throughput behavior• If it shows 1/sqrt(p) behavior it is ok• But is this really true?4Lecture 19: 04-25-2004 13Overview• TCP modeling• TCP & router queuing• TCP detailsLecture 19: 04-25-2004 14Queuing Disciplines• Each router must implement some queuing discipline• Queuing allocates both bandwidth and buffer space:• Bandwidth: which packet to serve (transmit) next • Buffer space: which packet to drop next (when required)• Queuing also affects latencyLecture 19: 04-25-2004 15Typical Internet Queuing• FIFO + drop-tail• Simplest choice• Used widely in the Internet• FIFO (first-in-first-out) • Implies single class of traffic• Drop-tail• Arriving packets get dropped when queue is full regardless of flow or importance• Important distinction:• FIFO: scheduling discipline• Drop-tail: drop policyLecture 19: 04-25-2004 16FIFO + Drop-tail Problems• Leaves responsibility of congestion control completely to the edges (e.g., TCP)• Does not separate between different flows• No policing: send more packets Æ get more service• Synchronization: end hosts react to same events5Lecture 19: 04-25-2004 17FIFO + Drop-tail Problems• Full queues• Routers are forced to have have large queues to maintain high utilizations• TCP detects congestion from loss• Forces network to have long standing queues in steady-state• Lock-out problem• Drop-tail routers treat bursty traffic poorly• Traffic gets synchronized easily Æ allows a few flows to monopolize the queue spaceLecture 19: 04-25-2004 18Active Queue Management• Design active router queue management to aid congestion control • Why?• Router has unified view of queuing behavior• Routers can distinguish between propagation and persistent queuing delays• Routers can decide on transient congestion, based on workloadLecture 19: 04-25-2004 19Design Objectives• Keep throughput high and delay low• High power (throughput/delay)• Accommodate bursts• Queue size should reflect ability to accept bursts rather than steady-state queuing• Improve TCP performance with minimal hardware changesLecture 19: 04-25-2004 20Lock-out Problem• Random drop• Packet arriving when queue is full causes some random packet to be dropped• Drop front• On full queue, drop packet at head of queue• Random drop and drop front solve the lock-out problem but not the full-queues problem6Lecture 19: 04-25-2004 21Full Queues Problem• Drop packets before queue becomes full (early drop)• Intuition: notify senders of incipient congestion• Example: early random drop (ERD):• If qlen > drop level, drop each new packet with fixed probability p• Does not control misbehaving usersLecture 19: 04-25-2004 22Random Early Detection (RED)• Detect incipient congestion• Assume hosts respond to lost packets• Avoid window synchronization• Randomly mark packets• Avoid bias against bursty trafficLecture 19: 04-25-2004 23RED Algorithm• Maintain running average of queue length• If avg < minthdo nothing• Low queuing, send packets through• If avg > maxth, drop packet• Protection from misbehaving sources• Else mark packet in a manner proportional to queue length• Notify sources of incipient congestionLecture 19: 04-25-2004 24RED
View Full Document
Unlocking...