On applying stochastic network calculus

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

References

[1] Cruz R. A calculus for network delay, Part i: network elements in isolation. IEEE Transactions on Information Theory, 1991, 37(1): 114-121

[2] Cruz R. A calculus for network delay, Part ii: network analysis. IEEE Transactions on Information Theory, 1991, 37(1): 132-141

[3] Chang C. Performance Guarantees in Communication Networks. Springer Verlag, 2000

[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

[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

[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

[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

[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

[16] Gibbens R, Hunt P. Effective bandwidths for the multi-type uas channel. Queueing Systems, 1991, 9(1): 17-28

[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

[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

[23] Chang C. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Transactions on Automatic Control, 1994, 39(5): 913-931

[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

[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

[32] Liu Y, Tham C, Jiang Y. A calculus for stochastic GoS analysis. Performance Evaluation, 2007, 64: 547-572

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg