Streaming Variable Bit-Rate Media Streams - Scalable Continuous Media Streaming Systems - page 124

until it reaches the end of the video. It can be shown (see Appendix) that the above pro-
cedure guarantees that the generated transmission schedules are monotonic decreasing. The
transmission schedule is then defined from the resultant rate-time tuples { r i , T i } :

t

S ( t ) = s ( τ ) d τ, where s ( τ ) = r i , for T i ≤ τ< T i + 1 (7.7)

0

The rate-time tuples are then stored together with the video data. The video server will
simply schedule the transmission of the video according to this MDR transmission schedule.
Its monotonicity property ensures that once a stream is admitted, there will always be sufficient
system bandwidth for the whole duration of the video stream, even if there are other random
traffics such as web, file transfer, etc., in the system.
This MDR scheduler has several additional desirable properties, namely modest admission
complexity, minimum peak rate, and minimum client buffer requirement. These are discussed
in the following sections.

7.3.2 Admission Complexity
We first consider admission complexity, defined as the number of computations needed to
determine if a new video stream can be admitted to a systemwith finite bandwidth. For existing
smoothing algorithms with transmission schedules consisting of both upward and downward
rate adjustments, it is necessary to check the system's bandwidth availability to determine if
admitting the new stream will exceed the system capacity.
Let U be the total system capacity and U ( t ) be the system utilization at time t . Suppose the
new stream request arrives at time t 0 , then the system can admit the new stream if and only
if there is sufficient system capacity available for the entire duration of the new video stream,
i.e.,

+ − ≤ ,

for all t from t 0 to ( t 0 +

U ( t ) S ( t t 0 ) U L ) (7.8)

In practice, we do not compute equation (7.8) in the continuous time domain as I/O schedules
are likely to be organized into service rounds (e.g., disk retrieval rounds). Let δ be the round

length. Then, for a video of length L , there will be rounds. For clarity, we refer to the

system scheduler's cycles as rounds, counting from zero from the start-up of the system; and
refer to a video title's data unit to be retrieved and transmitted in a round as a block, counting
from zero from the beginning of the video.
Let u i ( i

w = L /δ

1) be
the transmission rate of block j of the video, which can be computed from the transmission
schedule

= 0 , 1 ,... ) be the system's utilization in round i , and v j ( j = 0 , 1 ,...,w −

{ r i , T i } . Then, for a newclient arriving at round A , the admission processwill require w

additions to compute the new aggregate bandwidth utilization for round A to round A + w − 1:

u i = u i + v i − A , i = A , A + 1 ,..., A + w − 1 (7.9)

and w comparisons to determine if the network capacity is exceeded in any of those w rounds.

The admission complexity is then of order O(2 w ) for a successful admission.