Multimedia applications with stringent delay requirements are usually supported by the constant bit rate (CBR) or real-time variable bit rate VBR (rt-VBR) service categories of ATM. This paper shows that ABR service, which was originally designed for data, can also support multimedia applications under certain circumstances. Issues related to the design of proper ABR traffic management algorithms for such support are presented.

Keywords:Multimedia applications, ATM switch algorithms, ABR service, traffic management, multicast.

   
Introduction

Asynchronous transfer mode (ATM) is a cell switching, connection oriented, high speed technology. The ATM Forum has defined five service categories: constant bit rate (CBR), real-time variable bit rate (rt-VBR), non real-time VBR (nrt-VBR), available bit rate (ABR) and unspecified bit rate (UBR). The International telecommunication union (ITU-T) defines similar service categories for ATM. CBR and rt-VBR provide delay and loss guarantees and can be used to transfer delay and loss sensitive, unadaptive, multimedia applications. Nrt-VBR provides loss guarantees. ABR and UBR are usually used for transferring data applications. UBR is a simple service that gives no guarantees.

ABR provides minimum cell rate (MCR) guarantees and is designed to provide low cell loss for well-behaving sources. It uses closed-loop feedback control to indicate to the sources the network congestion information. The sources adjust their allowed cell rate (ACR) based on the network feedback. Feedback is indicated in resource management (RM) cells, which are periodically sent by the source and turned around by the destination. The switches along the path indicate the maximum rate which they can currently support in the RM cell. The RM cells in the forward direction are called forward RM (FRM) cells and the RM cells in the backward direction are called backward RM (BRM) cells (see figure  1).

   

Figure 1: RM cell path

Multimedia applications are the key applications to use the large bandwidth provided by high-speed networks, such as ATM networks. Sample multimedia applications include video conferencing, video on demand, distance learning, distributed gamesand movies on demand. Some of these applications, specifically those which have video and voice traffic, need delay and loss guarantees. Others such as the world wide web (WWW) and white boards may be delay insensitive.

Compressed video and voice traffic is usually bursty in nature [ 1] (although video streaming products can generate constant rate video with varying quality). If there are insufficient network resources, CBR and VBR connections may be rejected. In some cases, such as defense applications, it may be more desirable to use whatever bandwidth is available than to get the connection rejected. In such cases, ABR service is preferable. Also, with a CBR or VBR connection, the user may be forced to accept a low bandwidth connection and cannot use bandwidth even if it becomes available later on. Similarly, if the available bandwidth reduces for some reason, the network will simply disconnect the CBR/VBR connections since currently it is not possible to renegotiate the contract.

The ABR service provides minimum cell rate guarantees, which can be used to provide an acceptable quality of service (QoS) for video applications. Due to the closed-loop feedback control, usually the queues in the network switches are small and cell loss is low. Most of the queuing occurs only at the end systems. Multimedia applications, specifically video applications, can use feedback information and information about source queues, to adjust their rates to efficiently use the available bandwidth [ 2]. Furthermore, queuing delay can be bounded if part of the bandwidth is reserved for ABR connections.

The remainder of this paper is organized as follows. Section  2reviews related work. Section  3defines the set of problems to be solved for supporting multimedia applications over the ABR service. Section  4shows how switch algorithms can be modified to provide minimum rate guarantees. Section  5discusses how to reduce the cell loss and delay for multimedia traffic. Providing support for multipoint connections is discussed in section  6. Section  7examines the open issues and problems, and, finally, section  8summarizes the paper.

   
Related Work

There are several studies which address the problem of supporting multimedia traffic over CBR and VBR services. The ATM Forum service aspects and applications (SAA) working group has approved specifications on transporting multimedia service over ATM networks. Luo and Zarki use a layered source encoder to generate high priority and low priority video traffic [ 3]. They study two scalable priority schemes which match the distribution of video information contained in the high and the low priority bit streams. They show that an interleaved transmission scheme (high priority cells are interleaved with low priority cells) performs better than a coupled concatenation scheme (low priority cells are concatenated after the high priority cells). Aravind et. alstudy packet loss resilience using layered video traffic [ 4]. They compare the performance of data partitioning, signal-to-noise ratio scalability, and spatial scalability approaches (specified in the MPEG standards) for generating layered video traffic.

