ETRI Journal

Electronics and Telecommunications Research Institute (한국전자통신연구원)
권호 표지
DOI QR코드

DOI QR Code

Multi-constrained Shortest Disjoint Paths for Reliable QoS Routing

  • Xiong, Ke (Institute of Information Science, Beijing Jiaotong University) ;
  • Qiu, Zheng-Ding (Institute of Information Science, Beijing Jiaotong University) ;
  • Guo, Yuchun (School of Electronics and Information Engineering, Beijing Jiaotong University) ;
  • Zhang, Hongke (School of Electronics and Information Engineering, Beijing Jiaotong University)
  • Received : 2008.09.24
  • Accepted : 2009.06.24
  • Published : 2009.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

Finding link-disjoint or node-disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. We propose design principles of an algorithm to fill this gap, which we arrive at by analyzing the properties of optimal solutions for the multi-constrained link-disjoint path pair problem. Based on this, we propose the link-disjoint optimal multi-constrained paths algorithm (LIDOMPA), to find the shortest link-disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure-aware non-dominance, are introduced to reduce its search space without loss of exactness. Extensive simulations show that LIDOMPA outperforms existing schemes and achieves acceptable complexity. Moreover, LIDOMPA is extended to the node-disjoint optimal multi-constrained paths algorithm (NODOMPA) for the multi-constrained node-disjoint path pair problem.

Keywords

References

  1. A. Sprintson et al., “Reliable Routing with QoS Guarantees for Multi-Domain IP/MPLS Networks,” Proc. IEEE INFOCOM, 2007, pp. 1820-1828.
  2. C. Lu et al., “A Novel Shared Segment Protection Algorithm for Multicast Sessions in Mesh WDM Networks,” ETRI Journal, vol. 28, no. 3, June 2006, pp. 329-336. https://doi.org/10.4218/etrij.06.0105.0158
  3. C. Peng and H. Shen, “An Improved Approximation Algorithm for Computing Disjoint QoS Paths,” Proc. ICN/ICONS/MCL, April 2006, pp. 10.
  4. W.K. Lai et al., “Fast Reroute with Pre-established Bypass Tunnel in MPLS,” Computer Communications, vol. 31, no. 9, June 8, 2008, pp. 1660-1671. https://doi.org/10.1016/j.comcom.2007.11.008
  5. P. Zhang et al., “Researches on the Problem of Link Disjoint Paths with QoS Constraints,” Journal on Communications, vol. 27, no. 6, June 2006, pp. 37-42.
  6. Y. Xiao et al., “Constrained Shortest Link-Disjoint Paths Selection: A Network Programming Based Approach,” IEEE Trans. Circuits and Systems-I: Regular Papers, vol. 53, no. 5, May 2006, pp. 1174-1187. https://doi.org/10.1109/TCSI.2006.869907
  7. D.H. Xu et al., “On the Complexity of and Algorithms for Finding the Shortest Path With a Disjoint Counterpart,” IEEE/ACM Trans. Networking, vol. 14, no. 1, Feb. 2006, pp. 147-158. https://doi.org/10.1109/TNET.2005.863451
  8. H. Naser and M. Gong, “Link-Disjoint Shortest-Delay Path-Pair Computation Algorithms for Shared Mesh Restoration Networks,” Proc. IEEE ISCC, 2007, pp. 269-274.
  9. Y.C. Guo, F.A. Kuipers, and P.V. Mieghem, “A Link Disjoint Paths Algorithm for Reliable QoS Routing,” Int. Journal of Communication Systems, vol. 16, no. 9, 2003, pp. 779-798. https://doi.org/10.1002/dac.612
  10. Y.C. Guo et al, “Disjoint Multiple-Constrained Paths Algorithms,” Journal of the China Railway Society, vol. 27, no. 2, Apr. 2005, pp. 49-57.
  11. H.D. Nevea and P.V. Mieghem, “TAMCRA: A Tunable Accuracy Multiple Constraints Routing Algorithm,” Computer Commun., vol. 23, no. 7, March 2000, pp. 667-679. https://doi.org/10.1016/S0140-3664(99)00225-X
  12. Z. Wang and J. Crowcroft, “Quality-of-Service Routing for Supporting Multimedia Applications,” IEEE J. Selected Areas in Commun., vol. 14, no. 7, Sept. 1996, pp. 1228-1234. https://doi.org/10.1109/49.536364
  13. R. Teixeira et al., “Characterizing and Measuring Path Diversity of Internet Topologies,” Proc. ACM SIGMETRICS, 2003, Poster Session, pp. 304-305.
  14. F.A. Kuipers and P.V. Mieghem, “The Impact of Correlated Link Weights on QoS Routing,” Proc. IEEE INFOCOM, vol. 2, 2003, pp. 1425-1434.
  15. P.V. Mieghem and F.A. Kuipers, “On the Complexity of QoS Routing,” Computer Communications, vol. 26, no. 4, 2003, pp. 376-387. https://doi.org/10.1016/S0140-3664(02)00156-1
  16. P.V. Mieghem et al., “Hop by Hop Quality of Service Routing,” Computer Networks, vol. 37, no. 3-4, Nov. 2001, pp. 407-423. https://doi.org/10.1016/S1389-1286(01)00222-5
  17. P.V. Mieghem and F.A. Kuipers, “Concepts of Exact QoS Routing Algorithms,” IEEE/ACM Trans. on Networking, vol. 12, no. 5, Oct. 2004, pp. 851-863. https://doi.org/10.1109/TNET.2004.836112
  18. B. Bollobas, “Random Graphs,” 2nd ed., Cambridge, New York: Academic Press, 2001.
  19. P.V. Mieghem, “Paths in the Simple Random Graph and the Waxman Graph,” Prob. in the Eng. and Info. Sci., vol. 15, no. 4, 2001, pp. 535-555.
  20. A. Orda and A. Sprintson, “QoS Routing: The Precomputation Perspective,” Proc. IEEE INFOCOM, vol. 1, 2000, pp. 128-136.

Cited by

  1. An Efficient Approximate Algorithm for Disjoint QoS Routing vol.2013, pp.None, 2013, https://doi.org/10.1155/2013/489149
  2. A Path-Counter Method for Fault-Tolerant Minimal Routing Algorithms in 2D Mesh vol.27, pp.4, 2009, https://doi.org/10.1142/s0218126618500548