WO2014126976A1

WO2014126976A1 - Network fragmentation measurement in an optical wavelength division multiplexing (wdm) network

Info

Publication number: WO2014126976A1
Application number: PCT/US2014/015971
Authority: WO
Inventors: Ankitkumar Patel; Philip Nan Ji
Original assignee: NEC Laboratories America Inc
Current assignee: NEC Laboratories America Inc
Priority date: 2013-02-14
Filing date: 2014-02-12
Publication date: 2014-08-21
Anticipated expiration: 2015-08-14
Also published as: WO2014126977A1; JP2016511577A; US20140226986A1; EP2957055A1; US9166723B2; US20140226985A1; EP2957055B1; EP2957054B1; EP2957055A4; JP6125667B2; JP2016511576A; JP6181775B2; EP2957054A4; EP2957054A1; US9160477B2

Abstract

A method implemented in a network apparatus used in a wavelength division multiplexing (WDM) optical network is disclosed. The method includes (a) finding K-shortest routes between each node pair (s, d), where s, d ∈ V and |V| ≤ K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes, (b) selecting unconsidered node pair (s, d), (c) selecting unconsidered route k between nodes s and d out of the K-shortest routes, (d) finding a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k, (e) selecting unconsidered line rate l out of offered set L of line rates, and (f) finding a probability αl ^s,d,k of provisioning a connection with line rate l. Other apparatuses, systems, and methods also are disclosed.

Description

Network Fragmentation Measurement in an Optical Wavelength Division

Multiplexing (WDM) Network

[0001] This application claims the benefit of U.S. Provisional Application No. 61/764,568, entitled "Procedure to Measure Network Fragmentation in Optical WDM Networks," filed on February 14, 2013, the contents of which are incorporated herein by reference.

[0002] This application is related to commonly assigned application No. (Attorney

Docket No. 12121), entitled "A Virtual Network Embedding Procedure in an Optical Wavelength Division Multiplexing (WDM) Network," filed concurrently herewith, the contents of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

[0003] The present invention relates to wavelength division multiplexing (WDM) optical networks and, more particularly, to measurement of spectral fragmentation in the WDM networks.

[0004] In wavelength division multiplexing (WDM) optical networks, upon an arrival of a demand requesting a line rate between end nodes, an optical channel is established by allocating finite amount of spectrum on all fibers along the route. If an intermediate node along the route does not support wavelength conversion capability, then the channel must follow the wavelength continuity constraint, which is defined as an allocation of the same center wavelength to the channel, and the spectral continuity constraint, which is defined as an allocation of the same amount of spectrum to the channel in the ingress and egress fibers of a node. To support multiple such channels over a fiber, the spectral conflict constraint must be satisfied, which is defined as an allocation of non-overlapping spectrum to the channels routes over the same fiber.

[0005] Conventionally to address interoperability issues, the International Telecommunication Union Telecommunication Standardization Sector (ITU-T) has standardized fixed channel spacing [1]. The network that follows the ITU-T standard is referred to as fixed grid network as shown in Fig. 1(a). Fixed grid networks may not optimize spectral efficiency while supporting line rates with heterogeneous granularity for ever increasing bandwidth demands. Recently, flexible grid network architecture (as shown in Fig. 1(b)) is introduced in which flexible amount of spectrum is assigned to channels based on the requirements of requested bandwidth, transmission reach, and offered modulation formats. Flexible grid networks highly optimize network spectral efficiency. However, dynamic arrival and departure of channels with heterogeneous spectrum requirements causes fragmentations in spectrum (as shown in Fig. 2), and the network can no longer be in its optimal state. The state of fragmented spectrum in a network is referred to as network fragmentation. Network fragmentation is a serious issue in fixed and flexible grid networks. Spectral fragmentation can block a connection in spite of the availability of sufficient amount of spectrum for the connection and deteriorate the network performance.

[0006] To restore a network in its optimal state and enhance the blocking performance, several network defragmentation schemes are investigated [2] [3] [4]. However, in order to make timely judgments on when to defragment the network and to verify the effectiveness of network defragmentation or resource provisioning solutions, there is a need to accurately measure the network state. Thus, the problem is how to quantify the fragmentation in a network. The problem is formally defined as follows.

[0007] We are given an optical network topology G(V, E), where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes and E is a set of fibers connecting ROADM nodes. The network supports a set of line rates L. The required spectral width for each line rate is Hi GHz for a line rate /. The network offers total Z GHz of spectrum to support the network traffic. A connection demand requesting a line rate / between a set of nodes arrive with probability Qi. The problem is how to measure spectral fragmentation in the network.

