15 744 Computer Networking L 10 Queue Management Queue Management RED Other AQMs Assigned reading FJ93 Random Early Detection Gateways for Congestion Avoidance Srinivasan Seshan 2002 L 10 10 9 02 2 Overview Queuing Disciplines RED RED Alternatives Srinivasan Seshan 2002 L 10 10 9 02 3 Queuing 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 latency Srinivasan Seshan 2002 L 10 10 9 02 4 Packet Drop Dimensions Aggregation Per connection state Single class Class based queuing Head Drop position Tail Random location Early drop Srinivasan Seshan 2002 Overflow drop L 10 10 9 02 5 Typical Internet Queuing FIFO drop tail Simplest choice Used widely in the Internet FIFO first in first out Drop tail Implies single class of traffic Arriving packets get dropped when queue is full regardless of flow or importance Important distinction FIFO scheduling discipline Drop tail drop policy Srinivasan Seshan 2002 L 10 10 9 02 6 FIFO 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 events Srinivasan Seshan 2002 L 10 10 9 02 7 Active 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 workload Srinivasan Seshan 2002 L 10 10 9 02 8 Active 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 as congestion is starting Srinivasan Seshan 2002 L 10 10 9 02 9 Overview Queuing Disciplines RED RED Alternatives Srinivasan Seshan 2002 L 10 10 9 02 16 Internet 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 space Srinivasan Seshan 2002 L 10 10 9 02 17 Design 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 changes Srinivasan Seshan 2002 L 10 10 9 02 18 Lock out Problem Random drop Drop front Packet arriving when queue is full causes some random packet to be dropped On full queue drop packet at head of queue Random drop and drop front solve the lockout problem but not the full queues problem Srinivasan Seshan 2002 L 10 10 9 02 19 Full 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 users Srinivasan Seshan 2002 L 10 10 9 02 20 Random Early Detection RED Detect incipient congestion allow bursts Keep power throughput delay high Keep average queue size low Assume hosts respond to lost packets Avoid window synchronization Randomly mark packets Avoid bias against bursty traffic Some protection against ill behaved users Srinivasan Seshan 2002 L 10 10 9 02 21 RED Algorithm Maintain running average of queue length If avgq minth do nothing If avgq maxth drop packet Low queuing send packets through Protection from misbehaving sources Else mark packet in a manner proportional to queue length Notify sources of incipient congestion Srinivasan Seshan 2002 L 10 10 9 02 22 RED Operation Min thresh Max thresh P drop Average Queue Length 1 0 maxP minth Srinivasan Seshan 2002 maxth L 10 10 9 02 Avg queue length 23 RED 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 Pa Mark the arriving packet Else if maxth avg Srinivasan Seshan 2002 Mark the arriving packet L 10 10 9 02 24 Queue Estimation Standard EWMA avgq 1 wq avgq wqqlen Special fix for idle periods why Upper bound on wq depends on minth Want to ignore transient congestion Can calculate the queue average if a burst arrives Set wq such that certain burst size does not exceed minth Lower bound on wq to detect congestion relatively quickly Typical wq 0 002 Srinivasan Seshan 2002 L 10 10 9 02 25 Thresholds minth determined by the utilization requirement 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 RTT Paper suggest ratio of 2 Current rule of thumb is factor of 3 Srinivasan Seshan 2002 L 10 10 9 02 26 Packet Marking Marking probability based on queue length Pb maxp avgq minth maxth minth Just marking based on Pb can lead to clustered marking Could result in synchronization Better to bias Pb by history of unmarked packets Pa Pb 1 count Pb Srinivasan Seshan 2002 L 10 10 9 02 27 Packet Marking maxp is reflective of typical loss rates Paper uses 0 02 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 Vary drop rate from maxp to 1 as the avgq varies from maxth to 2 maxth More robust to setting of maxth and maxp Srinivasan Seshan 2002 L 10 10 9 02 28 Extending RED for Flow Isolation Problem what to do with non cooperative flows Fair queuing achieves isolation using perflow state expensive at backbone routers How can we isolate unresponsive flows without per flow state RED penalty box Monitor history for packet drops identify flows that use disproportionate bandwidth Isolate and punish those flows Srinivasan Seshan 2002 L 10 10 9 02 29 Overview Queuing Disciplines RED RED Alternatives Srinivasan Seshan 2002 L 10 10 9 02 30 FRED Fair Random Early Drop Sigcomm 1997 Maintain per flow state only for active flows ones having packets in the buffer minq and maxq min and max number of buffers a flow is allowed occupy avgcq average buffers per flow Strike count of number of times flow has exceeded maxq Srinivasan Seshan 2002 L 10 10 9 02 31 FRED Fragile
View Full Document
Unlocking...