Closed-Loop Algorithms - Scalable Continuous Media Streaming Systems - page 297

2
4
5

A free channel becomes
available.

3 7 3 3 1 3 3 6 7 9 1 9

Media title 8 completed

FIFO Queue

4- Streams
Media Server

2
4
5
9

wait

Two users are batched.

3 7 3 3 1 3 3 6 7 1

Media title 9 started
to serve 2 users.

FIFO Queue

4 -Streams
Media Server

Figure 17.2 FCFS batching is not optimized for batching efficiency

users requesting media object “9”, there are five other queueing users requesting media object
“3”. In other words, if the system allocates the available multicast channel to serve media object
“3” instead of “9”, even more bandwidth resources will be saved (four instead of one). More
generally, instead of using a single queue, we can use separate queues assigned to individual
media objects as shown in Figure 17.3. When a free channel becomes available, the systemwill
simply serve the media object with the most number of users waiting to maximize batching
efficiency. This technique is called Maximum Queue Length (MQL) [1].
The MQL queueing discipline, however, introduces another issue. Suppose that one of the
media objects is very unpopular and rarely get requested by any user. If a user happens to
request this unpopular media object during a period of heavy system load, i.e., there are many
waiting users, then it may experience a very long delay before it can receive service. Thus,
under the MQL queueing discipline the waiting time will be shorter for popular media objects
and longer for unpopular media objects, creating a fairness issue.
This fairness issue and other related issues have been addressed in other studies. Interested
readers are referred to the work by Dan et al. [1-2], Aggarwal et al. [3], Shachnai and Yu [4],
and Liao and Li [5] for more details.

17.3 Patching
Unlike batching, patching (or stream merging) [5-17] is a technique to enable a client to share
media data from an existing on-going multicast stream. Figure 17.4 illustrates the patching
technique for a client arriving at time t a . Instead of starting a new media stream to serve this
client, we can apply patching to enable the client to share data from an existing multicast stream
started earlier at time t 0 . Referring to Figure 17.4, the new client upon arrival immediately