Methods and apparatus for optimizing utilization in a ring network

• US 20060193632A1
• Filed: 02/25/2005
• Published: 08/31/2006
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Risbood, Pankaj
• Granted Patent: US 7,660,525 B2
• Time in Patent Office: Days
• US Class Current: 398/59
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 2011/0086 Network resource allocation, dimensioning or optimisation
• CPC Class Codes: H04Q 2011/0092 Ring

Abstract

Techniques are disclosed for generating a hitless migration plan to optimal state, given an optimal routing and wavelength assignment for demands. For example, a technique for use in performing a circuit transition in accordance with an optical ring-based network comprises the following steps/operations. First, a first (e.g., initial) circuit layout and a second (e.g., final) circuit layout for a given set of demands to be routed on the optical ring-based network are obtained. Then, a minimum number of free wavelengths required to transition the network from the first circuit layout to the second circuit layout is determined such that substantially no network service disruption occurs due to the circuit transition.

Claims

1. A method for use in performing a circuit transition in accordance with an optical ring-based network, comprising the steps of:

obtaining a first circuit layout and a second circuit layout for a given set of demands to be routed on the optical ring-based network; and

calculating a minimum number of free wavelengths required to transition the network from the first circuit layout to the second circuit layout such that substantially no network service disruption occurs due to the circuit transition.

2. The method of claim 1, wherein the first circuit layout is an initial circuit layout and the second circuit layout is a final circuit layout.

3. The method of claim 1, wherein the first circuit layout and the second circuit layout are each representable as a partition of the given set of demands into subsets, further wherein each subset is capable of being routed on a single wavelength.

4. The method of claim 3, wherein the calculating step comprises application of a first constraint that a circuit can be moved at most once in a transition sequence.

5. The method of claim 4, wherein the calculating step comprises application of a second constraint that, in any intermediate state during a transition sequence, a demand d_i either shares a wavelength with all demands in a set F_i or a subset of demands in a set O_i, where, for the demand d_i, sets O_i and F_i are subsets of the given set of demands that share a wavelength with d_i in the first circuit layout and the second circuit layout, respectively.

6. The method of claim 5, wherein the calculating step further comprises representing a transition from an first partition to a second partition of the demand set as a bipartite transition graph having nodes and edges, wherein each node of the graph corresponds to a subset in the first or second partition and each edge of the graph represents a transition of a demand from its first subset to its second subset.

7. The method of claim 6, wherein the calculating step further comprises:

inputting a connected component of the transition graph, the given set of demands, a first partition set P_o and a second partition set P_f; and

determining a transition sequence of intermediate states that require the minimum number of free wavelengths.

8. The method of claim 7, wherein the connected component of the transition graph comprises W_o nodes representing an initial state and W_f nodes representing a final state.

9. The method of claim 8, wherein, for each state i, W_i represents the number of required wavelengths excluding the free wavelengths.

10. The method of claim 9, wherein N_ij represents the minimum number of extra wavelengths needed to reach from a state S_i to a state S_j.

11. The method of claim 10, wherein, for a path in the state space from S_j to S_f via an intermediate state S_i, N_jif=N_ji+max(0,(N_if−

(W_j−

W_i)), and N_of=min(N_oif) ∀

states i.

12. The method of claim 10, wherein a state is represented as a bit vector of size W_f, with each bit corresponding to a subset in the second partition.

13. The method of claim 12, wherein if S_i is obtained from S_j such that {P_i∩

P_f)−

{P_j∩

P_f)=T, then N_ji is zero if there exist subsets Θ

_ixε

P_i such that Θ

_ix⊂

T, otherwise N_ji is one.

14. The method of claim 13, wherein the calculating step further comprises transitioning different connected components of the transition graph in an ascending order with respect to their free wavelength requirements.

15. The method of claim 1, wherein the optical ring-based network comprises a wavelength division multiplexing network, a synchronous optical network, or a synchronous digital hierarchy network.

16. Apparatus for use in performing circuit transition in accordance with an optical ring-based network, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain a first circuit layout and a second circuit layout for a given set of demands to be routed on the optical ring-based network; and

(ii) calculate a minimum number of free wavelengths required to transition the network from the first circuit layout to the second circuit layout such that substantially no network service disruption occurs due to the circuit transition.

17. The apparatus of claim 16, wherein the first circuit layout is an initial circuit layout and the second circuit layout is a final circuit layout.

18. An article of manufacture comprising a machine-readable medium storing one or more programs for use in performing circuit transition in accordance with an optical ring-based network, the one or more programs when executed in a processor implementing a method comprising the steps of:

obtaining a first circuit layout and a second circuit layout for a given set of demands to be routed on the optical ring-based network; and

calculating a minimum number of free wavelengths required to transition the network from the first circuit layout to the second circuit layout such that substantially no network service disruption occurs due to the circuit transition.