Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Green Media: The Future of Wireless Multimedia Networks:Guest Editorial

By 2015, with the proliferation of wireless multimedia applications and services (e.g., mobile TV, video on demand, online video repositories, immersive video interaction, peer to peer video streaming, and interactive video gaming), and any-time anywhere communication, the number of smartphones and tablets will exceed 6.5 billion as the most common web access devices. Data volumes in wireless multimedia data-intensive applications and mobile web services are projected to increase by a factor of 10 every five years, associated with a 20 percent increase in energy consumption, 80 percent of which is multimedia traffic related. In turn, multimedia energy consumption is rising at 16 percent per year, doubling every six years. It is estimated that energy costs alone account for as much as half of the annual operating expenditure. This has prompted concerted efforts by major operators to drastically reduce carbon emissions by up to 50 percent over the next 10 years. Clearly, there is an urgent need for new disruptive paradigms of green media to bridge the gap between wireless technologies and multimedia applications.

Management Driven Hybrid Multicast Framework for Content Aware Networks

The need for better adaptation of networks to transported flows has led to research on new approaches such as content aware networks and network aware applications. In parallel, recent developments of multimedia and content oriented services and applications such as IPTV, video streaming, video on demand, and Internet TV reinforced interest in multicast technologies. IP multicast has not been widely deployed due to interdomain and QoS support problems; therefore, alternative solutions have been investigated. This article proposes a management driven hybrid multicast solution that is multi-domain and media oriented, and combines overlay multicast, IP multicast, and P2P. The architecture is developed in a content aware network and network aware application environment, based on light network virtualization. The multicast trees can be seen as parallel virtual content aware networks, spanning a single or multiple IP domains, customized to the type of content to be transported while fulfilling the quality of service requirements of the service provider.

Ownserver: sistema doméstico de prestação de serviços cloud

Neste trabalho foi considerada a possibilidade de incorporar serviços remotos, normalmente associados a serviços web e cloud computing, numa solução local que centralizasse os vários serviços num único sistema e permitisse aos seus utilizadores consumir e configurar os mesmos, quer a partir da rede local, quer remotamente a partir da Internet. Desta forma seria possível conciliar o acesso a partir de qualquer local com internet, característico nas clouds, com a simplicidade de concentrar num só sistema vários serviços que são por norma oferecidos por entidades distintas e ainda permitir aos seus utilizadores o controlo e configuração sobre os mesmos. De forma a validar que este conceito é viável, prático e funcional, foram implementadas duas componentes. Um cliente que corre nos dispositivos dos utilizadores e que proporciona a interface para consumir os serviços disponíveis e um servidor que irá conter e prestar esses serviços aos clientes. Estes serviços incluem lista de contactos, mensagens instantâneas, salas de conversação, transferência de ficheiros, chamadas e conferências de voz e vídeo, pastas remotas, pastas sincronizadas, backups, pastas partilhadas, VoD (Video-on Demand) e AoD (Audio-on Demand). Para o desenvolvimento do cliente e do servidor foi utilizada a framework Qt que recorre à linguagem de programação C++ e ao conjunto de bibliotecas que possui, para o desenvolvimento de aplicações multiplataforma. Para as comunicações entre clientes e servidor, foi utilizado o protocolo XMPP (Extensible Messaging and Presence Protocol), pela forma da biblioteca qxmpp e do servidor XMPP ejabberd. Pelo facto de conter um conjunto de centenas de extensões atualmente ativas que auferem funcionalidades como salas de conversação, transferências de ficheiros e até estabelecer sessões multimédia, graças à sua flexibilidade permitiu ainda a criação de extensões personalizada necessárias para algumas funcionalidades que se pretendeu implementar. Foi ainda utilizado no servidor a framework ffmpeg para suportar algumas funcionalidades multimédia. Após a implementação do cliente para Windows e Linux, e de implementar o servidor em Linux foi realizado um conjunto de testes funcionais para perceber se as funcionalidades e seus mecanismos funcionam corretamente. No caso onde a análise da performance e do consumo de recursos era importante, foram realizados testes de performance e testes de carga.

Les risques découlant de la diffusion sur les plateformes néomédiatiques du point de vue des producteurs audiovisuels

