ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

QoS-aware Video Transcoding Service Composition Process in a Distributed Cloud Environment

Nawaf O. Alsrehin
Graduate Teaching Assistant, Dept. of Computer Science, College of Engineering, Utah State University, Logan, Utah, USA
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

In this paper, we address the problem of selecting and composing video transcoding services in a distributed cloud environment. One of the challenging issues for video transcoding service composition is how to find the best transcoding path to route the data flow through while satisfying the viewer requirements and specifications. In a cloud environment, video transcoding service providers provide different video transcoding services that have similar functionality (i.e., format conversion), but with different Quality of Services (QoS) specifications. Since the combination of the QoS specifications, such as frame size, frame rate, video bit rate, and transcoding delay might affect the end user’s experience in non-intuitive and subjective way and also might affect the delivering of a high quality video content over any type of network, we propose a QoS-aware model to select and compose the best video transcoding services to satisfy hard constraints on the input and output video formats and comes as close as possible to satisfying soft constraints on the QoS. This model uses an aggregate function to evaluate the QoS for each transcoding service and for each viewer request to explore the best composition path. In this paper, we adapt the Simulated Annealing (SA) algorithm and the Genetic Algorithm (GA) as candidate solutions to help in the composition process. The SA/GA algorithms provide multi-constraints QoS assurance for video transcoding service composition. They also support directed acyclic graph composition topology. We have implemented a prototype of the proposed algorithms and conducted experiments using small-, medium-, and large-scale graphs of video transcoders and sample viewer requests to measure the performance and the quality of the results. The experimental results show that the SA outperforms the GA in terms of performance and success ratio for small-scale graph, while GA outperforms the SA algorithm in terms of performance for medium- and large-scale graphs. The success ratio for the SA and GA algorithms are close to each other for medium- and large-scale graphs. At the end, we provide several directions and suggestions for future work.

KEYWORDS

video transcoding services; quality of service; service selection; service discovery; video delivery system, cloud computing

I. INTRODUCTION AND BACKGROUND

