An improved topology discovery algorithm for networks with wormhole routing and directed links

We propose a new parallel topology discovery algorithm for irregular, mesh- connected networks with unidirectional links and wormhole routing. An algor ithm of this type was developed for the ATOMIC high speed local area networ k to avoid the need for manually updating routing tables. Similar needs may arise in wireless networks when channels may be unidirectional because of limited transmission power, multipath, and similar effects. Like the ATOMIC topology discovery algorithm, our algorithm accumulates a map of the netwo rk at a distinguished node called the Address Consultant. However, our algo rithm is much faster. In addition, our algorithm is more general, because i t can correctly resolve topologies that contain multiple links between the same nodes. We implemented both algorithms in a concurrent simulation envir onment, and tested them on a variety of topologies. (C) 1999 Published by E lsevier Science B.V. All rights reserved.