Transcript Document

Scheduling for maximizing
throughput
EECS, UC Berkeley
Presented by Antonis Dimakis (dimakis@eecs)
Outline
1. Setting, throughput optimal scheduling policies.
2. Basic tools: Lyapunov functions and fluid limits
3. Maximum Weight matching (MaxWeight)
4. Varying Channel models
5. Longest Queue First (LQF)
6. Summary & Open problems
2
Scheduling in ad-hoc wireless
networks
2
1
3
4
5
6
• Goals:
–
–
–
–
Large throughput
Delay / Loss
Fairness
Simple protocol
3
Scheduling in data comm. switches
input 1
l11
l12
Q11(t)
1
1
output 1
2
2
output 2
Q12(t)
input 2
l21
l22
Q21(t)
Q22(t)
4
1. Setting
A1(t)
A2(t)
:
D1(t)
D2(t)
:
Q(t)
A|K|(t)
D|K|(t)
. . .
M[K]=
m11
m21
m12
m22
m13
m23
m|K|1
m|K|2
m|K|3
service rate matrix
R
K: set of queues
A(t): arrivals
D(t): departures
M[K]: service rate matrix
R: routing matrix
[Tassiulas’92],[McKeown et al.’95]
[Andrews et al.’00],…
5
Example
l1
l2
l3
1
2
3
• K={1,2,3}
• Service matrix
• Routing matrix
• Queueing equation:
6
Feasible region & Optimal policy
• Given avg. input rates l=E(A(0)), is there a static
schedule that supports it?
i.e., exist f¸ 0, y 2 Co(M[K]) s.t. l+RTf=0, f < y.
• If rates l are stable under some policy, then
necessarily l is supported by a static schedule:
l = limt A(t)/t = limt D(t)/t · liminft y(t) 2 Co(M[K]).
• Feasible rates = rates supported by static schedules.
• Optimal policy = stabilizes all feasible rates.
7
2. Basic tools: Lyapunov functions
• Goal: show irreducible Markov chain Xt is positive
recurrent.
• Pakes’ lemma: Assume V(x)¸ 0,8 x.
If E[V(Xt+1)-V(Xt)|Xt=x]· -e<0, for all x except on a finite set C,
then Xt is positive recurrent.
8
2. Basic tools: fluid limits
• Goal: show a queueing system is stable
• Queueing equation
• Consider deterministic fluid model
• theorem: If 9 t0 s.t. Q(t)=0,8 t¸ t0 , the original
queueing system is stable (pos. rec.).
9
Fluid limit example
l1
l2
1
2
•
Consider sequence of systems indexed by n, with Q1n(0)+Q2n(0)=n.
•
Under ergodic inputs, any limit must satisfy
10
Fluid limit example (ctd.)
•
If l1+l2<1, then 8 t¸ t0=1/(1-l1-l2), Q1(t)=Q2(t)=0.
•
This gives a Lyapunov function for Q(t).
11
3. Maximum Weight Matching
(MaxWeight)
• Choose m 2 argmax{-fRQ: f 2 Co(M[K])}
• Example:
l1
l2
l3
1
2
3
• In this case, check max{Q1+Q3,Q2-Q3}
• When Q=(2,7,3) activate {1,3}.
[Tassiulas’92]
• Basic theorem: MaxWeight is throughput optimal.
12
MaxWeight optimality:
• V(q)=qTq is a Lyapunov function.
• Recall:
so, dV(Q(t))/dt=2(l+RTf(t))TQ(t)
=2(lTQ(t)+f(t)TRQ(t))
=2(-fTRQ(t)+f(t)TRQ(t))
· 0,
since, -f(t)TRQ(t)=max{-fTRQ(t): f 2 Co(M[K])}.
13
4. Varying Channel model
A1(t)
A2(t)
:
. . .
M1[K]=
D1(t)
D2(t)
Q(t)
A|K|(t)
m11
m21
m12
m22
m13
m23
m|K|1
m|K|2
m|K|3
service rate matrix
[Andrews et al.’00],…
:
D|K|(t)
channel state
M2[K]=
. . .
m11
m21
m12
m22
m13
m23
m|K|1
m|K|2
m|K|3
service rate matrix
14
Varying Channel analysis
•
•
•
•
•
l1
l2
1
2
Consider 2 channel states (service matrices) M1, M2, w.p. pi.
Feasible region: {l ¸ 0: l < p1 y1+p2 y2,yi2 Co(Mi)}.
MaxWeight: at state i, choose argmax{fTQ(t): f2 Co(Mi)}
Again, V(q)=q12+q22, is a Lyapunov function:
In an interval (t,t+d) channel is Mi for time pid. During this time,
MaxWeight some fi2 Co(Mi) is always optimal.
15
5. LQF generalized switch model
A1(t)
A2(t)
:
D1(t)
D2(t)
:
Q(t)
A|K|(t)
D|K|(t)
. . .
M[K]=
m11
m21
m12
m22
m13
m23
m|K|1
m|K|2
m|K|3
service rate matrix
K: set of queues
A(t): arrivals
D(t): departures
M[K]: service rate matrix
Longest Queue First
16
Longest Queue First (LQF)
1. Easy case: local pooling ) stability.
2. Subtle effect: fluctuations can stabilize.
rank condition and non-deterministic arrivals ) stability.
17
Stability of LQF
l1
l2
l3
1
2
3
service vectors
• Necessary: l1+l2<1, l2+l3<1.
• Sufficient:
• Under LQF, longest queues tend to decrease:
– Say, Q1¼ Q2>>Q3, for some time.
– Then, Q1+Q2 decreases, and so do Q1,Q2.
• Key: locally in time, service from common resource pool.
18
Local Pooling
L
Q(t)
service matrix
M[L]
K\L
t
• Assume 9 nonzero vector a¸0 s.t. af=constant C, 8 f 2 M[L].
• M[L], or L, is said to satisfy local pooling (LP).
• Then,
aQL(t)=aQL(0) + aAL(t) – C £ t
has negative drift, for feasible arrival rates l. (al<ay=C)
19
Local Pooling
• Note:
If f<y for some service vectors f,y of the subsystem L, then Local
Pooling cannot hold for L.
• Characterization:
20
Stability of LQF
 If every L½ K satisfies Local Pooling and arrival