In recent years, accessing video content has become more difficult for several reasons. First, the number of end-user wire and wireless devices, such as desktop computers, smart phones, tablets, laptops, …, etc, has increased dramatically, putting increased demands on video delivery systems. Cisco® predicts that there will be 50 billion devices connected to the Internet of Things by 2020 [1]. Second, the end-user devices themselves have better displays characteristics, computational power, and storage, enabling higher video quality, which in turn increases the demand and performance expectations for content delivery. For example, iPhone 6 supports 1080p HD video at 60 frames per second (fps) and SLO-MO video at 720p [2]. Third, as the video delivery systems grow, they tend to diversify and introduce more heterogeneity among the components. Fourth, the end-users demand more control of the Quality of Service (QoS), to accommodate different uses of videos. Finally, there has been an unprecedented explosion in the availability of video content and varieties of video formats. By 2018, Cisco® predicts that every second, nearly a million minutes of video content will cross the network and the IP video traffic will grow from 66% in 2013 of all the internet traffic consumers to 79% by 2018 [3]. This is just the beginning of a video flood that will inundate the internet. To allow any user to watch any video from any kind of display device over any type of network, any video delivery system must be able to transcode the original video content into a compatible format (i.e., codec) that meets bandwidth limitations, device-specific requirements, and end-user preferences. Video transcoding services are components within a delivery system that transform or convert video content from one format to another (e.g., from MPEG-2 to H.264). This transcoding process may also involve frame-size conversion, bit-rate conversion, or frame-rate conversion. These conversions are based on the end-user preference values. The transcoding process is usually done in cases where a target device (or playback software) does not support the original video’s format or has limited storage capacity, or in order to convert incompatible or obsolete data to a better-supported or modern format [4]. Fig. 1 depicts the general video transcoding process.
image
When an end-user wants to watch a cloud-based video through a viewer (i.e., video playback software), the viewer needs to request a stream for that video. That request includes: a) the required video-coding format, also called the video-compression format, and b) a desired QoS that specifies a hoped-for video quality and a tolerable delay. A video coding format defines the structure of the video’s image and audio data. Some popular formats are H.264/MPEG-4, MJPEG (Motion JPEG), WMV, and DivX, but there are over 20 in common use today [5]. A codec is a piece of software that can encode video data into a particular format or decode a video from that format. A codec’s name is often used as a synonym for the format with which it works.
In general, frame size, frame rate, video bit rate, and audio sampling rate characterize the quality of a video and part of QoS specifications [6]. However, since the audio portion of the video accounts for only a small portion of the data, it is often not considered in QoS-related decisions. When dealing with streaming, a desired QoS may also include a constraint on the amount of delay that the viewer is willing to tolerate in the stream. Even though the delay does not directly characterize a video’s quality, it does characterize a video stream and it affects the end user’s experience. So, in this paper, we limit the QoS properties to: frame size, frame rate, video bit rate, and the average transcoding delay.
A viewer’s desired QoS will be determined based on user preferences, viewer’s window size, device capabilities, power-savings setting, network bandwidth, and other device-specific factors. For example, a 78.0" Diagonal UHD display device requires around 80Mbps video bitrate [7] while a 5.5" iPhone 6 plus requires around 18Mbps video bitrate [8]. Optimal utilization of the overall video delivery system resources comes from successfully calculating the desired QoS values for a specific device, playback software, or network connection. These resources are either devicespecific resources, such as the computational power and the internal buffers, or network-specific resources, such as network bandwidth. Incorrect calculation of these values might negatively impact the end-user’s subjective perception of the video. For example, asking for higher video bitrate for a device that has low computational power or low network bandwidth might make the device much slower than usual and the video might look jerky. In contrast, asking for low video bitrate while the device has a high computational power and network bandwidth may generate low video quality and negatively affect the user experience. Therefore, calculating the right QoS for a video will entirely change the user experience regarding video quality. How a viewer computes a desired QoS is an interesting human-factors and device-management problem, but it is outside the scope of this paper.
In general, this paper deals with the overall problem of delivering an original video in some format with a particular quality to a viewer who wants that video in a different format and with a specific QoS. There are two parts to this overall problem: a) transcoding or converting an original video to the desired format and quality while satisfying a delay constraint, and b) streaming that video to the viewer. The conversion may occur in its entirety before the streaming begins (e.g., Amazon Elastic Transcoder [9]), or it may be integrated into the streaming process (e.g., Akamai Media Content Delivery [10]). This paper focuses on the conversion process and, except for managing the delay; it doesn’t matter whether the conversion occurs before streaming or in a pipeline with the streaming.
In a cloud-based video transcoding environment, the most important task is to transcode any video content in such a way that a) the quality of the transcoded video come as close as possible to the requested QoS quality level, b) the enduser can play the transcoded video smoothly without video freezes, c) the transcoded video can be played with the shortest start-up time [11]. A better video quality comes from satisfying the requested QoS level. Video freezes occur due to unavailability of video frames while video startup time is the interval between the moment when the user selects the link and the moment when the video starts playing. The delay in start-up time is due to a delay in transcoding, streaming, or playing. In this paper, we focus on satisfying the requested QoS level while performing the transcoding process, which in turn helps in enhancing all the other factors.
Video transcoding for an on-demand video is a computer-intensive operation. Therefore, transcoding a large number of on-demand videos requires a large number of transcoding servers. Similarly, a large amount of disk space is required to store multiple transcoded versions for each source video [13]. Cloud computing provides computing and storage resources under the pay-per-use business model [12]. Infrastructure as a Service (IaaS) such as Amazon Elastic Computing Cloud (EC2)1 provides the computing resources through Virtual Machines (VM) by dynamically creating scalable clusters of servers. Similarly, Amazon Simple Storage Service (S3)2 provides the storage resources. EC2 can be used to virtually create scalable clusters of video transcoding servers that hold thousands of video transcoding services, and similarly S3 can be used to store both the original source video and the multiple transcoded versions. In a cloud environment, video transcoding can be performed in several different ways; for example, it is possible to map the entire video stream to a dedicated VM to transcode the entire stream, or split the video streams into smaller segments and independently transcode each of them in different VMs [13]. Regardless of which transcoding approach is used; guaranteeing the QoS level of the transcoded video requires selecting and composing the best video transcoding services from a pool of available ones, based on the viewer requirements and specifications to perform the transcoding process.
Software as a Service (SaaS) is a model where the customers can access the services via the internet without paying attention to how these services are maintained. The service providers are responsible for maintaining these services. In this paper, we assume that video transcoding functionalities are available as services, which are provided by service providers. A piece of software that converts a video from one coding format and quality to another format and quality is called a transcoding service or simply a transcoder. A cloud-based video delivery system may have thousands of different transcoders. If the delivery system has some transcoders that map from the requested video’s original coding format to the viewer’s desired format, which we called compatible transcoders, then the problem becomes one of best selection, where the system must choose a transcoder with a transcoding function whose output closely matches the desired QoS. If the delivery systems do not have any compatible transcoders, the system will need to convert the original video into an intermediate format(s) before converting into the required format. In this case, the problem becomes one of composing multiple best selections. In this paper we focus on a QoS-aware video transcoding service composition problem given input and output specifications.
Amazon Elastic Transcoder [9] is a video transcoding service provider that provides the transcoding functionality in the cloud. There are over 30 such providers today [14]. Many of the available video transcoding services provide the same functionality (i.e., format conversion), but with different QoS values. So, the challenge is how to select the best video transcoding services whose output closely matches the desired QoS, then compose these services together in a chain fashion, to satisfy the viewer requirements and specifications. Service composition is known to be an NP-hard problem and can be modeled as a multi-dimension, multi-choice, knapsack problem (MMKP) [15]. In this paper, we present a QoS-aware video transcoding service composition process in a distributed cloud environment where the video transcoding services are distributed in the cloud. In the composition process, we adapt the Simulated Annealing (SA) algorithm and the Genetic Algorithm (GA), which are generic probabilistic meta-heuristic learning algorithms to solve the combinatorial multi-objective optimization problem. They help in locating a very good state that is a good approximation to the global optimum of a given function in a large search space [16] [17].
Benefits of composing multiple transcoder in a chain fashion are: a) the final transcoded content would be exactly the same as if the transcoding had been done in one step, b) more complicated transcoding processes can be done even with a limited number of transcoders, c) the computations could be distributed among different processing units, d) improved the client QoS level while properly scaling with number of clients, e) provide a clear separation between video contents and the transcoded ones, and f) generate more powerful applications with more complex functionalities because the functionality offered by individual services is limited [20].
Manual composition of services is time consuming, error prone, generally hard and not scalable. Therefore, many fully or partially automatic service composition approaches have been investigated [15]. Service composition involves creating composite services by combining different services to provide a new value-added service [15]. It does not only improve reusability of service components, but also enables rapid development of new complex applications and requirements [18] . Composing the best transcoders is an open problem to date; there are similar composition problems in other domains, like web-services, that have been heavily investigated [15]. Section II reviews this related work and categorize them into five different groups.
Section III formally defines fundamental concepts that are related to this problem domain, such as video and transcoding service. In Section IV, we present a general model for cloud-based video delivery system independent of any particular video transcoding composition algorithm. We use this model as a framework to evaluate our adaptation to the SA and GA algorithms, which we introduce and describe them in sections V and VI, respectively.
We select and adapt the SA and GA algorithms to the video transcoding service composition problem domain due to several reasons: a) SA and GA have been widely used by researchers to solve many optimization problems, b) SA and GA algorithms have low initial cost, c) SA avoids getting stuck in local optima [16], d) GA has been widely and efficiently used in a cloud-based service composition research [19].
Section VII discusses the evaluation results, which include two kinds of experiments. The first experiment focuses on sensitivity analysis of a) the SA algorithm’s parameters and b) the GA algorithm’s parameters. The results of this experiment show that for small-scale scenarios, the SA algorithm finds optimal solutions, while for medium- and largescale scenarios; the GA algorithm outperforms the SA algorithm in finding near optimal solutions. In the second experiment, we focus on evaluating the proposed algorithms in terms of success ratio. Basically, we focus in this experiment on the quality of the results (i.e., how well the proposed algorithms generate results). This experiment shows that the SA algorithm is better than GA for small-scale scenario in terms of success ratio, while for medium- and large-scale scenarios, both the SA and GA generate close results in terms of success ratio. Finally, we discuss these results along with some recommendations and future directions from this preliminary study.

