Date: Tue, 14 Jan 1997 21:49:40 GMT Server: NCSA/1.5.1 Last-modified: Sun, 06 Oct 1996 18:13:54 GMT Content-type: text/html Content-length: 17449 Design and Analysis of ATM Networks

Design and Analysis of ATM Networks

Computer Networks Research Group
in the Department of Computer Science
at the University of Massachusetts

Unlike traditional data networks, future broadband-ISDN (BISDN) wide-area networks will be required to carry a broad range of traffic classes ranging from bursty, variable-rate sources, such as voice and variable-rate coded video, to smooth, constant bit rate sources. Moreover, these networks will have to do so while providing a guaranteed performance or quality-of-service (QOS) to these traffic classes. The problem of characterizing performance in such networks is thus particularly important since this must be done not only for the traditional off-line tasks of dimensioning and design (e.g., determining link bandwidths, buffer capacities and processing capacities at network switchpoints) but also for on-line, performance-driven traffic control purposes such as session-level admission control. In this section, we outline our research aimed at providing the analytical tools and techniques for analyzing such networks and their diverse workloads and for designing and characterizing the properties of scheduling policies in these networks.

Traditional approaches towards performance evaluation of communication networks are generally not applicable in a high-speed network environment for a number of reasons. First, the traffic in future high-speed networks is projected to be ``bursty,'' often processing complex correlations in the cell arrival processes. Simple Markovian assumptions (such as memoryless inter-arrival times) are thus likely to be invalid in such networks. The gigabit rates of future high-speed networks also render simulation ineffective for systems of any realistic size. The very performance metric(s) of interest in a high-speed network will also be different -- average delay will no longer be the primary performance measure, and, instead, secondary performance measures such as probability of buffer overflow, maximum packet delay, and the tail of delay distributions must be considered. In this respect, there is evidence that even relatively sophisticated performance models which work well for predicting average delay in the presence of correlated arrivals may be less well-suited for computing these new performance measures of interest [Naga91]. We also note that many previous performance evaluation techniques have been confined to studying the performance of the aggregate traffic generated by a set of identical sources at a single multiplexer in isolation; in connection-oriented high-speed networks with QOS guarantees, it is clear that performance must be examined on a per-session basis and in a network setting [Kuro92,Schu92]. Finally, we note that given the potentially complex nature of network traffic, it is becoming increasingly valuable to be able to broadly characterize properties (such as optimality, or near optimality) of network control mechanisms which hold over a wide range of traffic models and assumptions. Thus far, however, little work has been reported on this problem for traditional networks, much less for high-speed networks.

Given the above considerations, it is evident that new performance evaluation techniques will be required for the design and analysis future high-speed networks. Furthermore, given the QOS requirements of such emerging standards as ATM, these techniques will also be needed for on-line performance driven, traffic control purposes such as session-level admission control. Our research in these areas is aimed at addressing this need. Our research divides broadly into four areas:

BIBLIOGRAPHY

[Bacc92] F. Baccelli, Z. Liu, D. Towsley, ``Optimal Scheduling of Parallel Processing Systems With and Without Real-Time Constraints'', to appear in Journal of the ACM.

[Chip89] R. Chipalkatti, J.F. Kurose, and D. Towsley, ``Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer,'' Proc. IEEE Infocom'89, (Ottawa Canada), pp. 774-783.

[Goli90] P. Goli, J. Kurose, and D. Towsley, ``Approximate Minimum Laxity Scheduling Algorithms for Real-Time Systems,'' Technical Report 90-88, Department of Computer and Information Science, University of Massachusetts, Amherst, MA.

[Hong89] J. Hong, X. Tan, and D. Towsley, ``A Performance Analysis of Minimum Laxity and Earliest Deadline Scheduling in a Real-Time System,'' IEEE Transactions on Computers, Vol. 38, No.~12, (December 1989), 1736--1744.

[Hwan91] R.H. Hwang and J.F. Kurose, ``On Virtual Circuit Routing and Re-Routing in Packet-Switched Networks,'' 1991 IEEE Int. Conf. on Communications, pp. 318-323.

