Private:mobile streaming ideas

Mobile TV

Summer 2009

Joint transcoders in mobile TV networks.

Broadcasting multiple VBR streams over a wireless network using statistical multiplexing can be done in one of two ways: (i) burst scheduling on base stations, and (ii) joint rate control among multiple video transcoders. The main difference between them is that the former approach broadcasts multiple VBR streams with diverse and varying total bit rate, while the second approach broadcasts multiple VBR streams with a constant total bit rate. We describe each of them in the following.

{\bf By Burst Scheduling. } This approach assumes that the TV channels are not jointly transcoded on the base station, and thus the total instantaneous bit rate is diverse and varying along the time. This approach has two advantages, it: (i) does not require transcoding any pre-encoded videos such as movies and TV episodes, and (ii) does not require all the transcoders to be collocated with the statistical multiplexing controller.

The authors of \cite{RBG09} propose a statistical multiplexing solution for DVB-H networks. Their system divides the time axis into fixed-length recurring time periods, and then schedule all TV channels in round-robin fashion in every time period. That is, every TV channel is assigned a burst length based on its average bit rate. To accommodate the bit rate variations in each TV channel, the burst length and burst boundary are partially flexible: the start and end times can be shifted within a per-determined range. Since the burst start times are not deterministic, the authors propose to wake up mobile devices earlier so that they never miss the beginning of bursts. The system proposed in \cite{RBG09} has three drawbacks. First, the scheduling algorithm only provides limited flexibility: burst scaling and shifting are only allowed in a small pre-determined range of time. Second, mobile devices are waken up earlier to accommodate the nondeterministic burst length and time, which leads to lower energy saving. Third, the resulting burst schedules are in round-robin, and TV channels with low bit rates may suffer from low energy saving.

The SMS algorithm proposed in our MM09 work also achieves statistical multiplexing using burst scheduling. In contrast to the solution in \cite{RBG09}, our algorithm dynamically allocates bursts to individual TV channels: burst start times and lengths are flexible without any limitations, and the bursts are not scheduled in strict round-robin fashion. In addition, It uses a small look-ahead window (in the order of seconds) to compute deterministic burst start times and lengths. The SMS algorithm has a shortcoming: it does not guarantee that the mobile devices never suffer from buffer underflow instances. There are two approaches to address this. First, we can use smoothing buffers on mobile devices to receive data in advance in order to absorb buffer underflow instances. We call this variation as SMS', which gives guarantees on no buffer underflow instances at the expense of larger memory requirement and longer initial buffering delay. Second, we can develop a dynamic programming algorithm to compute the optimal burst scheduling in terms of energy saving. Unfortunately, such an algorithm incurs extremely high computational complexity while the additional energy saving may be marginal compared to SMS and SMS'.

{\bf By Joint Transcoders. } This approach transcodes all TV channels together so that the total instantaneous bit rate can be fit into a CBR channel. Fig. 1 illustrates a joint transcoder, which consists of S transcoders and a statistical multiplex controller. Joint transcoders are similar to individual transcoders, except the former transcoders exchange video statistics among each other in order to properly allocate the bit budget provided by the CBR channel among TV channels. Joint transcoders have been widely studied in the late 90', e.g., see \cite{WV99}, and have been recently updated for modern video coders, e.g., see \cite{TVT08}.

The authors of \cite{RBG08} study the joint rate control problem among multiple transcoders, and propose a rate control algorithm based on fuzzy logic. Their algorithm aims at achieving low end-to-end delays and small quality variance among TV channels. While the authors of \cite{RBG08} claim that their statical multiplexing system is designed for DVB-H networks, it does not take any DVB-H system parameters as input nor does it take any feedback from the DVB-H base station. Therefore, we believe the system in \cite{RBG08} is merely another joint transcoder design based on fuzzy logic. (More precisely, the authors repackaged their joint transcoder for DVB-H networks without performing any evaluation directly related to DVB-H networks.)

{\bf In Real Deployments.} UDCast IPE-10 implements statistical multiplexing using joint transcoder, similar to \cite{RBG08}, and flexible burst start time and length, similar to \cite{RBG09}. UDCast does not implement their own joint transcoders, but require customers to find a proper transcoder implementation. IPE-10 assumes several (say 12) TV channels are grouped into a statistical multiplexing group, and allocate periodical and fixed-length air-time to each group. Within a group, the air-time is then divided into bursts for individual TV channels, where burst time and length are partially flexible within a pre-determined range. IPE-10 has four drawbacks. First, it does not support pre-encoded video streams. Second, it performs strict round-robin scheduling, which is not efficient for low bit rate TV channels in terms of energy saving. Third, it wakes up mobile devices slightly earlier in order to accommodate the flexibility on burst start time and length. Fourth, how to split TV channels into groups itself is difficult.

{\em Summary. } When transcoding is not an option, our SMS and SMS' algorithms can be used to broadcast pre-encoded video streams for optimal network utilization and near-optimal energy saving. Dynamic programming based optimal algorithms, while possible, may not be justified for the high time complexity and marginal energy saving improvement over SMS.

When transcoding is possible, adding joint transcoders to adjust video stream bit rates allows mobile TV networks to fully utilize the available bandwidth. Previous works in the literature do not consider time slicing and receiver buffer limits in mobile TV networks. UDCast IPE-10, on the other hand, employs nondeterministic burst start times and lengths. Since mobile devices must be waken up earlier to accommodate the nondeterminism, IPE-10's statistical multiplexing leads to lower energy saving (, however, the manual suggests the difference is negligible).

There are three possible directions to improve upon IPE-10. First, we may add a control channel between transcoders and the IP encapsulator. So that transcoders will give the IP encapsulator the start time of the next burst, and free mobile devices from waking up earlier. While this approach leads to higher energy saving, it's an engineering issue and may not be interesting to the research community. Second, we may move one step further, and consider more comprehensive burst scheduling algorithm rather than simple round-robin. For example, the IP encapsulator can schedule a burst to the TV channel whose receivers are about to face buffer underflow instances. This heuristic allows the base station to schedule longer bursts for higher energy saving. It is, however, not completely clear how much energy saving can be achieved by employing this (or more comprehensive) burst scheduling algorithm. Third, we may get rid of the complex and expensive transcoders all together, and use scalable coded streams in mobile TV networks. This can largely simplify the whole base station, because IP encapsulator no longer needs to negotiate with joint transcoders, and it can locally perform real-time stream adaptation for all TV channels.

{\bf References. }

• BG09: M. Rezaei, I. Bouazizi, and M. Gabbouj. Implementing statistical multiplexing in DVB-H. Internal Journal of Digital Multimedia Broadcasting, 2009, April 2009.
• WV99: L. Wang and A. Vincent. Bit allocation and constraints for joint coding of multiple video programs. IEEE Transactions on Circuits and Systems for Video Technology, 9(6):949-959, September 1999.
• TVT08: M. Tagliasacchi and G. Valenzise and S. Tubaro. Minimum variance optimal rate allocation for multiplexed H.264/AVC bitstreams. IEEE Transactions on Image Processing, 17(7):1129-1143, July 2008.
• RBG08: M. Rezaei, I. Bouazizi, and M. Gabbouj. Joint video coding and statistical multiplexing for broadcasting over DVB-H channels. IEEE Transactions on Multimedia, 10(7):1455-1464, December 2008.

Earlier Ideas

• Extend power awareness to WiMax and TDMA networks.

• Equalizing perceived-quality for multiple concurrent TV channels: We consider a mobile TV system that broadcasts several video sequences at the same time, while these video sequences have heterogeneous characteristics/complexities and require diverse bit rates to achieve the same perceived-quality. Our goal is to determine the best streaming bit rate for each TV channel such that all TV channels achieve a uniform perceived-quality that is less than or equal to a given target quality chosen by network operators.
  • We then show that by tolerating a small quality variation (or quality degradation), we can increase the energy saving (or battery life).
  • The same solution can be applied to an Internet on-demand video server to reduce the server-load and bandwidth consumption by providing users good, but not too good, perceived quality. The target quality can be in server level agreements.

• Dependency-aware burst scheduling: Video refresh time, caused by decoding dependency among video frames, is one of the dominating sources of channel switching delay. Therefore, reducing refresh time is important for user experience because most users tend to switch channels frequently. Our goal is to reduce video refresh time without compromising bandwidth utilization. Most previous works insert/replace an immediately decode-able (IDR) frame at the beginning of each burst. Although doing so will reduce video refresh time, it also increases the bandwidth consumption because IDR frames are much larger than predictive frames. We believe this problem can be better solved by dynamically varying burst sizes according to given frame structures so that IDR frames are as close to the beginning of individual bursts as possible. For example, having an IDR frame as the 2nd frame in a burst only incurs negligible delay compared to inserting an IDR frame as the 1st frame. However, the former case consumes lower bandwidth because P- or B-frames are much smaller than I-frames.

• Statistical multiplexing: We consider VBR-coded video streams and apply statistical multiplexing method in the literature to mobile TV networks to solve burst scheduling problem. We analytically analyze the performance of such mobile TV networks in terms of energy saving, channel switching delay, packet loss rate/re-buffering instances, among others. Our analysis is based on existing models of VBR traffic flow and of Internet router design. At high level, our burst scheduler allocates bursts to individual TV channel with proportional length to their buffer levels: more air time is assigned to TV channels with more pending packets in the outgoing queues. The ultimate goal of our analysis is to design an admission algorithm that provides QoS guarantees in statistical fashion.