History of network topology

Network Topology - 1969-1970

During the summer and fall of 1969, Roberts struggled with the issue of network topology: the interconnection of nodes, or sites. Based on his prior experience with the telephone companies, he knew he had to order the communication lines well in advance of when they would be needed. So he began simulating network topologies on a computer and quickly concluding he needed expert help.

Roberts turned to Dr. Howard (Howie) Frank. Frank had founded Network Analysis Corporation (NAC), a company specializing in topological design based on his groundbreaking work at the Office of Emergency Preparedness (OEP). Frank remembers Roberts’ call requesting a meeting:

“Arpanet was a four node network. That's what existed. He had a piece of graph paper on his desk and he was showing me extensions to the network. It was on the west coast at the time. But there was nothing on the east coast. He needed to order communication lines for that, and he said: 'I don't know what I'm doing. I'm just drawing these lines. Could you figure out a way to do this better?' So, we wrote him a proposal, and we started our contract in October 1969. Larry had a deadline. It was a real deadline. He said: ' I can cancel the orders by this date.' We analyzed the configuration that he had given us, and we developed the very first techniques for designing distributed computing systems, which were primitive compared to the ones we subsequently developed. I would say that within a period of two to three months -- no more than that -- we came back with a design which was something like 25% cheaper and had 40% more throughput than the one that he had come up with. We worked like a bear because it was truly a hard project."

Frank and Kleinrock shared an interest in network design, although each looked at the problem from a different perspective. Just months before receiving his Ph.D. from Northwestern, a classmate told Frank: "Your thesis is in the book store." Frank recalls:

"I charged over to the book store, and there I find a monograph by Len called On Communication Networks, Stochastic Message Flow and Delay. My thesis was titled On Probabilistic Graphs of Some Applications. So I open it up, and I look through it for three minutes, and discover it has nothing to do with what I'm doing. It's the same general area, but he was looking at queues and networks and I was looking at the existence of the fundamental structures themselves. Essentially he was pumping traffic through and seeing what happens to the traffic. I was saying: 'There is an underlying uncertainty in the network itself.' Kleinrock used words like capacity, but really that's not a deterministic quantity. The links may not be there because of reliability or vulnerability. Somebody may be attacking them or the nodes may not be there, and I was looking at the fundamental phenomenon of how do you talk about connectivity when the elements are uncertain."

In 1966, Frank wrote a paper stimulated by Baran's On Distributed Communication and an article in the Journal of Mathematical Biophysics on what happens to human cells when they are radiated. In seeing the commonalties with Baran’s networks disrupted by nuclear bombardment, Frank developed a series of equations that reproduced everything Baran had done by simulation. The paper, Vulnerability of Communication Networks, published in the IEEE Transactions On Communication Technology in 1967, led to Frank being offered the position at OEP. The paper investigated how the Federal Power Commission approved Gulf of Mexico pipeline applications and Frank developed new techniques that proved valuable in finding solutions for expanding the Arpanet.