Algorithms for System Expansion - Scalable Continuous Media Streaming Systems - page 263

15

Algorithms for System Expansion

One of the desirable features of parallel server architectures is the incremental scalability,
i.e., we can progressively add more servers to increase the system streaming capacity. In
practice, a service operator will likely begin with a smaller system, and then gradually add
more servers when the user population grows. This system expansion, however, creates
two new challenges. First, as the media data are already stored among the existing media
servers, we will need to redistribute some of the media data to the newly added servers so
that they can share the streaming workload. Second, for fault tolerance, in addition to the
media data, there will also be redundant data encoded from the media data using erasure
correction codes. After adding more servers and redistributing the media data, however, the
original redundant data unfortunately will become invalid as the size of the parity group
has increased. Hence, we will need to update the redundant data so that the system's fault-
tolerant capability can be maintained. This chapter presents new algorithms to solve these
two challenges.

15.1 Introduction
There are two challenges in expanding a parallel streaming server with more servers. First,
the newly added servers cannot share the streaming workload until a portion of the media data
have been redistributed to them from the existing media servers. We call this process data
reorganization . While simple algorithms can easily be devised, our results show that they are
very inefficient and incur significant overheads in transferring data between the existing and
the new servers. To tackle this problem we present in Section 15.3 a Row-Permutated Data
Reorganization (RPDR) algorithm that can efficiently reorganize data in a parallel streaming
server. Compared to the trivial algorithm, RPDR can reduce the reorganization overhead by
over 70%. More importantly, RPDR can guarantee streaming load balance after the data have
been reorganized.
Second, if the parallel streaming server employs redundant data to support fault tolerance,
then the redundant data will also need to be updated after the media data are reorganized.
We call this the redundant data update problem. In Section 15.4 we present a Sequential