Abstract

Lightpath reconfiguration is a networking task that can be performed in order to improve resource utilization. The lightpath reconfiguration problem becomes nontrivial when a new set of lightpaths requires the release of resources previously seized by the (working) lightpaths currently in place, but, in order to ensure continuity of the traffic flow, the working lightpaths cannot be torn down before the new ones are set up. Under this condition the reconfiguration can fall into a deadlock state, and deadlocks can only be solved by temporary disruption of some connections. At this point, traffic disruptions are necessary, and network operators must compensate customers with penalty fees for the service disruption. In this paper we focus on minimizing the number of simultaneously disrupted connections at any time during the reconfiguration process. In this paper, we propose a mixed-integer program (MIP) model, an exact algorithm, and a heuristic for solving the problem considering our objective.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Farrel, J.-P. Vaseur, J. Ash, “A Path Computation Element (PCE)-Based Architecture,” IETF, RFC 4655, Aug. 2006.
  2. ITU-T, “Architecture for the Automatically Switched Optical Network (ASON),” ITU-T Recommendation G.8080/Y.1304, 2001.
  3. E. Mannie, “Generalized Multi-Protocol Label Switching (GMPLS) Architecture,” IETF, RFC 3945, Oct. 2004.
  4. Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.
  5. M. Saad, Z.-Q. Luo, “Reconfiguration with no service disruption in multifiber WDM networks,” J. Lightwave Technol., vol. 23, no. 10, pp. 3092–3104, Oct. 2005.
    [CrossRef]
  6. A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
    [CrossRef]
  7. N. Jose, A. Somani, “Connection rerouting/network reconfiguration,” in IEEE Design of Reliable Communication Networks (DRCN), Banff, Canada, 2003, pp. 23–30.
  8. D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.
  9. D. Coudert, D. Mazauric, “Network reconfiguration using cops-and-robber games,” INRIA, Research Report RR-6694, 2008.
  10. N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.
  11. D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.
  12. D. Banerjee, B. Mukherjee, “Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598–607, Oct. 2000.
    [CrossRef]
  13. H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.
  14. K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
    [CrossRef]
  15. E. Modiano, P. J. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag., vol. 39, no. 7, pp. 124–129, July 2001.
    [CrossRef]
  16. C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
    [CrossRef]
  17. F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
    [CrossRef]
  18. F. Solano, “Analyzing two different objectives of the WDM lightpath reconfiguration problem,” in IEEE GLOBECOM 2009, Honolulu, HI, 2009.
  19. H.-M. Lin, 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, TX, 1999, pp. 364–369.
  20. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979.
  21. M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann Publishers, 2004.

2007

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

2005

2004

C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
[CrossRef]

2003

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

2002

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

2001

E. Modiano, P. J. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag., vol. 39, no. 7, pp. 124–129, July 2001.
[CrossRef]

2000

D. Banerjee, B. Mukherjee, “Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598–607, Oct. 2000.
[CrossRef]

H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Ash, J.

A. Farrel, J.-P. Vaseur, J. Ash, “A Path Computation Element (PCE)-Based Architecture,” IETF, RFC 4655, Aug. 2006.

Banerjee, D.

D. Banerjee, B. Mukherjee, “Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598–607, Oct. 2000.
[CrossRef]

Caro, L.

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

Cohen, N.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

Coudert, D.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

D. Coudert, D. Mazauric, “Network reconfiguration using cops-and-robber games,” INRIA, Research Report RR-6694, 2008.

D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.

de Oliveira, J.

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

Dixit, S.

C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
[CrossRef]

Fabregat, R.

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

Farrel, A.

A. Farrel, J.-P. Vaseur, J. Ash, “A Path Computation Element (PCE)-Based Architecture,” IETF, RFC 4655, Aug. 2006.

Garey, M. R.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979.

Gencata, A.

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

Huc, F.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

Johnson, D. S.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979.

Jose, N.

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

Jou, J.-Y.

H.-M. Lin, 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, TX, 1999, pp. 364–369.

Jue, J.

H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

King, D.

Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.

Le Roux, J.-L.

Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.

Lee, Y.

Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.

Lin, H.-M.

H.-M. Lin, 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, TX, 1999, pp. 364–369.

Lin, P. J.

E. Modiano, P. J. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag., vol. 39, no. 7, pp. 124–129, July 2001.
[CrossRef]

Luo, Z.-Q.

Mannie, E.

E. Mannie, “Generalized Multi-Protocol Label Switching (GMPLS) Architecture,” IETF, RFC 3945, Oct. 2004.

Marzo, J.

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

Mazauric, D.

D. Coudert, D. Mazauric, “Network reconfiguration using cops-and-robber games,” INRIA, Research Report RR-6694, 2008.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

Medhi, D.

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

Modiano, E.

E. Modiano, P. J. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag., vol. 39, no. 7, pp. 124–129, July 2001.
[CrossRef]

Mukherjee, B.

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

D. Banerjee, B. Mukherjee, “Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598–607, Oct. 2000.
[CrossRef]

Mukherjeee, B.

H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Nepomuceno, N.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

Nisse, N.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

Oki, E.

Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.

Pérennes, S.

D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.

Pham, Q.-C.

D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.

Pioro, M.

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

Qiao, C.

C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
[CrossRef]

Saad, M.

Sereni, J.-S.

D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

Solano, F.

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

