  Video streams usually have to be transcoded to match the characteristics of
viewers' devices. Streaming providers have to store numerous transcoded
versions of a given video to serve various display devices. Given the fact that
viewers' access pattern to video streams follows a long tail distribution, for
the video streams with low access rate, we propose to transcode them in an
on-demand manner using cloud computing services. The challenge in utilizing
cloud services for on-demand video transcoding is to maintain a robust QoS for
viewers and cost-efficiency for streaming service providers. To address this
challenge, we present the Cloud-based Video Streaming Services (CVS2)
architecture. It includes a QoS-aware scheduling that maps transcoding tasks to
the VMs by considering the affinity of the transcoding tasks with the allocated
heterogeneous VMs. To maintain robustness in the presence of varying streaming
requests, the architecture includes a cost-efficient VM Provisioner. This
component provides a self- configurable cluster of heterogeneous VMs. The
cluster is reconfigured dynamically to maintain the maximum affinity with the
arriving workload. Results obtained under diverse workload conditions
demonstrate that CVS2 architecture can maintain a robust QoS for viewers while
reducing the incurred cost of the streaming service provider up to 85%
