Full Text:   <871>

Summary:  <382>

CLC number: TP393

On-line Access: 2015-09-06

Received: 2014-12-04

Revision Accepted: 2015-07-18

Crosschecked: 2015-08-06

Cited: 1

Clicked: 2098

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Jie Shen

http://orcid.org/0000-0003-4391-813X

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2015 Vol.16 No.9 P.732-743

http://doi.org/10.1631/FITEE.1400414


End-to-end delay analysis for networked systems


Author(s):  Jie Shen, Wen-bo He, Xue Liu, Zhi-bo Wang, Zhi Wang, Jian-guo Yao

Affiliation(s):  Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   jshen@iipc.zju.edu.cn, wangzhi@iipc.zju.edu.cn

Key Words:  Networked system, End-to-end, Delay distribution


Jie Shen, Wen-bo He, Xue Liu, Zhi-bo Wang, Zhi Wang, Jian-guo Yao. End-to-end delay analysis for networked systems[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(9): 732-743.

@article{title="End-to-end delay analysis for networked systems",
author="Jie Shen, Wen-bo He, Xue Liu, Zhi-bo Wang, Zhi Wang, Jian-guo Yao",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="16",
number="9",
pages="732-743",
year="2015",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1400414"
}

%0 Journal Article
%T End-to-end delay analysis for networked systems
%A Jie Shen
%A Wen-bo He
%A Xue Liu
%A Zhi-bo Wang
%A Zhi Wang
%A Jian-guo Yao
%J Frontiers of Information Technology & Electronic Engineering
%V 16
%N 9
%P 732-743
%@ 2095-9184
%D 2015
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1400414

TY - JOUR
T1 - End-to-end delay analysis for networked systems
A1 - Jie Shen
A1 - Wen-bo He
A1 - Xue Liu
A1 - Zhi-bo Wang
A1 - Zhi Wang
A1 - Jian-guo Yao
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 16
IS - 9
SP - 732
EP - 743
%@ 2095-9184
Y1 - 2015
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1400414


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.

In this paper, the authors proposed a novel theoretical framework to analyzed end-to-end delay distributions. This paper deals with the very interesting and important issue on large-scale networked systems. By analyzing the end-to-end delay, large-scale networked systems can be improved by improving the delay distribution of bottleneck link. Overall, this paper is well organized and well written.

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

目的:面向大规模复杂网络,提出一种有效的端到端延时的分析方法,保障网络服务性能。
创新点:基于频域分析方法提出一种新的网络延时分析方法,具有高效率的特点。
方法:首先,将网络系统的延时从时域转换到频域,并用信号流图建模(图1)。然后,用克莱姆法则或者梅森增益公式计算信号流图模型的传递函数。接着,分析传递函数的脉冲响应和阶跃响应得到系统的端到端延时的概率密度函数和概率分布函数(图2)。最后,用该方法分析两个实际例子。包括:第一,用该方法得到网络中的瓶颈链路(图3、4);第二,用该方法分析网络通信协议(图6)。
结论:针对大规模复杂网络,提出基于频域分析的网络延时分析方法,这种方法是有效的。

关键词:网络系统;端到端;延时分布

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Abdelzaher, T.F., Prabh, S., Kiran, R., 2004. On real-time capacity limits of multihop wireless sensor networks. Proc. 25th IEEE Int. Real-Time Systems Symp., p.359-370.

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

[3]Bakshi, B.S., Krishna, P., Vaidya, N.H., et al., 1997. Improving performance of TCP over wireless networks. Proc. 17th Int. Conf. on Distributed Computing Systems, p.365-373.

[4]Balakrishnan, H., Padmanabhan, V.N., Seshan, S., et al., 1997. A comparison of mechanisms for improving TCP performance over wireless links. IEEE/ACM Trans. Netw., 5(6):756-769.

[5]Bauer, H., Scharbarg, J., Fraboul, C., 2010. Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach. IEEE Trans. Ind. Inform., 6(4):521-533.

[6]Bisnik, N., Abouzeid, A.A., 2009. Queuing network models for delay analysis of multihop wireless ad hoc networks. Ad Hoc Netw., 7(1):79-97.

[7]Bolot, J.C., 1993. End-to-end packet delay and loss behavior in the Internet. ACM SIGCOMM Comput. Commun. Rev., 23(4):289-298.

[8]Boorstyn, R.R., Burchard, A., Liebeherr, J., et al., 2000. Statistical service assurances for traffic scheduling algorithms. IEEE J. Sel. Areas Commun., 18(12):2651-2664.

[9]Burchard, A., Liebeherr, J., Patek, S.D., 2006. A min-plus calculus for end-to-end statistical service guarantees. IEEE Trans. Inform. Theory, 52(9):4105-4114.

[10]Chakravorty, R., Katti, S., Crowcroft, J., et al., 2003. Flow aggregation for enhanced TCP over wide-area wireless. Proc. 22nd Annual Joint Conf. of the IEEE Computer and Communications, p.1754-1764.

[11]Choe, J., Shroff, N.B., 1998. A central-limit-theorem-based approach for analyzing queue behavior in high-speed networks. IEEE/ACM Trans. Netw., 6(5):659-671.

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

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

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

[15]Despaux, F., Song, Y.Q., Lahmadi, A., 2012. 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, p.317-322.

[16]El-Hajj, A., Kabalan, K.Y., 1995. A transfer function computational algorithm for linear control systems. IEEE Contr. Syst., 15(2):114-118.

[17]Exel, R., Bigler, T., Sauter, T., 2014. Asymmetry mitigation in IEEE 802.3 Ethernet for high-accuracy clock synchronization. IEEE Trans. Instrum. Meas., 63(3):729-736.

[18]Fidler, M., 2010. Survey of deterministic and stochastic service curve models in the network calculus. IEEE Commun. Surv. Tutor., 12(1):59-86.

[19]Gupta, G.R., Shroff, N., 2009. Delay analysis for multi-hop wireless networks. IEEE INFOCOM, p.2356-2364.

[20]He, W., Liu, X., Zheng, L., et al., 2010. Reliability calculus: a theoretical framework to analyze communication reliability. Proc. IEEE 30th Int. Conf. on Distributed Computing Systems, p.159-168.

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

[22]Koubaa, A., Alves, M., Tovar, E., 2006. Modeling and worst-case dimensioning of cluster-tree wireless sensor networks. Proc. 27th IEEE Int. Real-Time Systems Symp., p.412-421.

[23]Li, Y., Chen, C.S., Song, Y.Q., et al., 2009. Enhancing real-time delivery in wireless sensor networks with two-hop information. IEEE Trans. Ind. Inform., 5(2):113-122.

[24]Paxson, V., 1997. End-to-end Internet packet dynamics. ACM SIGCOMM Comput. Commun. Rev., 27(4):139-152.

[25]Qiu, J.Y., Knightly, E.W., 1999. Inter-class resource sharing using statistical service envelopes. Proc. 18th Annual Joint Conf. of the IEEE Computer and Communications Societies, p.1404-1411.

[26]Rao, L., Liu, X., Xie, L., et al., 2010. Minimizing electricity cost: optimization of distributed Internet data centers in a multi-electricity-market environment. Proc. IEEE INFOCOM, p.1-9.

[27]Reisslein, M., Ross, K.W., Rajagopal, S., 2002. A framework for guaranteeing statistical QoS. IEEE/ACM Trans. Netw., 10(1):27-42.

[28]Schmitt, J.B., Zdarsky, F.A., Thiele, L., 2007. A comprehensive worst-case calculus for wireless sensor networks with in-network processing. Proc. 28th IEEE Int. Real-Time Systems Symp., p.193-202.

[29]Wang, Z., Liao, J., Cao, Q., et al., 2014. Achieving k-barrier coverage in hybrid directional sensor networks. IEEE Trans. Mob. Comput., 13(7):1443-1455.

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

[31]Xie, M., Haenggi, M., 2009. Towards an end-to-end delay analysis of wireless multihop networks. Ad Hoc Netw., 7(5):849-861.

[32]Yao, J., Liu, X., Zhu, G., et al., 2013. NetSimplex: controller fault tolerance architecture in networked control systems. IEEE Trans. Ind. Inform., 9(1):346-356.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE