Packet Switching
Paul Baran wrote eleven memoranda for RAND in August 1964 describing what he called a Distributed Adaptive Message Block Network. The argument for cutting a message into pieces that find their own way is not elegance: it is that a network built this way keeps working after most of it has been destroyed, and he showed it with a number. This page recomputes that number. Three hundred and twenty-four stations, each one destroyed with a probability you choose, and the measure is his: not how many are left standing, but how many are left standing and still in contact with the largest group of survivors.
Cut the message up, and losing the network stops mattering
1 The array, and how many links it is given
Three hundred and twenty-four stations in an eighteen by eighteen array, which is the model Baran's own memorandum used. The redundancy level is how many links each station gets: level two is the plain grid, and every level above it adds more ways round.
2 The attack, station by station
Now destroy stations. Each one independently, with the same probability, which is what Baran's curves vary along their bottom axis. An empty square is a station that is gone.
3 The largest group still in contact, against the best that could survive
Standing is not the same as talking. Baran's criterion counts only the stations that survived and are still in electrical connection with the largest single group of survivors: a filled square is in that group, an outlined one survived the attack and has been cut off from it. The best that could possibly survive is the fraction not destroyed, and the gap between that line and the filled squares is what the network cost you.
4 Sweeping the redundancy level, which is where three or four comes from
The same attack run at every redundancy level, averaged over a fixed number of trials from a fixed seed. This table is computed in this browser; the spread column is how far the answer moves between seeds, printed because an average with no spread beside it claims a precision it has not got.
| level | links per station | survivability | spread | of the best possible |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it. The expected values are read out of Baran's memorandum, which is cited below and archived.
| claim | held | measured |
|---|---|---|
| The array is the one the memorandum used: eighteen by eighteen, 324 stations | yes | 18 by 18, 324 stations |
| Destroying each station with probability one half leaves about half of them standing | yes | measured 50.0%, and the memorandum's example says 50% |
| At the plain grid, less than half of what survives is still in contact | yes | level 2 keeps 14.7% in contact out of 50.0% left standing |
| Three or four times the minimum span is where that stops being true | yes | level 2: 14.7%, level 3: 28.6%, level 4: 44.1% |
| And more redundancy than that buys very little | yes | 4 to 8 adds 5.8 points; 2 to 4 adds 29.5 |
| Over 1000 trials the answer moves less than one point between seeds | yes | four seeds gave 28.6, 28.2, 28.2, 28.1; the spread is 0.47 points |
What is real here, and what is not
This is a Monte Carlo, and it says so
The Middle Square one page over is a census: every seed there is, counted. This is not. An attack is random, so every number here is an average over a fixed number of trials from a fixed seed, and the page prints the spread it measured rather than one figure. At ten trials the answer moves further between seeds than the gap between two redundancy levels, which would make the whole comparison meaningless; at the count this page uses it moves by less than half a point, and the checks say so. Baran's own curves are simulation too, and the page says that rather than implying he proved it.
Redundancy level is implemented from Baran's sentence, not from his picture
His Figure 2 defines levels 1, 1½, 2, 3, 4, 6 and 8 as diagrams. Reading pixels off a scan would be a guess wearing a citation. He also writes the equivalence in words, that redundancy level is the link-to-node ratio in an infinite array of stations, and that is what this implements. A finite 18 by 18 array has edges, so the ratio comes out below the level it is built for; the page prints the ratio it actually got beside the level it was aiming at rather than hiding the difference.
Survivability is the largest connected group, which is smaller than the survivors
Baran's criterion is the percentage of stations both surviving the attack and remaining in electrical connection with the largest single group of surviving stations. Counting stations left standing would be an easier and much kinder number. The page uses his.
Nothing here routes anything
There are no packets in this simulation. No message is cut up, no node forwards anything, there is no queue and no hot-potato heuristic, all of which Baran describes and none of which this page models. What it computes is the property that makes routing worth doing: whether a path exists at all after most of the network is gone. Saying so matters because the page is called Packet Switching.
Putting the pieces back in order is a different machine
Cutting a message into pieces that find their own way is this page. Reassembling them, detecting the gap and asking again is Sequence Numbers, which is on the roster and not built. The seam is deliberate and neither page should absorb the other.
Baran did not call them packets
The word is Donald Davies's, at the National Physical Laboratory in England, and it is the word that survived. Baran's eleven RAND memoranda are about a Distributed Adaptive Message Block Network and say message block throughout; the phrase packet switching appears nowhere in the volume this page cites. The page uses the modern word in its title because that is what the subject is called now, and says whose word it is. The year Davies coined it is not stated here, because the only document read for this page is Baran's and it cannot support a date for somebody else's work.
No sound
Nothing here has a duration.
Sources
- Paul Baran, On Distributed Communications: I. Introduction to Distributed Communications Networks, RAND Memorandum RM-3420-PR, August 1964. Read for this page: the survivability criterion, the eighteen by eighteen array of 324 nodes, the best possible line, the equivalence between redundancy level and link-to-node ratio, and the sentence about three or four times the minimum span network.
- Logical Art, the studio this belongs to.