PDF de programación - Scheduling (2)

REDES

Área de Ingeniería Telemática

Scheduling (2)

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

4º Ingeniería Informática



Redes


a
c
i
t

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á

Temario

Introducción a las redes

1. 
2.  Encaminamiento
3.  Transporte extremo a extremo
4.  Arquitectura de conmutadores de paquetes
5.  Tecnologías para redes de área local
6.  Tecnologías para redes de área extensa y última

milla

7.  Conmutación de circuitos

Objetivos

•  Conocer las características y el funcionamiento de

los planificadores más habituales

•  Saber que se pueden calcular cotas a parámetros de

red estadísticos que afectan al tráfico


a
c
i
t

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á


a
c
i
t

l



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

i

I



S
E
D
E
R

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


a
c
i
t

l



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

i

I



S
E
D
E
R

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


a
c
i
t

l



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

i

I



S
E
D
E
R

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)


a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
E
R

PS


a
c
i
t

l



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

i

I



S
E
D
E
R

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


a
c
i
t

l



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

i

I



S
E
D
E
R

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

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á

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

a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
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)

a
c
i
t

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á

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

–  Enlace a 45Mbps
–  500 flujos con peso 1 y 500 flujos con peso 10
–  Supongamos que todos los flujos tiene tráfico
–  Todos los paquetes de tamaño constante, 53 bytes
–  Un turno requiere enviar: 500 x 1 + 500 x 10 = 5500 paquetes
–  5500 paquetes a 45Mbps requieren 51.82ms
–  Por debajo de una escala de 50ms unos flujos reciben más que otros

Deficit Round Robin (DRR)

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

de paquetes

a
c
i
t

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á

•  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

a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
E
R

•  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


a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
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

l



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

i

I



S
E
D
E
R

e
d



a
e
r
Á

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


a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
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


a
c
i
t

l



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

i

I



S
E
D
E
R

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


a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
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


a
c
i
t

l



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

i

I


e
d



a
e
r
Á



S
E
D
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