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

10000

1000

= 1

k

= 2 k

k

= 3

k

= 5

100

10

50

0 100 150 200

System Size (nodes)

Figure 15.9 Comparison of per-node reorganization overhead versus system size

15.3.4.2 Streaming Load Balance
Most media streaming systems retrieve and transmit media data blocks in fixed-duration service
rounds (cf. Chapter 3), thus if the media blocks are not distributed evenly across all nodes some
nodes will be overloaded while others will be underutilized. Among the data reorganization
algorithms, only the round-robin and the 1-RPDR algorithms can achieve perfect streaming
load balance. All other algorithms, including SCADDR and m-RPDR with m > 1, will result

in some degree of load imbalance.
To quantify streaming load balance, we count the number of overflow media blocks for each
algorithmafter data reorganization is completed, and then plot the proportion of overflowmedia
blocks in Figure 15.10. As expected, both round-robin and 1-RPDR achieve zero overflow. The
SCADDAR algorithm results in over 35% overflow blocks. The m -RPDR algorithm, on the
other hand, results in fewer overflows depending on the choice of m . Finally, another desirable
feature of m -RPDR is that it can guarantee that the maximum number of overflow blocks in
each service round will not exceed m . This enables one to incorporate the overflow effect either
by design or through admission control.

15.4 Sequential Redundant Data Update
In data reorganization we have ignored the redundant data, which will become invalid once data
reorganization is performed. Obviously, to maintain the system's fault tolerance capability we