计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 26-33.doi: 10.11896/jsjkx.200900211

所属专题: 智能化边缘计算

• 智能化边缘计算* 上一篇    下一篇

基于排队论的服务资源可用性相关研究综述

张恺琪, 涂志莹, 初佃辉, 李春山   

  1. 哈尔滨工业大学(威海)计算机科学与技术学院 山东 威海 264209
  • 收稿日期:2020-09-29 修回日期:2020-11-07 出版日期:2021-01-15 发布日期:2021-01-15
  • 通讯作者: 涂志莹(tzy_hit@hit.edu.cn)
  • 作者简介:2931801774@qq.com
  • 基金资助:
    国家重点研发项目(2018YFB1702900);国家自然科学基金(61772159,61802089,61832004);山东省自然科学基金(ZR2017MF02661802089)

Survey on Service Resource Availability Forecast Based on Queuing Theory

ZHNAG Kai-qi, TU Zhi-ying, CHU Dian-hui, LI Chun-shan   

  1. School of Computer Science and Technology,Harbin Institute of Technology,Weihai,Weihai,Shandong 264209,China
  • Received:2020-09-29 Revised:2020-11-07 Online:2021-01-15 Published:2021-01-15
  • About author:ZHANG Kai-qi,born in 1995,Ph.D student.Her main research interests include service recommendation and so on.
    TU Zhi-ying,born in 1983,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include service computing and knowledge engineering.
  • Supported by:
    National Key Research and Development Projects (2018YFB1702900),National Natural Science Foundation of China(61772159,61802089,61832004) and Shandong Province Nature Science Foundation(ZR2017MF02661802089).

摘要: 排队论在很多领域中解决了复杂的排队问题,文中首先对排队论的一般模型表示和常见模型进行了介绍。然后,简要对排队论解决的各类问题进行了归纳总结,重点对近年来有关排队论的服务资源可用性预测文献进行了综述,对排队模型在日常生活、云计算以及网络资源等场景中的应用进行总结。通过对文献进行综述找到服务与用户需求之间的关系,并对预测服务可用性的目的进行分类和总结归纳,包括对资源进行预测、合理规划以及分配资源、满足用户需求、缩短用户等待时间、提高系统可靠性等。通过对此类文献的总结,找出其存在的问题,并提出了改进方法和建议。最后,对基于排队论的服务资源可用性预测在推荐方面的应用进行趋势展望,并简要说明今后的研究方向和将要遇到的挑战。

关键词: 服务资源, 排队论, 网络资源, 云计算, 资源可用性

Abstract: Queuing theory solves various complex queuing problems in many fields.This paper first introduces the general model representation and common models of queuing theory.Secondly,it briefly summarizes the various problems solved by queuing theory,and focuses on the literatures on service availability prediction of queuing theory in recent years,including its application in different fields,such as daily life,cloud computing,and network resources.To find the relationship between service and user needs,it classifies and summarizes the purpose of predicting service availability,including predicting resources,reasonably planning and allocating resources,meeting user needs,reducing user waiting time,and improving system reliability,etc.Through the summary of such documents,it finds the existing problems,and puts forward improvement methods and suggestions.Finally,the application of service resource availability predictions based on queuing theory in recommendation is forecasted,and the future research directions and challenges are briefly explained.

Key words: Cloud computing, Network resources, Queuing theory, Resource availability, Service resources

中图分类号: 

  • TP311.5
