Topological analysis of local-area internetworks

ABSTRACT

It has become common to connect local-area networks together to form high-bandwidth internetworks. The topology of such an internetwork — how the component networks and gateways are interconnected — is an important factor in determining the reliability of the internet. We present several techniques for analyzing an internetwork's topology. These techniques are based on a novel mapping of network components onto a bipartite graph. We use these techniques to analyze the topology of the Stanford University Network and the impact of topological changes as it has grown to its current size of 60 networks.

REFERENCES

• 1: Caroline Arms (Ed.). Campus Networking Strategies. Digital Press, 1988.
• 2: Eric Benhamou. "Integrating Bridges and Routers in a Large Intemetwork". IEEE Network 2, 1 (January 1988), 65-71.
• 3: Leonard Bosack and Charles Hedrick. "Problems in Large LANs". IEEE Network 2, 1 (January 1988), 49-56.
• 4: Charles Hedrick, Andrew Malis, Vint Cerf, Jack Haverty, Ken Pogran, et alia. Arpanet outage. In "TCP-IP" mailing list, tcp-i~sri-nic.arpa. Archive available from sri-nic.arpa in file TS:<TCP-IP>tcp-ip. 1986D, under subject "Arpanet outage", beginning 15 Doc 1986.
• 5: Robert Michaels, Norman Kind, and Walter Underwood. Designing and Installing An International TCP/iP Network. STL 87-19, Hewlett-Packard Laboratories, December, 1987.
• 6: Howard Salwen, Richard Boule, J. Noel Chiappa. "Examination of the Applicability of Router and Bridging Techniques". iEEE Network 2, 1 (january 1988), 77-80.
• 7: William M. Seifert. "Bridges and Routers". IEEE Network 2, 1 (January 1988), 57-64.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

General Terms:
Algorithms, Design, Measurement, Reliability, Theory