Route selection using cached partial trees in a data communications network

• US 5,321,815 A
• Filed: 10/16/1992
• Issued: 06/14/1994
• Est. Priority Date: 10/13/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McGinn, John E., Siddall, William E., Bartolanzo, Leo J. Jr., Clouston, Robert D.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US07/962,626
• Time in Patent Office: 606 Days
• Field of Search: 395/200
• US Class Current: 709/241
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

A process for selecting a least weight path between two nodes in a data communication network uses partial trees created and cached in prior route selection operations. All root nodes on possible paths between the two nodes are identified. Any cached tree having a root matching one of the identified root nodes is retrieved from storage. If necessary, each retrieved tree is extended until it includes all possible destination nodes. The extended and/or retrieved trees are used to select the least weight path between the two nodes. The extended tree is then cached for possible use in future route selection operations.

Claims

1. For use in a data communications network having end nodes and network nodes, said network nodes being capable of storing network topology information including routing trees defining least weight paths between different network nodes and of providing route selection services for at least one end node, an improved method of establishing a least weight path between a first end node and a second end node, said method comprising the steps of:

a) examining the stored network topology information to build a first list of network nodes connected to the first end node and a second list of network nodes connected to the second end node;

b) examining the stored network topology information to determine the weight for each path between the first end node and each of the network nodes on the first list and the weight for each path between the second end node and each of the network nodes on the second list;

c) selecting a network node from the first list;

d) determining whether there is a stored routing tree for which the selected network node is the root node;

e) if no such routing tree is determined to exist, constructing a routing tree beginning with the selected network node as the root node and extending to all network nodes on the second list;

f) if such a routing tree is determined to exist, extending the tree as necessary until it includes all network nodes on the second list;

g) repeating the steps b, c, d and e until all network nodes on the first list have been selected; and

h) combining the weight of the least weight path from each network node on the first list to each network node on the second list with the weights of the paths from the first end node to the network nodes on the first list and the weights of the paths to the second end node from the network nodes on the second list to determine the least weight path from the first node to the second node.

2. In a data communications network having end nodes and network nodes, said network nodes being capable of providing route selection services for end nodes, an improved network node including:

a) means for storing network topology information including the weights of paths between the network node and the end nodes which it serves and routing trees defining least weight paths between pairs of network nodes;

b) means responsive to a request to select a route from a served first end node to a remote second end node to generate a first list consisting of network nodes connected to the first end node and a second list consisting of network nodes connected to the second end node;

c) means for crating for storing a set of routing trees defining least weight paths from each of the network nodes on the first list to all the network nodes on the second list, said means for creating extending previously stored routing trees where possible to create the set;

d) means for combining the weight for each routing tree in the set with the weights of the paths from first and second end nodes to the network nodes in the tree to determine the weights of the possible paths from the first end node to the second end node; and

e) means for selecting the path having the least weight as the route from the first end node to the second end node.