Patent US6021113A successfully refreshed from Google Patents.
US6021113A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Distributed precomputation of network signal paths with table-based link capacity control
Assignee: Nokia of America Corp
•
Filing: 1997-10-29
•
Granted: 2000-02-01
•
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-10-29 15:10
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/0001; H04Q11/0005; H04J; H04J14/00; H04J14/02; H04J14/0227; H04J14/0241; H04J14/0278; H04J14/0284; H04Q2011/0037; H04Q2011/005; H04Q11/0062; H04Q2011/0079; H04Q2011/0081
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
187 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link is currently participating in link-based contention resolution with another demand and therefore can neither allocate capacity nor can it allow a requesting demand to enter a link-based contention resolution state.
Claim 2
Independent Claim
187 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link is currently participating in link-based contention resolution with another demand and therefore can neither allocate capacity nor can it allow a requesting demand to enter a link-based contention resolution state.
Claim 3
Independent Claim
175 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link has no spare capacity but it can allow a requesting demand to enter a link-based contention resolution state.
Claim 4
Independent Claim
175 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link has no spare capacity but it can allow a requesting demand to enter a link-based contention resolution state.
Claim 5
Independent Claim
153 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures; wherein the link status table is continuously updated as a corresponding link receives requests for network capacity from demands.
Claim 6
Independent Claim
153 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; and providing link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures; wherein the link status table is continuously updated as a corresponding link receives requests for network capacity from demands.
Claim 7
Independent Claim
204 words
An apparatus for use in 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 network wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link is currently participating in link-based contention resolution with another demand and therefore can neither allocate capacity nor can it allow a requesting demand to enter a link-based contention resolution state.
Claim 8
Independent Claim
204 words
An apparatus for use in 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 network wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link is currently participating in link-based contention resolution with another demand and therefore can neither allocate capacity nor can it allow a requesting demand to enter a link-based contention resolution state.
Claim 9
Independent Claim
192 words
An apparatus for use in 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 network, wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link has no spare capacity but it can allow a requesting demand to enter a link-based contention resolution state.
Claim 10
Independent Claim
192 words
An apparatus for use in 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 network, wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures, the link status table further including a link status indicator; wherein a value of the link status indicator indicates that the given link has no spare capacity but it can allow a requesting demand to enter a link-based contention resolution state.
Claim 11
Independent Claim
171 words
An apparatus for use in 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 are computation process for determining at least one signal path in the network, wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures; wherein the link status table is continuously updated as a corresponding link receives requests for network capacity from demands.
Claim 12
Independent Claim
171 words
An apparatus for use in 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 are computation process for determining at least one signal path in the network, wherein the nodal processor further provides link-based capacity control as part of the distributed precomputation process to identify demands contending for capacity on a specific link and to resolve contention on the specific link, wherein the link-based capacity control involves storing a link status table at one or more nodes controlling a given one of the links, the link status table listing a number of specific failures and demands which are affected by the failures; wherein the link status table is continuously updated as a corresponding link receives requests for network capacity from demands.
Claim 13
Dependent Claim
39 words
The method of claim 1 wherein a value of the link status indicator indicates that spare capacity is available for a specific failure and that the given link is ready to allocate and reserve capacity for a requesting demand.
Claim 14
Dependent Claim
39 words
The method of claim 1 wherein a value of the link status indicator indicates that the link has no spare capacity and also that it will not entertain any requests from demands to enter a link-based contention resolution state.
Claim 15
Dependent Claim
39 words
The method of claim 2 wherein a value of the link status indicator indicates that spare capacity is available for a specific failure and that the given link is ready to allocate and reserve capacity for a requesting demand.
Claim 16
Dependent Claim
39 words
The method of claim 2 wherein a value of the link status indicator indicates that the link has no spare capacity and also that it will not entertain any requests from demands to enter a link-based contention resolution state.
Claim 17
Dependent Claim
28 words
The method of claim 3 wherein the link status table includes, for one or more of the specific failures, an indication of spare capacity on a corresponding link.
Claim 18
Dependent Claim
39 words
The apparatus of claim 4 wherein a value of the link status indicator indicates that spare capacity is available for a specific failure and that the given link is ready to allocate and reserve capacity for a requesting demand.
Claim 19
Dependent Claim
39 words
The apparatus of claim 4 wherein a value of the link status indicator indicates that the link has no spare capacity and also that it will not entertain any requests from demands to enter a link-based contention resolution state.
Claim 20
Dependent Claim
39 words
The apparatus of claim 5 wherein a value of the link status indicator indicates that spare capacity is available for a specific failure and that the given link is ready to allocate and reserve capacity for a requesting demand.
Claim 21
Dependent Claim
39 words
The apparatus of claim 5 wherein a value of the link status indicator indicates that the link has no spare capacity and also that it will not entertain any requests from demands to enter a link-based contention resolution state.
Claim 22
Dependent Claim
28 words
The apparatus of claim 6 wherein the link status table includes, for one or more of the specific failures, an indication of spare capacity on a corresponding link.
References Cited (Backward Citations)
US5093824A
Cited
US5495471A
Cited
US5623481A
Cited
US5646936A
Cited
US5812524A
Cited
US5835482A
Cited
US5768256A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-31 | 2003-08-02 | 2004-02-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-31 | 2007-08-02 | 2008-02-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-31 | 2011-08-02 | 2012-02-01 | $7700.00 | Window Closed / Lapsed |