Abstract

We propose an optimal scheme for finding end-to-end shortest disjoint paths with a given sequence of domains in path computation element-based multi-domain networks. We compute the shortest path over multiple domains in the forward direction and compute the disjoint path in the backward direction. The scheme has lower time and message complexity compared to contemporary schemes for finding optimal survivable paths across domains. We prove the optimality of the proposed scheme. To further simplify the implementations in practical scenarios, we also provide heuristic algorithms. Simulation results exhibit superior performance of the proposed optimal and heuristic algorithms compared to existing approaches.

© 2012 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
    [CrossRef]
  2. F. Hao and E. Zegura, “On scalable QoS routing: Performance evaluation of topology aggregation,” in Proc. of INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 147–156.
  3. N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.
  4. R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.
  5. A. Farrel, J. P. Vasseur, and J. Ash, “A path computation element (PCE)-based architecture,” IETF RFC 4655, Aug.2006.
  6. K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.
  7. F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.
  8. D. King and A. Farrel, “The application of the path computation element architecture to determination of a sequence of domains in MPLS & GMPLS,” IETF Internet Draft, draft-king-pce-hierarchy-fwk-05, Sept.2010.
  9. M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
    [CrossRef]
  10. J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.
  11. A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.
  12. I. Nishioka and D. King, “The use of synchronization VECtor (SVEC) list for synchronized dependent path computations,” IETF RFC 6007, Sept.2010.
  13. Y. Lee, G. Bernstein, and W. Imajuku, “Framework for GMPLS and path computation element control of wavelength switched optical networks,” IETF RFC 6163, Apr.2011.
  14. A. A. M. Saleh, “Transparent optical networking in backbone networks,” in Proc. of OFC, Baltimore, MD, Mar. 2000.
  15. J. P. Vasseur and J. L. Le Roux, “Path computation element (PCE) communication protocol (PCEP),” IETF RFC 5440, Mar.2009.
  16. J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
    [CrossRef]
  17. R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, 1st ed.Springer, 1999.
  18. S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
    [CrossRef]
  19. H. Chen, “A forward-search P2P TE LSP inter-domain path computation,” IETF Internet Draft, draft-chen-pce-forward-search-p2p-path-computation-02, Oct.2011.
  20. Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.
  21. R. Bradford, J. P. Vasseur, and A. Farrel, “Preserving topology confidentiality in inter-domain path computation using a path-key-based mechanism,” IETF RFC 5520, Apr.2009.
  22. P. Erdös and A. Rényi, “On random graphs. I,” Publ. Math., vol. 6, pp. 290–297, 1959.

2009 (1)

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

2008 (2)

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

2007 (1)

S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
[CrossRef]

2004 (1)

K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
[CrossRef]

1984 (1)

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
[CrossRef]

1959 (1)

P. Erdös and A. Rényi, “On random graphs. I,” Publ. Math., vol. 6, pp. 290–297, 1959.

Ash, J.

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

Benhaddou, D.

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

Bernstein, G.

Y. Lee, G. Bernstein, and W. Imajuku, “Framework for GMPLS and path computation element control of wavelength switched optical networks,” IETF RFC 6163, Apr.2011.

Bhandari, R.

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, 1st ed.Springer, 1999.

Bitar, N.

J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.

Bradford, R.

R. Bradford, J. P. Vasseur, and A. Farrel, “Preserving topology confidentiality in inter-domain path computation using a path-key-based mechanism,” IETF RFC 5520, Apr.2009.

Castoldi, P.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

Chamania, M.

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

Chen, H.

H. Chen, “A forward-search P2P TE LSP inter-domain path computation,” IETF Internet Draft, draft-chen-pce-forward-search-p2p-path-computation-02, Oct.2011.

Chen, S.

K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
[CrossRef]

Chen, X.

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

Cugini, F.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

Dasgupta, S.

S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
[CrossRef]

de Oliveira, J. C.

S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
[CrossRef]

Douville, R.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

Erdös, P.

P. Erdös and A. Rényi, “On random graphs. I,” Publ. Math., vol. 6, pp. 290–297, 1959.

Farrel, A.

R. Bradford, J. P. Vasseur, and A. Farrel, “Preserving topology confidentiality in inter-domain path computation using a path-key-based mechanism,” IETF RFC 5520, Apr.2009.

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

D. King and A. Farrel, “The application of the path computation element architecture to determination of a sequence of domains in MPLS & GMPLS,” IETF Internet Draft, draft-king-pce-hierarchy-fwk-05, Sept.2010.

Ghani, N.

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

Hao, F.

F. Hao and E. Zegura, “On scalable QoS routing: Performance evaluation of topology aggregation,” in Proc. of INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 147–156.

Hasan, M. M.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

