Petrie: What about the host interface? There's a different host interface for every host? Was there a different type of host at every site?
Kleinrock: No. There was a preponderance of PDP-10s. In fact so much so that ARPA stopped buying PDP-10s because this almost became a homogeneous network, and they wanted to develop a heterogeneous network.
Petrie: So how many hosts were there initially?
Kleinrock: One per IMP. Typically one, occasionally two per IMP. So the number of nodes grew. It was 10 in summer of 1970.
Petrie: At that point, how many different kinds of hosts?
Kleinrock: Oh, I suspect about four or five different hosts. But we didn't have the host/host protocol then. October 1971 is when we finally got the protocol implemented in most of the host machines. And the DEC PDP-10 was the main host machine. For example, by August 1973, there were 16 PDP-10's, eight other PDP-class machines, six IBM 360-class machines, one 370-class machine, one Burroughs B6700, the TX-2, some miscellaneous machines, and, of course, our lonely SDS Sigma 7. It was just a weird mix of things. Each one required its own surgery to adapt to the system.
Petrie: By a different team? It's a wonder that it worked.
Kleinrock: Yes, and that was its strength, too. You can imagine how much BBN liked us as we kept crashing their network any time we wanted. So what would happen was the network would crash, but BBN didn't give us source code for the IMP operating system. They held it close to their chest. So when it crashed, we would say, "Here's what happened, please fix it." They would reply, "No, it's too complicated to fix; it's gonna take us six months." We got that answer continuously. So one day the government pressured BBN to release the source code. After all, the government had paid for it, and BBN had no right to keep it from the government. So now we got source code. Then we could see what happened, we'd see what the trouble was, we'd write the code to fix it and send it BBN. And it still took six months. [laughter]
Petrie: But every site was doing this now?
Kleinrock: No, we were the only ones stressing the network. We were the Network Measurement Center for the entire Arpanet. Each IMP had the ability to measure itself and send us back messages. So we turned on and turned off the measurements.
Here was a really interesting problem, what we referred to as reassembly deadlock. I published the first book about the Arpanet in 1976 [Queueing Systems: Computer Applications, John Wiley & Sons] and described reassembly deadlock there, along with many other deadlocks. Let's assume that a number of messages are in the process of arriving at some destination IMP, which is reassembling these messages. But there's only so much space for reassembly. When a packet for a new message comes in, it might be eight packets long (that was the max), and so eight packet buffers are put aside for reassembling that message. So you have a bunch of eight-buffer segments put aside, partially filled, none of them complete; let's refer to the missing packets as "pink" packets.
Let's further assume that all of the reassembly buffer space is currently in the process of reassembling these messages. Now if you look at all the switches in the IMPs attached to this IMP, they're also sending packets to this same destination IMP. Let's further assume that all of the storage in these IMPs is full of packets, but none of them are the missing pink packets. They're all from newer messages (say "green" packets).
Where's the missing pink stuff? One layer behind that. Now these missing pink guys can't get to the destination until these green guys get through; and the green can't get through until the pink get through, complete the reassembly of some messages, and release the reassembly buffer space! Bang! That's your re-assembly deadlock. It forced BBN to change the whole operating system for the IMP. That was deadly.
Petrie: They should have anticipated that one.
Kleinrock: Yeah, well. These were new times, you know? And it was complex. I mean in order to get a message into the network, you had to grab an available logical link, you had to get storage at the other end, and you had to get a token to move it. So those three things had to be collected. They're all in different locations with different control processes collecting them. You can imagine the craziness.
Flow control is still the Achilles' heel of our networks. That's what took down the AT&T network, takes down the Internet. Little simple things. Signaling System 7, the signaling control structure of the telephone network, took down AT&T. Of course, it's a digital system. One of the switches thought it was overloaded-it wasn't-and it told the other switches next to it, "Stop sending," and that propagated. Crash! Once you see these things occur, you can easily fix them. The trick is to anticipate the problem, and that is very very difficult.
Petrie: You're saying this brings down the Internet. Has it brought down the Internet?
Kleinrock: The Internet goes down every so often. Sometimes you don't know why. But in those early days we knew what was going on because we had hooks all over the place. They removed the Network Measurement Center in the mid-70s. BBN continued with the maintenance function, but DCA [Defense Communications Agency] took over the Measurement Center in 1975. After that we don't know what happened. So that was the growth of the network.
Petrie: When you finally did get the host to host protocol, what was the first use?
Kleinrock: Well, there were some uses before that, but email was put in in 1972 as an ad hoc add-on by Ray Tomlinson. Just a trivial thing to add to a network. It caught fire and dominated network traffic immediately. That was again another signal of what was coming today. The people to people thing.
Petrie: What was the use before email?
Kleinrock: Some military Air Force bases, Tinker and McClellan, sent some stuff. We don't know what it was. We have no idea. Mostly sending a message to someone else or trying to use a remote machine. But it was a crude kind of e-mail. Just testing machine-to-machine communication. File transfers, sending documents around, very low level use.