Username   Password       Forgot your password?  Forgot your username? 

 

SLA Constraint Quickest Path Problem for Data Transmission Services in Capacitated Networks

Volume 15, Number 4, April 2019, pp. 1061-1072
DOI: 10.23940/ijpe.19.04.p1.10611072

Ashutosh Sharmaa, Rajiv Kumara, and Pradeep Kumar Singhb

aDepartment of Electronics and Communication, Jaypee University of Information Technology, Solan, 173215, India
bDepartment of Computer Science and Engineering, Jaypee University of Information Technology, Solan, 173215, India

 

(Submitted on July 10, 2018; Revised on November 10, 2018; Accepted on March 15, 2019)

Abstract:

In this paper, an extension has been made on the quickest path problem (QPP) with a constraint of service level agreements and energy required for the data transmission services. This new variant of QPP strengthens the applicability of QPP with criticality of data transmission service. The criticality of service is measured in terms of the requested service completion time and mean time of failure of service. The selection of the values of the constraint plays an important role in the computation of the SLA constraint quickest path problem (SLAQPP) for the data transmission services. The variation of SLA has been analysed to obtain the pattern of selection of number of SLAQPP paths. The proposed algorithm is tested on serval benchmark networks and random networks, providing results after computation of SLAQPP. The results show that the proposed algorithm outperforms several existing algorithms in terms of selection of paths and computation time.

