Automatic update of replicated topology data bases

ABSTRACT

In computer communication networks, routing is often accomplished by maintaining copies of the network topology and dynamic performance characteristics in various network nodes. The present paper describes an algorithm that allows complete flexibility in the placement of the topology information. In particular, we assume that an arbitrary subset of network nodes are capable of maintaining the topology. In this environment, protocols are defined to allow automatic updates to flow between these more capable nodes. In addition, protocols are defined to allow less capable nodes to report their topology data to the major nodes, and acquire route information from them.

REFERENCES

• 1: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 2: M. Schwartz and T. E. Stern, "Routing Protocols", in Computer Network Architecture and Protocols, P. E. Green, ed., Plenum Press, 1982.
• 3: J. M. McQuillan, I. Richer, and E. C. Rosen, "The New Routing Algorithm for the ARPANET", IEEE Trans. on Comm., Vol. COM-28, No. 5, pp 711-719, May, 1980.
• 4: L. Tymes, "Routing and Flow Control in TYMNET", IEEE Trans. on Comm., Vol. COM-29, No. 4, pp 392-399, April, 1981.
• 5: L. Kleinrock and F. Kamoun, "Hierarchical Routing for Large Networks - Performance Evaluation and Optimization", Computer Networks, 1, (1977), 155-174.
• 6: A.E. Baratz and J. M. Jaffe, "Establishing Virtual Circuits in Large Computer Networks", INFOCOM' 83, San Diego, CA.
• 7: J.D. Atkins, "Path Control - The Network Layer of SNA", in Computer Network Architecture and Protocols, P. E. Green, ed., Plenum Press, 1982.
• 8: A. Segall and J. M. Jaffe, "A Reliable Distributed Route Set-Up Procedure", GLOBECOM '83, San Diego, CA.
• 9: A. E. Baratz and A. Segall, "Reliable Link Initialization Procedures", IBM Research Report RC 10032, IBM, York-town Heights, NY, Aug. 1983; also in H. Rudin, C.West, ed., Protocol Specification, Testing and Verification III, North Holland, 1983.
• 10: A. Segall and J. M. Jaffe, "A Distributed Protocol for Maintaining Central Network Control", submitted to ICC'84.
• 11: J.M. Jaffe and A.Segall, "Automatic Update of Replicated Data Bases", IBM Research Report RC 10254, Yorktown Heights, Nov. 1983.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance