Private:mobile streaming ideas

From NMSL

Mobile TV

Broadcasting VBR Streams in Mobile TV Networks

Statistically multiplexing multiple VBR streams over a wireless network can be done in one of two ways: (i) burst scheduling on base stations, and (ii) joint rate control among multiple video transcoders. 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.


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 is simpler because it requires no joint transcoders, which are more complex than standalone transcoders. In addition, joint transcoders must be deployed at the same location, and are less flexible for deployment.


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. This allows the SMS algorithm to save more energy. 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 store data in advance in order to absorb buffer underflow instances. We develop an algorithm, called SMS', that guarantees 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 leads to high computational complexity while the additional energy saving may be marginal compared to SMS and SMS'.


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 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 based on fuzzy logic. Furthermore, they do not evaluate their joint transcoders from the aspects of DVB-H networks.


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 allocates periodical and fixed-length air-time to each group. Within a group, the air-time is 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 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 flexible burst start times and lengths. Fourth, how to split TV channels into groups itself is difficult.


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 and SMS'.


When transcoding is possible, adding joint transcoders to adjust video stream bit rates leads to higher bandwidth utilization and better perceived video quality, at the expense of higher implementation and deployment complexities. 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.


There are two extensions beyond the MM09 paper. First, we polish the SMS' algorithm for smaller memory requirement and shorter initial buffering delay. We can send the SMS and SMS' to TOMCCAP. Second, we propose a new mobile TV base station, where IP encapsulator employs multiple scalable stream for R-D optimization, and perform optimal burst scheduling in terms of energy saving. The goals of the new mobile TV base station include: (i) R-D optimized stream adaptation, (ii) fully utilized bandwidth, (iii) no buffer violation instances, (iv) optimal energy saving, and (v) very low implementation and deployment complexity. This new design combines the advantages of the existing two approach for statistical multiplexing, which hasn't been showed in the literature. We may submit this work to NSDI 2010 and USENIX 2010.


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.