Table 1
Algorithm 1 Sequential path computation for LD i with starting time t.
Require: LD i to be set up, K,
${R}_{i}$
, W

1: return computes a physical route and selects a pathfree wavelength for the incoming LD 
2: for each newly arrived LD i at time t
do

3: for
$k=1$
to K
do

4: for
$\omega =1$
to W
do

5: Compute
${\gamma}_{i,k}^{\omega ,t}$

6: end for

7: end for

8: if
${\sum}_{k=1}^{K}{\sigma}_{i,k}^{t}\u2a7e{\pi}_{i}$
then

9: (
${\text{\hspace{0.17em}}}^{*}$
Set up the LD.
${\text{\hspace{0.17em}}}^{*}$
) 
10:
$k\Leftarrow 11$

11:
$p\Leftarrow 1$

12: while
$(k\u2a7dK)$
and
$(p\u2a7d{\pi}_{i})$
do

13:
$\omega \Leftarrow 1$

14: while
$(\omega \u2a7dW)$
and
$(p\u2a7d{\pi}_{i})$
do

15: if
${C}_{i,k}^{\omega ,t}\u2a7d+\infty $
then

16:
${C}_{i,k}^{\omega ,t}\Leftarrow +\infty $

17: Update to
$+\infty $
the cost on wavelength
${\lambda}_{\omega}$
of all paths in
${B}_{i,k}$
that share at least one common fiber link with
${P}_{i,k}$
. 
18:
$p\Leftarrow p+1$

19: end if

20:
$\omega \Leftarrow \omega +1$

21: end while

22: end while

23: else

24: (
${\text{\hspace{0.17em}}}^{*}$
The LD cannot be set up. The LD is rejected in the
absence of any rerouting scheme.
${\text{\hspace{0.17em}}}^{*}$
) 
25: end if

26: end for

Table 2
Algorithm 2 The rerouting algorithm used for PHASE 2.
Require: LD i, K,
${R}_{i}$
, W

1: return reroutes a minimum number of RLDs to free a pathfree wavelength for a new arriving LD 
(
${\text{\hspace{0.17em}}}^{*}$
The algorithm tries to free one pathfree wavelength on one
of the considered
K
alternate shortest paths after rerouting a
minimum number of alreadyrouted RLDs.
${\text{\hspace{0.17em}}}^{*}$
) 
2:
$k\u22541$

3: while
$(k\u2a7dK)$
and
$(\text{FLAG}=0)$
do

4: for
$\omega =1$
to W
do

5: compute
${\mathcal{Q}}_{i,k}^{\omega ,t}$

6: discard a wavelength if a SLD is to be added to
${\mathcal{Q}}_{i,k}^{\omega ,t}$

7: compute
${\mathcal{O}}_{i,k}^{\omega ,t}$

8: end for

9: compute
${\mathcal{O}}_{i,k}^{t,\mathrm{min}}$
, the minimum number of RLDs to reroute to accommodate the LD on
${P}_{i,k}$
using wavelength
${\lambda}_{\omega}$

10: while
$({\mathcal{O}}_{i,k}^{t,\mathrm{min}}\u2a7d+\infty )$
do

11:
$\text{FLAG}\Leftarrow 0$

12:
$p\Leftarrow 1$

13: while
$(\text{FLAG}=0)$
do

14: reroute all the RLDs in
${\mathcal{Q}}_{i,k}^{\omega ,t}$
. 
15: if one RLD in
${\mathcal{Q}}_{i,k}^{\omega ,t}$
cannot be rerouted, then

16:
$\text{FLAG}\Leftarrow 1$

17: end if

18: end while

19: if
$\text{FLAG}=0$
then

20: (
${\text{\hspace{0.17em}}}^{*}$
all the RLDs in
${\mathcal{Q}}_{i,k}^{\omega ,t}$
are rerouted. The newly arriving
LD
i
is to be set up on
${P}_{i,k}$
using
${\lambda}_{\omega}$
${\text{\hspace{0.17em}}}^{*}$
) 
21: free the wavelengths used by the RLDs to be rerouted. 
22: instantiate the lightpath required by LD i. 
23: update the cost of path
${P}_{i,k}$
on wavelength
${\lambda}_{\omega}$
to
$+\infty $
. 
24: update the cost of all the paths that share a common link with
${P}_{i,k}$
on
${\lambda}_{\omega}$
to
$+\infty $
. 
25: update the cost of the new lightpaths used by the rerouted RLDs to
$+\infty $
. 
26: update the cost of the paths that share common links with the new paths of the rerouted RLDs on the used wavelengths. 
27: else