rates l are feasible, then system is stable:
Proof:
1. Fix time t,. L:=argmax
i Qi(t).
.
2. W.l.o.g., Qi(t)=Qj(t) for all i,j2 L.
3. If. l feasible, then lL<f2Co(M[L]). But f does not dominate
DL(t)2Co(M[L]), by Local
. Pooling.
.
4. Thus, 9 k2 L s.t., lk<Dk(t), so Qk(t)<-e*.
5. maxi Qi(t) is a Lyapunov function for fluid system.
21
Stability of LQF
• Graphs that satisfy Local Pooling:
3, 4, 5, 7 Cycles
Trees
Combinations
22
Stability of LQF: Subtle Effect
• Graph that does not satisfy Local Pooling:
2
3
1
4
6
• Service Vectors:
{1, 3, 5}, {2, 4, 6}
{1, 4}, {2, 5}, {3, 6}
5
• ½{1,3,5}+ ½{2,4,6} > (1/3){1,4}+(1/3){2,5}+(1/3){3,6}.
 {1,…,6} does not satisfy Local Pooling.
• Every proper subset satisfies Local Pooling.
23
Stability of LQF: Subtle Effect
• Note: Deterministic inputs with
rate close to 0.5  unstable
2
1
3
4
6
5
• Assume arrival of constant 0.5-e
work to each queue.
• Initial state: all queues are equal.
• Tie breaking rule: with >0 prob. a size-2 service vector is
selected.
• For any sequence of service vectors, all-equal state is reached
again.
• Sequence of service vectors does not depend on e.
24
Stability of LQF: Subtle Effect
2
3
1
4
6
theorem:
LQF stable for i.i.d. arrivals with nonzero variance.
5
key idea:
{1,…,6} cannot be set of longest queues for a positive fraction of
time
 Local Pooling holds most of the time.
 Longest queue decreases.