[0008] In [5], a Spectrum Compactness parameter is introduced to quantify fragmentation over a fiber based on the occupied and available spectrum slots. In [6], Utilization Entropy parameter is introduced to evaluate fragmentation over a fiber based on the number of changes in the states of spectrum. Both of these parameters do not consider fiber correlations while measuring network fragmentation.

[0009] References

[0010] [1] ITU-T G.694.1, "Spectral grids for WDM applications: DWDM frequency grid," May 2002.

[0011] [2] A. N. Patel, P. N. Ji, J. P. Jue, and T. Wang, "Defragmentation of Transparent Flexible Optical WDM (FWDM) Networks," Proceeding of OFCNFOEC, no. OTuI8, Mar 2011.

[0012] [3] F. Cugini, M. Secondini, N. Sambo, G. Bottari, G. Bruno, P. Iovanna, and P. Castoldi, "Push-Pull Technique for Defragmentation in Flexible Optical Networks, " Proceeding of OFCNFOEC, no. JTh2A.40, Mar. 2012.

[0013] [4] K. Wen, Y. Yin, D. Geisler, S. Chang, and S. J. Ben Yoo, "Dynamic On-demand Lightpath Provisioning Using Spectral Defragmentation in Flexible Bandwidth Networks," Proc. of ECOC, no. Mo.2.K.4, 2011.

[0014] [5] X. Yu, J. Zhang, Y. Zhao, T. Peng, Y. Bai, D. Wang, and X. Lin, "Spectrum Compactness based Defragmentation in Flexible Bandwidth Optical Networks," Proc. of OFCNFOEC, no. JTh2A.35, 2012.

[0015] [6] X. Wang, Q. Zhang, I. Kim, P. Palacharla, and M. Sekiya, "Utilization Entropy for Assessing Resource Fragmentation in Optical Networks," Proc. of OFCNFOEC, no. OThlA.2, 2012.

BRIEF SUMMARY OF THE INVENTION

[0016] An objective of the present invention is to measure fragmentation in a network to evaluate and design methods to efficiently provision spectral resources.

[0017] An aspect of the present invention includes a method implemented in a network apparatus used in a wavelength division multiplexing (WDM) optical network. The method includes (a) finding AT-shortest routes between each node pair (s, d), where s, d& Y and |V| < K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes, (b) selecting unconsidered node pair (s, d), (c) selecting unconsidered route k between nodes s and d out of the Α -shortest routes, (d) finding a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k, (e) selecting unconsidered line rate / out of offered set L of line rates, and (f) finding a probability af^,d,k of provisioning a connection with line rate /.

[0018] Another aspect of the present invention includes a network apparatus used in a wavelength division multiplexing (WDM) optical network. The network apparatus includes (a) a first finding means for finding Α -shortest routes between each node pair (s, d), where s, i e V and | V| < K, where V is a set of reconfigurable optical add-drop multiplexer

(ROADM) nodes, (b) a first selection means for selecting unconsidered node pair (s, d), (c) a second selection means for selecting unconsidered route k between nodes s and d out of the Α -shortest routes, (d) a second finding means for finding a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k, (e) a third selection means for selecting unconsidered line rate / out of offered set L of line rates, and (f) a third finding means for finding a probability af'^d'^k of provisioning a connection with line rate /.

[0019] Still another aspect of the present invention includes a wavelength division multiplexing (WDM) optical network. The WDM optical network includes a network apparatus, wherein the network apparatus (a) finds AT-shortest routes between each node pair (s, d), where s, d e V and |V| < K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes, (b) selects unconsidered node pair (s, d), (c) selects unconsidered route k between nodes s and d out of the AT-shortest routes, (d) finds a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k, (e) selects unconsidered line rate / out of offered set L of line rates, and (f) finds a probability af^,d,k of provisioning a connection with line rate /.

[0020] Means herein can comprise one or more of various kinds of components such as, for example, software, a computer program, an electronic device, a computer, and/or a dedicated controller. BBRRIIEEFF DDEESSCCRRIIPPTTIIOONN OOFF TTHHEE DDRRAAWWIINNGGSS

[[00002211]] FFiigg.. 11((aa)) ddeeppiiccttss cchhaannnneell ssppaacciinngg ooff aa ffiixxeedd ggrriidd WWDDMM nneettwwoorrkk..

[[00002222]] FFiigg.. 11 ((bb)) ddeeppiiccttss cchhaannnneell ssppaacciinngg ooff aa fflleexxiibbllee WWDDMM nneettwwoorrkk..

[[00002233]] FFiigg.. 22 ddeeppiiccttss ffrraaggmmeennttaattiioonn iinn tthhee ssppeeccttrruumm ooff aa ffiibbeerr..