Hoffman, M.

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

Imajuku, W.

Y. Lee, G. Bernstein, and W. Imajuku, “Framework for GMPLS and path computation element control of wavelength switched optical networks,” IETF RFC 6163, Apr.2011.

Jukan, A.

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

King, D.

D. King and A. Farrel, “The application of the path computation element architecture to determination of a sequence of domains in MPLS & GMPLS,” IETF Internet Draft, draft-king-pce-hierarchy-fwk-05, Sept.2010.

I. Nishioka and D. King, “The use of synchronization VECtor (SVEC) list for synchronized dependent path computations,” IETF RFC 6007, Sept.2010.

Kumaki, K.

K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.

Le Roux, J. L.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.

J. P. Vasseur and J. L. Le Roux, “Path computation element (PCE) communication protocol (PCEP),” IETF RFC 5440, Mar.2009.

Lee, Y.

Y. Lee, G. Bernstein, and W. Imajuku, “Framework for GMPLS and path computation element control of wavelength switched optical networks,” IETF RFC 6163, Apr.2011.

Lehman, T.

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

Liu, K.

K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
[CrossRef]

Liu, Q.

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

Masip-Bruin, X.

A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.

Murai, T.

K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.

Nahrstedt, K.

K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
[CrossRef]

Nishioka, I.

I. Nishioka and D. King, “The use of synchronization VECtor (SVEC) list for synchronized dependent path computations,” IETF RFC 6007, Sept.2010.

Orda, A.

A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.

Palacharla, P.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

Paolucci, F.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

Rambach, F.

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

Rao, N. S. V.

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

Rényi, A.

P. Erdös and A. Rényi, “On random graphs. I,” Publ. Math., vol. 6, pp. 290–297, 1959.

Rougier, J. L.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

Saleh, A. A. M.

A. A. M. Saleh, “Transparent optical networking in backbone networks,” in Proc. of OFC, Baltimore, MD, Mar. 2000.

Sasaki, C.

K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.

Secci, S.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

Sekiya, M.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

Sprintson, A.

A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.

Suurballe, J.

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
[CrossRef]

Tarjan, R.

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
[CrossRef]

Valcarenghi, L.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

Vasseur, J. P.

S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
[CrossRef]

J. P. Vasseur and J. L. Le Roux, “Path computation element (PCE) communication protocol (PCEP),” IETF RFC 5440, Mar.2009.

R. Bradford, J. P. Vasseur, and A. Farrel, “Preserving topology confidentiality in inter-domain path computation using a path-key-based mechanism,” IETF RFC 5520, Apr.2009.

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

J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.

Wang, X.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

Welin, A.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

Yamagata, T.

K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.

Yannuzzi, M.

A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.

Zegura, E.

F. Hao and E. Zegura, “On scalable QoS routing: Performance evaluation of topology aggregation,” in Proc. of INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 147–156.

Zhang, Q.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

Zhang, R.

J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.

IEEE Commun. Mag. (2)

N. Ghani, Q. Liu, D. Benhaddou, N. S. V. Rao, and T. Lehman, “Control plane design in multi-domain multilayer optical networks,” IEEE Commun. Mag., vol. 46, no. 6, pp. 78–87, June2008.

R. Douville, J. L. Le Roux, J. L. Rougier, and S. Secci, “A service plane over the PCE architecture for automatic multi-domain connection-oriented services,” IEEE Commun. Mag., vol. 46, no. 6, pp. 94–102, June2008.

IEEE Netw. (1)

S. Dasgupta, J. C. de Oliveira, and J. P. Vasseur, “Path-computation-element-based architecture for inter-domain MPLS/GMPLS traffic engineering: Overview and performance,” IEEE Netw., vol. 21, no. 4, pp. 38–45, July–Aug.2007.
[CrossRef]

IEEE/ACM Trans. Netw. (1)

K. Liu, K. Nahrstedt, and S. Chen, “Routing with topology abstraction in delay-bandwidth sensitive networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 17–29, Feb.2004.
[CrossRef]

Networks (1)

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
[CrossRef]

Opt. Switching Netw. (1)

M. Chamania, X. Chen, A. Jukan, F. Rambach, and M. Hoffman, “An adaptive inter-domain PCE framework to improve resource utilization and reduce inter-domain signaling,” Opt. Switching Netw., vol. 6, no. 4, pp. 259–267, Dec.2009.
[CrossRef]

Publ. Math. (1)

P. Erdös and A. Rényi, “On random graphs. I,” Publ. Math., vol. 6, pp. 290–297, 1959.

Other (15)

J. P. Vasseur, R. Zhang, N. Bitar, and J. L. Le Roux, “A backward-recursive PCE-based computation (BRPC) procedure to compute shortest constrained inter-domain traffic engineering label switched paths,” IETF RFC 5441, Apr.2009.

