On applying stochastic network calculus

doi:10.1007/s11704-013-3095-1

Front Comput Sci

2013, Vol. 7

Issue (6) : 924-942 https://doi.org/10.1007/s11704-013-3095-1

REVIEW ARTICLE

On applying stochastic network calculus

Chuang LIN¹(

), Yiping DENG²(

), Yuming JIANG³(

)

1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China; 2. China Electric Equipment and Systems Engineering Ltd., Beijing 100084, China; 3. Department of Telematics, Norwegian University of Science and Technology, Trondheim NO-7491, Norway

Download: PDF(473 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Performance evaluation plays a crucial role in the design of network systems. Many theoretical tools, including queueing theory, effective bandwidth and network calculus, have been proposed to provide modeling mechanisms and results. While these theories have been widely adopted for performance evaluation, each has its own limitation. With that network systems have become more complex and harder to describe, where a lot of uncertainty and randomness exists, to make performance evaluation of such systems tractable, some compromise is often necessary and helpful. Stochastic network calculus (SNC) is such a theoretical tool. While SNC is a relatively new theory, it is gaining increasing interest and popularity. In the current SNC literature, much attention has been paid on the development of the theory itself. In addition, researchers have also started applying SNC to performance analysis of various types of systems in recent years. The aim of this paper is to provide a tutorial on the new theoretical tool. Specifically, various SNC traffic models and SNC server models are reviewed. The focus is on how to apply SNC, for which, four critical steps are formalized and discussed. In addition, a list of SNC application topics/areas, where there may exist huge research potential, is presented.

Keywords stochastic network calculus bound performance arrival curve service curve

Corresponding Author(s): LIN Chuang,Email:chlin@tsinghua.edu.cn; DENG Yiping,Email:dyp2003@gmail.com; JIANG Yuming,Email:jiang@item.ntnu.no

Issue Date: 01 December 2013

Cite this article:

Chuang LIN,Yiping DENG,Yuming JIANG. On applying stochastic network calculus[J]. Front Comput Sci, 2013, 7(6): 924-942.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-3095-1
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I6/924

1	Cruz R. A calculus for network delay, Part i: network elements in isolation. IEEE Transactions on Information Theory , 1991, 37(1): 114-121 doi: 10.1109/18.61109
2	Cruz R. A calculus for network delay, Part ii: network analysis. IEEE Transactions on Information Theory , 1991, 37(1): 132-141 doi: 10.1109/18.61110
3	Chang C. Performance Guarantees in Communication Networks. Springer Verlag , 2000 doi: 10.1007/978-1-4471-0459-9
4	Le Boudec J, Thiran P. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer Verlag , 2001
5	Jiang Y, Liu Y. Stochastic Network Calculus. Springer , March 2008
6	Mao S, Panwar S. A survey of envelope processes and their applications in quality of service provisioning. IEEE Communications Sur veys and Tutorials , 2006, 8(3): 2-20 doi: 10.1109/COMST.2006.253272
7	Fidler M. A survey of deterministic and stochastic service curve models in the network calculus. IEEE Communications Surveys and Tutorials , 2010, 12(1): 59-86 doi: 10.1109/SURV.2010.020110.00019
8	Jiang Y. Stochastic network calculus for performance analysis of internet networks: an overview and outlook. In: Proceedings of the 2012 International Conference on Computing, Networking and Communications (ICNC) . 2012, 638-644 doi: 10.1109/ICCNC.2012.6167501
9	Erlang A K. The theory of probabilities and telephone conversations. Nyt Tidsskrift for Matematik , 1909, 20: 33-39
10	Erlang A K. Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. Elektrotkeknikeren , 1917, 13: 5-13
11	Jackson J. Networks of waiting lines. Operations Research , 1957, 5: 518-521 doi: 10.1287/opre.5.4.518
12	Brockemeyer E. The life and works of A K Erlang. Copenhagen Telephone , 1948
13	Bertsekas D, Gallager R. Data Networks. Prentice Hall , 1992
14	Kleinrock L. Communications Nets: Stochastic Message Flow and Delay. McGrawHill, Inc. , 1964
15	Hui J. Resource allocation for broadband networks. IEEE Journal of Selected Areas in Communications , 1988, 6(9): 1598-1608 doi: 10.1109/49.12887
16	Gibbens R, Hunt P. Effective bandwidths for the multi-type uas channel. Queueing Systems , 1991, 9(1): 17-28 doi: 10.1007/BF01158790
17	Kelly F. Notes on effective bandwidths. Stochastic Networks: Theory and Applications , 1996, 141-168
18	Roberts L. The evolution of packet switching. Proceedings of the IEEE , 1978, 66(11): 1307-1313 doi: 10.1109/PROC.1978.11141
19	Ciucu F. Scaling properties in the stochastic network calculus. PhD thesis, University of Virginia , 2007
20	Wu D, Negi R. Effective capacity: a wireless link model for support of quality of service. IEEE Transactions onWireless Communications , 2003, 2(4): 630-643
21	Kurose J. On computing per-session performance bounds in highspeed multi-hop computer networks. In: Proceedings of the 1992 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 1992, 128-139
22	Yaron O, Sidi M. Performance and stability of communication networks via robust exponential bounds. IEEE Transactions on Networking , 1993, 1(3): 372-385 doi: 10.1109/90.234858
23	Chang C. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Transactions on Automatic Control , 1994, 39(5): 913-931 doi: 10.1109/9.284868
24	Lee K. Performance bounds in communication networks with variable rate links. In: Proceedings of ACM SIGCOMM . 1995, 126-136
25	Cruz R. Quality of service management in integrated services networks. In: Proceedings of the 1st Semi-Annual Research Review, CWC, UCSD . 1995
26	Yin Q, Jiang Y, Jiang S, Kong P Y. Analysis on generalized stochastically bounded bursty traffic for communication networks. In: Proceedings of IEEE Local Computer Networks (LCN) . 2002, 141-149
27	Burchard A, Liebeherr J, Patek S D. A Calculus for End-to-end Statistical Service Guarantees. Technical Report CS-2003-20 , 2002
28	Ciucu F, Burchard A, Liebeherr J. A network service curve approach for the stochastic analysis of networks. In: Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 2005, 279-290 doi: 10.1145/1064212.1064251
29	Jiang Y. A basic stochastic network calculus. In: Proceedings of ACM SIGCOMM . 2006, 123-134
30	Fidler M. An end-to-end probabilistic network calculus with moment generating functions. In: Proceedings of the 14th IEEE International Workshop on Quality of Services (IWQoS) . 2006, 261-270
31	Ciucu F, Burchard A, Liebeherr J. Scaling properties of statistical endto-end bounds in the network calculus. IEEE Transaction on Information Theory , 2006, (6): 2300-2312 doi: 10.1109/TIT.2006.874380
32	Liu Y, Tham C, Jiang Y. A calculus for stochastic GoS analysis. Performance Evaluation , 2007, 64: 547-572 doi: 10.1016/j.peva.2006.07.003
33	Li C, Burchard A, Liebeherr J. A network calculus with effective bandwidth. IEEE Transactions on Networking , 2007, 15(6): 1142-1153
34	Schmitt J, Zdarsky F, Ciucu F. Delay bounds under arbitrary multiplexing: when network calculus leaves you in the lurch. In: Proceedings of IEEE Infocom . 2008, 1669-1677
35	Jiang Y, Yin Q, Liu Y, Jiang S. Fundamental calculus on generalized stochastically bounded bursty traffic for communication networks. Computer Networks , 2009, 53(12): 2011-2021 doi: 10.1016/j.comnet.2009.03.004
36	Wu K, Jiang Y, Li J. On the model transform in stochastic network calculus. In: Proceedings of the 18th International Workshop on Quality of Service (IWQoS) . 2010, 1-9
37	Ciucu F, Schmitt J. Perspectives on network calculus- no free lunch but still good value. In: Proceedings of ACM SIGCOMM . 2012, 311-322
38	Baccelli F, Cohen G, Olsder G J, Quadrat J P. Synchronization and Linearity, Volume 2. Wiley New York , 1992
39	Jiang Y. Network calculus and queueing theory: two sides of one coin. In: Proceedings of the 4th Interational ICST Conference on Performance Evaluation Methodologies and Tools . 2009, 37: 1-37:12 doi: 10.4108/ICST.VALUETOOLS2009.7450
40	Xie J, Jiang Y. Stochastic network calculus models under max-plus algebra. In: Proceedings of the 2009 IEEE Global Telecommunications Conference . 2009, 1-6
41	Xie J, Jiang Y. Stochastic service guarantee analysis based on timedomain models. In: Proceedings of the 17th Annual Meeting of the IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication (MASCOTS) . 2009, 1-12
42	Xie J, Jiang Y, Xie M. A temporal approach to stochastic network calculus. http://arxiv.org/abs/1112.2822, 2011
43	Wrege D, Knightly E N, Zhang H, Liebeherr J. Deterministic delay bounds for vbr video in packet-switching networks: fundamental limits and practical trade-offs. IEEE/ACM Transactions on Networking , 1996, 4(3): 352-362 doi: 10.1109/90.502234
44	Knightly E W. H-BIND: A new approach to providing statistical performance guarantees to VBR traffic. In: Proceedings of IEEE Infocom . 1996, 3: 1091-1099
45	Knightly E W. Second moment resource allocation in multi-service networks. In: Proceedings of the 1997 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 1997, 181-191 doi: 10.1145/258612.258687
46	Jiang Y. A note on applying stochastic network calculus. Technical Report, Norwegian University of Science and Technology (NTNU) , 2010
47	Starobinski D, Sidi M. Stochastically bounded burstiness for communication networks. IEEE Transactions on Information Theory , 2000, 46(1): 206-212 doi: 10.1109/18.817518
48	Jiang Y, Emstad P. Analysis of stochastic service guarantees in communication networks: a traffic model. In: Proceedings of the 19th International Teletraffic Congress (ITC) . 2005, 2337-2346
49	Ciucu F. Network calculus delay bounds in queueing networks with exact solutions. In: Proceedings of the 20th International Teletraffic Congress (ITC) . 2007, 495-506
50	Burchard A, Liebeherr J, Patek S D. A min-plus calculus for end-toend statistical service guarantees. IEEE Transactions on Information Theory , 2006, 52(9): 4105-4114 doi: 10.1109/TIT.2006.880019
51	Boorstyn R R, Burchard A, Liebeherr J, Oottamakorn C. Statistical service assurances for traffic scheduling algorithms. IEEE Journal on Selected Areas in Communications , 2000, 18(12): 2651-2664 doi: 10.1109/49.898747
52	Crovella M E, Bestavros A. Self-similarity in world wide web traffic: evidence and possible causes. In: Proceedings of the 1997 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 1997, 160-169
53	Beran J, Sherman R, Taqqu M, Willinger W. Long-range-dependence in variable-bit-rate video traffic. IEEE Transactions on Communications , 1995, 43(2): 1566-1579 doi: 10.1109/26.380206
54	Yu X, Thng I, Jiang Y, Qiao C. Queueing processes in GPS and PGPS with LRD traffic inputs. IEEE/ACM Transactions on Networking , 2005, 13(3): 676-689 doi: 10.1109/TNET.2005.850213
55	Norros I. On the use of fractional brownian motion in the theory of connectionless networks. IEEE Journal on Selected Areas in Communications , 1995, 13(6): 953-962 doi: 10.1109/49.400651
56	Melo C A, Fonseca d N L. An envelope process for multifractal traffic modeling. In: Proceedings of the 2004 IEEE International Conference on Communications . 2004, 2168-2173
57	Kumar A, Manjunath D, Kuri J. Communication Networking: An Analytical Approach. San Fransisco: Morgan Kaufmann , 2004
58	Jiang Y. Relationship between guaranteed rate server and latency rate server. Computer Networks , 2003, 43(3): 307-315 doi: 10.1016/S1389-1286(03)00276-7
59	Liebeherr J, Patek S, Burchard A. Statistical per-flow service bounds in a network with aggregate provisioning. In: Proceedings of IEEE Infocom . 2003, 3: 1680-1690
60	Le Boundec J, Vojnovic M. Elements of probabilistic network calculus for packet scale rate guarantee nodes. In: Proceeding of MTNS . 2002
61	Rizk A, Fidler M. Leveraging statistical multiplexing gains in singleand multi-hop networks. In: Proceedings of the 19th International Workshop on Quality of Service (IWQoS) . 2011, 1-9
62	Yuan Y, Wu K, Jia W, Jiang Y. Performance of acyclic stochastic networks with network coding. IEEE Transactions on Parallel and Distributed Systems , 2011, 22(7): 1238-1245 doi: 10.1109/TPDS.2010.192
63	Wu K, Jiang Y, Hu G. A calculus for information-driven networks. In: Proceedings of the 17th International Workshop on Quality of Service (IWQoS) . 2009, 1-9
64	Zhang H. Service disciplines for guaranteed performance service in packet-switching networks. Proceedings of the IEEE , 1995, 83(10): 1374-1396 doi: 10.1109/5.469298
65	Ghiassi-Farrokhfal Y, Ciucu F. On the impact of finite buffers on perflow delays in FIFO queues. In: Proceedings of the 24th International Teletraffic Congress (ITC) . 2012
66	Fidler M, Schmitt J B. On the way to a distributed systems calculus: an end-to-end network calculus with data scaling. In: Proceedings of the 2006 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 2006, 287-298
67	Burchard A, Liebeherr J, Ciucu F. On superlinear scaling of network delays. IEEE/ACM Transactions on Networks , 2011, 19(4): 1043-1056 doi: 10.1109/TNET.2010.2095505
68	Liebeherr J, Burchard A, Ciucu F. Delay bounds in communication networks with heavy-tailed and self-similar traffic. IEEE Transactions on Information Theory , 2012, 58(2): 1010-1024 doi: 10.1109/TIT.2011.2173713
69	Jiang Y, Emstad P J, Nevin A, Nicola V, Fidler M. Measurement-based admission control for a flow-aware network. In: Proceedings of the International Symposium on Next Generation Internet Networks . 2005, 318-325
70	Jiang Y, Nevin A, Emstad P J. Implicit admission control for a differentiated services network. In: Proceedings of the 2nd Conference on Next Generation Internet Design and Engineering . 2006, 358-365
71	Hu G, Jiang Y. On the balance between accuracy and robustness for online estimation of delay tail probability. In: Proceedings of the 19th IEEE International Conference on Computer Communication and Networks . 2010, 1-5
72	Lübben R, Fidler M, Liebeherr J. A foundation for stochastic bandwidth estimation of networks with random service. In: Proceedings of IEEE Infocom . 2011, 1817-1825
73	Jiang Y, Emstad P J. Analysis of stochastic service guarantees in communication networks: a server model. In: Proceedings of the 13th International Workshop on Quality of Service (IWQoS) . 2005, 233-245
74	Fidler M. WlC15-2: a network calculus approach to probabilistic quality of service analysis of fading channels. In: Proceedings of the 2006 IEEE Global Telecommunications Conference . 2006
75	Xie J, Jiang Y. A network calculus approach to delay evaluation of ieee 802.11 dcf. In: Proceedings of the 35th IEEE Conference on Local Computer Networks (LCN) . 2010, 560-567
76	Wang Y, Wang T. Applying stochastic network calculus to 802.11 backlog and delay analysis. In: Proceedings of the 19th International Workshop on Quality of Service (IWQoS) . 2011, 1-3
77	Gao Y, Jiang Y. Performance analysis of a cognitive radio network with imperfect spectrum sensing. In: Proceedings of the 2010 Infocom . 2010, 1-6 doi: 10.1109/INFCOM.2010.5462281
78	Gao Y, Jiang Y. Analysis on the capacity of a cognitive radio network under delay constraints. IEICE Transactions on Communications , 2012, E95(4): 1180-1189 doi: 10.1587/transcom.E95.B.1180
79	Mahmood K, Rizk A, Jiang Y. On the flow-level delay of a spatial multiplexing mimo wireless channel. In: Proceedings of the 2011 IEEE International Conference on Communications (ICC) . 2011, 1-6 doi: 10.1109/icc.2011.5963105
80	Mahmood K, Vehkapera M, Jiang Y. Delay constrained throughput analysis of a correlated mimo wireless channel. In: Proceedings of the 20th IEEE International Conference on Computer Communication and Networks , 2011
81	She H, Lu Z, Jantsch A, Zhou D, Zheng L R. Modeling and analysis of rayleigh fading channels using stochastic network calculus. In: Proceedings of the 2011 IEEEWireless Communications and Networking Conference (WCNC) . 2011, 1056-1061
82	Mahmood K, Vehkapera M, Jiang Y. Performance of multiuser cdma receivers with bursty traffic and delay constraints. In: Proceedings of the 2012 International Conference on Computing, Networking and Communications (ICNC) . 2012, 428-433 doi: 10.1109/ICCNC.2012.6167458
83	Zhang Y, Jiang Y. Performance of data transmission over a gaussian channel with dispersion. In: Proceedings of the 2012 International Symposium on Wireless Communication Systems (ISWCS) . 2012, 721-725 doi: 10.1109/ISWCS.2012.6328462
84	Zheng K, Lei L, Liu F, Lin C, Jiang Y. Stochastic performance analysis of a wireless finite-state markov channel. IEEE Transactions on Wireless Communications , 2013, 12(2): 782-793 doi: 10.1109/TWC.2012.122212.120223
85	Deng Y, Lin C, Ren F. Stochastic delay bound for heterogeneous aggregation in sensor networks. In: Proceedings of the 2011 IEEE Global Telecommunications Conference . 2011, 1-5
86	Wang Y. On effectiveness of backlog bounds using stochastic network calculus in 802.11. arXiv preprint arXiv:1202.2914 , 2012
87	Wang K, Lin M, Ciucu F, Wierman A, Lin C. Characterizing the impact of the workload on the value of dynamic resizing in data centers. In: Proceedings of the 2012 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . 2012, 405-406
88	Wang K, Jiang Y, Lin C. Modeling and analysis of a p2p-vod system based on stochastic network calculus. Lecture Notes in Computer Science , 2012, 7201: 302-316 doi: 10.1007/978-3-642-28540-0_25
89	Wang K, Ciucu F, Lin C, Low S. A stochastic power network calculus for integrating renewable energy sources into the power grid. IEEE Journal on Selected Areas in Communications (JSAC): Smart Grid Communications Series , 2012, 30(6): 1037-1048
90	Wu K, Jiang Y, Marinakis D. A stochastic calculus for network systems with renewable energy sources. In: Proceedings of IEEE INFOCOM . 2012, 109-114

Viewed

Full text

Abstract

Cited

Shared

Discussed