Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
The Internet

Leonard Kleinrock On The Origins of Packet Switching 137

An Anonymous Coward writes: "From Ben Sullivan's Tech Blog (http://www.techblog.com). An email from Leonard Kleinrock on why he really was the brains behind packet switching. It's a first-hand account from Kleinrock in a blog. A neat little journalistic scoop for bloggers, and some insights for techheads on Internet history."
This discussion has been archived. No new comments can be posted.

Leonard Kleinrock On The Origins of Packet Switching

Comments Filter:
  • "I invented packet switching"

    -Al Gore
    • Re:everyone knows... (Score:2, Informative)

      by Zeinfeld ( 263942 )
      "I invented packet switching" -Al Gore

      It is a shame that the GOP have to pay dweebs to sit in front of computers to repeat lies. Gore never claimed to invent the Internet.

      Gore correctly and truthfully took credit for getting us the money to develop the Internet. He was also very helpful in the development of the Web. The endorsement of the Web by the Whitehouse had a massive effect on commercial use. It was also the final nail in the coffin for 'Interactive TV'.

      Of course if a lie is repeated often enough people will eventually mistake it for the truth. This particular lie was invented because the GOP was frightened of the comparison between Gore who had achieve a lot and their empty suit of whom the best they could say was he would not interfere with his advisers.

      • During the campaign of '00 scheduled debates, when Bush was preaching ridiculously incorrect numbers and Gore proved him wrong, Bush said the following:

        "It appears that Gore has not only invented the internet but the Calculator as well."

        That was a rather witty comeback. Being a president is about having a good sense of humor, eloquence, and people skills. The point I'm trying to make is that you shouldn't take everything too seriously, or whatever.
      • by Anonymous Coward
        Time Magazine, August 18, 1997, Al Gore: ``It was my determined work in the Senate that was responsible for the Internet. I invented it.''

        Al Gore thinks he invented the Internet.

      • Gore correctly and truthfully took credit for getting us the money to develop the Internet.

        Right. I suppose you also believe that President Clinton did not perjure himself because he consciously defined "is" differently than his questioner.

        Let's quote Al Gore...

        "I took the initiative in creating the Internet." I'll grant that he didn't use the word "invent." I'll also suggest this analogy...

        You work 70-hour weeks for a year to develop THE software technology that will rocket your startup into the ranks of the Fortune 500. Your manager goes to the CEO and says "I should be given money and power because I took the initiative in creating this new technology." Did he lie? According to you, no. Did he choose his words carefully so that the uninformed would be led to believe a mistruth? Absolutely.
        • Re:everyone knows... (Score:3, Informative)

          by isdnip ( 49656 )
          In Congress, "initiative" refers to a funding measure. Gore led the charge for the funding for the NSFnet. That was indeed an "initiative". And the NSFnet was *the* major Internet backbone after the ARPAnet and before commercialization.

          Finding a different meaning of a word which doesn't apply is simply obfuscation.
  • From last time (Score:3, Informative)

    by oregon ( 554165 ) on Sunday February 03, 2002 @03:05PM (#2947008) Homepage
    A previous discussion here [slashdot.org].
  • Excerpt from the article:
    "I must emphasize that the totality of understanding the full picture, and not just the issue of packetization (i.e., chopping messages into small pieces) had to be developed before a convincing body of knowledge could be amassed to prove the case for data networks."

    Wow. Maybe this guy would get more credit for his discoveries if he could describe them in English

    • Wow. Maybe this guy would get more credit for his discoveries if he could describe them in English
      Kleinrock's discoveries are described mainly in mathematics. Like:
      w(t) = ì(1 - ó) exp(-ì(1 - ó)t)
      (sorry for the way that looks through HTML)
  • I think I now understand why Davies was so hung up on the issue. He had developed a one-node packet switch in the UK before the ARPANET was deployed. Unfortunately, the UK would not provide enough financial support to Davies so that he could expand his one-node switch into an operational network. Had they done so, the Internet might have been born in the UK; instead his work was stalled and could not go forward. This must have been very frustrating for him.

    That would have been interesting. Britain as the home of the Internet.

    The possibilities of an alternate history are fascinating.

    In any case some of it is a matter of research being done in parallel, which means that these sort of debates will take place as a matter of course.

  • I'm rather surprised that anyone on /. is willing to seriously consider any of these claims to have "invented" packet switching.

    Every other time that someone has claimed to have "invented" an obvious electronic analogue of a well-established mechanism, we've laughed; why is this any different? Packet switching has been used in the (snail) mail system for over a century.
    • How do you figure that? If it was used in the snail mail system it would mean writing one word on a sheet of paper placing that in an envelope, numbering the letter, mialing it, then repeating the process until the letter is complete. And I don't know of anybody who sends mail this way.
      • Do IP packets only contain a single byte payload?

        I've known a number of people to send two postcards because what they want to write doesn't fit on one; and they helpfully write "continued on next postcard", exactly the way that IP fragments do. And, somewhat rarer but an even closer analogue, when there has been a weight limit on lettermail, people have sent (for example) the first five pages of a long letter in one envelope, and the last three pages in a second envelope.

        And then there's all the furniture which is shipped in parts for the recipient to assemble...
      • by Tony-A ( 29931 )
        Multi-volume set, sent a volume at a time.
        Multi-chapter book, sent a chapter at a time.
        Newspaper serials, sent a column at a time.
        I'm sure somebody has sent a longer missive, written on the back of postcards.
    • This is an excellent point. Packet switching really is an obvious idea, it is just the postal system done electronically. Watching these computer scientists squabble over these crumbs of creativity is embarrasing.

  • Hogwash to the lot of them.... The ideas they call packet switching were clearly being used by the Romans, the only difference was the transport involved people and horses not electrical signals but the transport if totally irrelevant to all the concepts they claim are packet switching. Odds are good it was used well before the Romans.
  • That is what Metcafe says.
  • His own webpage (Score:3, Informative)

    by leiz ( 35205 ) <leizNO@SPAMjuno.com> on Sunday February 03, 2002 @03:53PM (#2947166)
    He has his very own webpage [ucla.edu] with information about the early days of the internet as well as his accomplishments.
  • US Law (Score:3, Insightful)

    by glowingspleen ( 180814 ) on Sunday February 03, 2002 @04:03PM (#2947201) Homepage
    Whoever owns the patent, wins. Even that guy who said "Let's Roll"'s family lost their right to the phrase b/c someone quickly patented it.
    • Actually, that's not true.

      In the USA, the law is "first to invent" not "first to file".

      This means that if you invent something, but don't file until after someone else does, and your invention date is prior to the invention date of the first filer, and you can prove it (with lab notebooks, witnesses, etc.), you win.

      There are limitations on this -- you can't have publicly disclosed the invention more than one year before filing, for example, nor can you invent something and sit on it indefinitely without filing unless you are "actively developing" it.

      In other countries, "first to file" is typically the rule.

      (note, I am not a lawyer, so don't rely on this and sue me later!)
  • From avi freedman's homepage: [freedman.net] the Freedman doc [netaxs.com] - info on multihoming and BGP.
  • For the common folk who no longer read the finely honed tribal rhetoric of bickering academicians this isn't about objective reporting so much as it's about jockeying for position in the ivory tower world of publish or perish.
  • by Aztech ( 240868 ) on Sunday February 03, 2002 @04:58PM (#2947423)
    Donald Davies [slashdot.org] is largely acknowledged for developing Packet Switching (and even coining that very phrase) at the National Physical Laboratory in the UK, however he was not American so he's largely ignored.
    • Read the damn article! It is entirely a discussion about why Kleinrock believes it was not Davies, but he, who invented packet-switching.
    • Donald Davies is largely acknowledged for developing Packet Switching (and even coining that very phrase) at the National Physical Laboratory in the UK, however he was not American so he's largely ignored.

      The article covers Davies' involvement. Kleinrock repeats again and again that there is cold hard evidence that he created packet switching before Davies (in his dissertation). This has nothing to do with whether Davies is around to defend himself or not. You really should have read the article.
    • The commercial uptake of packet switching in the UK was slow though. The General Post Office who used to run all forms of communications in the UK from letters through to telephones (probably including carrier pidgeons) quite liked selling fixed lines.

      the early nets did exist in the seventies, but these were research institutions and universities running on top of GPO leased circuits. They were vital for research infrastructure, but there wasn't much interest from other sources with deeper pockets, i.e., the military or commercial interests. The GPO eventially got some of the research switches rebuilt as products by GEC and it launched EPSS (Experimental Packet Switched Service) in the mid seventies.

      The commercial PSS net didn't start until later. A lot of the early X.25 work was done in the UK and by that time other interests were getting involved, but now we are talking about the late seventies.

      Effectively, the UK was running almost ten years behind the UK by then. Many companies started moving to X.25 nets but the initiative had been lost. I guess if defence interests had got interested in the technology, thst would have given it a financial boost.

      Davies, though was not just an expert on packet switched networks, he also had quite a lot to do with computer security. Perhaps he didn't 'discover' PSS, but he certainly contributed a lot there as well as in other areas.

    • And I am widely acknowledged as the King of America.

      Come on, read the article, find a flaw in his statements, and refute them. Kleinrock states that he analyzed packet switching mathematically in his 1962 thesis, something that Davies never did. Is he overstating? Does Davies have a publication that predates this? Did he develop/discover independently and then parlay that into the current technology? The latter would be a particularly cunning argument, if you can support it. But don't tell us "Oh, everybody says ..." because it makes you sound like an idiot rather than an informed individual. And don't mind me, I'm just a normal largely ignorant slashdotizen.
      • The 1962 paper is interesting, which incidentally wasn't published until 1964, people generally go by the date of publication not when they inked the first paragraph. Surprsingly the above paper doesn't mention the word 'packet' once, which is a bit of a contradiction if you claim to have invented 'packet switching'.

        The first instance of "Packet" and '"acket Switching" was in Davies' 1967 paper "A digital Communications Network for Computers", which was presented at a conference in Tennessee, at the same conference Lawrence Roberts of ARPA presented a design for creating a computer network. He had also made presentations before ARPA a year before on the concepts of 'packet switching'.
        • The first instance of "Packet" and '"acket Switching" was in Davies' 1967 paper "A digital Communications Network for Computers"

          Again, something mentioned in the article. It has a link. It's okay for you to read it. There must be innumerable inventions that did not have a popular name until much later after they were invented.

        • The 1962 paper is interesting...Surprsingly the above paper doesn't mention the word 'packet' once, which is a bit of a contradiction if you claim to have invented 'packet switching'

          He credits Davies with coining the term "packet switching." You seem to be saying that if you don't use the currently popular name when you first describe your idea, then you're not the originator of the idea...the guy who thinks up the popular name is the inventor.

          By your reasoning, Newton, who coined the term "calculus" should get all the credit for the development of that branch of mathematics, and Leibniz should get none, since the German-speaking Leibniz didn't use the term "calculus." (In case you're not up on your history of mathematics, Leibniz independently co-developed calculus and is credited in many non-English speaking countries as the developer of that branch of mathematics.)

          Your rhetorical skills are sorely lacking. First Davies is the inventor because everyone knows he is, and now he's the inventor because he was the first to name it by the name you know it by. Here's my question:

          What's your evidence for your belief that Davies either developed the concepts prior to Kleinrock, did more significant development work than Kleinrock, or for some other reason has a stronger term to the title "Inventor of Packet Switchng"?

          My position is that the title is about as valid as "Inventor of the World Wide Web" and that all these guys should take a lesson from Newton..."If I have seen farther than others, it is because I am standing on the shoulders of giants...
    • ...he was not American so he's largely ignored


      ... his MG broke down on the way to the patent office.

      ... he tried to phone it in over BT

      ... his design called for packets to travel on the left side of the Net
  • Packet switching refers to protocols in which messages are divided into packets before they are sent. Each packet is then transmitted individually and can even follow different routes to its destination. Once all the packets forming a message arrive at the destination, they are recompiled into the original message.

    Most modern Wide Area Network (WAN) protocols, including TCP/IP, X.25, and Frame Relay, are based on packet-switching technologies. In contrast, normal telephone service is based on a circuit-switching technology, in which a dedicated line is allocated for transmission between two parties. Circuit-switching is ideal when data must be transmitted quickly and must arrive in the same order in which it's sent. This is the case with most real-time data, such as live audio and video. Packet switching is more efficient and robust for data that can withstand some delays in transmission, such as e-mail messages and Web pages.

    A new technology, ATM, attempts to combine the best of both worlds -- the guaranteed delivery of circuit-switched networks and the robustness and efficiency of packet-switching networks.
    ...courtesy of Webopedia [webopedia.com]

    • by Anonymous Coward
      ..please post at least up-to-date and correct information.
      Bbbbrrrr, calling ATM "a new technology".
  • Bill Gates, of course. Just ask him.
  • Although they're forgotten today, there were many pre-packet-switching systems that built up to the technology. Polled terminals, like the IBM 3270 and its prececessors, could be thought of as a form of centralized packet-switching. (Polling goes all the way back to the mechanical teletype era.) There were "statistical time-division multiplexers", which multiplexed N async char data streams into a pipe that had less bandwidth than all the incoming lines. There was the original RAND proposal for a flooding network for emergency military messages.

    The big breakthrough needed for the ARPANET was the militarized DDP-516 minicomputer, which was the first computer you could just ship someplace and expect it to work when turned on.

    • Polled terminals? 3270?

      Uh oh - Flashback

      3420, 3480, TSO, CICS, JES, Netview!


      T Tur Tt ttur turw...


    • The first fully automated store and forward network was Plan 55 [ev1.net], deployed in the 1950s. This store and forward message switch was the backbone of Western Union's telegram service, and versions were used by the military.

      Plan 55 was basically Sendmail built out of paper tape equipment and telephone relays. Messages came in on teletype links and were saved on incoming queues built from pairs of paper tape punches and readers, connected by a big bin for the paper tape. The header of each message was read, an outgoing link selected by looking up the destination address automatically, and a telephone switch was used to establish a cross-office link to an outgoing buffer. The message, including header, was then copied to the outgoing paper tape buffer across the room, via the telephone switch, at a higher rate than the incoming and outgoing lines to avoid internal congestion within the switching system. Outgoing paper tape buffers, when not empty, were transmitted on their associated lines.

      Crude though this seems, all the basics of a store and forward network had been fully automated. Incoming buffers, message header parsing, determination of outgoing route from destination address, message queuing for output on the proper route, and forwarding were all present in Plan 55. Plan 55 centers were distributed and networked, with redundant routes. Messages were often forwarded multiple times, with the original header and content preserved. So all the basics of networking were present.

      All this required building-sized installations, consumed vast amounts of paper tape (every forwarded message was punched twice per node, and the tape went directly from the reader to a trash can), and was slow. But all the crucial ideas were there.

      Plan 55 message format lives on in NOAA weather forecasts and some FEMA emergency message systems. Messages that begin "ZCZC" and end "NNNN" are in Plan 55 format. The letters and numbers between "ZCZC" and the next CR are the address; everything else up to the NNNN is the message text.

  • Packet switching is great, but it turns out that
    the IP mechanism of IP packet fragmentation and
    reassembly was a big mistake. In other words, you
    don't want to break up packets. The original idea was that the MTU (minimum transmission unit) was
    unknown, so that you should be able to have
    routers which break a single IP packet into smaller fragments and have someone reassemble them elsewhere in the network. It added loads of hair and performance penalties, and really
    broke the whole "end to end" model. Here in the future, I believe that people now think you can use end-to-end MTU discovery, and just keep notching the packet size down until you get reliable transmission. Anyone know if IP packet fragmentation is still part of IPV6?
  • Kleinrock is claiming too much credit.

    Yes, his work on queueing theory is important, at least to people concerned with math and network analytics. And if anybody gives a damn about analyzing the performance of a packet-switched network mathematically, then it'll fall back onto Kleinrock's work.

    But what passes for packet switching nowadays -- "The Internet" -- is most certainly not the result of careful analysis! It works by brute force. It's inefficient. It is badly monitored and mostly unmetered. So Kleinrock's analysis, which might be useful, is ignored.

    Anybody with half a sense of the math wouldn't dare try to cram constant-rate streaming traffic, like telephony or broadcasting, onto the IP Internet. It's inefficient as hell. Economy of scale is what makes it seem to work, compared to economy of specialization (what ATM would excel at). But that's the Internet's current ruling ethos -- if it seems to work, do it, even to excess.

    The original inventors -- Davies, Baran, and the BBN crew -- were not doing mathematical optimization. They were hacking (in the good sense) something together and observing what worked. Kleinrock is like a guy who invents a great network management system that never gets turned on, but who still claims credit for the network that his system might have been able to manage.

    And puh-LEEZ, don't give Vint any of the credit. He's made a great living as the Chauncy Gardiner of the Internet.
    • Mmm.. Of cause that's an old discussion between scientists and engineers, on what is really important, theoretical prediction and analysis, or a working implementation. Being both a scientist and an engineer, I would dare to say: both is very much needed, and whoever came up with the idea should be given proper credit.

      When you do your most basic "hacking together", you stand on the shoulders of many very much academicians, even if do not realise it fully. Nothing works just by "brute force" - you use multitude of concepts, from basic like search or hashing or graphs, to advanced once, such as queuing theory and network analysis, carefully designed, analysed and implemented, and only then you add your "observing what worked". Do not dismiss theory, it is jsut as important as implementation..

      • The point I'm making is that the implementation is not primarily based on academic theory. It's based on the Internet's own culture, which puts experimentation in front of architecture, implementation in front of design. It's based on empiricism, on doing what works, and for the most part doesn't give a goat's bzadeh about Kleinrock's theory. Even when it should pay more heed!
        • The point I was making, is that pure empiricism, experimentation is a goat bzadeh, as you so eloquently put it. One uses the works of academics, whether you realise it or not, its in every library, every piece of algorithms, in your text books, in the words you use. My guess you never actually looked at the research literature on networking - but make yourself a favor. And give the credit where the credit is due.
    • Off course, today implementation has changed a lot from the beginning, and we have a more ordered system, like the Vegas and Reno BSD algorithms.
    • The subject line of this article is misleading. Analysis of a system isn't the same as building the system. But in many cases, the analysis of a system has demonstrated that it made sense to attempt building it. I could cite many examples -- not only in CS; the same principle applies to bridges and space elevators. As a general rule, the analyst gets credit for the original idea.

      Kleinrock's analysis...is ignored

      Sorry, but that's just plain wrong. Analysis has been a major part of networking from the very beginning, in no small part due to Kleinrock's influence.

      Kleinrock is like a guy who invents a great network...that never gets turned on, but who still claims credit

      Again, wrong. UCLA was one of the first three nodes on the ARPANET These issues have been discussed in great detail on the computer history mailing list. The general consensus as I recall it is that all of Kleinrock, Baran, and Larry Roberts made major contributions. None can really claim to be the sole inventor. All can claim that without them, the ARPANET wouldn't have happened.

  • For Baran's point of view, see this interview [wired.com] at Wired.
  • Just because someone says, "Hey, wouldn't it be cool if someone built a machine that flies" doesn't mean he invented the airplane. Even if they add details like "using a motor to force air over a convex airfoil" and "steering and stabilization by means of a vertical rudder."

    You could even have detailed diagrams and equations for weight/displacement, etc. But the trick is in details like figuring out how to make the engine powerful enough achieve lift off but light enough to achieve lift off.
    • Interestingly the first powered flight is actually credited to John Stringfellow of Chard in Somerset, England in 1848. The Wright brothers even credited him with doing the groundwork required to enable their first powered flight with a human passenger.
  • The reason why mathematicians don't like computer work ?? Because a lot of the "inventions" cannot be attributed to a sole genius. And so in the field of computers there isn't enough space for the hyperspace-filling egos that you find in mathematics and physics.

    The fact is, NOBODY, NOT EVEN KLEINROCK, DAVIES, AND BAREN, IN SUM OR SEPARATELY, INVENTED PACKET SWITCHING. You see, the idea did not work for almost 25 years after it was "supposedly" invented by Kleinrock et. al. It wasn't until Van Jacobsen and Karels applied optimal queuing theory and tight feedback control to exponential backoff and "slow start" to TCP feedback congestion control that packet switching was worth a damn.

    I was a user of the Arpanet from 1980-1984, and the dang thing almost never worked. It would take a whole minute just to open a pair of TCP connections in order to download a single RFC. The Arpanet was badly, badly broken. Kleinrock was not responsible for making the Internet scale. What Kleinrock invented was a broke piece of crud in 1985, 1986, etc.

    Do we attribute the invention of the computer to Bardeen, Brattain, and Shockley (hint : given in order of true technical contribution) because these guys invented the transistor ?? No, those guys only invented a "piece" of the modern computer - it was up to others to finish the puzzle. And it's similarly unfair to try to attribute the invention of packet switching to any ONE person, since it took 25 years to get all of the bugs out.
    • Don't fixate on ARPANet and TCP/IP as if they are the only form of packet switching -- it may not have worked well in the early 80s, but I can rememeber using BT's Packet SwitchStream X.25 network in 1983 -- and it worked just fine. That was certainly Mr Davies' doing.

What is algebra, exactly? Is it one of those three-cornered things? -- J.M. Barrie