Big-Data Streaming Applications Scheduling Based on Staged Multi-Armed Bandits

Several techniques have been recently proposed to adapt Big-Data streaming applications to existing many core platforms. Among these techniques, online reinforcement learning methods have been proposed that learn how to adapt at run-time the throughput and resources allocated to the various streaming tasks depending on dynamically changing data stream characteristics and the desired applications performance (e.g., accuracy). However, most of state-of-the-art techniques consider only one single stream input in its application model input and assume that the system knows the amount of resources to allocate to each task to achieve a desired performance. To address these limitations, in this paper we propose a new systematic and efficient methodology and associated algorithms for online learning and energy-efficient scheduling of Big-Data streaming applications with multiple streams on many core systems with resource constraints. We formalize the problem of multi-stream scheduling as a staged decision problem in which the performance obtained for various resource allocations is unknown. The proposed scheduling methodology uses a novel class of online adaptive learning techniques which we refer to as staged multi-armed bandits (S-MAB). Our scheduler is able to learn online which processing method to assign to each stream and how to allocate its resources over time in order to maximize the performance on the fly, at run-time, without having access to any offline information. The proposed scheduler, applied on a face detection streaming application and without using any offline information, is able to achieve similar performance compared to an optimal semi-online solution that has full knowledge of the input stream where the differences in throughput, observed quality, resource usage and energy efficiency are less than 1, 0.3, 0.2 and 4 percent respectively.

Big-Data Streaming Applications Scheduling Based on Staged Multi-armed Bandits

David Atienza Alonso, Karim Kanoun, Cem Tekin

Institute of Electrical and Electronics Engineers2016

Adaptive Prioritized Random Linear Coding and Scheduling for Layered Data Delivery from Multiple Servers

Pascal Frossard, Eymen Kurdoglu, Nikolaos Thomos

In this paper, we deal with the problem of jointly determining the optimal coding strategy and the scheduling decisions when receivers obtain layered data from multiple servers. The layered data is encoded by means of prioritized random linear coding (PRLC) in order to be resilient to channel loss while respecting the unequal levels of importance in the data, and data blocks are transmitted simultaneously in order to reduce decoding delays and improve the delivery performance. We formulate the optimal coding and scheduling decisions problem in our novel framework with the help of Markov decision processes (MDP), which are effective tools for modeling adapting streaming systems. Reinforcement learning approaches are then proposed to derive reduced computational complexity solutions to the adaptive coding and scheduling problems. The novel reinforcement learning approaches and the MDP solution are examined in an illustrative example for scalable video transmission. Our methods offer large performance gains over competing methods that deliver the data blocks sequentially. The experimental evaluation also shows that our novel algorithms offer continuous playback and guarantee small quality variations which is not the case for baseline solutions. Finally, our work highlights the advantages of reinforcement learning algorithms to forecast the temporal evolution of data demands and to decide the optimal coding and scheduling decisions.

Ieee-Inst Electrical Electronics Engineers Inc2015

Adaptive media streaming over multipath networks

Dan Jurca

With the latest developments in video coding technology and fast deployment of end-user broadband internet connections, real-time media applications become increasingly interesting for both private users and businesses. However, the internet remains a best-effort service network unable to guarantee the stringent requirements of the media application, in terms of high, constant bandwidth, low packet loss rate and transmission delay. Therefore, efficient adaptation mechanisms must be derived in order to bridge the application requirements with the transport medium characteristics. Lately, different network architectures, e.g., peer-to-peer networks, content distribution networks, parallel wireless services, emerge as potential solutions for reducing the cost of communication or infrastructure, and possibly improve the application performance. In this thesis, we start from the path diversity characteristic of these architectures, in order to build a new framework, specific for media streaming in multipath networks. Within this framework we address important issues related to an efficient streaming process, namely path selection and rate allocation, forward error correction and packet scheduling over multiple transmission paths. First we consider a network graph between the streaming server and the client, offering multiple possible transmission paths to the media application. We are interested in finding the optimal subset of paths employed for data transmission, and the optimal rate allocation on these paths, in order to optimize a video distortion metric. Our in-depth analysis of the proposed scenario eventually leads to the derivation of three important theorems, which, in turn represent the basis for an optimal, linear time algorithm that finds the solution to our optimization problem. At the same time, we provide distributed protocols which compute the optimal solution in a distributed way, suitable for large scale network graphs, where a centralized solution is too expensive. Next, we address the problem of forward error correction for scalable media streaming over multiple network paths. We propose various algorithms for error protection in a multipath scenario, and we assess the opportunity of in-network error correction. Our analysis stresses the advantage of being flexible in the scheduling and error correction process on multiple network paths, and emphasizes the limitations of possible real systems implementations, where application choices are limited. Finally, we observe the improvements brought by in-network processing of transmitted media flows, in the case of heterogeneous networks, when link parameters vary greatly. Once the rate allocation and error correction issues are addressed, we discuss the packet scheduling problem over multiple transmission paths. We rely on a scalable bitstream packet model inspired from the media coding process, where media packets have different priorities and dependencies. Based on the concept of data pre-fetch, and on a strict time analysis of the transmission process, we propose fast algorithms for efficient packet scheduling over multiple paths. We ensure media graceful degradation at the client in adverse network conditions by careful load balancing among transmission paths, and by conservative scheduling which transparently absorb undetected network variations, or network estimation errors. The final part of this thesis presents a possible system for media streaming where our proposed mechanisms and protocols can be straightforwardly implemented. We describe a wireless setup where clients can access various applications over possibly multiple wireless services. In this setup, we solve the rate allocation problem with the final goal of maximizing the overall system performance. To this end, we propose a unifying quality metric which maps the individual performance of each application (including streaming) to a common value, later used in the optimization process. We propose a fast algorithm for computing a close to optimal solution to this problem and we show that compared to other traditional methods, we achieve a more fair performance, better adaptable to changing network environments.