CONTACT Geoffrey G. Xie, Assistant Professor Department of Computer Science Naval Postgraduate School Monterey, CA 93943 (408) 656-2693 (408) 656-5717 (fax) xie@cs.nps.navy.mil Towards Application-Level, Guaranteed Statistical Service As the current technological trend is towards integrated services, all types of data including audio, video, graphics, images, and text are to be transported by the same network. Therefore, next-generation networks must be able to provide diverse services to applications in the presence of heterogeneous traffic. So far, three types of quality of service (QoS) requirements have been identified for an integrated services network: best-effort, deterministic, and statistical. The best-effort service is well understood, and it is provided by the current Internet. There is also a fairly good understanding of deterministic services following the recent development of rate-based packet scheduling algorithms. However, many important questions remain in characterizing statistical services. Specifically, the lack of a good understanding of statistical services is manifested in three areas: * The loss rate of packets has been used as the performance measure. To an application, however, the loss rate of its data units is much more relevant. For example, pictures being sent by a video application over an IP network are segmented into sequences of IP packets. The loss rate of pictures is much more important to the application than the packet loss rate. Furthermore because of segmentation, even a small rate of packet losses could result in a large number of application-level data unit (ADU) losses. (This is similar to the throughput degradation phenomenon discovered in recent studies on IP over ATM [11,12]). * The term "statistical" is not well defined. There is a general consensus that it implies that a small fraction of packets could be lost. However, the consequence to applications can be quite different depending on how and at what time scale the loss rate is measured. For example, if the loss rate is measured at a large time scale, say over intervals of several hours, a large number of consecutive packets could be lost for a flow even if the measured loss rate is small. Such a statistical service (like the predictive service defined in [9]) is appropriate only for applications that can adapt to long periods of persistent packet losses. Moreover, the important issue of fair distribution of losses among different flows has not received much attention. * Complex statistical traffic models are often used in the development of new techniques to provide statistical performance guarantees at a small time scale (e.g., over intervals of milliseconds) [8,10]. Such models may not be practical because (i) real world traffic is very diverse statistically and has long range dependency, and (ii) traffic monitoring and policing, if required, can be difficult with a complex traffic model. We believe that future networks should provide application-level QoS. Specifically, we propose to add a guaranteed statistical service to the service model; the service is characterized by (i) a bounded loss rate of ADUs in a flow, (ii) ADU losses distributed fairly among flows subscribing [page 1] to the service and uniformly over the duration of each flow. Such a guaranteed statistical service will greatly enhance the ability of existing networks to support distributed multimedia applications such as Internet broadcasting, distance education, and tele-collaborating, which cannot tolerate long durations of data (e.g. video picture) losses, and for which a deterministic service is unnecessary and may be too expensive. We have done some preliminary work towards this goal [1,2,3,4,5,6]. First, we developed a novel traffic model for real-time traffic such as variable bit rate (VBR) video. Specifically, the sequence of packets of a particular flow (i.e. session) is modeled as a sequence of bursts, each of which is a sequence of packets that carry an application data unit. Based on this model, we designed a class of burst scheduling networks to provide bounded-delay burst transfer service. Recently, we designed an admission control framework that enables a network node to provide the following service: bounded-delay burst transfer at a specified rate of burst losses [5]. We have used the concept of active networking in our design [6,7]. A salient feature of our new traffic model is that each burst carries, in its first packet, information on its rate while traversing the network. It enables the network to allocate bandwidth to a VBR flow efficiently on a per burst basis, which promotes statistical multiplexing. However, we are still a long way from the goal of providing guaranteed statistical services to applications. Therefore we propose to conduct more research in the following two key areas: admission control and resource management. We plan to continue to use an active network approach to providing application-level QoS. In particular, our design will be based on a programmable network architecture that can dynamically customize its services according to application requirements carried in packets. For admission control, we plan to build upon our algorithm for a single network node [5,6]. We focus on the following tasks: (i) develop a robust method to distribute an end-to-end burst loss requirement to individual nodes, (ii) improve the algorithm, especially its loss prediction performance, with better estimation or on-line measurement of traffic parameters, and (iii) extend the algorithm to take into consideration the effects of routing. For the guaranteed statistical service, not only data loss rate needs to be upper bounded, but also the losses must be distributed fairly among all flows subscribing to the service, uniformly over the duration of each flow, and according to application requirements. Appropriate resource management must be used at network nodes to ensure these properties. We focus on the following tasks [6]: (i) develop an algorithm to distribute losses fairly among flows and uniformly over the duration of each flow, (ii) develop a selective early discard mechanism to reduce losses of "critical" application data units (e.g. I frames for MPEG applications), and (iii) extend our traffic model and network design to accommodate the use of layered coding for application data (such as video). [page 2] BIBLIOGRAPHY * Available from http://www.cs.nps.navy.mil/people/faculty/xie/pub [1] G. Xie and S. Lam. Delay guarantee of Virtual Clock server. IEEE/ACM Trans. Networking, 3(6): 683-689, December 1995 [2] S. Lam and G. Xie. Burst scheduling networks. Technical Report TR-94-20, Univ. of Texas at Austin, July 1994. To appear in the journal: Performance Evaluation, 1997. An abbreviated version in Proceedings of IEEE INFOCOM '95. [3] S. Lam and G. Xie. Group priority scheduling. IEEE/ACM Trans. Networking (to appear in 1997). An abbreviated version in Proceedings of IEEE INFOCOM '96. [4] G. Xie and S. Lam. An Efficient Adaptive Search Algorithm for scheduling real-time traffic. In Proceedings of 1996 IEEE International Conference on Network Protocols (ICNP '96). [5] G. Xie and S. Lam. Real-time block transfer under a link sharing hierarchy. To appear in Proceedings of IEEE INFOCOM '97. [6] G. Xie and S. Lam. An Application-Level Guaranteed Statistical Service. Submitted for publication. [7] S. Bhattacharjee, K. Calvert, and E. Zegura. On active network and congestion. Technical Report GIT-CC-96/02, Georgia Institute of Technology, Atlanta, Georgia, 1996. [8] S. Chong, S. Li, and J. Ghosh. Dynamic bandwidth allocation for efficient transport of real-time VBR video over ATM. In Proceedings of IEEE INFOCOM '94, pages 81-90, June 1994. [9] D. Clark, S. Shenker and L. Zhang. Supporting real-time applications in an integrated services packet network. In Proceedings of ACM SIGCOMM '92, pages 14-26, August 1992. [10] R. Guerin, H. Ahmadi, and M. Naghshineh. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE Journal on Selected Areas in Communications, 9(7):968-981, 1991. [11] A. Romanow and S. Floyd. The dynamics of TCP traffic over ATM Networks. In Proceedings of ACM SIGCOMM '94, London, England, August, 1994. [12] J.S. Turner. Maintaining high throughput during overload in ATM networks. In Proceedings of IEEE INFOCOM '96, San Francisco, CA, April 1996.