Transcript 30 - ShareCourse

Promoting the Use of End-to-End
Congestion Control in the Internet
Sally Floyd and Kevin Fall
IEEE-ACAM Transactions on Networking,1999
101062804 馬儀蔓
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
1 /30
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
2 /30
Introduction
• The Internet is more and more bigger.
• No longer rely on
• All end-nodes to use end-to-end congestion control
for best-effort traffic.
• All developers to incorporate end-to-end congestion
control in their Internet applications.
• The network itself must participate in controlling
its own resource utilization.
3 /30
Controlling Best-Effort Traffic
• Assume the Internet will continue to become
congested due to a scarcity of bandwidth, three
approaches
• Per-flow scheduling
• Separately regulate the bandwidth used by each
best-effort flow.
• Incentives for end-to-end congestions control
• Restrict the bandwidth of unresponsive best-effort
flows.
• Pricing mechanisms
4 /30
Purpose
• As the Internet expands to an even larger
community
• Recognize the essential role of end-to-end
congestion control.
• Strengthening incentives for using end-to-end
congestion control is critical issues.
5 /30
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
6 /30
Unresponsive Flows
• Unresponsive flows are high bandwidth flows
that
• Do not use end-to-end congestion control
• Do not reduce their load on the network when
subjected to packet drops.
• Two problems
• Unfairness
• Congestion collapse
7 /30
Problem of Unfairness
• When TCP flows competing with unresponsive
UDP flows for scare bandwidth
• TCP flows reduce their sending rates.
• The uncoorperate UDP flows use the available
bandwidth.
3 TCP flows
8 /30
1 UDP flow
Problem of Unfairness
Aggregate goodput
UDP arrival rate
UDP goodput
TCP goodput
• Unfairness with FCFS scheduling in routers.
• Goodput: a goodput of a flow is as the bandwidth delivered to the receiver,
excluding duplicate packets.
9 /30
Problem of Unfairness
Aggregate goodput
TCP goodput
UDP arrival rate
UDP goodput
• No unfairness with weighted round-robin (WRR)
scheduling in routers
10/30
Congestion collapse
• Congestion collapse occurs when an increase in
the network load results in a decrease in the
useful work done by the network.
• Classical congestion collapse
• Fragment-based congestion collapse
• Congestion collapse from
• Undelivered packets
• Bandwidth is wasted by delivering packets through the
network that are dropped before reaching their ultimate
destination
• Increased control traffic
• Stale packets
11/30
Congestion collapse
• Simulations with one TCP flow and three UDP
flows, showing congestion collapse with FIFO
scheduling.
12/30
Congestion collapse
• Simulations with one TCP flow and three UDP
flows, showing congestion collapse with WRR
scheduling.
13/30
Congestion collapse
• Congestion collapse as the number of UDP flows
increases.
14/30
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
15/30
Flows to be Detected
• Identify a high bandwidth flow in times of
congestion as
• Not TCP-friendly flow
• Applied to a single flow.
• Unresponsive flow
• Applied to a single flow.
• Disproportionate-bandwidth flow
• Applied to both a single flow and aggregates of
flows.
• Based on IP and port number to distinguish
different flows.
16/30
Identify Not TCP-friendly flow
• Definition: TCP-friendly flows
• Reducing its congestion window at least by
half upon indications of congestion.
• Increasing its congestion window by a constant
rate of at most one packet per roundtrip time.
• Sending rate for a TCP connection—
17/30
Identify Not TCP-friendly flow
• Limitation
• Only can test a flow of a single TCP
connection.
• Difficult to determine the maximum packet
size B in bytes or the minimum RTT.
• Measurements should be taken over a
sufficiently large time interval.
• Only applies for non-bursty packet drop
behavior.
18/30
Identify Not TCP-friendly flow
• Response by the router:
• Restrict the bandwidth of best-effort flows
determined not to be TCP-friendly in times of
congestion.
• Remove restriction when
• There is no longer any significant link congestion.
• It has been shown to reduce its arrival rate
appropriately in response to congestion.
19/30
Identify Unresponsive Flows
• The TCP-friendly test is
• Based on the specific congestion control
responses of TCP.
• Not very useful for routers unable to assume
strong bounds on TCP packet sizes and roundtrip times.
• So, verify that a high-bandwidth flow was
responsive.
20/30
Identify Unresponsive Flows
• Responsive flow: its arrival rate decreases
appropriately in response to an increased packet
drop rate.
• Drop rate increase by a factor 𝑥, the presented
load for a high bandwidth flow should decrease
by a factor 𝑥.
• Require estimates of
• Flow’s arrival rate
• Packet drop rate
21/30
Identify Unresponsive Flows
• Limitation: less straightforward for a flow with a
variable demand.
• Possible end-to-end congestion mechanisms.
• The original data source itself could be ON/OFF or
have strong rate variations over time.
• Response by the router:
• Restrict the bandwidth of best-effort flows
determined to be unresponsive in times of
congestion.
• Can apply test actively.
22/30
Identify Disproportionatebandwidth flow
• Identify flows that use a disproportionate share of
the bandwidth in times of high congestion.
• A disproportionate share is defined as a
significantly larger share than other flows.
• TCP flow could use a “disproportionate share” of
bandwidth, if TCP
• With persistent demand
• Using large windows
• With a significantly smaller roundtrip time or
larger packet sizes
23/30
Identify Disproportionatebandwidth flow
• Two components of the disproportionatebandwidth test
• Check if a flow is using a disproportionate
share of the bandwidth.
• The fraction of the flow’s aggregate arrival rate is
more than log(3𝑛)/ 𝑛 ,for n is the number of flows
with packet drops.
• Takes into account the level of congestion itself
• Define a flow as having a high arrival rate relative
to the level of congestion if its arrival rate is greater
than 𝑐/ 𝑝 Bps for some constant 𝑐.
24/30
Identify Disproportionatebandwidth flow
• Limitation: gauging the level of unsatisfied
demand is problematic.
• A large RRT TCP flow
• A short busty web transfer
• Response by the router:
• Limit the restriction of a high-bandwidth
responsive flow.
• So, over the long run, each such flow receives as
much bandwidth as the highest-bandwidth
unrestricted flow.
25/30
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
26/30
Per-flow scheduling
• Per-flow scheduling separately regulate the
bandwidth used by each best-effort flow.
• Indeed care of many of the fairness issues
concerning competing best-effort flows.
• However,
• It can not prevent congestion collapse from
undelivered packets.
• May encourage flows make sure that “their”
queue in congested router never goes empty.
27/30
Pricing mechanisms
• Pricing mechanisms use pricing as a way to
• Share transmission resources.
• Control and prevent the network congestion.
• However, the deployment of pricing structures is
sensitive to the behavior of each flow in the
global Internet.
28/30
Outline
• Introduction
• The Problem of Unresponsive Flows
• Identifying Flows to Regulate
• Alternate Approach
• Conclusion
29/30
Conclusion
• In the Internet,
• Need for end-to-end congestion control.
• Need mechanisms to detect and restrict
unresponsive or high-bandwidth best-effort
flows in times of congestion control.
• Not yet outlined a specific proposal for
mechanisms for identifying and controlling
unresponsive flows.
30/30