[[00002244]] FFiigg.. 33 ddeeppiiccttss ssppeeccttrraall iissllaannddss aanndd wwaavveelleenngghhtt sslloottss iinn tthhee ffrraaggmmeenntteedd ssppeeccttrruumm.. [[00002255]] FFiigg.. 44 ddeeppiiccttss aa fflloowwcchhaarrtt ooff tthhee pprroocceedduurree ttoo mmeeaassuurree nneettwwoorrkk ffrraaggmmeennttaattiioonn..

DDEETTAAIILLEEDD DDEESSCCRRIIPPTTIIOONN

[[00002266]] WWhheenn ccoonnnneeccttiioonnss aarree rroouutteedd wwiitthh tthhee wwaavveelleennggtthh aanndd ssppeeccttrraall ccoonnttiinnuuiittyy ccoonnssttrraaiinnttss oovveerr mmuullttiippllee ffiibbeerrss,, tthhee aavvaaiillaabbllee aanndd ooccccuuppiieedd ssppeeccttrruumm iinn tthhee ffiibbeerrss aarree ccoorrrreellaatteedd.. TThhee ssttaatteess ooff ffiibbeerrss aarree ccoorrrreellaatteedd.. WWee ddeessiiggnn aa nnoovveell pprroocceedduurree tthhaatt ttaakkeess iinnttoo aaccccoouunntt tthhee ccoorrrreellaattiioonnss ooff ffiibbeerr ssttaatteess ttoo mmeeaassuurree nneettwwoorrkk ffrraaggmmeennttaattiioonn..

[[00002277]] TToo rreedduuccee tthhee mmaannaaggeemmeenntt ccoommpplleexxiittyy,, tthhee ssppeeccttrruumm iiss ssllootttteedd aatt tthhee ggrraannuullaarriittyy ooff TT GGHHzz.. AA sslloott iiss rreeffeerrrreedd ttoo aass aa wwaavveelleennggtthh sslloott aass sshhoowwnn iinn FFiigg.. 33.. TThhuuss,, ssppeeccttrruumm ccaann bbee rreepprreesseenntteedd bbyy aa sseett ooff ccoonnsseeccuuttiivvee wwaavveelleennggtthh sslloottss,, aanndd aammoonngg tthheemm,, tthhee ffiirrsstt wwaavveelleennggtthh sslloott iinnddeexx iiss ddeennootteedd aass wwaavveelleennggtthh.. TThhuuss,, tthhee nneettwwoorrkk ccoonnssiissttss ooff ttoottaall FF ==

wavelength slots. The state of each wavelength slot is represented by a binary variable; ' 1 ' indicated that the wavelength slot is available and '0' indicates that the wavelength slot is occupied. The spectrum state of a fiber is represented by a binary vector.

[0028] The procedure first finds up to AT-shortest routes between each pair of nodes, where

|K| < K . Next, the procedure finds binary spectrum state along each route k between each pair of nodes (s, d), which is referred to as bit-map of a route. The bit-map of a route is found by performing bit- wise logical-AND operations on the bit vectors of all fibers along the route. Based on the available spectrum island (defined as a set of consecutive available wavelength slots) and the required spectrum for each line rate, the procedure finds the probability of provisioning a connection with a line rate / on a route k between an (s, d) node pair, a\^,d,k . Finally, using this probability of provisioning a connection with a line rate / on a route k between an (s, d) node pair, a^{s d,k} , and the probability of requesting a line rate /, Qi, the procedure determines the fragmentation factor FF of the network.

[0029] The detail procedure is described in terms of the flow chart as shown in Fig. 4 as follows:

[0030] In Step 101, the procedure finds AT-shortest routes between each pair of nodes (s, d), where s, d G V and | V\<K.

[0031] In Step 102, the procedure selects a pair of nodes (s, d) that is not yet considered.

[0032] In Step 103, among the Α -shortest routes between the selected pair of nodes, the procedure selects a route k that is not yet considered.

[0033] In Step 104, the procedure finds the bit-map of the selected route k y performing bit-wise logical-AND operations on the bit vectors of fibers along the selected route.

[0034] In Step 105, the procedure selects a line rate / that is not yet considered among the offered set of line rates L.

[0035] In Step 106, the procedure finds the probability of provisioning a connection with line rate / on a route k between a (s, d) node pair, a\ ^,k .

[0036] In Step 107, the procedure checks whether all line rates are considered. If all line rates are already considered, then the procedure follows Step 108, otherwise the procedure repeats Step 105.

[0037] In Step 108, the procedure checks whether all Α-shortest routes between the (s, d) pair are taken into account. If at least one of the routes is not yet considered, then the procedure repeats Step 103, otherwise the procedure follows Step 109.

