A basic stochastic network calculus

ABSTRACT

A basic calculus is presented for stochastic service guarantee analysis in communication networks. Central to the calculus are two definitions, maximum-(virtual)-backlog-centric (m. b. c) stochastic arrival curve and stochastic service curve, which respectively generalize arrival curve and service curve in the deterministic network calculus framework. With m. b. c stochastic arrival curve and stochastic service curve, various basic results are derived under the (min, +)algebra for the general case analysis, which are crucial to the development of stochastic network calculus. These results include (i)superposition of flows, (ii)concatenation of servers, (iii) output characterization, (iv)per-flow service under aggregation, and (v)stochastic backlog and delay guarantees. In addition, to perform independent case analysis, stochastic strict server is defined, which uses an ideal service process and an impairment process to characterize a server. The concept of stochastic strict server not only allows us to improve the basic results (i)-(v)under the independent case, but also provides a convenient way to find the stochastic service curve of a serve. Moreover, an approach is introduced to find the m.b.c stochastic arrival curve of a flow and the stochastic service curve of a server.

REFERENCES

• 1: Rajeev Agrawal , Rene L. Cruz , Clayton Okino , Rajendran Rajan, Performance bonds for flow control protocols, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.310-323, June 1999 [doi>10.1109/90.779197]
• 2: S. Ayyorgun and W. Feng. A systematic approach for providing end-to-end probabilistic QoS guarantees. In Proc. IEEE IC3N '04, 2004.
• 3: F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat. Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, 1992.
• 4: Jorg Liebeherr , Stephen Patek , Almut Burchard, A Calculus for End-to-end Statistical Service Guarantees, University of Virginia, Charlottesville, VA, 2001
• 5: C.-S. Chang. Stability, queue length, and delay of deterministic and stochastic queueing networks. IEEE Trans. Automatic Control, 39 5):913--931, May 1994.
• 6: C.-S. Chang. On the exponentiality of stochastic linear systems under the max-plus algebra. IEEE Trans. Automatic Control, 41(8):1182--1188, August 1996.
• 7: Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, London, 2000
• 8: Cheng Shang Chang , Rene L. Cruz , Jean Yves Le Boudec , Patrick Thiran, A min, + system theory for constrained traffic regulation and dynamic service guarantees, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.805-817, December 2002 [doi>10.1109/TNET.2002.804824]
• 9: Florin Ciucu , Almut Burchard , Jörg Liebeherr, A network service curve approach for the stochastic analysis of networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 10: R. L. Cruz. A calculus for network delay, part I: network elements in isolation. IEEE Trans. Information Theory, 37(1):114--131, Jan. 1991.
• 11: R. L. Cruz. A calculus for network delay, part II: network analysis. IEEE Trans. Information Theory, 37(1):132--141, Jan. 1991.
• 12: R. L. Cruz. Quality of service guarantees in virtual circuit switched networks. IEEE JSAC, 13(6):1048--1056, Aug. 1995.
• 13: R. L. Cruz. Quality of service management in integrated services networks. In Proc. 1st Semi-Annual Research Review, CWC, UCSD, June 1996.
• 14: M. Fidler. An end-to-end probabilistic network calculus with moment generation functions. In Proc. IWQoS, 2006.
• 15: Pawan Goyal , Harrick M. Vin, Generalized guaranteed rate scheduling algorithms: a framework, IEEE/ACM Transactions on Networking (TON), v.5 n.4, p.561-571, Aug. 1997 [doi>10.1109/90.649514]
• 16: Yuming Jiang, Relationship between guaranteed rate server and latency rate server, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.3, p.307-315, 22 October 2003 [doi>10.1016/S1389-1286(03)00276-7]
• 17: Yuming Jiang, Per-domain packet scale rate guarantee for expedited forwarding, IEEE/ACM Transactions on Networking (TON), v.14 n.3, p.630-643, June 2006 [doi>10.1109/TNET.2006.876177]
• 18: Y. Jiang and P. J. Emstad. Analysis of stochastic service guarantees in communication networks:A server model. In Proc. 13th International Workshop on Quality of Service (IWQoS), June 2005.
• 19: Y. Jiang and P. J. Emstad. Analysis of stochastic service guarantees in communication networks: A traffic model. In Proc. 19th International Teletraffic Congress (ITC19), August 2005.
• 20: Y. Jiang. Analysis of stochastic service guarantees communication networks:A basic calculus. Preprint, Norwegian University of Science and Technology, Nov. 2005, arXiv e-Print, No. cs. PF/0511008.
• 21: Edward W. Knightly, Second moment resource allocation in multi-service networks, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.181-191, June 15-18, 1997, Seattle, Washington, United States
• 22: Jim Kurose, On computing per-session performance bounds in high-speed multi-hop computer networks, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.128-139, June 01-05, 1992, Newport, Rhode Island, United States
• 23: J.-Y. Le Boudec. Application of network calculus to guaranteed service networks. IEEE Trans. Information Theory, 44(3):1087--1096, May 1998.
• 24: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 25: Kam Lee, Performance bounds in communication networks with variable-rate links, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.126-136, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 26: C. Li, A. Burchard, and J. Liebeherr. A network calculus with effective bandwidth. Technical report, CS-2003-20, University of Virginia, November 2003.
• 27: J. Liebeherr. IWQoS 2004 Panel Talk:Post-Internet QoS Research, 2004.
• 28: Y. Liu, C.-K. Tham, and Y. Jiang. A stochastic network calculus (revised). Technical report, ECE-CCN-0301, National University of Singapore, November 2004.
• 29: Yong Liu , Chen-Khong Tham , Yuming Jiang, Conformance analysis in networks with service level agreements, Computer Networks and ISDN Systems, v.47 n.6, p.885-906, 22 April 2005 [doi>10.1016/j.comnet.2004.10.001]
• 30: A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, 3rd edition, 1991.
• 31: J. Qiu and E. W. Knightly. Inter-class resource sharing using statistical service envelopes. In IEEE INFOCOM '99, 1999.
• 32: S. Ross. Stochastic Processes. John Wiley &Sons, 2nd edition, 1996.
• 33: J. S. Sadowsky and W. Szpankowski. Maximum queue length and waiting time revisited:Multiserver G/G/c queue. Probability in the Engineering and Informational Science, 6:157--170, 1992.
• 34: D. Starobinski and M. Sidi. Stochastically bounded burstiness for communication networks. IEEE Trans. Information Theory, 46(1):206--212, Jan. 2000.
• 35: Dimitrios Stiliadis , Anujan Varma, Latency-rate servers: a general model for analysis of traffic scheduling algorithms, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.611-624, Oct. 1998 [doi>10.1109/90.731196]
• 36: D. Stoyan. Comparison Methods for Queues and Other Stochastic Models. John Wiley & Sons, 1983.
• 37: Workshop Attendees. Report of the National Science Foundation Workshop on Fundamental Research in Networking, April 2003.
• 38: D. Wu and R. Negt. Effective capacity: A wireless link model for support of quality of service. IEEE Trans. Wireless Communications, 2 4):630--643, July 2003.
• 39: Opher Yaron , Moshe Sidi, Performance and stability of communication networks via robust exponential bounds, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.372-385, June 1993 [doi>10.1109/90.234858]
• 40: Qinghe Yin , Yuming Jiang , Shengming Jiang , Peng Yong Kong, Analysis on Generalized Stochastically Bounded Bursty Traffic for Communication Networks, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.141-149, November 06-08, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Performance, Theory

Keywords:
independent case analysis, stochastic arrival curve, stochastic network calculus, stochastic quality of service guarantee, stochastic service curve, stochastic strict server