PDF de programación - Scheduling

REDES
Área de Ingeniería Telemática

Scheduling

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Redes

4º Ingeniería Informática

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
Á

Hoy...

1. Introducción a las redes
2. Tecnologías para redes de área local
3. Conmutación de circuitos
4. Tecnologías para redes de área extensa y última milla
5. Encaminamiento
6. Arquitectura de conmutadores de paquetes

• Scheduling / planificación

• Control de acceso al medio
• Transporte extremo a extremo

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
Á

Scheduling why?

• No es suficiente con elegir el primero?

FCFS first come first served? cola unica elijo el primer paquete de la cola
DropTail si voy a colocar un paquete en la cola y no hay sitio lo descarto
– Puede no existir el concepto de el primero en llegar

en el caso de colas a la entrada tenemos que elegir entre paquetes en
varios puertos de entrada... cuál es el primero en llegar?

– Podemos querer tratar de forma diferente a diferentes aplicaciones

Aplicaciones elásticas (mail, web, transferencia de ficheros)
No les importa mucho tardar unos pocos milisegundos mas en salir
(best-effort)
Aplicaciones con restricciones de tiempo (VoIP, videoconf, juegos)
Milisegundos de mas marcan la diferencia entre funcionar o no

– Podemos querer tratar a todos los paquetes por igual (Fairness) y si no

tenemos cuidado FCFS puede crear injusticias

Llegan 2 cada ∆t
Data Hdr
Data Hdr

Data Hdr
Data Hdr

Data Hdr
Data Hdr

Queda sitio para 1

Sale 1 cada ∆t

Data Hdr Data Hdr

Data Hdr

Data Hdr

3

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
Á

Principios de scheduling

• Requisitos

– Facilidad de implementación

La decisión debe tomarse por cada paquete
Debe escalar con el numero de entradas/flujos/conexiónes
Debe tener poco estado interno
Normalmente se hará en hardware

– Equidad(fairness) and protection

Debe tratar por igual a las entradas
incluso en condiciones en
correctamente no debe penalizar a las que si lo hacen
fairness -> protection pero no al reves

las que las entradas no se comportan

– Requisitos de prestaciónes

Ser capaz de garantizar limites arbitrarios de prestaciones para algunas
entradas/flujos
Estos limites se garantizaran asignando recursos

– Facilidad de control de admisión

Ser capaz de decidir si permitir una nueva entrada/flujo permitira seguir
cumpliendo los limites o no, para decidir si aceptarla

4

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
Á

Equidad max-min (max-min fairness)
• Propiedad deseable para un reparto de un recurso escaso
• El recurso tiene una capacidad a repartir C
• Las demandas de recurso de los diferentes usuarios son

•

{x1,x2,x3...} tales que en general x1+x2+x2+... > C
Intuitivamente querríamos conceder su petición a los usuarios
que piden poco y repartir por igual entre los usuarios que piden
mucho

C

x1 x2 x3 x4 x5 x6

5

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
Á

Equidad max-min (max-min fairness)

• Algoritmo
• Ordenar las demandas de menor a mayor
• Supondremos que {x1,x2,x3...} están ordenadas de forma que

x1<x2<x2<...

• Asignamos C/N a cada usuario

Si x1<C/N nos sobra C/N-x1 para repartir entre el resto
Sumamos (C/N-x1)/(N-1) a cada uno del resto
x1 ya tiene asignado la cantidad correcta tomamos el siguiente y
repetimos el proceso

• Maximiza el mínimo asignado a las demandas que no son

satisfechas
No penaliza a los usuarios que se comporten bien y piden poco
incluso en presencia de usuarios que piden mucho.

6

Scheduling más simple

FCFS + DropTail

•
• No hacemos distinciones

Primero en entrar primero en salir
Al colocar un paquete en cola si no hay sitio se elimina

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
Á

• Utilización media del servidor (independiente del scheduling utilizado)

FCFS no hace distinción entre paquetes y todos tienen que esperar en
media eso. ¿Podemos hacer otras disciplinas de scheduling que consigan
que algunos paquetes esperen menos?

0.2

0.4

0.6

0.8

1.0 Ρ

ρ=λ x
λ paquetes por unidad de tiempo
x tiempo medio de servicio del paquete
q : Tiempo medio de espera en la cola
depende de la utilización
cómo depende se discute en teoría de colas

q￿￿s￿

0.30
0.25
0.20
0.15
0.10
0.05

•

•

Ley de conservacion

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
Á

•

• Si que se puede conseguir menos tiempo de espera si separamos las