A number of studies have addressed the problem of supporting real-time video applications with feedback control. Kanakia et. alshow how binary feedback can be used to adjust the traffic generated by a video application [ 2]. Lakshman et. aldiscuss how to use the explicit rate feedback of the ABR service to transport video [ 1]. The MPEG encoder parameters (such as quantization level) are adjusted to generate traffic which matches the feedback rate. Vickers et. alstudy the problem of transporting unicast and multicast multi-layered video traffic using both credit-based and rate-based feedback congestion control [ 5]. The video sources adapt to changing network conditions by adjusting encoding parameters, and by adding or dropping a video layer. Recently, an algorithm to transport smoothed compressed video over explicit rate networks has been proposed by Duffield et. al[ 6]. Buffers at the source are used to smooth the video traffic, and adaptive encoding is performed based upon the explicit rate indicated by feedback. Zheng and Atiquzzaman discuss the traffic management issues for multimedia applications over ATM networks [ 7].

   
Multimedia Application Support over ABR

Although the studies mentioned in section  2have addressed multimedia transport, the problem of supporting multimedia applications is not yet a fully solved problem. The components of the ATM technology are shown in Figure  2. The main components used to support multimedia applications are the following:

   

Figure 2: Components for supporting multimedia applications

• Routing and Signaling:The private network-to-network interface (PNNI) protocol provides routing and signaling capabilities between ATM switches. The current PNNI protocol (version 1.0) supports anycast (connection to one among a group) and quality of service based routing. The user-to-network interface signaling currently supports point-to-point connections, point-to-multipoint connections, and leaf initiated joins.
• Traffic Management:Traffic management includes connection admission control (CAC), usage parameter control (UPC), and congestion control. CAC is used to decide whether a connection request can be accepted or rejected, and to decide the parameters associated with that connection. UPC ensures the sources respect the traffic contract by monitoring and controlling traffic at the entrance to the network. It detects violations and takes appropriate actions (such as cell tagging and cell discard). It protects the network and the QoS of other connections from misbehaving connections. For the ABR service, feedback and flow control are used to regulate traffic and adaptively share the available bandwidth in a fair manner.

• The ABR service provides MCR guarantees which can be used by the multimedia applications to achieve a minimum quality of service. Some of the current ABR switch schemes assume MCRs to be zero. These switch schemes have to be modified to support non-zero MCR.
• The ABR service was designed for providing support for delay insensitive data applications. When supporting multimedia applications over ABR, the delay should be minimized and variation in quality of service should be minimized.
• Many multimedia applications, such as videocast and distance learning, can be multicast. Therefore, the problem of providing a multicast capability by supporting ABR point-to-multipoint, multipoint-to-point, and multipoint-to-multipoint connections should be addressed.

The next three sections address these three issues.

   
MCR Support for ABR Switch Algorithms

The ATM Forum traffic management specifications version 4.0 addresses ABR traffic management issues related to ATM end systems in detail. The behavior of the ABR switch is not standardized by this specification. ABR switch algorithms use either binary feedback or explicit rate feedback to provide congestion information to the end systems. The switches monitor the load on the network and divide the available bandwidth fairly among the competing sources. Several distributed switch algorithms which provide explicit rate feedback control have been proposed and proved to give fair and efficient allocations.

When the requested minimum cell rates (MCRs) are zero, the switch schemes attempt to satisfy the max-min fairness criteria. For non-zero MCRs, several similar fairness criteria can be used as defined in the ATM traffic management specifications. A generalized definition of fairness is given in [ 8], in which the excess bandwidth is divided proportional to a predetermined weight, associated with each ABR connection. Other fairness criteria, such as giving MCR plus equal shares, or MCR plus MCR-proportional shares, are special cases of this general definition of fairness. MCR guarantee of the ABR service can be used to achieve a minimal quality of service of multimedia applications.

