| 摘要 |
The communications network includes a plurality of interconnected nodes and communication links between nodes. Computing apparatus in provided for determining a shortest path from a starting node to a destination node. The computing apparatus is adapted so that each node forms a routing tree having nodes with indentities, branches with weights, and a distinguished node called a root. The routing tree is the estimated shortest path to all of the nodes and each node communicates its routing tree to each adjacent node. Upon receipt of a routing tree by a reference node from an adjacent node, the reference node stores the routing tree and produces a large tree having roots and branches by placing the reference node as the root of the large tree and creating branches from the reference node to the roots of the routing trees of the adjacent nodes. The lengths of the branches are equal to the lengths of the links from the reference node to the adjacent nodes. A breadth first search of the large tree is performed to determine a connected subset of the large tree where each node identity appears only once. The connected subset forms the new routing tree for the reference node. If the new routing tree differs from the previous routing tree, the new routing tree is broadcast to all adjacent nodes and the procedure is repeated until no new tree differs from a previous tree, thereby defining a final routing tree. The final routing tree includes the shortest path from the reference node to all connected nodes.
|
