Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (11): 286-293.doi: 10.11896/jsjkx.191200072

• Computer Network • Previous Articles     Next Articles

Network Service Tail Latency Analysis Based on M/M/1 Queuing Model

GUO Zi-ting1,2, ZHANG Wen-li 1, CHEN Ming-yu1,2,3   

  1. 1 State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China
    2 University of Chinese Academy of Sciences,Beijing 100049,China
    3 Peng Cheng Laboratory,Shenzhen,Guangdong 518055,China
  • Received:2019-12-12 Revised:2020-04-05 Online:2020-11-15 Published:2020-11-05
  • About author:GUO Zi-ting,born in 1995,postgra-duate.Her main research interests include data center networks and so on.
    ZHANG Wen-li,born in 1980,Ph.D,is a senior member of China Computer Federation.Her main research interests include architecture and algorithm optimization for high end computers and datacenter networks.
  • Supported by:
    This work was supported by the National Key Research and Development Program of China (13th Five-Year Plan) (2017YFB1001602).

PDF (PC)

1960

Abstract: Studies have shown that in large-scale network service systems,network latency often exhibits a long tail effect,i.e.,a certain percentage of latency are much larger than the average latency of the network service systems.The long tail of latency has caused widespread concern,and can seriously affect user experience and content provider revenue,especially in large interactive network applications that are sensitive to latency.Therefore,the focus of network service system research has experienced a change from focusing on throughput and average latency to the tail latency of the system of interest.However,most of the exi-sting theoretical models focus on average latency,and it is difficult to analyze the tail characteristics of the network service latency.Due to the complexity of existing research,stay time calculations in complex network services lack formal modeling and computational methods.This paper proposes a method of abstracting a complex network into a queuing model.Based on the model,the expressions of stay time distribution in series and parallel scenes are given,and at the same time,the influence of the tail latency on the change of individual sub-components in the model is analyzed.The predicted results of the model analysis are compared with the results of the simulation network,the error does not exceed 2%.

Key words: M/M/1, Modeling, Parallel, Series, Tail latency

CLC Number: 

  • TP391