Switch algorithms can be modified to support non-zero MCRs. As an example, the ERICA+ switch algorithm was modified to support non-zero MCRs. The ERICA+ switch algorithm operates at the output port of an ABR switch. It periodically monitors the load, capacity and activity of connections, and calculates an overload factor. The monitoring interval is called the ``averaging interval.'' The algorithm also keeps track of the maximum allocation given as feedback during the previous averaging interval. The available capacity divided by the number of connections gives an estimate for the fair share of a connection. If the link is not overloaded, the algorithm gives the explicit feedback rate as the maximum of the current cell rate divided by the overload factor and the maximum previous allocation. If the link is overloaded, the maximum of the current cell rate divided by the overload factor and the fair share is given as the explicit rate. ERICA+ also uses dynamic capacity estimate scaling to control queuing delay.

Before discussing the modifications to switch algorithms, we define the term excess fair share and the notion of activity level. The excess fair share (EFS) is calculated by dividing the excess available bandwidth in proportion to the predetermined weights for each connection. The general weighted fair share is the sum of MCR and the excess fair share. The activity level is defined as the ratio of the actual source rate divided by the fair share of the source. The value of the activity level is less than one if the source does not use its fair share. The effective weight of a connection is its activity level multiplied by the predetermined weight. The excess fair share is calculated by dividing the excess available bandwidth in proportion to the effective weights.

Let SrcRate(i) be the source rate of virtual connection (VC) i. Let MCR(i) be the MCR of VC i. Let ER_z(i) be the explicit rate calculated by an algorithm assuming zero MCRs. Let ER_nz(i)be the explicit rate to be calculated for non-zero MCRs. The modifications to a switch scheme to support MCR guarantees are as follows:

1.

The problem with non-zero MCRs is reduced to one with zero MCRs. This is done by subtracting the MCR from each connection's current source rate ( SrcRate(i) - MCR(i)) to obtain the excess rate over MCR of each source.

2.

The switch algorithm for zero MCRs is applied to these excess rates to obtain the explicit rate (ER_z(i) is obtained).

3.

The MCR of the connection is added to the above explicit rate and indicated in the BRM cells.

Simulation results of the above algorithm show that the MCR guarantee is provided and allocations converge to the desired general fair allocation [ 8]. A proof for convergence of the modified algorithm is also given in the same reference.

   
Controlling Delay and Loss

The ABR service is designed for data traffic with no delay guarantees. This section discusses approaches to minimize delay, loss, and variation in quality of service.

During start-up the queue length is dependent upon the value of ICR (initial cell rate) times RTT (round trip time). Other competing sources also influence the initial queue buildup. During steady state period, due to the closed-loop feedback control of the ABR service, network queues are usually small, and queues build up only at the end systems. The cell loss is low for the ABR service. Multi-layer encoding and forward error correction techniques can be used to make the application more loss resilient.

The queuing delay of an ABR connection can be controlled by using a dynamic queue control function. For example, the ERICA+ switch scheme uses a queue control function f(Q) to calculate bandwidth to be allocated as f(Q) times the available bandwidth. The value of f(Q) is dependent on the switch queue length (Q). A controlled queue length, and hence controlled delay in steady state, can be achieved using an appropriate queue control function.

A good queue control function should exhibit the following properties:

1.

Sources should be encouraged to increase their rates if the queue is very small (below a desired length). This implies that f(Q) > 1 in the range .

2.

Maintain constant queue length at steady state, i.e., f(Q) = 1 in the range .

3.

Decrease the source rate under lightly loaded conditions, i.e., f(Q) < 1 in the range .

4.

Under heavy overload, only part of the available bandwidth should be used in order to leave enough capacity to drain large queues. However, a minimum portion of the available bandwidth should always be used for forwarding normal traffic. This can be achieved by limiting the f(Q) value to a threshold. This threshold is known as queue drain limiting factor (QDLF). This implies that f(Q) = QDLFfor the range .

   

Figure 3: Queue control functions

Figure  3shows step, linear, hyperbolic and inverse hyperbolic queue control functions. A thorough simulation and analysis of these different queue control functions and their tradeoffs is given in [ 9]. Based on the analysis, the inverse hyperbolic queue control function was found to have the best performance. The linear queue control function, which is simpler to implement, performs satisfactorily in most cases. Due to the bursty nature of compressed video and voice traffic, the network might not achieve a steady state. By carefully choosing the parameters of the queue control function, the queuing delay can be minimized. Moreover, buffering is used at the source and/or destination to remove jitter in delay.