[1] XU X,SHENG Q Z,ZHANG L J,et al.From Big Data to Big Service[J].Computer,2015,48(7):80-83.
[2] DORDA M,TEICHMANN D,GRAF V.Optimisation of service capacity based on queueing theory[J].MM Science Journal,2019(3):2975-2981.
[3] GORUNESCU F,MCCLEAN S I,MILLARD P H.A queueing model for bed-occupancy management and planning of hospitals[J].Journal of the Operational Research Society,2002,53(1):19-24.
[4] LI X,BEULLENS P,JONES D,et al.Optimal bed allocation in hospitals[M].Berlin:Springer Berlin Heidelberg,2009.
[5] TIRDAD A,GRASSMANN W K,TAVAKOLI J.Optimal policies of M(t)/M/c/c queues with two different levels of servers[J].European Journal of Operational Research,2016,249(3):1124-1130.
[6] CHAN J,ZHANG L.Case mix index weighted multi-objective optimization of inpatient bed allocation in general hospital[J].Journal of Combinatorial Optimization,2019,37(1):1-19.
[7] KRPAN L,ROBERT M,MILKOVIĆM.A model of the dimensioning of the number of service places at parking lot entrances by using the queuing theory[J].Tehnicki vjesnik-Technical Gazette,2017,24(1):231-238.
[8] KATSINIS C,CONSTANT A.Effect of queue selection andservice time distributions in multiple resource allocation[J].Computer Systems Science & Engineering,1994,9(3):184-194.
[9] JONATHA A,PAOLO C,EDOARDO A.On the consolidation of data-centers with performance constraints[M].Berlin:Springer Berlin Heidelberg,2009.
[10] ZHOU X,CAI Y,CHOW E.An integrated approach with feedback control for robust web QoS design[J].Computer Communications,2006,29(16):3158-3169.
[11] ELSHERIF A A,MOHAMED A.Joint routing and resource allocation for delay minimization in cognitive radio based mesh networks[J].IEEE Transactions on Wireless Communications,2014,13(1):186-197.
[12] KHOMONENKO A D,GINDIN S I,MODHER K M.A cloud computing model using multi-channel queuing system with coo-ling[C]//XIX IEEE International Conference on Soft Compu-ting & Measurements.IEEE,2016:103-106.
[13] YAN Z X,LIU W,XU D.Study of cloud service queuing model based on imbedding markov chain perspective[J].Cluster Computing,2018,21(1):837-844.
[14] SALAH K,SHELTAMI T R.Performance modeling of cloudapps using message queueing as a service (MaaS)[C]//Confe-rence on Innovations in Clouds.IEEE,2017:65-71.
[15] LI L,XUE,LIN Y L.A two-stage stochastic model for cloud computing simulation of resource efficiency cost analysis[C]//IEEE International Conference on Computer and Communications (ICCC).IEEE,2017:2267-2274.
[16] HICHA B A,SAID B A,ABDALLAH E.A novel architecture with dynamic queues based on fuzzy logic and particle swarm optimization algorithm for task scheduling in cloud computing[M]//Advances in Ubiquitous Networking 2.Springer Singapore,2017.
[17] BARABASI,ALBERTl L.The origin of bursts and heavy tails in human dynamics[J].Nature,2005,435(7039):207.
[18] BOYDON C.Assessment of an alternative payment scheme for manual gasoline stations using queuing theory[C]//IEEE International Conference on Industrial Engineering and Applications (ICIEA).IEEE,2019:299-305.
[19] BJATTACHARJEE P,RAY P K.Simulation modelling andanalysis of appointment system performance for multiple classes of patients in a hospital:A case study[J].Operations Research for Health Care,2015,8:71-84.
[20] VARNE J,BEAN N,MACKAY M.The self-regulating nature of occupancy in ICUs:stochastic homoeostasis[J].Health Care Management Science,2019,22(4):615-634.
[21] LU R,LIN X,ZHU H,et al.SPARK:A new VANET-based smart parking scheme for large parking lots[C]//IEEE Infocom.IEEE,2009:1413-1421.
[22] LAM W H K,LI Z C,HUANG H J,et al.Modeling time-dependent travel choice problems in road networks with multiple user classes and multiple parking facilities[J].Transportation Research Part B,2006,40(5):368-395.
[23] BROWN L,GANS N,MANDELBAUM A,et al.Statisticalanalysis of a telephone call center:A queueing-science perspective[J].Publications of the American Statistical Association,2005,100(469):36-50.
[24] MOVAGHAR A.On queueing with customer impatience untilthe beginning of service[J].Queueing System,1998,29(2):337-350.
[25] BARRER D Y.Queuing with impatient customers and ordered service[J].Operations Research,1957,5(5):650-656.
[26] DEFRAEYE M,VAN N I.Staffing and scheduling under nonstationary demand for service:A literature review[J].Omega,2016,58:4-25.
[27] SINGHAL K,SINGHAL J,KUMAR S.The value of the customer's waiting time for general queues[J].Decision Sciences,2018,50(3):567-581.
[28] DIVYA P,SEEMA H.Navigation based-intelligent parking manegement system using queuing theory and IOT[C]//2018 Second International Conference on Green Computing and Internet of Things.IEEE,2018:159-165.
[29] BO L,YI J P,HAO W,et al.MADM-based smart parking guidance algorithm[J].Plos One,2017,12(12):1-30.
[30] FUENTES A,HEASLIP K,DANTONIO A,et al.Evaluation of vehicle parking queueing in a national park:case study of the laurance S[J].Rockefeller Preserve in Grand Teton National Park.Transportation Research Record,2017,2654(1):1-10.
[31] PEL A J,CJANIOTAKIS E.Stochastic user equilibrium traffic assignment with equilibrated parking search routes[J].Transportation Research,2017,101(Jul.):123-139.
[32] HO C Y,YEONG G S,JEONG D Y.LoRa network based parking dispatching system:queuing theory and Q-learning approach journal of digital contents society[J].Journal of Digital Contents Society,2017,18(7):1443-1450.
[33] CHANG Y L,CHEN Z C,SUN C,et al.Urban parking flow assignment model based on G/G/c/FCFS queuing theory[J].Journal of Transportation Systems Engineering & Information Technology,2019,19(5):205-211.
[34] JOSEPH W.Queuing theory and modeling emergency depart-ment resource utilization[J].Emergency Medicine Clinics of North America,2020,38(3):563-572.
[35] WU K,ZHU X,ZHANG R,et al.Hospital Bed Planning in a Single Department Based on Monte Carlo Simulation and Queuing Theory[C]//IEEE International Conference on Industrial Engineering and Engineering Management (IEEM).IEEE,2020:644-648.
[36] CAYIRLI T,VERAL E.Outpatient scheduling in health care:A review of literature[J].Production & Operations Management,2009,12(4):519-549.
[37] GUPTA D,DENTA B.Appointment scheduling in health care:challenges and opportunities[J].IIE Transactions,2008,40(9):800-819.
[38] LI J,DONG M,ZHAO W.Admissions optimisation and premature discharge decisions in intensive care units[J].International Journal of Production Research,2015,53(23/24):7329-7342.
[39] GOLDWASSER R S,LOBO M S,ARRUDA E F,et al.Difficulties in access and estimates of public beds in intensive care units in the state of Rio de Janeiro[J].Revista De Saude Publica,2016,50(19):1-9.
[40] YADUVABSHI D,SHARMA A,MORE P V.Application ofqueuing theory to optimize waiting-time in hospital operations[J].Operations and Supply Chain Management An International Journal,2019,12(3):165-174.
[41] DIJK N M V,KORTBEEK N.Erlang loss bounds for OT-ICU systems[J].queueing systems,2009,63(1-4):253-280.
[42] GREE N,LINDA V.How many hospital beds?[J].Inquiry,2002,39(4):400-412.
[43] ACOSTA O,RUIZ P,RUEDA J,et al.Solving the negative impact of congestion in the postanesthesia care unit:a cost of opportunity analysis[J].Journal of Surgical Research,2017,210:86-91.
[44] MALLOR F,FERMIN J,AZCARATE C,et al.Control problems and management policies in health systems:application to intensive care units[J].Flexible Services & Manufacturing Journal,2016,28(1/2):62-89.
[45] ANDERSEN A R,NIELSEN B F,REINHARDDT L B.Optimization of hospital ward resources with patient relocation using markov chain modeling[J].European Journal of Operational Research,2017,260(3):1152-1163.
[46] LI X Y,LIU Y,KANG R,et al.Service reliability modeling and evaluation of active-active cloud data center based on the IT infrastructure[J].Microelectronics Reliability,2017,75:271-282.
[47] BALLA H,CHEN G S,JING W P.Cloud Biometric Authentication:An Integrated Reliability and Security Method Using the Reinforcement Learning Algorithm and Queue Theory[J].Journal of Universal Computer Science,2018,24(4):372-391.
[48] YANG Z X,LIU W,XU D.Study of cloud service queuing mo-del based on imbedding Markov chain perspective[J].Cluster Computing,2018,21(1):837-844.
[49] BALLA,HUSAMELDDIN A,CHEN G S,et al.Reliability Enhancement in Cloud Computing via Optimized Job Scheduling Implementing Reinforcement Learning Algorithm and Queuing Theory[C]//2018 1st International Conference on Data Intelligence and Security (ICDIS).2018:127-130.
[50] AKBARI E,CUNG F,PATEL H,et al.Incorporation of weighted linear prediction technique and M/M/1 queuing theory for improving energy efficiency of cloud computing datacenters[C]//2016 IEEE Long Island Systems,Applications and Technology Conference.IEEE,2016:1-5.
[51] QU C,CALHEIROS R N,BUYYA R.Auto-scaling web applications in clouds:A taxonomy and survey[J].ACM Computing Surveys,2016,51(4):1-33.
[52] SONG B,HASSANA M,ALAMRI A.A two-stage approach for task and resource management in multimedia cloud environment[J].Computing,2016,98(1/2):119-145.
[53] KAI Q X,PERROS H.SLA-based resource allocation in cluster computing systems[C]//2008 IEEE International Symposium on Parallel and Distributed Processing.IEEE,2008:1-12.
[54] GAWALI M B,SHINDE S K.Implementation of IDEA,BATS,ARIMA and queuing model for task scheduling in cloud computing[C]//Fifth International Conference on Eco-friendly Computing & Communication Systems.IEEE,2016:7-12.
[55] FENG G,GARG S,BUYYA R,et al.Revenue maximizationusing adaptive resource provisioning in cloud computing environments[C]//IEEE International Conference on Grid Computing.ACM,2012:192-200.
[56] TING Q H,LI J C,ZI Y D.Queuing-Oriented job optimizingscheduling in cloud mapreduce[C]// International Conference on P2P,Parallel,Grid,Cloud and Internet Computing.Springer International Publishing,2017:435-446.
[57] SHI J,DONG F,ZHANG J,et al.Resource provisioning optimization for service hosting on cloud platform[C]//IEEE 20th International Conference on Computer Supported Cooperative Work in Design.IEEE,2016:340-345.
[58] VAKILINIA,SHAHIN,CHERIET,et al.Preemptive cloud resource allocation modeling of processing jobs[J].Journal of Supercomputing,2018,74(5):2116-2150.
[59] KONORSKI J.Coordination of distributed user-defined resource sharing supportedby an intelligent communication network[C]//Private Switching Systems and Networks.IET,1992:138-143.
[60] SOOMANAT K,VATANAWOOD W.Formalism of stochastic queueing network using stochastic petri nets[C]//2018 19th IEEE/ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing (SNPD).IEEE,2018:347-351.
[61] GONG L,SUN X H,WATSON E F.Performance modeling and prediction of nondedicated network computing[J].IEEE Transactions on Computers,2002,51(9):1041-1055.
[62] SUGANYA R,JAYASHREE L S.Fuzzy rough set inspired rate adaptation and resource allocation using hidden markov model (FRSIRA-HMM) in mobile ad hoc networks[J].Cluster Computing,2019,22(S4):9875-9888.
[63] VANDY B,JOEL G,EMMANUEL J.On the Distribution of Sequential Jobs in Random Brokering for Heterogeneous Computational Grids[J].IEEE Press,2006,17(2):113-124.
[64] SIMHON E,STAROBINSKI D.On the impact of information disclosure on advance reservations:A game-theoretic view[J].European Journal of Operational Research,2018,267(3):1075-1088.
[65] NING N G,HONG J.A resource reservation algorithm with muti-parameters[C]//2011 Sixth Annual Chinagrid Confe-rence.2011:211-214.
[66] NGUYEN D N,ERYK D,MARWAN K.Harvesting short-lived white spaces via opportunistic traffic offloading between mobile service providers[J].IEEE Transactions on Cognitive Communications & Networking,2018,4(3):635-647.
[67] MANN C R,BALDWIN R O,KHAROUFED J P,et al.Aqueueing approach to optimal resource replication in wireless sensor networks[J].Performance Evaluation,2008,65(10):689-700.
[68] MA Y,HAN J J,TRIVEDI K S.Composite performance and availability analysis of communications networks:A comparison of exact and approximate approaches[C]//IEEE Global Telecommunications Conference.IEEE,2000:1771-1777.
[69] FALKNER M,DEVETSIKIOTIS M,FALKNER M.Minimum cost traffic shaping:a user's perspective on connection admission control[J].IEEE Communications Letters,1999,3(9):257-259.
[70] ZHOU J H,ZHI G H,ZHEN H L.Resource availability evaluation in service grid environment[C]//IEEE Asia-pacific Service Computing Conference.IEEE,2007:232-238.
[71] KAMALI S H,HEDAYATI M,IZADI A S,et al.The monitoring of the network traffic based on queuing theory and simulation in heterogeneous network environment[M]//2009 International Conference on Computer Technology and Development.Kota Kinabalu,Malaysia,2009:322-326.
[72] WANG J P,LI X M,JIAO C L.The network traffic management based on queuing theory[J].Applied Mechanics & Mate-rials,2011,121-126:4721-4747.
[1] 高诗尧, 陈燕俐, 许玉岚.
云环境下基于属性的多关键字可搜索加密方案
Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing
计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[2] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[3] 潘瑞杰, 王高才, 黄珩逸.
云计算下基于动态用户信任度的属性访问控制
Attribute Access Control Based on Dynamic User Trust in Cloud Computing
计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[4] 陈玉平, 刘波, 林伟伟, 程慧雯.
云边协同综述
Survey of Cloud-edge Collaboration
计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[5] 王文娟, 杜学绘, 任志宇, 单棣斌.
基于因果知识和时空关联的云平台攻击场景重构
Reconstruction of Cloud Platform Attack Scenario Based on Causal Knowledge and Temporal- Spatial Correlation
计算机科学, 2021, 48(2): 317-323. https://doi.org/10.11896/jsjkx.191200172
[6] 蒋慧敏, 蒋哲远.
企业云服务体系结构的参考模型与开发方法
Reference Model and Development Methodology for Enterprise Cloud Service Architecture
计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
[7] 毛瀚宇, 聂铁铮, 申德荣, 于戈, 徐石成, 何光宇.
区块链即服务平台关键技术及发展综述
Survey on Key Techniques and Development of Blockchain as a Service Platform
计算机科学, 2021, 48(11): 4-11. https://doi.org/10.11896/jsjkx.210500159
[8] 王勤, 魏立斐, 刘纪海, 张蕾.
基于云服务器辅助的多方隐私交集计算协议
Private Set Intersection Protocols Among Multi-party with Cloud Server Aided
计算机科学, 2021, 48(10): 301-307. https://doi.org/10.11896/jsjkx.210300308
[9] 雷阳, 姜瑛.
云计算环境下关联节点的异常判断
Anomaly Judgment of Directly Associated Nodes Under Cloud Computing Environment
计算机科学, 2021, 48(1): 295-300. https://doi.org/10.11896/jsjkx.191200186
[10] 徐蕴琪, 黄荷, 金钟.
容器技术在科学计算中的应用研究
Application Research on Container Technology in Scientific Computing
计算机科学, 2021, 48(1): 319-325. https://doi.org/10.11896/jsjkx.191100111
[11] 李彦, 申德荣, 聂铁铮, 寇月.
面向加密云数据的多关键字语义搜索方法
Multi-keyword Semantic Search Scheme for Encrypted Cloud Data
计算机科学, 2020, 47(9): 318-323. https://doi.org/10.11896/jsjkx.190800139
[12] 马潇潇, 黄艳.
大属性可公开追踪的密文策略属性基加密方案
Publicly Traceable Accountable Ciphertext Policy Attribute Based Encryption Scheme Supporting Large Universe
计算机科学, 2020, 47(6A): 420-423. https://doi.org/10.11896/JsJkx.190700131
[13] 金小敏, 滑文强.
移动云计算中面向能耗优化的资源管理
Energy Optimization Oriented Resource Management in Mobile Cloud Computing
计算机科学, 2020, 47(6): 247-251. https://doi.org/10.11896/jsjkx.190400020
[14] 孙敏, 陈中雄, 叶侨楠.
云环境下基于HEDSM的工作流调度策略
Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment
计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[15] 梁俊斌, 张敏, 蒋婵.
社交传感云安全研究进展
Research Progress of Social Sensor Cloud Security
计算机科学, 2020, 47(6): 276-283. https://doi.org/10.11896/jsjkx.190400116
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!