PDF de programación - Queueing

NUEVOS SERVICIOS DE RED EN INTERNET

Área de Ingeniería Telemática

Queueing

Área de Ingeniería Telemática

http://www.tlm.unavarra.es



Máster en Comunicaciones

Objetivos

•  Conocer los mecanismos de gestión

activa de cola



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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E





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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

Congestion Avoidance
•  También llamado Active Queue Management
•  Su objetivo es evitar que interfaces o colas se

congestionen

•  Diseñado para TCP pues es un protocolo que
reacciona ante congestión reduciendo la tasa de
envío

Passive Queue Management



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
Á

Drop-Tail (la más habitual)
•  Simple
•  Descarta un paquete independientemente de su importancia
•  Controla la congestión pero no la evita
• 

(...)



T
E
N
R
E
T
N

I


N
E





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

Passive Queue Management

Drop-Tail (la más habitual)
•  Simple
•  Descarta un paquete independientemente de su importancia
•  Controla la congestión pero no la evita
•  TCP puede enviar ráfagas (limitadas por el tamaño de la ventana)
•  Si llega una ráfaga a una cola casi llena se perderán varios paquetes
•  Ante pérdidas TCP reduce ventana de congestión y así velocidad de envío
•  Varias conexiones pueden entrar simultaneamente en este proceso de control

de la congestión y reducirse en gran medida el throughput global
Introduce sincronización global con varias conexiones TCP en el enlace
(...)

• 
• 





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

Passive Queue Management

Drop-Tail (la más habitual)
•  Simple
•  Descarta un paquete independientemente de su importancia
•  Controla la congestión pero no la evita
•  TCP puede enviar ráfagas (limitadas por el tamaño de la ventana)
•  Si llega una ráfaga a una cola casi llena se perderán varios paquetes
•  Ante pérdidas TCP reduce ventana de congestión y así velocidad de envío
•  Varias conexiones pueden entrar simultaneamente en este proceso de control

de la congestión y reducirse en gran medida el throughput global
Introduce sincronización global con varias conexiones TCP en el enlace

• 
•  Unos pocos flujos pueden monopolizar el recurso
• 
•  Pero la cola es para absorber ráfagas, luego no se podrán

La cola se mantiene llena por largos periodos

•  Colas llenas no lleva a mayor throughput sino a menor

•  Colas poco ocupadas llevan a mayor throughput y

absorber

throughput

menor retardo

Passive Queue Management



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

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

Active Queue Management



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

•  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

Active Queue Management



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

Early-Random-Drop (cola no llena)
•  Si la cola excede un nivel se tira cada paquete que llega con una

probabilidad fija



Weighted Tail Drop
•  Se asignan umbrales en la cola a diferentes clases de tráfico
•  Cuando se alcanza el umbral U1 se descartan los paquetes que

?

lleguen de la clase 1

•  Cuando se alcanza el umbral U2 se descartan también los paquetes
•  De la tercera clase se descartarán solo cuando se llene la cola

que lleguen de la clase 2

U2

U1

Active Queue Management



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

RED (Random Early Detection)
•  RFC 2309
•  Descartar paquetes probabilísticamente antes de la congestión
•  Evalúa la ocupación media del buffer
•  Cálculo mediante exponential moving average
•  Para w bajo la media sigue los cambios rápidos del valor instanténeo

qavg = qavg_old 1−

"
$
#

1
2w

%
'+ qcurrent
&

"
$
#

1
2w

%
'
&

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%

Av. Queue Size

Active Queue Management



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

RED (Random Early Detection)
•  Difícil medir sus beneficios
•  Con mala configuración podría comportarse peor que drop-tail
•  Se han propuesto bastantes más algoritmos de AQM
•  RED es el más extendido en implementaciones

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%

Av. Queue Size

a
c
i
t

Active Queue Management
WRED (Weighted RED)
•  Emplea un Minth y Maxth diferente para diferentes clases de
•  Mayor cuanto mayor es el valor de precedencia

tráfico

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

T
E
N
R
E
T
N

e
d

I



i

l



I

I



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



a
e
r
Á

I


N
E

Otras propuestas: Adaptive RED (ARED), RED In & Out (RIO),
Flow weighted RED (FRED)...

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

Maxth2

Av. Queue Size

Minth2

Minth1

Maxth1

100%


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

ECN

•  Explicit Congestion Notification
•  RFC 3168
•  Extensión a RED: marcar en vez de descartar (salvo cuando se

alcanza ocupación máxima que sí se descarta)

•  Bit ECT = ECN-Capable Transport
•  Bit CE = Congestion Experienced
•  Requiere extender el control de congestión de TCP

ECN field
ECT

CE

ECN Field
ECT CE
0
0
1
1
offset

Longitud
M
F

D
F

13-bit fragmentation

0 Not-ECT Paquete no emplea ECN
1 ECT(1)
0 ECT(0)
1

Extremos ECN-capable
idem (recomendado)
Congestion experienced

CE

Versión Header
Length

ToS
16-bit identifier
TTL

Protocolo Header checksum


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

ECN y TCP
•  Emplea dos flags nuevos en la cabecera
•  ECN-Echo (ECE): para que el receptor del paquete con CE

activo devuelva esta indicación a emisor

•  Emisor reacciona como si hubiera detectado una pérdida
•  CWR flag: emisor notifica a receptor en el siguiente paquete de

que ha recibido el ECE

•  Poco extendida la implementación de ECN en routers y hosts

Puerto origen

Puerto destino

Long
cab.

Número de secuencia
Número de confirmación
No
usado
Checksum
Opciones (longitud variable)

Ventana

U A P R S F
U

Puntero a urgentes

Datos de
aplicación

C
W
R

E
C
E

U
R
G

A
C
K

P
S
H

R
S
T

S
Y
N

F
I
N

NUEVOS SERVICIOS DE RED EN INTERNET

Área de Ingeniería Telemática

Implementación

Implementación



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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

Implementación



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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

NUEVOS SERVICIOS DE RED EN INTERNET

Área de Ingeniería Telemática

Equipos

D-Link DES-1210



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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

D-Link DES 3828P



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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E





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
Á


a
c
i
t



T
E
N
R
E
T
N

I


N
E

Cisco Catalyst 2950 (SI)

NETWORK CONTROL
Cisco Catalyst 2950SX-48, 2950T-48, 2950SX-24, 2950-24, and 2950-12 switches deliver LAN-
edge QoS, supporting two modes of reclassification. One mode-based on the IEEE 802.1p
standard-honors the class-of-service (CoS) value at the ingress point and assigns the packet to
the appropriate queue. In the second mode, packets can be reclassified based on a default
CoS value assigned to the ingress port by the network administrator. In the case of frames
that arrive without a CoS value (such as untagged frames), these Cisco Catalyst 2950 Series
switches support classification based on a default CoS value per port assigned by the network
administrator. After the frames have been classified or reclassified using one of the above
modes, they are assigned to the appropriate queue at the egress. Cisco Catalyst 2950
Series switches support four egress queues, which allow the network administrator to