28: (
${\text{\hspace{0.17em}}}^{*}$
LD
i
cannot be set up on
${P}_{i,k}$
on
${\lambda}_{\omega}$
. Update
${\mathcal{Q}}_{i,k}^{\omega ,t}$
to
$+\infty $
and then compute again
${\mathcal{O}}_{i,k}^{t,\mathrm{min}}$
still considering the
K
alternate shortest paths in
${R}_{i}$
.
${\text{\hspace{0.17em}}}^{*}$
) 
29:
${\mathcal{Q}}_{i,k}^{\omega ,t}\Leftarrow +\infty $
. 
30: compute
${\mathcal{O}}_{i,k}^{t,\mathrm{min}}$
. 
31: end if

32: end while

33:
$k\Leftarrow k+1$

34: end while

Table 1
Example of Three Scheduled Lightpath Demands (SLDs)
Number 
s

d

π

α

β


${\delta}_{1}$
 2  8  2  08:00  14:40 
${\delta}_{2}$
 3  7  3  11:00  13:00 
${\delta}_{3}$
 5  6  2  17:00  19:30 
Table 2
Set of Established LDs
Number 
s

d
 Path  Wavelength 

1  2  8  23478 
${\lambda}_{1}$

2  3  7  347 
${\lambda}_{2}$

3  1  6  156 
${\lambda}_{2}$

4  6  9  689 
${\lambda}_{1}$

5  8  7  897 
${\lambda}_{2}$

Table 3
Comparison of the Rerouting Algorithms
 RRA1 [20]  RRA2 [22]  New Algorithm 

Traffic model  RLDs  RLDs 
$\mathrm{PLDs}+\mathrm{SLDs}+\mathrm{RLDs}$

Auxiliary graphs  yes  yes  no 
Lightpath retunability information  checked online  updated  updated 
Type of lightpaths  bidirectional  bidirectional  unidirectional 
Complexity 
$O({N}^{3}W+{N}^{2}{W}^{2})$

$O\left({N}^{2}W\right)$

$O\left(KW\right)$

Wavelength rerouting  yes  yes  yes 
Lightpath rerouting  no  no  yes 
Table 4
Average Rejection Ratio (
$N=14$
,
$W=32$
,
$K=5$
,
${\mu}^{1}=500$
,
${\nu}^{1}=1$
,
$\pi =1$
)
D
 1219  1282  1375  1393  1495  1578  1626  1744  1864  1933 

seqRWA
$\left({\mathit{10}}^{\mathit{3}}\right)$
 12.566  21.869  39.771  43.626  68.477  88.949  98.667  124.106  152.918  164.691 
sepRWA
$\left({\mathit{10}}^{\mathit{3}}\right)$
 11.877  21.464  39.131  45.950  73.987  96.576  105.503  138.349  174.270  186.500 
seqRWAwR
$\left({\mathit{10}}^{\mathit{3}}\right)$

0.755

3.588

11.259

14.465

35.308

57.322

63.975

90.482

122.468

135.680

sepRWAwR
$\left({\mathit{10}}^{\mathit{3}}\right)$
 1.115  3.900  12.597  16.589  41.380  64.317  72.581  104.748  150.494  164.132 
Table 5
Average Number of Rejected SLDs (
$N=14$
,
$W=32$
,
$K=5$
,
${\mu}^{1}=500$
,
${\nu}^{1}=1$
,
$\pi =1$
)
D
 1219  1282  1375  1393  1495  1578  1626  1744  1864  1933 

seqRWA
 3  6  15  17  32  48  61  86  130  145 
sepRWA
 0  0  0  0  0  0  0  0  0  1 
seqRWAwR
 0  1  4  5  15  29  37  61  100  114 
sepRWAwR

0

0

0

0

0

0

0

0

0

1

Table 6
Average Number of Rejected RLDs (
$N=14$
,
$W=32$
,
$K=5$
,
${\mu}^{1}=500$
,
${\nu}^{1}=1$
,
$\pi =1$
)
D
 1219  1282  1375  1393  1495  1578  1626  1744  1864  1933 

seqRWA
 12  22  40  44  70  92  100  131  155  173 
sepRWA
 14  28  54  64  111  152  172  241  325  359 
seqRWAwR

1

4

11

15

37

61

68

97

128

148

sepRWAwR
 1  5  17  23  62  102  118  183  280  316 