Sheng Huang,^{1}
Ming Xia,^{2}
Chip Martel,^{2}
and Biswanath Mukherjee^{2}

^{1}S. Huang (e-mail: sheng.huang@intel.com) is a component design engineer at Intel, Folsom, California 95630, USA.

^{2}M. Xia (e-mail: xia@cs.ucdavis.edu), C. Martel (e-mail: martel@cs.ucdavis.edu), and B. Mukherjee (e-mail: mukherje@cs.ucdavis.edu) are with the Department of Computer Science, University of California at Davis, Davis, California 95616, USA.

We investigate the survivable traffic grooming problem with inverse multiplexing in telecommunication mesh networks employing next-generation SONET/SDH and WDM. With the support of virtual concatenation, a connection of any bandwidth can be provisioned as several subconnections (i.e., inverse multiplexed) over diverse paths. Therefore, it is important to efficiently groom and protect these low-speed subconnections onto high-capacity wavelength channels, considering the typical constraints. We propose and investigate the characteristics of survivable multipath traffic grooming with protection-at-connection and protection-at-lightpath levels for grooming connections with shared pro- tection, subject to the constraints of the inverse-multiplexing factor, differential-delay constraint, and grooming ports. Since this problem is $\mathcal{N}\mathcal{P}$-complete, we propose effective heuristics using a novel analytical model. Our results show that (1) the network performance, in metrics of bandwidth blocking ratio and resource overbuild, can be notably improved by exploiting the inverse-multiplexing capability, (2) tight constraints have negative impact on performance, (3) protection-at-connection performs better in most cases of multipath provisioning when the constraints are not too tight, and (4) protection-at-lightpath achieves better performance when the number of grooming ports is moderate or small.

Chengyi Gao, Hakki C. Cankaya, Ankitkumar N. Patel, Jason P. Jue, Xi Wang, Qiong Zhang, Paparao Palacharla, and Motoyoshi Sekiya J. Opt. Commun. Netw. 4(3) 259-270 (2012)

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Input: Network: $G=(V,E,D,W,P,g,\mathrm{DDC},\mathrm{IMF})$; current network state; a request $R=\u27e8s,d,B,{t}_{h}\u27e9$.

Output: Route each request with respect to DDC, IMF, P and protect it for single link failure while minimizing the cost.

1: If R is the first request, set up a connection list to include all connections and a lightpath list to record connections and lightpaths as they are routed. One connection consists of one f-lightpath, which includes a set of working paths ${\mathcal{P}}_{w}$ and one backup path ${P}_{b}$.

2: Back up current network state (including the current connection and lightpath list, wavelength and grooming port usage, and the conflict set of backups).

3: Search for an existing connection from the same s–d pair with enough free capacity for B. Note that the existing connection must be set up with the same IMF and DDC constraints. If an existing connection cannot be found, go to Step 4 to set up new f-lightpath; otherwise, reuse the f-lightpath of the existing connection and go to Step 9.

4: Calculate the differential-delay-constrained K link- disjoint paths using the DDCKDP algorithm [27] and calculate all paths that meet the DDC by using cost functions thatconsider whether we can set up new lightpaths from the d pair. If two link-disjoint paths are not found above, calculate the two shortest link-disjoint paths by setting DDC as a large value (e.g., $50\text{\hspace{0.17em}}\mathrm{ms}$), since for two disjoint paths, there is only one working path, so no need to consider DDC.

The DDCKDP algorithm is based on the K shortest link-disjoint paths algorithm. After finding all link-disjoint paths, we recombine the subpaths between all merge nodes (common nodes on two or more paths except source and destination nodes) to search for the largest number set of link-disjoint paths that are subject to DDC between any two paths. K is the largest number of link-disjoint paths we can find between the s–d pair. We use two cost functions to differentiate the situations in which we may or may not be able to set a new lightpath between the s–d pair. The costs are set as the same value in different conditions in the two cases.

a) No new lightpath can be set between s–d pair (no free transmit port at s, or no free receive port at d).

b) A new lightpath can be set between an s–d pair ($\mathrm{g}\text{\_}\mathrm{txp}\left(\mathrm{s}\right)>0$ and $\mathrm{g}\text{\_}\mathrm{rxp}\left(\mathrm{d}\right)>0$).

5: If we cannot find at least two disjoint paths, go to Step 10 to block the request.

