Host Recommendation in the Adaptive Distributed Multimedia Server

by Ottó Hutter, Tibor Szkaliczki and Balázs Goldschmidt

The Adaptive Distributed Multimedia Server (ADMS) developed at the Klagenfurt University is able to add and remove its components to and from different nodes of the network. This novel feature of the multimedia server enables the dynamic placement of the server components according to the current requests and Quality of Service (QoS) parameters of the network. Researchers at SZTAKI and the Budapest University of Technology and Economics have developed and implemented algorithms for the optimal placement of nodes for hosting the ADMS components in the network.

The Adaptive Distributed Multimedia Server (ADMS) was developed at the Klagenfurt University. It is an adaptive architecture for distributing video streams through networks covering large territories, and manages both network and node overloads by migrating and replicating server components in the network. The Host Recommendation module developed at the Budapest University of Technology and Economics (BUTE) is responsible for finding proper placement of the components according to the dynamically changing network parameters and client demands. SZTAKI is also participating in the development of the Host Recommendation module, in cooperation with the Klagenfurt University and BUTE. The module was tested as a stand-alone in a simulated network environment using randomly generated client requests, and is integrated into the ADMS at the Klagenfurt University for experimental tests.

First, we concentrated on where to put proxies in the network. The task was to find suitable locations for proxies of the distributed multimedia server, while maximizing the clients' satisfaction and minimizing the network load. The clients receive the same video in parallel.

Proxy and cache placement is a heavily studied area, but we found significant differences between the placement of Web proxies and ADMS proxies. In our case, the clients do not need accurate delivery but rather strict Quality of Service. Moreover, ADMS delivers huge media streams instead of small files. Nodes hosting server applications in a network are usually assigned in a static way. However, this approach is not applicable to the ADMS. The delivery of the data-streams with proper quality can start only after the placement of the server nodes. As a consequence, the dynamic reconfiguration of the server requires an automatic host recommendation whose running time should comply with strict time constraints. The Technical University of Budapest began work on this problem by analysing two methods, namely the greedy algorithm and the particle swarm algorithm. SZTAKI joined the server development by proposing and implementing two other methods (linear programming rounding and incremental algorithm) in 2003 and 2004.

The greedy approach was the first algorithm to be implemented, and has proven to be successful in many similar problems. The particle swarm algorithm is a kind of evolutionary algorithm. The incremental algorithm finds an initial solution as fast as possible and then the algorithm incrementally improves it, complying with the time constraints in order to approximate the optimal placement. Another approach is the linear programming rounding technique, where the integer programming formulation of the problem is derived, its linear programming relaxation is solved and the results are rounded.

We compared the results gained by running the implementations of the four proposed algorithms on different test networks. The greedy algorithm was clearly the worst of the four, while the particle swarm algorithm produced the best result. In terms of running time, the incremental algorithm was the best. There was no single winner from the particle swarm, linear programming and incremental algorithms; they can be applied in a smart combination.

After the stand-alone tests, our next task is to integrate this module into the ADMS and to test it in an experimental environment before the multimedia service becomes available for a wider audience. This year, the three partners participating in ADMS development started a new project to complete the server and to introduce pilot applications. This is running in cooperation with two SMEs within the framework of the Hungarian Economical Competitiveness Operative Programme.

The Klagenfurt University implemented and evaluated a mechanism called Client Behaviour Prediction, which determines the most likely locations of client requests in the near future. This mechanism enables the server to execute the time-consuming process of the placement of the data managers and videos in advance, without significant delay in serving the client requests. For this reason, the placement of the videos recently came into the focus along with that of the proxies.

Numerous online training materials contain videos that can be streamed to the user. SZTAKI intends to apply the research results to e-learning applications containing video-based courseware. Our objective is to create an Adaptive Learning Management System through the integration of standard Learning Management Systems (LMS), our own standardized courseware repository, and the ADMS platform. This integrated system delivers the videos appearing in the training materials through the ADMS. Student behaviour in requesting the training videos can be modeled relatively well. For this reason, the student and course data gained from the LMS can significantly facilitate the prediction of the client requests.

Please contact:
Ottó Hutter, SZTAKI, Hungary
Tel: +36 1 279 6191
E-mail: huttersztaki.hu

Tibor Szkaliczki, SZTAKI, Hungary
Tel: +36 1 279 6172
E-mail: sztiborsztaki.hu

Balázs Goldschmidt, Budapest University
of Technology and Economics, Hungary
Tel: +36 1 463 2649
E-mail: balageinf.bme.hu