Multi-phase process for distributed precomputation of network signal paths

• US 6,215,763 B1
• Filed: 10/29/1997
• Issued: 04/10/2001
• Est. Priority Date: 10/29/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wang, Yufei, Harshavardhana, Paramasiviah, Dravida, Subrahmanyam, Doshi, Bharat Tarachand
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US08/960,463
• Time in Patent Office: 1,259 Days
• Field of Search: 370/216, 370/16, 370/221, 370/228, 370/217, 370/222, 370/244, 370/224, 370/468, 370/465, 370/252, 395/182.02, 395/575, 714/1, 714/2, 714/3, 714/4, 714/7, 714/8, 340/617, 340/618
• US Class Current: 370/216
• CPC Class Codes: H04J 14/0227 Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
• CPC Class Codes: H04J 14/0241 Wavelength allocation for communications one-to-one, e.g. unicasting wavelengths
• CPC Class Codes: H04J 14/0278 WDM optical network architectures
• CPC Class Codes: H04J 14/0284 WDM mesh architectures
• CPC Class Codes: H04Q 11/0005 Switch and router aspects
• CPC Class Codes: H04Q 2011/005 Arbitration and scheduling
• CPC Class Codes: H04Q 2011/0081 Fault tolerance; Redundancy; Recovery; Reconfigurability

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.

Claims

1. A method of determining signal paths for capacity demands in a communication 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 communication network using a distributed precomputation process implemented by at least a subset of the plurality of nodes; and

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, and wherein determination of a path does not depend on a particular failure in the network due to a use of one or more disjoint paths.

2. The method of claim 1 wherein the first phase of the distributed precomputation process includes a contention locking mechanism which locks a primary path of a given capacity demand to prevent other demands from contending for the same capacity.

3. The method of claim 1 wherein a primary path for the particular demand is removed from consideration in a restoration path search for that demand, such that the primary and restoration paths for that demand are failure disjoint.

4. The method of claim 1 wherein the first phase of the distributed precomputation process provides link capacity control, wherein the link 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.

5. The method of claim 1 wherein the second phase of the distributed precomputation process reroutes paths previously allocated to one or more demands in order to free up capacity required for another demand.

6. The method of claim 1 wherein the first phase includes the steps of:

selecting a demand for which a restoration path is to be computed;

sending a locking message along a primary path of the selected demand in order to lock the primary path;

if the locking of the primary path is not successful, waiting for a period of time and then re-sending the locking message; and

if the locking of the primary path is successful, initiating a restoration path search for the demand with the primary path of the demand removed from consideration.

7. The method of claim 6 wherein the first phase includes the steps of:

if a restoration path is found for the demand, releasing the lock on the primary path of the demand and storing the restoration path for the demand; and

if a restoration path is not found for the demand, releasing the lock on the primary path of the demand and waiting for the second phase.

8. The method of claim 1 wherein the second phase includes the steps of:

selecting a first demand for which a restoration path is to be computed;

identifying a second demand with which to negotiate;

locking the primary paths of the first and second demands;

releasing the capacity associated with the second demand, and initiating a restoration path search for the first demand with the primary path of the demand removed from consideration; and

if a restoration path is not found for the first demand, releasing the lock on the primary path of the second demand and selecting another demand for negotiation.

9. The method of claim 8 wherein the second phase includes the steps of:

if a restoration path is found for the first demand, initiating a restoration path search for the second demand;

if a restoration path is found for the second demand, releasing the locks on the primary paths of the first and second demands, and storing the restoration paths for the first and second demands; and

if a restoration path is not found for the second demand, determining a restoration path for the first demand, using a search in which high costs are assigned to links in a cut set identified in a failed path search for the second demand, and initiating a path search for the second demand.

10. The method of claim 9 wherein the second phase includes the steps of:

if a restoration path is found for the second demand, releasing the locks on the primary paths of the first and second demands, and storing the restoration paths for the first and second demands; and

if a restoration path is not found for the second demand, releasing the lock on the primary path of the second demand and selecting another demand for negotiation.

11. The method of claim 1 wherein the distributed precomputation process computes primary and restoration paths at the same wavelength for each of a plurality of demands, with no sharing of restoration capacity between the demands.

12. The method of claim 1 wherein the distributed precomputation process computes primary and restoration paths at the same wavelength for each of a plurality of demands, with sharing of restoration capacity permitted between different demands which are not both affected by any single failure.

13. An apparatus for use in determining signal paths for capacity demands in a communication 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 communication 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 resolving contentions, 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 due to a use of one or more disjoint paths.

14. The apparatus of claim 13 wherein the first phase of the distributed precomputation process includes a contention locking mechanism which locks a primary path of a given capacity demand to prevent other demands from contending for the same capacity.

15. The apparatus of claim 13 wherein a primary path for the particular demand is removed from consideration in a restoration path search for that demand, such that the primary and restoration paths for that demand are failure disjoint.

16. The apparatus of claim 13 wherein the first phase of the distributed precomputation process provides link capacity control, wherein the link 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.

17. The apparatus of claim 13 wherein the second phase of the distributed precomputation process reroutes paths previously allocated to one or more demands in order to free up capacity required for another demand.