An End-to-End Source-Adaptive Multi-layered Multicast (SAMM) Algorithm

Abstract: Layered encoding is often recommended as a solution to the problem of varying bandwidth constraints in video multicast applications. However, multi-layered encoding alone is not sufficient to provide ideal video quality and bandwidth utilization, because network bandwidth constraints change over time. Adaptive techniques are required. In this paper we consider a rate-based Source-Adaptive Multi-layered Multicast (SAMM) algorithm that operates on an end-to-end basis. Video sources adapt the rates of their video layers in response to congestion feedback from receivers. To prevent feedback implosion, the use of computationally simple feedback mergers is proposed. Network switches and routers are not required to implement complex flow or congestion control algorithms. Using simulations, we demonstrate that the end-to-end SAMM algorithm exhibits better scalability and responsiveness than algorithms which are not source-adaptive.

This research is supported by the National Science Foundation through grant NCR-9628109. It has also been supported by grants from the University of California MICRO program, Hitachi Ltd., Hitachi America, Standard Microsystem Corp, Tokyo Electric Power Company, Nippon Telegraph and Telephone Corporation (NTT), Nippon Steel Information and Communication Systems Inc. (ENICOM), Matsushita Electric Industrial Company, and Fundação CAPES/Brazil.

1. Introduction

The simultaneous multicast of video to many receivers is complicated by variation in the amount of bandwidth available throughout the network. The use of layered video is commonly recommended to address this problem. A multi-layered video encoder encodes raw video data into one or more streams, or layers, of differing priority. The layer with the highest priority, called the base layer, contains the most important portions of the video stream, while additional layers, called enhancement layers, are encoded with progressively lower priorities and contain data that further refines the quality of the base layer stream. For each unique bandwidth constraint, the encoder generates an enhancement layer of video, thereby ensuring that all receivers obtain a quality of video commensurate with their available bandwidth.

However, multi-layered encoding alone is not sufficient to provide ideal video quality and bandwidth utilization, because network bandwidth constraints often change continuously and rapidly. To improve the bandwidth utilization of the network and optimize the quality of video obtained by each of the receivers, the source must respond to these changing network conditions. It should dynamically adjust the number of video layers it generates as well as the rate at which each layer is transmitted. For the source to do this, it must have congestion feedback from the receivers and the network.

We define a Source-Adaptive Multi-layered Multicast (SAMM) algorithm as any multicast algorithm which uses congestion feedback to adapt the transmission rates of multiple layers of data. Our previous work [1,2,3] has focused on network-based SAMM algorithms which require that network switches be capable of executing complex flow and congestion control algorithms. However, in most existing networks and internetworks, where datagram routing and forwarding are often the only universally shared operations, the existence of such congestion control functions cannot be assumed.

This paper focuses on an end-to-end SAMM algorithm that should be implementable in next generation internets. Prerequisites for its implementation include router-based priority drop preference and flow isolation via either class-based queueing or weighted fair queueing. In the algorithm, video receivers generate congestion feedback to the source by monitoring the arrival rate of video traffic, and feedback packets are merged by an overlaid virtual network of feedback mergers. Network switches or routers are not required to implement any novel flow or congestion control algorithms.

The remainder of this paper is organized as follows. Trade-offs between sender-driven and receiver-driven approaches to layered multicast are considered in section 2. The details of the end-to-end SAMM algorithm introduced by this paper are described in section 3. The performance of the algorithm in terms of scalability, responsiveness, and fairness is compared with that of a non-adaptive algorithm in section 4. And some concluding remarks are provided in section 5.

2. Sender-Driven vs. Receiver-Driven Adaptation

