PDF de programación - Scheduling (3)

NUEVOS SERVICIOS DE RED EN INTERNET

Área de Ingeniería Telemática

Scheduling (3)

Área de Ingeniería Telemática

http://www.tlm.unavarra.es



Máster en Comunicaciones



Objetivos

•  Saber calcular cotas a parámetros de red que

afectan al tráfico



I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á





I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ

•  Weighted Fair Queueing
•  Aproximación de GPS (Generalized Processor Sharing) para el

•  Equivalente a PGPS (Packet-by-packet Generalized Processor

caso de paquetes

Sharing)

•  No requiere conocer el tamaño medio de paquete
•  Emplea un reloj virtual
•  Calcula el final virtual en que se enviaría cada paquete en el

caso ideal GPS

•  Se envían en orden de tiempo final virtual
•  Más complejo de implementar
•  Puede ofrecer worst-case bounds


a
c
i
t



I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á



T
E
N
R
E
T
N

I


N
E

WFQ

•  Se simulan “turnos”
•  Supongamos que no hay pesos
•  Supongamos que GPS no sirve fluido perfecto sino bit-a-bit
•  El número de turno (round number) es el número de turnos bit-a-bit

que se han completado en un instante

•  Cuantos más flujos activos simultáneos hay, más despacio se
incrementa el turno con el tiempo pues en un turno hay que enviar un
bit de cada uno de ellos

•  En realidad podemos ignorar el servir bit-a-bit si definimos el round
number como un valor que crece a una velocidad inversamente
proporcional al núero de flujos activos

•  El finish number F(i,k,t) del paquete k del flujo i que llega en t es:

–  Si el flujo está inactivo: el round number actual + el tamaño en bits
–  Si el flujo está activo: máx[F(i,k-1,t), round_number] + tamaño en bits

•  Si un paquete llega a una cola llena se descartan paquetes en

orden decreciente de finish number hasta que quepa

•  Una vez calculado el finish number de un paquete no hay que

recalcularlo ante nuevas llegadas





I



I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Enlace a 1 unidad/s
• 

Llegadas de tamaños 1, 2 y 2 unidades en t=0 y de tamaño 2 unidades en t=4

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo




I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Finish numbers:
–  A1 = 0 + 1 = 1
–  B1 = 0 + 2 = 2
–  C1 = 0 + 2 = 2

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo





I



I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Hay 3 flujos a enviar simultáneamente
•  El round number se incrementa a C/3 = 1/3 por unidad de tiempo

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo




I



I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  En el instante t=3 se han servido 3 bits, eso es uno por flujo y por lo tanto

termina el round 1 y termina de enviarse A1

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo




I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  A partir de ahí se siguen sirviendo B1 y C1 con finish number = 2
•  Al haber dos flujos activos crece el round number a 1/2

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo





I



I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  B1 y B2 terminarían de enviarse al alcanzar round number = 2 (t = 5) pero llega

antes A2

A
B
C

3

2

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo




I



I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Finish number de A2 es 1.5 + 2 = 3.5
•  A partir de t=4 vuelve a haber 3 flujos simultáneos

A
B
C

3

2

1.5

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo





I

I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Se alcanza el round number 2 en t = 4 + 0.5/(1/3) = 5.5
•  Entonces se completaría el envío GPS de B1 y C1

A
B
C

3

2

1.5

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo





I

I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

WFQ (Ejemplo)

•  Queda solo una fuente activa luego ahora se avanza a 1 round por unidad de

tiempo

A
B
C

3

2

1.5

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo

WFQ (Ejemplo)


a
c
i
t



I



I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

T
E
N
R
E
T
N

I


N
E

•  Queda solo una fuente activa luego ahora se avanza a 1 round por unidad de

tiempo



•  En t = 7 se alcanza el round number 3.5 y termina de enviarse A2

A
B
C

3.5

3

2

1.5

1


r
e
b
m
u
n

d
n
u
o
r

1

2

3

4

5

6

7

8

tiempo

WFQ
•  Calcular el round number es complejo
•  Hay que hacerlo para cada paquete que llega y por cada uno