[0038] In Step 109, the procedure checks whether all possible (s, d) pairs of the network are taken into account. If at least one (s, d) pair is not yet considered, then the procedure repeats Step 102, otherwise the procedure follows Step 110.

[0039] In Step 110, the procedure determines the fragmentation factor of the network using the probability of provisioning a connection for each possible line rates on each of the Ά-shortest routes between each node pairs and the probability of requesting a line rate /, and finally the procedure is terminated. The fragmentation factor is determined as follows:

[0041] (1) The procedure accurately measures fragmentation in a network compared to the existing approaches.

[0042] (2) The procedure is used to evaluate and design methods to efficiently provision spectral resources.

[0043] (3) The procedure is applicable in the optical control plane, such as Path Computation Element (PCE), OpenFlow controller, and distributed controllers at nodes.

[0044] (4) The procedure is applicable to timely make decisions on network defragmentation.

[0045] (5) The application of this procedure can enhance network performance in terms of higher spectral efficiency and lower connection blocking.

[0046] The methods disclosed herein can be implemented in a network apparatus.

[0047] The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.

Claims

What is claimed is:

1. A method implemented in a network apparatus used in a wavelength division multiplexing (WDM) optical network, the method comprising:

(a) finding Α -shortest routes between each node pair (s, d), where s, d& Y and | V| < K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes;

(b) selecting unconsidered node pair (s, d);

(c) selecting unconsidered route k between nodes s and d out of the AT-shortest routes;

(d) finding a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k;

(e) selecting unconsidered line rate / out of offered set L of line rates; and

(f) finding a probability af'^d'^k of provisioning a connection with line rate /.

2. The method as in claim 1 , further comprising:

(g) iterating steps (e) and (f) until all line rates in offered set L are considered.

The method as in claim 2, further comprising:

(h) iterating steps (c) to (g) until all of the AT-shortest routes between node pair (s, d)

4. The method as in claim 3, further comprising:

(i) iterating steps (b) to (h) until all node pairs are considered.

5. The method as in claim 4, further comprising:

(j) determining fragmentation factor (FF) according to the following formula:

where T is granularity at which a spectrum is slotted.

6. A network apparatus used in a wavelength division multiplexing (WDM) optical network, the network apparatus comprising:

(a) a first finding means for finding Α -shortest routes between each node pair (s, d), where s, d& Y and | V| < K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes;

(b) a first selection means for selecting unconsidered node pair (s, d);

(c) a second selection means for selecting unconsidered route k between nodes s and d out of the Α -shortest routes;

(d) a second finding means for finding a bit map of route k by performing bit-wise logical AND operation on bit vectors of fibers along route k;

(e) a third selection means for selecting unconsidered line rate / out of offered set L of line rates; and

(f) a third finding means for finding a probability af'^d'^k of provisioning a connection with line rate /.

7. The network apparatus as in claim 6, further comprising:

(g) a first iteration means for iterating steps (e) and (f) until all line rates in offered set L are considered.

8. The network apparatus as in claim 7, further comprising:

(h) a second iteration means for iterating steps (c) to (g) until all of the AT-shortest routes between node pair (s, d) are considered.

9. The network apparatus as in claim 8, further comprising:

(i) a third iteration means for iterating steps (b) to (h) until all node pairs are considered.

10. The network apparatus as in claim 9, further comprising: (j) a determination means for determining fragmentation factor (FF) according to the following formula:

where T is granularity at which a spectrum is slotted.

1 1. A wavelength division multiplexing (WDM) optical network comprising:

a network apparatus,

wherein the network apparatus

(a) finds Α -shortest routes between each node pair (s, d), where s, d& Y and |V| < K, where V is a set of reconfigurable optical add-drop multiplexer (ROADM) nodes,

(b) selects unconsidered node pair (s, d),

(c) selects unconsidered route k between nodes s and d out of the Α -shortest routes,

(d) finds a bit map of route k by performing bit- wise logical AND operation on bit vectors of fibers along route k,

(e) selects unconsidered line rate / out of offered set L of line rates, and

(f) finds a probability af^,d,k of provisioning a connection with line rate /.

The WDM optical network as in claim 1 1 , wherein the network apparatus

(g) iterates steps (e) and (f) until all line rates in offered set L are considered.

The WDM optical network as in claim 12, wherein the network apparatus

(h) iterates steps (c) to (g) until all of the AT-shortest routes between node pair (s, d)

14. The WDM optical network as in claim 13, wherein the network apparatus

(i) iterates steps (b) to (h) until all node pairs are considered.

15. The WDM optical network as in claim 14, wherein the network apparatus (j) determines fragmentation factor (FF) according to the following formula:

granularity at which a spectrum is slotted.