PDF de programación - Tema 1 (2ª parte): QoS Quality of Service

NUEVOS SERVICIOS DE RED EN INTERNET
Área de Ingeniería Telemática

Tema 1 (2ª parte): QoS

Quality of Service





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

Á

Previously on NSRI…

• Congestión y QoS
• Clasificación y marcado
• CAC
• Policing y Shaping

l
i
t
u

o
d
a
s
r
u
C

Sin

Congestión

Congestión
Moderada

Congestión

Fuerte

Carga

Core

1/53



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

Á

A continuación…

• Scheduling
• Queue management
• Arquitecturas

2/53

NUEVOS SERVICIOS DE RED EN INTERNET
Área de Ingeniería Telemática

Scheduling





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

Á

Scheduling

• Recursos compartidos

– Buffer space
– Capacidad en el enlace de salida
– Tiempo de procesador

• Tipos de schedulers
– Work-conserving
– Non-work-conserving (no veremos)

• Schedulers sin prioridades

– FCFS, RR, …

• Schedulers con prioridades

– GPS, WFQ, SCFQ, WF2Q, …

• Características deseables
– Sencillo de implementar
– Reparto justo (max-min fair share) y protección
– Performance bounds (deterministas o estadísticos)
– Que permita implementar un CAC simple

4/53

The Conservation Law

• Sea un conjunto de N flujos en un planificador
• Para el flujo i la tasa media de llegadas es λi
• El tiempo medio de servicio de los paquetes del flujo i es xi
•
La utilización media del enlace debido al flujo i es ρi = λixi
• El tiempo medio de espera en cola de los paquetes del flujo i es qi



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

Á

Conservation Law
• Si el planificador es conservativo en

entonces

N

#

i =1

"iqi = Constante

trabajo (work-conserving)

• Es independiente del planificador en concreto
•

Implica que para reducir el retardo medio de una clase debemos
aumentar el de otra(s)

!

5/53





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

Á

Max-min Fair

• Asignar recursos en orden creciente de demanda
• Ningún cliente recibe más de lo que solicita
• Aquellos cuya demanda no se pueda satisfacer se

reparten el remanente del recurso

• Se pueden incluir pesos

6/53



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

Á

Max-min Fair (Ejemplo)

• Recurso: 10
• Demandas: 2, 2.6, 4 y 5
• 10/4 = 2.5

– Demasiado para el primer cliente
– Asignarle 2 y queda 0.5

• Ese 0.5 repartirlo entre los otros 3:

– 0.5/3 = 0.167
– Asignaciones [2, 2.67, 2.67, 2.67]
– Demasiado para el segundo cliente
– Asignarle 2.6 y quedan 0.07

• Repartir ese 0.07 entre los otros 2:

– 0.07/2 = 0.035
– Asignaciones [2, 2.6, 2.703, 2.705]

7/53





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

Á

FCFS (FIFO)

• Almacenamiento y reenvío
• Es el método más rápido y sencillo de implementar
• Se suele utilizar por defecto (Best Effort)
• Limitado por la capacidad del buffer ante congestión
• No permite diferenciar entre distintos tipos de paquete

8/53



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

Á

Priority Queueing (PQ)

• Packets in the high-priority queue are always sent first
• Packets in the low-priority queue are not sent until all the high-priority

queues become empty (multilevel priority with exhaustive service)

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

prioritario.

9/53



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

Á

Round Robin (RR)

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

tiempo fijo

10/53





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

Á

GPS

• Algoritmo basado en flujos, cada uno a una cola
• PS = Processor Sharing : Cada uno de los N flujos recibe 1/N
• GPS = Generalized Processor Sharing : pesos a cada uno
• A gran escala cada clase obtiene un servicio proporcional al peso

asignado

• Asegura que las diferentes colas no se queden privadas de un mínimo

ancho de banda

• No da garantías totales como PQ
• Max-min fair (y por ser fair ofrece protección)

11/53



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

Á

WRR

