Patent US2105089A successfully refreshed from Google Patents.
US5274643A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for optimizing a network having virtual circuit routing over virtual paths
Assignee: Cisco Technology Inc
•
Filing: 1992-12-11
•
Granted: 1993-12-28
•
Expires: 2012-12-11
Abstract
Abstract Virtual circuits are routed and grouped into virtual paths during an interactive topology design process. Virtual circuits are assigned to virtual paths that provide minimum cost to each pass through a topology design. Virtual paths are dispersed into subgroups that minimize bandwidth consumption and maximize routing flexibility. This topology optimization process is constrained to minimize use of network resources.
Inventors
- 👤 Benjamin W. Fisk
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 23:00
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/10; G; G06; G06F; G06F30/00; G06F30/10; G06F30/18; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04Q3/00; H04Q3/58; H04Q3/62; H04J; H04J2203/00; H04J2203/0001; H04J2203/0051; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
178 words
A method for designing a telecommunications network topology comprising at least one site, each site comprising a number of nodes and virtual circuits between nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of: configuring an initial network topology; optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of; grouping virtual circuits at each node into virtual paths for routing comprising a step of merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency; wherein the network topology incorporating virtual paths is optimized.
Claim 2
Independent Claim
178 words
A method for designing a telecommunications network topology comprising at least one site, each site comprising a number of nodes and virtual circuits between nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of: configuring an initial network topology; optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of; grouping virtual circuits at each node into virtual paths for routing comprising a step of merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency; wherein the network topology incorporating virtual paths is optimized.
Claim 3
Dependent Claim
84 words
The method as set forth in claim 1, wherein the step for merging virtual circuit comprises the steps of: determining a cost measure for each virtual circuit between nodes; sorting the virtual circuits by the cost measure; examining each virtual circuit in sorted order; and merging the virtual circuit into a virtual path as a virtual path member if the maximum number of virtual path members has not been reached and if the virtual circuit has the same characteristics as other virtual path members.
Claim 4
Dependent Claim
32 words
The method as set forth in claim 2, wherein the cost measure is determined according to a measure of consumption of a link bandwidth between nodes and a minimum routing between nodes.
Claim 5
Dependent Claim
29 words
The method as set forth in claim 3, wherein the measure of consumption of link bandwidth between nodes is determined according to a minimum information rate for the node.
Claim 6
Dependent Claim
21 words
The measure as set forth in claim 3, wherein the minimum routing between nodes is determined according to a minimum hop.
Claim 7
Dependent Claim
75 words
The method as set forth in claim 2, wherein the step for determining the cost measure for each virtual circuit between nodes comprises the step of computing the cost measure according to the following equation: VIRTUAL CIRCUIT.sub.-- COST=MIR * MIN.sub.-- HOP wherein VIRTUAL CIRCUIT -- COST represents the cost measure, MIR represents the minimum information rate has the network and MIN -- HOP represents the minimum hop for the virtual circuit for the network topology.
Claim 8
Dependent Claim
72 words
The method as set forth in claim 2, wherein if a virtual circuit does not have the same characteristics as other virtual path members, said method further comprises the step of establishing an additional virtual path if the predetermined number of virtual paths for a node has not been exceeded, said virtual path having the characteristics of the virtual circuit, such that the virtual circuit becomes the leader for the virtual path.
Claim 9
Dependent Claim
79 words
The method as set forth in claim 2, wherein the step of splitting comprises the steps of: determining if a virtual path can be split by determining if both end nodes of the virtual path have not exceeded the predetermined number of virtual paths specified for a node and there is more than one virtual circuit in the virtual path; if the virtual path can be split, moving a portion of the virtual circuits to a new virtual path.
Claim 10
Dependent Claim
20 words
The method as set forth in claim 8, wherein alternate virtual path members are moved into a new virtual path.
Claim 11
Dependent Claim
27 words
The method as set forth in claim 9, wherein the virtual circuit having a lowest cost measure becomes a virtual path leader for the new virtual path.
Claim 12
Dependent Claim
41 words
The method as set forth in claim 8, further comprising the step of sorting the virtual paths according to a virtual paths cost measure and examining each virtual path in sorted order to determine if the virtual path can be split.
Claim 13
Dependent Claim
31 words
The method as set forth in claim 11, wherein the virtual path cost measure is determined according to the minimum number of hops to route the virtual path and bandwidth utilization.
Claim 14
Dependent Claim
32 words
The method as set forth in claim 8, wherein the step of splitting is continued until the resources at the node are exhausted or until all possible virtual paths have been split.
Claim 15
Dependent Claim
34 words
The method as set forth in claim 1, wherein a site comprises a plurality of nodes, and steps of grouping virtual circuits and splitting virtual paths are performed on a site by site basis.
Claim 16
Independent Claim
221 words
A method for designing a telecommunications network topology comprising multiple sites and virtual circuits between sites, each site comprising a number of nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of: (a) configuring an initial network topology; (b) optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of: grouping the virtual circuits at each node into virtual paths for routing comprising the steps of; determining a cost measure for each virtual circuit between nodes, and merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency; (c) determining a network cost for the topology; (d) configuring an alternate topology based on the network cost; (e) repeating steps (b), (c) and (d) until the network cost is minimized; wherein the network topology incorporating virtual paths is optimized.
Claim 17
Independent Claim
221 words
A method for designing a telecommunications network topology comprising multiple sites and virtual circuits between sites, each site comprising a number of nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of: (a) configuring an initial network topology; (b) optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of: grouping the virtual circuits at each node into virtual paths for routing comprising the steps of; determining a cost measure for each virtual circuit between nodes, and merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency; (c) determining a network cost for the topology; (d) configuring an alternate topology based on the network cost; (e) repeating steps (b), (c) and (d) until the network cost is minimized; wherein the network topology incorporating virtual paths is optimized.
Claim 18
Dependent Claim
157 words
A telecommunications network designed to incur minimum costs comprising at least one site comprising a plurality of nodes and virtual circuits between nodes, said network comprising at least one virtual path between nodes, each virtual path comprising a plurality of virtual circuits having like characteristics, the characteristics of the virtual path specified according to the characteristics of the virtual circuit which is a virtual path leader for the virtual path, each node accommodating a maximum number of virtual paths, the number of virtual paths and characteristics of virtual paths specified by merging virtual circuits at each node which have common characteristics including common node points into virtual paths, said virtual circuits merged in order of a cost measure determined for each virtual circuit, and splitting at least one virtual path at the node into two new virtual paths until the maximum number of virtual paths at the node is reached, to distribute resource usage and maximize efficiency.
Claim 19
Dependent Claim
157 words
A telecommunications network designed to incur minimum costs comprising at least one site comprising a plurality of nodes and virtual circuits between nodes, said network comprising at least one virtual path between nodes, each virtual path comprising a plurality of virtual circuits having like characteristics, the characteristics of the virtual path specified according to the characteristics of the virtual circuit which is a virtual path leader for the virtual path, each node accommodating a maximum number of virtual paths, the number of virtual paths and characteristics of virtual paths specified by merging virtual circuits at each node which have common characteristics including common node points into virtual paths, said virtual circuits merged in order of a cost measure determined for each virtual circuit, and splitting at least one virtual path at the node into two new virtual paths until the maximum number of virtual paths at the node is reached, to distribute resource usage and maximize efficiency.
Claim 20
Dependent Claim
40 words
The telecommunications network as set forth in claim 16 wherein the virtual circuit having a lowest cost measure in each new virtual path formed by splitting virtual paths is identified as the virtual path leader for the new virtual path.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-12-27 | 1997-06-28 | 1997-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-12-27 | 2001-06-28 | 2001-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-12-27 | 2005-06-28 | 2005-12-28 | $7700.00 | Window Closed / Lapsed |