Abstract

This paper presents different methods to solve the network reconfiguration problem in wavelength-switching optical networks. The network reconfiguration problem consists of finding a sequence of operations that can be used to migrate traffic from one lightpath configuration to another. Operations correspond to establishing or tearing down a given lightpath. The methods presented exploit for the first time (to our knowledge) the structure of the underlying combinatorial problems in order to divide the reconfiguration process into independent stages, decreasing the amount of disrupted traffic. Our numerical results show that our approaches can reduce the number of disruptions up to 10% more than the traditional approach (computing the minimum feedback vertex set of the dependency graph), while releasing 40% of seized resources during the reconfiguration process. The methodology presented can be easily adapted to other circuit-switching technologies, such as flexpaths.

© 2013 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Farrel, J.-P. Vaseur, and J. Ash, “A path computation element (PCE)-based architecture,” , Aug. 2006.
  2. “Architecture for the automatically switched optical network (ASON),” , 2001.
  3. E. Mannie, “Generalized multi-protocol label switching (GMPLS) architecture,” , Oct. 2004.
  4. F. Solano and M. Pioro, “Lightpath reconfiguration in WDM networks,” J. Opt. Commun. Netw., vol.  2, no. 12, pp. 1010–1021, Dec. 2010.
  5. N. Jose and A. Somani, “Connection rerouting/network reconfiguration,” in IEEE Design of Reliable Communication Networks (DRCN), Banff, Canada, Oct. 2003, pp. 23–30.
  6. H.-M. Lin and J.-Y. Jou, “Computing minimum feedback vertex sets by contraction operations and its applications on CAD,” in IEEE Int. Conf. on Computer Design (ICCD), Austin, Texas, Oct. 1999, pp. 364–369.
  7. D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.
  8. R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Comput., vol.  1, no. 2, pp. 146–160, 1972.
    [CrossRef]
  9. M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.
  10. P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.
  11. B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Appl. Math., vol.  117, nos. 1–3, pp. 253–265, Mar. 2002.
    [CrossRef]

2010 (1)

2003 (1)

P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.

2002 (1)

B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Appl. Math., vol.  117, nos. 1–3, pp. 253–265, Mar. 2002.
[CrossRef]

1972 (1)

R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Comput., vol.  1, no. 2, pp. 146–160, 1972.
[CrossRef]

Ash, J.

A. Farrel, J.-P. Vaseur, and J. Ash, “A path computation element (PCE)-based architecture,” , Aug. 2006.

Couder, D.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Farrel, A.

A. Farrel, J.-P. Vaseur, and J. Ash, “A path computation element (PCE)-based architecture,” , Aug. 2006.

Gleiss, P.

P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.

Huc, F.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Jose, N.

N. Jose and A. Somani, “Connection rerouting/network reconfiguration,” in IEEE Design of Reliable Communication Networks (DRCN), Banff, Canada, Oct. 2003, pp. 23–30.

Jou, J.-Y.

H.-M. Lin and J.-Y. Jou, “Computing minimum feedback vertex sets by contraction operations and its applications on CAD,” in IEEE Int. Conf. on Computer Design (ICCD), Austin, Texas, Oct. 1999, pp. 364–369.

Leydold, J.

P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.

Lin, H.-M.

H.-M. Lin and J.-Y. Jou, “Computing minimum feedback vertex sets by contraction operations and its applications on CAD,” in IEEE Int. Conf. on Computer Design (ICCD), Austin, Texas, Oct. 1999, pp. 364–369.

Mannie, E.

E. Mannie, “Generalized multi-protocol label switching (GMPLS) architecture,” , Oct. 2004.

Mazauric, D.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Medhi, D.

M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.

Nisse, N.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Pioro, M.

F. Solano and M. Pioro, “Lightpath reconfiguration in WDM networks,” J. Opt. Commun. Netw., vol.  2, no. 12, pp. 1010–1021, Dec. 2010.

M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.

Schwikowski, B.

B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Appl. Math., vol.  117, nos. 1–3, pp. 253–265, Mar. 2002.
[CrossRef]

Sereni, J.-S.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Solano, F.

Somani, A.

N. Jose and A. Somani, “Connection rerouting/network reconfiguration,” in IEEE Design of Reliable Communication Networks (DRCN), Banff, Canada, Oct. 2003, pp. 23–30.

Speckenmeyer, E.

B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Appl. Math., vol.  117, nos. 1–3, pp. 253–265, Mar. 2002.
[CrossRef]

Stadler, P.

P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.

Tarjan, R. E.

R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Comput., vol.  1, no. 2, pp. 146–160, 1972.
[CrossRef]

Vaseur, J.-P.

A. Farrel, J.-P. Vaseur, and J. Ash, “A path computation element (PCE)-based architecture,” , Aug. 2006.

Discrete Appl. Math. (1)

