Panagiotis+Oikonomou　Maria+G.+Koziri　Nikos+Tziritas　Thanasis+Loukopoulos　XU+Cheng??Zhong

Abstract

Efficient video delivery involves the transcoding of the original sequence into various resolutions， bitrates and standards， in order to match viewers capabilities. Since video coding and transcoding are computationally demanding， performing a portion of these tasks at the network edges promises to decrease both the workload and network traffic towards the data centers of media providers. Motivated by the increasing popularity of live casting on social media platforms， in this paper we focus on the case of live video transcoding. Specifically， we investigate scheduling heuristics that decide on which jobs should be assigned to an edge mini?datacenter and which to a backend datacenter. Through simulation experiments with different QoS requirements we conclude on the best alternative.

Keywords

video transcoding； edge computing； scheduling； heuristics； x264

M1 Introduction

odern applications built on top of an integrated Internet of Things （IoT） environment [1]， together with Cyber Physical Systems （CPSs） [2]， involve heavy video traffic， e.g.， in smart vehicle traffic management. At the same time， the proliferation of smart mobile devices carrying cameras of continuously higher resolution， together with the explosive growth in the popularity of social media platforms， poses great challenges in cloud resource management. As an indication， Cisco reported in [3] that during 2015， mobile Internet traffic experienced a growth of 74%， the majority of which （>50%） was video transmissions. Therefore， minimizing video related network traffic becomes of paramount importance.

Video coding is the process of compressing a raw video sequence using some standards. Examples of such standards are H.264/AVC [4] which is the most popular （but aging） standard currently in use， High Efficiency Video Coding （HEVC） [5] and VP9 [6]， which are newer standards achieving higher compression ratios compared to H.264/AVC. Although video coding is a computationally demanding task， it is usually performed at the point where the initial video is captured （camera， smart device etc.）， often with the aid of specialized hardware. Thus， the initial coding of a video sequence does not hinder a cloud based social media platform （SMP） computationally wise and the only overhead is the consumed bandwidth for uploading. However， in order to be able to deliver the video sequence to a variety of clients differing in screen resolutions， decoders and network capabilities， the originally uploaded sequence must be encoded into multiple output sequences of various resolutions， bitrates， quality levels and perhaps coding standards. This process is called transcoding and burdens computationally and network?wise the SMPs cloud. In particular， the case of live casting offers the most challenges since real time performance is a requirement.

Motivated by the above， we investigate the case where an SMP can take advantage of mini?data centers existing at network edges in order to offload live transcoding jobs， thus， saving resources and bandwidth. Fig. 1 illustrates an example whereby two broadcasts are performed， one at 1080p and the other at 720p from two different edges. In the first case （1080p）， the sequence is not transcoded at the edge but transmitted to one of the SMPs data centers for processing. Then two different outputs （720p and 480p） are sent to some Content Delivery Network （CDN）. In contrast to this， the other input sequence （720p） is transcoded into two output sequences at the edge. Copies of the outputs are sent to the CDN and also used to satisfy local demands （480p）. Clearly， the second alternative of using edge transcoding reduces both the processing and network resource consumption at the SMPs cloud.

In this paper， we tackle the associated scheduling problem induced by the scenario of Fig. 1. Namely， given edge resources and the characteristics of arriving transcoding tasks， task?server assignment must be made so that the percentage of tasks not processed by the edge （satisfied with overhead by SMPs Cloud） is minimized. We evaluate different scheduling heuristics for the scheduling problem under the constraint that each assigned task must obtain the required processing power to exhibit real time behavior. We then examine the case where the aforementioned constraint is softened， allowing for some quality loss in order to increase the number of tasks assigned to the edge. All heuristics are evaluated using a dataset of Twitch broadcasts [7] and realistic values for transcoding job characteristics obtained by using x264 codec [8] over class B and class A common test video sequences [9].

The rest of the paper is organized as follows. Section 2 discusses the related work. Section 3 presents the problem formulation. Heuristics are illustrated in Section 4 and evaluated in Section 5. Finally Section 6 concludes the paper.

2 Related Work

The number of transcoding tasks hosted by edges is dictated by their processing requirements. Related to this requirement is research concerning speeding up of video coding and transcoding. An avid research exists on parallelizing video coding with approaches varying from coarse grained parallelism， whereby parallelism is considered at the level of group of Macroblocks （H.264/AVC） or Coding Tree Units （CTUs in HEVC）， to finer grained parallel approaches implementable within a block of pels. Examples of coarse grained parallelization include slices， tiles and wavefront in the HEVC standard. Efficient implementation of these parallel options are described in [10] for slices， [11] for tiles and [12] for wavefront. Fine grained techniques usually consist of applying the Single Instruction Multiple Data （SIMD） paradigm at various levels of the encoding [13] and decoding stages [14].