llegadas y las tratamos de forma diferente
En las próximas clases se discutirán métodos
Pero... hay un limite
Ley de conservación
Si tenemos clases de usuarios i=0,1,2...
Cada clase genera una carga ρi=λi xi
Cada clase obtiene un tiempo medio de espera qi
Y el sistema es conservativo de trabajo=si hay paquetes para servir los
sirve
Se cumple que para cualquier disciplina de scheduling

N￿i=0

N￿i=0

ρiqi = constante

Para FCFS

q

ρi = constante

• No podemos obtener un retardo medio menor que el que obtiene FCFS.
Sólo podemos reducir el tiempo medio de espera de una clase
aumentando el de otras

8

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

Scheduling: el escenario

• Servidor que no puede atender a todo lo que le llega

En media si, pero en un momento de pico tiene que elegir

• Los clientes pertenecen a N entradas/clases/flujos diferentes

– Entre estas clases debemos garantizar fairness
– o requisitos arbitrarios de prestaciones (bandwidth, delay,

jitter)

scheduler

9

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

FCFS: first come first served

•

Scheduler simple
Una cola por orden de llegada
Sirvo en orden
No max-min fair
Reparto proporcional a la demanda
No hay protección contra flujos que envían mucho que consiguen mas recursos
Los flujos que se comportan bien y envían poco tienen más probabilidades de
perder todos los paquetes

10

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

• Usando prioridades
•

Scheduler simple
Una cola para cada clase
Ordenadas por prioridad
Sirvo la cola de prioridad k solo si no hay nada que servir en las colas de
prioridad <k

• Cierta protección: flujos de alta prioridad no entorpecidos por flujos de menos

prioridad

p1
p2
p3
p4

•

Problemas:
– Starvation: demasiado trafico en prioridad alta puede dejar sin servicio a los

de menor prioridad

– No siempre queremos prioridad de unos flujos sobre otros (max min fair)

11

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
Á

Max-min fair

• No todos los repartos son max-min fair

scheduler

∆t

∆t

scheduler

∆t

∆t

• Y depende de a que escala de tiempo se observe
• Cómo construimos schedulers max-min fair

12

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 (Generalized processor sharing)

• Hay un algoritmo max-min fair ideal

Supongamos que el servidor es capaz de enviar por separado trozos
infinitamente pequeños de los paquetes (aproximación de trafico como
fluido ideal :-))
Una cola para cada clase

Si dos clases tiene paquetes de
tamaño s ...
el servidor envía alternativamente
trozos infinitamente pequeños de
cada uno

tiempo

t2 = s

C
2

Es como si se enviaran los dos a la
vez entremezclados pero tardan el
doble porque cada uno va a la mitad
de la velocidad
= 2 s
C

13

t1 = s
C

el paquete ocupa tiempo enviandose
si solo una clase tiene un paquete
de tamaño s
se envia durante 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
Á

GPS (Generalized processor sharing)

• Es equivalente a pensar que los paquetes se envían como un fluido que se

envía en total a C unidades por unidad de tiempo

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

N clases
activas
a C/N

tiempo

14

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

GPS (Generalized processor sharing)

• El reparto puede ser a partes iguales entre las clases

ci = C
N

• O proporcional a un conjunto de pesos

{φ(1), φ(2), ...}

ci = C

φ(i)

￿ φ(i)

• El problema es que GPS es un algoritmo ideal

– No podemos repartir el servidor entre paquetes en

tiempos infinitesimalmente pequeños

– Tenemos que elegir uno de los paquetes para servir

•

¿Podemos construir aproximaciones a GPS?

15

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
Á

Round robin (RR)

• Scheduler simple (aproximación más simple de GPS)

Una cola para cada clase
El scheduler coge cada paquete de una cola y pasa a la siguiente
Si una cola esta vacia pasa a la siguiente sin esperar (work conserving)
Si se llena la cola de una clase se tiran paquetes de esa clase, no afecta a
otras.
Esto parece justo, no?

• Es una aproximación a GPS... suficientemente buena?

– Necesitamos soportar pesos
– En la realidad los paquetes no son de longitud constante

16

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
Á

Weighted round robin (WRR)
φ(i)
si

• Asignamos pesos a las clases
• Normalizamos por el tamaño medio de paquete en cada clase
• Normalizamos los pesos para que sean números enteros
• Con pesos enteros {ni} el algoritmo es fácil

φ(i)

– Enviar ni paquetes de la cola i
– Pasar a la cola i+1

n1=10
n2=3
n3=15
n4=6

• Es una buena aproximación de GPS...

Si la miramos en periodos de tiempo mayores que el ciclo (de 34 paquetes
en el ejemplo)

• Necesita saber la media del tamaño de paquete de una clase: no es facil
• Es útil en algunos enlaces de muy alta velocidad (con tamaño fijo de

paquete y ciclos cortos)

17

a
c
i
t

l



á
m
e
e
T