An efficient QoS routing algorithm for multi-constrained path selection

Abstract

An efficient QoS routing algorithm was proposed for multiple constrained path selection. Making use of efficient pruning policy, the algorithm reduces greatly the size of search space and the computing time. Although the proposed algorithm has exponential time complexity in the worst case, it can get the running results quickly in practical application. When the scale of network increases, the algorithm can efficiently control the size of search space by constraint conditions and prior queue. The results of simulation show that successful request ratio (r) of efficient algorithm for multi-constrained optimal path (EAMCOP) is better than that of heuristic algorithm for multi-constrained optimal path (H-MCOP), but average computing time (t) of EAMCOP is far less than that of H-MCOP. And it can be seen that the computing time of EAMCOP is only one fourth of that of H-MCOP in Advanced Research Projects Agency Network (ARPANet) topology.

Keywords

QoS routing / multiple constraint / path selection / algorithm

References

[1] Guerin R, Orda A. Networks with advance reservations: the routing perspective [A]. Proceedings of the INFOCOM 2000 Conference [C]. Israel, 2000.

[2] WangJian-xin, ChenSong-qiao, ChenJian-er. An effective randomized QoS routing algorithm on networks with inaccurate parameters [J]. Journal of Computer Science and Technology, 2002, 17(1): 38-46

[3] WANG Z, Crowcroft J. Bandwidth-delay based routing algorithms[A]. Proceedings of the GLOBECOM’ 95 Conference [C]. Singapore, 1995.

[4] AhujaR K, MagnantiT. L, OrlinJ. B.Network Flows: Theory, Algorithms, and Applications [M], 1993, New Jersey, Prentice Hall Press

[5] JaffeJ M. Algorithms for finding paths with multiple constraint[J]. Networks, 1984, 14(1): 95-116

[6] Korkmaz T, Krunz M. Multi-constrained optimal path selection [A]. In Proceedings of the IEEE INFOCOM 2001 Conference [C]. Alaska, 2001.

[7] WaxmanB M. Routing of multipoint connections [J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622

[8] CalvertK I, DoarM B, ZeguraE W. Modeling Internet topology [J]. IEEE Communications Magazine, 1997, 35(6): 160-163

[9] WangJian-xin, ChenSong-qiao, ChenJian-er. Anycast service model and its QoS routing algorithm [J]. Journal of Central South University of Technology, 2001, 8(2): 135-139

[10] RampalS, ReevesD S. An evaluation of routing and admission control algorithms for multimedia traffic [J]. Computer Communication, 1995, 18(10): 755-768