115-744: Computer NetworkingL-6 TCP & RoutersTCP & Routers•RED•XCP•Assigned readingAssigned reading• [FJ93] Random Early Detection Gateways for Congestion Avoidance• [KHR02] Congestion Control for High Bandwidth-Delay Product Networks2Overview• Queuing Disciplines•RED•RED• RED Alternatives•XCP3Queuing 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 (when4•Buffer space: which packet to drop next (when required)• Queuing also affects latency2Packet Drop DimensionsAggregationPerconnection stateSingle classPer-connection stateSingle classDrop positionHeadTailClass-based queuing5Random locationEarly drop Overflow dropTypical Internet Queuing• FIFO + drop-tail• Simplest choice•Used widely in the Internet•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 importance6• Important distinction:• FIFO: scheduling discipline• Drop-tail: drop policyFIFO + Drop-tail Problems• Leaves responsibility of congestion control to edges (e.g., TCP)• Does not separate between different flows• No policing: send more packets Æ get more service• Synchronization: end hosts react to same 7eventsActive Queue Management• Design active router queue management to aid congestion control •Why?• Routers can distinguish between propagation and persistent queuing delays• Routers can decide on transient congestion, based on workload8based on workload3Active Queue Designs• Modify both router and hosts• DECbit – congestion bit in packet header• Modify router, hosts use TCP• Fair queuing• Per-connection buffer allocation• RED (Random Early Detection)•Drop packet or set bit in packet header as soon as9•Drop packet or set bit in packet header as soon as congestion is startingOverview• Queuing Disciplines•RED•RED• RED Alternatives•XCP10Internet 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 problem11p• Drop-tail routers treat bursty traffic poorly• Traffic gets synchronized easily Æ allows a few flows to monopolize the queue spaceDesign Objectives• Keep throughput high and delay low•Accommodate bursts• Queue size should reflect ability to accept bursts rather than steady-state queuing• Improve TCP performance with minimal hardware changes124Lock-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 fullqueues problem13out problem but not the full-queues problemFull 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 p14pyp• Does not control misbehaving usersRandom Early Detection (RED)• Detect incipient congestion, allow bursts•Keep power (throughput/delay) highpp ( g p y) g• Keep average queue size low• Assume hosts respond to lost packets• Avoid window synchronization• Randomly mark packets15• Avoid bias against bursty traffic• Some protection against ill-behaved usersRED Algorithm• Maintain running average of queue length• If avgq < minthdo nothinggqthg• Low queuing, send packets through• If avgq > maxth, drop packet• Protection from misbehaving sources• Else mark packet in a manner proportional 16to queue length• Notify sources of incipient congestion5RED OperationMin threshMax threshAverage Queue Length1.0P(drop)17minthmaxthmaxP1.0Avg queue lengthRED Algorithm• Maintain running average of queue length• Byte mode vs. packet mode – why?• For each packet arrival• Calculate average queue size (avg)• If minth≤ avgq < maxth• Calculate probability Pa•With probability P18•With probability Pa• Mark the arriving packet• Else if maxth ≤ avg• Mark the arriving packetQueue Estimation• Standard EWMA: avgq = (1-wq) avgq + wqqlen• Special fix for idle periods – why?• Upper bound on wqdepends on minth• Want to ignore transient congestion• Can calculate the queue average if a burst arrives•Set wqsuch that certain burst size does not exceed minth• Lower bound on wqto detect congestion relatively quickly19quickly•Typical wq= 0.002Thresholds•minthdetermined by the utilization requirementT d ff b t i d l d tili ti•Tradeoff between queuing delay and utilization• Relationship between maxth and minth• Want to ensure that feedback has enough time to make difference in load• Depends on average queue increase in one RTT20RTT • Paper suggest ratio of 2• Current rule of thumb is factor of 36Packet Marking•maxpis reflective of typical loss rates•Paper uses 0.02p• 0.1 is more realistic value• If network needs marking of 20-30% then need to buy a better link!• Gentle variant of RED (recommended)22• Vary drop rate from maxpto 1 as the avgq varies from maxthto 2* maxth• More robust to setting of maxthand maxpExtending RED for Flow Isolation• Problem: what to do with non-cooperative flows?• Fair queuing achieves isolation using per-flow state – expensive at backbone routers• How can we isolate unresponsive flows without per-flow state?• RED penalty box23• Monitor history for packet drops, identify flows that use disproportionate bandwidth• Isolate and punish those flowsOverview• Queuing Disciplines•RED•RED• RED Alternatives• XCP24FRED• Fair Random Early Drop (Sigcomm, 1997)• Maintain per flow state only for active flows py(ones having packets in the buffer)•minq and maxqÆ min and max number of buffers a flow is allowed occupy• avgcq = average buffers per flow25• Strike count of number of times flow has exceeded maxq7FRED – Fragile Flows• Flows that send little data and want to avoid loss•minqis meant to protect these• What should minqbe?• When large number of flows Æ 2-4 packets• Needed for TCP behaviorWh ll b f flÆit26•When small number of flows Æincrease to avgcqFRED• Non-adaptive flows• Flows
View Full Document
Unlocking...