Unformatted text preview:

CS 268: Computer NetworkingTCP & RoutersOverviewQueuing DisciplinesPacket Drop DimensionsTypical Internet QueuingFIFO + Drop-tail ProblemsActive Queue ManagementActive Queue DesignsSlide 10Internet ProblemsDesign ObjectivesLock-out ProblemFull Queues ProblemRandom Early Detection (RED)RED AlgorithmRED OperationSlide 18Queue EstimationThresholdsSlide 22Extending RED for Flow IsolationSlide 24FREDFRED – Fragile FlowsSlide 27CHOKeSlide 29Stochastic Fair BlueSlide 31Slide 32How does XCP Work?Slide 34Slide 35How Does an XCP Router Compute the Feedback?Getting the devil out of the details …LessonsDiscussionCS 268: Computer NetworkingL-6 Router Congestion Control2TCP & Routers•RED•XCP•Assigned reading•[FJ93] Random Early Detection Gateways for Congestion Avoidance•[KHR02] Congestion Control for High Bandwidth-Delay Product Networks3Overview•Queuing Disciplines•RED•RED Alternatives•XCP4Queuing 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 latency5Packet Drop DimensionsAggregationPer-connection stateSingle classDrop positionHeadTailRandom locationClass-based queuingEarly drop Overflow drop6Typical 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 policy7FIFO + 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 events8Active 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 workload9Active 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 starting10Overview•Queuing Disciplines•RED•RED Alternatives•XCP11Internet 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 space12Design 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 changes13Lock-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 problem14Full Queues Problem•Drop packets before queue becomes full (early drop)•Intuition: notify senders of incipient congestion•Example: early random drop (ERD):•If queue length > drop level, drop each new packet with fixed probability p•Does not control misbehaving users15Random 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 users16RED Algorithm•Maintain running average of queue length•If avgq < minth do nothing•Low queuing, send packets through•If avgq > maxth, drop packet•Protection from misbehaving sources•Else mark packet in a manner proportional to queue length•Notify sources of incipient congestion17RED OperationMin threshMax threshAverage Queue LengthminthmaxthmaxP1.0Avg queue lengthP(drop)18RED 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•Mark the arriving packet19Queue 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.00220Thresholds•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 two•Current rule of thumb is factor of three22Packet 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 maxp23Extending 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 box•Monitor history for packet drops, identify flows that use disproportionate bandwidth•Isolate and punish those flows24Overview•Queuing Disciplines•RED•RED Alternatives•XCP25FRED•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 maxq26FRED – Fragile Flows•Flows that send little data and want to avoid loss•minq is meant to protect


View Full Document

Berkeley COMPSCI 268 - Lecture Notes

Documents in this Course
Lecture 8

Lecture 8

33 pages

L-17 P2P

L-17 P2P

50 pages

Multicast

Multicast

54 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?