# 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 Sharma^{a}, Rajiv Kumar^{a}, and Pradeep Kumar Singh^{b}
^{a}Department of Electronics and Communication, Jaypee University of Information Technology, Solan, 173215, India
^{b}Department 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**
- 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
- 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
- L. -J. Jin, V. Machiraju, and A. Sahai, “Analysis on Service Level Agreement of Web Services,”
*HP June*, 2002
- 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
- Y. Chen and Y. Chin, “The Quickest Path Problem,”
*Computers & Operations Research*,* *Vol. 17, pp. 153-161, 1990
- M. H. Moore, “On the Fastest Route for Convoy-Type Traffic in Flowrate-Constrained Networks,”
*Transportation Science*,* *Vol. 10, pp. 113-124, 1976
- H. W. Hamacher and S. A. Tjandra, “Mathematical Modelling of Evacuation Problems: A State of Art,” 2001
- H. I. Calvete, “The Quickest Path Problem with Interval Lead Times,”
*Computers & Operations Research*,* *Vol. 31, pp. 383-395, 2004
- G. -H. Chen and Y. -C. Hung, “On the Quickest Path Problem,”
*Information Processing Letters*,* *Vol. 46, pp. 125-128, 1993
- Y. Chen, “Finding the k Quickest Simple Paths in a Network,”
*Information Processing Letters*,* *Vol. 50, pp. 89-92, 1994
- 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
- G. Ghiani and E. Guerriero, “A Lower Bound for the Quickest Path Problem,”
*Computers & Operations Research*,* *Vol. 50, pp. 154-160, 2014
- 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
- 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
- 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
- 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
- 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
- B. Pelegrı́n and P. Fernández, “On the Sum-Max Bicriterion Path Problem,”
*Computers & **O**perations **R**esearch*,* *Vol. 25, pp. 1043-1054, 1998
- 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
- 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
- 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
- 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
- H. I. Calvete, L. del-Pozo, and J. A. Iranzo, “The Energy-Constrained Quickest Path Problem,”
*Optimization Letters*,* *Vol. 11, pp. 1319-1339, 2017
- 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
- 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
- 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
- A. Sharma and R. Kumar, “Risk-Energy Aware Service Level Agreement Assessment for Computing Quickest Path in Computer Networks,”
*Int**ernational** J**ournal of** Reliability and Safety*,* *2018
- S. Ruzika and M. Thiemann, “Reliable and Restricted Quickest Path Problems,” Network Optimization, pp. 309-314, Springer, 2011
- G. Xue, “End-to-End Data Paths: Quickest or Most Reliable?”
*IEEE Communications Letters*,* *Vol. 2, pp. 156-158, 1998
- 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
- 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
- R. E. Shawi, J. Gudmundsson, and C. Levcopoulos, “Quickest Path Queries on Transportation Network,”
*Computational Geometry*,* *Vol. 47, pp. 695-709, 2014
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- C. Gen-Huey and H. Yung-Chen, “Algorithms for the Constrained Quickest Path Problem and the Enumeration of Quickest Paths,”
*Computers & **O**perations **R**esearch*,* *Vol. 21, pp. 113-118, 1994
- 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
- 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
- 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. |