End-to-end delay analysis for networked systems

SHEN Jie; HE Wen-bo; LIU Xue; WANG Zhi-bo; WANG Zhi; YAO Jian-guo

doi:10.1631/FITEE.1400414

Your Location：

Home >

Browse articles >

End-to-end delay analysis for networked systems

Computer & Automation | Updated：2022-06-06

- End-to-end delay analysis for networked systems
- 网络系统的端到端延时分析
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 9, Pages: 732-743(2015)
- Affiliations：
  
  1.Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China
  2.School of Computer Science, McGill University, Montreal H3A0E9, Canada
  3.School of Computer, Wuhan University, Wuhan 430072, China
  4.Su zhou Institute of Wuhan University, Suzhou 215000, China
  5.School of Software, Shanghai Jiao Tong University, Shanghai 200240, China
- Author bio：
  
  [ "Jie SHEN, E-mail: jshen@iipc.zju.edu.cn" ]
  Zhi WANG, E-mail: wangzhi@iipc.zju.edu.cn
- Funds：
- DOI：10.1631/FITEE.1400414
  CLC： TP393
- Received：04 December 2014，
  
  Revised：2015-08-06，
  
  Published：2015-09
- Accepted：
Scan QR Code
SHEN Jie, HE Wen-bo, LIU Xue, et al. End-to-end delay analysis for networked systems[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(9): 732-743.
DOI：

SHEN Jie, HE Wen-bo, LIU Xue, et al. End-to-end delay analysis for networked systems[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(9): 732-743. DOI： 10.1631/FITEE.1400414.

摘要

目的

面向大规模复杂网络，提出一种有效的端到端延时的分析方法，保障网络服务性能。

创新点

基于频域分析方法提出一种新的网络延时分析方法，具有高效率的特点。

方法

首先，将网络系统的延时从时域转换到频域，并用信号流图建模（图1）。然后，用克莱姆法则或者梅森增益公式计算信号流图模型的传递函数。接着，分析传递函数的脉冲响应和阶跃响应得到系统的端到端延时的概率密度函数和概率分布函数（图2）。最后，用该方法分析两个实际例子。包括：第一，用该方法得到网络中的瓶颈链路（图3、4）；第二，用该方法分析网络通信协议（图6）。

结论

针对大规模复杂网络，提出基于频域分析的网络延时分析方法，这种方法是有效的。

Abstract

End-to-end delay measurement has been an essential element in the deployment of real-time services in networked systems. Traditional methods of delay measurement based on time domain analysis

however

are not efficient as the network scale and the complexity increase. We propose a novel theoretical framework to analyze the end-to-end delay distributions of networked systems from the frequency domain. We use a signal flow graph to model the delay distribution of a networked system and prove that the end-to-end delay distribution is indeed the inverse Laplace transform of the transfer function of the signal flow graph. Two efficient methods

Cramer's rule-based method and the Mason gain rule-based method

are adopted to obtain the transfer function. By analyzing the time responses of the transfer function

we obtain the end-to-end delay distribution. Based on our framework

we propose an efficient method using the dominant poles of the transfer function to work out the bottleneck links of the network. Moreover

we use the framework to study the network protocol performance. Theoretical analysis and extensive evaluations show the effectiveness of the proposed approach.

关键词

Keywords

references

T.F. Abdelzaher , S. Prabh , R. Kiran . On real-time capacity limits of multihop wireless sensor networks . Proc. 25th IEEE Int. Real-Time Systems Symp. , 2004 . p.359 - 370 . DOI: 10.1109/REAL.2004.37 http://doi.org/10.1109/REAL.2004.37 .

L. Almeida , P. Fonseca , J.A. Fonseca , 等 . Scheduling and clock synchronization in CAN-based distributed systems . Proc. Int. CAN Conf. , 1999 . p.1 - 9 . .

B.S. Bakshi , P. Krishna , N.H. Vaidya , 等 . Improving performance of TCP over wireless networks . Proc. 17th Int. Conf. on Distributed Computing Systems , 1997 . p.365 - 373 . DOI: 10.1109/ICDCS.1997.598070 http://doi.org/10.1109/ICDCS.1997.598070 .

H. Balakrishnan , V.N. Padmanabhan , S. Seshan , 等 . A comparison of mechanisms for improving TCP performance over wireless links . IEEE/ACM Trans. Netw. , 1997 . 5 ( 6 ): 756 - 769 . DOI: 10.1109/90.650137 http://doi.org/10.1109/90.650137 .

H. Bauer , J. Scharbarg , C. Fraboul . Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach . IEEE Trans. Ind. Inform. , 2010 . 6 ( 4 ): 521 - 533 . DOI: 10.1109/TII.2010.2055877 http://doi.org/10.1109/TII.2010.2055877 .

N. Bisnik , A.A. Abouzeid . Queuing network models for delay analysis of multihop wireless ad hoc networks . Ad Hoc Netw. , 2009 . 7 ( 1 ): 79 - 97 . DOI: 10.1016/j.adhoc.2007.12.001 http://doi.org/10.1016/j.adhoc.2007.12.001 .

J.C. Bolot . End-to-end packet delay and loss behavior in the Internet . ACM SIGCOMM Comput. Commun. Rev. , 1993 . 23 ( 4 ): 289 - 298 . DOI: 10.1145/167954.166265 http://doi.org/10.1145/167954.166265 .

R.R. Boorstyn , A. Burchard , J. Liebeherr , 等 . Statistical service assurances for traffic scheduling algorithms . IEEE J. Sel. Areas Commun. , 2000 . 18 ( 12 ): 2651 - 2664 . DOI: 10.1109/49.898747 http://doi.org/10.1109/49.898747 .

A. Burchard , J. Liebeherr , S.D. Patek . A minplus calculus for end-to-end statistical service guarantees . IEEE Trans. Inform. Theory , 2006 . 52 ( 9 ): 4105 - 4114 . DOI: 10.1109/TIT.2006.880019 http://doi.org/10.1109/TIT.2006.880019 .

R. Chakravorty , S. Katti , J. Crowcroft , 等 . Flow aggregation for enhanced TCP over wide-area wireless . Proc. 22nd Annual Joint Conf. of the IEEE Computer and Communications , 2003 . p.1754 - 1764 . DOI: 10.1109/INFCOM.2003.1209198 http://doi.org/10.1109/INFCOM.2003.1209198 .

J. Choe , N.B. Shroff . A central-limit-theorem-based approach for analyzing queue behavior in high-speed networks . IEEE/ACM Trans. Netw. , 1998 . 6 ( 5 ): 659 - 671 . DOI: 10.1109/90.731205 http://doi.org/10.1109/90.731205 .

R.L. Cruz . A calculus for network delay, part Ⅰ:network elements in isolation . IEEE Trans. Inform. Theory , 1991a . 37 ( 1 ): 114 - 131 . .

R.L. Cruz . A calculus for network delay, part Ⅱ:network analysis . IEEE Trans. Inform. Theory , 1991b . 37 ( 1 ): 132 - 141 . .

J. D'Azzo , C. Houpis . Linear Control System Analysis and Design:Conventional and Modern . McGraw-Hill Higher Education, USA , 1995 .

F. Despaux , Y.Q. Song , A. Lahmadi . Combining analytical and simulation approaches for estimating end-to-end delay in multi-hop wireless networks . Proc. IEEE 8th Int. Conf. on Distributed Computing in Sensor Systems , 2012 . p.317 - 322 . DOI: 10.1109/DCOSS.2012.31 http://doi.org/10.1109/DCOSS.2012.31 .

A. El-Hajj , K.Y. Kabalan . A transfer function computational algorithm for linear control systems . IEEE Contr. Syst. , 1995 . 15 ( 2 ): 114 - 118 . DOI: 10.1109/37.375319 http://doi.org/10.1109/37.375319 .

R. Exel , T. Bigler , T. Sauter . Asymmetry mitigation in IEEE 802 . 3 Ethernet for high-accuracy clock synchronization. IEEE Trans. Instrum. Meas. , 2014 . 63 ( 3 ): 729 - 736 . DOI: 10.1109/TIM.2013.2280489 http://doi.org/10.1109/TIM.2013.2280489 .

M. Fidler . Survey of deterministic and stochastic service curve models in the network calculus . IEEE Commun. Surv. Tutor. , 2010 . 12 ( 1 ): 59 - 86 . DOI: 10.1109/SURV.2010.020110.00019 http://doi.org/10.1109/SURV.2010.020110.00019 .

G.R. Gupta , N. Shroff . Delay analysis for multihop wireless networks . IEEE INFOCOM , 2009 . p.2356 - 2364 . DOI: 10.1109/INFCOM.2009.5062162 http://doi.org/10.1109/INFCOM.2009.5062162 .

W. He , X. Liu , L. Zheng , 等 . Reliability calculus:a theoretical framework to analyze communication reliability . Proc. IEEE 30th Int. Conf. on Distributed Computing Systems , 2010 . p.159 - 168 . DOI: 10.1109/ICDCS.2010.73 http://doi.org/10.1109/ICDCS.2010.73 .

S. Heimlicher , P. Nuggehalli , M. May . End-to-end vs . hop-by-hop transport. SIGMETRICS Perform. Eval. Rev. , 2007 . 35 ( 3 ): 59 - 60 . .

A. Koubaa , M. Alves , E. Tovar . Modeling and worst-case dimensioning of cluster-tree wireless sensor networks . Proc. 27th IEEE Int. Real-Time Systems Symp. , 2006 . p.412 - 421 . DOI: 10.1109/RTSS.2006.29 http://doi.org/10.1109/RTSS.2006.29 .

Y. Li , C.S. Chen , Y.Q. Song , 等 . Enhancing realtime delivery in wireless sensor networks with two-hop information . IEEE Trans. Ind. Inform. , 2009 . 5 ( 2 ): 113 - 122 . DOI: 10.1109/TII.2009.2017938 http://doi.org/10.1109/TII.2009.2017938 .

V. Paxson . End-to-end Internet packet dynamics . ACM SIGCOMM Comput. Commun. Rev. , 1997 . 27 ( 4 ): 139 - 152 . DOI: 10.1145/263109.263155 http://doi.org/10.1145/263109.263155 .

J.Y. Qiu , E.W. Knightly . Inter-class resource sharing using statistical service envelopes . Proc. 18th Annual Joint Conf. of the IEEE Computer and Communications Societies , 1999 . p.1404 - 1411 . DOI: 10.1109/INFCOM.1999.752160 http://doi.org/10.1109/INFCOM.1999.752160 .

L. Rao , X. Liu , L. Xie , 等 . Minimizing electricity cost:optimization of distributed Internet data centers in a multi-electricity-market environment . Proc. IEEE INFOCOM , 2010 . p.1 - 9 . DOI: 10.1109/INFCOM.2010.5461933 http://doi.org/10.1109/INFCOM.2010.5461933 .

M. Reisslein , K.W. Ross , S. Rajagopal . A framework for guaranteeing statistical QoS . IEEE/ACM Trans. Netw. , 2002 . 10 ( 1 ): 27 - 42 . DOI: 10.1109/90.986511 http://doi.org/10.1109/90.986511 .

J.B. Schmitt , F.A. Zdarsky , L. Thiele . A comprehensive worst-case calculus for wireless sensor networks with in-network processing . Proc. 28th IEEE Int. Real-Time Systems Symp. , 2007 . p.193 - 202 . DOI: 10.1109/RTSS.2007.17 http://doi.org/10.1109/RTSS.2007.17 .

Z. Wang , J. Liao , Q. Cao , 等 . Achieving k-barrier coverage in hybrid directional sensor networks . IEEE Trans. Mob. Comput. , 2014 . 13 ( 7 ): 1443 - 1455 . DOI: 10.1109/TMC.2013.118 http://doi.org/10.1109/TMC.2013.118 .

F. Xia , A. Vinel , R. Gao , 等 . Evaluating IEEE 802.15.4 for cyber-physical systems . EURASIP J. Wirel. Commun. Netw., arXiv:1312.6837 , 2011 .

M. Xie , M. Haenggi . Towards an end-to-end delay analysis of wireless multihop networks . Ad Hoc Netw. , 2009 . 7 ( 5 ): 849 - 861 . DOI: 10.1016/j.adhoc.2008.04.010 http://doi.org/10.1016/j.adhoc.2008.04.010 .

J. Yao , X. Liu , G. Zhu , 等 . NetSimplex:controller fault tolerance architecture in networked control systems . IEEE Trans. Ind. Inform. , 2013 . 9 ( 1 ): 346 - 356 . DOI: 10.1109/TII.2012.2219060 http://doi.org/10.1109/TII.2012.2219060 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Large investment model

Efficient decoding self-attention for end-to-end speech synthesis

Related Author

Jian GUO

Heung-Yeung SHUM

Wei ZHAO

Li XU

Related Institution

IDEA Research, International Digital Economy Academy

College of Electrical Engineering, Zhejiang University

Institute of Robotics, Zhejiang University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