End-to-end delay analysis for networked systems

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

Networked system / End-to-end / Delay distribution

References

[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., , 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., , 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., , 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., , 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 minplus calculus for end-to-end statistical service guarantees. IEEE Trans. Inform. Theory, 52(9): 4105―4114. [

[10] Chakravorty, R., Katti, S., Crowcroft, J., , 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 multihop wireless networks. IEEE INFOCOM, p.2356―2364. [

[20] He, W., Liu, X., Zheng, L., , 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., , 2009. Enhancing realtime 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., , 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., , 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., , 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., , 2013. NetSimplex: controller fault tolerance architecture in networked control systems. IEEE Trans. Ind. Inform., 9(1): 346―356. [