II. RELATED WORK

Revising literature related to composition process, we can classify the composition related work (but not limited to) into five groups, a) web-service composition related work, b) multimedia service composition related work, c) multimedia transcoding service composition related work, d) cloud-based service composition related work, and e) SA and GA based service composition related work. After that we discuss the limitations of some of the revising approaches.
A. Web-Service Composition Related Work
Web service composition has received considerable attention in recent years [15]. The problem of web service composition shares many of the same concerns found in the video transcoding composition problem. However, it is not easy to directly apply web service composition approaches into multimedia domain due to several reasons: a) the rich semantic and the complex internal structure of multimedia content itself, which is a combination of different forms (e.g., video, audio, or images), b) the size of the multimedia content makes the process of store, transcode, transport, and receive them very expensive, c) the dynamic characteristics of the multimedia applications, such as the continuous flow of multimedia streams, and c) the real-time processing requirements and the required QoS level [20].
Optimization algorithms like Linear Programming, Dynamic Programming, and Dijkstra-based algorithm m have been proposed as solutions to the web service composition problem [20]. Yan Gao et al. applied Dynamic Programming to solve the web service selection problem based on interface matching, and to dynamically select the optimum Web services for composite services [21]. However, their approach has some limitations, like the complexity of runtime decision. Rathore and Suman proposed a Local Selection and Local Optimization (LSLO) approach based on linear programming for optimal candidate service selection for composition [22]. In spite of the advantages of their approach, there are also some limitations. For example, they considered only the positive QoS properties. Avoiding negative QoS properties may result in inappropriate selections that violate viewer expectations. Tongguang proposed QoS-aware web service selection and composition approach based on Particle Swarm Optimization (PSO). The author provided a sequential QoS utility function to calculate the overall global best solution for finding the best service candidates for each service class [23]. The author also evaluated the performance of the proposed approach by experiments. In spite of the efficiency of the PSO approach, he did not evaluate the QoS assurance and user satisfaction rate.
B. Multimedia Service Composition Related Work
Xiaohui Gu and Klara Nahrstedt proposed a fully decentralized service composition framework called SpiderNet [24]. This framework supports a distributed multimedia service composition process with a statistical QoS assurance. The prototype implementation and the simulation results showed the feasibility and the efficiency of the SpiderNet. The QoS properties cover both the application and the network levels. However, video transcoding composing process requires a special handling due to the sequential dependency of the video transcoding services. Moreover, they do not consider frame rate and frame size as QoS properties.
Moissinac proposed a semantic-based automatic discovery and composition approach for multimedia adaptation service. The author focused on developing a semantic description of the basic adaptation services [25]. Service composition based on semantic description of multimedia services is a good approach. However, it needs to be extended by adding a complete description to all known categories of multimedia services.
Li et al. proposed a heuristic algorithm named Greedy-EF to solve the multimedia service composition problem in overlay networks [18]. This composition process finds the proper service paths and routes the data flows through, so that the resource requirements and the QoS constraints of the applications are satisfied. The simulation results showed that their proposed approach can achieve the desired QoS assurance as well as load balancing in multimedia service overlay networks. However, they considered only the response time and the availability of the services as QoS requirements. In addition, they assumed that the user knows the service classes he will request. In our proposed approach, the user has to know only the requested video file, his QoS specifications, and the required format or codec. After that, our proposed system will find the best service path and route the data flows through, so his/her QoS specifications are satisfied. Moreover, their QoS properties covered just only the application level.
Hossain proposed QoS-aware service composition approach for distributed video surveillance in which he used the ant-based algorithm to solve the multi-constraints QoS routing problem [26]. He validated his proposed approach through implementation and simulation. The implementation results showed the quality of the transcoded results in terms of Peak Signal-to-Noise Ratio (PSNR), while the simulation results also showed the performance and satisfaction rates.
C. Multimedia Transcoding Service Composition Related Work
For multimedia transcoding composition problem, Hossain and Saddik proposed QoS-aware multimedia transcoding service selection process that uses Ant Colony Optimization (ACO) algorithm for selecting the most suitable multimedia transcoding services for the desired composition process [20]. They used only average transcoding delay and frame rate as QoS properties for the selection process. In spite of the dynamicity of their proposed algorithm, it has more overhead than the genetic and traditional Dijkstra algorithms. Moreover, it has a long convergence time.
Alberto et al. introduced how the Service Oriented Architecture (SOA) paradigm can be applied to context-aware multimedia communications [27]. In addition, they presented a scoring function for selecting codec for a case of selecting transcoding functions taking into account different quality assessment metrics. They defined a new quality analyzer model to assign a score to each transcoding service. We think that they have some limitations: a) their evaluation focused just only on the audio codecs, b) their composition process based on the quality or the compression ratio for each codec, while the general video transcoding composition process handle the selection of the best implementation from different implementations of the same codec, c) their evaluation results are based on a single video/audio source with a specific configurations, evaluating their approach based on a set of video/audio sources with different configurations might help in generating more general results.
D. Cloud-based Service Composition Related Work.
Vaidas Giedrimas and Leonidas Sakalauskas proposed a simulated annealing and variable neighborhood search algorithms for automated software services composition in the cloud [28]. The experimental results showed that their proposed algorithm is able to approximate to best know solution in relatively short time. However, we think that their experiment is not enough to evaluate the efficiency and the effectiveness of the proposed approach. Moreover, they do not calculate the execution time.
Zhen et al. proposed an extensible QoS model to calculate the QoS values of service in cloud computing and a genetic-algorithm-based approach to compose services in cloud computing [29]. The experimental results showed that the proposed approach finds optimal solutions for small-scale scenarios. For larger-scale problems, it outperforms the integer programming approach. However, calculating the QoS values is done offline and the penalty factor in the fitness function is static.
E. SA and GA-based Service Composition Related Work
SA has been applied in many problem domains, such as the traveling salesman problem, job shop scheduling, multicast routing, service selection for composite web services, and many more [30]. To date, a few others have attempted to use simulated annealing in selecting multimedia transcoding services. G. Zhi-peng, et al. shows one of these applications [31]. They applied the simulated annealing-based genetic algorithm (QQDSGA) to efficiently select web services with excellent QoE. They defined a set of QoS criteria, which includes: service cost, execution time, availability and reliability. In addition, they defined a calculation model for each one of these criteria that considers the inconsistency of the attributes and the target direction. They also defined an objective function that makes the global QoS value for service composition the key element of the evaluation. For QoE, they have used five customer satisfaction degrees that indicate the general acceptability of the composite services based on customer expectation and environment. L. Arockiam and N. Sasikaladevi developed and compared the simulated annealing with the genetic algorithms as service selection algorithms [32]. They also concluded that the simulated annealing algorithm outperforms the genetic algorithm in selecting reliable services. Arockiam and Sasikaladevi developed a simulated annealing as a service selection algorithm for composite web services. Arockiam and Sasikaladevi considered reliability as a QoS parameter to maximize the non-functional characteristics of composite web services [33].
Amiri and Serajzadeh applied GA for QoS-aware web service composition; they considered the response time, execution cost, reputation, availability, and successful execution rate as QoS properties. They increased the performance of the algorithm and to escape from local optimum, they enhance the selection and crossover functions. The experiments showed the computation time of the algorithm is very low.
F. Limitations of Existing Approaches
Here we want to discuss the limitations of some of the existing composition approaches. First, most of the aforementioned approaches considered multimedia services in general without focusing on video transcoding services in particular. Second, some of the aforementioned approaches considered just only the QoS properties that are related to the application itself, or that are related to the network itself. However, few of them directly focus on the QoS properties that are related to video transcoding services such as video bit rate, frame size, frame rate, video transcoding delay, and aspect ratio. Third, some of the existing solutions are not readily applicable to the video transcoding composition problem due to the transcoding requirements and the inter-service dependency constraints between them. Fourth, to the best of our knowledge, there is no previous work for composing different video transcoding services in a distributed cloud environment based on application-specific QoS requirements using SA or GA algorithms.