• Weighted Round Robin
• Aproximación de GPS (Generalized Packet Sharing) para el caso de

paquetes

• Opera en “turnos” (rounds). En cada turno visita cada cola (en round-

robin)

• Divide el peso por el tamaño medio de los paquetes del flujo
• En la visita sirve uno o más paquetes de forma que la cantidad sea

proporcional al peso asignado a la cola
• Fair por encima de la escala del turno

12/53



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

Á

WFQ

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

caso de paquetes

• Equivalente a PGPS
• Emplea un reloj virtual
• Calcula el comienzo y 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

13/53





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

Á

Típica implementación de WFQ

• Cada flujo es una “conversación” reconocida por info. de layer 3

(direcciones IP, precedencia) y de layer 4 (puertos)

• Pesos en función de los bits de precedencia de los paquetes
• No requiere configuración
• No escala (una cola por conversación)
• CBWFQ

– Class Based WFQ
– Especificar los filtros (clases) que determinan los paquetes que van

a cada cola (una por clase, no por flujo)

– Especificar peso para cada cola

∑ Bwi < 75%

14/53



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

Á

Tocken bucket + WFQ

• PGPS permite ofrecer garantías de límite de retardo
• Si:

– Flujo restricción (σ, ρ) (el resto puede no estar conformado)
– Camino con h saltos (todos WFQ)
– Se le ha asignado al menos una tasa de ρ en todos ellos

• Entonces:

– El retardo end-to-end está acotado

arriving
traffic

token rate, ρ

bucket size, σ

WFQ

WFQ

WFQ

15/53





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

Á

Low Latency Queueing (LLQ)

• Añade una PQ (Priority Queue) a CBWFQ = PQ-CBWFQ = LLQ
• Recomendable para tráfico multimedia (VoIP): bajo retardo y

jitter.

• Se puede configurar junto al resto de colas CBWFQ como una

cola más asociada a una clase determinada.

LLQ se comporta como una Priority Queue
Priority Queue..
LLQ se comporta como una

V: voice

16/53





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

Á

Class Based Queueing (CBQ)

• Puede contener diferentes planificadores

17/53

NUEVOS SERVICIOS DE RED EN INTERNET
Área de Ingeniería Telemática

Queueing





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

Á

Queue Management

Pasivo
• Drop-Tail (la más habitual)

– Simple
– Introduce sincronización global cuando hay varias conexiones TCP

atravesando ese enlace

– Controla la congestión pero no la evita, posible synch.

• Head-drop

– Tira los paquetes que más tiempo llevan en el buffer
– Probablemente ya han sido retransmitidos (TCP)
– Probablemente ya llegan tarde (UDP/RTP)
– Controla la congestión pero no la evita, posible synch

• Random-Drop (ante cola llena)

– Se puede reducir la sincronización global pero no controlar UDP
– Controla la congestión pero no la evita

19/53





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

Á

Queue Management

Activo (AQM)
• Pensando en TCP, no controla UDP igual de bien
• Evita sincronizaciones, menores retardos y fluctuaciones
• TCP regula su tasa al detectar pérdidas (Congestion avoidance)

TCP Tahoe

• Early-Random-Drop (cola no llena)

– Si la cola excede un nivel se tira cada paquete que llega con una

probabilidad fija

?

20/53

a Active Queue Management

• RED (Random Early Detection)

– RFC 2309
– Evalúa la ocupación media del buffer (exponential weighted moving

average)

– Descartar paquetes probabilísticamente antes de la congestión
– Ojo: Con mala configuración se comporta peor que drop-tail



I

I



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



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

Á

1

y maxp

t
i
l
i

g
n
i
k
r
a
M
/
g
n
i
p
p
o
r
D

b
a
b
o
r
P

0

Minth

Maxth

100%

21/53

Av. Queue Size

a Active Queue Management

• WRED (Weighted RED)

– Emplea un Minth diferente para diferentes clases de tráfico
– Mayor cuanto mayor es el valor de precedenci