Transcript CHEN-cj04

“A cost-based admission control algorithm for
digital library multimedia systems storing
heterogeneous objects” – I.R. Chen & N. Verma
– The Computer Journal – Vol. 46, No. 6, Oct.
2003, pp. 645-659
Andy Connors
Abstract








Multimedia Systems
Mixed workloads – Video, Images & Text
Cost-based admission control algorithm
Based on rewards & penalties
Resource reservation instead of serving requests
until all resources exhausted
Reservation based on maximizing total reward
Exploit left over resources
Simulate algorithm and compare to other schemes
Multimedia System
Video
Audio + Images
Streams
Images
High
Low
Different
Bandwidth
Requirements
Streaming Video
(Real-time)
Disk Buffer
Text
Network Buffer
Data
Blocks
Data
Blocks
Disk Array
`
Mixed-Workload
Multimedia Server
Data Block
From
Stripe Across Disk Array
Challenge

Service mixed workloads




Real-time video/audio request – resource
demanding and varying data rates
Discrete media – images and text
Need algorithm to “squeeze” in image &
text requests without affecting QoS of
video requests
However, 70% of data types on Web are
image & text
Previous algorithms

Video taking higher priority over image/text data


Shenoy & Vin – two-level disk scheduling framework



not justified as 70% of requests are image/text not video
Level 1: class-independent scheduler – assign bandwidth to application
classes – used to dynamically allocate bandwidth to adapt to workload
changes – no details on adaption scheme
Level 2: class-specific scheduler – order requests into a common queue
for access – minimizes seek time and rotational latency overhead –
satisfies QoS requirements of each class – discussed in detail
To & Hamidzadeh – Continious Media-to-Discrete Media redirection
ratio





Redirect bandwidth from CM to DM
Allocate more buffer space to CM – reduces admissible CM requests
Optimize disk reads
Use leftover bandwidth for DM requests
How much bandwidth to move from CM to DM requests?
Basic Idea

Dynamically partition resources based on runtime workload changes




Maximize value metric
Ensuring that response time requirements met
Image/text have “own” resources rather than use
“leftovers”
Assign value/penalty pair to each request



Value: reward if serviced successfully
Penalty: loss if service rejected due to lack of
resources
High value → video higher priority over image/text
Multimedia Server Model

Cycle based disk scheduling:



Video/audio requests



As many data blocks as covered by TSR
Double buffered – disk buffer & network buffer
Image/text requests


All requests serviced in TSR – service round duration
Image/text either serviced after video/audio or interleaved – use
interleaving to minimize disk seek time and latency
As many blocks to cover requests object
SCAN algorithm:


Requests ordered and heads traverse in one direction only
Minimizes seek time
Refresher - Scan Algorithm
14
Time
30
60 62
83
95
123
145
160
Resource Partitioning

Text/images serviced in batch



Statistics of each multimedia object



Distribution of all images and text objects
Histogram of distribution of size needed to satisfy playback
Partition TSR into three parts – video, image and text



Depart at end of service cycle
Two FIFO queues, one for text, other for images
Based on cost & workload
Estimate maximum amount of resources allocated to each type
Use left-over time to service more image/text requests
Performance Metric


Maximize reward without compromising
QoS (bandwidth & response time)
Reward rate
vVNV + vINI + vTNT - qVMV + qIMI + qTMT
N{V,I,T} = requests completed per unit time
M{V,I,T} = requests rejects per unit time
v{V,I,T} = average reward values
q{V,I,T} = average penalty values
Algorithm


Use models derived from queing theory
Build lookup table for run-time bandwidth allocation









Estimation of reward rate under given workload condition
Best bandwidth allocation to maximize reward rate
f{V,I,T} = ratio of disk bandwidth for video, image & text requests
fV + fI + fT = 1 (when normalized)
Service times: f{V,I,T}TSR = disk service time
Use statistical admission control to compute number of requests
of each type so that probability of disk overload is below a
threshold (10-4)
(fV, fI, fT) → (nV, nI, nT)
System behaves like three separate partitions – three queues
For image/text requests


n{I,T} image/text requests per TSR
Total of K{I,T} * n{I,T} image/text requests – K{I,T} = maximum
queue size for image/text requests – can use requests in queue to
use left-over bandwidth – K{I,T} depends on QoS
Video Request Model

M/M/nV/nV queue
 each video stream acts as if served by separate
server until departs
 V, V = arrival/departure rate of video requests
λ
0
λ
1
µ
λ
λ
2
2µ
λ
V-1
3µ
( V-1)µ
V
Vµ
Video Request Model



Pv(j) = probability that j video out of nV slots occupied
0 ≤ j ≤ nV
V, V = arrival/departure rate of video requests
PV j
1
1
V
j
V
nV
j
1
V
k 1 k
V
k
Video Request Reward

With probability Pv(j), reward rate = j*vV*V

So total reward gained =

Rejection rate =



jvVV Pv(j)
V Pv(nV)
Lost reward = qV V Pv(nV)
Reward rate from video = RV
RV
=
( jvV
V
Pv(j)
)-
qV V Pv(nV)
Image & Text Model

For K{I,T}≥1 - M/M/1[n {I,T}]/ K{I,T}* n{I,T} queue

Let K{I,T} = 2
λ
0
λ
1
λ
λ
2
λ
3
λ
I-1
λ
I
λ
λ
2 I-1
I+1
µ
µ
µ
µ
µ
µ
µ
λ
µ
2
I
Image & Text Model

PI(j) = probability that j video out of nV slots occupied
0 ≤ j ≤ nI
I, I = arrival/departure rate of video requests

Let KI = 1


Image & Text Model

PI(j) = probability that j video out of nV slots occupied
0 ≤ j ≤ nI
I, I = arrival/departure rate of video requests

Let KI = 2


Image/Text Request Reward

With probability PI(j) reward rate =





j*vI*I if j < nI
nI*vI*I if j ≥ nI
I PI(KInI)
Lost reward = qI IPI(KInI)
Rejection rate =
Reward rate from video = RI
RI = ( jvII PI(j) ) + ( nIvII PI(j) ) - qI I
PI(KInI)
j = 1 … nI -1
j = nI … KInI
Maximizing Reward





Given
V,V,I, I,T,T,vV,qV,vI,qI,vT,qT
Maximize R by searching for optimal
(nV, nI, nT) → (n*V, n*I, n*T)
Subject to condition (normalized to text requests)
Here NV, NI, NT are maximum number of requests that can
be served of each type (if all bandwidth allocated to each
type)
To use total disk bandwidth
Search

Exhaustive




Search all possible solutions
Complexity O(NT2)
Once found all solutions build lookup table
Nearest Neighbor




When NT is too large and exhaustive is computationally
too expensive
Complexity O(NT)
Fix one nV, nI, nT then next etc.
Heuristic – largest product of arrival rate and reward
selected first
Admission Control Algorithm








Use lookup table to dynamically change to a set of
(n*V, n*I, n*T) depending on workload
By monitoring input rates
Use for admission control
Worst case response time for image and text is K{I,T} TSR
Use common schedule queue for disk requests
If total schedule time < TSR use image/text at head of
respective queues to use up remaining time by moving to
common queue
Probablity that image will be placed on queue f *I/ (f *I+
f *T )
And for text f *T/ (f *I+ f *T)
Analysis


Numerical analysis of reservation system
Parameters:

Disk Array







Images


Text




Evenly distributed across [10kB, 500kB]
Evenly istributed across [1kB, 50kB]
Video


4 disks
Average seek time = 11ms
Rotational latency of 5.5ms
Read/write rate  = 33.3MBps
TSR = 1
Block size = 4 sectors (512bytes) = 2Kbytes
Star Wars – 7200 groups of pictures = 0.5s playback time
12 frames per group
Calculate
 NV = 53, NI = 37, NT = 57
Simulate
 V in range [10,100] arrivals/min, V in range [100,2000], I in range
[100,2000]
Other schemes

Compare with other algorithms:

Video First





Highest priority to video requests
Left-overs used for image/text
(nV, nI, nT) = (NV, 0, 0)
Use queue sizes of K{I,T} n*{I,T}
Greedy


Allocates disk in proportion to product of reward
and arrival rate
(nV, nI, nT) = (
,
,
)
Analysis Results
Effect of Arrival Rates


Effect of varying
image/text arrival rates as
video arrival rate increases
For lower image/text rates


reward rate increases as
video rates increase until hit
a maximum where we see a
decrease
For higher image/text
rates

Steadingly decreases due to
rejects
Effect Of Video Departure Rate


Using varying video
departure rates shows
effect on increasing
video arrival rate
At higher departure
rates


See an increase in
reward rate as arrival
rate increases until a
threshold where server
is heavily loaded and
rejects requests
At lower

Video requests stay in
system for longer time
and so system admits
fewer requests
Effect Of Video Reward Value


Using varying video
reward values shows
effect on increasing
video arrival rate
At higher reward rates

Systems admits more
requests – threshold
shifts higher
Results – Reward Rate

Under light loads


At higher loads


Returns back to theoretical as
text/image queues are full
and consume all server
resources
Same as video-first at lower
loads


Higher than calculated – due
to effect of using left-over
bandwidth which is more
pronounced at higher loads
In limit


Close to predicted lowerbound reward rates
as system can accommodate
most users at these loads
At higher loads

Out performs both video-first
and greedy algorithms
Results – Response Time

Under light loads


Close to other algorithms
At higher loads


As explicitly allocate time
for image/text request see
better response times than
video-first – difference
between 1s and 5s
Greedy favors video/text
and so has better
response times – but
compares favorably
Results – Utilization


Does not show greedy
algorithm as shows
same trends as
reservation algorithm
For video-first


Higher utilization for
video requests – lower
for image/text
For reservation


Better utilization for
image/text
Lower for video
Results – Rejection Rates

At higher loads



Rejects fewer
image/text requests
than video-first or
greedy
Achieved by rejecting
more video requests
Video-first rejects 0
video requests but a
high number of
image/text
Conclusions


Significant improvement in reward rate
compared to video-first and greedy
algorithms
Without sacrificing performance metrics
such as response time & system utilization