F. Solano, “Analyzing two different objectives of the WDM lightpath reconfiguration problem,” in IEEE GLOBECOM 2009, Honolulu, HI, 2009.

Somani, A.

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

Vaseur, J.-P.

A. Farrel, J.-P. Vaseur, J. Ash, “A Path Computation Element (PCE)-Based Architecture,” IETF, RFC 4655, Aug. 2006.

Xin, C.

C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
[CrossRef]

Zang, H.

H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Zhu, K.

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

IEEE Commun. Mag.

E. Modiano, P. J. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag., vol. 39, no. 7, pp. 124–129, July 2001.
[CrossRef]

IEEE J. Sel. Areas Commun.

C. Xin, C. Qiao, S. Dixit, “Traffic grooming in mesh WDM optical networks—performance analysis,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658–1669, Nov. 2004.
[CrossRef]

F. Solano, L. Caro, J. de Oliveira, R. Fabregat, J. Marzo, “G+: enhanced traffic grooming in WDM mesh networks using lighttours,” IEEE J. Sel. Areas Commun., vol. 25, no. 5, pp. 1034–1047, June 2007.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

IEEE/ACM Trans. Netw.

D. Banerjee, B. Mukherjee, “Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598–607, Oct. 2000.
[CrossRef]

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

J. Lightwave Technol.

Opt. Networks Mag.

H. Zang, J. Jue, B. Mukherjeee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Other

F. Solano, “Analyzing two different objectives of the WDM lightpath reconfiguration problem,” in IEEE GLOBECOM 2009, Honolulu, HI, 2009.

H.-M. Lin, 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, TX, 1999, pp. 364–369.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979.

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

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

D. Coudert, S. Pérennes, Q.-C. Pham, J.-S. Sereni, “Rerouting requests in WDM networks,” in AlgoTel’05, Presqu’le de Giens, France, 2005, pp. 17–20.

D. Coudert, D. Mazauric, “Network reconfiguration using cops-and-robber games,” INRIA, Research Report RR-6694, 2008.

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, N. Nisse, “Tradeoffs in process strategy games with application in the WDM reconfiguration problem,” in 5th Int. Conf. on Fun With Algorithms (FUN), Italy, 2010.

D. Coudert, F. Huc, D. Mazauric, N. Nisse, J.-S. Sereni, “Reconfiguration of the routing in WDM networks with two classes of services,” in ONDM 2009, Braunschweig, Germany, 2009.

A. Farrel, J.-P. Vaseur, J. Ash, “A Path Computation Element (PCE)-Based Architecture,” IETF, RFC 4655, Aug. 2006.

ITU-T, “Architecture for the Automatically Switched Optical Network (ASON),” ITU-T Recommendation G.8080/Y.1304, 2001.

E. Mannie, “Generalized Multi-Protocol Label Switching (GMPLS) Architecture,” IETF, RFC 3945, Oct. 2004.

Y. Lee, J.-L. Le Roux, D. King, E. Oki, “Path Computation Element Communication Protocol (PCEP) Requirements and Protocol Extensions in Support of Global Concurrent Optimization,” IETF, Internet Draft, July 2008, draft-lee-pce-global-concurrent-optimization-04.

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 (14)

Fig. 1
Fig. 1

Example of lightpath reconfiguration.

Fig. 2
Fig. 2

Dependency graph of the example depicted in Fig. 1.

Fig. 3
Fig. 3

Trade-off between the two problems.

Fig. 4
Fig. 4

Each sequence must be read from left to right. Negative vertices represent interrupt actions, whereas positive ones represent reconnect actions. Unsigned vertices represent reconfigure actions.

Fig. 5
Fig. 5

Sequence of lightpath establishments. Sequence of disconnections at the top and sequence of establishments at the bottom. Dashed arrows correspond to the edges of the dependency graph.

Fig. 6
Fig. 6

Representation of Eq. (13). Vertex α is black, vertices belonging to C = { a , c } are shaded, and vertices that have been disrupted have a dashed contour line. For this case, Δ ( { a , c } , α ) = { b , d } .

Fig. 7
Fig. 7

B&B recursive procedure for MMD.

Fig. 8
Fig. 8

Bounding in the proposed procedure.

Fig. 9
Fig. 9

Hardness of solving real instances.

Fig. 10
Fig. 10

Distribution of the number of vertices and connections in real problems and their dominant SCC.

Fig. 11
Fig. 11

Total and maximum number of disrupted connections in real instances.

Fig. 12
Fig. 12

Reconfiguration time in optimal solutions for each problem.

Fig. 13
Fig. 13

Total disruption time in optimal solutions for each problem.

Fig. 14
Fig. 14

Maximum disruption achieved by different heuristics.

Equations (15)

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

minimize z ,
x α t x α t , α C , t = t + 1 , , | T | ,
y α t y α t , α C , t = t + 1 , , | T | ,
| δ ( α ) | y α t β δ ( α ) x β t , α C , t T ,
α C y α 1 1 ,
α C y α t + 1 α C y α t + 1 , t T \ { T } ,
α C y α T = C ,
u α t α C ( x α t y α t ) , α C , t T ,
z α C u α t , t T ,
0 x α t , u α t 1 ,
y α t { 0 , 1 } ,
0 z C .
Δ ( C , α ) = | ( β C δ ( β ) δ ( α ) ) \ C | .
f ( C ) = min α C max { Δ ( C \ { α } , α ) , f ( C \ { α } ) } .
Δ ( B , α ) ϵ B , α