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

doi:10.23940/ijpe.19.04.p1.10611072

Abstract

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.

Key words: quickest path problem, service level agreements constraint, reliability, minimization problem, computer communication network

Ashutosh Sharma, Rajiv Kumar, and Pradeep Kumar Singh. SLA Constraint Quickest Path Problem for Data Transmission Services in Capacitated Networks [J]. Int J Performability Eng, 2019, 15(4): 1061-1072.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

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,D. Goderis, “Service Level Agreements: A Main Challenge for Next Generation Networks,” inProceedings 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,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,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,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,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,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,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,” inProceedings of ACM SIGCOMM Computer Communication Review, pp. 289-298, 1993
44 S. Zhang, C. Martel,B. Mukherjee, “Dynamic Traffic Grooming in Elastic Optical Networks,”IEEE Journal on Selected Areas in Communications, Vol. 31, pp. 4-12, 2013

[1]	Zhiyang Zhang, Yonghua Li, Dongxu Zhang, Yuhan Tang, and Qing Xia. Reliability Evaluation of Flat Car Underframe based on GSA-BP Neural Network and Probability Box [J]. Int J Performability Eng, 2024, 20(6): 400-411.
[2]	Kangjun Xu, Yonghua Li, Qi Gong, Dongxu Zhang, and Tao Guo. A Novel Fatigue Reliability Calculation Method Based on INGO-BPNN [J]. Int J Performability Eng, 2024, 20(5): 319-332.
[3]	Darius Muyizere, Arcade Nshimiyimana, Theophile Mugerwa, Lawrence K. Letting, and Bernard B. Munyazikwiye. Reliability Assessment of Distribution System Grid-Connected Multi-Inverter for Solar Photo-Voltaic Systems: A Case Study [J]. Int J Performability Eng, 2024, 20(3): 149-156.
[4]	Amit Kumar Singh and P. C. Tewari. An Overview of Reliability, Availability, Maintainability, and Safety Strategies for Complex Systems in Various Process Industries [J]. Int J Performability Eng, 2023, 19(12): 788-796.
[5]	Yonghua Li, Shujian Liu, Xiaoning Bai, and Yufeng Wang. An Interval-Probability Hybrid Structural Reliability Calculation Method Based on CSSA-BR-BP [J]. Int J Performability Eng, 2023, 19(10): 687-699.
[6]	Jinxin Wang, Zhiping Zhai, Yuezheng Lan, Xiaoyi Zhai, and Lixiang Zhao. Reliability Analysis and Optimization of Forage Crushers Based on Bayesian Network [J]. Int J Performability Eng, 2023, 19(10): 700-709.
[7]	Yu-Lun Chao, Yi-Kuei Lin, and Cheng-Ta Yeh. AMC-Based Algorithm for Network Reliability Evaluation of a Manufacturing System with Scrapping and Rework [J]. Int J Performability Eng, 2022, 18(4): 231-240.
[8]	Madhumitha J, and G. Vijayalakshmi. Multi-State Performance Analysis of Linear Consecutive 2-out-of-4: F System using Markov Reward Model [J]. Int J Performability Eng, 2022, 18(12): 903-910.
[9]	Risu Na, Weiguo Zhang, Kaifa Jia, and Quan Zhang. Key Factors of Seal Ring Reliability based on QFD [J]. Int J Performability Eng, 2022, 18(11): 759-769.
[10]	Tae-Jin Yang. Comparative Analysis on the Reliability Performance of NHPP Software Reliability Model Applying Exponential-Type Lifetime Distribution [J]. Int J Performability Eng, 2022, 18(10): 679-689.
[11]	Surbhi Gupta, H.D. Aroraa, Anjali Naithania, Anil Chandrab. Reliability Assessment of the Planning and Perception Software Competencies of Self-Driving Cars [J]. Int J Performability Eng, 2021, 17(9): 779-786.
[12]	Tyler D. Ridder and Ram M. Narayanan. Radar Detection Performability under Graceful Degradation [J]. Int J Performability Eng, 2021, 17(8): 666-675.
[13]	Yi-Chun Cheng, Yi-Kuei Lin, and Ping-Chen Chang. Reliability Evaluation for a Multistate Network with Time Attribute and Periodical Maintenance [J]. Int J Performability Eng, 2021, 17(8): 676-685.
[14]	Yi-Fan Chen, Yi-Kuei Lin, and Cheng-Fu Huang. Using Deep Neural Networks to Evaluate the System Reliability of Manufacturing Networks [J]. Int J Performability Eng, 2021, 17(7): 600-608.
[15]	Youssef Bassir, Achraf Wahid, Abdelkarim Kartouni, and Mohamed ELghorba. Estimation of Wire Rope Reliability by Two Analytical Approach [J]. Int J Performability Eng, 2021, 17(7): 619-626.