초록 ▼

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

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.

대표청구항 ▼

In a communications network in which a plurality of nodes having unique identities transmit messages over links that have lengths between the nodes, a machine implemented method for sending massages from a first node to a destination node over a shortest path from the first node to the destination n

In a communications network in which a plurality of nodes having unique identities transmit messages over links that have lengths between the nodes, a machine implemented method for sending massages from a first node to a destination node over a shortest path from the first node to the destination node, comprising the steps of: forming a first routing tree for said first node that represents an estimated shortest path from said first node to other nodes and that includes all nodes that are connected by a link to said first node, one node in said first routing tree serving as a root of said first routing tree, sending, by said first node, an identical tree to all said nodes that are connected by a link to said first node, said identical tree comprising at least a portion of said first routing tree: receiving, by said first node, respective routing trees transmitted by said nodes that are connected by a link to said first node; and storing, by said first node, the received routing trees, forming a new routing tree for said first node using said received routing trees, said new routing tree including a group of said nodes one of which is said destination node, comparing said new routing tree to a previous routing tree at said first node and, if said trees are different, determining a subsequent new routing tree that is not different from said previous routing tree, whereby said subsequent new routing tree defines the shortest paths from said first node to all of said nodes in said group, and transmitting messages from said first node to said destination node over the shortest path for said destination node defined by said new routing tree.