MM000671.R1 1

Abstract—Traffic smoothing is an efficient means to reduce the bandwidth requirement for transmitting a VBR (variable-bit-rate) video stream. Several traffic smoothing algorithms have been presented to offline compute the transmission schedule for a prerecorded video. For live video applications, Sen et al. present a sliding-window algorithm, referred to as SLWIN(k), to online compute the transmission schedule on the fly. SLWIN(k) looks ahead W video frames to compute the transmission schedule for the next k frametimes, where k≤w. Note that W is upper bounded by the initial delay of the transmission. The time complexity of SLWIN(k) is O(W*N/k) for an N frame live video. In this paper, we present an O(N) online traffic smoothing algorithm and two variants, denoted as FOS, FOS1 and FOS2, respectively. Note that O(N) is a trivial lower bound of the time complexity of the traffic smoothing problem. Thus, the proposed algorithm is optimal. We compare the performance of our algorithms with SLWIN(k) based on several benchmark video clips. Experiment results show that FOS2, which adopts the aggressive workahead heuristic, further reduces the bandwidth requirement and better utilizes the client buffer for real-time interactive applications in which the initial delays are small