טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentHenig Asaf
SubjectThe Transcoders' Placement Problem over Multicast Networks
DepartmentDepartment of Computer Science
Supervisor Professor Dan Raz


Abstract

Scalable and efficient multicasting of multimedia information is a very challenging task. This is especially true in the emerging new Internet where users use devices such as smart phones and PDAs, a considerable amount of them are connected via wireless connections, and peer to peer applications are becoming more and more popular. In this new environment, the multimedia format that should be sent to different users varies considerably and sending a media stream to a set of users often involves transcoding of formats.

This work addresses the problem of controlling multicast streaming in this new environment by defining a framework in which transcoding can be done in internal network nodes, and not necessarily at the sender’s or at the receivers’ ends. In this framework the sender retrieves all the information regarding the transcoding abilities of the various nodes and the characteristics of the links. Then, it needs to decide how to broadcast the multimedia stream, in what formats, and where to perform the needed transcoding.

In this work we focus mainly on the algorithmic aspects and the computational complexity of the problem in hand using formal theoretic tools. We first formulate the problem of multicasting a media stream in a heterogenic environment as an optimization problem and show that it is NP-hard. Then we study the difficulty of approximating this problem both by proving approximation algorithms for different variants of the problem and by proving lower bounds on the possible approximability. We show that though the problem is hard to approximate in its general case, it is possible to find a close to optimal solution for the practical case where the number of relevant formats, supported in the system, is small.

Since efficient multimedia multicasting is a very practical problem we also study the actual performance of our algorithms using simulations. We compare our general case algorithm to the currently used approaches which allows transcoding only at the sender’s or at the receivers’ ends. Our simulations’ results indicate that performing transcoding at intermediate nodes is indeed efficient, and that our algorithm can find a much better streaming scheme than any other known paradigm.