As far as transcoding is concerned， a straightforward method is to first decode fully the input sequence， scale its resolution and then re?encode it. More efficient approaches target at utilizing the information already coded in the input， most noticeably the one concerning motion estimation， in order to reduce the search space when transcoding to another standard. Example works in the area include [15] where an H.264/AVC to HEVC transcoding architecture is presented that achieves a nominal speedup reaching 8x， when compared to re?encoding from scratch. If a bitrate change rather than a change in standard is needed， the process is often referred to as transrating. A survey on fast transrating methods can be found in [16]. In the experiments we obtained transcoding task weights by using the straightforward approach of re?encoding without using the information already coded. This was done both for reasons of simplicity and due to code availability （ffmpeg and x264 used）. However， based on the aforementioned research we scaled the values obtained to depict the case where a more efficient transcoder is used.

Concerning cloud transcoding， most works focused on providing job scheduling techniques at the level of a server cluster or a data center. In [7]， the authors considered the case of live video transcoding and proposed an integer linear program （ILP） formulation to tackle scheduling decisions. An online algorithm that schedules jobs among the servers of a datacenter with the target of satisfying delay requirements while using minimum energy was proposed in [17]. In [18] the scope was a single cluster and the optimization target was to keep the servers load balanced. In [19] an admission control algorithm was developed that differs or rejects requests that cannot be satisfied based on current workload. It is worth noting that this is the contrary approach to the one used in this paper for the case of edges， whereby it might be viable to reduce quality by over?assigning tasks to servers if the relevant benefits from edge processing are deemed sufficient. Finally， in [20] a combined caching and transcoding approach is discussed， whereby transcoding jobs are partially processed to allow for efficient caching. The target considered in this paper， i.e.， live transcoding excludes partial transcoding as an option. Caching and replication techniques in the cloud are surveyed in [21]， while [22] and [23] concern efficient video delivery.

Overall， compared to [7]， [17]， [18]， [19] and [20]， we differ in scope since we examine transcoding at edges while we view [21]， [22] and [23] as orthogonal to our approach. Perhaps the closest work in the literature is [24]， where system architecture for edge transcoding is described. Nevertheless， scheduling issues were not tackled in the manner done in this paper.

3 Problem Definition

We consider the case of a media provider receiving requests for live video casting， whereby the input stream must be transcoded into a set of output streams with different resolution， bitrate and quality demands. We consider two options for the set of transcoding tasks associated with each input. Either they are all assigned to a mini?datacenter existing at the edge of the network or they are all assigned to the backend main datacenter of the media provider. Clearly， if the tasks are processed at the edge， the processing workload at the backend datacenter is reduced and the network overhead for transmitting the input sequence is avoided.

Let the mini?datacenter consist of S servers， with Si denoting the ith of them， assuming a total ordering （1≤i≤S）. Each server has an associated processing capacity （let Ci）， which denotes the number of baseline transcoding tasks that can be processed concurrently at real time. Baseline tasks are the ones requiring the minimum power to process. Let Bj be the jth broadcast， assuming an ordering of the B total broadcasting events （1≤j≤B）. Similarly， let sj and dj be the arrival time and duration of Bj， respectively. Each broadcast entails a set of transcoding tasks. Let T be the total number of transcoding tasks for all broadcasts， and Tk be the kth such task， assuming a total ordering of them （1≤k≤T）. We represent whether Tk is a task of Bj or not， using a Boolean matrix A of B×T size， whereby Ajk=1 if and only if （iff） Bj has task Tk and 0 otherwise. Moreover， Wk depicts the relevant weight of Tk in processing terms over the baseline task. Put in other terms， Wk shows how much more computationally demanding Tk is， compared to the baseline scenario. Last， let X be an S×T Boolean matrix used to encode task server assignments as follows： Xik=1 iff Tk is assigned for processing at Si， otherwise Xik=0. We assume that once assigned， a task cannot be preempted and will remain for the whole duration [sj， ... ， sj+dj]. We consider that we want to optimize the system starting from a clean state （no task assignments exist） over a time frame divided into E equally sized slots （sj and dj values are now measured in time slot terms）. Let et be the tth such time slot， with a corresponding assignment matrix Xt. We typically formulate the problem as follows： Find all values in the E total matrices Xt， so that the objective function f given in （1） is maximized：

[f=t=1Ei=1Sk=1TXtik（1-Xt-1ik）]， （1）

subject to the following constraints：

[i=1Sk=1TAjkXtik-k=1TAjki=1Sk=1TAjkXtik=0， ?j， t=sj，] （2）