Adaptation to network congestion can be sender-driven or receiver-driven. In a sender-driven algorithm, the source adapts its transmission rate in response to congestion feedback from the receivers and/or the network. In a receiver-driven algorithm, the source transmits several sessions of data, and the receivers adapt to congestion by changing the selection of sessions to which they listen. Examples of sender-driven adaptive video transmission algorithms include SAMM [1,2,3], the probabilistic feedback algorithm of Bolot et al. [4], and several unicast adaptive algorithms [5,6]. Examples of receiver-driven video transmission algorithms include Receiver-driven Layered Multicast (RLM) [7], Layered Video Multicast with Retransmission (LVMR) [8], and TCP-like congestion control for layered data [9]. The Destination Set Grouping (DSG) approach [10] shares features of the receiver-driven and sender-driven approaches.

There are several trade-offs between receiver-driven and sender-driven approaches, particularly for the case of layered video multicast. The first trade-off is the granularity of adaptation. In a receiver-driven algorithm, the source typically generates a fixed number of layers at a coarse set of fixed rates. Hence, if the path to one of the receivers has an amount of available bandwidth that does not exactly match one of the layer transmission rates, the network will be underutilized and the quality of that receiver's video will be suboptimal. On the other hand, sender-driven algorithms are able to fine-tune their layer transmission rates in response to network bandwidth availability and can therefore achieve better network utilization and video quality.

Another trade-off arises in the ability of sender-driven and receiver-driven algorithms to respond to rapidly fluctuating background traffic. Because sources using sender-driven algorithms receive a continuous stream of congestion feedback from the network, they can adapt to changing bandwidth constraints either by adding a new video layer or by adjusting the rate of an existing layer. Furthermore, this can be done rapidly, usually within a single round-trip time. Most receiver-driven algorithms, on the other hand, adapt to changing network congestion through a combination of ``join experiments'' and branch pruning, both of which occur at time intervals greater than the round-trip time.

The layer subscription and unsubscription strategies of receiver-driven algorithms also have negative consequences for overall video throughput and loss -- consequences that sender-driven algorithms do not share. In most receiver-driven algorithms, receivers perform occasional join experiments, during which they request a new layer of data. If the join experiment creates congestion, packets may be lost and the experiment is considered by the receiver to be a failure. Since receiver-driven algorithms like RLM do not rely on priority discarding, packets from any video layer -- even the base layer -- may be lost during failed join experiments, causing brief but severe degradation in video quality for some receivers. Receiver-driven algorithms also rely on the receiver's ability to prune itself from the distribution tree of a given layer should there be insufficient bandwidth to support that layer. However, there is a significant ``leave latency'' associated with the pruning of a branch from a multicast tree. During this time, traffic congestion on the branch may be exacerbated, resulting in greater packet loss and delay for downstream receivers. In a network environment where bandwidth availability is continuously and sometimes severely fluctuating, the effects of join experiments and long leave latencies can result in periods of significant packet loss and, for the case of video, poor video quality.

Receiver-driven algorithms have the advantage that they are naturally more friendly to competing network traffic than are sender-driven algorithms. Sender-driven algorithms typically send all video data on a single transport layer connection and use priority indications to specify the drop precedence of each layer. This inevitably results in some low-priority traffic being sent needlessly down some branches of the multicast tree, only to be discarded further downstream. If this extraneous traffic shares FIFO queues with competing traffic that is adaptive (e.g., TCP flows), then the adaptive flows may experience an unfair degree of discarding or delay within the network. Receiver-driven algorithms do not share this deficiency with sender-driven algorithms, because they send each layer of video in a different flow and allow for the pruning of flows that have no downstream receivers. One way to correct this deficiency of the sender-driven algorithms is to isolate video traffic from other traffic. This can be done by implementing class-based queueing [11] or weighted fair queueing [12] within the routers or switches. There is, however, a greater complexity involved in the implementation of class-based and fair queueing.

3. Architecture and Algorithm

In the proposed end-to-end SAMM algorithm, the source adjusts its encoding parameters, including the number of video layers it generates and the encoding rate of each layer. These adjustments are performed in response to a continuous flow of congestion feedback from the receivers. Special feedback mergers are distributed throughout the network and prevent feedback implosion by aggregating the feedback returning from receivers. See Figure 1 for an illustration of the architecture. The complexity of the end-to-end SAMM algorithm is concentrated at network terminal points, namely the source, the receivers, and the feedback mergers. Network routers and switches are not assumed to perform any significantly complex or novel functions.

