US5787271A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Spare capacity allocation tool
Assignee: MCI Corp
•
Filing: 1996-06-26
•
Granted: 1998-07-28
•
Expires: 2016-06-26
Abstract
Abstract An apparatus and method is described that is used to design a minimal spares network for a given communications network. Three data files are used as input which describe the communications network. The information comprising such data files include the number and configuration of the nodes and spans, the current demand in terms of the required capacity between the source and destination nodes, current spare capacity (if any), and optionally current paths used to carry the demand traffic (including the presence or absence of glass-throughs). A three pass method is used to design an efficient and economical spares network from the given input data. A simulated cut is performed on each span in the communications network. From each simulated span cut, the affected demand traffic is identified and rerouted via spare capacity that is 'purchased' on an incremental cost basis. Pre-purchased spares are used before new spares are purchased.
Inventors
- 👤 Jay C. Box
- 👤 Sridhar S. Nathan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 23:05
CPC Classifications
H; H04; H04L; H04L41/00; H04L41/08; H04L41/0896
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
207 words
A method of deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the method comprising the steps of: (1) inputting a network model describing the physical topology of the network; (2) inputting demands for the network; (3) deriving a set of cutsite lists from said network model, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; (4) sorting said set of cutsite lists into a first sorted order according to a predefined sorting criteria; (5) processing said each cutsite list in said first sorted order to derive a first spares network comprising a first set of spare resources; (6) processing said each cutsite list in a second sorted order to derive a second spares network comprising a second set of spare resources; (7) initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second sets of spare resources; and (8) processing said each cutsite list to derive the minimal spares network.
Claim 2
Independent Claim
207 words
A method of deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the method comprising the steps of: (1) inputting a network model describing the physical topology of the network; (2) inputting demands for the network; (3) deriving a set of cutsite lists from said network model, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; (4) sorting said set of cutsite lists into a first sorted order according to a predefined sorting criteria; (5) processing said each cutsite list in said first sorted order to derive a first spares network comprising a first set of spare resources; (6) processing said each cutsite list in a second sorted order to derive a second spares network comprising a second set of spare resources; (7) initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second sets of spare resources; and (8) processing said each cutsite list to derive the minimal spares network.
Claim 3
Dependent Claim
89 words
The method of claim 1, wherein said processing steps 5,6, and 8, each comprise the steps of: (a) initializing a resulting spares network from said network model; (b) for each said cutsite list, simulating at least one severed span by removing said at least one span from said network model; (c) rerouting each demand in said list of affected demands by using spare resources in said resulting spares network, if available, and by adding new spare resources to said resulting spares network, if no said spare resources are available.
Claim 4
Dependent Claim
165 words
The method of claim 2, wherein said rerouting step comprises the steps of (i) determining an alternate route for each said demand; (ii) identifying zero spans in said alternate route which comprise spans having no available spare resources; (iii) determining a routing capacity, wherein said routing capacity is equal to the capacity of available spare resources within a single span in said alternate route having the least amount of available spare resources therein, not including said zero spans; (iv) rerouting the remaining affected demand, up to a maximum capacity equal to the lessor of said routing capacity and said remaining affected demand; (v) if at least one said zero span is identified in step (2)(b)(ii), adding new spare capacity to said resulting spares network by adding a capacity equal to the capacity rerouted in step (2)(b)(iv) to each of said zero spans. (vi) if all of said affected demand has not been rerouted, repeat at least steps (2)(b)(i)-(2)(b)(v), until all said affected demand is rerouted.
Claim 5
Dependent Claim
15 words
The method of claim 3 wherein step (2)(b)(i) comprises a minimum weighted path based solution.
Claim 6
Dependent Claim
22 words
The method of claim 1 wherein said predefined sort criteria includes a total of affected demand capacity within each said cutsite list.
Claim 7
Dependent Claim
25 words
The method of claim 1 wherein said network model includes a node data file comprising a list identifying the plurality of nodes within the network.
Claim 8
Dependent Claim
18 words
The method of claim 1, wherein said second sorted order is the reverse of said first sorted order.
Claim 9
Dependent Claim
35 words
The method of claim 1 wherein said network model includes a span data file comprising a listing for each of said plurality of spans, each said listing includes two interconnecting nodes and a span length.
Claim 10
Dependent Claim
32 words
The method of claim 1 wherein said demands comprises a demand data file comprising an entry for each demand, each said entry comprises a source node, a destination node, and a capacity.
Claim 11
Dependent Claim
15 words
The method of claim 9 wherein said entry for each demand further comprises routing information.
Claim 12
Dependent Claim
32 words
The method of claim 10, wherein said entry for each demand further comprises information relating to whether each node in said routing information is connected via a cross-connection or a bypass connection.
Claim 13
Dependent Claim
229 words
A computer program-product storage device readable by a computer system, tangibly embodying a computer program-product comprising instructions executable by the computer system to perform method steps for deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the method comprising the steps of: (1) inputting a network model describing the physical topology of the network; (2) inputting demands for the network; (3) deriving a set of cutsite lists from said network model, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; (4) sorting said set of cutsite lists into a sorted order according to a predefined sorting criteria; (5) processing said each cutsite list in said sorted order to derive a first spares network comprising a first set of spare resources; (6) processing said each cutsite list in a reverse sorted order to derive a second spares network comprising a second set of spare resources; (7) initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second sets of spare resources; and (8) processing said each cutsite list to derive the minimal spares network.
Claim 14
Dependent Claim
229 words
A computer program-product storage device readable by a computer system, tangibly embodying a computer program-product comprising instructions executable by the computer system to perform method steps for deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the method comprising the steps of: (1) inputting a network model describing the physical topology of the network; (2) inputting demands for the network; (3) deriving a set of cutsite lists from said network model, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; (4) sorting said set of cutsite lists into a sorted order according to a predefined sorting criteria; (5) processing said each cutsite list in said sorted order to derive a first spares network comprising a first set of spare resources; (6) processing said each cutsite list in a reverse sorted order to derive a second spares network comprising a second set of spare resources; (7) initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second sets of spare resources; and (8) processing said each cutsite list to derive the minimal spares network.
Claim 15
Dependent Claim
91 words
The computer program-product storage device of claim 12, wherein said processing steps 5,6, and 8, each comprise the steps of: (a) initializing a resulting spares network from said network model; (b) for each said cutsite list, simulating at least one severed span by removing said at least span from said network model; (c) rerouting each demand in said list of affected demands by using spare resources in said resulting spares network, if available, and by adding new spare resources to said resulting spares network, if no said spare resources are available.
Claim 16
Dependent Claim
168 words
The computer program-product storage device of claim 13, wherein said rerouting step comprises the steps of: (i) determining an alternate route for each said demand; (ii) identifying zero spans in said alternate route which comprise spans having no available spare resources; (iii) determining a routing capacity, wherein said routing capacity is equal to the capacity of available spare resources within a single span in said alternate route having the least amount of available spare resources therein, not including said zero spans; (iv) rerouting the remaining affected demand, up to a maximum capacity equal to the lessor of said routing capacity and said remaining affected demand; (v) if at least one said zero span is identified in step (12)(b)(ii), adding new spare capacity to said resulting spares network by adding a capacity equal to the capacity rerouted in step (12)(b)(iv) to each of said zero spans. (vi) if all of said affected demand has not been rerouted, repeat at least steps (12)(b)(i)-(12)(b)(v), until all said affected demand is rerouted.
Claim 17
Dependent Claim
18 words
The computer program-product storage device of claim 14 wherein step (12)(b)(i) comprises a minimum weighted path based solution.
Claim 18
Dependent Claim
25 words
The computer program-product storage device of claim 12 wherein said predefined sort criteria includes a total of affected demand capacity within each said cutsite list.
Claim 19
Dependent Claim
28 words
The computer program-product storage device of claim 12 wherein said network model includes a node data file comprising a list identifying the plurality of nodes within the network.
Claim 20
Dependent Claim
38 words
The computer program-product storage device of claim 12 wherein said network model includes a span data file comprising a listing for each of said plurality of spans, each said listing includes two interconnecting nodes and a span length.
Claim 21
Dependent Claim
35 words
The computer program-product storage device of claim 12 wherein said demands comprises a demand data file comprising an entry for each demand, each said entry comprises a source node, a destination node, and a capacity.
Claim 22
Dependent Claim
18 words
The computer program-product storage device of claim 19 wherein said entry for each demand further comprises routing information.
Claim 23
Dependent Claim
35 words
The computer program-product storage device of claim 20, wherein said entry for each demand further comprises information relating to whether each node in said routing information is connected via a cross-connection or a bypass connection.
Claim 24
Dependent Claim
34 words
The computer program-product storage device of claim 21, wherein said each cutsite list further comprises a list of spare resources that would be severed if said at least one span were to be severed.
Claim 25
Independent Claim
236 words
A system for deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the system comprising: network modeling means for providing a network model that defines the physical topology of the network; demand modeling means for modeling the demands of the network; simulator means for simulating a severed span within said network model; cutsite means for deriving a set of cutsite lists from said network modeling means, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; sorting means for sorting said set of cutsite lists into a first sorted order according to a predefined sorting criteria; first processing means for processing said each cutsite list in said first sorted order to derive a first spares network comprising a first set of spare resources; second processing means for processing said each cutsite list in a second sorted order to derive a second spares network comprising a second set of spare resources; initializing means for initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second processing means; and third processing for processing said each cutsite list to derive the minimal spares network.
Claim 26
Independent Claim
236 words
A system for deriving a minimal spares network for a communications network comprising a plurality of nodes and a plurality of spans interconnecting the nodes, the system comprising: network modeling means for providing a network model that defines the physical topology of the network; demand modeling means for modeling the demands of the network; simulator means for simulating a severed span within said network model; cutsite means for deriving a set of cutsite lists from said network modeling means, wherein each cutsite list identifies at least one span from said plurality of spans, and comprises a list of affected demands that would be interrupted if said at least one span were to be severed; sorting means for sorting said set of cutsite lists into a first sorted order according to a predefined sorting criteria; first processing means for processing said each cutsite list in said first sorted order to derive a first spares network comprising a first set of spare resources; second processing means for processing said each cutsite list in a second sorted order to derive a second spares network comprising a second set of spare resources; initializing means for initializing the minimal spares network with an initial set of spare resources that are derived from the spare resources that are common among said first and said second processing means; and third processing for processing said each cutsite list to derive the minimal spares network.
Claim 27
Dependent Claim
14 words
The system of claim 23, wherein said network modeling means comprises a network modeler.
Claim 28
Dependent Claim
14 words
The system of claim 23, wherein said demand modeling means comprises a demand modeler.
Claim 29
Dependent Claim
14 words
The system of claim 23, wherein said simulator means comprises a span cut simulator.
Claim 30
Dependent Claim
11 words
The system of claim 23, wherein sorting means comprises a sorter.
Claim 31
Dependent Claim
19 words
The system of claim 23, wherein said first, second and third processing means each comprises a cutsite list processor.
References Cited (Backward Citations)
US4956835A
Cited
US5235599A
Cited
US5481604A
Cited
US5491690A
Cited
US5537532A
Cited
US5459716A
Cited
US5659796A
Cited
US5627971A
Cited
US5657320A
Cited
US5623481A
Cited
US5646936A
Cited
US5590119A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-27 | 2002-01-26 | 2002-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-27 | 2006-01-26 | 2006-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-27 | 2010-01-26 | 2010-07-28 | $7700.00 | Window Closed / Lapsed |