Most of the end users of multimedia applications are humans. Human users expect constant quality of service. Hence, it is desirable to minimize the variation in the quality of service perceived by the human user. Currently, an RM cell is generated for each Nrm- 1data cells sent. According to current traffic management specifications, the value of the Nrmparameter is usually set to 32. At high link speeds (155.52 Mbps or more), this would give rise to frequent feedback from the network. We assume that the adaptable video source can change rates only at frame boundaries by changing parameters such as quantization levels. Therefore the frequent feedback due to low Nrmis not useful for the adaptable source. By setting a larger value of Nrm(say 256), the feedback rate is made comparable to the source frame rate. Disadvantages of using a higher value of Nrmare that it decreases the responsiveness of the network to new sources, and may increase the effective round trip time, resulting in larger end-to-end delay.

Cell loss and delay guarantees for multimedia ABR connections can also be provided by using a separate queue for them, and reserving a part of the bandwidth for these connections. Appropriate scheduling algorithms need to be used. The ABR parameters and switch algorithm parameters can be different for these connections. The averaging interval length can be large (order of feedback delay) if a large value of Nrm is used. Since these connections do not have a steady state, the parameter Q₁can be chosen as Q₁= Q₀. To provide a good transient response, a hyperbolic function can be used in the range .

   
Multipoint Connection Support

Many multimedia applications are multicast, so it is important to provide scalable and efficient multipoint support for ATM. Traffic management for multipoint connections is a complex problem, due to the presence of multiple senders with different traffic characteristics, multiple receivers with different quality of service requirements, and different bottlenecks along the multipoint connection path. Another difficulty in ATM multipoint support is that higher protocol layers must handle the multipoint communication functions, since lower layers are connection-oriented and not inherently broadcast. The signaling and routing working groups at the ATM Forum have defined point-to-multipoint connection setup and are finalizing UBR multipoint-to-point connection setup.

This section discusses the problems and current solutions for supporting multipoint ABR connections. The main feature of ABR is its feedback control mechanism. For point-to-multipoint ABR connections, the main issue is how to consolidate the feedback information at branch points. In multipoint-to-point connections, fairness definition within the sources in the same connection and among connections is difficult. In addition, feedback has to be regulated at the merge points since RM cells of different sources may be indistinguishable. Multipoint-to-multipoint connections combine the issues with point-to-multipoint and multipoint-to-point connections.

Point-to-Multipoint Connections

The current ATM signaling and routing standards only support point-to-multipoint VCs. Multicast trees are constructed through root-initiated joins. Leaf-initiated joins are also allowed by the latest standards.

Flow control for point-to-multipoint connections is an extension of that of point-to-point connections. A number of studies have addressed the problem of choosing appropriate values for the source end system parameters for point-to-multipoint connections to avoid transient queues. In addition to this, several algorithms tackle feedback implosion. The problem of ``feedback implosion'' arises if the feedback information provided to the sender increases in proportion to the number of leaves (receivers). To solve this problem, consolidation of feedback information from the different leaves of the tree is necessary (see figure  4).

   

Figure 4: Point-to-multipoint connections

The earliest proposal to solve the feedback consolidation problem works as follows. The forward RM cells are multicast to all branches, and are also turned around and sent back to the sender, carrying the minimum explicit rate value denoted by all branches. This approach was used to extend various point-to-point rate allocation algorithms. The extension preserves the fairness and efficiency of the corresponding point-to-point algorithm. This method, however, suffers from the ``consolidation noise'' problem, caused by the asynchrony of feedback arrival and rate changes. Consolidation noise occurs when feedback is not received from some of the branches when an RM cell is to be returned to the sender. Several variations of the early algorithm have been proposed to solve the feedback consolidation problem.

Sonia et. aldiscuss a scheme where the switch forwards BRM cells back to the sender only if BRM cells have been received from all branches [ 10]. However, if the network is overloaded, the switch quickly passes BRM cells returning from the branches, without waiting for all branch BRM cells to arrive. This approach eliminates the consolidation noise, while maintaining a fast transient response in case of overload.

Multipoint-to-Point Connections