As the source generates video, it segments the video into multiple layers, each of which is assigned a unique priority. The layer with the highest priority, called the base layer, is used to generate packets containing the most important features of the video stream, while additional layers, called enhancement layers, are encoded with progressively lower priorities and are used to generate packets that receivers can use to further refine the quality of the base layer stream. There are a number of ways to generate layered video data, but for the purposes of this paper we will assume that the source coarsely quantizes the video stream's frequency coefficients to produce the base layer and adds refinement data to produce enhancement layers.

Since the end-to-end SAMM algorithm relies on priority to differentiate layers, the underlying network architecture is required to give higher drop preference to low priority data. This is necessary to ensure that less important enhancement layer data is dropped in favor of more important enhancement and base layer data. Enhancement data is useless if the layer it is enhancing is missing. (According to the latest IETF draft specification, IPv6 will support 8 bits of priority [13], and efforts are underway to define standard semantics for these bits [14].)

When a branch of the multicast tree experiences (or is relieved of) congestion, available bandwidth decreases (or increases) on the branch, and the arrival rate of video packets at downstream receivers changes accordingly. Due to this fact, a receiver can obtain a rough estimate of the bandwidth available on the path from the source by monitoring how fast video packets arrive. In the end-to-end SAMM algorithm, each receiver monitors the arrival rate of video packets by using Clark and Fang's time sliding window (TSW) algorithm [17]. Normally, the receiver assumes the available bandwidth is equal to the received video rate. However, the actual available bandwidth may be higher than the video arrival rate when the network is under-utilized. In order to exploit the available bandwidth, the receiver occasionally reports an amount of available bandwidth that is slightly higher than the observed arrival rate of video packets. The receiver reports a higher rate whenever there is a significant change in the observed arrival rate and no packet losses have been recorded in a given interval of time. This allows source to capture newly available bandwidth in an incremental, and therefore stable, manner.

After receiving a given number of video packets, the receiver returns a feedback packet to the nearest upstream feedback merger. This feedback packet contains a rate field, which is the receiver's estimate of the available bandwidth on the path from the source.

Feedback mergers are deployed to prevent feedback implosion, an undesirable situation in which a large number of receivers consumes significant return-path bandwidth by sending feedback to a single source. In order to alleviate this problem, feedback mergers consolidate information from arriving feedback packets and route the resulting feedback packets upstream towards the next feedback merger on the path to the source. The idea of deploying special nodes in the network to alleviate feedback implosion originated with the Reliable Multicast Transport Protocol (RMTP) [18]. Feedback mergers ultimately form a virtual network overlaid on top of the underlying datagram network as shown in Figure 1. They may be deployed at the source, at dedicated nodes inside the network, at routers which have been enhanced to perform the merging function, and/or at one or more participating receivers. In realistic scenarios, feedback mergers are likely to be incrementally deployed as the load created by feedback packets becomes a greater issue.

Feedback packets contain two vectors: a rate vector {r_i}, which lists the rates requested by receivers, and a counter vector {c_i}, which lists the number of receivers requesting each rate in {r_i}. When a receiver generates a feedback packet, it contains only entries for r₁ and c₁, with r₁ set to the measured available bandwidth and c₁ set to one. For every end-to-end connection, feedback mergers store the most up-to-date feedback packets arriving on each downstream branch and merge them whenever one branch receives receives two feedback packets from the same connection. The resulting feedback packet is then returned towards the root of the video multicast tree.