[Hwan92] R. Hwang, J.F. Kurose, D. Towsley, ``The Effect of Processing Delay and QOS Requirements in High Speed Networks,'' 1992 IEEE Infocom Conference, (Florence, Italy, May 1992), pp. 160-169.

[Hwan92a] R. Hwang, J.F. Kurose, D. Towsley, ``State Dependent Routing for Multi-Rate Loss Networks,'' to appear in Proc. 1992 IEEE Globecom Conference, (Dec. 1992, Orlando, Fla.).

[Kuro90] J. Kurose, ``An Exact Analysis of Customer Loss Under Minimum Laxity Scheduling in Discrete Time Queueing Systems,'' to appear in Performance Evaluation.

[kuro91] J.F. Kurose, D. Towsley, C,.M. Krishna, `Design and Analysis of Processor Scheduling Policies for Real-Time Systems'' Foundations of Real-Time Computing: Scheduling and Resource Management, Ed. A. VanTilborg, Kluwer Publishers, 1991.

[Kuro92] J. Kurose, ``On Computing Per-Session Performance Bounds in High-Speed Multi-hop Computer Networks,'' 1992 ACM SigMetrics Conference, (Newport Beach, RI, June 1992), pp. 128-139.

[Lopr95:TR95-109], F. Lo Presti, Z.-L. Zhang, D. Towsley, "Bounds, Approximations and Applications for a Two-Queue GPS System", Technical Report UM-CS-95-109, Department of Computer Science, University of Massachusetts, December 1995. An abridged version of the paper ( Lopr95:Info96) appeared in INFOCOM'96, 1996.

[Lopr96:ATM_Time_Scale], F. Lo Presti, Z.-L. Zhang, J. Kurose and D. Towsley, "Source Time Scale and Optimal Buffer/Bandwidth Trade-off for Regulated Traffic in an ATM Node", Technical Report UM-CS-96-38, Department of Computer Science, University of Massachusetts, June 1996.

[Lopr96:INFOCOM97], F. Lo Presti, Z.-L. Zhang, J. Kurose and D. Towsley, "Source Time Scale and Optimal Buffer/Bandwidth Trade-off for Regulated Traffic in an ATM Node", To appear in Proc. IEEE INFOCOM'97, Kobe, Japan, 1997.

[Naga91] R. Nagarajan, J.F. Kurose, and D. Towsley, ``Approximation Techniques for Computing Packet Loss in Finite-Buffered Voice Multiplexers,'' IEEE Journal on Selected Areas in Communications, Vol. 9, No. 5 (April 1991).

[Naga92] R. Nagarajan, J.F. Kurose, D. Towsley, ``On Defining, Computing and Guaranteeing Quality-of-Service in High-Speed Networks,'' 1992 IEEE Infocom Conference, (Florence, Italy, May 1992), pp. 2026-2035.

[Nels92] R. Nelson, D. Towsley, A.N. Tantawi. ``Performance analysis of parallel processing systems,'' IEEE Transactions on Software Engineering, SE-14, 4, 532-540, April 1988.

[Panw88] S. Panwar, D. Towsley and J. Wolf, ``Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service,'' J. of the ACM, Vol. 35, No. 4 (Oct. 1988), pp. 832-844.

[Ping91] S. Pingali and J. Kurose, ``On Scheduling Two Classes of Real-Time Traffic with Correlated Deadlines,'' IEEE Globecom '91 Conference, June 1991.

[Schu90a] H.G. Schulzrinne, J.F. Kurose and D. Towsley, ``Congestion Control by Selective Packet Discarding for Real-Time Traffic in High-Speed Networks,'' Proc. IEEE Infocom'90, (San Francisco, CA), pp. 545-550.

[Schu90b] H.G. Schulzrinne, J.F. Kurose and D. Towsley, ``Congestion Control for Real-Time Traffic in High-Speed Networks,'' Technical Report TR89-92, Dept. of Computer and Info. Sci., Univ. of Mass., Amherst, MA.

[Schu91] H.G. Schulzrinne and J.F. Kurose, ``Distribution of the Loss Period for Some Queues in Continuous and Discrete Time,'' IEEE Infocom'91 Conference, pp. 1446-1455.

[Schu92:Voice] H.G. Schulzrinne, `` Voice Communication Across the Internet: A Network Voice Terminal,'' Technical Report TR 92-50, Dept. of Computer Science, University of Massachusetts, Amherst MA 01003, July 1992.

[Schu92] H.G. Schulzrinne, J.F. Kurose, D. Towsley, ``Loss Correlation for Queues with Single And Multiple Input Streams,'' 1992 IEEE Int. Conference on Communications.

[Tows89] D. Towsley and S. Panwar, ``Comparison of Service and Buffer Overflow Policies for Multiple Server Queues that Serve Customers with Deadlines,'' COINS Technical Report 89-72, University of Massachusetts, Amherst MA, (July, 1989).

[Tows90] D. Towsley, ``Applications of Sample Path Analysis Techniques to Communication Networks,'' Proc. 4th Conference on Data Communication Systems and their Performance, Barcelona, Spain, 1990 (invited paper).

[Yate93] David Yates, James Kurose, Don Towsley, and Michael G. Hluchyj, ``On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements,'' ACM SIGCOMM Symposium on Communications Architectures and Protocols, pp 2-12, Sep., 1993 (San Francisco, CA).

[Yate94] David Yates, James Kurose, Don Towsley, and Michael G. Hluchyj, ``On per-session end-to-end delay and the call admission problem for real-time applications with QOS requirements,'' Technical Report CMPSCI 93-20, University of Massachusetts, May, 1994.

[Zhan94:SIGCOMM] , Z.-L. Zhang, D. Towsley, J. Kurose, "Statistical Analysis of Generalized Processor Sharing Scheduling Discipline", 1994 ACM SigComm Conference.

[Zhan95:GPS_JSAC] , Z.-L. Zhang, D. Towsley, J. Kurose, "Statistical Analysis of Generalized Processor Sharing Scheduling Discipline", IEEE Journal on Selected Area in Communications, "Advances in the Fundamentals of Networking: Part I", Vol.13, No.6, pp. 1071-1080, August 1995.

[Zhan95:TR95-10], Z.-L. Zhang, D. Towsley, J. Kurose, "Statistical Analysis of Generalized Processor Sharing Scheduling Discipline", Technical Report UM-CS-95-10, Computer Science Department, University of Massachusetts, February 1995.

[Zhan95:TR95-52], Z.-L. Zhang, Z. Liu, J. Kurose and D. Towsley, "Call Admission Control Schemes under the Generalized Processor Sharing Scheduling Discipline", Technical Report UM-CS-95-52, Computer Science Department, University of Massachusetts, March 1995. An abridged version (Zhan96:GPS-CAC) to appear in Telecommunication Systems.

[Zhan95:TR95-96], Z.-L. Zhang, "Large Deviations and the Generalized Processor Sharing Scheduling for a Two-Queue Systems", Technical Report UM-CS-95-96, Computer Science Department, University of Massachusetts, Oct. 1995.

[Zhan95:TR95-97], Z.-L. Zhang, "Large Deviations and the Generalized Processor Sharing Scheduling for a Multiple-Queue Systems", Technical Report UM-CS-95-97, Computer Science Department, University of Massachusetts, Oct. 1995.

[Zhan96:Smoothing], Z.-L. Zhang, J. Kurose, J. Salehi, D. Towsley, ``Smoothing, Statistical Multiplexing and Call Admission Control for Stored Video'', Technical Report UM-CS-96-029, Department of Computer Science, University of Massachusetts, February 1996.

[Zhan96:JSAC-Smoothing], Z.-L. Zhang, J. Kurose, J. D. Salehi, and D. Towsley, "Smoothing, Statistical Multiplexing and Call Admission Control for Stored Video", Accepted for Publication ( JSAC Special Issue on Real-Time Video Services in Multimedia Networks ).