Patent US5979745A successfully refreshed from Google Patents.
US6151304A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Distributed precomputation of network signal paths with improved performance through parallelization
Assignee: Nokia of America Corp
•
Filing: 1997-10-29
•
Granted: 2000-11-21
•
Expires: 2017-10-29
Abstract
Abstract Distributed precomputation techniques for determining primary and/or restoration paths in an optical or electrical network. The invention provides a number of partially and fully asynchronous distributed precomputation algorithms which may be implemented, for example, by the nodes of an all-optical network, in which network links are constrained in terms of optical signal wavelength and failure isolation. A given distributed precomputation algorithm may include a first phase in which paths are allocated for capacity demands to the extent possible without resolving contentions, and a second phase in which contentions between demands for the same capacity are resolved. The first phase may implement a contention locking mechanism which locks a primary path of a given demand to prevent other demands from contending for the same capacity, and a link capacity control mechanism which involves storing a link status table at one or more nodes, the link status table listing a number of specific failures and demands which are affected by the failures. The second phase of the distributed precomputation algorithm reroutes paths previously allocated to one or more demands in order to free up capacity required for another demand, so as to optimize overall network capacity utilization.
Inventors
- 👤 Bharat Tarachand Doshi
- 👤 Subrahmanyam Dravida
- 👤 Paramasiviah Harshavardhana
- 👤 Yufei Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:48
CPC Classifications
H; H04; H04J; H04J14/00; H04J14/02; H04J14/0227; G; G06; G06F; G06F17/00; G06F17/10; H04J14/0241; H04J14/0278; H04J14/0284
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
160 words
A method of determining signal paths for capacity demands in a network which includes a plurality of nodes and a plurality of links, each of the links interconnecting a pair of nodes, the method comprising the steps of: determining at least one signal path in the network using a distributed precomputation process implemented by at least a subset of the plurality of nodes, wherein the distributed precomputation process implemented by the nodes includes a first phase in which paths are allocated for capacity demands to the extent possible without violating capacity constraints, and a second phase in which contentions between demands for the same capacity are resolved, and wherein determination of a path does not depend on a particular failure in the network; and utilizing at least one parallelization mechanism to improve the efficiency of the distributed precomputation process by at least substantially reducing contention among demands, wherein the parallelization mechanism permits multiple demands to be routed substantially in parallel.
Claim 2
Independent Claim
160 words
A method of determining signal paths for capacity demands in a network which includes a plurality of nodes and a plurality of links, each of the links interconnecting a pair of nodes, the method comprising the steps of: determining at least one signal path in the network using a distributed precomputation process implemented by at least a subset of the plurality of nodes, wherein the distributed precomputation process implemented by the nodes includes a first phase in which paths are allocated for capacity demands to the extent possible without violating capacity constraints, and a second phase in which contentions between demands for the same capacity are resolved, and wherein determination of a path does not depend on a particular failure in the network; and utilizing at least one parallelization mechanism to improve the efficiency of the distributed precomputation process by at least substantially reducing contention among demands, wherein the parallelization mechanism permits multiple demands to be routed substantially in parallel.
Claim 3
Dependent Claim
18 words
The method of claim 1 wherein the parallelization mechanism provides contention resolution among one or more contending demands.
Claim 4
Dependent Claim
30 words
The method of claim 1 wherein the parallelization mechanism involves processing the demands in an order which is determined to improve a path search operation of the distributed precomputation process.
Claim 5
Dependent Claim
55 words
The method of claim 1 wherein a given one of the nodes implementing the distributed precomputation process sends a locking message along a primary path of a particular demand prior to initiating a search for a restoration path for that demand, in order to lock out other demands which may contend for the same capacity.
Claim 6
Dependent Claim
38 words
The method of claim 4 wherein the primary path for the particular demand is removed from consideration in the restoration path search for that demand, such that the primary and restoration paths for that demand are failure disjoint.
Claim 7
Dependent Claim
42 words
The method of claim 2 wherein the contention resolution involves identifying a set of links having no available capacity, and attempting to reroute a demand already allocated capacity on one of the links, so as to free up capacity for another demand.
Claim 8
Dependent Claim
27 words
The method of claim 6 wherein the contention resolution includes a locking mechanism for locking one or more primary paths of demands participating in the contention resolution.
Claim 9
Dependent Claim
66 words
The method of claim 1 wherein the distributed precomputation process implemented by the nodes includes a first phase in which paths are allocated for capacity demands to the extent possible without resolving contentions, and a second phase in which contentions between demands for the same capacity are resolved using a contention resolution mechanism in which selected demands are rerouted to free up capacity for other demands.
Claim 10
Dependent Claim
13 words
The method of claim 1 wherein the distributed precomputation process is fully asynchronous.
Claim 11
Dependent Claim
85 words
The method of claim 1 wherein the distributed precomputation process includes: selecting a first demand which does not yet have a restoration path; sending a locking message along a primary path of the first demand; if the primary path is successfully locked, initiating a search for a restoration path for the first demand with the primary path of the first demand removed from consideration; and if a restoration path is found, unlocking the primary path of the first demand, and storing the restoration path information.
Claim 12
Dependent Claim
84 words
The method of claim 10 wherein the distributed precomputation process includes: if a restoration path is not found for the first demand, selecting a second demand which has already been routed and has a cut set of links having no spare capacity; sending a locking message along a primary path of the second demand; if the locking is successful, releasing capacity consumed by a restoration path previously allocated to the second demand; and initiating a search for a restoration path for the first demand.
Claim 13
Dependent Claim
127 words
The method of claim 11 wherein the distributed precomputation process includes: if a restoration path is found for the first demand, initiating a path search for a restoration path for the second demand; if a restoration path is found for the second demand, unlocking the primary paths of the first and second demand, and storing the restoration path information for the first and second demand; and if a restoration path is not found for the second demand, releasing the capacity consumed by the restoration path of the first demand, determining another restoration path for the first demand in a manner which avoids links identified in the previous restoration path search for the second demand, and initiating a second search for a restoration path for the second demand.
Claim 14
Dependent Claim
47 words
The method of claim 12 wherein if a restoration path is not found in the second search for the second demand, unlocking the primary path of the second demand and selecting another demand to negotiate with in attempting to determine a restoration path for the first demand.
Claim 15
Dependent Claim
50 words
The method of claim 1 wherein the distributed precomputation process includes: initiating a search for a restoration path for a demand with the primary path of the demand removed from consideration; continuing the search until a destination node has sent an indication of an available restoration path with sufficient capacity.
Claim 16
Dependent Claim
64 words
The method of claim 1 wherein the distributed precomputation process includes: receiving in a node of the network a request for capacity for a demand; reserving the requested capacity for the demand if the requested capacity is available; updating a link status table; and sending a message to a next node in a path search order to indicate if the capacity has been reserved.
Claim 17
Dependent Claim
61 words
The method of claim 1 wherein the distributed precomputation process includes: receiving in a first node a request for capacity from a second node; determining if one or more paths with sufficient capacity exist; selecting one of the paths; sending messages to release capacity on the unselected paths; and sending a message to notify the first node of the selected path.
Claim 18
Dependent Claim
75 words
The method of claim 1 wherein the distributed precomputation process includes: search for a restoration path for a first demand with a primary path of the first demand removed from consideration; receiving from a destination node information regarding contending demands for a given candidate path; requesting permission from the contending demands for contention resolution; and initiating a contention resolution process if permission is received from all of the contending demands for the given candidate path.
Claim 19
Dependent Claim
73 words
The method of claim 1 wherein the distributed precomputation process includes: receiving in a destination node a capacity request from a source node along with bottleneck links and contending demands for a restoration path search for a first demand; selecting the path with the least number of bottlenecks; requesting release of capacity on the remaining paths; and informing the source node of the selected path and its corresponding bottleneck links and contending demands.
Claim 20
Dependent Claim
69 words
The method of claim 1 wherein the distributed precomputation process includes: receiving in a first node a request from a second node for capacity for a demand; reserving the requested capacity if sufficient capacity is available on the corresponding link; updating a link status table to reflect the reservation of capacity; and sending a message indicating the reservation of capacity to a next node in a path search order.
Claim 21
Dependent Claim
70 words
The method of claim 1 wherein the distributed precomputation process includes: receiving in a first node a request from a second node for permission to resolve contention between a first demand and a second demand; denying permission if the second demand is already involved in contention resolution; and granting permission and updating a contention status of the first demand if the second demand is not already involved in contention resolution.
Claim 22
Dependent Claim
103 words
The method of claim 1 wherein the distributed precomputation process includes: sorting a first set of demands in order of path collision indexes, wherein the set of demands includes demands for which restoration paths have not been found due to contentions with other demands, and the collision index for a given path indicates the number of links of that path on which a given demand contends with a routed demand; and selecting one of the demands from the sorted first set for contention resolution based at least in part on its position in the sorted set relative to other demands in the set.
Claim 23
Dependent Claim
73 words
The method of claim 21 wherein the distributed precomputation process includes: searching a second set of demands which have a fault set which is disjoint from that of a demand selected from the first set, wherein a fault set of a given demand includes all faults that affect the given demand on its primary path; selecting a demand from the second set for contention resolution based on the results of the searching step.
Claim 24
Dependent Claim
85 words
The method of claim 22 wherein the distributed precomputation process includes: performing contention resolution for a set of all demands that can perform contention resolution in parallel with the demand selected from the second set; removing from the first set each demand from that set which is successfully rerouted as a result of the contention resolution; and repeating the steps of sorting the first set of demands, and searching and selecting from the second set of demands until the first set of demands is empty.
Claim 25
Dependent Claim
32 words
The method of claim 1 wherein the distributed precomputation process computes link, span and node disjoint primary and restoration paths for a given demand, without sharing of restoration capacity between different demands.
Claim 26
Dependent Claim
43 words
The method of claim 1 wherein the distributed precomputation process computes link, span and node disjoint primary and restoration paths for a given demand, with the same wavelength on both primary and restoration paths, and without sharing of restoration capacity between different demands.
Claim 27
Dependent Claim
40 words
The method of claim 1 wherein the distributed precomputation process computes link, span and node disjoint primary and restoration paths for a given demand, with sharing of restoration capacity permitted between different demands not affected by any single common failure.
Claim 28
Independent Claim
176 words
An apparatus for determining signal paths for capacity demands in a network which includes a plurality of nodes and a plurality of links, each of the links interconnecting a pair of nodes, the apparatus comprising: a nodal processor associated with a corresponding one of the plurality of nodes in the network, the nodal processor implementing at least a portion of a distributed precomputation process for determining at least one signal path in the optical network, wherein the distributed precomputation process implemented by the nodal processor includes a first phase in which paths are allocated for capacity demands to the extent possible without violating capacity constraints, and a second phase in which contentions between demands for the same capacity are resolved, wherein determination of a path does not depend on a particular failure in the network, and wherein the nodal processor utilizes at least one parallelization mechanism to improve the efficiency of the distributed precomputation process by at least substantially reducing contention among demands, and the parallelization mechanism permits multiple demands to be routed substantially in parallel.
Claim 29
Independent Claim
176 words
An apparatus for determining signal paths for capacity demands in a network which includes a plurality of nodes and a plurality of links, each of the links interconnecting a pair of nodes, the apparatus comprising: a nodal processor associated with a corresponding one of the plurality of nodes in the network, the nodal processor implementing at least a portion of a distributed precomputation process for determining at least one signal path in the optical network, wherein the distributed precomputation process implemented by the nodal processor includes a first phase in which paths are allocated for capacity demands to the extent possible without violating capacity constraints, and a second phase in which contentions between demands for the same capacity are resolved, wherein determination of a path does not depend on a particular failure in the network, and wherein the nodal processor utilizes at least one parallelization mechanism to improve the efficiency of the distributed precomputation process by at least substantially reducing contention among demands, and the parallelization mechanism permits multiple demands to be routed substantially in parallel.
Claim 30
Dependent Claim
18 words
The apparatus of claim 27 wherein the parallelization mechanism provides contention resolution among one or more contending demands.
Claim 31
Dependent Claim
30 words
The apparatus of claim 27 wherein the parallelization mechanism involves processing the demands in an order which is determined to improve a path search operation of the distributed precomputation process.
Claim 32
Dependent Claim
55 words
The apparatus of claim 27 wherein a given one of the nodes implementing the distributed precomputation process sends a locking message along a primary path of a particular demand prior to initiating a search for a restoration path for that demand, in order to lock out other demands which may contend for the same capacity.
Claim 33
Dependent Claim
38 words
The apparatus of claim 30 wherein the primary path for the particular demand is removed from consideration in the restoration path search for that demand, such that the primary and restoration paths for that demand are failure disjoint.
Claim 34
Dependent Claim
42 words
The apparatus of claim 28 wherein the contention resolution involves identifying a set of links having no available capacity, and attempting to reroute a demand already allocated capacity on one of the links, so as to free up capacity for another demand.
Claim 35
Dependent Claim
27 words
The apparatus of claim 32 wherein the contention resolution includes a locking mechanism for locking one or more primary paths of demands participating in the contention resolution.
Claim 36
Dependent Claim
68 words
The apparatus of claim 27 wherein the distributed precomputation process is implemented by the nodes and includes a first phase in which paths are allocated for capacity demands to the extent possible without resolving contentions, and a second phase in which contentions between demands for the same capacity are resolved using a contention resolution mechanism in which selected demands are rerouted to free up capacity for other demands.
Claim 37
Dependent Claim
13 words
The apparatus of claim 27 wherein the distributed precomputation process is fully asynchronous.
References Cited (Backward Citations)
US4956835A
Cited
US5093824A
Cited
US5435003A
Cited
US5537532A
Cited
US5581689A
Cited
US5646936A
Cited
US5835482A
Cited
US5850505A
Cited
US5933590A
Cited
US5781535A
Cited
US5943314A
Cited
US5856981A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-21 | 2004-05-22 | 2004-11-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-21 | 2008-05-22 | 2008-11-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-21 | 2012-05-22 | 2012-11-21 | $7700.00 | Window Closed / Lapsed |