[1] DEAN J,BARROSO L A.The tail at scale[J].Communications of the Acm,2013,56(2):74-80.
[2] JALAPARTI V,BODIK P,KANDULA S,et al.Speeding up distributed request-response workflows[J].ACM SIGCOMM Computer Communication Review,2013,43(4):219-230.
[3] DECANDIA G,HASTORUN D,JAMPANI M,et al.Dynamo:amazon's highly available key-value store[J].ACM SIGOPS Operating Systems Review,2007,41(6):205-220.
[4] HE Y,ELNIKETY S,LARUS J,et al.Zeta:Scheduling interactive services with partial execution[C]//Proceedings of the Third ACM Symposium on Cloud Computing.2012:1-14.
[5] YI J,MAGHOUL F,PEDERSEN J.Deciphering mobile search patterns:a study of yahoo! mobile search queries[C]//Procee-dings of the 17th International Conference on World Wide Web.2008:257-266.
[6] XU Y,MUSGRAVE Z,NOBLE B,et al.Bobtail:Avoiding Long Tails in the Cloud[C]//Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation.USENIX Association,2013:329-342.
[7] NISHTALA R,FUGAL H,GRIMM S,et al.Scaling Memcache at Facebook[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2013:385-398.
[8] BARROSO L A,DEAN J,HOLZLE U.Web search for a pla-net:The Google cluster architecture[J].IEEE Micro,2003,23(2):22-28.
[9] SURESH L,CANINI M,SCHMID S,et al.C3:Cutting tail latency in cloud data stores via adaptive replica selection[C]//12th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 15).2015:513-527.
[10] DELIMITROU C,KOZYRAKIS C.Amdahl's law for tail latency[J].Communications of the ACM,2018,61(8):65-72.
[11] ALESAWI S,NGUYEN M,CHE H,et al.Tail Latency Prediction for Datacenter Applications in Consolidated Environments[C]//2019 International Conference on Computing,Networking and Communications (ICNC).IEEE,2019:265-269.
[12] MIRHOSSEINI A,WENISCH T F.The queuing-first approach for tail management of interactive services[J].IEEE Micro,2019,39(4):55-64.
[13] LUMB C R,GANGER G R,GOLDING R.D-SPTF:Decentra-lized Request Distribution in Brick-based Storage (CMU-CS-03-202)[J].Acm Sigops Operating Systems Review,2004,39(11):37-47.
[14] VULIMIRI A,GODFREY P B,MITTAL R,et al.Low latency via redundancy[C]//Acm Conference on Emerging Networking Experiments & Technologies.ACM,2013.
[15] WU Z,YU C,MADHYASTHA H V.CosTLO:Cost-Effective Redundancy for Lower Latency Variance on Cloud Storage Services[C]//Usenix Conference on Networked Systems Design & Implementation.USENIX Association,2015.
[16] LI J,SHARMA N K,PORTS D R K,et al.Tales of the tail:Hardware,os,and application-level sources of tail latency[C]//Proceedings of the ACM Symposium on Cloud Computing.ACM,2014:1-14.
[17] JACKSON J R.Networks of waiting lines[J].OPER.RES.,1957,5(4):518-521.
[18] NGUYEN M,LI Z,DUAN F,et al.The tail at scale:how to predict it?[C]//Usenix Conference on Hot Topics in Cloud Computing.USENIX Association,2016.
[19] THOMASIAN A.Analysis of fork/join and related queueing systems[J].ACM Computing Surveys (CSUR),2014,47(2):1-71.
[20] NELSON R,TANTAWI A N.Approximate analysis of fork/join synchronization in parallel queues[J].IEEE transactions on computers,1988,37(6):739-743.
[21] CHEN R J.A hybrid solution of fork/join synchronization inparallel queues[J].IEEE Transactions on Parallel and Distributed Systems,2001,12(8):829-845.
[22] BALSAMO S,DONATIELLO L,VAN DIJK N M.Bound performance models of heterogeneous parallel processing systems[J].IEEE transactions on parallel and distributed systems,1998,9(10):1041-1056.
[23] CHEN R J.An upper bound solution for homogeneous fork/join queuing systems[J].IEEE Transactions on Parallel and Distributed Systems,2010,22(5):874-878.
[24] RIZK A,POLOCZEK F,CIUCU F.Computable bounds in fork-join queueing systems[C]//Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Mo-deling of Computer Systems.2015:335-346.
[25] NGUYEN M,ALESAWI S,LI N,et al.Forktail:a black-box fork-join tail latency prediction model for user-facing datacenter workloads[C]//Proceedings of the 27th International Sympo-sium on High-Performance Parallel and Distributed Computing.2018:206-217.
[26] QIU Z,PÉREZ J F,HARRISON P G.Beyond the mean in fork-join queues:Efficient approximation for response-time tails[J].Performance Evaluation,2015,91:99-116.
[1] WANG Zi-kai, ZHU Jian, ZHANG Bo-jun, HU Kai. Research and Implementation of Parallel Method in Blockchain and Smart Contract [J]. Computer Science, 2022, 49(9): 312-317.
[2] WEI Kai-xuan, FU Ying. Re-parameterized Multi-scale Fusion Network for Efficient Extreme Low-light Raw Denoising [J]. Computer Science, 2022, 49(8): 120-126.
[3] GAO Zhen-zhuo, WANG Zhi-hai, LIU Hai-yang. Random Shapelet Forest Algorithm Embedded with Canonical Time Series Features [J]. Computer Science, 2022, 49(7): 40-49.
[4] ZONG Di-di, XIE Yi-wu. Model Medial Axis Generation Method Based on Normal Iteration [J]. Computer Science, 2022, 49(6A): 764-770.
[5] LIU Bao-bao, YANG Jing-jing, TAO Lu, WANG He-ying. Study on Prediction of Educational Statistical Data Based on DE-LSTM Model [J]. Computer Science, 2022, 49(6A): 261-266.
[6] TAO Li-jing, QIU Han, ZHU Jun-hu, LI Hang-tian. Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment [J]. Computer Science, 2022, 49(6A): 480-484.
[7] LUO Jun-ren, ZHANG Wan-peng, LU Li-na, CHEN Jing. Survey on Online Adversarial Planning for Real-time Strategy Game [J]. Computer Science, 2022, 49(6): 287-296.
[8] CHEN Xin, LI Fang, DING Hai-xin, SUN Wei-ze, LIU Xin, CHEN De-xun, YE Yue-jin, HE Xiang. Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture [J]. Computer Science, 2022, 49(6): 99-107.
[9] CAI Xin-yu, FENG Xiang, YU Hui-qun. Adaptive Weight Based Broad Learning Algorithm for Cascaded Enhanced Nodes [J]. Computer Science, 2022, 49(6): 134-141.
[10] WANG Qi, WANG Gang-qiao, CHEN Yong-qiang, LIU Yi. Integrated Modeling Method and Application System for Social Computing [J]. Computer Science, 2022, 49(4): 25-29.
[11] SHEN Shao-peng, MA Hong-jiang, ZHANG Zhi-heng, ZHOU Xiang-bing, ZHU Chun-man, WEN Zuo-cheng. Three-way Drift Detection for State Transition Pattern on Multivariate Time Series [J]. Computer Science, 2022, 49(4): 144-151.
[12] LIU Jiang, LIU Wen-bo, ZHANG Ju. Hybrid MPI+OpenMP Parallel Method on Polyhedral Grid Generation in OpenFoam [J]. Computer Science, 2022, 49(3): 3-10.
[13] GAO Yan-lu, XU Yuan, ZHU Qun-xiong. Predicting Electric Energy Consumption Using Sandwich Structure of Attention in Double -LSTM [J]. Computer Science, 2022, 49(3): 269-275.
[14] ZHAO Geng, SONG Xin-yu, MA Ying-jie. Secure Data Link of Unmanned Aerial Vehicle Based on Chaotic Sub-carrier Modulation [J]. Computer Science, 2022, 49(3): 322-328.
[15] LI Jia-zhen, JI Qing-ge. Dynamic Low-sampling Ambient Occlusion Real-time Ray Tracing for Molecular Rendering [J]. Computer Science, 2022, 49(1): 175-180.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.