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, and only that number: nothing here is cut into packets and no station forwards anything, because the claim being checked is the one underneath routing rather than routing itself. Whether a path survives at all is what decides whether there is anything to route. 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.
New to networks? Start here
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.
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 Baran’s link-to-node ratio, which is half the number of links each station gets, because every link is shared by the two stations at its ends. Level two is the plain grid, where each station has four neighbours, and every level above it adds more ways round. The ratio each level actually produces in a finite eighteen by eighteen array is measured and printed below rather than assumed.
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 |
5 Routing: a node that is never told the shape of the network learns the way to everywhere by watching traffic arrive
Everything above asks whether a path survives. This asks whether the network can find it, on the seven-by-seven array Boehm simulated in the second memorandum rather than the eighteen-by-eighteen one Baran measured in the first. No node here is ever told the shape of the network. Each keeps a table of the fewest hops a message from each station has taken to reach it, over each link, and routes toward a station by the link whose entry for that station is lowest. The table is filled by traffic arriving from somewhere and read to send traffic to it.
- table total
- 91,110, 1.63 times the floor
- the floor it cannot go under
- 55,902
- pairs that arrive
- 600 of 600
- mean hops, against the shortest possible
- 4.38 against 4.07
9,800 wandering messages later the table total is 1.63 times the floor, every one of the 600 pairs arrives, and the mean route is 4.38 hops against a shortest possible 4.07. 77 per cent are shortest. No node was told any of it.
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.
Two arrays on one page, from two memoranda
The survivability stages run on the eighteen by eighteen array of 324 stations, which is the network RM-3420 measures. The routing stage runs on seven by seven, which is the network RM-3103 simulates: Boehm was limited to it by the storage of an IBM 7090, and the page uses it so its numbers stand beside hers rather than beside nothing. Using one array for both would have been tidier and would have meant quietly running her doctrine on a network she never ran it on.
What dummy traffic is here, and what it is in the memorandum
Page 13 says that starting a new network with dummy traffic is desirable if the shortest learning time is wanted, \u201cotherwise, many links that may lie on short paths would never be tested\u201d. It does not say what dummy traffic IS. Here it is a message that wanders at random for thirty hops, learning as it goes, which tests exactly the links a greedy route never picks. The effect she describes is measured on this page; the mechanism is this page\u2019s reading of a sentence, and the difference is worth keeping straight.
Every line is always free, so this shows learning and not congestion
Two of Boehm\u2019s nine constraints are not modelled. A node here accepts every message rather than only when storage is open, and the outgoing link is chosen by the table alone rather than from the lines that are not busy. So there is no queue, no waiting and no choking, and the traffic figures she derives from capacity have no counterpart here. What is left is the part this page is about: what a node knows, and how it came to know it.
A virgin network scores beautifully on the few messages that arrive
With no dummy traffic at all, 539 of 600 pairs never reach their destination, and of the 61 that do, 92 per cent take a shortest path. Seasoned with two hundred rounds every pair arrives and 77 per cent are shortest. The first figure is higher and means nothing, because it is measured on the pairs that happened to work. The page prints the denominator beside every quality figure for that reason.
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.
- Sharla P. Boehm and Paul Baran, On Distributed Communications: II. Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network, RAND Memorandum RM-3103-PR, August 1964. Read here as a scan, which has no text layer. Page 6 states the routing doctrine as nine lettered constraints and four of them are the fifth stage of this page; page 13 defines the table total and says a network learns faster if it is started with dummy traffic; page 5 gives the seven-by-seven array and page 4 the rule that a node in a large array has two links per unit of redundancy level.
- Logical Art, the studio this belongs to.