Method and apparatus for determining a routing table for each node in a distributed nodal system

• US 6,041,049 A
• Filed: 05/06/1997
• Issued: 03/21/2000
• Est. Priority Date: 05/06/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Brady, James T.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Ho, Tuan Q
• Application Number:
  US08/852,019
• Time in Patent Office: 1,050 Days
• Field of Search: 370/351, 370/395, 370/400, 370/257, 370/363, 370/367, 370/368, 370/371, 370/374, 370/378, 370/379, 370/383, 370/386, 370/396, 370/412, 370/428, 370/429, 340/825.06, 709/241, 707/10
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A method enables each node in a multi-nodal network to construct a routing table to all other nodes in the network. Each "home" or originating node performs a method which includes the steps of: transmitting a query to all immediate neighbor nodes and recording in a routing table, responses received which identify the neighbor node at the terminus of each link; transferring to each neighbor node, home node routing table entries and receiving routing table entries from each neighbor node; and, for each routing table entry to a node that is received from a neighbor node, if the route indicator is already present in the home node routing table, ignoring the entry; if the new entry indicates a route to a new node, entering the new node and a route identifier; and if the entry indicates a route to a node for which there is already an entry in the home node routing table, noting the new entry as a lower priority route to the node. Once the aforementioned procedure is repeated a number of times, each node in the multi-nodal network includes routes to all nodes in the network, with the routes having automatically been prioritized in accordance by sequence of receipt.

Claims

1. A method for enabling each node in a multi-nodal system to construct a route table to all other nodes in the multi-nodal system, each node being either a home node or a neighbor node which is positioned one link away from a home node, each home node performing the method comprising the steps of:

a) transmitting a query to all immediate neighbor nodes, said query inquiring into an identity of each said neighbor node;

b) recording in a route table, responses received from each said neighbor node, each said response identifying a neighbor node at a terminus of a link;

c) transferring to each said neighbor node, route table entries from the home node'"'"'s route table and receiving route table entries from each said neighbor node; and

d) for each route entry to a destination node indicated by a route table entry received from a said neighbor node;

1) ignoring said each route entry to said destination node if an identical link route is already present that corresponds to said destination node in the route table of the home node;

2) entering a new route entry to said neighbor node if a route to said destination node is not present in the route table of the home node, and

3) if said each route entry to said destination node indicates a route to a node for which there is already a different route entry in the route table of the home node, placing a further route entry to said neighbor node in the table of said home node as a lesser priority route to said destination node.

2. The method as recited in claim 1, wherein steps c) and d) are repeated until no further changes are experienced in entries in the route table of the home node.

3. The method as recited in claim 2, wherein said home node employs said route table to determine a path to a said neighbor node over which to transmit messages to said destination node, a priority value assigned to a path employed by said home node to determine which path to try before other paths in attempting to dispatch a message.

4. The method as recited in claim 1, wherein step d) includes the following substep of:

4) if plural different route entries are received to said destination node, randomly choosing one of said different route entries as a higher priority route and another of said different route entries as a lower priority route.

5. A memory media for enabling each node in a multi-nodal system to construct a route table to all other nodes in the multi-nodal system, said each node being either a home node or a neighbor node which is positioned one link away from said home node, each said home node including a processor that is controlled by said memory media, said memory media comprising:

a) means for controlling said processor to cause transmission of a query to all immediate neighbor nodes, said query inquiring into an identity of each said neighbor node;

b) means for controlling said processor to record in said route table, responses received from each said neighbor node, said responses identifying the neighbor node at a terminus of a link;

c) means for controlling said processor to transfer to each said neighbor node, route table entries from the home node'"'"'s route table and to receive route table entries from each neighbor node; and

d) means for controlling said processor to process each route entry to a destination node indicated by a route table entry received from said neighbor node by;

1) ignoring said route entry to said destination node if an identical link route is already present that corresponds to said destination node in the route table of the home node;

2) entering a further route entry to said neighbor node if a route to said destination node is not present in the route table of the home node;

or

3) if said route entry to said destination node indicates a route to a node for which there is already a different route entry in the route table of the home node, placing a further route entry to said neighbor node in the table of said home node as a lesser priority route to said destination node.

6. The memory media as recited in claim 5 wherein means c) and means d) repeat their respective functions until no further changes are experienced in entries in the route table of the home node.

7. The memory media as recited in claim 5, wherein means d) controls said processor to perform the following substep of:

4) if plural different route entries are received to said destination node, randomly choosing one of said different route entries as a higher priority route and another of said different route entries as a lower priority route.