During the vector merging operation, the feedback merger collects the rate (r_i) and counter (c_i) entries from each incoming feedback packet and stores them in a local array, sorted by rate. Each rate entry corresponds to a video rate requested by one or more downstream receivers, while the counter values indicate how many downstream receivers have requested each rate. Ultimately, the rate values will be used by the source to determine the rates at which to transmit each video layer. After filling the local rate array, the number of entries in the array is compared to the maximum number of video layers allowed for the connection (L_max). If the number of entries in the local rate array is less than or equal to L_max, then the merging is considered complete. However, if the number of entries exceeds L_max, then one (or more) of the rate entries must be discarded and its counter value added to the next lower entry. To determine which entry (or entries) to discard, the merger attempts to estimate the impact of dropping each listed rate on the overall video quality. This is done through the use of a simple estimated video quality metric.

The estimated video quality metric attempts to measure the combined "goodput" of video traffic that will be received by all downstream receivers. The goodput for a single receiver is defined as the total throughput of all video layers received without loss. For instance, suppose a source is transmitting three layers of video at 1 Mbps each. If a receiver entirely receives the most important first two layers but only receives half of the third layer due to congestion, then its total received throughput is 2.5 Mbps, but its goodput is equal to the combined rate of the first two layers, namely 2 Mbps. The goodput is a relatively useful estimate of video quality because it measures the total combined rate of uncorrupted video traffic arriving at an end system.

As feedback mergers consolidate feedback packets, they attempt to determine the goodput that downstream receivers will receive. The combined goodput G is estimated from the values listed in a rate array and calculated as follows:

where N is the number of entries in the local rate array, and r_i and c_i are the rate and counter values for each entry. To determine which entry to remove from the local rate array, the merger calculates the combined goodput that will result from each potential entry removal. The entry removal that results in the highest combined goodput is then removed from the rate array. This process is repeated until the number of entries in the local rate array is equal to the maximum number of layers allowed. For a specific example of this algorithm in operation, see [2].

By the time a feedback packet arrives at the source, it contains the number of video layers to encode and a list of cumulative rates at which to encode each layer.

An optional enhancement to this algorithm is to reserve from the network a fixed amount of bandwidth equal to the minimum transmission rate and encode the base layer at this rate. Enhancement layers can then be encoded whenever congestion feedback indicates that further bandwidth is available. Reserving bandwidth in this way guarantees that all receivers will receive at least the base layer without losses. It is envisioned that such a guarantee may be provided by a network resource reservation algorithm like RSVP [15] or by the emerging differentiated services architecture [14].

4. Performance

This section presents the results of several simulations designed to evaluate the performance of the end-to-end SAMM algorithm under various configurations. These configurations are designed to test the responsiveness, scalability with delay, scalability with the number of receivers, and fairness of the algorithm.

Unless otherwise specified, all simulations assume link capacities of 10 Mbps, propagation delays between end systems and routers of 5 $\mu$ s, and propagation delays between routers of 100 $\mu$ s. All packets are the size of ATM cells (53 bytes), and two class-based queues are used at each router hop to isolate background traffic from video traffic. To keep queueing delays minimal, only the amount of buffers necessary to tolerate 10 ms of feedback delay on a series of 10 Mbps links are used. For most simulation models, this works out to approximately 200 packets per router hop for each video flow. Feedback packets are generated by receivers once for every 32 video packets received. Every router is assumed to be directly connected to a feedback merger.

4.1 Responsiveness

One of the most important requirements of a source rate adaptation algorithm is that it be able to respond rapidly to changes in network congestion. This simulation experiment illustrates the trade-offs between algorithms source-adaptive and non-source-adaptive algorithms. It also shows the impact of network propagation delay on the responsiveness of the SAMM algorithm.

The model shown in Figure 2 is used to evaluate the responsiveness of the algorithm. It consists of one video source and two receivers. Background traffic is applied on links L₁ and L₂, and two responsiveness experiments are conducted. The first experiment is designed to explore the transient response of the source to changes in available bandwidth on one of the links. The second experiment explores the impact of the network propagation delay on the effectiveness of the mechanism.