III. PRELIMINARY DEFINITIONS

In this section we formalize the QoS-aware video transcoding service composition problem by introducing some definitions for the basic concepts that are related to the problem domain. Let’s start by defining the video.
image
WMV1, but with different output video characteristics. If an original video had a H.264 format and the viewer wanted a WMV1 format, all 1000 video transcoding functions would be compatible transcoders

IV. GENERAL CLOUD-BASED VIDEO DELIVERY SYSTEM

Fig. 2 shows a use case for cloud-based video delivery system where user A can upload any video to the cloud while user B can request and play that video using any device regardless of the original video format. If the original video format is not supported at the user B’s device or playback software, this video must be transcoded to a new format that the user B’s device supports. To allow any user to watch any cloud-based video from any kind of display device over any type of network, the cloud-based video delivery system must be able to transcode any video. Video transcoding is a computationally intensive operation and due to the limited computational power for the end-user’s devices; it may not be suitable to perform the transcoding process at the end-user side. Therefore, it is usually performed at the server-side [13].
image
On-demand video transcoding has many challenges: 1) it must be done on-the-fly in the real-time, 2) it must meet the viewer’s requirement and specification. In this paper, we will focus on the second challenge. Guarantee the viewer’s requirement and specification requires selecting the best video transcoding services, from a pool of available ones that satisfy the required QoS level to perform the transcoding process.
If the requested video is not available in the requested format, the cloud-based video delivery system should transcode the original video to the requested format and then streams the transcoded video to the end-user. If the cloudbased video delivery system does not have any compatible transcoders, the system will need to convert the original video into an intermediate format(s) before converting it into the required format. In this case, discovering these multiple transcoders and composing them into a chain fashion to meet the viewers’ requirement and specification is the challenge. We refer to this chain as a composition chain and we can formally define the composition chain as follows:
image
image
Based on the example given in Fig. 3, if the format of the original video is MPEG-2 and the end-user wants this video in DivX format and assume that the cloud-based video delivery system has just the following transcoders T1, T2, and T3 as follows: T1 transcodes from MPEG-2 to H.264, T2 transcodes from H.264 to MJPEG, and T3 transcodes from MJPEG to DivX. Each one of these transcoders (i.e., T1, T2, and T3) might have hundreds or thousands of video transcoding functions with different QoS values. Because the format of the requested video (i.e., MPEG-2) is different than the requested format (i.e., DivX), the cloud-based video delivery system must transcode the original video to the requested format. It is obvious that the cloud-based video delivery system that we provide in Fig. 3 has no compatible transcoder for the requested video and the requested format (i.e., no transcoder that directly convert from MPEG-2 to DivX). Therefore, the cloud-based video delivery system should discover the transcoders that meet the viewer requirements (i.e., the hard constraints). Based on the discovered transcoders, there will be three transcoders that participate in the composition chain in a sequential order, which means that there will be a three-level transcoding process as shown in Fig. 3.
In the three-level video transcoding composition chain that Fig. 3 presents, the original video is send to the T1 in which it transcodes the original video to generate a new video in a H.264 format, while T1 performs the transcoding process, it starts sending the transcoded frames to T2 to transcode these frames to MJPEG format, while T2 performs the transcoding process, it starts sending the transcoded frames to T3. Finally, when T3 starts receiving the transcoded frames, it performs the transcoding process to convert these frames to DivX, while T3 performs the transcoding process, it starts sending the transcoded frames to the streaming system that streams these frames to the end-user’s device. This process should be done on-the-fly in real-time. For best utilizing, each transcoder save its transcoded streams into a virtual storage device for later on requests. Assume that the cloud-based video delivery system has hundreds or thousands of each one of the above transcoders (i.e., T1, T2, and T3) and each one has different QoS specifications. The problem now is how we can select and compose these transcoding functions together in a way that guarantee the required QoS level during the transcoding process and guarantee the required QoS level of the video that is send to the end-user’s device. We will start describing the solution by first, describing a general model for on-demand cloud-based video distribution system in the following paragraphs.
Fig. 4 shows a general model for on-demand cloud-based video distribution system, which contains cloud-based video delivery system. Cloud-based video delivery system consists of three main sub-systems: a) cloud-based service management system, b) cloud-based video transcoding system, and c) cloud-based video streaming system. In this paper, we focus on the cloud-based service management system and, specifically, on the service composition process.
image
In this model, all the available transcoders and their transcoding functions, which are provided from the service providers, are captured in a Service Registry. Step 1, which only needs to occur once after the Service Registry is
image
Once the best video transcoding functions that satisfy the viewer requirement and specifications have been discovered and identified, then the processes, represented by Steps 5 and 6, perform the actual transcoding and then streaming the transcoded video to the end-user’s device.

