Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |

A Distributed Topology learning Algorithm for

LAN Interconnection-Analysis and

Complexity Comparisons

**Jean-Lien C. Wu and Tsang-Min Chen ^{#}**

National Taiwan Institute of Technology

Taipei, Taiwan, R.O.C.

National Taiwan University

Taipei, Taiwan, R.O.C.

A topology learning algorithm, referred as the *New Shortest Path Topology Algorithm *(NSPTA), is adopted in bridged LAN environments. The NSPTA is a distributed algorithm and is installed within the bridges of an interconnected LAN to demonstrate a correct view of the topology of the entire internet. This streamlined algorithm is found to be competitive with existing standards. The algorithm uses no sequence numbers, no periodic transmission, and avoids attendant reset. However, it achieves *transparency and optimal routing *through partial-topology message exchanges between neighboring bridges.

*Correctness proof and complexity analysis *are two major issues in our algorithm design, and we compare three major criteria of complexity analysis with existing algorithms. Complexity analysis includes message complexity, time complexity, and algorithm complexity. It is proved that the complexity of our algorithm is optimal in the sense that the performance is bounded by physical limitations alone. A distributed emulation system, TESLA, is employed for the purpose of measurement. The measured results also include two existing standards: the *Spanning Tree Protocol*and the *Source Routing Protocol*.

Keywords: topology, distributed, interconnection, optimal routing, complexity, correctness

Received August 27, 1993; revised November 19, 1994.

Communicated by Wen-Hsiang Tsai.
^{*}This work was supported by the National Science Council under research grant NSC-80-0408-E-011-04.