Statistical multiplexing of variable-bit-rate videos streamed to mobile devices

We address the problem of broadcasting multiple video streams over a broadcast network to many mobile devices, so that: (i) streaming quality of mobile devices is maximized, (ii) energy consumption of mobile devices is minimized, and (iii) goodput in the network is maximized. We consider two types of broadcast networks: closed-loop networks, in which all video streams are jointly encoded to ensure their total bit rate does not exceed the broadcast network bandwidth, and open-loop networks, in which videos are encoded using standalone coders, and thus must be carefully broadcast to avoid playout glitches. We first show that the problem of optimally broadcasting multiple videos is NP-complete. We then propose an approximation algorithm to construct burst schedules for multiple VBR (Variable-Bit-Rate) streams. The proposed algorithm frees network operators from the manual and error-prone bandwidth reservation process which is currently used in practice. We prove that the proposed algorithm achieves optimal goodput and near-optimal energy saving. We show that it produces glitch-free schedules in closedloop networks, and it minimizes number of glitches in open-loop networks. We implement the proposed algorithm in a tracedriven simulator, and conduct extensive simulations for both open- and closed-loop networks. The simulation results show that the proposed algorithm outperforms the existing algorithms in many aspects, including number of late frames, number of concurrently broadcast video streams, and energy saving of mobile devices. To show the practicality and efficiency of the proposed algorithm, we also implement it in a real mobile TV testbed as a proof of concept. The results from the testbed confirm that the proposed algorithm: (i) does not result in playout glitches, (ii) achieves high energy saving, and (iii) runs in real time.