PDF de programación - Scheduling (2)

NUEVOS SERVICIOS DE RED EN INTERNET

Área de Ingeniería Telemática

Scheduling (2)

Área de Ingeniería Telemática

http://www.tlm.unavarra.es



Máster en Comunicaciones



Objetivos

•  Conocer las características y el funcionamiento de

los planificadores más habituales

•  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
Á

Priority Queueing (PQ)

•  Paquetes en cola de mayor prioridad se envían siempre antes que

paquetes en colas de menor prioridad

•  Multilevel priority with exhaustive service: Los paquetes en una cola de
menor prioridad no se envían hasta que todas las colas de mayor
prioridad están vacías

•  En cada cola FCFS
•  Asegura que el tráfico importante reciba un servicio rápido
•  Puede crear inanición (starvation), es decir, dejar fuera de servicio a

tráfico menos prioritario

•  Menor retardo en cola medio para un flujo a costa de mayor para otros.

Priority Queueing



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
Á

•  El número de niveles de prioridad depende del número de

clases de retardo a crear
•  Son típicas al menos 3:

–  Prioridad alta: mensajes urgentes, por ejemplo protocolos de control de red
–  Prioridad media: servicio garantizado
–  Prioridad baja: best-effort

•  Otra posibilidad:
–  Prioriad alta: voz
–  Prioridad media: vídeo
–  Prioridad baja: resto de datos

•  Un flujo de alta prioridad puede “ahogar” a otros de prioridad

más baja

•  Es vital un correcto control de admisión y policing para todo lo

que no sea la clase más baja

•  Sencillo de implementar
•  El reparto del BW entre las clases no es max-min fair




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
Á

Priority Queueing

Ejemplo
•  Se conoce el tamaño de la ráfaga más larga que puede llegar

de un flujo (bi)

•  Para el flujo de prioridad mayor i = 1 el b1 debe ser inferior al

retardo de peor caso que se busque

•  Para el flujo de prioridad i = 2 el retardo máximo es b1+b2
k
•  El flujo de prioridad i = k sufre un retardo de caso peor de bi
∑
i=1

Round Robin (RR)

•  Opera en “turnos” (rounds)
•  En cada turno visita cada cola (en round-robin)
•  En cada cola FCFS
•  Se sirve un número de paquetes o paquetes durante un cierto

tiempo fijo (la diferencia es cómo afectan sus tamaños)



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
Á

PS



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
Á

•  Para best-effort querríamos un reparto max-min fair
•  Esto se puede lograr con un scheduler llamado Processor Sharing
•  Es un planificador work-conserving
•  Sirve de forma simultanea todas las colas, repartiendo la capacidad
•  O se puede decir que las sirve por turnos (round robin) pero sirviendo

una cantidad infinitesimal de cada una

•  Si una cola está vacía pasa a la siguiente, de forma que su tiempo se

está repartiendo entre el resto (y de ahí el max-min)

•  Aproximación de tráfico como un fluido
•  Es un planificador ideal e imposible de implementar, aunque se puede

aproximar

t1 = s
C

tiempo

t2 = s

C
2

= 2 s
C




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
Á

Processor Sharing

Ejemplo

envío de
la clase1

envío de
la clase2

envío de
la clase3

1 clase
activa
a C

2 clases
activas
a C/2

tiempo

N clases
activas
a C/N


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

GPS

•  Se puede asociar un peso a cada cola y entonces la

(i)

cantidad de servicio es proporcional al mismo

•  Ofrece weighted max-min fairness y lo llamamos Generalized

Processor Sharing (GPS)

•  En cualquier caso, en la realidad no podemos servir fluidos sino

que servimos paquetes así que solo podremos aproximarlo

•  Round Robin es una aproximación a PS

ci = C

(i)

P (i)

Weighted Round Robin (WRR)

•  Opera por “turnos”
•  Se normaliza el peso por el tamaño medio de paquete en la clase
•  Normaliza el resultado para que sean enteros
•  En cada turno visita cada cola (en RR) y sirve tantos paquetes como

(i)
si



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
Á

su peso normalizado

•  Ejemplo:

–  Pesos: 0.03, 0.05, 1 y 0.5
–  Tamaños medios: 50, 500, 1000 y 1200 bytes
–  Renormalizados según tamaños medios: 0.0006, 0.0001, 0.001 y 0.0004
–  Renormalizados a enteros: 6, 1, 10, 4

n1=6
n2=1
n3=10
n4=4

Weighted Round Robin (WRR)

•  Necesita saber el tamaño medio de paquete de cada clase
•  Más sencillo si los paquetes son de tamaño constante
•  Es justo solo por encima de la escala de la duración del turno. Ejemplo:



I

I



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



a
c
i
t

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

–  Enlace T3 (45Mbps)
–  500 PVCs ATM con peso 1 y 500 PVCs con peso 10
–  Supongamos que todos los PVCs tiene tráfico
–  Un turno requiere enviar: 500 x 1 + 500 x 10 = 5500 celdas ! 51.82 ms
–  Por debajo de una escala de 50ms unos PVCs reciben más que otros

•  El retardo que sufre una clase depende del número de clases que haya
•  Hay implementaciones que lo combinan con una cola de prioridad
•  SRR (Shaped Round Robin):

–  Modo Shaped: Reserva una porción del BW a cada clase reservando un
tiempo en cada round y dentro de él enviando los paquetes equiespaciados

–  Modo Shared: el tiempo no utilizado por una clase lo usan el resto
–  A partir de un cierto intervalo sirven los mismos paquetes de cada cola

WRR y SRR

–  SRR los envía con un orden diferente, más entremezclados de las

diferentes clases

Deficit Round Robin (DRR)

•  Permite hacer un RR con pesos sin conocer tamaños medios

de paquetes



I

I



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



a
c
i
t

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

•  Veamos primero versión sin pesos
•  Cada clase mantiene un contador de déficit inicializado a 0
•  En cada turno se añade q (el quantum) al contador de cada

clase si tiene paquetes por servir, si no se resetea

•  El planificador visita cada clase y sirve el primer paquete de la

cola si su tamaño es menor que su contador de déficit

•  y decrementa el contador en el tamaño del paquete
•  Ejemplo:

–  q = 1000 bytes
–  Tres clases A, B y C con paquetes de 1500, 800 y 1200 bytes
–  Turno 1: Clase A contador a 1000, clase B se sirve paquete y el contador

se queda en 200, clase C contador a 1000

–  Turno 2: Clase A se sirve paquete y contador a 500, clase B se resetea
pues no tiene paquetes (para que no acumule), clase C se sirve paquete y
contador a 800

Deficit Round Robin (DRR)

•  En la versión con pesos el quantum es el peso de

cada clase



I



I

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



a
c
i
t

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

•  El quantum debería ser al menos del tamaño máximo

de paquete para servir alguno en todos los turnos

•  Es sencillo de implementar





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 Packet 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

•  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