Broadcasting Topology and Routing Information in Computer Networks
Abstract
The topology problem in store and forward computer networks is that of keeping all nodes informed of the current operational status of each communication link in the network. The failure or repair of one or more communication links is called a topology change. Two efficient algorithms are presented for solving this problem. They require 0(l) communication and O(n) time for simple topology hanges in a network with l links and n nodes. The algorithms send messages only in resposne to topology changes, and each message usually contains information only about the links whose status has changed. The algorithms work properly in the presence of arbitrarily complex topology changes. The routing information problem is that of keeping each node informed of the packet transmission delay on each directed link in the network. Nodes need this information in order to make intelligent routing decisions. The two topology algorithms discussed above are used to also solve the routing information problem. The level of difficulty in solving this problem is found to depend greatly on the particular properties of the topology algorithm used.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1985
- Accession Number
- ADA155668
Entities
People
- J. M. Spinelli
Organizations
- Massachusetts Institute of Technology