V. VIDEO TRANSCODING COMPOSITION PROCESS

In order to support real-time multimedia applications such as video/audio streaming, video-on-demand or video conferencing over any type of network; the desired QoS should be satisfied in addition to the basic video format conversion. Notice that Step 4 shown in Fig. 4 does not completely describe the composition process. In this section, before start explaining the composition process, we want to assume that the cloud-based video delivery system is running in the cloud. Hence, the cloud-based video transcoding system that holds hundreds or thousands video transcoding functions are running in the cloud as well. In addition, we assume that these transcoding functions are services running in a number of virtual machines in the cloud.
Let us consider a video transcoding function network as a directed acyclic graph, G T, L ; so, we can formally define this graph as follows.
image
image
image
image
In general, we can summarize the video transcoding service composition process into the following steps:
Step 1: Calculate the cost of each video transcoding function using (5) and calculate the viewer request cost using (6).
Step 2: Analyze the viewer request and discover the �� transcoders as shown in the abstract view in Fig. 5.
Step 3: Discover the video transcoding functions for each transcoder. Each transcoder ���� might have ���� transcoding functions.
image

VI. SIMULATED ANNEALING ALGORITHM FOR VIDEO TRANSCODING COMPOSITION PROCESS

In this section, we discuss how we adapt the SA algorithm into the video transcoding service composition problem domain. SA algorithm models the annealing process in metallurgy. It involves heating up the material and then cooling it in a controlled way that helps in increasing the size of its crystals and reducing their defects, thus reaching a state with lower system energy [16].
We divide the SA algorithm into six parts: a) parameters configuration, b) the initial solution, c) the cost function, d) the neighboring function, e) the acceptance probability, and f) the cooling schedule. The following sub-sections describe these parts in more details.
A. Parameters configuration
In this part, we configure the parameters of the SA algorithm, mainly, the temperature and the cooling rate. Usually, the algorithm starts with a high temperature value, and then this value starts decreasing based on the cooling schedule to reach the lowest temperature. The cooling schedule is user defined and it is usually low enough to reflect the slow cooling. Function 1 describes this configuration process.
B. The Initial solution
After configured the parameters, we get to the initial solution. In the initial solution, we randomly select a video transcoding function from each level in the directed video transcoding function graph. We ensure the feasibility of the initial solution by adding the source and the destination to it. Function 2 describes the initialization process. A feasible solution is a solution or a composition path that satisfies the hard constraints based on the viewer requirements.
C. The cost function
Function 3 describes how we calculate the cost of any path. Basically, the cost of any path is the summation of cost of the links that are participating in that path. In essence, we use (7) to calculate the cost of any path.
D. Generating the neighboring path
Generating the neighboring solution or path based on the current one is one of the main parts in the SA algorithm. Function 4 shows the neighbor function in which we randomly select a neighbor path to the current one from the directed acyclic video transcoding function graph. This function randomly selects a video transcoding function (i.e., node) from each level in the graph and then composing them together to generate a feasible path. We ensure the feasibility of the new neighboring path by adding the source and the destination nodes to it. Therefore, the new neighboring path satisfies the viewer request’s hard constraints.
E. The acceptance probability
After generating the neighboring path, we use the acceptance probability function to calculate the acceptance probability based on the combination of the currentCost, newCost, userCost, and the ��������. This function compares the cost of the two paths with respect to the userCost. We described above how we calculate these costs. The acceptance probability function helps the SA algorithm to intelligently accept worse solutions and escape from the local optima that are worse than the global one [36]. The acceptance probability is a non-negative real number between 0 and 1. Function 5 describes the acceptance probability function.
F. The cooling schedule
The cooling schedule is a schedule that represents the decreasing value of the temperature. The temperature value should be decreased slowly and it depends on a pre-defined user value. Line 16 in Algorithm 1 shows the cooling schedule that we used.
image
image
image

