网络系统的端到端延时分析

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 >

网络系统的端到端延时分析

计算机与自动化 | Updated：2022-06-06

- 网络系统的端到端延时分析
- End-to-end delay analysis for networked systems
- 信息与电子工程前沿（英文） 2015年16卷第9期页码：732-743
- 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：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61273079 and 61502352), the Key Laboratory of Wireless Sensor Network & Communication of Chinese Academy of Sciences (No. WSNC2014001), the Open Research Project of the State Key Lab of Industrial Control Technology, Zhejiang University (Nos. ICT1541 and ICT1555), the Natural Science Foundation of Hubei Province, China (No. 2015CFB203), and the Natural Science Foundation of Jiangsu Province, China (No. BK20150383)
- DOI：10.1631/FITEE.1400414
  中图分类号： TP393
- 收稿：2014-12-04，
  
  修回：2015-08-06，
  
  纸质出版：2015-09
- Accepted：
Scan QR Code
网络系统的端到端延时分析[J]. 信息与电子工程前沿（英文）, 2015,16(9):732-743.

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.
网络系统的端到端延时分析[J]. 信息与电子工程前沿（英文）, 2015,16(9):732-743. DOI： 10.1631/FITEE.1400414.

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 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Large investment model

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