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

Figure 15.8 Comparison of reorganization overhead versus system size

increase when the system grows larger. This is because for the SCADDAR algorithm the
overheads approximately equal to B n and so decreases as the system grows. By contrast,

overheads of the round-robin algorithm approach B as n increases (cf. equation (15.1)).
Second, the reorganization overheads of the m -RPDR algorithms are lower than the round-
robin algorithm but higher than the SCADDAR algorithm. In particular, a larger value of m
will result in lower reorganization overhead, thus providing a tool to trade off streaming load
balance for lower reorganization overhead.
Third, the 1-RPDR algorithm can achieve lower overhead than the round-robin algorithm
and yet can still achieve perfect streaming load balance. Thus, the 1-RPDR algorithm can be
used in place of the round-robin algorithmwhenever perfect streaming load balance is required.
So far we have assumed that the system is reorganized whenever a new node is added to
the system. In practice, it may be desirable to add multiple nodes to the system at the same
time to amortize the administrative overheads. Interestingly, performing data reorganization
simultaneously for multiple nodes can also result in lower per-node reorganization overhead
compared to adding them one by one.
Figure 15.9 illustrates the potential savings from performing data reorganization for k

/

=

1 and 5 new nodes. The results clearly show that the per-node reorganization overhead

decreases significantly (note that the vertical axis is in logarithm scale) for larger values of k .
Moreover, the savings are most significant when switching from k

, 2 , 3 ,

2, suggesting
that adding nodes to the system two-at-a-time can be an efficient strategy to expand the system
incrementally.

= 1to k =