6: After finding K$(K\u2a7e2)$ candidate disjoint paths set $\mathcal{P}$, set up a new f-lightpath subject to constraint $\mathrm{IMF}$. Search ${\mathcal{L}}_{\mathcal{P}}$ for a working lightpath traversing each path in $\mathcal{P}$, or set up a new one-hop lightpath if there are available resources (free wavelength, transceivers) as a working lightpath until $\mathrm{min}(K-1,\mathrm{IMF})$ paths are reached, referred to ${\mathcal{P}}_{w}$, and set up backup lightpaths link-by-link covering the backup path ${P}_{b}$. Note that the backup lightpath of a f-lightpath does not reserve transmit/receive grooming ports at source/destination nodes.

7: If the backup lightpaths cannot be set over ${P}_{b}$, select one path from ${\mathcal{P}}_{w}$ as backup path, undo working lightpath setup, and set up backup lightpaths over each link of the backup path.

8: Split request R (of bandwidth B) to each path of the f-lightpath; assign working and backup capacity, considering backup sharing between different f-lightpaths.

a) Evenly split request R on working lightpaths based on their free capacity. Assign the backup path the maximum capacity of all working lightpaths.

b) Use the conflict set model for backup sharing [4]. Every link is associated with a conflict set, where ${\nu}_{e}^{{e}^{\prime}}$ is the amount of traffic that will be rerouted on link e when link ${e}^{\prime}$ fails. The amount of backup sharing on link e is thus ${\mathrm{max}}_{\forall {e}^{\prime}\u220aE}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}-{\mathrm{max}}_{\forall {e}^{\prime}\u220a{E}_{P}}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}$, where ${E}_{P}$ is the set of links on working lightpaths of the current f-lightpath.

9: Reserve working and backup capacity on each lightpath of the f-lightpath. If success, goto Step 11; if fail, continue.

10: Block request R, and restore network state saved in Step 2.

11: Accept the request by adding the f-lightpath to the connection, append the newly set up connection to the connection list, and update network state accordingly.

Input: Network: $G=(V,E,D,W,P,g,\mathrm{DDC},\mathrm{IMF})$; current network state; a request $R=\u27e8s,d,B,{t}_{h}\u27e9$.

Output: Route each request with respect to $\mathrm{DDC}$, $\mathrm{IMF}$, P, and protect it for single link failure while minimizing the cost.

1: If R is the first request, set up a lightpath list to record all lightpaths. The total number of lightpaths is bounded by the product of the total number of unidirectional links and total number of wavelengths on each link.

2: Back up current network state including wavelength, grooming ports, conflict set of backups, and lightpath list.

3: Calculate a set of link-disjoint paths between source and destination nodes, subject to $\mathrm{DDC}$.

a) Calculate differential-delay-constrained K disjoint paths using the DDCKDP algorithm [27]. Set link-cost function as

b) If no link-disjoint path can be found above, calculate the two shortest link-disjoint paths, since for two disjoint paths, there is only one working path, so no need to consider DDC.

4: After finding K$(K\u2a7e2)$ link-disjoint path set $\mathcal{P}$, set up an f-lightpath for the connection subject to $\mathrm{IMF}$, select $\mathrm{min}\{K-1,\mathrm{IMF}\}$ working paths and one backup path. Search or set up a new lightpath to cover the paths following the minimum-traffic-hop grooming policy.

a) For each path, search ${\mathcal{L}}_{\mathcal{P}}$ first to find a sequence of lightpaths (with enough free capacity) to cover the path following the minimum-traffic-hop grooming policy. A long lightpath can be split as two or three lightpaths if it is necessary to add traffic at intermediate nodes, with reserving additional grooming ports. If no lightpath is found for the path or subpath, set up a new lightpath using the above strategies if there are available resources (free wavelength, transceivers).

b) Add the sequence of lightpaths traversed over the path to the f-lightpath.

c) Repeat Steps 4a) and 4b) for the next disjoint path, until $\mathrm{min}(K-1,\mathrm{IMF})$ paths are processed or no more path in $\mathcal{P}$ can be processed. The set of processed working paths is referred to as ${\mathcal{P}}_{w}$.

d) Set up lightpaths for one backup path from $\mathcal{P}-{\mathcal{P}}_{w}$ following the same grooming policy.

e) If we fail to set up lightpaths for one backup path, convert one path in ${\mathcal{P}}_{w}$ to the backup path.

5: Split request R (of bandwidth B) to each path of the f-lightpath; assign working and backup capacity, considering backup sharing between different f-lightpaths.

