EP0423053A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method of using cached partial trees in computing a path in a data communication network
Assignee: International Business Machines Corp
•
Filing: 1990-08-22
•
Granted: —
•
Expires: 2010-08-22
Abstract
Abstract A process for selecting a least weight path between two nodes (10, 16) in a data communication network uses partial trees created and cached in prior route selection operations. All root nodes (12, 14) on possible paths between the two nodes (10, 16) are identified. Any cached tree having a root matching one of the identified root nodes (12, 14) 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 (10, 16). The extended tree is then cached for possible use in future route selection operations.
Inventors
- 👤 Leo Joseph Bartolanzo, Jr.
- 👤 Robert Donald Clouston
- 👤 John Ernest Mcginn
- 👤 William Edward Siddall
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-31 23:08
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L45/488
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
216 words
A method of using a stored tree in computing a preferred path from a first node to a second node in a data communication network having a plurality of network nodes and links interconnecting at least some of said network nodes, wherein at least one of said network nodes includes means for computing preferred paths between nodes and for storing the results of each path computation in the form of a tree, said method being characterized in that it comprises the steps of a) identifying each network node connected to said second node; b) retrieving a tree having the first node as the originating or root node; c) determining whether the retrieved tree includes all network nodes connected to said second node, and c.1) if the retrieved tree includes all network nodes connected to said second node, using the tree to select the preferred route from network nodes connected to the root node to network nodes connected to said second node; c.2) if the retrieved tree does not include all network nodes connected to said second node, extending the existing tree until all such network nodes are included, and using the extended tree to compute a preferred path from the network nodes connected to the root node to the network nodes connected to said second node.
Claim 2
Independent Claim
216 words
A method of using a stored tree in computing a preferred path from a first node to a second node in a data communication network having a plurality of network nodes and links interconnecting at least some of said network nodes, wherein at least one of said network nodes includes means for computing preferred paths between nodes and for storing the results of each path computation in the form of a tree, said method being characterized in that it comprises the steps of a) identifying each network node connected to said second node; b) retrieving a tree having the first node as the originating or root node; c) determining whether the retrieved tree includes all network nodes connected to said second node, and c.1) if the retrieved tree includes all network nodes connected to said second node, using the tree to select the preferred route from network nodes connected to the root node to network nodes connected to said second node; c.2) if the retrieved tree does not include all network nodes connected to said second node, extending the existing tree until all such network nodes are included, and using the extended tree to compute a preferred path from the network nodes connected to the root node to the network nodes connected to said second node.
Claim 3
Dependent Claim
75 words
The method according to Claim 1 further comprising the steps of : if the retrieved tree includes the second node, using the tree to determine the preferred path from said first node to said second node, and if the retrieved tree does not include the second node, extending the tree until the tree includes said second node, and using the extended tree to determine the preferred path from said first node to said second node.
Claim 4
Dependent Claim
24 words
The method according to Claim 1 or 2 further including the step of storing the extended tree for possible use in future route computations.
Claim 5
Dependent Claim
35 words
The method according to Claim 3 further including the step of storing the identity of each network node in the network that is directly connected to one of the nodes included in the stored tree.
Claim 6
Dependent Claim
63 words
The method according to Claim 4 further including the step of maintaining the stored tree upon a change in status of network resources, said maintaining step comprising: determining whether a stored tree includes a network resource whose status has changed since the tree was stored, determining whether the stored tree is affected by the status change, and removing any affected tree from storage.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.