Congestion Control for High Bandwidth-Delay Product Networks

XCP, the Explicit Control Protocol
SIGCOMM '02
by Diana Katabi, MIT-LCS, dk@mit.edu,
Mark Handley, ICSI, mjh@icsi.berkeley.edu
Charlie Rohrs, Tellabs, crhors@mit.edu

Presented by Guillaume Marceau for WPI CS577
on September 28, 2009

TCP is blind

TCP tries to discover the amount of bandwidth available, but it is blind
Packet drop are the only feedback, which ...

... is binary (drop/no drop)

... is ambiguous (caused by congestion or by faults)

... is delayed (must wait a full timeout before declaring a drop)

This has for consequence that ...

TCP oscillates at high delay bandwidth product

TCP's slow start is slow, which is painful at large b×d

TCP is biased against flows with large rtt

Can't the routers just tell the sender how much bandwidth is available and be done with it?

TCP oscillates

Outline of the talk

The problem with TCP

Intuitive overview XCP, with pictures    ⟸

The math of XCP

The efficiency controller (in three steps)

The fairness controller

Version I, Egalitarian

Version II, Proportional

Version III, Mix of both

Charts of the simulation results

XCP is built in two parts

The Efficiency Controller, responsible for,

S: the total amount of feedback given, as an aggregate of all flows

ϕ: adjustments for standing queue and control stability

Calling out to the fairness contoller to get the (Subscript[ξ, j])

H_feedback: spread the feedback across many packets

The Fairness Controller, responsible for,

Computing (Subscript[ξ, j]) to acheive fainess, or any some performance objective

Outline of the talk

The problem with TCP

Intuitive overview XCP, with pictures

The math of XCP                                    ⟸

The efficiency controller (in three steps)

The fairness controller

Version I, Egalitarian

Version II, Proportional

Version III, Mix of both

Charts of the simulation results

The Efficiency Controller

(How I understood it anyway, from the bottom up)

The Efficiency Controller, Step 1, Control throughput in aggregate

At its most simple, the feedback is the difference between the capacity and the usage.

S= capacity - offeredLoad    (* S is for Surplus [bytes/sec] *)

This is the aggregate feedback for all flow. But this is a control system, so you don't want to commit all at once (avoid shower burns).