La diffusion sur les plateformes néomédiatiques d’œuvres audiovisuelles, comme les sites Internet des télédiffuseurs ou des webdiffuseurs, la vidéo sur demande, la télévision mobile ou la webdistribution, modifie les risques que les producteurs audiovisuels doivent gérer normalement sur les plateformes traditionnelles, comme la télévision. La mutation des risques découle de quatre sources en particulier, soit du marché, des pratiques d’affaires, des lois et règlements et des techniques elles-mêmes. Ces sources peuvent également induire des normes pouvant constituer un cadre juridique afin de moduler ou éliminer les risques. Le présent mémoire analyse les risques encourus lors de la diffusion sur les plateformes néomédiatiques d’œuvres audiovisuelles du point de vue des producteurs par l’entremise du processus de gestion de risques. Il identifie et recense ainsi les risques en mutation et les nouveaux risques auxquels les producteurs sont confrontés. Puis, les risques identifiés y sont définis et le cadre juridique est abordé dans le contexte de la mise en œuvre d’une stratégie de gestion de risques et des mesures afin d’atténuer ou d’éviter les risques encourus par les activités de production et d’exploitation des producteurs.

QoS evaluation of bandwidth schedulersin IPTV networks offered SRD fluidvideo traffic: a simulation study

IPTV is now offered by several operators in Europe, US and Asia using broadcast video over private IP networks that are isolated from Internet. IPTV services rely ontransmission of live (real-time) video and/or stored video. Video on Demand (VoD)and Time-shifted TV are implemented by IP unicast and Broadcast TV (BTV) and Near video on demand are implemented by IP multicast. IPTV services require QoS guarantees and can tolerate no more than 10-6 packet loss probability, 200 ms delay, and 50 ms jitter. Low delay is essential for satisfactory trick mode performance(pause, resume,fast forward) for VoD, and fast channel change time for BTV. Internet Traffic Engineering (TE) is defined in RFC 3272 and involves both capacity management and traffic management. Capacity management includes capacityplanning, routing control, and resource management. Traffic management includes (1)nodal traffic control functions such as traffic conditioning, queue management, scheduling, and (2) other functions that regulate traffic flow through the network orthat arbitrate access to network resources. An IPTV network architecture includes multiple networks (core network, metronetwork, access network and home network) that connects devices (super head-end, video hub office, video serving office, home gateway, set-top box). Each IP router in the core and metro networks implements some queueing and packet scheduling mechanism at the output link controller. Popular schedulers in IP networks include Priority Queueing (PQ), Class-Based Weighted Fair Queueing (CBWFQ), and Low Latency Queueing (LLQ) which combines PQ and CBWFQ.The thesis analyzes several Packet Scheduling algorithms that can optimize the tradeoff between system capacity and end user performance for the traffic classes. Before in the simulator FIFO,PQ,GPS queueing methods were implemented inside. This thesis aims to implement the LLQ scheduler inside the simulator and to evaluate the performance of these packet schedulers. The simulator is provided by ErnstNordström and Simulator was built in Visual C++ 2008 environmentand tested and analyzed in MatLab 7.0 under windows VISTA.

La rivoluzione del marketing televisivo tra internet, applicazioni e web broadcasting

In questa tesi ci focalizzeremo sul connubio TV ed internet che rivoluzionerà l’erogazione dei servizi verso i telespettatori e di conseguenza il marketing pubblicitario in questo contesto. Partiremo dalla storia della televisione in Italia e dei dispositivi TV per poi analizzare i primi fenomeni di utilizzo televisivo del canale web e la conseguente nascita dei primi social media e servizi di video on demand. La seconda parte di questa tesi farà una larga panoramica sul marketing televisivo ed il web marketing, fino ad arrivare al punto di massima prossimità tra i due canali, ovvero l’advertising correlato ai contenuti video presenti sul web. Nella terza ed ultima parte analizzeremo le prime piattaforme di WebTV e servizi di internet television, per poi focalizzarci sui probabili risvolti e prospettive future sia a livello di fruizione dei contenuti che pubblicitario. Questo fenomeno avrà una netta influenza nel Marketing considerando che dal 1984 la TV è il mezzo che raccoglie la maggior parte degli investimenti pubblicitari ed il web è il media in maggiore ascesa a livello di penetrazione e popolarità negli ultimi anni.

The Changing Environment of Audiovisual Media. New Technologies, New Patterns of Consumer/Business Behaviour and Their Implications for Audiovisual Media Regulation

Digital TV offers of 200 channels and 500 video-on-demand films, podcasting, mobile television, a new web blog being created every two seconds - these are some of the factual elements depicting contemporary audiovisual media in the digital environment. The present article looks into some of these technological advances and sketches their implications for the markets of media content, in particular as newly emerging patterns of consumer and business behaviour are concerned. Ultimately, it puts forward the question of whether the existing audiovisual media regulatory models, which are still predominantly analogue-based, have been rendered obsolete by the transformed (and continually transforming) digital environment.

Cloud-based Orchestration of Multimedia Services and Applications

