US5533016A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Communications network ring router
Assignee: Nytell Software LLC
•
Filing: 1994-05-16
•
Granted: 1996-07-02
•
Expires: 2014-05-16
Abstract
Abstract A ring is routed through a subset of nodes of a communication network by first providing a branch-decomposition having a pattern relating to separations of the network. The branch-decomposition can be performed using internal two-separations, internal three-separations, eigenvector separations and pushing. If the branch-decomposition has a branch-width less than or equal to a predetermined constant value, then the branch-decomposition is used to determine costs associated with portions of the ring passing through separations of the network by examining matchings corresponding to edges of the branch-decomposition and selecting a lowest cost ring by examining the matchings and choosing a lowest cost set of matchings containing the subset of nodes. The branch-decomposition can be provided once for a fixed network and then costs can be determined and the ring route selected repeatedly for different subsets of ring nodes and different edge costs. The edge costs can be negative.
Inventors
- 👤 William J. Cook
- 👤 Paul D. Seymour
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:17
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L12/00; H04L12/28; H04L12/42; H04L12/437
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
157 words
A method for selecting a communication ring path of lowest cost through a subset of nodes of a communication network, each edge of the network having a particular cost associated therewith, the method comprising the steps of providing a tree data structure wherein each leaf vertex of the tree represents an edge of the network and each non-leaf vertex of the tree is connected to exactly three edges of the tree, said tree data structure being a branch-decomposition having a pattern of separations of the network, a separation of the network corresponding to each edge of the tree; in response to each separation of said branch-decomposition having a number of nodes less than or equal to a predetermined constant, determining costs associated with portions of the ring path passing through separations of the branch-decompositions by sequentially examining pairings of nodes of the separations of the branch-decompositions; and selecting a lowest cost ring path based upon such examinings.
Claim 2
Independent Claim
157 words
A method for selecting a communication ring path of lowest cost through a subset of nodes of a communication network, each edge of the network having a particular cost associated therewith, the method comprising the steps of providing a tree data structure wherein each leaf vertex of the tree represents an edge of the network and each non-leaf vertex of the tree is connected to exactly three edges of the tree, said tree data structure being a branch-decomposition having a pattern of separations of the network, a separation of the network corresponding to each edge of the tree; in response to each separation of said branch-decomposition having a number of nodes less than or equal to a predetermined constant, determining costs associated with portions of the ring path passing through separations of the branch-decompositions by sequentially examining pairings of nodes of the separations of the branch-decompositions; and selecting a lowest cost ring path based upon such examinings.
Claim 3
Dependent Claim
90 words
A method for selecting a communication path ring through a subset of nodes of a communication network in accordance with claim 1, wherein said step of providing a tree data structure which is a branch-decomposition includes the steps of: testing if an internal separation of order two exists in the communication network; separating the communication network using an internal separation of order two if such internal separation of order two exists; and repeating said testing and separating steps until no further internal separations of order two exist in the network.
Claim 4
Dependent Claim
89 words
A method for selecting a communication path ring through a subset of nodes of a communication network in accordance with claim 1, wherein said step of providing a tree data structure which is a branch-decomposition includes the steps of: testing if an internal separation of order three exists in the communication network; separating the communication network using an internal separation of order three if such a separation of order three exists; and repeating said testing and separating steps until no further separations of order three exist in the network.
Claim 5
Dependent Claim
95 words
A method for selecting a communication path ring through a subset of nodes of a communication network in accordance with claim 1, wherein said step of providing a tree data structure which is a branch-decomposition includes the steps of: selecting an eigenvector separation of the communication network; testing if said eigenvector separation has an order that is less than or equal to the predetermined constant; and in response to the order of separation being less than or equal to said predetermined constant, repeating said selecting and testing steps until no further separations can be performed.
Claim 6
Dependent Claim
31 words
A method for selecting a communication path ring through a subset of nodes of a communication network in accordance with claim 1 wherein said predetermined constant has a value of eight.
Claim 7
Dependent Claim
39 words
A method for selecting a communication path ring through a subset of nodes of a communication network in accordance with claim 1 further comprising the step of providing negative costs for some of the edges of the communication network.
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) | 1999-07-02 | 2000-01-01 | 2000-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-02 | 2004-01-01 | 2004-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-02 | 2008-01-01 | 2008-07-02 | $7700.00 | Window Closed / Lapsed |