Slow Start
There is no field anywhere in TCP for how fast you may send. No router tells you, and in the algorithm of 1988 modelled here the only thing the network ever reports is that something was lost, which arrives a round trip after the damage. So the sender finds out by pushing until it hurts. Slow start is not slow: it opens exponentially rather than jumping straight to a large window, which is how it finds the ceiling quickly without arriving at it all at once.
New to a network with no speed limit posted? Start here
Nothing tells a sender how fast it may send. There is no field for it, no handshake that states it, and the answer changes minute to minute as other traffic comes and goes.
So the sender has to find out by trying, and the only signal it gets back is loss: send too much and packets are dropped. This page is about probing upwards fast enough to be useful and backing off fast enough not to make the problem worse.
A message that takes time and may not arrive
Two computers in one room are far apart by a processor's standards. A message crossing between them takes time you cannot argue with, and across a continent that floor is set by the speed of light in glass.
Worse, it may arrive after a message sent later, or arrive twice, or never arrive at all, and the sender is not told which. There is no moment at which both ends know the same thing. Every machine in this topic is a way of getting useful work done anyway, without that guarantee, and the ones that look overcomplicated are usually the ones that stopped pretending.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Doubling, loss, collapse, and climbing back a segment at a time
1 One segment, then two, then four
The window is how much may be in flight at once. It opens at one segment and doubles every round trip, so it reaches a thousand in ten of them rather than a thousand.
| rtt | window | sent | arrived | phase |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | slow start |
| 2 | 2 | 2 | 2 | slow start |
| 3 | 4 | 4 | 4 | slow start |
| 4 | 8 | 8 | 8 | slow start |
| 5 | 16 | 16 | 16 | slow start |
| 6 | 32 | 32 | 24 | lost a segment |
| 7 | 1 | 1 | 1 | slow start |
| 8 | 2 | 2 | 2 | slow start |
| 9 | 4 | 4 | 4 | slow start |
| 10 | 8 | 8 | 8 | slow start |
| 11 | 16 | 16 | 16 | congestion avoidance |
| 12 | 17 | 17 | 17 | congestion avoidance |
| 13 | 18 | 18 | 18 | congestion avoidance |
| 14 | 19 | 19 | 19 | congestion avoidance |
| 15 | 20 | 20 | 20 | congestion avoidance |
| 16 | 21 | 21 | 21 | congestion avoidance |
| 17 | 22 | 22 | 22 | congestion avoidance |
| 18 | 23 | 23 | 23 | congestion avoidance |
| 19 | 24 | 24 | 24 | congestion avoidance |
| 20 | 25 | 25 | 24 | lost a segment |
2 The window growing until something is dropped
Nothing announces the limit. The window keeps doubling straight past what the path can carry, and the first the sender knows of it is a segment that does not arrive.
- the widest the window got
- 32 segments
- the round trip that first lost something
- round trip 6
3 Loss, which is the only signal the network ever sends back
For this algorithm loss is the entire feedback channel. Not a rate, not a warning, not a number: one bit of information, arriving a round trip late, meaning you have already gone too far. Modern TCP can also be told directly, by a router marking a packet instead of dropping it, which is what explicit congestion notification is for.
- round trips that lost a segment
- 2
- where it now stops doubling
- 16 segments
4 Back off, and probe again from there
So it halves what it believes the limit is, restarts at one segment, and doubles back up to that belief before switching to one extra segment per round trip. The sawtooth in the table above is the shape of never being told.
- segments delivered
- 274
- what a sender who knew would have carried
- 480
- efficiency
- 57 per cent
Over 20 round trips this carried 274 segments where a sender who simply knew the answer would have carried 480. The missing 43 per cent is the cost of there being nothing in the protocol that tells you, and of the only signal arriving a round trip after it was needed.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| in slow start the window doubles every round trip, not every segment | yes | 9 of 9 slow-start rounds are followed by twice the window |
| one loss takes the window to 1, whatever it had climbed to | yes | the window was 32 at round 6 and 1 at the next |
| the threshold halves rather than resetting, so the second climb stops sooner than the first | yes | from 64 to 16 after a window of 32 |
| past the threshold it is one more segment per round trip, not a doubling | yes | 9 of 9 avoidance rounds add exactly one |
| having to find the capacity costs 42.9 per cent of what simply knowing it would have carried | yes | 274 segments against 480, and a sender that knew the answer would send capacity every round |
| every loss is discovered by overshooting: all 2 sent more than the path could carry | yes | 2 of 2 overshot, the largest by 8 segments |
What is real here, and what is not
This is the 1988 behaviour, and TCP has not stood still
A loss here halves the threshold and drops the window to one, which is the original algorithm and is brutal. Fast retransmit and fast recovery, added within a few years, let a sender that loses one segment keep going at half rate instead of starting over. Modern stacks start at ten segments rather than one, and several no longer treat loss as the only signal at all.
The path is a single number and real ones are not
One capacity, constant for the whole run, and a loss exactly when the window exceeds it. A real path shares a queue with everybody else's traffic, its capacity moves, and loss can happen for reasons that have nothing to do with congestion, which is exactly why treating loss as congestion goes wrong on a lossy wireless link.
Round trips are the clock here, and time is not modelled
Everything is counted in round trips rather than seconds, because that is the unit the algorithm actually works in. It does mean the page cannot show the thing that makes slow start painful in practice, which is that a short connection may finish before the window ever opens.