[Xtik=Xt+1ik， ?i，k， t|sj≤t

[i=1Sk=1TAjkXtik=0， ?j， t|tsj+dj，] （4）

[k=1TXtikWk≤Ci， ?i， t，] （5）

[i=1SXtik≤1， ?k，t]. （6）

The objective function encodes the tasks that will be assigned to the edge. Eqs. （2）-（6） give the main constraints of the problem. Constraint （2） states that either all tasks of a broadcast Bj will be assigned to the edge at the time the broadcast arrives or none. Constraint （3） enforces that the decision taken for a transcoding task at the time of its broadcast arrival remains for the duration of the broadcast. Constraint （4） ensures that neither before a broadcast arrival， nor after its end time， can a corresponding task be scheduled for edge transcoding. Constraint （5） dictates that a server can exceed its capacity at no point in time. Finally， （6） states that a task can only be scheduled at one server.

Clearly， the fact that broadcasts are known in advance reduces the applicability of the presented problem formulation to cases of prescheduled event covering， e.g.， sports. Nevertheless， the formulation provides a thorough definition of the optimization target and the related constraints. These remain the same both in the static problem variation presented and in the dynamic case. A last note concerns complexity. It can be shown that the relevant decision problem is NP?complete since the processing capacity constraint at the servers effectively introduces a （0， 1） Knapsack component. Next， we present heuristics for dynamic scheduling of transcoding tasks at the network edge.

4 Scheduling Heuristics

4.1 Scheduling with Tight Task QoS Requirements

The proposed heuristics tackle the dynamic version of the scheduling problem presented in the previous section. Specifically， upon the arrival of a broadcast request， the necessary transcoding tasks are defined. Then， they are sorted according to their weight and considered either in increasing order （MIN policy） or in decreasing （MAX policy）. Each task is assigned to a server （using one of the policies described in the sequel） provided the task computational demands can be met by the server as per （5）. If a suitable server is found for every transcoding task of the broadcast under consideration， the assignments are committed； otherwise， even if one task fails to find a hosting server， all the tasks are sent to the SMPs datacenter for processing. The assignment policies considered are based on the well?known bin?packing heuristics：

·Best Fit （BF）： Select the server where the remaining capacity， left after task assignment， is the minimum possible.

·Worst Fit （WF）： Similar to BF only that the server with the maximum remaining capacity will be selected.

·First Fit （FF）： The first server where the task fits will be selected.

The corresponding heuristics are named after the order with which the task list is considered and the packing method followed. For instance MAX?BF refers to the heuristic that considers the heaviest task first and assigns it using Best Fit.

4.2 Scheduling with Relaxed Task QoS Requirements

The motivation for the relaxed QoS case is the following. Assume that all but one task of a broadcast could fit to the available servers of the edge. With strict QoS requirements， none of these tasks will be assigned. However， it might be possible to assign the remaining task to one server so that its processing capacity is exceeded by a very small margin. In practice， this means that all the tasks processed by this server will exhibit a small quality drop. For instance， if a broadcaster transmits at 30 fps （frames per second） then a 3.3% drop at the processing rate of one of its transcoding tasks means that roughly the output stream will be at 29 fps. Depending on decoder characteristics， such a drop might not even be noticeable by a human viewer. Assuming that p denotes the maximum percentage of allowable performance drop， （5） becomes：

[k=1TXtikWk≤（1+p）Ci， ?i， t]. （7）

The heuristics first attempt to allocate all the tasks of a broadcast as per Section 4.1. In case a task does not fit， it is considered for assignment using （7） as server capacity constraint and one of the below described policies.

·Min Quality Decrease （MQD）： Selects the server that incurs the minimum proportional capacity violation （equivalent to asking for the minimum quality penalty for its hosted tasks）.

·First Fit （FF）： The first server where the task fits as per （7） will be selected.

·View Weighted Penalty （VWP）： Weights the quality penalty of each task by the number of its viewers. The server with the minimum aggregated weighted quality penalty value is selected.

5 Experiments

5.1 Setup

To simulate broadcasting activity， we used the same dataset from Twitch as the one described in [7]. We kept the portion of the dataset representing one day activity （Jan. 6th， 2014）. We then filtered it by deleting entries with broadcasts having no viewers and the broadcasts of resolution less than 220p. To keep the simulation time manageable we considered the following 5 resolutions： 240p， 360p， 480p， 720p and 1080p. In case a broadcast in the trace did not follow one of the previously mentioned resolutions， we clustered it to its closest matching. We assumed that a broadcast must be transcoded to all the resolutions that were lower than the one it used. Clearly， with this setting the maximum number of transcoding tasks incurred by a broadcast is 4， corresponding to a 1080p stream that must be downscaled to 720p， 480p， 360p and 240p. Upscaling was not considered in the experiments. Finally， for simulation purposes we assumed that all videos used 30 fps. Furthermore， the recorded in the dataset viewing demand was split equally among the resolutions used by a broadcast， i.e.， the input and all lower ones. Table 1 summarizes some of the dataset characteristics， while Fig. 2 plots the broadcasting job arrival rates as a histogram of a 1000 seconds （s） step. As it can be seen， the arriving jobs do not exhibit sharp peaks （at least with the used interval）， but the distribution is rather uniform. This favors job scheduling at edges since it makes sizing decisions for edges less demanding. However， duration of broadcasts does not follow a similar trend. As noted in Table 1， the difference between the average and maximum duration is two orders of magnitude， implying a heavy tailed distribution. This hinders scheduling decisions， since it means that duration estimation will be hard to achieve in the general case. For this reason， none of the scheduling heuristics described in Section 4 uses such estimates.