Multipoint-to-point connections are supported only for the UBR service in the baseline text of the current ATM Forum specifications. Traffic management rules for multipoint-to-point connections are still under study. Bandwidth management at the merge point is important since the merged traffic is the sum of all traffic from the leaves (see figure  5).

   

Figure 5: Multipoint-to-point connections

Defining the fairness criteria for multiple senders in the same connection can be difficult. Fairness can be defined at the source level, the VC level, or the flow level. A flow is defined as a VC coming on an input link. All fairness definitions are equivalent for point-to-point connections, where each VC has one source and comprises one flow. For multipoint-to-point connections, a VC can have multiple sources and several flows (where each flow may contain merged traffic of several sources). Four different types of fairness can be defined for multipoint-to-point connections as follows [ 11]:

1.

Source-based fairness:Bandwidth is fairly divided among active sources as if they were source in point-to-point connections, ignoring group memberships.

2.

VC/source-based fairness:Bandwidth is fairly divided among active VCs. The bandwidth of each VC is fairly allocated among active sources of that VC.

3.

Flow-based fairness:Bandwidth is fairly allocated among active flows.

4.

VC/flow-based fairness:Bandwidth is fairly divided among active VCs. The bandwidth of each VC is fairly allocated among active flows of that VC.

More work is needed to extend traffic management rules for multipoint-to-point connections. Rigorous performance analysis to evaluate complexity, fairness, transient response, delay, and scalability tradeoffs is required.

Multipoint-to-Multipoint Connections

In the presence of multipoint-to-multipoint connections, switches must combine the branch point and merge point algorithm functionalities. Multipoint-to-multipoint connections are still under study. Careful performance analysis is necessary to evaluate congestion control for many-to-many VCs with different topologies, traffic characteristics, bottlenecks, and round trip times.

   
Open Issues

More extensive performance analysis is required for multimedia applications over the ABR service. The following issues should be resolved for providing support for scalable and adaptable multimedia applications over ABR service:

1.

The problem of mapping the traffic characteristics of multimedia to the traffic parameters of the ABR service (such as MCR) has to solved. Efficient connection admission policy and policing mechanisms for such traffic have to be developed.

2.

Support for renegotiation, and heterogeneity in multipoint connections would provide a more flexible service.

3.

Efficient schemes for supporting multipoint-to-point and multipoint-to-multipoint connections have to be developed. The schemes should have a low overhead and provide fair allocation of the available bandwidth.

4.

Hierarchically encoded video (multi-layer) streams can provide scalable video. In the event of congestion, some of the layers need to be dropped. Currently, ATM connections support only dual priority using the cell loss priority (CLP) bit of cell header. Developing multi-priority discard scheme is necessary to support scalable and adaptable video.

5.

Guidelines for setting ABR source parameters to provide support for multipoint connections transporting multimedia traffic should be developed.

6.

The performance of the multimedia multipoint connections should be comprehensively analyzed using different topologies. Scalability requirements should be analyzed by studying the performance using a large number of end systems.

   
Summary

The following issues were discussed in this paper:

1.

Adaptive multimedia applications can be efficiently transported over the ATM ABR service. The ABR service has attractive features such as low cell loss, short queuing delays, and closed-loop feedback control.

2.

The ABR service provides MCR guarantees, which can provide an acceptable quality of service for voice and video applications. Modifications are necessary to switch algorithms which assume zero MCR values to provide non-zero MCR guarantees.

3.

Loss can be minimized for multimedia ABR connections by using a separate queue and reserving part of the link bandwidth for these connections. Switch queue and hence delay can be controlled using appropriate queue control functions to scale the available bandwidth estimate.

4.

Many multimedia applications are multicast. Point-to-multipoint connections need feedback consolidation algorithms at the branch points. Some of these algorithms suffer from the consolidation noise problem. Several schemes have been proposed to solve this problem. Fair bandwidth allocation for multipoint-to-point and multipoint-to-multipoint connections is currently under study.

Bibliography

1

T. V. Lakshman, P. P. Mishra, and K. K. Ramakrishnan.
Transporting compressed video over ATM networks with explicit rate feedback control.
In Proc. of IEEE INFOCOMM, 1997.

2