In the first experiment, we apply CBR background traffic at a rate of 3 Mbps to link L₁ and sharply oscillating square-wave background traffic to link L₂. The square-wave traffic oscillates between constant rates of 4 and 7 Mbps over a period of 500 ms and is used to test the responsiveness of the source to sudden and substantial changes in available bandwidth. As a basis for comparison, we also examine the performance of a source which is not adaptive and transmits three layers of video at fixed, cumulative rates of 1, 4.5 and 8 Mbps. This set of rates is admittedly arbitrary, but so is any choice of rates for a non-adaptive layered transmission mechanism.

Figure 3 shows the results of the simulation. First, notice that the SAMM algorithm generated only two video layers. As expected, the source adapts the rate of the base layer in response to the oscillating available bandwidth on link L₂. The enhancement layer is transmitted at a cumulative rate of 7 Mbps, which correspond to the available bandwidth on link L₁. Note that the source responds quickly to the square-wave traffic oscillations, usually within 10 milliseconds. For the purposes of comparison, Figure 3(b) plots the cumulative transmission rates of each layer for the non-adaptive case.

The receiver goodput values for the adaptive and non-adaptive mechanisms are shown in Figs. 3(c) and 3(d). Recall that video goodput is defined as the total throughput of all video layers received without loss during a block transmission interval. Clearly the SAMM algorithm produces better goodput than the non-adaptive scheme due to its ability to adjust encoding behavior based on network congestion feedback. Although receiver R₂ experiences degradations of goodput during downward transitions due to buffer overflow, they are brief and the overall goodput levels are desirable. In contrast, the goodput of the non-adaptive mechanism suffers significantly from its inability to take the current state of the network into account.

In the second experiment, we explore the impact of propagation delay on the goodput. We apply CBR background traffic on link L₁ and square-wave background traffic with a period of 200 ms on link L₂. The background traffic transmission rates are the same as for the first experiment. End-to-end propagation delays are varied from 0.2 to 100 msec, and each simulation is run for 60 simulation seconds.

The average goodput delivered to each receiver is plotted in Figure 4. As end-to-end propagation delay increases beyond 10 msec, the average goodput delivered to receiver 2 by the SAMM algorithm drops almost linearly. This is due to the fact that as the propagation delay increases, the source uses increasingly stale congestion feedback to adjust its layer transmission rates. Despite this drawback, the SAMM algorithm produces better goodput than the non-adaptive mechanism for both receivers and all propagation delays.

4.2 Scalability

Scalability is perhaps the most important performance measure of a multicast mechanism. Multicast connections can reach dozens or even hundreds of receivers, each with varying bandwidth constraints. It is therefore important to understand how a multicast mechanism performs as the number of receivers grows.

The network model shown in Figure 5 consists of one video source, four groups of receivers, and seven routers. Within each receiver group, the number of receivers can be varied between 2 and 32. Independent background traffic streams are applied to each leaf link, and the traffic loads are divided into four heterogeneous groups ( $\rho_1 = 2$ Mbps, $\rho_2 = 4$ Mbps, $\rho_3 = 6$ Mbps, $\rho_4 = 8$ Mbps). Background traffic is generated by a 10-state Markov-Modulated Poisson Process with state transition rates of 100 sec^-1. This traffic model captures the superposition of 10 on-off, interrupted Poisson processes and is generally much burstier than a simple Poisson process.

We first examine the performance of the SAMM algorithm as the number of receivers increases and the maximum number of video layers is varied from 2 to 8. Figure 6 plots the results. The goodput ratio is defined as the fraction of the available bandwidth used to transport uncorrupted video layers. To calculate the goodput ratio, the combined rate of video layers arriving at all receivers is divided by the total amount of bandwidth available to all receivers. These results reveal that the SAMM algorithm scales well with the number of receivers. They also illustrate the expected result that video goodput (and thereby video quality) can be improved by increasing the maximum number of layers generated by the source.

In the second scalability experiment we encode and decode actual video sequences and transmit them through the simulated network shown in Figure 5. For this experiment we use an embedded zero-tree wavelet encoder to generate multiple layers of video from a raw video sequence. The raw video sequence we use is the Academy Award winning short animation, Wallace & Grommit. The number of multicast receivers is varied between 8 and 128, up to 4 video layers are used, and the background traffic used in the first scalability experiment is reapplied to the leaf links.