a) Evenly split request R on working paths (select the longest one as backup path) based on the free capacity of the paths of the f-lightpath. Assign the backup path the maximum capacity of all working paths.

b) Use the conflict set model for backup sharing [4]. Every link is associated with a conflict set, where ${\nu}_{e}^{{e}^{\prime}}$ is the amount of traffic that will be rerouted on link e when link ${e}^{\prime}$ fails. The amount of backup sharing on link e is thus ${\mathrm{max}}_{\forall {e}^{\prime}\u220aE}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}-{\mathrm{max}}_{\forall {e}^{\prime}\u220a{E}_{P}}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}$, where ${E}_{P}$ is the set of links on primary paths of the current f-lightpath.

6: Reserve working and backup capacity on each path of the f-lightpath. If success, go to Step 8; if failed, continue.

7: Block request R if the algorithm is unable to find such disjoint paths, and restore to the network state saved in Step 2.

8: Accept the request by adding the f-lightpath to the connection, append the newly set-up lightpath to the lightpath list, and update the network state accordingly.

Input: Network: $G=(V,E,D,W,P,g,\mathrm{DDC},\mathrm{IMF})$; current network state; a request $R=\u27e8s,d,B,{t}_{h}\u27e9$.

Output: Route each request with respect to DDC, IMF, P and protect it for single link failure while minimizing the cost.

1: If R is the first request, set up a connection list to include all connections and a lightpath list to record connections and lightpaths as they are routed. One connection consists of one f-lightpath, which includes a set of working paths ${\mathcal{P}}_{w}$ and one backup path ${P}_{b}$.

2: Back up current network state (including the current connection and lightpath list, wavelength and grooming port usage, and the conflict set of backups).

3: Search for an existing connection from the same s–d pair with enough free capacity for B. Note that the existing connection must be set up with the same IMF and DDC constraints. If an existing connection cannot be found, go to Step 4 to set up new f-lightpath; otherwise, reuse the f-lightpath of the existing connection and go to Step 9.

4: Calculate the differential-delay-constrained K link- disjoint paths using the DDCKDP algorithm [27] and calculate all paths that meet the DDC by using cost functions thatconsider whether we can set up new lightpaths from the d pair. If two link-disjoint paths are not found above, calculate the two shortest link-disjoint paths by setting DDC as a large value (e.g., $50\text{\hspace{0.17em}}\mathrm{ms}$), since for two disjoint paths, there is only one working path, so no need to consider DDC.

The DDCKDP algorithm is based on the K shortest link-disjoint paths algorithm. After finding all link-disjoint paths, we recombine the subpaths between all merge nodes (common nodes on two or more paths except source and destination nodes) to search for the largest number set of link-disjoint paths that are subject to DDC between any two paths. K is the largest number of link-disjoint paths we can find between the s–d pair. We use two cost functions to differentiate the situations in which we may or may not be able to set a new lightpath between the s–d pair. The costs are set as the same value in different conditions in the two cases.

a) No new lightpath can be set between s–d pair (no free transmit port at s, or no free receive port at d).

b) A new lightpath can be set between an s–d pair ($\mathrm{g}\text{\_}\mathrm{txp}\left(\mathrm{s}\right)>0$ and $\mathrm{g}\text{\_}\mathrm{rxp}\left(\mathrm{d}\right)>0$).

5: If we cannot find at least two disjoint paths, go to Step 10 to block the request.

6: After finding K$(K\u2a7e2)$ candidate disjoint paths set $\mathcal{P}$, set up a new f-lightpath subject to constraint $\mathrm{IMF}$. Search ${\mathcal{L}}_{\mathcal{P}}$ for a working lightpath traversing each path in $\mathcal{P}$, or set up a new one-hop lightpath if there are available resources (free wavelength, transceivers) as a working lightpath until $\mathrm{min}(K-1,\mathrm{IMF})$ paths are reached, referred to ${\mathcal{P}}_{w}$, and set up backup lightpaths link-by-link covering the backup path ${P}_{b}$. Note that the backup lightpath of a f-lightpath does not reserve transmit/receive grooming ports at source/destination nodes.

7: If the backup lightpaths cannot be set over ${P}_{b}$, select one path from ${\mathcal{P}}_{w}$ as backup path, undo working lightpath setup, and set up backup lightpaths over each link of the backup path.

8: Split request R (of bandwidth B) to each path of the f-lightpath; assign working and backup capacity, considering backup sharing between different f-lightpaths.

a) Evenly split request R on working lightpaths based on their free capacity. Assign the backup path the maximum capacity of all working lightpaths.

