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

Therefore, to employ m -RPDR the system will need to be designed with this load imbalance
in mind to guarantee streaming performance.

15.3.4 Performance Analysis
In this section, we evaluate and compare the multi-row-permutated data reorganization algo-
rithmwith the round-robin [2] and the SCADDAR [3] algorithms, both originally proposed for
disk arrays. The performance metrics used for comparison are data reorganization overhead
and streaming load balance.
The results are computed numerically for a media object of B 4,000 blocks. Unless stated

otherwise the system begins with a single node and then incrementally grows to 200 nodes
by adding new nodes one by one. Each data point is averaged over 50 results obtained from
using different random seeds for the random number generator (used in SCADDAR and the
m -RPDR algorithms).

=

15.3.4.1 Data Reorganization Overhead

Data reorganization overhead is defined as the number of data blocks that need to be redis-
tributed to bring the system back to streaming load balance. This metric can reflect the time,
memory and bandwidth requirement incurred by the reorganization process.
For a system with B blocks already evenly distributed to n nodes, the minimum number of
blocks that need to be redistributed when a new node is added is equal to B

1), provided
that perfect storage balance is to be maintained. Note that this lower bound does not consider
streaming load balance. The SCADDAR algorithm in some cases incurs less overhead than
the lower bound because SCADDAR does not guarantee storage balance.
For round-robin placement, we can derive the approximate reorganization overhead analyt-
ically. Consider expanding a system from ( n

/ ( n +

− 1) nodes to n nodes. If we divide the media

blocks into groups of LCM( n − 1 , n ) blocks, where the function LCM( n − 1 , n ) computes

− −

the least common multiple of n 1) blocks in each group will

not need to be moved (see Figure 15.1 for an example). All other blocks in the group will
need to be relocated. Therefore, the reorganization overhead in round-robin placement is
given by

1 and n , then the first ( n

B LCM ( n B ( n

− , − − − − −

1 n ) ( n 1) 1) n ( n 1)

=

LCM ( n − 1 , n ) ( n − 1) n

B 1

1
n

= − (15.1)

For the SCADDAR algorithm the reorganization overhead has been shown to approach the
theoretical lower bound of B n and the exact values can be obtained from simulated calcu-

lations. Similarly, we also obtain the reorganization overhead of m -RPDR using simulated
calculations. Figure 15.8 compares the reorganization overhead of round-robin, SCADDAR,
and m -RPDR for m

/

and 10.
There are three observations. First, the round-robin algorithm and the SCADDAR algorithm
have the highest and lowest reorganization overhead respectively. Moreover, the differences

= 1 , 2 , 5 ,