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

Journal of Inforamtion Science and Engineering, Vol.11 No.2, pp.207-232 (June 1995)
A Distributed Topology learning Algorithm for
LAN Interconnection-Analysis and
Complexity Comparisons*

Jean-Lien C. Wu and Tsang-Min Chen#
Department of Electronic Engineering
National Taiwan Institute of Technology
Taipei, Taiwan, R.O.C.
*Department of Computer Science and Information Engineering
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 Protocoland 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.