Performance bounds in communication networks with variable-rate links

ABSTRACT

In most network models for quality of service support, the communication links interconnecting the switches and gateways are assumed to have fixed bandwidth and zero error rate. This assumption of steadiness, especially in a heterogeneous internet-working environment, might be invalid owing to subnetwork multiple-access mechanism, link-level flow/error control, and user mobility. Techniques are presented in this paper to characterize and analyze work-conserving communication nodes with varying output rate. In the deterministic approach, the notion of "fluctuation constraint," analogous to the "burstiness constraint" for traffic characterization, is introduced to characterize the node. In the statistical approach, the variable-rate output is modelled as an "exponentially bounded fluctuation" process in a way similar to the "exponentially bounded burstiness" method for traffic modelling. Based on these concepts, deterministic and statistical bounds on queue size and packet delay in isolated variable-rate communication server-nodes are derived, including cases of single-input and multiple-input under first-come-first-serve queueing. Queue size bounds are shown to be useful for buffer requirement and packet loss probability estimation at individual nodes. Our formulations also facilitate the computation of end-to-end performance bounds across a feedforward network of variable-rate server-nodes. Several numerical examples of interest are given in the discussion.

REFERENCES

• 1: A. Banerjea and S. Keshav, "Queueing Delays in Rated Controlled ATM networks," Proc. INFOCOM '93, pp. 547- 556, Mar. 1993.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: C. S. Chang, "Stability, Queue Length and Delay, Part I: Deterministic Queueing Networks." IEEE Trans. Auto. Control, vol. 39, no. 5, pp. 913-931, May 1994.
• 4: R.L. Cruz, "A Calculus for Network Delay, Part I: Network Elements in isolation," IEEE Trans. Inform. Theory, vol. 37, no. 1, pp. 114-131, Jan. 1991.
• 5: R. L. Cruz, "A Calculus for Network Delay, Part II: Network Analysis," IEEE Trans. Inform. Theory, vol. 37, no. 1, pp. 132-141, Jan. 1991.
• 6: R. L. Cruz, "Service Burstiness and Dynamic Burstiness Measures: A Framework," J. of High Speed Networks, vol. 1, no. 2, pp. 105-1127, 1992.
• 7: R.L. Cruz and H. N. Liu, "End-to-End Queueing Delay in ATM Networks," J. of High Speed Networks, vol. 3, no. 4, pp. 413-428, 1994.
• 8: R.L. Cruz, "Quality of Service Guarantees in Virtual Circmt Switched Networks," to appear in IEEE JSAC, 1995.
• 9: F.P. Kelly, Reversibility and Stochastic Networks, New York: Wiley, 1979.
• 10: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 11: L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, New York: Wiley, 1976.
• 12: 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
• 13: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 14: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 15: 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]
• 16: O. Yaron and M. Sidi, "Generalized Processor Sharing Networks with Exponentially Bounded Burstiness Arrivals," Proc. IEEE INFORM '94, pp. 5b.4.1-5b.4.7, June 1994.
• 17: David Yates , James Kurose , Don Towsley , Michael G. Hluchyj, On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements, Conference proceedings on Communications architectures, protocols and applications, p.2-12, September 13-17, 1993, San Francisco, California, United States
• 18: Zhi-Li Zhang , Don Towsley , Jim Kurose, Statistical analysis of generalized processor sharing scheduling discipline, Proceedings of the conference on Communications architectures, protocols and applications, p.68-77, August 31-September 02, 1994, London, United Kingdom

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Performance