Distributed precomputation of network signal paths with table-based link capacity control
First Claim
1. 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 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
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
10 Claims
-
1. 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 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
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. - View Dependent Claims (2, 3, 4, 5)
-
-
6. 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 distributed precomputation process 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 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. - View Dependent Claims (7, 8, 9, 10)
Specification