VII. GENETIC ALGORITHM FOR VIDEO TRANSCODING COMPOSITION PROCESS

In this section, we discuss how we adapt the GA algorithm into the video transcoding service composition problem domain. GA is a meta-heuristic searching algorithm used to generate useful solutions to the optimization problems in a large search space. It depicts the biological evaluation of genes and chromosomes. GA works on a search space called population that contains a set of randomly generated solutions called chromosomes. After £ iterations, this population is evolved toward a better state. Each chromosome has a fitness value that defines the quality of the solution. GA uses adaptive search strategy in which it evolves the population by finding a set of best solutions, and then performs the crossover operation to create a new generation or population. The weaker candidates get less chance to be in the new generation while the best candidates from the previous generation are moving to the new generation. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached.
In video transcoding service composition problem domain we used the graph to represent the search space. The population represents a set of composition paths. Each chromosome represents a composition path. We calculate the fitness of each chromosome by using (7). Similarly, we can divide the GA algorithm into three parts: a) configuration part, b) initialization, and c) the loop part, in the following sub-sections, we will describe each part in details.
A. Parameters configuration
In this part, we configure the parameters of the GA algorithm, mainly, the population size and the number of iterations. These parameters are user defined and their values depend on the problem domain and size. Function 6 describes this configuration process.
B. The Initialization
After configured the parameters, we get to the initialization step. In this step, we create a population which contains a set of video transcoding composition paths that are stored in an array structure. The size of this array depends on the population size which is a user defined value from the previous configuration step. Each element in this array represents a feasible video transcoding composition path. Function 7 describes the initialization process.
C. The Loop
In this part, we used a for-loop structure that iterate £ times, the value of the £ is a user-defined value based on the previous configuration step. For each iteration, we evolve the population by generating a new population from the previous one. Function 8 describes the evolving process. Evolving the population requires randomly selecting two parents and performs the crossover operation to generate a new child. Each one of the parents and the child represents a composition path. Selecting each parent requires generating a new population that contains �� randomly selecting composition paths (�� is 5 in our proposed algorithm), and then finds the path that has the highest fitness value (i.e., the path that has the lowest cost value). Function 10 describes the process of how the GA randomly creates a path. We calculate the fitness value for each composition path by taking the absolute difference value between the existing path’s cost and the viewer request’s cost. Function 9 describes how we calculate the fitness value.
After generating new parents, we perform the crossover process. This process requires selecting a random number between 0 and the path size, then dividing each parent into two parts based on the selected random number. After that, merges the first part of parent1 with the second part of parent2 to generate a new child composition path. Function 11 describes this crossover method and Fig. 6 depicts the crossover process. After generating a new child from his parents, then we save this child in the current population and then repeat the whole process �������������� times. The crossover process helps in creating a new path that might have a better fitness value than his parents.
Algorithm 2 shows our adaptation to the GA algorithm in which it iterate £ times to find a near-optimal path. As we mentioned above and in each iteration, we evolve the current population until the termination condition is satisfied, finally, we return the best video transcoding path as an output from the GA algorithm.
image
image

VIII. EVALUATIONS AND DISCUSSION

In this section, we evaluate our adaptation to the SA/GA algorithms through experiments. In the first experiment we focus on: a) the sensitivity analysis of the parameters of the SA algorithm, b) the sensitivity analysis of the parameters of the GA, and c) analyzing the execution time for both of them. Then we provide a discussion and analysis that compare these evaluation results.
In the second experiment, we focus on the quality of the results. In other words, how well the proposed algorithms generate results. To measure their quality results, we calculate the success ratio of the SA algorithm and compare it with the GA algorithm’s success ratio. Finally, we provide a discussion regarding the limitations and some possible extensions of our work.
A. Configuration
For these experiments, we use Java JDK 1.8 via IDE Eclipse Kepler service release 2 to implement our adaptation to the SA and GA algorithms and other utility classes. The evaluation is done using a desktop computer that has an Intel Core i5 CPU 3.30 GHz; 8 GB RAM, and runs Windows 7 Professional.
B. Setup
To evaluate our adaptation to the SA/GA algorithms, we create the following groups of video transcoding functions; these video transcoding functions cover some of the common video characteristics, Table 2 shows a number of them.
The descriptions of these groups are presented in Table 3. Each group represents a graph which contains set of nodes and links as we described above. The nodes are the video transcoding functions and the links are the edges that connect these nodes. Each group has a set of levels. Each level represents a transcoder (i.e., set of video transcoding functions that convert from one codec to another). For example, group A has two levels (i.e., the first level converts from MPEG- 2 codec to H.264 codec and the second level converts from H.264 codec to MJPEG codec). Group A contains two transcoders; each one has 36 video transcoding functions. Therefore, this group contains 72 video transcoding functions. Each group (i.e., graph) also contains two other nodes, the source and the destination. The source node represents the original video content and the destination node represents the transcoded video based on the viewer requested format.
image
C. Sensitivity analysis of the parameters
image
image
image
image
Based on the results that are shown in Tables 4, 5, 6, and 7, we can conclude that:
 SA can find the optimal results for small groups or graphs and it can find good enough results for medium or bigger groups or graphs within a small duration of time.
 GA can find near-optimal results for medium or bigger groups. However, it takes very long time.