The Mobile Cloud Networking project develops among others, several virtualized services and applications, in particular: (1) IP Multimedia Subsystem as a Service that gives the possibility to deploy a virtualized and on-demand instance of the IP Multimedia Subsystem platform, (2) Digital Signage Service as a Service that is based on a re-designed Digital Signage Service architecture, adopting the cloud computing principles, and (3) Information Centric Networking/Content Delivery Network as a Service that is used for distributing, caching and migrating content from other services. Possible designs for these virtualized services and applications have been identified and are being implemented. In particular, the architectures of the mentioned services were specified, adopting cloud computing principles, such as infrastructure sharing, elasticity, on-demand and pay-as-you-go. The benefits of Reactive Programming paradigm are presented in the context of Interactive Cloudified Digital Signage services in a Mobile Cloud Platform, as well as the benefit of interworking between different Mobile Cloud Networking Services as Digital Signage Service and Content Delivery Network Service for better performance of Video on Demand content deliver. Finally, the management of Service Level Agreements and the support of rating, charging and billing has also been considered and defined.

Content Delivery System for Optimal VoD Streaming

The demand of video contents has rapidly increased in the past years as a result of the wide deployment of IPTV and the variety of services offered by the network operators. One of the services that has especially become attractive to the customers is real-time video on demand (VoD) because it offers an immediate streaming of a large variety of video contents. The price that the operators have to pay for this convenience is the increased traffic in the networks, which are becoming more congested due to the higher demand for VoD contents and the increased quality of the videos. As a solution, in this paper we propose a hierarchical network system for VoD content delivery in managed networks, which implements redistribution algorithm and a redirection strategy for optimal content distribution within the network core and optimal streaming to the clients. The system monitors the state of the network and the behavior of the users to estimate the demand for the content items and to take the right decision on the appropriate number of replicas and their best positions in the network. The system's objectives are to distribute replicas of the content items in the network in a way that the most demanded contents will have replicas closer to the clients so that it will optimize the network utilization and will improve the users' experience. It also balances the load between the servers concentrating the traffic to the edges of the network.

Popularity based distribution schemes for P2P assisted streaming of VoD contents

The Video on Demand (VoD) service is becoming a dominant service in the telecommunication market due to the great convenience regarding the choice of content items and their independent viewing time. However, it comes with the downsides of high server storage and capacity demands because of the large variety of content items and the high amount of traffic generated for serving all requests. Storing part of the popular contents on the peers brings certain advantages but, it still has issues regarding the overall traffic in the core of the network and the scalability. Therefore, we propose a P2P assisted model for streaming VoD contents that takes advantage of the clients unused uplink and storage capacity to serve requests of other clients and we present popularity based schemes for distribution of both the popular and unpopular contents on the peers. The proposed model and the schemes prove to reduce the streaming traffic in the core of the network, improve the responsiveness of the system and increase its scalability.

P2P assisted streaming for low popularity VoD contents

The Video on Demand (VoD) service is becoming a dominant service in the telecommunication market due to the great convenience regarding the choice of content items and their independent viewing time. However, due to its high traffic demand nature, the VoD streaming systems are faced with the problem of huge amounts of traffic generated in the core of the network, especially for serving the requests for content items that are not in the top popularity range. Therefore, we propose a peer assisted VoD model that takes advantage of the clients unused uplink and storage capacity to serve requests for less popular items with the objective to keep the traffic on the periphery of the network, reduce the transport cost in the core of the network and make the system more scalable.

A survey on usage of mobile video in Australia

The growth of powerful entertainment functions of mobile devices, in particular mobile video, has recently attracted much attention. Studies on mobile TV, one form of mobile video, have been conducted in many countries. However, little research focuses on the holistic usage of mobile video. To understand the features of such usage, we conducted an online survey in Brisbane, Australia, during the first half of 2010. Our findings reveal similarities and diversities between usage of mobile TV in particular and mobile video on the whole. The results could aid in improving the design of future studies, with a view to ultimately increase user satisfaction.

Impact of region-of-interest video coding on perceived quality in mobile video

Effective streaming of video can be achieved by providing more bits to the most important region in the frame at the cost of reduced bits in the less important regions. This strategy can be beneficial for delivering high quality videos in mobile devices, especially when the availability of bandwidth is usually low and limited. While the state-of-the-art video codecs such as H.264 may have been optimised for perceived quality, it is hypothesised that users will give more attention to interesting region/object when watching videos. Therefore, giving a higher quality to region of interest (ROI)while reducing quality of other areas may result in improving the overall perceived quality without necessarily increasing the bitrate. In this paper, the impact of ROI-based encoded video on perceived quality is investigated by conducting a user study for varous target bitrates. The results from the user study demonstrate that ROI-based video coding has superior perceived quality compared to normal encoded video at the same bitrate in the lower bitrate range.