Oral-History:Leonard Kleinrock
About Leonard Kleinrock
Leonard Kleinrock was educated at the City College of New York and received his Ph.D. from the Massachusetts Institute of Technology (MIT) in 1963. A National Medal of Science recipient and a 1973 IEEE fellow, he made an enormous contribution to the birth of the Internet through his development of packet switching theory. Kleinrock is a computer science professor at the University of California, Los Angeles; he joined the faculty after completion of his Ph.D.
Leonard Kleinrock starts this interview with a discussion of his early interests and education. He mentions the importance of the practical experience that he acquired, including his independent childhood interest in radio. Kleinrock describes the learning environments of the Bronx High School of Science and of the City College of New York's engineering curriculum. Then, he details his training at MIT and discusses the influence of his mentor, Claude Shannon. Kleinrock describes the beginning of his work and research with computer networks, including his Ph.D. research on data communications, queueing theory, and packets, which contributed to his development of the Independence Assumption. The interview also describes Kleinrock's role in developing and implementing ARPANET. Kleinrock narrates the birth of the "infant Internet" on 2 September 1969, when he oversaw the connection of the UCLA host computer as the first node of ARPANET.
Kleinrock analyzes reception of this technology by business and industry, assessing the subsequent evolution of Internet business models. Kleinrock characterizes the functions of Internet technology in society, including the emergence of malicious Internet use. He discusses his contemporary work in nomadic computing and the founding of Nomadix Company. The interview ends with some comments about his family, work philosophy, and personal interests.
On his UCLA home page, Dr. Kleinrock includes documents and recollections of his role in Internet history.
About the Interview
LEONARD KLEINROCK: An Interview Conducted by John Vardalas, IEEE History Center, 21 February 2004
Interview # 434 for the IEEE History Center, The Institute of Electrical and Electronics Engineers, Inc.
Copyright Statement
This manuscript is being made available for research purposes only. All literary rights in the manuscript, including the right to publish, are reserved to the IEEE History Center. No part of the manuscript may be quoted for publication without the written permission of the Director of IEEE History Center.
Request for permission to quote for publication should be addressed to the IEEE History Center Oral History Program, 39 Union Street, New Brunswick, NJ 08901-8538 USA. It should include identification of the specific passages to be quoted, anticipated use of the passages, and identification of the user.
It is recommended that this oral history be cited as follows:
Leonard Kleinrock, an oral history conducted in 2004 by John Vardalas, IEEE History Center, New Brunswick, NJ, USA.
Interview
Interview: Leonard Kleinrock
Interviewer: John Vardalas
Date: 21 February 2004
Place: At Kleinrock's Home In Los Angeles, California
Childhood and family
Vardalas:
Let's start with some basic information. When and where were you born?
Kleinrock:
I was born in Manhattan, in New York City, on June 13, 1934.
Vardalas:
In what neighborhood of Manhattan were you born?
Kleinrock:
I was actually born in Harlem. I was raised in Washington Heights, which is near the George Washington Bridge.
Vardalas:
Do you have any brothers or sisters?
Kleinrock:
I have a sister. She is two years older than I.
Vardalas:
Is she in science and engineering?
Kleinrock:
No.
Childhood radio experimentation; crystal radio
Vardalas:
In the autobiographical sketch on your website you have some interesting material about yourself. I would like you to elaborate on the whole story with the Superman comic. I found that quite amusing and interesting. As I understand it, a comic book launched you into a life of engineering.
Kleinrock:
I was an avid comic book reader as a child. In the centerfold of the comics there would always be some non-comic thing. In a particular Superman comic book there was a two-page text description of how to build a crystal radio, and it caught my eye. The thing that attracted me was that this could be built out of household materials. No battery was needed and one would get music and radio programs out of it. I thought, "I want to try this." I needed my father's old razorblade, a piece of pencil lead, an empty toilet paper roll, some wire, something called a variable capacitor and an earphone. I did not have the variable capacitor or earphone, but I had all the other stuff. I stole an earphone from a public telephone booth. I was just a young kid you know. The variable capacitor threw me. I could not find that in the street or in the house. So I had my mother take me on the Subway down to one of the electronic stores on Canal Street. I walked in and proudly said, "I want a variable capacitor." The guy said, "What size?" Of course, I had no idea, and it blew my cover. I told him what I was trying to do and he knew just what I needed. He sold me this variable capacitor, and I went home and wired the whole thing up. Then, son of a gun, music suddenly came in my ears. It had no battery. I just tuned the capacitor and adjusted the little crystal that I formed with the lead and razorblade. It was amazing. This was magic. Where was this coming from? There was no energy going into the system. I just had to find out how this all worked. Basically, I was hooked.
Vardalas:
That was what hooked you then.
Kleinrock:
Yes. I was a kid that experimented with a lot of things, but never with serious electronics until that crystal radio.
Vardalas:
With what had you experimented?
Kleinrock:
Just playing with toys and taking them apart and reassembling them, building model airplanes, fixing toasters, with simple electrical gadgets like telegraph key sets and things like that.
Vardalas:
In the mind of a six-year-old, was it the magic in this crystal radio that did it for you?
Kleinrock:
The magic of radio waves and that it required nothing that would break down or wear out, like a battery. We did not have much money, and to buy batteries was too expensive. I liked the fact that it was absolutely free. Electromagnetics and radios are mystical. I said, "I want to understand what is going on here." I collected broken radios from friends, relatives and trash barrels. I would take them apart and rebuild them. I would also build radios from scratch after studying diagrams of their design. If I needed a particular vacuum tube I could not afford to buy a new one, but outside the shops on Canal Street they would display little cardboard boxes full of tubes. You may remember that. They would say, "Tubes guaranteed to light, a nickel apiece." The filaments would usually light, but they would not always amplify. I did not have any measuring instruments. Who could afford a Simpson meter? I had to figure out what was going on by trial and error.
Vardalas:
I see. How did you move through this learning curve? Where did you go?
Kleinrock:
I went to the library when I was a little older, just around 8 years old. I remember a particular book called Elements of Radio by Marcus, Marcus and Horton. That was a wonderful book that explained not only the mathematics – which was hard to read – but gave excellent and intuitive descriptions of electrons moving, filaments heating up, electrons boiling off. It explained in layman's terms and in a way I could understand as a young child. I would read that book late into the night. To me it was magical. I taught myself all about radios. There was a lot of war surplus equipment available and there were many war surplus training manuals that were written for the military. There was also the very informative RCA Radio Tube Manual which had a terrific tutorial section on radio. I managed to find these manuals through magazine ads, in the Canal Street electronic stores, in hobby shops, and most of them were free.
Vardalas:
You were fairly resourceful on your own. You just dug this stuff up?
Kleinrock:
Yes. I was pretty determined to find out all I could since there was no one in my life who knew anything about electronics. My first formal training came much later in high school.
Vardalas:
Was radio your key obsession before high school?
Kleinrock:
Radio was a key obsession, but I also spent time building model airplanes that could fly.
Vardalas:
Did you get more sophisticated in your abilities as you got a little bit older as a teenager?
Kleinrock:
As you might expect, I wanted to become a ham radio operator, but it cost too much money. The rig was expensive. Some really sophisticated equipment was needed. I could not afford that, so I never became a ham radio operator.
Education; Bronx High School of Science
Vardalas:
About your interests as a child, What did grade school do for you? Did it reinforce this obsession or did it block you? How did you find school?
Kleinrock:
I loved going to elementary school. I was in a class with smart kids. The thing I liked about school was that it was orderly and structured. When I made progress, I was graded accordingly – as opposed to my home life, which was very unstructured. School gave me a set of goals and I would achieve them. I also liked competing with the other kids in a friendly way. I remember once in elementary school the teacher gave us an oral word mathematics puzzle. She went around the room asking, "What is the answer?" When she got to me I said, "Naught." She said, "No" and went on to the next person. Someone else said, "Zero" and she said, "That's right." I said, "Wait a minute. I said naught." She didn't understand the word naught. I don't know where I picked up that word, but it upset me to have been the first with the correct answer, and to have been told I was wrong.
Vardalas:
Let's discuss now the Bronx High School of Science. I was surprised that you listed it in your CV. To me this obviously means that the experience was something important to you.
Kleinrock:
Very important.
Vardalas:
Let's explore that a little bit further. First of all, did you go to the high school already having an idea of what you wanted to become in life?
Kleinrock:
Of course I loved electronics, but I had in no way decided what I wanted to do. My junior high school, like most junior high schools in New York, was a pretty hard place in terms of a lot of rough kids and a rough neighborhood. Those couple of years in junior high were difficult. I was in a smart class and felt protected in there, but when we went out in the hallways and streets it was bad. I lived in a really rough neighborhood. I was the only Jewish kid in my neighborhood, and it was hell. I had to learn how to take care of myself on the street very early in life.
In junior high school, they gave an entrance exam for the Bronx High School of Science and Mathematics and I took it with no expectations. Lo and behold, I was accepted. Then I was a little concerned. I did not want to be channeled only into science. I wanted to keep my options.
Vardalas:
You were already thinking that way at that early age?
Kleinrock:
Yes. A general high school education seemed more appropriate to me, so it took me a little while, but I finally decided to go to Bronx Science. The first class I took there was a social studies class. When I walked in the teacher said, "We are going to study social studies using the scientific method." That really worried me. However it was a wonderful experience. I was surrounded with really smart kids, some of whom were quite nerdy. This school drew in the mad scientist types. There was one guy who won the Westinghouse science talent search. He built a big Helmholtz coil.
That sort of mad science stuff was stimulating. I took my first formal radio engineering courses there. There were about three or four kids in the class. Most of the students were interested in mainstream sciences – biology, chemistry and physics. I found those radio engineering classes very rewarding. I had a real leg up and I learned a lot of advanced material. I got to see the science behind radio as opposed to just the hobby. I also had a wonderful physics teacher there. I took physics before chemistry – as did my wife by the way, totally independently.
Vardalas:
Did your wife go to the same high school?
Kleinrock:
No, but when she went to high school she took physics first. Maybe that is why we were attracted to each other. I loved physics. I remember something that really struck me one day when I was on an elevated train station platform in the Bronx waiting to catch the train. I was with a friend who was also in science. I said to him, "I wonder how high we are?" He picked up a stone, dropped it, timed it and told me our height above the ground. I said, "How did you do that?" He explained the physics behind his calculation and I was amazed.
The ability to apply science to real world problems was just fascinating to me – far more than chemistry, which is much more abstract. I could do levers, mechanical advantage, pulleys – it was wonderful. Physics was great and the radio engineering was a wonderful course.
Vardalas:
What are your most vivid memories of those high school years? Were you there three years, 10th, 11th and 12th grades?
Kleinrock:
That's right. I started there in 1949 and graduated in 1951. I accelerated and skipped one grade while there. I did so for strategic reasons, namely, because I was out of the normal sequence for graduation. I had been scheduled to graduate in January rather than in June. That was not the best cycle to get into college since most students enter college in September. Therefore I accelerated. That was a mistake, because I was neither fish nor fowl. I left the class with which I had entered and in the middle of it all I joined a class whose students I did not know.
The social side was a little bit warped as a result. Most people traveled by bus or subway to attend Bronx Science, so one didn't spend afternoons with those same kids. I was in two clubs there. One was the recording squad. We had a wire tape recorder. It was wonderful. Again more electronics and I loved that. I was also in the orchestra. I played the violin. My orchestra teacher was a wonderful guy and I enjoyed it very much.
City College of New York; Photobell Corporation
Kleinrock:
When I was getting ready to graduate high school of course I wanted to go to college. In an earlier question you were wondering about parental influence. That was their strongest influence. It was clear. "You are going to go to college." There was no question about it. However there was no science in my household at all. Both of my parents were immigrants from Eastern Europe. My father was a grocer. My mother had been a secretary and then she was a housewife. I wanted to have an out-of-town college experience but I knew we couldn't afford it, so I wrote to every state Chamber of Commerce in the United States asking, "What is your state scholarship program and what kind of fellowships do you have?" I got a number of replies indicating that they had quite a number to offer me. I applied for, and was offered, many of these scholarships, but I couldn't go to any of those out of town schools since they would not be able to provide sufficient funds for my needs. Beyond my tuition expenses, which they offered to pay, I needed additional money for living expenses and still more to send home to help support my family. The situation was that my father had gotten very ill in 1945 and could not work a full-time job. He got ill with asthma when I was eleven years old. He had to sell his grocery store and stop working. It was tough. I worked long hours all through junior high and high school.
Vardalas:
That must have been tough on him too.
Kleinrock:
It was tough. It was hard for the entire family. I worked all kinds of jobs. For example, I was an usher in two movie theaters at the same time, and every afternoon after school I would rush to work and get home late in the evening; it made it hard to find time to do my homework.
Therefore I decided to remain in New York City and was accepted by the City College of New York (CCNY), which at that time was a top-rated school. More Nobel Laureates have come out of there than any other public university.
I was scheduled to go into the electrical engineering program in the Fall of 1951. By then I had decided that electrical engineering was to be my career. During the summer of 1951 I was a New York City lifeguard. I was seventeen. Towards the end of that summer, my Dad took me down to his cousin's electronics firm. My cousin had an industrial electronics design firm where the focus was on photocells. The photocells would count boxes of cereal as they moved along assembly lines, observe when people entered the rooms, etc. It was a fairly interesting technology.
Vardalas:
Was this Photobell?
Kleinrock:
Yes, that was Photobell. Corporation. Very good. During that visit, I was offered a position to work there full time. I said, "Why are you offering me a position? I am entering college this Fall." However, my Dad encouraged me to take the position, so it was decided that I go to work there and attend evening session at CCNY. That was a big blow to my plans to go to day session, but it provided an income for my family which they needed. I was living at home so all the money I earned went into the house.
Since I had taken accelerated courses at Bronx Science I had not taken advanced algebra. That was one of the first courses I took in evening session. Guess who was teaching that course? My high school orchestra teacher. He was moonlighting at night. It was quite uplifting for me, because I was glum about this whole idea of going to college at evening session in a city school. In him I found a friend, someone to whom I could relate. You have to understand that there was a weird collection of students in evening session. There were some very smart kids. They were all working, some motivated and some not so motivated and sort of trying it out. There were a lot of immigrants who were there for the same economic reasons I was. However we had great instructors. These instructors were working in industry and teaching at night. They had first-hand experience of what was happening in engineering.
I had wonderful teachers.
They taught me about amplifiers, AC circuits, DC circuits, pulse and digital circuits, analog computers, control theory, and more. They were using the technology, and not just teaching it. Maybe I am getting ahead of you.
Work ethic; Boy Scouts and Eagle Scouts
Vardalas:
No, that is okay. We will cover it all one way or another. You say you were glum. It must have been difficult for you to accept the fact that your schoolmates at Bronx High School of Science were all going on to full-time university studies, probably some nice universities outside the city, and you were now confined to this. Was it tough to accept?
Kleinrock:
Yes, it was very tough to accept. I always felt like an outsider in that sense. Most of the kids in high school were living reasonably middle class lives. I did not think of myself that way, so it was hard. There was something that happened during high school that was important, and it is a question you may eventually ask so I will ask it for you now.
Vardalas:
Sure, please.
Kleinrock:
One of the important events in my life that helped me realize that I could overcome difficult odds was the following. I was a Boy Scout in Junior High and High School. I liked that because it allowed me to get out of the city and into woods – for camping and hiking. I just loved it. I rose through the ranks, Tenderfoot, Second Class, First Class and then became a Star Scout which requires five merit badges. When I was awarded the rank of Star Scout, my Scoutmaster said to me, "Len, you can become the first Eagle Scout in our troop," and he challenged me to do it. That was hard. How the heck was I going to get twenty-one merit badges in the city? I took the challenge on and I did become the first Eagle Scout in my troop. That was the first real achievement for me, one that looked almost out of reach. It was hard to do, and I did it. I went to Scout Camp one summer and got thirteen merit badges in two weeks. When I came back my mother did not recognize me when I got off the bus. I was as thin as a rod. As a result, I became an Eagle Scout. If you go upstairs in my house, you will see I have a big wall full of my academic diplomas and awards, and I have placed them in a collage. Of those many significant diplomas, the one in front is my Eagle Scout award; it trumps them all in importance to me.
Vardalas:
That must have affected the way you approached City College of New York and going to night school. You graduated with honors of distinction, and you had a job while in school. Obviously you were bright, but you also had a single-minded sense of purpose. Was that kind of how it started, with this Eagle Scout achievement? Did that give you this sense of purpose?
Kleinrock:
Yes. The fact that I could achieve a really hard objective. I had always worked very hard. In elementary school I was a good student but I was not the top student. In high school I did very well but I do not think I was top there either. Those kids were really bright. However I began to get my act together and say, "I can do hard things." I believe as a philosophy that one's first success is very important because once you taste success you know you have it in you to do it again. Before that first success you wonder if you can accomplish a really hard goal. That Eagle Scout award was a very important step for me.
Bronx High School of Science culture
Vardalas:
To go back a little, you mentioned there were a lot of nerdy kids. You were not one of those nerdy kids the way you describe the neighborhood in which you lived.
Kleinrock:
No, I was a street kid.
Vardalas:
Yes, you grew up in a tough neighborhood so you had to watch out for yourself.
Kleinrock:
Yes.
Vardalas:
That is an interesting balance, being in that life and the intellectual life.
Kleinrock:
In Bronx Science we had the head of the South Bronx gangs and the head of the Harlem gangs. They were students there.
Vardalas:
Really?
Kleinrock:
They were smart kids. Think about it. They were great.
Vardalas:
That is interesting.
Kleinrock:
Yes. There were also the nerdy and awkward kids. It was a wonderful experience, but I did not get deeply into any social group there.
Vardalas:
Right, because it was a commuting school.
Kleinrock:
It was a commuting school and I always worked and could not spend much time after school before I came home. However, I did join the swim team there, and that was a great experience. That was a nice social group, because swimming was always my favorite sport. I went to camp a couple of times before high school and always engaged in the swimming activities. I beat out one kid who had perfect form, and I had no form at all, but I had a great deal of determination. When I got to the swimming team my instructor taught me the proper form. It was great. We had to swim in the nude there.
Vardalas:
No. Really?
Kleinrock:
Yes. Just the guys. One time there was a water shortage so they couldn't heat the pool. He made us continue our practice and swim in that really cold water.
Vardalas:
Were you on the swim team all through high school?
Kleinrock:
Oh yes. I loved it.
Vardalas:
Then you became a lifeguard too.
Kleinrock:
That's right.
Vardalas:
It's based on that.
Kleinrock:
That's right.
Electrical engineering at CCNY
Vardalas:
That's very interesting. Would you elaborate more about the electrical engineering program at City College of New York? You hold it in high esteem. What did you cover? Was it solid-state electronics at this point?
Kleinrock:
No.
Vardalas:
Not yet.
Kleinrock:
Well, almost. We had a teacher who taught us a little about transistors, just those early germanium transistors, which were just coming out. I remember his comment very clearly. He said, "Transistors are better thermometers than they are amplifiers." They were so heat-sensitive it would change their characteristics. However we did not really study much about transistors. It was almost all about vacuum tubes. My whole history by that time had been learning about vacuum tubes. When I find somebody else who is into electrical engineering I reminisce by saying things like 6SN7 – that was a dual-triode amplifier, you know – and they get all excited. Or 6L6 or 35Z5. These were the famous tubes of that era. And then came the miniature tubes like the 12AU7 and the 12SN7.
Vardalas:
Was City College of New York starting to get into any digital electronics at this time?
Kleinrock:
Yes, I took some digital circuits courses toward the end of my undergraduate studies. It took me five and a half years to complete my studies there, which was really fast for evening because the day session program was almost a five-year program. I went three-quarter time plus summers while I was working full time. I felt like I went into a tunnel when I went to evening session, and I was not sure if I was going to come out the other end. It was a long haul and slow progress. It was hard.
Vardalas:
Did evening session teach the same things as the daytime session?
Kleinrock:
The courses were exactly the same, but the instructors were not. We had a few of the day session professors there, but it was mostly people coming in from industry.
Vardalas:
That was what you thought was a big asset.
Kleinrock:
Yes. It was wonderful. These guys really knew what was happening. Like this thing about the thermometer. I'm sure in the day session they said, "Here is the transistor, here is the way it works, here are the governing equations." Our evening session instructors said that plus, "Look. It doesn't work very well; and here’s why."
Vardalas:
Your first introduction to the concept of digital technology was at the every end of your time there?
Kleinrock:
Toward the end. A book by [Jacob] Millman and [Herbert] Taub called Pulse and Digital Circuits was the classic at the time. It came late in my college career, but I had studied analog computers and control theory from some very fine professors before that. I know you are going to ask if there were any professors that influenced me. There was one named Mr. Smith who taught me AC theory and he was a role model for me. He wore a bow tie, so I started wearing a bow tie.
Vardalas:
Was AC power engineering then?
Kleinrock:
No, the power engineering courses consisted of AC machinery and DC machinery. I hated machinery. I loved electronics. The course I am referring to was AC circuits. It included Fourier series and analysis, impedance and all the rest. A funny thing about City College at the time was that they taught us about AC circuits and that the impedance of an inductor is jωL. Are you an engineer at all?
Vardalas:
I did my graduate degree in physics.
Kleinrock:
Great. Okay. So you would use the symbol i instead of j for √-1.
Vardalas:
Right. The i comes all the other way around.
Kleinrock:
Right; i stands for current in electrical engineering, so it cannot be used for √-1. Instead, j is used. And 1/jωC was the impedance of a capacitor. We learned that, but by the time I graduated City College it was not clear to me that we were actually dealing with Laplace-Fourier transforms, even though we had studied Fourier analysis. They did not nail down that idea at all. That hit me when I got to MIT.
Vardalas:
Oh, I'm sure.
Kleinrock:
I took analog computers and control theory, so later on when I applied to MIT and they wanted to know what field I wanted to study I said analog computers; specifically not digital computers, because I did not know anything about them. It had not entered my vision. After I made that application I studiedPulse and Digital Circuits which was the basis of digital computers and said to myself, "Wow, this is the stuff," and that is what I actually did focus on when I got to MIT.
Photobell employment
Kleinrock:
I had also taken what I had learned about digital circuits – remember I was working all this time – and introduced the idea of digital circuits to Photobell. That was natural. We were trying to detect if there was a box there or not, or an individual there or not. This was obviously a zero-one condition.
The idea of going from linear amplifiers to the highly nonlinear circuits of digital electronics was a big innovation I introduced to Photobell, and they adopted it and it was very good. I enjoyed doing that. In the daytime when I was working at Photobell I interacted with graduate electrical engineers there. These guys were like gods to me, and I learned much from them – so much. There was a guy named Ted Lasar who was my mentor there. He had come out of City College. He was about ten years my senior. He really knew electronics. It was so great. All these guys at Photobell by the way came out of World War II. They were all soldiers and they told me their war stories. One of my first jobs at Photobell was to take a resistor and solder it inside a phone plug to get the proper impedance. The boss said, "Do that and make a little diagram of it." I had just taken descriptive geometry class and I was great at drafting, so I did that little job in 5 minutes and then spent about an hour drawing a perfect diagram. I handed it to my boss and he went ballistic, saying, "What the hell are you doing? Why waste an hour doing that?" I quickly got much more practical with that experience. It was great.
Vardalas:
I was going to ask about how your experience at Photobell shaped your development.
Kleinrock:
My early experience in practical physical engineering stayed with me even though I was going into more and more mathematical structures and research – building it myself as a kid, playing around with it in high school, studying at City College in the evening and building it at Photobell in the daytime made it all come to life. Dealing with instructors who were doing the same kind of thing while learning the theory kept me very well grounded in the real world as opposed to marching off into theoretical physics or something else. Even though my work is highly mathematical now, it is deeply rooted in the reality of things. What does it mean? How does it work? What is the physical feel? What is the application?
Vardalas:
That is an important asset in the way you do things.
Kleinrock:
Absolutely.
Graduate electrical engineering and computer science education
Vardalas:
Would you say that today graduate students who do electrical engineering tend to be overly theory-based? Are many missing this practical grounding?
Kleinrock:
By and large, you are correct. By the way, I teach in the Computer Science Department. Electrical engineering and computer science overlap so much that we share many students. I would say since the dot-com boom things have changed. Before the dot-com boom, yes, they were going off into never-never land. The dot-com boom attracted many into industry and that started them thinking, "What can I do with my theoretical ideas? How can I make contributions count?" They started thinking about industry and applications. They are coming back to seeing applications. I see that among the students now. They are all thinking, "What will I be able to do with this?" in jobs and business.
A few years ago as a professor, and as a department chairman, I would lecture the incoming graduate students and say, "How many of you read Datamation or Computerworld or InfoWorld?" No hands would go up. They were busy reading the IEEE, ACM, the professional journals. I said, "Look, if you don't read the industry news you may have no idea why you are studying what you are studying. Why are you looking at a new database structure? Why do you care about magnetic memory? It is because that is what the industry is doing. There are millions of dollars going into it." If they don't see that, they probably don't know why they are learning what they learning. That is a big mistake.
Vardalas:
I want to pursue this tangent for a second. In the formation of engineers, and computer scientists in particular, there are two categories. There are computer engineers who study computer engineering and there are computer scientists. Depending on to whom one speaks, I get the impression that computer scientists tend to be more theoretically minded and less hands-on and industrious. Do you see a difference in the way they approach problems? Is there a problem or are they coming together now?
Kleinrock:
I think they are coming together now, more so than historically. I have always wanted to be in both worlds. I love academe for all the good things it has, but one cannot be a really good teacher or a really good researcher – and I am going back to my City College evening session roots – unless one understands what is happening in industry and the applications in the real world. A faculty member can do that by consulting. In my case I consulted and I started some companies. One has got to get out there and see what is happening.
Vardalas:
I noticed that the computer engineer types are more entrepreneurial.
Kleinrock:
Yes.
Vardalas:
They will go out and form spin-off companies and try to do something, whereas the theoretical computer scientists or those who tend to be more theory based tend to stay in the comfort zone of academia.
Kleinrock:
They do, and yet I can show you a lot of counterexamples, for instance the people in cryptography.
Vardalas:
Yes, of course. Some artificial intelligence guys must have tried back in the 1980s.
Kleinrock:
The tried to commercialize robotics technology.
Vardalas:
Yes. I am just looking at the number of companies.
Kleinrock:
You're right.
Vardalas:
In most universities the two fields are separated into different departments.
Kleinrock:
Yes, but in our department, both fields were represented.
Vardalas:
I am surprised that you have not been able to capitalize on the synergies being in the same department.
Kleinrock:
We do benefit from being in one department.
Vardalas:
You have the synergies between them?
Kleinrock:
Yes. We often put in joint research proposals where both the strong theoretical and application components are needed.
Vardalas:
Okay.
Kleinrock:
In general, there is not that much cooperation among these two groups. Basically, they have different views. The University of California at Los Angeles is unique in that we were one of the first computer science departments to be created. At the University of California at Los Angeles as an institution, we did not have the classic battle between mathematics, business and engineering fighting over this thing called computer science. It was formed in engineering. Years later that came back to haunt us. Some of it later went to the Department of Mathematics. Other parts went to the Business School where students are taught more practical programming. In computer science, we don't train programmers to go into industry. We teach the academic side. It did come back to bite us later, whereas in most universities they had that fight and settled it early.
MIT fellowship application
Vardalas:
After the evening session experience at City College of New York and working so much, how did you come to Massachusetts Institute of Technology?
Kleinrock:
I wanted to go to graduate school, and while I was at City College they announced there was going to be someone coming down from MIT Lincoln Laboratory to describe a scholarship fellowship program at four o'clock on a Thursday afternoon. I took off work early (but made up the time the next day) and learned about this wonderful, wonderful fellowship program. It was called the Staff Associate program.
The program was set up for the student to get a master's degree at MIT in three full-time semesters plus an additional part-time semester for one last course. During the first two semesters one is basically a research assistant at MIT and getting paid for that. In the summers there was full-time work (and pay) at Lincoln Laboratory, and in the third semester one would get a full-time salary even though still attending MIT as a student. The Masters thesis was to be finished by the end of the third semester. We were expected to work full-time at Lincoln Laboratory in the fourth semester while finishing our final course. In order to accomplish this we were expected to make a 20-mile commute by Lincoln shuttle to MIT. That was the program. I said, "This is terrific. It's good money and perhaps the finest engineering school." The visitor from MIT Lincoln Laboratory said to the student audience, "If you want to apply for this program, see the professor in the back of the room after the lecture." I went back there and talked to him and said, "I'd like an application." He said, "I don't recognize you." I said, "Oh, I'm an evening session student." He said, "Evening session? You can't have an application." I said, "What are you talking about? I'm first in my class, day and evening." He said, "You can't have an application." So I wrote directly to MIT Lincoln Laboratory and got the application. I was the only CCNY student to be accepted into the program.
CCNY student life
Vardalas:
There was a stigma against the evening session?
Kleinrock:
Definitely. I was not quite aware of that because I did not interface with the day session people. He was a professor with an attitude. By the way, one way I did interact with the day session was that I had formed an evening session swimming team. We foolishly took on the day session freshman swimming team.
Vardalas:
Was this at City College of New York?
Kleinrock:
Yes, at City College of New York. We got whipped badly, because I had a bunch of ragtag guys. I must say I had an interesting life there. I would work all day and go there in the evening. At eleven o'clock at night I would be done with classes, and then my social life began. We didn't have fraternities. We had a thing called House Plan, which was just a collection of men’s clubs and women’s clubs all housed in a brownstone building. We had a great time.
Vardalas:
Where was this?
Kleinrock:
This was literally one block north of the campus. They were in three or four brownstone buildings. It was great. As a college student one gets into all kinds of things. And for us at CCNY, that was where all the debates and social activities took place. It was a wonderful institution.
Vardalas:
When did you do your studying?
Kleinrock:
On the subway, and sometimes on the weekend. I had a scheme. I would take a letter-sized piece of paper, fold it in half and then fold it in half again to get narrow columns. That made eight sides. I would write all the equations that I needed to study on the subway. That's where I did a lot of my studying. I also studied on the weekend, but I sailed through City College. I worked hard, but not studiously because I did not have to. It just came naturally to me. Engineering is really easy in the sense that you just have to grasp what’s going on and how things work and behave. You don't have to wonder, "Gee, what is the philosophy of Kant?" or something less precise of that sort.
Vardalas:
Did you have the same experience at Massachusetts Institute of Technology? Did you sail through that?
Kleinrock:
No. I hit a wall. But first, let’s return to life at CCNY.
Vardalas:
You were talking about the house plan and your social life and your application to Massachusetts Institute of Technology.
Kleinrock:
I met my wife through House Plan and got married at the age of 20. I then got accepted to the Massachusetts Institute of Technology.
MIT master's degree, Servomechanisms Lab
Kleinrock:
But now I faced a dilemma, because I had also applied to the west coast for a Masters degree. I received Masters fellowships from both Hughes and Lockheed. I actually pondered for a while whether I wanted to accept the Massachusetts Institute of Technology offer. I think I was afraid of Massachusetts Institute of Technology because of its imposing image. In this case my father urged me to accept the MIT offer. The value was obvious to him. It was really obvious to me, but I like to keep my options open until the last minute. I finally came to my senses, accepted MIT and found myself facing that imposing MIT dome in Cambridge, Massachusetts. I was surrounded by some of the best and brightest students from all over the country and all over the world. My academic advisor was a well-known Professor named Murray Gardner. He had coauthored a book on Laplace transforms and analysis – the mathematics of circuit analysis. He was also one of my first instructors. For my research, I was working in the Servomechanisms Lab.
Kleinrock:
Frank Reintjes was head of the Servomechanisms Lab.
Vardalas:
Okay. They were developing numerical control systems there.
Kleinrock:
Yes, numerical control and automatic fire control systems. I worked for a researcher named Mark Conley on a contract in the Servomechanisms Lab. Conley told me, "It would behoove you to do well in Gardner's course." It was the one that separated the men from the boys when they first came there. It was all about Laplace transforms and circuit analysis and used Gardner’s book. In my first exam in that course I got a 50! I couldn’t believe it – 50! That was the wall. I had never gotten less than 90-plus. I said, "What's going on here?" I realized, as I said earlier, that City College had not emphasized transform analysis, a topic that the other students at MIT understood well. I went to Gardner and it turned out to be a 70. He had not graded it correctly. Nevertheless, I went driving around Cambridge in my car yelling, "Fifty? You can't do this to yourself." It was a wakeup call. I really dove into my studies after that. I realized that I would have to work a lot harder than I had at City College. The hard work paid off and I did get an A in the course.
It was a good lesson, because I was surrounded by really tough competition and I needed to knuckle down. I did my Masters thesis in the Servomechanisms Lab on something unrelated to anything else I had ever done before. It was basically optical data processing with thin magnetic films using something known as the Kerr magneto-optic effect and it involved bouncing polarized light off a magnetic surface. According to the direction of the magnetization the angle of the polarized light will change one way or the other.
Kleinrock:
That difference in angles can be used to distinguish the direction of the magnetization, hence distinguishing a digital “zero” from a “one”. This research was heavily dependent on physics. I was depositing thin magnetic films in a vacuum chamber and also trying to do some digital logic with it.
Lincoln Laboratory; Ph.D. studies
Vardalas:
There was a lot of interest in thin films then.
Kleinrock:
There was a lot of interest. They were trying to develop new magnetic memory technologies. I did some interesting work on magnetic film memory but that was not my strength. I was not a physicist. I did a very good job though - so good that Frank Reintjes urged me to go on for a Ph.D. I had no intention of ever getting a Ph.D., no plan to go into academia, and little confidence that I was cut out to do truly advanced research. My plan was to take a job at MIT Lincoln Laboratory upon completing my degree. Indeed, I had some wonderful experiences at Lincoln Laboratory. When I first got there in the summer of 1957 I had worked for Ken Olsen.
He was my immediate supervisor. I designed a circuit for him which was a delayed pulse amplifier. A delay is dialed in, and once the amplifier is triggered on, a pulse comes out of the amplifier after that delay expires. I did a lot more for Olsen than building that particular device and one day Ken Olsen said, "Listen, Len. I'm forming a company. You have got to join me."
I had just started my Masters degree and said, "No, I can't do that. I need to pursue my graduate degree."
Vardalas:
When you look back on that do you ever wonder if you should have taken that job?
Kleinrock:
No. I am happy that I didn't join what became Digital Equipment Corporation. Look where I am now. I would have been an engineer there and maybe a founder, but I have instead gone on to do some other interesting things. By the way, that device I designed for him was one of the first things he sold. He did not sell computers at first. He sold little modular parts. Then eventually he sold computers.
I knew a lot of the guys that went to work for him. When that company started it met with some unfortunate events. A few months after it began their chief engineer was murdered. His name was Ben Gurley. He was a brilliant guy. I had worked with him that summer at Lincoln Lab. Some disgruntled employee killed him in his kitchen right in front of his children. Another guy who was still a technician for us at Lincoln, but who was considering working for Ken walked out of his house and somebody plugged him in each of his four limbs. He never said who it was.
Vardalas:
This was Boston, and you worry about growing up near Harlem.
Kleinrock:
I was in the group that had developed the TX-0 computer, which was the first transistorized computer. At this time they were building the follow-on computer, the TX-2 and I worked a lot on that. Wes Clark was head of that group. This was when I first met Larry Roberts. He was also a staff associate and was my officemate as well as a classmate. Ivan Sutherland was also a classmate. He and his brother were just written up in the New York Times this past week. Other greats were there as well. With my professors urging me to go on for a PhD, I decided I wanted to work for the absolutely best faculty member in my field at Massachusetts Institute of Technology. So I contacted the legendary MIT Professor Claude Shannon who had created Information Theory and asked to work with him; to my delight, he agreed.
Claude Shannon; chess software
Vardalas:
You worked for Claude Shannon? I did not realize that.
Kleinrock:
This man was my idol. I took some fantastic courses with him. He was an unbelievable guy. If you walked into his office, he would have a Swiss army knife open, screwing around with some kind of a differential gear. As mathematical as he was, he possessed great physical intuition. This is that same capability to which I referred earlier. He understood the way things worked. He would start with his physical intuition and then go to the mathematics to prove his results. He had come to MIT from Bell Labs to continue his work in information theory and coding theory. But he had interests well beyond those disciplines.
I started writing a chess-playing program with Shannon, John McCarthy and McCarthy's student Paul Abrahams. Those two were writing software to generate legal moves in chess, and Shannon and I worked on the strategy of the middle game. The first thing Shannon said to me was, "Here is a book by Fred Reinfeld called 1001 Winning Chess Sacrifices and Combinations. On each page is a situation ripe as an opportunity to make a brilliant sequence. Find it."
Each sequence was very hard to find, but the solutions were in the back of the book. Shannon said, "Look at the solutions and categorize the winning sequences. Find out which is the most popular first move of a winning sequence." The answer, by the way, turned out to be “check”. No surprise, right? “Check” severely limits the options open to your opponent. The second most popular first move is “capture”. We put these strategies into our algorithms and started writing the program. This work evolved into the MIT Chess playing program.
As interesting as this was, I decided not to do my dissertation on the game of chess. That was just a temporary project for me. I was looking around for something more significant. Besides Claude Shannon, the faculty there included Bob Fano, Peter Elias, Jerry Weisner, Dave Huffman, Norbert Wiener, Marvin Minsky, John McCarthy, Amar Bose, Jack Wozencraft and many others. They were brilliant guys. Massachusetts Institute of Technology was very inward looking, as if the outside world did not exist. We had special lectures and seminars by these great faculty members about once a week. There were amazing graduate students there too. It was a very exciting environment. But, when I looked around me, I saw my classmates were all working in different aspects of information theory and coding theory, areas in which Shannon had already done the key work. What was left were really hard problems of relatively small significance. Shannon had laid it all out.
Ph.D. research in computer networks
Kleinrock:
I said, " I don't want to spend my time working on small problems. I want to find more interesting and virgin territory." At the same time, having worked at Lincoln Laboratory and MIT where I found myself surrounded by computers, I realized that sooner or later, these computers would need to communicate with each other. I also realized that the existing telephone network was woefully inadequate for such communication and that what was needed was a new network technology. I recognized that providing an effective solution to these problems was a fascinating challenge and one that I hoped would have a significant impact on technology and computers. The challenge and possible impact appealed to me, and so in 1960 I went forward on my Ph.D. research in the area of computer networks.
Vardalas:
That is how you came to this specific problem, with just that realization?
Kleinrock:
It was an obvious need to me, and I saw an approach to the solution to this problem. Specifically, the 1950s and 1960s was the era of timesharing and it was clear to me that the fundamental principles of timesharing would also apply to data networks.
Vardalas:
Had the MAC project started yet?
Kleinrock:
No, that had not started. However there were plenty of embryonic timesharing systems around. They addressed the same kind of problem that was facing data communications. We can talk about that in a minute, but I don't know if you want to get into that technical side yet.
MIT environment and colleagues
Kleinrock:
The environment at MIT was so alive and so rich. Classmates interacted with one another. I don't know if you know the names Tom Kailath and Jack Ziv for example. Jack Ziv was one of the guys who created the Lempel-Ziv algorithm. Tom Kailath was a great communication theorist. One is Indian and one is Israeli. These two guys taught each other their specialties on their own in Tom's office. These impromptu interactions were unbelievable. I sat next to a guy doing artificial intelligence and another guy doing coding theory. It was a wonderful environment. By now I had moved from the Servomechanisms Lab to the Research Laboratory for Electronics (RLE).
I watched Shannon and Norbert Wiener teaching there, and, in fact, Wiener was in a class with me. We took scientific Russian together with a few others. The environment could not be replicated. It was a real hotbed of intellectual brilliance. To be accepted into the PhD program, one had to pass a qualifying exam, which was a killer. It was a written exam full of trick questions. If you did not see the trick, you failed. There was a 50 percent failure rate on that exam.
Ph.D. thesis and committee
Vardalas:
Your idea of a virgin territory to get into just came to you very naturally?
Kleinrock:
Yes, but with an approach that I learned when I studied under Shannon. One of Shannon's key teachings was that you should look at important problems. He also recommended that one look at the systems in their limit of large numbers. Coding theory works when there are long sequences. I thought, "These computers are going to have to talk to each other." My natural mathematical side said, "Let's examine the case when a large number of computers have to interact and communicate. However I solve this problem, it has got to yield a scalable solution." My thesis proposal was called "Information Flow in Large Communication Nets."
It had a different title before it was done, but my focus was on large systems. That meant that I could not allow centralized control, because that is a point of overload and failure. Therefore one key idea I introduced was distributed control, specifically, distributed routing. No one piece of the network should control the rest of the network; it is all local control.
A key underlying problem was, "Why not let the then-existing communication network – the telephone network – solve this problem?" However, it was clear to me that would not work because the telephone network is basically a fixed assignment system. When you and I speak on the telephone, our communication is carried over a sequence of communication links dedicated to our conversation.
Vardalas:
Right. It is locked in there.
Kleinrock:
When we speak, we are silent about one-third of the time, which is acceptable for voice communication. But with data communications you are silent more than ninety-nine percent of the time. You hit a key and wait. An eternity later you hit another key. The communication links supporting that kind of interaction are idle almost all the time.
Vardalas:
Yes, those lines are being wasted.
Kleinrock:
In data communications we cannot tolerate such inefficiencies. I had to find a way to share these resources. The same problem occurred with timesharing. The way we originally used computers in the very early days was such that a person would sign up for an hour or five hours at a time. That person would sit there and say, "Hmm. Why is the program not working?" and try to solve the problem. Meanwhile the machine would be sitting idle. Timesharing fixed that problem by observing that, "While one person is idling, others could be working, so let's find a way for organizing and scheduling people so they can share that machine." The same idea was apparent to me for letting computers talk to each other. When I am not using the communications line let someone else use it. The key idea I came up with was the idea of dynamic assignment or demand access. You don't get the channel until you need it.
Vardalas:
What was Shannon's reaction to this?
Kleinrock:
He was quite excited by it. However, Shannon was not my supervisor. He was, however, on my committee.
Vardalas:
Who was your supervisor?
Kleinrock:
Someone you probably never heard of, namely Professor Ed Arthurs. He had been consulting on a classified project about which he could reveal nothing except that it involved the problems facing computer-to-computer communications. His interest in this problem was keen, and so I began to work with him. While at MIT, he graduated only five Ph.D. students: Irwin Mark Jacobs, Ed Hoffstedder, Jack Rosenfeld, myself, and Hersch Loomis, in that order.
Vardalas:
What happened?
Kleinrock:
He left MIT after a few years. He was a brilliant researcher, but he chose to leave MIT and go to Bell Labs. He was full of hundreds of ideas. Working with that kind of a mind was just wonderful for me. Another professor on my committee was in the area of operations research; his name was Herb Galliher. I asked myself, "If I am going to study a system that uses demand access to decide which message gets to use a resource, and have messages wait for their turn to use a resource, what tool should I use to analyze how the system behaves?" The answer was the theory of random processes. That came out of my exposure to Shannon’s legacy of looking at things statistically. The right tool for me was queueing theory, a branch of random processes. I have never taken a course in queueing theory (yet, later at UCLA, I wrote a widely used two-volume series on the subject). However, I did come across a book on the subject written by Philip Morse. He wrote a great book on queueing theory called Queues, Inventories and Maintenance. It was somewhat theoretical, yet application oriented as well, and I said, "This looks like just the right tool to model and analyze computer networks." Queueing theory is about response time, throughput, storage, buffering, assignments and priorities – just the metrics I needed in this dynamic environment where data messages are going to compete for channels, awaiting an assignment of who uses the channel and when.
Kleinrock:
Queueing theory was mostly about one channel. But I was interested in a network of channels. I said, "Well, how is this resource sharing or demand access going to work? There were going to have to be queues in front of each of the intermediate switching points. I wondered, "Are the queues going to blow up? Will this work? Will things get bottlenecked, deadlocked and grid-locked?" I decided I had to prove that this thing would work – if it would. Therefore I developed a model using the fundamental principle of demand access, i.e., if I am not using the channel then someone else on the queue can use it. A queue is a perfect resource-sharing device for use in the demand access environment which I was creating.
For instance, picture a queue of messages or packets waiting to use a server (i.e., a data channel). The server will accept messages in a first come/first serve order, for example. It will always serve something if there is anything to be served. In the case of telecommunications, a data channel will not remain idle waiting for the arrival of a message that is far away in the network. Rather, it will serve whatever is in its queue at the moment. That way, the server will be used whenever there is work to be done. That is not the case in the telephone network, which lies idle during silent periods. A queue perfectly uses its server. (Some of the problems I am working on now have the complication that one does not know who is on queue. If you do not know who is on queue, how do you schedule them? That question leads directly to what we now call multi-access communications.) The idea is that in a wired network – which was the case in those earlier days – queueing seemed to be the right method to use. Moreover, a priority queueing rule, i.e., a rule that decides who gets served next, is very important. I wondered, "Will the queue explode, i.e., will it grow excessively?" Therefore I made an analytical model, which was basically a model of a network of queues. Then I analyzed it and I found design procedures to answer questions like, "Where should the capacity be allocated? What should the routing procedure look like? What should the topology look like?", etc . Then I optimized the design. If you want to minimize delay with all those variables, what do you do? I formalized and solved these problems.
Vardalas:
When you were designing this process, was the research for your thesis one step at a time? Did you run into a lot of dead ends, or did it work very nicely for you?
Kleinrock:
There were dead ends. First, the model itself. When I work, I tend to get little pieces together, and then they form the whole, rather than taking a clean sheet of paper and saying, "Let's see, I want that goal and I will carefully do it this way." I tend to work around the problem at the edges more, poking here and there to get into it. I started doing that.
One thing I learned at the Massachusetts Institute of Technology, which was a surprise to me, was that most of the research is done by graduate students. Before that I thought that the professors did all the research. The wonderful thing with the graduate students, was that when they would get results they would tell their classmates about it. "Look, I've got this new result here" – something in coding theory, something in communication theory and so on. Until one gets that first successful result – like my experience achieving Eagle Scout – one wonders if he or she can do it. One keeps working and gets a research result and then discovers, "Oh, somebody else already got that result. It is in the literature already." However when that starts happening you know you are getting close. I finally got my first new analytical result, which addressed whether there should be separate servers or a single server to serve a collection of demands. A single server was better for some very significant reasons. It was a new result of some importance and I was very pleased. I began to piece together what the nodes of this network would look like. Then I developed this overall model of a network of queues. The problem there was, I could set it up in a mathematically exact fashion, but I couldn't obtain the exact solution. I could not solve it because there was a significant amount of dependency among the queues. If you know anything about queueing theory, it involves people arriving, waiting in line, and after they get served, they leave. Their arrival times are statistical. Their service times are also statistical.
Most of queueing theory assumes these two are statistically independent. That is, the time of arrival and the amount of service needed are usually assumed to be independent of each other. That is not the case for data networks. In data networks if there is a long message the amount of time it takes to arrive on one data channel is related to how much time will it will spend being serviced by the next data channel as it makes its way along a path in the network. They are directly coupled. Looking at that problem, it is really hard. That problem still has not been solved today. I said, "I have to make an approximation if I am to proceed." Again this came from Shannon's legacy. He made approximations and he put bounds on things. He would say, "Let me make an approximation." Therefore I made a critical approximation called the Independence Assumption.
It turns out that by making that assumption the problem cracks wide open. Without that the problem is impenetrable.
Independence Assumption and packets
Vardalas:
Did this come to you in a flash or did you get to it by necessity?
Kleinrock:
I knew I could not get any further without it. In fact in my dissertation there is a whole chapter devoted to the problems of finding the exact solution. Transform equations can be set up; they just can't be solved. I said, "Let's step back. What would make this work?" It occurred to me that this became the equivalent of something a researcher named James Jackson has already solved in 1957. He had solved the problem of analyzing what he called networks of queues. However, in order to apply his results, it was critical for me to introduce my Independence Assumption. Once I applied that assumption, the problem just opened up. Then I could use a network of queues model for the analysis part. That in turn led me to the design technology, which came later.
Vardalas:
What does this independence mean exactly? I think of some parallels I had in my own graduate work, which was in large statistical mechanics. Sometimes you break complex many-particle distribution functions to single-particle distribution functions and separate them out.
Kleinrock:
Right, and you assume they don't interact.
Vardalas:
Is this kind of two pointing reduced to one pointing? Is that what you did?
Kleinrock:
I would not describe it that way. Here is exactly what I did. I said, "Even though there is coupling between when a message or packet arrives and how long it spends in service, let's assume that the arrival time and service time are independent." In other words, assume that each time a message arrives to a new node, its length is chosen again at random. Of course, the assumption is wrong, but it turns out that the assumption is okay in the sense that it yields a model that does an excellent job of predicting network performance. The way I proved this was by doing extensive simulations running the exact system (with no assumption) and then comparing that to simulations in which the assumption was used. The results were almost identical. The reason is very easy to understand.
Consider a server to which messages are arriving. If a long message arrives followed by a short message, then the interarrival times will be proportional to the size of the long message; note also that the long message will also have a long service (transmission) time in this server. That is, the interarrival time and service time are correlated. However if there are many ways into this node from other links, then the order in which messages get served is not necessarily the same as the order in which they arrived. A short message could sneak in front of a longer one since the longer one might not be fully received by the time the shorter one arrives. In this way, the dependency between the inter-arrival times and the service times is drastically reduced. The inter-arrival times come from messages arriving from many links. Moreover, if the messages are choosing output paths over many links, then any given link will not necessarily see the same outgoing stream that arrived on any single incoming link. That is the physical reason behind the intuition. If there is any kind of richness in the topology the dependency will reduce dramatically.
Vardalas:
Were you convinced from your simulation that it would scale up?
Kleinrock:
My architecture was designed to scale up. That was important. One key ingredient was to introduce distributed control in the network.. In my research, I addressed the issues of scalability, performance evaluation, large network design, distributed adaptive control, hierarchical routing, shared resources, demand access, packetization of messages, and the advantages of large shared systems; additionally, I uncovered the underlying principles for the behavior of these networks. In summary, these were the basic principles I applied: (1) resource sharing demand access; (2) distributed control; and (3) the recognition that large shared systems are far more efficient than small shared systems. As an example of the third point, consider a hundred people sharing an amount of capacity equal to X. If, instead, we had a thousand people sharing a capacity of ten X, then the performance is ten times better in terms of response time. That is not intuitive, but I was able to prove that exactly – and it was a revelation.
Vardalas:
All right. Bigger is better then.
Kleinrock:
Bigger is better. Most queueing theorists do not know that result, because they don't think you can speed up a server. If it was a human server, it is true that you cannot speed up that server. But in a network, it is not a human; it is a communications link. If you add more bandwidth, you can indeed speed up the transmission. There is an assumption behind it, but it is a very effective assumption.
There is one other thing I did which is really important. I studied the effect of the order in which things are served and investigated a number of priority queueing structures, because I wanted to make sure that the flow went well. Importantly, I was the first to publish the concept of chopping a message up into small pieces and serving each small fixed-size piece one at a time. The theory behind that was, if there is a long message in front of a short message, we do not want the long message to hold up the short one – just like in timesharing.
That is why timesharing works, by the way. In timesharing you get a time slice and then you go to the back of the queue. You would like the shortest jobs to be served first in these systems. That turns out to be best in terms of overall delay. However, you do not know which are the shortest jobs. By “packetizing” messages, you allow them to expose how short they are.
Vardalas:
Does breaking it up into packets reinforce the independence assumption?
Kleinrock:
Of course it does. That is exactly right. That is, if you consider the end-to-end behavior, where the pieces of the message are put back together again, you find that they have been through so much mixing that the ergodic theorem predicts that the dependence will be gone.
Again, some of this thinking came out of being around Shannon.
Influence of Claude Shannon
Vardalas:
Did you have interactions with him as you were doing this work?
Kleinrock:
Yes, a lot. In my book you will see reference to an interesting result I obtained one day. It was a very complex problem and the answer turned out to be very simple. I walked into Shannon's office that day as soon as I got the result and asked him, "Why does it turn out so easy?" In two minutes he had it. He had not even seen the problem before.
Vardalas:
Was it easy to work with Shannon? Was he the kind of man with a really open door?
Kleinrock:
Very easy. I won't say he was critical, but he would not easily give praise. He was very objective. The highest praise he ever gave me was, "Now you are cooking with gas." I could not have been more thrilled. He was very reserved. He had a good sense of humor but did not laugh much. He was a very interesting person. He was a juggler, you know. Shannon was even able to balance himself on a board which itself rested on top of a wobbly bowling ball. Rumor has it that Martin Minsky fell down and broke some bones when he tried it. In class while lecturing, Shannon would repetitively and nonchalantly flip a long piece of chalk in the air and catch it. However when he had to do arithmetic, for instance 45 times 13, he would use long multiplication. He was not a mathematical or arithmetic whiz in that sense, but he was just creatively brilliant. It was amazing to watch his mind work.
Vardalas:
He was very crucial for you.
Kleinrock:
Yes, he is my role model to this day. He had the ability to look at a problem, understand the physics of the problem, come up with a very clever approach to figure out what the answer is probably going to be, and then do the mathematics to prove it. He was awesome at balancing those two worlds.
Vardalas:
You say he also lived in a world, in terms of his models, of the law of large numbers.
Kleinrock:
Exactly. Limit theorems. Go to the limit. Go to extremes and find the boundaries.
Vardalas:
I see. Very interesting.
Kleinrock:
He was wonderful.
Vardalas:
When I was in graduate school and doing statistical mechanics, entropy could be represented as information.
Kleinrock:
Yes. Amazing result. How did he get to entropy? He said entropy should have simple three properties. One property was that the more equally likely choices you have, the more the uncertainty. Secondly , entropy should be continuous. If you change one of the probabilities a small amount, the entropy should not change much. The third was composability. For example, consider a three-sided coin which, when tossed has a probability of a half, a quarter, a quarter for each of the sides coming up. The entropy of a single toss of that three-sided coin should be the same as a fair two-sided coin tossed as follows. Toss it once; if it comes up heads, that is one outcome and has probability of one half. If, instead, it comes up tails, toss it again; now if it comes up heads, that will have an overall probability of one quarter, and the same for the second toss coming up tails. If now we put either the three-sided coin in the box and toss it once, or put the fair coin in the box and toss it up to two times, the entropy of either experiment should be the same.. Those three simple and obvious properties lead directly to a unique definition of entropy as Σ-pi Log pi.
Vardalas:
That's very interesting. In physics you get it through large numbers, energy distribution and other things.
Impact of computer networks research; industrial resistance
Vardalas:
I was looking at your presentation in 1999 to SIGCOMM, the special interest group communications. In it you said the telecoms could care less about the work you did at that time.
Kleinrock:
Yes.
Vardalas:
Would you elaborate on what this meant to you? This is a typical iceberg or something.
Kleinrock:
Okay. I am going to answer you a little bit differently. I am going to start someplace else. We are getting now into the impact of this work. There were two independent developments.
One was my work at Massachusetts Institute of Technology which I have described above, along with independent developments by Paul Baran and Donald Davies. In the early 60’s, Baran of the RAND Corporation was busy working on military communications with the goal of using redundancy and digital technology to design a robust communications network. He also introduced the use of standard-size addressed message blocks and adaptive alternate routing procedures with distributed control. This work was done independently of the work that I had done at MIT, and in many ways the results we achieved in addressing the problem of packet networks were complementary. In addition, Davies of the National Physical Laboratory (NPL), UK, began thinking about packet networks in 1965 and coined the term “packet” that year; he later described a design for a public packet-switched data network. These were the three key threads of researchers, each of us having developed elements of the technology of packet switching independently.
The second development was a result of the 1957 launch of Sputnik which precipitated the creation of the Advanced Research Projects Agency (ARPA) in 1958. Among other things, ARPA started funding research in computers. In 1963, they officially formed a computer science research group. J.C.R. Licklider was the first Director of that computer research effort; he had also been working at MIT. Licklider had a vision of an intergalactic network, in which he envisioned a series of connected computers linking everyone to a universe of information.. He articulated his ideas in a 1962 paper but did not offer a plan to implement such a system. Meanwhile at MIT, by that time I had already laid out the exact technology to do it, but neither of us knew about one another until a little later when ARPA decided to develop a computer network. Ironically, the combination of our work had laid the foundation for the technology and application of the Internet – something that would not be realized until years later.
Now getting back to your question specifically, my experience was that I had created a mathematical theory of packet networks at MIT and came to the University of California at Los Angeles ready to extend and implement it. In those days we had the Spring Joint Computer Conference and the Fall Joint Computer Conference. These were very large events. At every one of those meetings there would be a plenary session with a panel of experts. On the panel were computer folks like myself and telecommunication folks like AT&T [American Telephone and Telegraph], and we discussed this issue of data communications. I would kick it off and say to the telephony folks, "Please give us good data communications. We want to connect our computers together." They would say, "What are you talking about? The United States is a copper mine full of telephone wires. Use the telephone network." I said, "No, no, you don't understand. It takes twenty-five seconds to dial up a call, there is a charge for a minimum of three minutes, and I only want to send fifty milliseconds of data." They refused to consider this as a valid concern, probably because it was a disruptive technology and they saw no obvious revenue in transmitting data; it was all in voice at that time. Well, I had no choice but to develop packet switching networks with the support of ARPA and without the cooperation of AT&T.
In more private discussions they said, "Look, this thing is not going to work, and even if it does work we want nothing to do with it." It was competitive and threatening to them – and lastly, economically there was no market for data communications at the time. Remember this was the early 1960s. It was very frustrating. Finally an opportunity came when ARPA decided to create the ARPANET.
Vardalas:
Was this the first opportunity for you to apply your ideas in a real way?
Kleinrock:
Yes, besides the simulation I had done.
Vardalas:
If ARPA had not been formed would your ideas have languished a lot longer?
Kleinrock:
I don't think so. They were building a packet switching network at NPL in England and actually were building a one-node network (which is like an oxymoron). However the UK decided not to continue funding it.
Military interest, ARPANET
Kleinrock:
Meanwhile, in the United States, people were seeing the need for data networks and the military was getting very interested in them. The military wanted secure communication networks. Data networks would have come along eventually, but ARPA accelerated it at just the right time in just the right way. It was a perfect match for me.
Vardalas:
There is a lot of discussion about the military's preoccupation with this data network and to what extent military preoccupations gave birth and sustained the ARPANET model. I get the impression that for the military, redundancy in a communication system was primary concern. Is that true or not? By redundancy I mean not losing everything at one node or two nodes.
Vardalas:
Can you recast their interest in this whole thing?
Kleinrock:
I will give you the pure story first and then some of the embellishments. The Advanced Research Projects Agency was formed and started funding research scientists in the computer area. They would go to a faculty member at a university and say, "Let's do some research. We will fund you for it." The researcher would say, "Buy me a computer," and they would buy the researcher a computer – typically a PDP-10 or something like that. At the University of Utah that machine would become an excellent graphics machine, because that was what they were doing there. At University of California Los Angeles, we worked on simulation and modeling; at SRI [Stanford Research Institute], they focused on database applications; at the University of Illinois, it was high-performance computing. As ARPA began to fund these research projects these centers of excellence developed. Then they would go to another new researcher and agree to fund the research. The researcher would say, "Fine. Buy me a computer," and they'd say, "Fine. I'll buy you a computer." Then the researcher would say, "In addition, I want a computer with all the power the other guys have – the graphics, the simulation, the modeling, the database and the high performance." ARPA said, "We can't afford to do all of that."
That's the first thing. Meanwhile at ARPA, Bob Taylor was running the funding for the computer research. He was using one terminal to connect to one computer at, say, the University of Utah and another terminal for another computer elsewhere. There were too many terminals that were independent, so the realization came to him that, "Let's put these computers in a network." If you want to do graphics you log onto the graphics machine through that network, etc., that is, let’s share the resources of the applications. The thing that drove Bob Taylor at ARPA was resource sharing. It was not the need to support a military network.
You can only imagine what he told the people above him at the Department of Defense (DOD), but I am guessing that it did not affect anyone below that level. I don't know. It would have been reasonable for him to say, "This network will be great for military communications. It will be a reduction in cost for operating networks and it will be resilient and redundant."
Bob Taylor needed someone to manage this kind of network. He went to my old classmate Larry Roberts, about whom I talked before, who was still at Lincoln Lab. Larry Roberts got his Ph.D. in the same Staff Associate program as did I and at the same time. ARPA wanted him to come and work on this. Larry was intimately familiar with what I had done. We were literally officemates. However, Larry did not want to go. They finally convinced him to come by threatening to take funding away from Lincoln Lab.
I remember sitting with Larry in his Volkswagen in Lexington, Massachusetts, in the snow. He said, "Len, they want me to go and I don't want to go. Should I do it?" I said, "Look Larry, take a chance. If you don't like it, return to Lincoln Lab." By the way that was exactly what Lincoln Lab said to me. When I finished my Ph.D. there was no pressure to stay at Lincoln Lab. They really wanted to train people and allow them to take a position anywhere they chose. However they were very happy and gratified when people stayed there. They said to me, "Before you stay here, look out there. See if there is something else you want." "Try it. If you don't like it, come back." Therefore I interviewed for a number of different positions, including UCLA where I accepted a position. After joining the faculty there, I found that I really enjoyed it and so I advised Larry to try the position at ARPA. He took my advice.
When he went there, the first thing he did was bring a bunch of us together in 1967 to try to specify what this network would do. At that meeting, we created a number of specifications for the network. One of the things we insisted on was that it be fault tolerant. We brought that in because we recognized that the switches and/or links might fail, and we wanted this network to be running for applications. To accomplish this, we built what is called a two-connected topology in which there had to be two independent paths between every pair of switches. That meant that if any link or switch breaks, everything else continues to work. It is very easy to build such a network, and we could have made it three-connected if we chose. We were not doing it for military purposes at all. None of us. The belief that we designed this network for military purposes is an absolute myth.
Early work on ARPANET; "the infant Internet"
Vardalas:
Okay. Your website is very good on this aspect of the early days of how the first node was set up. I am sure there was a lot of exhilaration and enthusiasm at that time. Looking back on those days, thirty-five years later, what do you retain as your most vivid memories of that whole early experience?
Kleinrock:
I just wrote a paper on that subject which is not yet published. It's on my website and can be found at http://www.lk.cs.ucla.edu/PS/paper224.pdf. It's called "The Internet Rules of Engagement Then and Now." The question I pose there is, "Looking back thirty-five years, what could we have done then in establishing the rules of behavior and engagement which could have ameliorated some of the problems we are seeing today?" and "If that is the case, what can we do today to fix things?" I go back and look at the early vision and understanding and the culture at that time and then take a bold look at today. I think it is an interesting read, because it addresses these issues. The excitement back then, first of all, was that to create a data network was a huge engineering challenge.
Vardalas:
That could be lost in today's world because people take it for granted. Could you recreate that feeling of the challenge that it was at the time?
Kleinrock:
Okay. I had already laid out the theory and the technology of packet switched networks. However whether it would work in practice, how much it would cost and how it could be implemented, deployed and used were big questions. Plus we added new things. The theory was fine, but many details had to be worked out, such as the specific details of some of the algorithms. Distributed routing algorithms were the key to scalability. That was very important. Would this thing really be stable? The simulation showed it, but we had to get it out there and see since things fail in strange ways.
After creating the specification we sent it out as a Request For Proposal. BBN [Bolt, Beranek, Newman] won the contract shortly after Christmas of 1968. They had eight months to deliver the product. There is no way any organization today could deliver such a new technology on such a massive scale in eight months and make it work.
Vardalas:
Did you know that then?
Kleinrock:
No, we didn't. We just believed it could be done.
Vardalas:
Obviously you believed it could be done in eight months.
Kleinrock:
Sure. Why not? I understood what had to happen. We simply had to do some hard engineering. Understand this was a research environment. Therefore it did not have to be bulletproof. It did not have to serve a population of users who were going to complain. We were all in this together. I put together a group of 40 people consisting of Ph.D. students, software engineers, and hardware engineers. The Ph.D. students and I were developing algorithms, and conducting analytic, design and measurement studies. To the software group of graduate students I said, "Look, we need a host-host protocol. Here's the idea. Go do it." That was the culture in which we lived. I extended the idea of distributed control to the management structure and fostered the idea that no one person should be in control of everything, that everybody shares, just as every node shares; that same philosophy had been initiated by ARPA in that they said to their researchers, "Here's money. Go and make a network. We are not going to tell you how to do it. We trust you. Go make it happen." They had complete confidence in us– no project meetings, no reports, just "Give us an end result." The researcher receiving that kind of trust and flexibility would give the same thing to the students. "Go ahead and do it. Here's our big plan. Report back to me as you're moving along." It was this idea of shared culture, everybody participating, cooperating, no hard lines of authority, no hard lines of accountability and doing it as a group, that it made it successful and exciting. The graduate students across the country formed their own group. They formed their own network working groups and created their RFCs [requests for comments] . It began to come to life. Meanwhile BBN [Bolt, Beranek, Newman] was back there in Cambridge putting together this minicomputer (i.e., the packet switch, which was called an Interface Message Processor – IMP), implementing the software and the hardware.
On the Labor Day weekend of 1969, the machine arrived, a little ahead of time. We were all scrambling for those eight months to make this thing work. BBN was building the switch (IMP) and we had to build the IMP-HOST protocol. On September 2, 1969, the day after Labor Day, we connected the IMP and our UCLA Host computer, and we began to get bytes traveling back and forth. I like to refer to that day as the day that the infant Internet took its first breath of life. This first piece of networking equipment first became aware of the outside world as it sent bytes to our timeshared computer that was serving the computer science population at UCLA [University of California at Los Angeles]. However we were not all that smart about it. We did not have a camera or a tape recorder. We made no physical record of that day.
Vardalas:
You have just your memories.
Kleinrock:
Just our memories. There was so much excitement in making it happen. It worked. We plugged it in and it sent the bytes back and forth. A month later in early October, another switch, an IMP, was delivered to Stanford Research Institute (SRI) in Northern California and later in October, they connected their IMP to their host computer.
Toward the end of October we had our host connected to our IMP which connected to the first link of the backbone network (connecting us to SRI), connected to the SRI IMP and finally to the SRI Host computer. We wanted to log in from our host to their host to send the first Internet message. As you might imagine, this was a momentous event. What did we send? You know the story.
Vardalas:
Log in, right.
Kleinrock:
When Samuel Morse sent his first telegraph message, he chose to send "What hath God wrought?" How do we know that? He was very smart and he recorded it. It was a big event.
Vardalas:
He was PR conscious.
Kleinrock:
Exactly – and we were not. We were simply naïve engineers and researchers. We didn't plan a media event.
Vardalas:
He was trying to get investors and you weren't.
Kleinrock:
Yes, that's right. We were really naïve. We were thrilled, but we didn't break out the champagne. We just said, "Okay. That's good. Let's go on and do the next thing."
Vardalas:
What year was this?
Kleinrock:
This was 1969.
Business models and early computer networking
Vardalas:
At the same time there was a whole frenzy around the computing utility since 1965. It started with Fano’s first comment about a computing utility based on a regulated monopoly.
Kleinrock:
That's right.
Vardalas:
That concept. A lot of companies jumped on the bandwagon. There was an investment frenzy over this from 1965 to 1970.
Kleinrock:
Right.
Vardalas:
I am wondering about your interpretation and the time when all these people were running off and forming these little computer utilities – Tymshare, Control Data Corporation, Cybernet, and various others. BBN [Bolt, Beranek and Newman] was involved in it.
Kleinrock:
That was the era of big time-sharing utilities.
Vardalas:
It was a hierarchical kind of thing.
Kleinrock:
Right. Terminals connecting to a centralized computing facility.
Vardalas:
Right. That was it. What did you think of that at the time it was happening? Did you think, "This is the wrong way to do it"? What were you thinking?
Kleinrock:
It made sense for locally connected terminals, but connecting terminals over long-distance links to a facility was absolutely wrong in my mind. You want a boundary called a network and you just want to attach to the network edge. Then the network can connect you to whatever utility you want.
There is a press release on my site where I articulate my vision of what networking would become. The important thing is that the press release was sent out on July 3, 1969. That was two months before the first connection was made. People always ask me now, "Did you see it coming?" and "What did you see then?”. In that release, I described what the network would look like, and what would be a typical application. I am quoted in the final paragraph as saying, “As of now, computer networks are still in their infancy, but as they grow up and become more sophisticated, we will probably see the spread of ‘computer utilities’, which, like present electric and telephone utilities, will service individual homes and offices across the country.” I am pleasantly surprised at how the ‘‘computer utilities’’ comment anticipated the emergence of web-based IP services, how the ‘‘electric and telephone utilities’’ comment anticipated the ability to plug in anywhere to an always on and ‘‘invisible’’ network, and how the ‘‘individual homes and offices’’ comment anticipated ubiquitous access. However, I did not foresee the powerful community side of the Internet and its impact on every aspect of our society.
Vardalas:
A lot of people at the time did not recognize that, because they were spending all their money on it. There was a business model based on a regulated monopoly.
Kleinrock:
That's right.
Vardalas:
As soon as you see the words electrical utility or telephone, it is clear that their mindset was not aligned with what you were doing.
Kleinrock:
Not at all.
Vardalas:
There was a conflict because the business models would drive the technology.
Kleinrock:
Right. That was not the intention of my using the phrase “computer utilities”. I was thinking of services that would be received.
Evolution of Internet business models
Vardalas:
Okay. I rarely get a chance to ask someone of your position this question. When the Internet really took off – in the 1980s and early 1990s, when people were really talking about it, there was a belief that it would lead to a very democratic flat kind of world and that there would be local computational power everywhere and everyone would kind of share and link up. Things moved way back since then.
Kleinrock:
To a centralized service.
Vardalas:
Yes, to a very centralized service. It is like a computer utility, but more sophisticated. Now applets are being dropped down. Before the computer utility one wanted to buy computational time on your computer, but now I get the applet coming to me.
Kleinrock:
That's right.
Vardalas:
I am curious as to how this evolved – the business model of the Internet today versus how it was before.
Kleinrock:
Right now there are two competing models. The antithesis of that is the peer-to-peer model. The bad example is the Kazaa network where people are illegally sharing music files. It is all done client-to-client in a very distributive fashion. There is great value in that model where we can share our end devices collectively. I hate the idea of stealing music. I think that is wrong. However the idea of sharing ideas, files and other applications we want to distribute which are not copyrighted is excellent. That is opposed to the highly centralized service. There is a need for both, by the way.
A Google search engine cannot be replicated everywhere. They need the power of all those machines in one location. They may need to replicate that in one or two places, but not in a hundred million places. Clearly there are reasons for both. I like the idea of power out at the edges. Intelligence at the edge. That is very important.
And yet the telephone network is a smart network unfortunately. It does things internally. That's why they could hold off attaching devices for so long.
There is still a move to make intelligent switches in the network. The power of the Internet comes from a variety of sources from the original ideas of open access, open research, shared ideas, trust in your fellow community of people and the ability for many people to communicate with one another. That led to the seven-layer model, as you know.
The seven-layer model can be viewed as an hourglass. This is articulated in a report I chaired for the Computer Science and Telecommunications Board of the National Research Council in 1994 called "Realizing the Information Future: The Internet and Beyond." It recognizes that the way the architecture is set up there is a very narrow waist to this stack that is called Internet protocol (IP). IP is a very simple set of agreements everyone makes. If you are going to join the network, you obey the IP – which dictates the way addresses are defined and specifies a particular quality of service which happens to be best effort in the Internet. Anyone who meets that standard can play on the Internet. That means that anyone with an underlying communications technology at the lower layers of the architecture can offer that service to any application at the higher layers through the intermediary layer of IP. That is, any application can say, "I need this bandwidth, with this delay tolerance, this delay jitter, " etc. “Can anyone down there offer it?” “You have it? Fine, I'll connect." It's a many-to-many negotiation, rather than a stovepipe service as, for example, had been a paging network for a cellular pager that used to say, "I'll sell you the network, I'll sell you the service, I’ll sell you the device and all you can do is send paging messages”. That was not a good idea. That pager network should have been able to be used for email and other services. Now such networks have much broader uses. This is providing far greater simplicity and flexibility in the network. It is a bad idea to add a lot of weight and rigidity to services because if you do, you might preclude other applications that want to use new technologies which have not yet been invented.
The idea of simplicity, dumbness and things being well defined is very important; it is the end-to-end philosophy.
Vardalas:
Okay, I see. You said there is a need for both views of the Internet – simplicity in the middle and intelligence on the fringes and then some intelligence in the middle.
Kleinrock:
The intelligence is not in the middle. It is on the edge. It is a big resource outside the network.
Vardalas:
I am thinking about the other case of bringing some intelligence into the switching circuits.
Kleinrock:
I think that is a bad idea.
Vardalas:
Or big servers or big centralized things?
Kleinrock:
No, no. I think of big servers as being outside the network core, not in the switching servers, but in the application servers.
Vardalas:
You have doubts about putting intelligence in switching servers?
Kleinrock:
I do not think you should put increased intelligence inside the network. When you look at photonics the core network is even simpler. With wavelength division multiplexing, you get a straight pipe right through the network. You don't want anything to happen in there. You don't want to do any kind of fancy compression. If you want to compress something, enhance it or render it, do it at the edge.
Vardalas:
Do you see possible conflict between this technological model you have of the Internet and various business models for profit like ISPs, the telephone companies merging and so on? I notice that you see peer-to-peer.
Kleinrock:
You need to balance business models with customer acceptance with the long-range implications of architectural decisions.
Vardalas:
Yes. So where is the money to be made? Will business models impose some kind of restraint on the technological model?
Kleinrock:
Yes they will. Market forces always apply, but the two sides of the market are users and suppliers and you must allow an equilibrium to be reached. These days most of the industry is in the game of applying intelligence at the edge. The whole last mile access problem is there. I want to also talk about nomadic computing if we have a minute.
All these services are at the edge. There is little need to put them internally. You can try to put them internally, like active networks, and there is some functionality that can be imagined there. However I like to think of them as outside the network. That means that you don't have to use that intelligence, you can get a straight-through pipe, you can get end-to-end encryption and end-to-end functionality without that internal manipulation.
Influence of data networks on society
Vardalas:
Data networks have come a long way since what you did in the 1960s. Looking back, are you surprised at certain twists and turns it has taken? Has your work been applied in ways you never anticipated and that really surprise you?
Kleinrock:
I talked about the vision I articulated earlier – that the Internet would be everywhere, always on, always available, and anybody with any device could get on at any time from any location, and it would be invisible. What I did not see clearly was that it would reach out to all aspects of society.
Vardalas:
You didn't see it becoming a mass consumer phenomenon.
Kleinrock:
Right. What I did not realize back then was that it was not about computers talking each other; it was about communication among people and communities. When email was first introduced on the Internet in 1972, it surprised everyone and quickly dominated the network traffic. Then I said, "Ah. This is not about machines talking to one another, it's about people talking to one another."
That has been the case ever since. The bigger surprise is what I like to call the dark side of the network: pornography, pedophilia, denial of service, invasion of privacy, theft of identity, spam, viruses and worms. That bad side of the network affects what takes place on the network. Originally the philosophy was that we trusted people on the network. We did not put in protective mechanisms against malicious use. We put in protective mechanisms against failures but not against evil-minded use. It was an open community. The thing that allowed the network to grow the way it did was this openness, sharing, collective use, free access and easy access. That is also a perfect formula for the dark side, because now one individual can reach millions of people easily, cheaply, and anonymously – the Internet gives you can enormous amount of anonymity – and opens up the door to all these other things.
That is a twist I did not anticipate, and it didn't happen until the mass market came in. The first worm was launched in 1988, created by Robert Morris; the first large scale and purposeful spam was released in 1994 by Cantor and Siegel.
Reasons for Internet growth, 1980s-1990s
Vardalas:
It seems like it happened when it left this trusting community and went out to the world.
Kleinrock:
When it went out to both the dot-coms and the consumer. That's right. There are three reasons why the Internet traffic exploded on the world stage in the early 1990s. (1): In the early 1980s the National Science Foundation started funding large supercomputer centers in the U.S.A. Then toward the late '80s – and you probably got involved with that some as a physicist – they wanted to connect them together to support some large-scale remote applications. NSF took over support of the Internet backbone in 1986 which then came to be known as the NSFNET. The Internet's backbone speed was not high enough. The initial speed of the NSFNET was 56 kilobits/sec. It was upgraded to 1.5 megabits/sec in 1988 and then to 45 megabits/sec in 1991. When they started connecting these supercomputer centers together that meant that no longer were just computer scientists, but all of the NSF researchers were members – this included physicists, biologists, chemists, oceanographers, geologists, etc. This larger community began to have access to the Internet. The community had now expanded way beyond computer scientists. These people worked not only in universities but also inside the research labs of large commercial corporations in industry, for example IBM Research. Guess what these commercial enterprises were using the Internet for besides file transfer? Email! Do you think email is going to stay hidden in the laboratory setting of a larger corporation? Heck no. The sales force, the managers the marketing people and the general staff said, "This is great." They started using the Internet services. It was toward the end of the 1980s when this happened that the dot-coms began to appear. This toy of a flexible network began to be perceived as an interesting tool. Commercial organizations got interested, first of all. (2) The second thing that occurred was that the backbone net was upgraded to very high bandwidths. In the late 1980s, Senator Al Gore was one of the few statesmen who supported the Internet. One of the first reports I chaired for the National Research Council’s Computer Science and Telecommunications Board was called "Towards a National Research Network." In that 1988 report we promoted the idea of a very high-speed network to support research and education. Gore was a strong proponent of gigabit networking for the government. He got the then-President [George H. W.] Bush to sign as his last act, the High-Performance Computing and Communications Act of 1991 which funded the gigabit test beds out of which came asynchronous transfer mode (ATM). They got universities, industry and government to work together. (3) The third and most critical thing was that the Web appeared in 1993. The Web provided a user-friendly graphical user interface to the Internet. Those three things: the recognition of the Internet by the commercial world, the high-speed backbone to support the communications and the introduction of the Web, were the critical enablers for the worldwide spread of Internet use. That is when it hit the consumer world. All of this must be acknowledged along with the fact that the Internet has been growing exponentially since the earliest days of the ARPANET.
Significance of Kleinrock's work in communications history
Vardalas:
I see. Have you ever given any thought to where your contributions fit within the grand scheme of communications history? Let me put it differently. How do you think future historians will situate your life's work within the story of 20th century communications? Is that too grand a thing? Have you ever thought about that?
Kleinrock:
I think about what this century has brought. The Internet is just one more important development in a long sequence of developments going back to Maxwell and Marconi with wireless and telephony. I often think about how fortunate I am to have contributed to the founding of this important technology.
Vardalas:
Do you see your work as being a natural continuation or a new start to something?
Kleinrock:
I would say yes to both; it is a continuation of important technological breakthroughs and it has initiated a new age of communication. I think the Internet is important not only for its technology – which was important – but also for how it has changed society. It has had an impact on education, work habits, consumer habits, social interaction, marketing and selling. It has had an enormous impact – just the way the automobile had an enormous impact on the way we lived and as did the telephone.
Kleinrock:
The impact will be large, and my work is just one piece of the Internet story. I contributed to the underlying technology, some of the philosophy, put together the first node and then was in charge of launching the first Internet message. Beyond that, there has been the Web – which was dramatic; TCP/IP was a critical development; as were the powerful and often unanticipated applications which continue to surprise us. We are in the Stone Age of the Internet. We have yet to see where future generations will take it.
Bandwidth
Vardalas:
You said you always like to push things to the limits like Shannon – looking for limit theorems and things like that.
Kleinrock:
Right.
Vardalas:
I was looking at your article about latency and bandwidth. Not being an expert in this, I could be naïvely going off in the wrong direction, but one of the things changes wrought was cheaper connectivity, more and more connectivity. Have you thought about what will happen if bandwidth stays approximately the same or is reaching pretty high? With the optical bandwidth, optical networks, if you push the number of users or data moving through a system and the number of nodes to higher limits, do you envision that things will keep going nicely or will it run into problems?
Kleinrock:
One barrier we hit and which will only get worse as the bandwidth increases, is that we are bumping against the speed of light. That's an essential problem. As a result, we are always looking for latency hiding mechanisms.
Vardalas:
Will that get worse as the number of nodes starts going toward infinity?
Kleinrock:
It will get worse as humans get out of the loop. I anticipate that most of the traffic on the Internet will not be generated by humans but will be generated by intelligent agents and intelligent devices in our environment. This will be done with better technology and software. Those things can react far more quickly than can humans, and there the latency of the speed of light is enormous. One thing we can do is to incorporate a great deal of parallelism. That is one way to hide latency specifically, by spreading one’s data stream over many (parallel) long latency lines we can reduce the effects of the latency by a factor roughly equal to the number of parallel lines. However, in terms of bandwidth, it is going to be pretty hard to exhaust the bandwidth. We keep finding new ways to provide more bandwidth via fiber optics. Moreover, radio spectrum is almost an unlimited source of bandwidth as the transmission range is shrunk down, thereby providing dramatic gains. Specifically, you get spatial reuse, which is powerful. Fiber optics has a lot of bandwidth. I don't see bandwidth as being a limitation.
Network limitations; UCLA Network Measurement Center
Kleinrock:
I see the limitations more from protocol problems. There is no question that every large system we have – and the Internet is a good example – contains deadlocks and lockups that are in the code right now but have just not yet been activated. They happen all the time. The electric power blackout was one example. We just have to hit those right situations. In the early days of the ARPANET my role at UCLA [University of California at Los Angeles] was to serve as the Network Measurement Center. It was our job to attempt to break the network – to stress it and find the outer edge of its performance envelope. We were able to crash it at will. Every time we did it we would find a fault in the code or an implementation error and then indicated how to fix it. Once it was fixed, then there would always be another fault to be found.
Vardalas:
Interesting. When they develop large VLSI [Very Large Scale Integration] and very complex things like that, they have all kinds of testing for reliability but still not everything is found.
Kleinrock:
That's exactly right.
Vardalas:
Did your people try to simulate collapses or find weak points in the system?
Kleinrock:
We could anticipate where there was trouble, so we would stress it with traffic - by increasing the number of nodes, by sending lots of short messages, or lots of long messages, by introducing traffic hotspots (i.e., by pushing all the traffic to one place), etc. These are the ways we did it. We didn't know what we would find, but inevitably we would find a problem as we went higher and higher in traffic or numbers. I am convinced that more faults are still there. The process of network measurement for which we at UCLA were responsible was stopped many years ago by the way. Nobody is testing the overall network these days.
Vardalas:
Nobody does?
Kleinrock:
No, there is no stress testing because the Internet is a now a production network and one does not attempt to take down a production network. By the way it is very hard to bring the network down, but sections can be brought down. With the ARPANET, which started out as an experimental network, we were consistently able to do that. I am convinced there are deadlocks out there just waiting to be activated. It's in the code. The code is too complex and too unstructured.
Vardalas:
You can't really simulate it because you don't know where to look.
Kleinrock:
That's right. It's hard to simulate all the implementation errors. Most often, the problems are caused by flow control mechanisms. A flow control mechanism is the following. You have a network and you can define input and output boundaries. For good reasons, one often puts constraints on what goes in and what comes out of the network across these boundaries. One constraint is that the order in which things come in should be the order in which they come out. If you legislate that you, have just created a deadlock as follows. Suppose one day, one message or one packet is lost. You will never deliver anything again because everything else is out of order – and it’s your fault! A natural remedy is to keep a copy somewhere so that you can recover from a loss – but that is an afterthought. That simple sounding constraint on the flow introduces the potential for a deadlock. The trouble is, there are a lot of these flow control issues – these constraints on what you can and cannot do. Once you have constraints, then you are vulnerable to not being able to meet these constraints, in which case, you have a deadlock. On the other hand, if you are slow in meeting these constraints, then you have a performance degradation.
Kleinrock:
These flow control protocol constraints are all over the code. No one was intelligent enough to say, "Let's put all the flow control protocol in one place in the code so that we can examine it." You add this, you add that, you add the other thing and you don't know how these things interact, so you get this kind of emergent behavior in large networks. The complexity is enormous.
Nomadic computing
Vardalas:
I saw the phrase ‘nomadic computing.’
Kleinrock:
Yes.
Vardalas:
Is that very similar to ubiquitous computing that Xerox PARC was trying to do in the 1990s?
Kleinrock:
It's related in a strange way. I see three legs to a stool that are very important for providing the infrastructure of the future. One leg is the ability to travel anywhere and be recognized as a “friendly” user instead of as an “alien”; that is what I refer to as “nomadic computing”. The second leg is what I like to call “smart spaces” in which my environment contains many kinds of embedded technology such that cyberspace can be found in my physical space instead of just in my virtual space. The third leg is “ubiquity” in that wherever I go, there should be access to the net. These three provide what I see as an important part of the future vision.
Vardalas:
Is this the work you are interested in now?
Kleinrock:
Yes, exactly. Here is a link to a recent paper I wrote on the subject: http://www.lk.cs.ucla.edu/PS/paper223.pdf. Recall those five things I said earlier in the vision – (1) the Internet should be always accessible; (2) it should always be on; (3) it should be everywhere; (4) anyone with any device should be able to connect at any time from any location; and (5) and it should be invisible. We got the first three. Why did we fail in the other two? One of the reasons is that TCP/IP assumed that you the user, your device, your physical location and your IP address were all coupled tightly; this model was generated during the days when computing was done from one’s desktop. That is no longer the case. Now we take our laptops, we travel about, we arrive someplace else and plug the laptop into an Ethernet port. The laptop ”arps” (i.e., looks for) its router back home and can't find it. The router in your new location says, "Who the heck are you?" Or your computer may expect to be behind a proxy server at your home location. The idea of being able to be on the move, i.e., a road warrior, and appear someplace else and gain access without jumping through hurdles and gain easy plug-and-play access, be provided the same set of privileges, preferences and profiles, and the same services one had back in their “home” environment seamlessly– is what is called nomadic computing. Basically, it is the ability to move from one place to another and get the same set of services without any hassle.
Providing this seamless mobility is what nomadic computing is about. I recognized that problem in the early '90s, wrote about it and then formed a company in the late 90’s called Nomadix. That company was devoted to making that all happen and is doing that right now. We have tens of thousands of points of presence out there making it possible for someone to walk into a location and get those services. Such a location might have a wireless WiFi access point or an Ethernet connection with a connection to the Internet. The problem is, how do you get plug-and-play access so you don't have to load any software or change configurations? How do you authenticate yourself? How do you pay? How do you make sure no one user hogs all the bandwidth? Then there is all the software in the remote location to make that happen. How should they handle the billing, the settlement costs and all the rest? That is what Nomadix is about, and solving those problems is the key to nomadic computing.
Xerox PARC was looking at the ubiquity and smart spaces (two of the three legs I referred to earlier). Smart spaces refers to physical environments that are alive with technology. When I walk into a room, it should know I have arrived; it should know what I want; and the devices I am carrying should recognize that they are now in this environment. There should be logic, memory, processing, sensors, actuators, microphones, speakers and displays in the walls, in my shoes, in my eyeglasses, in my fingernails, in my chair, in my table and everywhere else so that I can interact with the environment and it can interact with me. I should be able to speak to the room and say, "Tell me about such-and-such." The room should respond with voice or hologram or video etc. This idea of smart spaces is the second leg I referred to earlier. When you take those three you get what I like to call the “global invisible infrastructure”. This is where the technology has disappeared into the environment. Cyberspace will no longer be hidden behind the computer screen, which is where you see it now. It will be out in the physical world. Once you have that infrastructure you add two more things: (1) applications and services and (2) intelligent agents to provide those services to you. They will seek out a pizza joint in your current location or give you current stock market quotes – there will be various elements of serving you. These embedded devices and the software agents will generate traffic in vast, fast networks with enormous amounts of processing, solving the mission-critical problems of individuals, institutions and systems.
Vardalas:
Are you saying the current network can support all that more or less?
Kleinrock:
No, not now, but it is heading in that direction. Nomadic computing is beginning to happen. Wi-Fi and other wireless access is a strong component here, allowing us to go to many locations and gain access. We still don't have the intelligent embedded devices. That's the smart spaces. That is happening slowly. You probably carry a lot of devices around with you. I do too. They don't interoperate. They all have different interfaces. The keyboards are small and ugly.
Vardalas:
With the interfaces on PDAs you can't do anything.
Kleinrock:
Exactly. The keyboards are getting smaller and my fingers are not.
Vardalas:
Yes. Unless you sharpen your fingers in a pencil sharpener you can't use the darned things.
Kleinrock:
The screens are getting smaller and my eyes are getting worse. This is the whole world of what the industry has done in terms of pushing product on people. It is in their best interest that these devices don't interoperate, but that is going to settle out in the services. What made the cell phone so popular in the United States was the ability to do flat rate billing with no roaming costs, no long distance costs, anywhere in the country, and through an interaction with only one carrier. If one is a Verizon customer, fine. If you go into a service area of T-Mobile you don't care because you don't notice it. That has to happen with Wi-Fi access. The Internet will become a global mobile nervous system.
Vardalas:
This is how you are occupying your time now?
Kleinrock:
That's right.
Career overview
Vardalas:
Do you have any regrets about roads not taken in your career?
Kleinrock:
No. I love the path I have taken. There were a few critical decision points or crossroads in my life. It began with my early fascination in electronics. The decision to go to graduate school was an important one, even though many of my classmates went directly into high-paying jobs right out of college. I got my Ph.D. so that I could teach and pursue research; to me, solving puzzles has always been a welcome challenge. The decision to join the UCLA faculty was the right decision. I love teaching, I choose the research I want to do and I'm working with creative young minds all the time. That keeps me engaged and challenged. I meet some of the smartest people in the world, I get to travel and I am making important contributions. Teaching and research have been the wellsprings of my life. For me, it is the most gratifying endeavor.
Vardalas:
Well, I think we have pretty well run the course. Thank you very much for agreeing to be part of our history project. From my perspective this has been a fascinating and stimulating interview.
Education and work ethic
Vardalas:
As an aside, I was fascinated by the fact that your parents were not in the sciences. I was talking to Herbert Kroemer, who got the Nobel Prize, and no one else in his family was in science. However he did tell me about how the education ethic was very strong in the family. Was that what was very strong in you?
Kleinrock:
Absolutely.
Vardalas:
Did your parents think science was important?
Kleinrock:
No, but they certainly valued education. They actually wanted me to be an accountant, because their accountant was a professional who advised and helped them.
Vardalas:
Not a lawyer or doctor?
Kleinrock:
No. I thought about medicine but didn't want it.
Vardalas:
Okay. It was just the strong education ethic in the family.
Kleinrock:
That's right. It was always assumed in my family that the kids would get a college education in spite of our economic limitations.
Vardalas:
Where did you get this discipline? You went out yourself and organized how you learned about radio and you organized how you found stuff, etc.
Kleinrock:
I think I can thank my mother for that. She gave me the freedom. I tinkered and played around by myself a lot. I had my mess in the corner of the room, with all my electronics behind a little sofa and she didn’t ask me to clean it up even though she was quite fastidious about keeping a clean apartment. She gave me the flexibility and freedom I needed.
Vardalas:
Did she also give you a sense of dedication and purpose, or was this part of your character?
Kleinrock:
I think the sense of dedication and purpose was part of my character. Once I accept a challenge, I become very determined. I’ve run some marathons. I also have a black belt in karate which I took up at UCLA at the age of 47. Karate appeals to me since it is so different from my professional life. In karate, I am the student who follows orders; when my Sensei says to bow, I bow. If he says to punch, I punch. I enjoy the clarity and the role reversal.
Vardalas:
UCLA had a course in karate?
Kleinrock:
Yes. They had an extracurricular non-credit class. One day when I was jogging I dropped by this karate class and asked the instructor (the Sensei), "Where can I learn self defense of the Asian style?" and Sensei said, "Right here," so I enrolled.
Vardalas:
What style of karate was it?
Kleinrock:
Shotokan
Vardalas:
Yes.
Kleinrock:
Did you take it too?
Vardalas:
Yes.
Kleinrock:
Really? Then you clearly understand the appeal of discipline and contrast in one’s life.
Vardalas:
Yes. I taught it for a while. I was a 3rd degree.
Kleinrock:
That’s impressive. Good for you. I am Shodan and I still train.
Vardalas:
Do they have Japanese instructors coming here?
Kleinrock:
Yes, they do.
Vardalas:
At UCLA?
Kleinrock:
My instructor was taught by Mr. Nishiyama and Mr. Yaguchi.
Vardalas:
Oh really? I trained with Okazaki. I know him really well.
Kleinrock:
He comes here occasionally too.
Vardalas:
I also took classes from Okazaki's teacher, the late [Masatoshi] Nakayama.
Kleinrock:
Oh, the one who wrote the Best Karate book series.
Vardalas:
Yes, yes.
Kleinrock:
He came here only once. I saw him. He was amazing.
Vardalas:
Right. Thank you for the interview.
