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
qs
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
Ni=0
Ni=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
Crear cuenta
Comentarios de: Scheduling (0)
No hay comentarios