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.