D. Success ratio
In this experiment, we focus on evaluating the proposed approaches in terms of success ratio. Then, we compare the success ration of the SA algorithm with the success ratio of the GA algorithm. Formally we can define the success ratio as follows:
image
where Sr represents the success ratio, α represents the total number of QoS criteria that are satisfied, and β represents the total number of the QoS criteria that we measure (i.e., the total number of QoS criteria is 6). We provide a range of user satisfactions: 100%, 90%, and 80%. The 100% means that the end-user requests a 100% satisfaction on all the QoS criteria, which means that the end-user requests a video transcoding functions that are 100% compatible with his QoS requirements. For example, if the user wants a 25 fps as a frame rate and he requests a 100% satisfaction rate, we count this QoS as a satisfied QoS criterion if and only if the algorithm generates a path that has the last video transcoding function in this path generates exactly 25 fps as a frame rate. Similarly, the 90% satisfaction rate means we count this QoS criterion as a satisfied QoS criterion if and only if the algorithm generates a path that has the last video transcoding function in this path generates a frame rate between 22.5 and 27.5, which means if the viewer request a 90% satisfaction rate, he can accept any frame rate between the above range (i.e., 225 and 27.5).
image
image

IX. LIMITATIONS AND FUTURE DIRECTION

Real-time video transcoding for on-demand videos requires transcoding the video content on-the-fly and in realtime. Satisfying the requested QoS level during the transcoding process requires selecting and/or composing several video transcoding functions together in a chained fashion. Efficient selection/composition processes requires more efficient approaches. The proposed approaches still have some limitations, such as low performance and quality results. However, this is just the beginning to propose robust video transcoding service composition approaches in cloud computing. In addition to the current application specific QoS, future work may focus on adding the network QoS to the composition process. Also, we are planning to enhance the performance of these proposed algorithms by further implementation improvement. More possible future directions would be to build a complete cloud-based video delivery system, which includes both video transcoding and streaming subsystems, based on the viewer requirements and preferences.

X. CONCLUSION

Delivering real-time video content over any type of network is becoming a necessary requirement. During the
delivery process, the original multimedia content might be transcoding to meet the different viewer’s requirements and
preferences. Guarantee QoS during the transcoding process requires selecting and composing the best video
transcoding functions from a pool of transcoding functions. So, in this paper, we propose a video transcoding service
selection and composition approach, which introduce two candidate algorithms based on the simulated annealing and
the genetic algorithm, to satisfy the required QoS level and meet the viewer’s requirements. We have implemented a
prototype of the proposed algorithms and conducted experiments using small-, medium-, and large-scale graphs of
video transcoders and sample viewer requests to measure the performance and the quality of the results. The
experimental results show that the SA outperforms the GA in terms of performance and success ratio for small-scale
graph, while GA outperforms the SA algorithm in terms of performance for medium- or large- scale graph. The success
ratio for the SA and GA algorithms are close to each other for medium- or large-scale graph.