References: 44

    1. H. Liu, H. Ning, Q. Mu, Y. Zheng, J. Zeng, L. T. Yang, et al., “A Review of the Smart World,” Future Generation Computer Systems, 2017
    2. E. Marilly, O. Martinot, H. Papini, and D. Goderis, “Service Level Agreements: A Main Challenge for Next Generation Networks,” in Proceedings of the 2nd European Conference on Universal Multiservice Networks, pp. 297-304, 2002
    3. L. -J. Jin, V. Machiraju, and A. Sahai, “Analysis on Service Level Agreement of Web Services,” HP June, 2002
    4. R. Kumar and P. Cholda, “A Framework for Continuity of Mission-Critical Network Services,” in Proceedings of 2015 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), pp. 1-3, 2015
    5. Y. Chen and Y. Chin, “The Quickest Path Problem,” Computers & Operations Research, Vol. 17, pp. 153-161, 1990
    6. M. H. Moore, “On the Fastest Route for Convoy-Type Traffic in Flowrate-Constrained Networks,” Transportation Science, Vol. 10, pp. 113-124, 1976
    7. H. W. Hamacher and S. A. Tjandra, “Mathematical Modelling of Evacuation Problems: A State of Art,” 2001
    8. H. I. Calvete, “The Quickest Path Problem with Interval Lead Times,” Computers & Operations Research, Vol. 31, pp. 383-395, 2004
    9. G. -H. Chen and Y. -C. Hung, “On the Quickest Path Problem,” Information Processing Letters, Vol. 46, pp. 125-128, 1993
    10. Y. Chen, “Finding the k Quickest Simple Paths in a Network,” Information Processing Letters, Vol. 50, pp. 89-92, 1994
    11. J. C. Clímaco, M. M. Pascoal, J. M. Craveirinha, and M. E. V. Captivo, “Internet Packet Routing: Application of a K-Quickest Path Algorithm,” European Journal of Operational Research, Vol. 181, pp. 1045-1054, 2007
    12. G. Ghiani and E. Guerriero, “A Lower Bound for the Quickest Path Problem,” Computers & Operations Research, Vol. 50, pp. 154-160, 2014
    13. E. D. Q. V. Martins and J. L. E. Dos Santos, “An Algorithm for the Quickest Path Problem,” Operations Research Letters, Vol. 20, pp. 195-198, 1997
    14. C. -K. Park, S. Lee, and S. Park, “A Label-Setting Algorithm for Finding a Quickest Path,” Computers & Operations Research, Vol. 31, pp. 2405-2418, 2004
    15. J. B. Rosen, S. -Z. Sun, and G. -L. Xue, “Algorithms for the Quickest Path Problem and the Enumeration of Quickest Paths,” Computers & Operations Research, Vol. 18, pp. 579-584, 1991
    16. M. Pascoal, M. Captivo, and J. Clímaco, “Computational Experiments with a Lazy Version of a K Quickest Simple Path Ranking Algorithm,” TOP, Vol. 15, pp. 372-382, 2007
    17. M. M. Pascoal, M. E. V. Captivo, and J. C. Clı́maco, “An Algorithm for Ranking Quickest Simple Paths,” Computers & Operations Research, Vol. 32, pp. 509-520, 2005
    18. B. Pelegrı́n and P. Fernández, “On the Sum-Max Bicriterion Path Problem,” Computers & Operations Research, Vol. 25, pp. 1043-1054, 1998
    19. Y. -K. Lin, “Extend the Quickest Path Problem to the System Reliability Evaluation for a Stochastic-Flow Network,” Computers & Operations Research, Vol. 30, pp. 567-575, 2003
    20. Y. -K. Lin, “Optimal Pair of Minimal Paths under Both Time and Budget Constraints,” IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol. 39, pp. 619-625, 2009
    21. M. M. Pascoal, M. E. V. Captivo, and J. C. Clímaco, “A Comprehensive Survey on the Quickest Path Problem,” Annals of Operations Research, Vol. 147, pp. 5-21, 2006
    22. H. I. Calvete, L. del-Pozo, and J. A. Iranzo, “Algorithms for the Quickest Path Problem and the Reliable Quickest Path Problem,” Computational Management Science, Vol. 9, pp. 255-272, 2012
    23. H. I. Calvete, L. del-Pozo, and J. A. Iranzo, “The Energy-Constrained Quickest Path Problem,” Optimization Letters, Vol. 11, pp. 1319-1339, 2017
    24. A. Sharma and R. Kumar, “A Framework for Pre-Computated Multi-Constrained Quickest QoS Path Algorithm,” Journal of Telecommunication, Electronic and Computer Engineering (JTEC), Vol. 9, pp. 73-77, 2017
    25. A. Sedeño-Noda and J. D. González-Barrera, “Fast and Fine Quickest Path Algorithm,” European Journal of Operational Research, Vol. 238, pp. 596-606, 2014
    26. H. I. Calvete, L. del-Pozo, and J. A. Iranzo, “Dealing with Residual Energy When Transmitting Data in Energy-Constrained Capacitated Networks,” European Journal of Operational Research, Vol. 269, No. 2, pp. 602-620, 2018
    27. A. Sharma and R. Kumar, “Risk-Energy Aware Service Level Agreement Assessment for Computing Quickest Path in Computer Networks,” International Journal of Reliability and Safety, 2018
    28. S. Ruzika and M. Thiemann, “Reliable and Restricted Quickest Path Problems,” Network Optimization, pp. 309-314, Springer, 2011
    29. G. Xue, “End-to-End Data Paths: Quickest or Most Reliable?” IEEE Communications Letters, Vol. 2, pp. 156-158, 1998
    30. M. Ghiyasvand and A. Ramezanipour, “Solving the MCQP, MLT, and MMLT Problems and Computing Weakly and Strongly Stable Quickest Paths,” Telecommunication Systems, Vol. 68, pp. 217-230, 2018
    31. N. Agatz, P. Bouman, and M. Schmidt, “Optimization Approaches for the Traveling Salesman Problem with Drone,” Transportation Science, Vol. 52, No. 4, pp. 965-981, 2018
    32. R. E. Shawi, J. Gudmundsson, and C. Levcopoulos, “Quickest Path Queries on Transportation Network,” Computational Geometry, Vol. 47, pp. 695-709, 2014
    33. D. Männel and A. Bortfeldt, “A Hybrid Algorithm for the Vehicle Routing Problem with Pickup and Delivery and 3D Loading Constraints,” European Journal of Operational Research, Vol. 254, No. 3, pp. 840-858, 2016
    34. E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, “The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints,” European Journal of Operational Research, Vol. 251, pp. 369-386, 2016
    35. D. -Y. Lin and Y. -T. Chang, “Ship Routing and Freight Assignment Problem for Liner Shipping: Application to the Northern Sea Route planning problem,” Transportation Research Part E: Logistics and Transportation Review, Vol. 110, pp. 47-70, 2018
    36. M. Issabakhsh, S. -M. Hosseini-Motlagh, M. -S. Pishvaee, and M. Saghafi Nia, “A Vehicle Routing Problem for Modeling Home Healthcare: a Case Study,” International Journal of Transportation Engineering, Vol. 5, pp. 211-228, 2018
    37. A. Sharma and R. Kumar, “An Optimal Routing Scheme for Critical Healthcare HTH Services—An IOT Perspective,” in Proceedings of 2017 Fourth International Conference on Image Information Processing (ICIIP), pp. 1-5, 2017
    38. W. -W. Wu, A. Ning, and X. -X. Ning, “Evaluation of the Reliability of Transport Networks based on the Stochastic Flow of Moving Objects,” Reliability Engineering & System Safety, Vol. 93, pp. 838-844, 2008
    39. W. Fawaz, B. Daheb, O. Audouin, M. Du-Pond, and G. Pujolle, “Service Level Agreement and Provisioning in Optical Networks,” IEEE Communications Magazine, Vol. 42, pp. 36-43, 2004
    40. G. Xie, G. Zeng, Y. Chen, Y. Bai, Z. Zhou, R. Li, et al., “Minimizing Redundancy to Satisfy Reliability Requirement for a Parallel Application on Heterogeneous Service-Oriented Systems,” IEEE Transactions on Services Computing, 2017
    41. C. Gen-Huey and H. Yung-Chen, “Algorithms for the Constrained Quickest Path Problem and the Enumeration of Quickest Paths,” Computers & Operations Research, Vol. 21, pp. 113-118, 1994
    42. M. L. Fredman and R. E. Tarjan, “Fibonacci Heaps and their Uses in Improved Network Optimization Algorithms,” Journal of the ACM (JACM), Vol. 34, pp. 596-615, 1987
    43. J. -C. Bolot, “End-to-End Packet Delay and Loss Behavior in the Internet,” in Proceedings of ACM SIGCOMM Computer Communication Review, pp. 289-298, 1993
    44. S. Zhang, C. Martel, and B. Mukherjee, “Dynamic Traffic Grooming in Elastic Optical Networks,” IEEE Journal on Selected Areas in Communications, Vol. 31, pp. 4-12, 2013

     

    Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

     
    This site uses encryption for transmitting your passwords. ratmilwebsolutions.com