(Subscript[ϕ, T]) = α·S             (*  (Subscript[ϕ, T]) is for Total Feedback [bytes/sec],
			     0 < α < 1 is a control damper,
				 think Zeno's router algorithm *)

Reserve some bandwidth to get rid of any standing queue in the buffer.

(Subscript[ϕ, T]) = α·S - β·Q / d     (* Q is the standing queue size [bytes],
					d is the control delay      [seconds],
					β another control damper       *)

The standing queue is defined as the minimum size of the queue during the previous control period.

The control delay is defined as the average round trip time of all the packets during the previous control period.

The Efficiency Controller, Step 2, Allocate the aggregate feedback

Ask some other module (the fairness controller) to split the feedback in some fair way.

(∑^n)(Subscript[ξ, j])=1  (* (Subscript[ξ, j]) is the proportion of throughput feedback
		assigned to the (j^th) flow, 
		n is the number of flows        *)

Then split it equally across the packets.

(Subscript[H_feedback, T,j,i])= ((Subscript[ξ, j])· (Subscript[ϕ, T]))  / (Subscript[E, j]) (* (Subscript[E, j]) is the expected number of
					 packets from flow j during the next
					 control period *)

Hack alert: They assume that the current packet is representative of the whole flow, or that it all averages out in the end. That is, assume that

(Subscript[E, j])=(((Subscript[cwnd, i]),)/(Subscript[s, i]))·(d/(Subscript[rtt, i]))  (* The number of packet in the cwnd
				 × the number of cwnd's in 
					the control period *)

(Subscript[H_feedback, T,j,i])= ((Subscript[ξ, j])· (Subscript[ϕ, T]))  /( (((Subscript[cwnd, i]),)/(Subscript[s, i]))·(d/(Subscript[rtt, i])) )

The Efficiency Controller, Step 3, Convert Δthroughput to Δcwnd

Rates are hard to measure. Beside, rates at the sender are controlled by the congestion window, might as well control the senders cwnd's, it's more direct.
Recall,

cwnd = bandwidth × delay   (* cwnds are set to the b-d product *)

Then  converting the aggregate feedback from throughput to congestion window,

(Subscript[ϕ, T]) = α·S - β·Q / d

means multiplying by d on both sides,

ϕ = α·d·S -β·Q

Similarly, convert the per-packet feedback from from throughput to congestion window,

(Subscript[H_feedback, j,i])= (Subscript[H_feedback, T,j,i])·(Subscript[rtt, i])  (* assuming the packet is representative of the whole.
aka, (Subscript[rtt, i]) ≈ (Subscript[rtt, j]) *)

(Subscript[H_feedback, j,i])= (((Subscript[ξ, j])· (Subscript[ϕ, T]))  /((((Subscript[cwnd, i]),)/(Subscript[s, i]))·(d/(Subscript[rtt, i]))))·(Subscript[rtt, i])

(Subscript[H_feedback, j,i])=(Subscript[ξ, j])·(((Subscript[ϕ, T])·((Subscript[rtt, i])^2)·(Subscript[s, i]))/(d·(Subscript[cwnd, i])))

The Fairness Controller

(Choosing (Subscript[ξ, j]) wisely)

Version I, Egalitarian feedback

A first intuition of fairness might be, set all the (Subscript[ξ, j]) to the same value. Namely,

(Subscript[ξ, 1])=(Subscript[ξ, 2])=... =(Subscript[ξ, n])= ξ = (1/n)

But measuring n directly is hard. Let's try to find an indirect definition.

(Subscript[ϕ, T])=(Overscript[(∑_(i=0)), L])(Subscript[H_feedback, T,j,i])   (* L is the total number of packets
			through the router during control period *)

Substitute the definition of (Subscript[feedback, T,j,i]). Since all the flows have the same ξ, we can drop the j subscript.

(Subscript[ϕ, T])  = (Overscript[(∑_(i=0)), L])(ξ·(((Subscript[ϕ, T])·(Subscript[rtt, i])·(Subscript[s, i]))/(d·(Subscript[cwnd, i]))))  
(Subscript[ϕ, T])=((ξ·(Subscript[ϕ, T]))/d)·(Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))  
ξ=(d/((Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))     (* which is an odd way to measure (1/n) *)

Version I, Egalitarian feedback (continued)

(Subscript[H_feedback, i])=ξ·(((Subscript[ϕ, T])·((Subscript[rtt, i])^2)·(Subscript[s, i]))/(d·(Subscript[cwnd, i])))
(Subscript[H_feedback, i])=(d/((Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))·(((Subscript[ϕ, T])·((Subscript[rtt, i])^2)·(Subscript[s, i]))/(d·(Subscript[cwnd, i])))
(Subscript[H_feedback, i])=((Subscript[ϕ, T])/((Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))·((((Subscript[rtt, i])^2)·(Subscript[s, i]))/(Subscript[cwnd, i]))  (* the d cancel *)
(Subscript[H_feedback, i])=(ϕ/(d·(Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))·((((Subscript[rtt, i])^2)·(Subscript[s, i]))/(Subscript[cwnd, i]))  (* with (Subscript[ϕ, T])=(ϕ/d) *)

Which is the formula in the paper for equal-Δthroughput feedback without shuffling.

Hack Alert: The left side of the dot refers to values from past packets, the right side of the dot refers the values taken from this packet's header.

Version II: Feedback proportional to throughput

(Subscript[ξ, j])= (Subscript[bandwidth, j])/ offeredLoad

This is well-formed, ∑(Subscript[ξ, j])=1, since (∑^n)(Subscript[bandwidth, j])=offeredLoad. Then

(Subscript[ξ, j])= ((Subscript[cwnd, i])/(Subscript[rtt, i]))/offeredLoad

Same slight of hand, assume the packet is representative of the whole.

(Subscript[H_feedback, j,i])=(Subscript[ξ, j])·(((Subscript[ϕ, T])·((Subscript[rtt, i])^2)·(Subscript[s, i]))/(d·(Subscript[cwnd, i]))) (*recall the def. of feedback*)

(Subscript[H_feedback, i])=((Subscript[cwnd, i])/((Subscript[rtt, i])·offeredLoad))·(((Subscript[ϕ, T])·((Subscript[rtt, i])^2)·(Subscript[s, i]))/(d·(Subscript[cwnd, i])))(*insert (Subscript[ξ, j])*)

(Subscript[H_feedback, i])=(1/offeredLoad)·(((Subscript[ϕ, T])·(Subscript[rtt, i])·(Subscript[s, i]))/d)   (*cancel*)

(Subscript[H_feedback, i])=(1/((∑(Subscript[s, i]))/d))·((ϕ·(Subscript[rtt, i])·(Subscript[s, i]))/(d^2)) (*def. of load and (Subscript[ϕ, T])*)

(Subscript[H_feedback, i])=(ϕ/(d·∑(Subscript[s, i])))·((Subscript[rtt, i])·(Subscript[s, i])) (*cancel and regroup *)

Which is the formula in the paper for feedback ∝ throughput without shuffling.

Same Hack Alert: The left side of the dot refers to values from past packets, the right side of the dot refers the values taken FROM this packet's header.

Version III : A bit of both

Version I, egalitarian feedback (equal Δthroughput for everyone) doesn't make sense for negatives feedback — you might be asking a flow to go negative.

Version II, feedback ∝ throughput, doesn't make sense for positive feedback — you give the most boost to the already fast flows.

Thus Version III, mix of both, positive feedback is egalitarian, negative feedback is ∝ throughput.

(Subscript[posFeedback, i]) = ((Max[ϕ,0])/(d·(Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))·((((Subscript[rtt, i])^2)·(Subscript[s, i]))/(Subscript[cwnd, i]))

(Subscript[negFeedback, i]) = ((Max[-ϕ,0])/(d·∑(Subscript[s, i])))·((Subscript[rtt, i])·(Subscript[s, i]))

(Subscript[H_feedback, i]) = (Subscript[posFeedback, i]) - (Subscript[negFeedback, i])

Good news! If you oscillate between the two you converge to fairness!

Bad news! The whole point of this protocol is to kill oscillations!

Exploring convergence via oscillations

ϕ[offeredLoad_,capacity_]:=α (capacity-offeredLoad);
HfEgalitarian[offeredLoad_,capacity_,bandwidth_,n_]:=
ϕ[offeredLoad,capacity]/n;
HfProportional[offeredLoad_,capacity_,bandwidth_,n_]:=
ϕ[offeredLoad,capacity](bandwidth/offeredLoad);

length[lst_]:=Dimensions[lst][[1]];

XCPEgalitarian[bandwidths_]:=
Map[b|->
b+HfEgalitarian[Apply[Plus,bandwidths],capacity,b,length[bandwidths]],
bandwidths];
XCPProportional[bandwidths_]:=
Map[b|->
b+HfProportional[Apply[Plus,bandwidths],capacity,b,length[bandwidths]],
bandwidths];

convergeXCPfn[xcpFn_,init_]:=Module[{tbl=Table[Nest[b|->xcpFn[b],init,t],{t,0,40}]},
Append[Transpose[tbl],Map[lst|->Apply[Plus,lst], tbl]]];

XCPPlot[xcpFn_]:=
ListLinePlot[
convergeXCPfn[xcpFn,init],
PlotStyle->Append[Table[Thick,{i,length[init]}],{Thin,Dashing[0.02]}],
PlotRange->{Automatic,{Automatic,Max[init,capacity]}},
AxesLabel->{"iterations", "bandwidth"}
];

α=0.4;
capacity = 50;
init = {10. ,20.,30.,40.,800.};
{XCPPlot[XCPEgalitarian],XCPPlot[XCPProportional]}

init = {1. ,5.};
{XCPPlot[XCPEgalitarian],XCPPlot[XCPProportional]}

XCPBoth[bandwidths_]:=
(capacity =capacity*1.5;
Module[{b2=XCPEgalitarian[bandwidths]},
capacity = capacity/ 1.5/1.5;
Module[{b3 = XCPProportional[b2]},
capacity = capacity * 1.5;
b3]]);

init = {10. ,20.,30.,40.,200.};
XCPPlot[XCPBoth]

init = {1. ,5.};
XCPPlot[XCPBoth]

Forcing a small amount of oscillation

The solution: re-introduce oscillation into the system in a controlled manner

h = Max[0, γ·y - Abs[ϕ]]

where

γ = 0.1                         (* the size of the oscillation desired *)
y = offeredLoad · d  (* the trafic during a control period*)

namely, unless we converged on a fair distribution, some minimum amount of traffic must always be trifled with, if not by ϕ, then by h.

(Subscript[posFeedback, i]) = ((h+Max[ϕ,0])/(d·(Overscript[(∑_(i=0)), L])((((Subscript[rtt, i])·(Subscript[s, i]))/(Subscript[cwnd, i])))))·((((Subscript[rtt, i])^2)·(Subscript[s, i]))/(Subscript[cwnd, i]))

(Subscript[negFeedback, i]) = ((h+Max[-ϕ,0])/(d·∑(Subscript[s, i])))·((Subscript[rtt, i])·(Subscript[s, i]))

(Subscript[H_feedback, i]) = (Subscript[posFeedback, i]) - (Subscript[negFeedback, i])

The magical h shuffle

h[γ_,offeredLoad_,capacity_]:=
Max[0,γ offeredLoad - Abs[capacity - offeredLoad]];
ϕ[offeredLoad_,capacity_]:=
α (capacity-offeredLoad);
neg[γ_,offeredLoad_,capacity_]:=
h[γ,offeredLoad,capacity]+Max[0,-ϕ[offeredLoad,capacity]];
pos[γ_,offeredLoad_,capacity_]:=
h[γ,offeredLoad,capacity]+Max[0,ϕ[offeredLoad,capacity]];
Hf[γ_,offeredLoad_,capacity_,bandwidth_,n_]:=
pos[γ,offeredLoad,capacity]/n-neg[γ,offeredLoad,capacity](bandwidth/offeredLoad);
Hf'[γ_,surplus_,fairRatio_,n_]:=
Hf[γ,capacity-surplus,capacity,fairRatio/n*capacity,n];

α=1.0;
capacity=50;
Manipulate[Plot[
Hf'[γ,surplus, fairRatio,n],
{surplus, -capacity,capacity},
PlotStyle->Thick,
AxesLabel->{"Surplus","Feedback"}],
{{fairRatio,0},0,4,0.1,Appearance->"Labeled"},
{{n,2},1,10,1,Appearance->"Labeled"},
{{γ,0},0,0.9,0.05,Appearance->"Labeled"}]

Convergence to fairness

XCP[γ_,bandwidths_]:=
Map[b|->
b+Hf[γ,Apply[Plus,bandwidths],capacity,b,length[bandwidths]],
bandwidths];
convergeXCP[γ_,init_]:=Module[{tbl=Table[Nest[b|->XCP[γ,b],init,t],{t,0,40}]},
Append[Transpose[tbl],Map[lst|->Apply[Plus,lst], tbl]]];

init = {10. ,20.,30.,40.,200.};
α=0.4;
Manipulate[
ListLinePlot[
convergeXCP[γ,init],
PlotStyle->Append[Table[Thick,{5}],Thin],
PlotRange->{Automatic,{0,200}},
AxesLabel->{"iterations", "bandwidth"}
],
{{γ,0.1},0,0.5,Appearance->"Labeled"}]

Outline of the talk

The problem with TCP

Intuitive overview XCP, with pictures

The math of XCP

The efficiency controller (in three steps)

The fairness controller

Version I, Egalitarian

Version II, Proportional

Version III, Mix of both

Charts of the simulation results                     ⟸

Simulation results

(Skipping to the most interesting ones)

Simulation topologies

Fixed: Bottleneck topology, 50 flows forwards, 50 flows reversewards, RTT is 80ms
Vary: Link bandwidth

Largest bandwidth-delay is  320 Megs · seconds (!)
Longest queue size is 2.3 Megs at 1Meg/s (2.3 seconds to clear)
150 Meg/s comes back later

Fixed: Bottleneck topology, 50 flows forwards, 50 flows reversewards, Link is 150Meg/s
Vary: RTT

Fixed: Bottleneck topology, RTT is 80ms, Link is 150Meg/s
Vary: Number of flows

The war between mice and elephants

New Slide

New Slide

Quick convergence to fairness

Quick and stable asjustment to suddent changes

Non-fair bandwidth allocation, assign (Subscript[ξ, i])∝$

XCP is TCP-friendly

Robustness to high variance to round trip time

This is not a good challenge of this weakness of the design of XCP. Large variance in RTT will make it difficult for XCP to adjust to the dynamic of flows which are far away from the average RTT. Yet, there are no dynamics in this simulation.