Today he moves through his busy schedule carrying an arsenal of modern communications devices — a Motorola two-way email pager, a Psion PDA, a cell phone, and often, an IBM ThinkPad. To many people, these are tools worn as badges to indicate membership in the tech-savvy army of business professionals. To Leonard Kleinrock, they're a different kind of badge-more like campaign ribbons for the work he did to make the Internet a reality.
Known as the "father of modern data networking," Kleinrock developed the underlying principles of packet switching, the communications technology of the Internet. He also laid out some of the key functional specifications for the Arpanet, predecessor to the Internet. Destined for a career in science, Kleinrock's early interest in radio cast him through the Bronx High School of Science, City College of New York, and eventually a full graduate fellowship at the Massachusetts Institute of Technology in the Electrical Engineering Department.
Kleinrock joined the faculty at UCLA in 1963. Through his ongoing participation in establishing the data networking technology for Arpanet, his UCLA lab became first node on it. This first switch (known as an interface message processor, or IMP) arrived at UCLA on Labor Day weekend, 1969. Kleinrock's team of 40 people connected the first host computer to the IMP and started sending packets of data. Along the way, Kleinrock was the first person to use the Arpanet for personal email/chat — not a function in the original specification, but he needed to retrieve an electric razor left in England.
Since the pioneering days that led to the birth of the Internet, Kleinrock has continued his participation in its growth and development. Most recently, new technology for nomadic computing and communications has been on his mind. He's developing technology that will support the nomadic user in his computing and communication needs as he travels from place to place.
Internet Computing's EIC, Charles Petrie, got a chance to talk with Kleinrock at the Supercomputing Conference in Pittsburgh, where Kleinrock received the Computer Society's 1996 Harry Goode Memorial Award for "fundamental contributions to packet switching and queuing theory, two of the principal technologies that led to the Internet, empowering the global community to participate in worldwide economic, political, and cultural processes."
What follows is the behind-the-scene story of how the Internet came to be, as told by one of its founders.
Charles Petrie: As I understand it, your doctorate thesis outlined the ideas behind packet technology 10 years before the Arpanet was launched, is that right?
Leonard Kleinrock: That's correct. My dissertation laid out the basic principles for packet switching and data networking. I developed not only the basic analytical tools but the basic network design principles as well. And I talked about what the tradeoffs were and why they were so attractive.
Petrie: So you actually did some of the design as well? Design in terms of the tradeoffs?
Kleinrock: Yes, that was a major part of my research. I developed a way to calculate the optimal channel capacity assignment. I invented effective dynamic routing procedures and also established the analytic model by which you could calculate delay . . . and to simulate it I had to make some fundamental assumptions — I simulated the hell out of it to show that the assumptions worked. It's the kind of problem where if you try to solve the exact problem, you'll never get it solved; it's totally intractable. And it's intractable for two reasons. The first reason is that the queuing theory just kills you.
Petrie: Is it inadequate, or is it just too big?
Kleinrock: Inadequate. We don't know how to solve these multidimensional queueing problems. The second reason you can't solve the exact problem is due to the topological complexity. Network traffic flow is a multicommodity flow problem, and you can't solve multicommodity flow problems when more than three commodities flow in the network.. As an example of a one-commodity flow problem, consider that we want to ship grapefruits around the country on the railroad system. Each link of the railway network has a certain capacity — so many tons a day can be shipped on that link. The problem is to figure out the maximum tonnage of grapefruits that can be shipped through the railway system per day, assuming that the entire system is devoted to that task.
That problem is solvable. It's called the max-flow problem. Suppose instead that I want to send apples and oranges from different locations. That's two commodities. That's a little harder. Three commodities you can do in some cases. Beyond that, there's no efficient computation algorithm.
Now in networking, every pair of users is a different commodity. So from a theoretical point of view, you just can't solve these problems. So I asked, what can I do? And I made an assumption. I called it the independence assumption. And that cracked the problem wide open. The analysis became totally doable.
Petrie: And the assumption is?
Kleinrock: The problem involves the sending of a sequence of messages. If you look at what's happening on any link, you will see a sequence of messages arriving, and the time between the arrival of the first of two adjacent messages is related to the service time of the second message. In queuing theory, when service times and arrival times are correlated, you just can't handle the analysis. In the case of sequential messages, we see a very high degree of correlation, because the minimum time between two arriving messages is the service time of the second one.
My assumption was that they're not correlated. This was the independence assumption. I assumed that every time a message hit a node, its length was randomly reselected, guaranteeing that its length was independent of its arrival time. Sounds like a bold assumption but it turns out to be fine. The reason is that it's not only my stuff moving down the line, but other people's traffic is also joining the fray. In addition, my messages go out to different places — one goes here, one goes there — so it busts up that dependence very effectively from an engineering point of view.
That was the assumption needed to allow the analysis to go forward. But you must recognize that I was the first to develop an exact (and very simple) formulation of the problem. I can tell you what the equation is, it's trivial. It's a one-liner. It's exact. But it contains a term you can't solve for, and that's why you have to use the independence assumption. It totally broke the back of the problem. Once you have that, you can do a design based on that assumption. It has now come to be known as Kleinrock's Independence Assumption.