H. Kanakia, P. P. Mishra, and A. Riebman.
An daptive congestion control scheme for real-time packet video transport.
In Proc. of ACM SIGCOMM, pages 20-31, Sept 1993.

3

W. Luo and M. Zarki.
Adapive data partitioning for MPEG-2 video transmission over ATM based networks.
Proc. of IEEE International Conference on Image Processing, 1, 1995.

4

R. Aravind, M. Civanlar and A. Reibman.
Packet loss resilience of MPEG-2 scalable video coding algorithms.
IEEE Transactions on Circuits and Systems for Video Technology, 6(5):426-435, 1996.

5

B. J. Vickers, M. Lee, and T. Suda.
Feedback control mechanisms for real-time multipoint video services.
IEEE J. Selected Areas Comm., 15(2), April 1997.

6

N. G. Duffield, K. K. Ramakrishnan, and A. R. Reibman.
SAVE: An algorithm for smoothed adaptive video over explicit rate networks.
In Proc. of IEEE INFOCOM, Apr. 1998.

7

B. Zheng and M. Atiquzzaman.
Traffic management of multimedia over ATM networks.
IEEE Communications Magazine, January 1999.

8

B. Vandalore, S. Fahmy, R. Jain, R. Goyal, and M. Goyal.
A definition of general weighted fairness and its support in explicit rate switch algorithms.
In Proc. of IEEE ICNP, pages 22-30, Oct. 1998.

9

B. Vandalore, S. Fahmy, R. Jain, R. Goyal, and M. Goyal.
Design and analysis of queue control functions for explicit rate switch schemes.
In Proc. of IEEE ICCCN, pages 780-786, Oct. 1998.

10

S. Fahmy, R. Jain, R. Goyal, B. Vandalore, S. Kalyanaraman, S. Kota, and P. Samudra.
Feedback consolidation algorithms for ABR point-to-multipoint connections.
In Proceedings of IEEE INFOCOM 1998, volume 3, pages 1004-1013, March 1998.

11

S. Fahmy, R. Jain, R. Goyal, B. Vandalore, S. Kota, and P. Samudra.
Fairness for ABR multipoint-to-point connections.
ATM Forum/97-0832, September 1997.

All our papers and ATM Forum contributions are available through http://www.cse.wustl.edu/ jain/

Bobby Vandalorereceived his B.Tech degree in 1993 from Indian Institute of Technology, Madras and MS degree in 1995 from the Ohio State University, both in Computer Science. He is currently a PhD candidate at the Ohio State University. His main research interests are in the areas of multimedia communications, traffic management, and performance analysis. He is the author of several papers and ATM Forum contributions. He is a student member of the ACM and IEEE-CS.

Sonia Fahmyreceived her MS degree in Computer Science in 1996 from the Ohio State University, where she is currently a PhD candidate. Her main research interests are in the areas of multipoint communication, traffic management, and performance analysis. She is the author of several papers and ATM Forum contributions. She is a student member of the ACM, the IEEE, and the IEEE Communications and Computer societies.

Professor Raj Jainis an active member of ATM Forum Traffic Management group and has influenced its direction considerably. He is a Fellow of IEEE, a fellow of ACM, and serves on the editorial boards of Computer Networks and ISDN Systems, Computer Communications (UK), and the Journal of High Speed Networks. He is the author of two popular books: ``FDDI Handbook: High Speed Networking using Fiber and Other Media'' published by Addison-Wesley and "The Art of Computer Systems Performance Analysis" published by Wiley. His publications and ATM Forum contributions and can be found at http://www.cse.wustl.edu/ jain/

Rohit Goyalis a PhD. candidate with the Department of Computer and Information Science at the Ohio State University, Columbus. He received his BS in Computer Science from Denison University, Granville. His work has been published in several papers and ATM forum contributions. His other interests include Distributed Systems, Artificial Intelligence, and Performance Analysis.

Mukul Goyalis currently a PhD student in CIS Dept at Ohio State University. He received his B.Tech. in Electronics and Communication Engineering from Regional Engineering College, Kurukshetra, India in 1995. He worked as a software engineer in Siemens Communication Software Ltd, Bangalore, India from 1995-1997.

... Service.¹

This research was sponsored in part by Rome Laboratory/C3BC Contract #F30602-96-C-0156.