A. Sprintson, M. Yannuzzi, A. Orda, and X. Masip-Bruin, “Reliable routing with QoS guarantees for multi-domain IP/MPLS networks,” in Proc. of IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 1820–1828.

I. Nishioka and D. King, “The use of synchronization VECtor (SVEC) list for synchronized dependent path computations,” IETF RFC 6007, Sept.2010.

Y. Lee, G. Bernstein, and W. Imajuku, “Framework for GMPLS and path computation element control of wavelength switched optical networks,” IETF RFC 6163, Apr.2011.

A. A. M. Saleh, “Transparent optical networking in backbone networks,” in Proc. of OFC, Baltimore, MD, Mar. 2000.

J. P. Vasseur and J. L. Le Roux, “Path computation element (PCE) communication protocol (PCEP),” IETF RFC 5440, Mar.2009.

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

K. Kumaki, T. Murai, T. Yamagata, and C. Sasaki, “BGP protocol extensions for path computation element (PCE) discovery in a BGP/MPLS IP-VPN,” IETF Internet Draft, draft-kumaki-pce-bgp-disco-attribute-06, Sept.2010.

F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, and A. Welin, “PCE communication protocol for resource advertisement in multi-domain BGP-based networks,” in Proc. of OFC, San Diego, CA, Mar. 2009.

D. King and A. Farrel, “The application of the path computation element architecture to determination of a sequence of domains in MPLS & GMPLS,” IETF Internet Draft, draft-king-pce-hierarchy-fwk-05, Sept.2010.

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, 1st ed.Springer, 1999.

F. Hao and E. Zegura, “On scalable QoS routing: Performance evaluation of topology aggregation,” in Proc. of INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 147–156.

H. Chen, “A forward-search P2P TE LSP inter-domain path computation,” IETF Internet Draft, draft-chen-pce-forward-search-p2p-path-computation-02, Oct.2011.

Q. Zhang, M. M. Hasan, X. Wang, P. Palacharla, and M. Sekiya, “Efficient PCE-based survivable path computation in multi-domain networks,” in Proc. of IEEE INFOCOM High Speed Networks (HSN), Shanghai, China, Apr. 2011.

R. Bradford, J. P. Vasseur, and A. Farrel, “Preserving topology confidentiality in inter-domain path computation using a path-key-based mechanism,” IETF RFC 5520, Apr.2009.

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

Fig. 1
Fig. 1

(Color online) BRPC computes a shortest path that does not follow a given domain sequence.

Fig. 2
Fig. 2

(Color online) The FPC scheme.

Fig. 3
Fig. 3

(Color online) The FPC–BPC scheme.

Fig. 4
Fig. 4

(Color online) FPC–BPC with Suurballe’s algorithm using path keys.

Fig. 5
Fig. 5

(Color online) Different domain sequences for working and backup paths.

Fig. 6
Fig. 6

(Color online) Possible overlapping between shortest paths.

Fig. 7
Fig. 7

(Color online) Finding multi-domain overlapping.

Fig. 8
Fig. 8

(Color online) Possible traversals of shortest paths at D k during BPC.

Fig. 9
Fig. 9

Comparison of number of successes in finding path pairs. (The total number of demands is 200.)

Fig. 10
Fig. 10

Comparison of average total cost per disjoint path pair.

Fig. 11
Fig. 11

(Color online) Number of shortest path routing executions per demand.

Fig. 12
Fig. 12

(Color online) Average running time per demand.

Tables (1)

Tables Icon

Table I A Comparison of Multi-domain Path Computation Schemes

Equations (6)

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

SP 1 = ( s , PKS 12 , E 12 , I 22 , PKS 22 , d ) ,
SP 2 = ( s , E 13 , I 23 , PKS 23 , I 22 , E 12 , PKS 12 , s , PKS 11 , E 11 , I 21 , PKS 21 , d ) .
SP 2 = s , b , t  path segment of SP 2 + t , a , l  path segment of reversed–negated SP 1 + l , c  path segment of  p + c , d  path segment of  SP 2 .
W ( SP 2 ) = W ( s , b , t ) W ( t , a , l ) + W ( l , c ) + W ( c , d ) .
W ( SP 2 ) = W ( s , b , t ) W ( t , a , l ) W ( l , e ) + W ( e , c ) + W ( c , d ) .
W ( SP 2 ) W ( SP 2 ) = W ( l , c ) + W ( l , e ) W ( e , c ) = [ W ( s , e ) + W ( l , e ) + W ( l , c ) ] [ W ( s , e ) + W ( e , c ) ] = W ( the shortest path  p  from  s  to  c ) W ( s , e , c ) = 0 .