US4967345A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of selecting least weight routes in a communications network
Assignee: International Business Machines Corp
•
Filing: 1988-06-23
•
Granted: 1990-10-30
•
Expires: 2008-06-23
Abstract
Abstract A least weight route computation algorithm for use in computing routes through a data communications network is improved by recording the number of equally weighted paths to a particular node through different predecessor nodes. If a route must be selected to the particular node, the relative numbers of equally weighted routes through different predecessor nodes determines the probability with which a route will be selected through the particular predecessor node.
Inventors
- 👤 Kathryn E. Clarke
- 👤 John E. Drake, Jr.
- 👤 Diane P. Pozefsky
- 👤 William E. Siddall
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:54
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/24
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
152 words
An improved method of selecting least weight routes through a communications network including network nodes interconnected by transmission groups, said nodes and transmission groups having associated weights, said method comprising the steps of: (a) adding a selected root node to a tree; (b) establishing a set comprising all network nodes connected to any node in the tree other than a network node already in the tree; (c) calculating the weights of paths from the root node to each node in the set; (d) selecting a path having the least weight or, if multiple paths to a given node have equal least weights, quasi-randomly selecting one of those multiple paths; (e) transferring to the tree the node in the selected least weight path; (f) removing any other entries for the transferred node from the set; (g) repeating steps b through f until all nodes in the network have been transferred to the tree.
Claim 2
Dependent Claim
152 words
An improved method of selecting least weight routes through a communications network including network nodes interconnected by transmission groups, said nodes and transmission groups having associated weights, said method comprising the steps of: (a) adding a selected root node to a tree; (b) establishing a set comprising all network nodes connected to any node in the tree other than a network node already in the tree; (c) calculating the weights of paths from the root node to each node in the set; (d) selecting a path having the least weight or, if multiple paths to a given node have equal least weights, quasi-randomly selecting one of those multiple paths; (e) transferring to the tree the node in the selected least weight path; (f) removing any other entries for the transferred node from the set; (g) repeating steps b through f until all nodes in the network have been transferred to the tree.
Claim 3
Dependent Claim
66 words
An improved method as defined in Claim 1 wherein the step of quasi-randomly selecting a path further comprises the steps of: determining the number of equally-weighted least weight paths which may exist to a given node through different predecessor nodes in the tree; and selecting one of those paths as a function of the relative number of equally weighted paths existing through the different predecessor nodes.
Claim 4
Dependent Claim
65 words
An improved method as defined in claim 2, wherein the probability that a given path in a set of equally-weighted least weight paths will be selected is a function of the formula a/(A+B+...n) where A is the number of equally weighted paths through a given predecessor node and A+B+...n is the total of equally-weighted least weight paths through all predecessor nodes to the given node.
Claim 5
Dependent Claim
186 words
An improved method of selecting least weight routes through a communications network including network nodes interconnected by transmission groups, said nodes and transmission groups having associated weights, said method comprising the steps of: (a) adding a selected root node to a tree; (b) establishing a set comprising all network nodes connected to any node in the tree other than a network node already in the tree; (c) calculating the weights of paths from the root node to each node in the set; (d) recording the number of equally weighted paths leading to each node in the set from different predecessor nodes; (e) selecting a path having the least weight or, if multiple paths to a given node have equal least weights, quasi-randomly selecting one of those multiple paths as a function of the recorded number of equally weighted paths through different predecessor nodes; (f) transferring to the tree the node in the selected least weight path; (g) removing any other entries for the transferred node from the set; (h) repeating steps b through g until all nodes in the network have been transferred to the tree.
Claim 6
Dependent Claim
186 words
An improved method of selecting least weight routes through a communications network including network nodes interconnected by transmission groups, said nodes and transmission groups having associated weights, said method comprising the steps of: (a) adding a selected root node to a tree; (b) establishing a set comprising all network nodes connected to any node in the tree other than a network node already in the tree; (c) calculating the weights of paths from the root node to each node in the set; (d) recording the number of equally weighted paths leading to each node in the set from different predecessor nodes; (e) selecting a path having the least weight or, if multiple paths to a given node have equal least weights, quasi-randomly selecting one of those multiple paths as a function of the recorded number of equally weighted paths through different predecessor nodes; (f) transferring to the tree the node in the selected least weight path; (g) removing any other entries for the transferred node from the set; (h) repeating steps b through g until all nodes in the network have been transferred to the tree.
Claim 7
Dependent Claim
65 words
An improved method as defined in Claim 4 wherein the probability that a given path in a set of equally-weighted least weight paths will be selected is a function of the formula A/(A+B+...n) where A is the number of equally weighted paths through a given predecessor node and A+B+...n is the total of equally-weighted least weight paths through all predecessor nodes to the given node.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-10-29 | 1994-04-30 | 1994-10-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-10-29 | 1998-04-30 | 1998-10-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-10-29 | 2002-04-30 | 2002-10-30 | $7700.00 | Window Closed / Lapsed |