Network-Based Congestion ControlENEE 426 | Communication Networks | Spring 2008 Lecture 20Motivation• Hosts can’t always be “trusted” to implement proper congestion control• Network needs to place guarantees on traffic flows to ensure required service level– Support real-time traffic, multimedia• Before– Network treats each packet equally• After– Network treats packets as a part of a network flow and ensures fair allocation between flowsENEE 426 | Communication Networks | Spring 2008 Lecture 20Flow View10 Mbps100 Mbps 1 MbpsENEE 426 | Communication Networks | Spring 2008 Lecture 20Flow Definition• Definition … undefined– Flow could be all traffic from a particular source– Flow could be all traffic to a particular destination– Flow could be all traffic to/from a particular source/destination pair– Flow could be an individual TCP or UDP stream identified by source/destination address/port• Depends on what your ISP wants to throttle– Different policies on the edge of the network versus the core of the network• For now, assume it’s a TCP or UDP streamENEE 426 | Communication Networks | Spring 2008 Lecture 20Goal: Fairness• Goal is to provide a fair allocation between flows• What’s fair?ENEE 426 | Communication Networks | Spring 2008 Lecture 20Fairness Criteria• Given traffic flows x1, …, xn• F(x1, …, xn) is fairness function, want to maximize• Max-Min Fairness– F(x1, …, xn) = min(x1, …, xn)• Maximal Throughput– F(x1, …, xn) = x1+ … + xn• Proportional Fairness– F(x1, …, xn) = x1.… .Xn• In networks, max-min fairness is typically usedENEE 426 | Communication Networks | Spring 2008 Lecture 20Queuing Disciplines• Routers are basically sets of queues• The order packets are serviced from queues determines which flows get how much of the networks resourcesENEE 426 | Communication Networks | Spring 2008 Lecture 20FIFO• First-In First-Out• If queue is full, packets are droppedENEE 426 | Communication Networks | Spring 2008 Lecture 20Priority FIFO• Packets are marked with “service class”• Uses the TOS (type of service) field in the IP header• Problem: Starvation– Low priority packets may NEVER get through if the queue is constantly full with higher priority packets– Only works if very few packets have a higher priorityENEE 426 | Communication Networks | Spring 2008 Lecture 20Fair Queuing• Each flow receives its own virtual queue• Virtual queues are serviced in round-robin fashion• Problem: per-flow state– Router must maintain queue for every active flow– Not scalableENEE 426 | Communication Networks | Spring 2008 Lecture 20Fair Queuing• Implementation more complex• Need to handle differing packet sizes• Typically implemented as a single priority FIFO where priorities are computed based on packet historiesENEE 426 | Communication Networks | Spring 2008 Lecture 20Congestion Avoidance• Rather than have the routers strictly enforce congestion control policies, they can provide additional information to end hosts such that those hosts can make better decisions• Key approach: Random Early Detection (RED)• Two key ideas:– When router queues are starting to fill up, they warn flows by marking the ECN bit– Statistically drops packets based on the probability of the queue filling up• Prevents TCP synchronization problemsENEE 426 | Communication Networks | Spring 2008 Lecture 20RED FlowchartENEE 426 | Communication Networks | Spring 2008 Lecture 20Penalization Schemes• “TCP Friendliness” refers to property that a non-TCP flow behaves well with TCP flows• Some queuing disciplines can encourage end-hosts to self-enforce TCP Friendliness• If usedRate > fairRate, allocate fairRate2/usedRateto flow– The more rate they try to use over their fair share, the less rate they receive– Game theoretical result is self regulationENEE 426 | Communication Networks | Spring 2008 Lecture 20TCP Friendly UDP• Would like self-regulating UDP streams• Use TCP congestion control, but not sliding window• Result: Equation-based Congestion Control• RTT = Round Trip Time•r= loss