b) Use the conflict set model for backup sharing [4]. Every link is associated with a conflict set, where ${\nu}_{e}^{{e}^{\prime}}$ is the amount of traffic that will be rerouted on link e when link ${e}^{\prime}$ fails. The amount of backup sharing on link e is thus ${\mathrm{max}}_{\forall {e}^{\prime}\u220aE}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}-{\mathrm{max}}_{\forall {e}^{\prime}\u220a{E}_{P}}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}$, where ${E}_{P}$ is the set of links on working lightpaths of the current f-lightpath.

9: Reserve working and backup capacity on each lightpath of the f-lightpath. If success, goto Step 11; if fail, continue.

10: Block request R, and restore network state saved in Step 2.

11: Accept the request by adding the f-lightpath to the connection, append the newly set up connection to the connection list, and update network state accordingly.

Input: Network: $G=(V,E,D,W,P,g,\mathrm{DDC},\mathrm{IMF})$; current network state; a request $R=\u27e8s,d,B,{t}_{h}\u27e9$.

Output: Route each request with respect to $\mathrm{DDC}$, $\mathrm{IMF}$, P, and protect it for single link failure while minimizing the cost.

1: If R is the first request, set up a lightpath list to record all lightpaths. The total number of lightpaths is bounded by the product of the total number of unidirectional links and total number of wavelengths on each link.

2: Back up current network state including wavelength, grooming ports, conflict set of backups, and lightpath list.

3: Calculate a set of link-disjoint paths between source and destination nodes, subject to $\mathrm{DDC}$.

a) Calculate differential-delay-constrained K disjoint paths using the DDCKDP algorithm [27]. Set link-cost function as

b) If no link-disjoint path can be found above, calculate the two shortest link-disjoint paths, since for two disjoint paths, there is only one working path, so no need to consider DDC.

4: After finding K$(K\u2a7e2)$ link-disjoint path set $\mathcal{P}$, set up an f-lightpath for the connection subject to $\mathrm{IMF}$, select $\mathrm{min}\{K-1,\mathrm{IMF}\}$ working paths and one backup path. Search or set up a new lightpath to cover the paths following the minimum-traffic-hop grooming policy.

a) For each path, search ${\mathcal{L}}_{\mathcal{P}}$ first to find a sequence of lightpaths (with enough free capacity) to cover the path following the minimum-traffic-hop grooming policy. A long lightpath can be split as two or three lightpaths if it is necessary to add traffic at intermediate nodes, with reserving additional grooming ports. If no lightpath is found for the path or subpath, set up a new lightpath using the above strategies if there are available resources (free wavelength, transceivers).

b) Add the sequence of lightpaths traversed over the path to the f-lightpath.

c) Repeat Steps 4a) and 4b) for the next disjoint path, until $\mathrm{min}(K-1,\mathrm{IMF})$ paths are processed or no more path in $\mathcal{P}$ can be processed. The set of processed working paths is referred to as ${\mathcal{P}}_{w}$.

d) Set up lightpaths for one backup path from $\mathcal{P}-{\mathcal{P}}_{w}$ following the same grooming policy.

e) If we fail to set up lightpaths for one backup path, convert one path in ${\mathcal{P}}_{w}$ to the backup path.

5: Split request R (of bandwidth B) to each path of the f-lightpath; assign working and backup capacity, considering backup sharing between different f-lightpaths.

a) Evenly split request R on working paths (select the longest one as backup path) based on the free capacity of the paths of the f-lightpath. Assign the backup path the maximum capacity of all working paths.

b) Use the conflict set model for backup sharing [4]. Every link is associated with a conflict set, where ${\nu}_{e}^{{e}^{\prime}}$ is the amount of traffic that will be rerouted on link e when link ${e}^{\prime}$ fails. The amount of backup sharing on link e is thus ${\mathrm{max}}_{\forall {e}^{\prime}\u220aE}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}-{\mathrm{max}}_{\forall {e}^{\prime}\u220a{E}_{P}}\left\{{\nu}_{e}^{{e}^{\prime}}\right\}$, where ${E}_{P}$ is the set of links on primary paths of the current f-lightpath.

6: Reserve working and backup capacity on each path of the f-lightpath. If success, go to Step 8; if failed, continue.

7: Block request R if the algorithm is unable to find such disjoint paths, and restore to the network state saved in Step 2.

8: Accept the request by adding the f-lightpath to the connection, append the newly set-up lightpath to the lightpath list, and update the network state accordingly.