que se envía


a
c
i
t



I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á



T
E
N
R
E
T
N

I


N
E

•  En el caso con pesos a la hora de calcular el finish number:

–  Si flujo inactivo: el round number actual + tamaño / peso
–  Si flujo activo: máx[F(i,k-1,t), round_number] + tamaño / peso

•  y el round number se incrementa con el inverso de la

suma de los pesos

•  Existen variantes para simplificar este cálculo:

–  Self-Clocked Fair Queuing (SCFQ)
–  Start-Time Fair Queuing

Cotas (bounds) en WFQ

•  WFQ garantiza reparto weighted max-min fair
•  Eso quiere decir que cada flujo recibe una asignación proporcional a su



I

I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

peso

ci = C

(i)

P (i)

•  Además pone una cota al retardo máximo
•  Supongamos un flujo con una restricción “sigma-ro” (σ, ρ) :

–  En un intervalo t llegan como mucho σ + ρt bits
–  Es la salida de un token bucket
–  Linear Bounded Arrival Process (LBAP)


o
d
a
l
u
m
u
c
a

o
c
i
f
á
r
T

σ

ρ

tiempo





I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Cotas (bounds) en WFQ

•  Un flujo i con restricción (σ(i), ρ(i)) (el resto puede no estar

conformado)

•  Camino con K saltos (todos WFQ)
•  Se le ha asignado una tasa g(i,k) en cada uno:

g(i,k) = r(k) φ(i,k)
φ(j,k)

∑

j
•  g(i) es el mínimo de g(i,k) y g(i) ≥ ρ(i)
•  Pmax(i) es el mayor tamaño de paquete del flujo i y Pmax en la red
•  Entonces el retardo extremo a extremo debido a encolado y

r(k) link rate en enlace k

transmisión en el peor caso es:

D*(i) ≤

σ(i)
g(i) +

K−1
∑
k=1

Pmax(i)
g(i,k)

+

K
∑
k=1

Pmax
r(k)

Tráfico

token rate, ρ

bucket size, σ

WFQ

WFQ

WFQ





I

I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

Cotas (bounds) en WFQ

•  Podemos garantizar un retardo máximo extremo a extremo
•  Planificadores WFQ en todo el camino
•  Requiere que el flujo esté conformado por un leaky bucket
•  No se imponen restricciones al resto de flujos en la red
•  Solo hay que seleccionar los valores adecuados de reserva de BW en
Pmax
r(k)

los enlaces

σ(i)
g(i) +

Pmax(i)
g(i,k)

D*(i) ≤

•  Ejemplo

K−1
∑
k=1

K
∑
k=1

+

– 

(...)




I



I



D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Cotas (bounds) en WFQ

•  Podemos garantizar un retardo máximo extremo a extremo
•  Planificadores WFQ en todo el camino
•  Requiere que el flujo esté conformado por un leaky bucket
•  No se impone restricciones al resto de flujos en la red
•  Solo hay que seleccionar los valores adecuados de reserva de BW en
Pmax
r(k)

los enlaces

σ(i)
g(i) +

Pmax(i)
g(i,k)

D*(i) ≤

•  Ejemplo

K−1
∑
k=1

K
∑
k=1

+

–  Flujo LBAP con parámetros (16 KBytes, 150 Kbps)
–  K = 10 saltos, todos a 45 Mbps, retardo de propagación total de 30ms
–  Máximo tamaño de paquete de 8 KBytes
–  Queremos un retardo extremo-a-extremo máximo de 100 ms
– 

(...)





I

I

D
E
R
E
D
S
O
C
V
R
E
S
S
O
V
E
U
N



T
E
N
R
E
T
N

I


N
E


a
c
i
t



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Cotas (bounds) en WFQ

•  Podemos garantizar un retardo máximo extremo a extremo
•  Planificadores WFQ en todo el camino
•  Requiere que el flujo esté conformado por un leaky bucket
•  No se impone restricciones al resto de flujos en la red
•  Solo hay que seleccionar los valores adecuados de reserva de