A Framework for Pre-computated Multi-Constrained Quickest QoS Path Algorithm

Ashutosh Sharma, Rajiv Kumar

Abstract


The era of advance computer networks and advance communication leads the technology to new heights and the algorithms used for the routing needs to be updated side by side parallel with the advancement. This paper presents the new multi-constrained routing algorithm which gives quality of service full-fill the service level agreements with the user. Finding a multi-constrained path is a NP-complete problem, but still the presented algorithm gives the feasible path for the routing in a given polynomial time. Furthermore the performance comparison shows the best results with presented approach and existed approach.

Keywords


QoS; Multi-Constraints; NP-Complete; Performance Envelope; Reliability;

Full Text:

PDF

References


P. Ratnasingham, “The importance of trust in electronic commerce,” Internet research vol. 8, no. 4, pp. 313-321, 1998.

X. Xiao, and L.M. Ni, “Internet QoS: A big picture,” IEEE network vol. 13, no. 2, pp. 8-18, 1999.

D. L. Tennenhouse, J. M. Smith, W. D. Sincoskie, D. J. Wetherall, and G. J. Minden, “A survey of active network research,” IEEE communications Magazine, vol. 35, no. 1, pp. 80-86, 1997.

J. Arata, H. Takahashi, P. Pitakwatchara, S. L. Warisawa, K. Tanoue, K. Konishi and Y. Fujino, “A remote surgery experiment between Japan and Thailand over Internet using a low latency CODEC system,” In Robotics and Automation, 2007 IEEE International Conference on pp. 953-959, IEEE, April, 2007.

H. Lutfiyya, G. Molenkamp, M. Katchabaw and M. Bauer, “Issues in managing soft QoS requirements in distributed systems using a policybased framework,” Policies for Distributed Systems and Networks, pp. 185-201, 2001. Springer Berlin Heidelberg.

J. Carlier, Y. Li and J. L. Lutton, “Reliability evaluation of large telecommunication networks,” Discrete Applied Mathematics, vol. 76, np. 1-3, pp. 61-80, 1997.

P. Khadivi, S. Samavi and T. D. Todd, “Multi-constraint QoS routing using a new single mixed metrics,” Journal of Network and Computer Applications, vol. 31, no 4, pp. 656-676, 2008.

S. Misra, G. Xue and D. Yang, “Polynomial time approximations for multi-path routing with bandwidth and delay constraints,” In proceedings of INFOCOM 2009, IEEE, pp. 558-566, April, 2009.

Y. L. Chen and Y. H. Chin, “The quickest path problem,” Computers & Operations Research, vol. 17, no. 2, pp. 153-161, 1990.

E. D. Q. V. Martins, J. L. E. D. Santos, "An algorithm for the quickest path problem", Operations Research Letters, vol. 20, no. 4, pp. 195- 198, 1997.

J. B. Rosen, S. Z. Sun and G. Xue, “Algorithms for the quickest path problem and the enumeration of quickest paths,” Computers Operations Research, vol. 18 pp. 579-584, 1991.

G. Xue, “End-to-end data paths: quickest or most reliable?,” IEEE Communications Letters, vol. 2, no. 6, pp. 156-158, June 1998.

S. Tragoudas, “The most reliable data-path transmission,” IEEE Transactions on Reliability, vol. 50, no. 3, pp. 281-285, Sep 2001.

H.I. Calvete L.D. Pozo and J.A. Iranzo, “Algorithms for the quickest path problem and the reliable quickest path problem,” Computer Management Science vol. 9, pp. 255-272, 2012.

S. Ruzika and M. Thiemann, “Reliable and Restricted Quickest Path Problems” Project REPKA FKZ 13N9961 (TU KL), 2011.

M. El Khadiri, W. C. Yeh, “An efficient alternative to the exact evaluation of the quickest path flow network reliability problem,” Computers & Operations Research, Vol. 76, pp. 22-32, Deccember 2016.

Y. K. Lin, “Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network,” Computers & Operations Research, Vol. 30, no. 4, pp. 567-575, April 2003.

Y. K. Lin, “Spare Routing Reliability for a Stochastic Flow Network Through Two Minimal Paths Under Budget Constraint,” IEEE Transactions on Reliability, vol. 59, no. 1, pp. 2-10, March 2010.

A. Orda and A. Sprintson, “Precomputation schemes for QoS routing,” IEEE/ACM Transactions on Networking (TON), vol. 11, no. 4, pp. 578-591, 2003.

A. Iwata and N. Fujita, “A hierarchical multilayer QoS routing system with dynamic SLA management,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 12, pp. 2603-2616, 2000.

A. Orda and A. Sprintson, “A scalable approach to the partition of QoS requirements in unicast and multicast,” IEEE/ACM Transactions on Networking (TON), vol. 13, no. 5, pp. 1146-1159, 2005.

K.B.Misra, “Handbook of Performability Engineering, Springer, London, UK, 2008.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 2180-1843

eISSN: 2289-8131