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

For an unsuccessful admission, the complexity will be lower as the admission test in equa-
tion (7.9) can be stopped once the system utilization is exceeded in any of the rounds. In this

case, the client will have to wait until the next round to repeat the admission test. This process
repeats until either the client is admitted or the client leaves the system due to excessive wait.
Therefore, the admission complexity is further multiplied by the waiting time.
By contrast, the MDR scheduler requires a very simple admission test with only one single
computation. As MDR schedules are all monotonic decreasing, this implies that the available
systembandwidth utilization u i is a non-increasing series. It follows that if the first transmission
rate can be accommodated, i.e.,

w

u A + v 0 ≤ U (7.10)

then the rest of the schedule is guaranteed to not exceed the system capacity as well:

u i + v i − A , i = A , A + 1 ,..., A + w − 1

≤ u A + v i − A , ∵ u i is non-increasing

≤ u A + v 0 , ∵ v j ( j = 0 , 1 ,...,w − 1) is non-increasing

= U , ∵ (7 . 10) (7.11)

If the admission is successful, then the system utilization u i s will be updated according
to equation (7.9). Otherwise, the admission test will be repeated in the next round. There is
one key difference compared to general smoothing algorithms: the system utilization update
needs to be performed once only, even if the client has to wait and perform multiple rounds
of admission tests. This is because the admission test can be completed using equation (7.10)
without computing equation (7.9) under the MDR scheduler. This leads to significantly lower
complexity in the admission process.

7.3.3 Peak Transmission Rate
The first rate in a MDR schedule is the peak transmission rate. Compared to the video's data
consumption function A ( t ), this peak rate r 1 is bounded from the above by the consumption
function's peak rate:

max dA ( t )
dt

0 r 0 ≤ |∀ t ≥ (7.12)

The equality will only occur when the peak rate of the cumulative data consumption function
appears right at the origin. In this case, any feasible transmission schedule with zero start-up
delay will have a start-up rate larger than or equal to the start-up rate of the cumulative data
consumption function. This is stated in Theorem 7.1:

Theorem 7.1. The MDR scheduler generates schedules with the minimum peak rate among
all feasible schedules with zero start-up delay.

Proof. The peak rate of a MDR schedule is the first rate r 1 , so it is sufficient to prove that
S ( t ) has the smallest slope among all feasible schedules for t in 0 ≤ t < T 1 . We prove this by