Transcript slides ppt

New Designs
for the Internet
• Why can’t I get higher throughput?
• Why is my online video jerky?
• How is capacity shared in the Internet?
Some Internet History
• 1974: First draft of TCP/IP
“A protocol for packet network interconnection”,
Vint Cerf and Robert Kahn
• 1983: ARPANET switches on TCP/IP
• 1986: Congestion collapse
• 1988: Congestion control for TCP
“Congestion avoidance and control”, Van Jacobson
“A Brief History of the Internet”, the Internet Society
TCP
bandwidth [0-100 kB/sec]
if (seqno > _last_acked) {
if (!_in_fast_recovery) {
_last_acked = seqno;
_dupacks = 0;
inflate_window();
send_packets(now);
_last_sent_time = now;
return;
}
if (seqno < _recover) {
uint32_t new_data = seqno - _last_acked;
_last_acked = seqno;
if (new_data < _cwnd) _cwnd -= new_data; else _cwnd=0;
_cwnd += _mss;
retransmit_packet(now);
send_packets(now);
return;
}
uint32_t flightsize = _highest_sent - seqno;
_cwnd = min(_ssthresh, flightsize + _mss);
_last_acked = seqno;
_dupacks = 0;
_in_fast_recovery = false;
send_packets(now);
return;
}
if (_in_fast_recovery) {
_cwnd += _mss;
send_packets(now);
return;
}
_dupacks++;
if (_dupacks!=3) {
send_packets(now);
return;
}
_ssthresh = max(_cwnd/2, (uint32_t)(2 * _mss));
retransmit_packet(now);
_cwnd = _ssthresh + 3 * _mss;
_in_fast_recovery = true;
_recover = _highest_sent;
}
time [0-8 sec]
How TCP shares capacity
individual
flow
bandwidths
available
bandwidth
sum of flow
bandwidths
time
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
Random Walks, Electrical Networks
j
rij
i
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
• Kakutani (1945)
• Consider a particle
performing a random
walk on a network
• From node i it jumps
to neighbouring node j
at rate 1/rij
Random Walks, Electrical Networks
node 1
Vi
node 0
• Let Vi be the probability
that, starting at i, the
particle hits node 1 before
it hits node 0
• Let Iij=(Vj-Vi)/rij
Random Walks, Electrical Networks
node 1
• Let Vi be the probability
that, starting at i, the
particle hits node 1 before
it hits node 0
• Let Iij=(Vj-Vi)/rij
• Then Vi are the potentials
resistance rij and I the currents in this
ij
electrical circuit
node 0
Three Levels of Description
• Microscopic:
particle-level rules of motion
• Macroscopic:
Ohm’s law and Kirchhoff’s laws
• Teleological:
Iij are such as to minimize heat dissipation
minimize ½ i,j Iij2 rij over Iij
Macroscopic description
• Consider several TCP flows sharing a single link
• Let RTT be the round-trip time [sec]
Let x be the mean bandwidth of a flow [pkts/sec]
Let y be the total bandwidth of all flows [pkts/sec]
Let C be the total available capacity [pkts/sec]
• The total fraction of packets that are lost is
p = (y-C)+/y
• The TCP algorithm achieves
average increase in rate = average decrease in rate
1/RTT2 = (p x) x/2
Teleological description
U(x)
• Consider several TCP flows sharing a single link
• Let RTT be the round-trip time [sec]
Let xr be the mean bandwidth of flow r [pkts/sec]
Let y be the total bandwidth of all flows [pkts/sec]
Let C be the total available capacity [pkts/sec]
• TCP and the network act so as to solve
maximise r U(xr) - (y - C log y/C-1)+
over xr where y=r xr
x
Teleological description
U(x)
• Consider several TCP flows sharing a single link
• Let RTT be the round-trip time [sec]
Let xr be the mean bandwidth of flow r [pkts/sec]
Let y be the total bandwidth of all flows [pkts/sec]
Let C be the total available capacity [pkts/sec]
• TCP and the network act so as to solve
maximise r U(xr) - (y - C log y/C-1)+
over xr where y=r xr
severe penalty for
allocating too little
bandwidth
little extra valued
attached to highbandwidth flows
x
Teleological description
U(x)
• Consider several TCP flows sharing a single link
• Let RTT be the round-trip time [sec]
Let xr be the mean bandwidth of flow r [pkts/sec]
Let y be the total bandwidth of all flows [pkts/sec]
Let C be the total available capacity [pkts/sec]
• TCP and the network act so as to solve
maximise r U(xr) - (y - C log y/C-1)+
over xr where y=r xr
small RTT
large RTT
x
Teleological description
• Consider several TCP flows sharing a single link
• Let RTT be the round-trip time [sec]
Let xr be the mean bandwidth of flow r [pkts/sec]
Let y be the total bandwidth of all flows [pkts/sec]
Let C be the total available capacity [pkts/sec]
• TCP and the network act so as to solve
maximise r U(xr) - (y - C log y/C-1)+
over xr where y=r xr
U(x)
no penalty
until y>C
i.e. the link is
overloaded
x
Teleological description
Is this what we want the Internet to optimize?
Does it make good use of the network?
Can it deliver high bandwidth?
Is it a fair allocation?
Can we design a better allocation?
U(x)
•
•
•
•
•
x
Stability of TCP
• TCP was designed to prevent congestion
collapse. How well does it work?
• A more detailed macroscopic model for
TCP is
• Is this dynamical system stable?
How fast does it converge?
Ongoing work
• Kelly (Cambridge statslab)
• Vinnicombe (Cambridge engineering)
proposed+analysed a good macro model
• Tom Kelly (CERN)
implemented it in Linux: ScalableTCP
• Raina (Cambridge management science)
analysed stability & instability
• Wischik (UCL computer science)
micro/macro models for the link:
how big should buffers be?
Ongoing work
• Low, Doyle (Caltech electrical engineering)
Proposed further micro/macro models, FAST TCP
• Cottrell (SLAC)
Testbed for TCP variants
• Srikant (UIUC electrical/computer engineering)
Towsley (UMass computer science)
Fluid model analysis
• Baccelli (ENS mathematics)
Marsan (Turin electrical engineering)
Mean field limit theory for TCP