B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Appl. Math., vol.  117, nos. 1–3, pp. 253–265, Mar. 2002.
[CrossRef]

Discuss. Math. Graph Theory (1)

P. Gleiss, J. Leydold, and P. Stadler, “Circuit bases of strongly connected digraphs,” Discuss. Math. Graph Theory, vol.  23, no. 2, pp. 241–260, 2003.

J. Opt. Commun. Netw. (1)

SIAM J. Comput. (1)

R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Comput., vol.  1, no. 2, pp. 146–160, 1972.
[CrossRef]

Other (7)

M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.

A. Farrel, J.-P. Vaseur, and J. Ash, “A path computation element (PCE)-based architecture,” , Aug. 2006.

“Architecture for the automatically switched optical network (ASON),” , 2001.

E. Mannie, “Generalized multi-protocol label switching (GMPLS) architecture,” , Oct. 2004.

N. Jose and A. Somani, “Connection rerouting/network reconfiguration,” in IEEE Design of Reliable Communication Networks (DRCN), Banff, Canada, Oct. 2003, pp. 23–30.

H.-M. Lin and J.-Y. Jou, “Computing minimum feedback vertex sets by contraction operations and its applications on CAD,” in IEEE Int. Conf. on Computer Design (ICCD), Austin, Texas, Oct. 1999, pp. 364–369.

D. Couder, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in Proc. of the Optical Network Design and Modeling Conf., Braunschweig, Germany, Feb. 2009, pp. 146–151.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1.
Fig. 1.

Example of a reoptimization solution. (a) Working configuration: connection a through 173, connection b through 1346, and connection c through 476. (b) Optimal rerouting: connection a through 13, connection b through 176, and connection c through 46.

Fig. 2.
Fig. 2.

Dependency graph, minimum feedback vertex set (MFVS), and derived transient configuration for the example. (a) Dependency graph and FVS for the working and optimal rerouting configuration. (b) Transient configuration considering the MFVS. Transient lightpath for connection b (MFVS) through 186. The configuration can be appreciated in t=6 of the sequence depicted in Fig. 3.

Fig. 3.
Fig. 3.

Representation of the reconfiguration sequence of the problem shown in Figs. 1(a) and 1(b) considering the transient configuration in Fig. 2(b). The order in time of the sequence is from left to right. In this case, the transient lightpath for connection b is first established, then its working lightpath is disconnected, and so on.

Fig. 4.
Fig. 4.

Transition from the working configuration to the new configuration through the stages, when solving the reconfiguration problem by decomposing it into SCC.

Fig. 5.
Fig. 5.

Non-MFVS transient configuration. Transient lightpath for connection a through 123 and for connection c through 456. The configuration can be obtained in t=4 of the sequence depicted in Fig. 6.

Fig. 6.
Fig. 6.

Representation of the reconfiguration sequence of the routing solution of Fig. 1(b) considering the transient configuration of Fig. 5. The order in time of the sequence is from left to right. In this case, transient lightpaths for connections a and c are first established, then their working lightpaths are disconnected, and so on.

Fig. 7.
Fig. 7.

Percentage of disrupted demands per method as the number of routed demands varies.

Fig. 8.
Fig. 8.

Running time per method as the number of demands varies.

Fig. 9.
Fig. 9.

Spare resources used during the reconfiguration of the network with and without considering SCC problem decomposition.

Fig. 10.
Fig. 10.

Percentage of demands involved in the FVS and percentage of disrupted demands for each method.

Fig. 11.
Fig. 11.

Results considering eight wavelengths per fiber in the WDM network: (a) disruption per method and (b) spare resources by method.

Tables (1)

Tables Icon

TABLE I Evaluated Methods

Equations (23)

Equations on this page are rendered with MathJax. Learn more.

r(Gf(j),Tf(j))Nijr(Gf(i),C)jkr(Gf(k),C),
mindyd
ea(Id),wxwed=yd,d,
ez(Ed),wxwed=yd,d,
ea(n)xwedez(n)xwed=0,d,w,n,
dCiyd+yd1,Cic,
dxwedf(w,e),(e,w),
xwed{0,1},yd1,
f(w,e)={1,if(w,e)is free at both configurations,yd*,ifd*uses(w,e)in any configuration,0,if(w,e)is used by a nondisruptive demand.
mindyd
d,p|(w,e)Lpdxpdf(w,e),w,e,
p,dCixpd+dCiyd1,CiC,
pxpd+yd1,d,
xpd{0,1},yd{0,1}.
γd+i,dCiβiw,eLpdαw,e.
mindyd
mzm1,
yd+yddDmzm,d,
ea(Id),wxwed=yd,d,
ez(Ed),wxwed=yd,d,
ea(n)xwedez(n)xwed=0,d,w,n,
dxwedf(w,e),w,e,
xwed{0,1},yd1,zm{0,1}.