Comments on Dr. Leonard Kleinrock's claim to be "the Father of Modern Data Networking"
Success has many fathers, while failure is an orphan - unknown
“The ARPANET Sourcebook” edited by Peter Salus was published in 2008. It is an excellent compendium of little-known documents that underlie modern data networking. It also includes forwards by a few people who could provide context for these old documents. One of the forwards was written by Dr. Leonard (Len) Kleinrock of UCLA, and in his forward (page 94) he repeats his bizarre claim to be "often referred to as the Father of Modern Data Networking."
There is no doubt that Len Kleinrock is a very smart guy, and there is no doubt that he spent time talking to his close friend Dr Lawrence (Larry) Roberts about the network ARPA’s Dr. Robert Taylor hired Larry to build. Indeed, in 2000 the IEEE presented its first Internet Award jointly to Paul Baran, Donald W. Davies, Leonard Kleinrock and Lawrence Roberts “For their early, preeminent contributions in conceiving, analyzing and demonstrating packet-switching networks, the foundation technology of the Internet.” But Len's claim to being the father of networking go so far beyond his actual role (which was mathematical and experimental analysis of networks) as to be ludicrous. Paul Baran invented the concepts of small packets and independent routes for each packet in a study for the US military. Donald Davies built a laboratory model packet network at the British National Physical Laboratory (NPL) and experimented with it; he also created the name "packet switching". Larry Roberts oversaw the construction of ARPANET, the first packet switched network providing real service to actual users.
The danger is that by relentlessly publishing, in every possible place, his claims to having invented it all Len Kleinrock will be successful in confusing historians of the technology about his own role and the critical roles of others. Because I would like the historical record to be as accurate as possible, in 2009 I checked my memory of the events of the 1970’s against a variety of sources. These comments are the result of my study.
There is an article written by Donald Davies and published in The Computer Journal [Volume 44, Number 3, 2001; Willis H. Ware: Introduction to Davies' Paper, pg 151; Donald W. Davies: An Historical Study of the Beginnings of Packet Switching, pp 152-162]. In the article Donald reviews the publications by Roberts and by Kleinrock from the 1970-1978 period looking for evidence that Kleinrock had the influence that he and Roberts began to claim during the 1990’s. There is zero evidence, which seems odd if the influence was so great. [The Davies article may be obtained from The Computer Journal for a fee. I have asked for the right to purchase a web distribution license for this paper but my request has been turned down.] My own review of the literature agrees with Donald’s findings.
In addition, a movie not cited by Davies was made in 1972 with ARPA funding; Roberts and and Dr. Robert Kahn (also well acquainted with Len and his work) were extensively involved in the creation of this movie. [As I recall, they expected the movie to be completed by October 1972 and to be shown continuously at the ICCC in connection with the ARPANET demo, but the movie was not completed in time for this use and a slide show put together by Bob Kahn and Al Vezza was used instead.] You can find a copy at Computer Networks: The Heralds of Resourch Sharing. Len Kleinrock does not appear at all in this movie, although Paul Baran, Donald Davies, and Larry Roberts are all on camera. If Kleinrock were as influential as he and Roberts now claim, how did it happen that not only does he not make an appearance but is not even mentioned by anyone?
Donald Davies also analyzed Kleinrock’s 1964 book Communication Nets - Stochastic Message Flow and Delay in Davies’ 2001 article. This book is a slightly revised version of Kleinrock’s PhD thesis. The thesis proposal, the thesis, and the 1964 book are cited by Roberts and Kleinrock as substantiation of the claim that Kleinrock originated packet switching. Davies’ analysis of the 1964 book shows that there is nothing in the book to substantiate the claim. However, I recognize that Davies is not a disinterested party in the debate (for my own background follow the link to my name under the title of these comments), and rather than rely on his analysis, I purchased a 2007 reprint (by Dover Publications) of the book and have read it from cover to cover to make my own analysis. I find Davies’ analysis to be accurate, and in addition I have several comments of my own. Kleinrock wrote a new preface for the 2007 Dover Edition; annotated copies of the entire preface and several relevant pages from the book accompany these comments– my analysis focuses on the text in those pages, although I also use short quotations from other parts of the book.
However, before commenting on those pages, I would like to review several of the reasons why the switching of packets is superior to the switching of messages, to make a clear distinction between the technology used in the ARPANET and other packet networks, and the message switching network analyzed by Kleinrock in his 1964 book. As Davies said in his 2001 article: "The 1964 book has been said by Kleinrock to contain the essence of his thesis results. By using the book to evaluate his contribution to the concept of packet switching we shall not do him an injustice, because clearly any new work after the thesis which he considered significant for the understanding of network behaviour [sic] will have been incorporated in the book."
Now let's look at some of the claims Kleinrock makes in his Preface to the 2007 Dover Edition of the 1964 book. This Preface is on pages vii-xi, with reference numbers/letters which are keyed to my comments added. [If you click on the this link a new window/tab will be created with the complete text of what I am commenting on. In addition, the specific quote on which I am commenting is incorporated into the text; the first is immediately below.]
There is no doubt that Len Kleinrock is a very smart guy, and there is no doubt that he spent time talking to his close friend Dr Lawrence (Larry) Roberts about the network ARPA’s Dr. Robert Taylor hired Larry to build. Indeed, in 2000 the IEEE presented its first Internet Award jointly to Paul Baran, Donald W. Davies, Leonard Kleinrock and Lawrence Roberts “For their early, preeminent contributions in conceiving, analyzing and demonstrating packet-switching networks, the foundation technology of the Internet.” But Len's claim to being the father of networking go so far beyond his actual role (which was mathematical and experimental analysis of networks) as to be ludicrous. Paul Baran invented the concepts of small packets and independent routes for each packet in a study for the US military. Donald Davies built a laboratory model packet network at the British National Physical Laboratory (NPL) and experimented with it; he also created the name "packet switching". Larry Roberts oversaw the construction of ARPANET, the first packet switched network providing real service to actual users.
The danger is that by relentlessly publishing, in every possible place, his claims to having invented it all Len Kleinrock will be successful in confusing historians of the technology about his own role and the critical roles of others. Because I would like the historical record to be as accurate as possible, in 2009 I checked my memory of the events of the 1970’s against a variety of sources. These comments are the result of my study.
There is an article written by Donald Davies and published in The Computer Journal [Volume 44, Number 3, 2001; Willis H. Ware: Introduction to Davies' Paper, pg 151; Donald W. Davies: An Historical Study of the Beginnings of Packet Switching, pp 152-162]. In the article Donald reviews the publications by Roberts and by Kleinrock from the 1970-1978 period looking for evidence that Kleinrock had the influence that he and Roberts began to claim during the 1990’s. There is zero evidence, which seems odd if the influence was so great. [The Davies article may be obtained from The Computer Journal for a fee. I have asked for the right to purchase a web distribution license for this paper but my request has been turned down.] My own review of the literature agrees with Donald’s findings.
In addition, a movie not cited by Davies was made in 1972 with ARPA funding; Roberts and and Dr. Robert Kahn (also well acquainted with Len and his work) were extensively involved in the creation of this movie. [As I recall, they expected the movie to be completed by October 1972 and to be shown continuously at the ICCC in connection with the ARPANET demo, but the movie was not completed in time for this use and a slide show put together by Bob Kahn and Al Vezza was used instead.] You can find a copy at Computer Networks: The Heralds of Resourch Sharing. Len Kleinrock does not appear at all in this movie, although Paul Baran, Donald Davies, and Larry Roberts are all on camera. If Kleinrock were as influential as he and Roberts now claim, how did it happen that not only does he not make an appearance but is not even mentioned by anyone?
Donald Davies also analyzed Kleinrock’s 1964 book Communication Nets - Stochastic Message Flow and Delay in Davies’ 2001 article. This book is a slightly revised version of Kleinrock’s PhD thesis. The thesis proposal, the thesis, and the 1964 book are cited by Roberts and Kleinrock as substantiation of the claim that Kleinrock originated packet switching. Davies’ analysis of the 1964 book shows that there is nothing in the book to substantiate the claim. However, I recognize that Davies is not a disinterested party in the debate (for my own background follow the link to my name under the title of these comments), and rather than rely on his analysis, I purchased a 2007 reprint (by Dover Publications) of the book and have read it from cover to cover to make my own analysis. I find Davies’ analysis to be accurate, and in addition I have several comments of my own. Kleinrock wrote a new preface for the 2007 Dover Edition; annotated copies of the entire preface and several relevant pages from the book accompany these comments– my analysis focuses on the text in those pages, although I also use short quotations from other parts of the book.
However, before commenting on those pages, I would like to review several of the reasons why the switching of packets is superior to the switching of messages, to make a clear distinction between the technology used in the ARPANET and other packet networks, and the message switching network analyzed by Kleinrock in his 1964 book. As Davies said in his 2001 article: "The 1964 book has been said by Kleinrock to contain the essence of his thesis results. By using the book to evaluate his contribution to the concept of packet switching we shall not do him an injustice, because clearly any new work after the thesis which he considered significant for the understanding of network behaviour [sic] will have been incorporated in the book."
- If a unit of transmitted data must be completely received at an intermediate node, and the checksum confirmed, before being forwarded to the next node, then breaking a long message into several short packets reduces the end-to-end transmission delay. Imagine an 8000-bit message being sent down an 8000 bps link. If the message is not broken into packets, it will not be completely received and the checksum verified for a full second. If it is broken into 1000-bit packets at the source, the first packet will be completely received and ready for forwarding after only 1/8 second. The effect of this is magnified for each additional intermediate node. There is nothing in the 1964 book which discusses this effect.
- At the time the ARPANET and the NPL network were designed and built, it was generally accepted that bit errors on standard long-distance communication circuits would be "bursty". That is, a large number of bits would be transmitted without error and then several bits close together would all be in error. (I don't know for sure if this was true then or if it is true now, but it is what everyone believed. See, for example, Roberts' comment on the ARPANET checksum - page 546, bottom left paragraph, of his 1970 SJCC paper.) By breaking "long" messages into "short" packets, the quantity of information that would need to be retransmitted after an error burst would be "short" rather than "long", leading to reduced transmission delay and increased network capacity. This is an engineering consideration. The 1964 book considered only error-free networks, so there was no reason to come up with this idea, and Kleinrock indeed makes no mention of it.
- The ARPANET was expected to have a bimodal traffic distribution, with most messages either quite short or quite long. It was envisioned that the short messages would be interactive traffic for which minimizing delay was most important, whereas long messages would be data transfers for which maximizing throughput was most important. The ARPANET design allowed one bit of "priority" information for each message (e.g. high or low priority). The network designers imagined (or at least allowed for the possibility) that interactive traffic would be marked high priority and data transfer would be marked low priority. [The Host protocol design, however, did not make use of this possibility.] Baran at least hints at the same kind of separation of digitized voice vs. data transfer in his network design. By breaking long messages into packets, there are opportunities at each intermediate queue for high priority messages to "leapfrog" ahead of low priority traffic. The 1964 book comes closest to advocating this reason for packetization in Chapter 5, where Kleinrock analyzes "priority with preemption". (Kleinrock's definition is that "when a preempted message reenters the service facility, its servicing is started at the point at which it was interrupted when the preemption occurred" - pp. 73-74.) However, after mentioning this as a possibility, Kleinrock gives it no importance and goes on to demonstrate that if high priority messages are allowed to go faster, low priority messages will go slower and the average waiting time remains constant. It is impossible to conclude from this discussion that Kleinrock considered this to be an argument for packetization.
Now let's look at some of the claims Kleinrock makes in his Preface to the 2007 Dover Edition of the 1964 book. This Preface is on pages vii-xi, with reference numbers/letters which are keyed to my comments added. [If you click on the this link a new window/tab will be created with the complete text of what I am commenting on. In addition, the specific quote on which I am commenting is incorporated into the text; the first is immediately below.]
In the sentences I have labeled "1" above ( from pg. viii), Kleinrock claims the introduction of queueing theory as the principal tool for analyzing network behavior. So far as I am aware this is an accurate claim, and Kleinrock deserves full credit for making this connection. This is a major contribution and qualifies Kleinrock as one of the many "fathers" of modern data networking.
In the sentences at "2" Kleinrock claims to "introduce distributed design technologies and distributed routing algorithms" key to Internet development. Neither of these things was introduced in the 1964 book; it requires only reading the book to realize this. The only design technology Kleinrock might legitimately claim to introduce is the selection of circuit capacities given a complete and accurate traffic matrix, and a specific network topology. This is certainly not a distributed design technology and, as Kleinrock points out, a traffic matrix is most likely time varying for a real network so his analytic technique will yield results that are rarely optimal. I will address the claim for "distributed routing algorithms" in my discussion of "The key concept of distributed control" below, but I can say here that the claim is clearly incorrect.
At "3" Kleinrock claims to have "introduced the notion of demand access". If by this he means that he created the notion he is clearly wrong; he acknowledges that his analysis is based on an already-existing network design (the Western Union Plan 55A network) which is described in detail on pages 12-14. Obviously, this network was a demand access network pre-existing Kleinrock's thesis analysis. Alternatively, Kleinrock could mean that he introduced the notion of demand access to the queueing theory literature. This is likely to be a correct statement - he was a pioneer - but it has a seriously different meaning than most readers would believe (so different it is hard to believe that the wording is not deliberately misleading).
At "4" Kleinrock claims to have introduced the idea of packetization, and then generalized this to have "anticipated the technology of packet switching". This is utter nonsense; there is NOTHING in the entire 1964 book that suggests, analyzes, or alludes to the idea of packetization. The closest he comes (and its not very close) is the concept of breaking a program into segments of fixed execution time (to be fair, he refers to the programs as "messages", apparently to fit the terminology of the rest of the book) and scheduling these segments for round-robin execution by a time-sharing system. This occurs in Section 5.3, which Kleinrock titled "Time-Shared Service" and describes as a "time-shared service facility". He then shows that the shortest programs will be executed with less delay, but that the average delay for all programs is the same as for first-come-first-served scheduling. Since the idea of packetization is never introduced in the book, the claimed generalization also is not present. The best that can be said of the claims at "4" is that they represent wishful thinking - the extensions of his analysis which he might have made but didn't.
At "5" Kleinrock talks about routing results in his work. His claim to have demonstrated that "random routing" and "distributed alternate routing" allowed a network to adapt to traffic flows different from the specified traffic matrix is correct (for the "random routing" and "alternate routing" [no "distributed"] which he defines). The random routing he describes is equivalent to Baran's "hot potato" (without learning) routing; he shows that it allows adaptation to incorrectly described traffic, incorrect line capacity assignment, and to network link failures, at the cost of severely limiting network capacity and severely increasing average message delay. However, he prefers fixed routing; on page 26 (Summary of Results) he concludes: "A quantitative comparison is made between random and fixed routing procedures for identical nets, demonstrating the superiority of the latter as regards message delay".
Kleinrock also describes, in Chapter 7, the simulation of a routing procedure he calls "alternate routing procedure". Note that the word "distributed" does not appear anywhere in Chapter 7 with reference to "alternate routing". The procedure consists of a table in each switching node listing the possible output circuits to be used for each destination. When the switching node receives a message for destination "j" it runs through the list of circuits for that destination, and sends the message over the first currently-idle circuit from that list; if no circuit is currently idle the message is put on a queue of messages waiting for circuit assignment. Kleinrock points out that "fixed routing" is a special case where each list has only one element. This is a far cry from the ARPANET, where an algorithm distributed among all the IMPs was periodically run over the current state of the network to determine the best path from each switching node to each destination. Kleinrock's use of the phrase "distributed alternate routing" (rather than simply "alternate routing") with reference to his 1964 book is misleading and inappropriate.
Kleinrock also describes, in Chapter 7, the simulation of a routing procedure he calls "alternate routing procedure". Note that the word "distributed" does not appear anywhere in Chapter 7 with reference to "alternate routing". The procedure consists of a table in each switching node listing the possible output circuits to be used for each destination. When the switching node receives a message for destination "j" it runs through the list of circuits for that destination, and sends the message over the first currently-idle circuit from that list; if no circuit is currently idle the message is put on a queue of messages waiting for circuit assignment. Kleinrock points out that "fixed routing" is a special case where each list has only one element. This is a far cry from the ARPANET, where an algorithm distributed among all the IMPs was periodically run over the current state of the network to determine the best path from each switching node to each destination. Kleinrock's use of the phrase "distributed alternate routing" (rather than simply "alternate routing") with reference to his 1964 book is misleading and inappropriate.
At "6" Kleinrock states that there are 3 key concepts that are necessary to successful network technology which are described in the 1964 book and which, by implication, are the foundation of his claim to be the "father of Modern Data Networking". I will comment on each of these concepts separately.
At "7" he discusses "The key concept of demand access." This is a key concept, but it is not Kleinrock's concept. As he acknowledges in the paragraph on page ix: "For sure, early and crude store-and-forward networks based on demand access already existed, but no one had elucidated the principles underlying the need for such structures." In other words, other people had invented and implemented this key concept, but Kleinrock was the first to do the mathematics showing that they had a good idea. I don't see how anyone can believe that Kleinrock's mathematics (applied to an idealized, errorless, unchanging network topology) takes precedence over the implemented networks based on demand access. Kleinrock's claim to precedence for this concept is silly.
At "8" he discusses "The key concept of large shared systems." The result Kleinrock describes in the text under this heading seems self-evident today, but it may not have seemed so in 1961 or 1964. It is certainly true that the mathematics in the 1964 book shows that greater capacity leads to lower delay. Yet what Kleinrock calls "the key concept of large shared systems" in queueing theory is not what most people think of when they hear this term. For example, the value of size as expressed by the saying "you can find anything on the Internet" is related to diversity and ubiquity, not to tradeoffs between capacity and delay. On the other hand, the value of "large shared systems" within the limited context of queueing theory lead to network designs lacking in other desirable characteristics.
For example, at "A" (page 28), Kleinrock notes that the "desirability of a concentrated traffic lead to consideration of a special topology, namely the star net"; this may be great for maximal sharing but is quite poor at robustness (which Kleinrock doesn't deal with in his errorless analysis).
Similarly, at "B" (page 60), queueing theory analysis leads to the conclusion that multi-channel systems are worse than single-channel systems. This is true in terms of capacity and delay when the channels are strictly parallel between the same two points, but argues against alternative routes, which help with robustness. I think Kleinrock's claim to precedence in this area is justifiable only in the sense that he has mathematically demonstrated a result which is not generally intuitive. However, the queueing theory leading to the choice of large shared systems over redundant components is not "key" to successful networking.
At "9" he discusses "The key concept of distributed control." This is a key concept, but it is not Kleinrock's concept. With regard to his text at "2" and "5" I have already commented on his inappropriate use of the word "distributed" to describe his work in 1964. I will amplify on that topic here.
First, we need to define "distributed control". What is generally meant by this term is a set of two or more decision-makers, each making decisions autonomously based on local knowledge of the environment. "Distributed control" in normal usage does not include the case where a single central authority distributes "decision tables" to each of a set of subordinate centers which then slavishly follow these tables until the central authority releases a new set of tables, because if the central authority becomes inoperative there is no control at all. To be "distributed," control cannot rely on any single element.
The 1964 book only considers one type of real-time decision making, namely routing decisions. In the text at "9" the only example of a control decision is in the area of routing. Therefore it is fair to evaluate Kleinrock's precedence in the "concept of distributed control" by what he has to say about routing. There are 3 routing strategies discussed in the book: random routing, alternate routing, and fixed routing.
First, we need to define "distributed control". What is generally meant by this term is a set of two or more decision-makers, each making decisions autonomously based on local knowledge of the environment. "Distributed control" in normal usage does not include the case where a single central authority distributes "decision tables" to each of a set of subordinate centers which then slavishly follow these tables until the central authority releases a new set of tables, because if the central authority becomes inoperative there is no control at all. To be "distributed," control cannot rely on any single element.
The 1964 book only considers one type of real-time decision making, namely routing decisions. In the text at "9" the only example of a control decision is in the area of routing. Therefore it is fair to evaluate Kleinrock's precedence in the "concept of distributed control" by what he has to say about routing. There are 3 routing strategies discussed in the book: random routing, alternate routing, and fixed routing.
Random routing is defined at "C" (page 95); it is a static procedure based on a fixed probability distribution over the set of output lines of a node.
At "D" (pp. 95-95) it is noted that nothing changes even if the network structure changes. This is not "distributed control" according to the definition above because there is no change over time based on changes in the environment. Since nothing ever changes, this is a degenerate case of centrally distributed "decision tables"; the tables are created by the network builder.
Alternate routing is defined at "E" (page 108), and fixed routing is defined as a
special case of alternate routing at "F" (page 109). In each case, the routing information is represented as a set of lists (at "E") or, alternatively, as a matrix (at
"G" - pages 108-109). Nowhere is there a hint that the matrix is other than static, and once again this is not "distributed control" according to the definition above.
Of course, it might be argued that although the 1964 book does not describe procedures for dynamically updating the routing matrix, perhaps this was not written down only because it was beyond the scope of the PhD thesis. However,
Of course, it might be argued that although the 1964 book does not describe procedures for dynamically updating the routing matrix, perhaps this was not written down only because it was beyond the scope of the PhD thesis. However,
at "H" (page 96), while discussing random routing, Kleinrock recognizes the possibility of dynamically updating routing information and specifically argues AGAINST it, on the grounds that in times of rapid change "the network might easily become flooded with directory information alone, thus leaving no transmission capability for message traffic."
To summarize: The only element of "control" considered in the 1964 book is routing, and none of the three routing mechanisms discussed includes any mechanism for dynamically reacting to network changes by either centralized or distributed means, but instead are each "wired in" at the time the network is constructed. Indeed, the concept of dynamic change to routing information is dismissed as a bad idea. Under the common understanding of the meaning of "distributed control" there is no hint of distributed control in the book. Therefore, we must conclude that Kleinrock's claim to precedence for this concept is not supported by the evidence.
To summarize: The only element of "control" considered in the 1964 book is routing, and none of the three routing mechanisms discussed includes any mechanism for dynamically reacting to network changes by either centralized or distributed means, but instead are each "wired in" at the time the network is constructed. Indeed, the concept of dynamic change to routing information is dismissed as a bad idea. Under the common understanding of the meaning of "distributed control" there is no hint of distributed control in the book. Therefore, we must conclude that Kleinrock's claim to precedence for this concept is not supported by the evidence.
Dr. Kleinrock played an important role in the analysis and measurement of the ARPANET. He was also a close friend of Dr. Roberts throughout the 1960’s and had a detailed understanding of the application of queueing theory to networks. It is quite possible that during private discussion of network concepts with Roberts in 1967 and 1968 he played a greater role than the documentation of that time allows us to know for certain. We undoubtedly should give the 1990’s recollections of Drs. Roberts and Kleinrock the benefit of the doubt. But it is just not correct to say that the 1964 book (or the previous thesis) by Kleinrock substantiates his claims to precedence for inventing packetization, demand access, distributed control or distributed routing algorithms, or that his analysis of large shared systems was of major importance to the creation of ARPANET or the Internet. His claim to be “the father of Modern Data Networking” is puffery, not fact.