25
Stability of LQF: Subtle Effect
Assume all queues are longest for a while
 {2, 3} and {5, 6} served at same rate

2
3
1
4
6
5
26
Stability of LQF: Subtle Effect
L
D(n)
kD(n)
(k + 1)D(n)
• Max-min large at kD(n): A subset L of queues dominates the
others during interval.
 This subset satisfies LP  Longest queue decreases in D(n)interval.
27
Stability of LQF: Subtle Effect
Qn(nt)
…
Qn(n(t+d))
time
nt
D(n) D(n)=n1/6
D(n) n(t+d)
1. Most of D(n)-intervals are dominated by proper subsets L of
{1,…,6}  LP holds for L.
2. This will imply maxiQi(n(t+d))-maxiQi(nt)<-nd e.
28
Stability of LQF: Subtle Effect
Theorem:
Assume that whenever a set L does not satisfy LP, the
corresponding service vectors have rank · |L|-2.
Assume also the arrivals are i.i.d. with positive variance
(and satisfy a large deviation bound).
Then LQF is stable for any feasible arrival rates.
29
Stability of LQF: Subtle Effect
• Examples
2
1
3
1
2
8
3
7
4
4
6
5
6
5
30
Example of instability
• 8-cycle. Bernoulli li=l1=0.4984<1/2, uniform tiebreaking policy.
1
2
8
3
7
4
6
5
31
Summary
• Lyapunov functions & fluid limits.
• MaxWeight throughput optimal
– No need to know arrival rates.
– Works under varying channel conditions.
– Must know independent sets.
• LQF is not always optimal
– No need to know arrival rates or independent sets.
– Stability depends on variance, not only average rates.
32
Open problems
• How suboptimal LQF is in reality?
• Optimal policy that does not use knowledge of
independent sets?
• Fair scheduling?
• Merits of using load-aware scheduling?
– Ethernet works “suboptimally”, but only ~10 nodes.
33
References
•
•
•
•
•
•
[Tassiulas’92] Tassiulas & Ephremides, “Stability properties of constrained queueing
systems and scheduling policies for maximum throughput in multihop radio networks”, IEEE
Trans. On Aut.Con., 37(12), 1992.
[Andrews et al.’00] M. Andrews, K. Kumaran, K. Ramanan, A.L. Stolyar, R. Vijayakumar, P.
Whiting, “Scheduling in a Queueing System with Asynchronously Varying Service Rates” ,
Probability in the Engineering and Informational Sciences, 2004, Vol.18.
[Rybko & Stolyar’92] A.N. Rybko and A.L.Stolyar, “Ergodicity of stochastic processes
describing the operation of open queueing networks,” Problems of Information Transmission,
vol. 28, 1992. (Translated from Problemy Peredachi Informatsii, vol. 28, no. 3, pp. 3-26,
1992.)
[Dai’95] J. G. Dai, "On positive Harris recurrence of multiclass queueing networks: a unified
approach via fluid limit models", Annals of Applied Probability, Vol 5, 49-77 (1995). [full
paper: ps file dai95a.ps (294 Kbytes) or pdf file dai95a.pdf (184 Kbytes) ]
[Dimakis & Walrand’06] “Sufficient conditions for stability of longest queue first scheduling:
second order properties using fluid limits" to appear in Advances in Applied Probability 38.2
(June 2006).
[McKeown et al.’95] Nick McKeown, Adisak Mekkittikul, Venkat Anantharam and Jean
Walrand "Achieving 100% Throughput in an Input-Queued Switch (Extended Version)"
IEEE Transactions on Communications, Vol.47, No.8, August 1999. 22 pages pdf
34