A new method for topological design in large, traffic laden packet switched networks

ABSTRACT

The AN/1 network architecture employs compact LANs as integrated switching nodes. The multibussed nodal architecture imposes a natural hierarchy to the network interconnection problem. A nodal interconnection method is introduced as a generalization of hierarchical topology design techniques. Based on traffic and distance, a flat nodal topology is decomposed into several level, overlapped subnetworks. Each subordinate subnetwork communicates with its ordinate subnetwork via two formal gates. The traffic matrix for each subnetwork can be obtained. Linear programming techniques are used to determine bandwidth requirements. Perturbation procedures are applied to determine the appropriate groupings of LANs into subnetworks and the appropriate hierarchy. A flat topology may be returned if it is optimal.

REFERENCES

• 1: R. Boorstyn, and H. Frank, "Large- Scale Network Topological Optimization," IEEE Trans. Commun., 25 (1) , 29-47(1977) .
• 2: G.H. Dysart, and N.D. Georgana s, "NEWCLUST: An Algorithm for the Topological Design of Two-Level Mult idrop Te leproce s sing Networks," IEEE Trans. Commun., 26 (1) , 55-62 (1978).
• 3: S. Even," An Alogrithm for Determining Whether the Connectivity of a Graph is at Least k," SIAM J. Comput., 4, 393-396 (1975).
• 4: H. Frank, I.T. Frisch, and W. Chou, "Topological Considerations in the Design of the ARPA Computer Network," AFIPS Nat. Comput. Conf. Exp. Conf. Proc., 36, 551-567 (1970).
• 5: H. Frank, and W. Chou, "Topological Optimization of Computer Networks," Proc. IEEE, 60(11), 1385-1397 (1972).
• 6: H. Frank, M. Gerla, and W. Chou, "Issues in the Design of Large Distributed Computer Communication Networks," Proc. of the Nat. Telecom. Conf. Atlanta, GA, November 1973, IEEE, New York, pp. 37A-1-37A-8.
• 7: M. Gerla, H. Frank, and J. Eckl, "A Cut Saturation Algorithm for Topological Design of Packet Switched Communication Networks," Proc. NTC, 1074-1085(1974).
• 8: M. Gerla, and L. Kleinrock, "Topological Design of Distributed Computer Networks," IEEE Trans. Commun., 25, 48-60(1977).
• 9: M. Hoshi, "Local Network Area Size Optimization," IEEE Trans. Commun., 33 (3), 199-202 (1985).
• 10: B.W. Kernighan, and S. Lin, " An Efficient Heuristic Procedure for " Bell Syst Partitioning Graphs, Tech. J., 49, 291-307 (1970) .
• 11: A. Kershenbaum, and R.R. Boorstn, " Centralized Teleprocessing Network Design," Networks, 13, 279-293 (1983) . "Op t ima 1
• 12: L Kleinrock, and F. Kamoun, Clustering Structures for Hierarchical Topological Design of Large Computer Networks," Networks, 10, 221-248 (1980).
• 13: T. Wu, J. Stach, and K. Chen, "Constrained Configuration of Local Area Networks for the AN/1 Switching Architecture", to be presented at the 10th Local Computer Network Conference, Minneapolis, October 1985.
• 14: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Theory