Figure 7 plots the average peak signal-to-noise ratio of the decoded video sequence for a sampled receiver from each receiver group. (The peak signal-to-noise ratio is a measure of the video quality. The larger the value, the lesser the distortion. It is calculated by comparing the original and the received video image.) The video quality at each receiver remains relatively flat as the number of receivers increases, confirming that the SAMM algorithm is scalable. Furthermore, the quality of video obtained by a receiver is determined by the amount of bandwidth available to it. Example of video sequences (in MPEG format) delivered to a sampled receiver from each receiver group is available at http://netresearch.ics.uci.edu/video/pv99/movie/.

4.3 Fairness

An important factor in the evaluation of any traffic control mechanism is its fairness. If the mechanism fails to divide bandwidth equally between competing connections, then some connections may unfairly receive better service than others. We use the simple "parking lot" model depicted in Figure 8 to examine the fairness of the SAMM algorithm. Propagation delays on links $L_1, \dots, L_4$ are 10 msec, representing distances of 2000 km, and each of these links is loaded with 6 Mbps of background traffic generated by four independent N-state MMPP processes. To adjust the burstiness of the background traffic, three values for the number of MMPP states are used: N=10 (heavily bursty), N=50 (moderately bursty) and N=2000 (lightly bursty).

The allocation of bandwidth to competing video traffic streams is said to be optimal if it is max-min fair. A max-min fair allocation of bandwidth occurs when all active connections not bottlenecked at an upstream node are allocated an equal share of the available bandwidth at every downstream node [16]. In the model shown in Figure 8, a max-min fair allocation of bandwidth occurs if all three sources transmit at the same rate. To measure fairness, we calculate the standard deviation $\sigma$ of the rates that each source transmits across the bottleneck links L₃ and L₄. An optimally fair allocation results in a standard deviation of zero.

Results for this set of simulations are shown in Table 1. There is a consistent degradation of fairness as the burstiness of the interfering traffic increases. This result was expected, since it is difficult for sources more distant from the shared bottleneck links (L₃ and L₄) to adapt their rates in response to rapid changes in the available bandwidth. Sources close to the shared bottleneck links unfairly grab a larger portion of the available bandwidth, especially when the background traffic is bursty. This kind of unfairness can be eliminated by using weighted fair queueing within each of the router output ports. If traffic flows from sources S₁, S₂ and S₃ are buffered in isolated queues and scheduled with equal weights, then their allocations of bottleneck link bandwidth become virtually identical as shown in the table.

Table: Video transmission rates and fairness with FIFO queues and fair queueing

	Lightly Bursty Background				Moderately Bursty Background				Heavily Bursty Background
	Rate (Mbps)			Fairness	Rate (Mbps)			Fairness	Rate (Mbps)			Fairness
Scheduling	S₁	S₂	S₃	$\sigma$	S₁	S₂	S₃	$\sigma$	S₁	S₂	S₃	$\sigma$
FIFO	1.318	1.332	1.350	0.025	1.312	1.316	1.349	0.035	1.299	1.312	1.400	0.094
Fair queuing	1.331	1.331	1.331	0.000	1.333	1.333	1.333	0.000	1.333	1.333	1.333	0.000

5. Conclusion

In this paper we have introduced the notion of a source adaptive multi-layered multicast (SAMM) algorithm and have proposed and investigated a simple end-to-end SAMM algorithm for possible use in next generation Internets. In the algorithm the source transmits several layers of video and adjusts their rates in response to congestion feedback from the receivers. Feedback implosion is prevented by deploying feedback mergers throughout the network. The algorithm makes very few demands on intermediate network nodes, requiring only a priority drop preference mechanism and class-based flow isolation. Simulation results presented in this paper indicate good responsiveness and scalability performance of the end-to-end SAMM algorithm. Our present and future work includes exploration of the impact of the algorithm on an actual network, through implementation on a modified IP network testbed.