References

  1. C. D. Evans, "The Internet of Things: How the Next Evolution of the Internet Is Changing Everything," April 2011. [Online]. Available: http://www.cisco.com/web/about/ac79/docs/innov/IoT_IBSG_0411FINAL.pdf. [Accessed 19 March 2015].
  2. Apple, [Online]. Available: https://www.apple.com/iphone-6/. [Accessed 15 March 2015].
  3. Cisco, "Cisco Visual Networking Index: Forecast and Methodology, 2013–2018," 10 June 2014. [Online]. Available: http://www.cisco.com. [Accessed 11 January 2015].
  4. Wikipedia, "Transcoding," 6 January 2015. [Online]. Available: http://en.wikipedia.org/wiki/Transcoding. [Accessed 11 January 2015].
  5. Wikipedia, "Video Codec," 1 July 2014. [Online]. Available: http://en.wikipedia.org/wiki/Video_codec. [Accessed 11 January 2015].
  6. J. Cabasso, "Determining Video Quality," November 2008. [Online]. Available: http://www.aventuracctv.com/PDF/ATI_Video_Quality.pdf. [Accessed 24 January 2015].
  7. Samsung, [Online]. Available: http://www.samsung.com/us/. [Accessed 21 March 2015].
  8. Apple. [Online]. Available: https://www.apple.com. [Accessed 11 January 2015].
  9. Amazon, "Amazon Elastic Transcoder," [Online]. Available: http://aws.amazon.com/elastictranscoder/. [Accessed 11 January 2015].
  10. "Akamai," [Online]. Available: http://www.akamai.com/. [Accessed 24 January 2015].
  11. W. Zhu, C. Luo, J. Wang and S. Li, "Multimedia Cloud Computing," Signal Processing Magazine, IEEE, Vol. 28, No. 3, pp. 59-69, 2011.
  12. M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica and M. Zaharia, "A View of Cloud Computing," Communications of the ACM, Vol. 53, No. 4, pp. 50-58, April 2010.
  13. F. Jokhio, A. Ashraf, S. Lafond, I. Porres and J. Lilius, "Cost-Efficient Dynamically Scalable Video Transcoding in Cloud Computing," TUCS Technical Report, Finland, 2013.
  14. Wikipedia, "List of video transcoding software," 31 July 2014. [Online]. Available: http://en.wikipedia.org/wiki/List_of_video_transcoding_software. [Accessed 15 March 2015].
  15. D. G. Joseph and M. Moghaddam, "Service Selection in Web Service Composition: A Comparative Review of Existing Approaches," in Web Services Foundations, Springer New York, 2014, pp. 321-346.
  16. "Wikipedia," 15 Fabruary 2015. [Online]. Available: http://en.wikipedia.org/wiki/Simulated_annealing. [Accessed 15 March 2015].
  17. Wikipedia, "Genetic Algorithm," 6 April 2015. [Online]. Available: http://en.wikipedia.org/wiki/Genetic_algorithm. [Accessed 14 April 2015].
  18. W. Li, Y. Wang, C. Li, S. Lu and D. Chen, "A QoS-aware service selection algorithm for multimedia service overlay networks," in Parallel and Distributed Systems, 2007 International Conference on, Hsinchu, pp. 1-8, 2007.
  19. A. Jula, E. Sundararajan and Z. Othman, "Cloud computing service composition: A systematic literature review," Expert Systems with Applications, Vol. 41, No. 8, pp. 3809–3824, 15 June 2014.
  20. M. S. Hossain and A. E. Saddik, "QoS Requirement in the Multimedia Transcoding Service Selection Process," IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, Vol. 59, No. 6, pp. 1498-1506, 2010.
  21. Y. Gao, J. Na, B. Zhang, L. Yang and Q. Gong, "Optimal Web Services Selection Using Dynamic Programming," in Proceedings of the 11th IEEE Symposium on Computers and Communications (ISCC'06), pp. 365-370, 2006.
  22. R. Maya and S. Ugrasen, "Web Service Selection Algorithm for Dynamic Service Composition using LSLO Approach," in IEEE, Dhaka, Bangladesh, pp. 1-6, 2013.
  23. T. Zhang, "QoS-aware Web Service Selection based on Particle Swarm Optimization," Journal of Networks, Vol. 9, No. 3, pp. 565- 570, 2014.
  24. X. Gu and K. Nahrstedt, "Distributed multimedia service composition with statistical QoS assurance," IEEE TRANSACTIONS ON MULTIMEDIA, Vol. 8, No. 1, pp. 141-151, 2006.
  25. J.-C. Moissinac, "Automatic Discovery and Composition of Multimedia Adaptation Services," in The Fourth International Conferences on Advances in Multimedia, Chamonix, France, April 29, pp. 155-160, 2012.
  26. M. S. Hossain, "QoS-aware service composition for distributed video surveillance," Multimedia Tools and Applications, Vol. 73, No. 1, pp. 169-188, 2014.
  27. A. J. Gonzalez, J. Alcober, R. M. d. Pozuelo, F. Pinyol and K. Z. Ghafoor, "Context-aware multimedia service composition using quality assessment," in 2011 IEEE International Conference on Multimedia and Expo (ICME), Barcelona, Spain, pp. 1-6, 11-15 July 2011.
  28. V. G. a. L. Sakalauskas, "Simulated Annealing and Variable Neighborhood Search Algorithm for Automated Software Services Composition," in 35th International Convention on Information and Communication Technology, Electronics and Microelectronics , Opatija, Croatia, pp. 395-399, May 21-25,2012.
  29. Z. Ye, X. Zhou and A. Bouguettaya, "Genetic Algorithm Based QoS-Aware Service Compositions in Cloud Computing," Database Systems for Advanced Applications, lecture Notes in Computer Science, Vol. 6588, pp 321-334, April, 2011.
  30. B. S. a. P. Kumar, "A Survey of Simulated Annealing as a Tool for Single and Multiobjective Optimization," The Journal of the Operational Research Society, Vol. 57, No. 10, pp. 1143-1160, 2006.
  31. Z.-p. GAO, J. CHEN, X.-s. QIU and L.-m. MENG, "QoE/QoS driven Simulated Annealing-based Genetic Algorithm for Web Service Selection," The Journal of China Universities of Posts and Telecommunications, Vol. 16, No. 1, pp. 102–107, September 2009.
  32. L. Arockiam and N. Sasikaladevi, "Simulated Annealing Versus Genetic Based Service Selection Algorithms," International Journal of U- & E-Service, Science & Technology, Vol. 5, issue 1, p35, 2012.
  33. L. Arockiam and N. Sasikaladevi, "Simulated Annealing Based Service Selection Algorithm for Composite Web Service," International Journal of Advanced Research in Computer Science, Vol. 3, No. 2, p.132, March 2012.
  34. " Euclidean Distance," Wikipedia, 17 November 2014. [Online]. Available: http://en.wikipedia.org/wiki/Euclidean_distance#Squared_Euclidean_distance. [Accessed 6 11 2014].
  35. Jinshan Liu, Val´erie Issarny, "QoS-aware Service Location in Mobile Ad-Hoc Networks," in 5th International Conference on Mobile Data Managment MDM, Berkeley, CA, United States. pp. 224-235, 2004.
  36. Y. Xu, R. Qu and R. Li, "A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems," Annals of Operations Research, Vol. 206, No. 1, pp. 527-555, July 2013.
  37. Wikipedia, "Video Quality," 9 March 2015. [Online]. Available: http://en.wikipedia.org/wiki/Video_quality. [Accessed 21 March 2015].
  38. Wikipedia, "Video Quality," 14 July 2014. [Online]. Available: http://en.wikipedia.org/wiki/Video_quality. [Accessed 12 January 2015].
  39. W. D. J. C. Lianyong Qi, "Weighted principal component analysis-based service selection method for multimedia services in cloud," Springer Computing - Springer-Verlag Wien, 2014.