PDF de programación - ALGORITMOS DE ADAPTACIÓN VELOCIDAD BINARIA

SIMULACIÓN DE PROTOCOLOS DE ENRUTAMIENTO

PARA REDES MÓVILES AD-HOC MEDIANTE

HERRRAMIENTA DE SIMULACIÓN NS-3

ALGORITMOS DE ADAPTACIÓN

VELOCIDAD BINARIA

Contenidos

1. Auto Rate Fallback (ARF)
2. Adaptive Auto Rate Fallback (AARF)
3. Adaptive Auto Rate Fall back with Collision Detection

(AARF-CD)

4. Collision-Aware Rate Adaptation (CARA)
5. Robust Rate Adaptation Algorithm (RRAA)
5. Robust Rate Adaptation Algorithm (RRAA)

Todos los algoritmos son conformes a las normas IEEE 802.11

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

2

Rate Adaptation (RA)

• Diferentes tasas especificadas en las normas

o 802.11b: 1, 2, 5.5, 11 Mbps
o 802.11a: 6, 9, 12, 18, 24, 36, 48, 54 Mbps
o 802.11g: 12 regímenes binarios (11a+11b)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

Rate Adaptation (RA)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

3

4

Rate Adaptation (RA)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

Auto Rate Fallback (ARF)

• Algoritmo de optimización de la velocidad binaria para

sistemas LAN 802.11

• Cada transmisor aumenta su tasa después de un
número mínimo de transmisiones con éxito a una
cierta velocidad

• Después de un número fijo de transmisiones erróneas

consecutivas, se disminuye la tasa binaria a un valor
menor anteriormente usado
menor anteriormente usado

• Ejemplo de implementación (ARF primitivo):

• Cuando ocurren dos errores de transmisión

consecutivos, se disminuye la tasa binaria y se
pone en marcha un temporizador

• Si se producen 10 transmisiones correctas (ack) o
expira el temporizador, se aumenta la tasa binaria
y se reinicia el temporizador

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

5

6

Auto Rate Fallback (ARF)

• Ejemplo (continuación):

• Cuando se incrementa la tasa, si la primera

transmisión (probing tx) no es correcta,
inmediatamente se disminuye la tasa binaria y se
reinicia el temporizador

El esquema adolece principalmente de dos defectos:

• Si las condiciones del canal varían muy rápidamente, el

sistema no llega a adaptarse nunca
sistema no llega a adaptarse nunca

o Las interferencias producidas por paquetes transmitidos por otros

transmisores 802.11 se limitan al intervalo de un solo paquete

o La tasa no se decrementa hasta que se producen 2 errores o no se

incrementa hasta experimentar 10 transmisiones correctas

no se adapta a los cambios a nivel intrapaquete

• Si las condiciones del canal son estáticas, tratará de aumentar

la tasa cada 10 transmisiones correctas, teniendo que
decrementarla de nuevo cuando la probing tx resulte errónea,
con la consiguiente pérdida de throughput de la aplicación

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

Auto Rate Fallback (ARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

7

8

Auto Rate Fallback (ARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

9

Auto Rate Fallback (ARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

10

Adaptive Auto Rate Fallback (AARF)

• Lo habitual es que las condiciones del canal sean

estáticas
• Ejemplo: usuarios de laptops que se sitúan en un determinado

lugar de una oficina y no se desplazan mientras lo utilizan

• En esos casos, ARF no es óptimo (siempre trata de
aumentar la tasa después de Nup transmisiones con
éxito, provocando fallos y las consiguientes
retransmisiones)
retransmisiones)

• AARF se basa en la modificación del valor de Nup de

forma dinámica, teniendo en cuenta la historia de las
condiciones del canal

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

11

Adaptive Auto Rate Fallback (AARF)

• Ejemplo de implementación de AARF

• Si el probing falla, se decrementa la tasa (igual que en ARF) y
se multiplica por 2 (con un límite máximo de 50) el número de
transmisiones consecutivas con éxito necesarias para
incrementar la tasa, Nup

• Cuando se decrementa la tasa por dos paquetes fallidos

consecutivos, se restablece el valor primitivo de Nup (número
de paquetes consecutivos con éxito necesarios para
incrementar la tasa)
incrementar la tasa)

Con esta estrategia se aumenta el período entre

intentos fallidos de incrementar la tasa (menor
número de retransmisiones, mejor throughput)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

12

Adaptive Auto Rate Fallback (AARF)

i

i

n
ó
s
m
s
n
a
r
t



e
d
o
d
o
M

i

i

n
ó
s
m
s
n
a
r
t



e
d
o
d
o
M

4

3

2

1

0

4

3

2

1

0

10 20 30 40

50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210

Iteración

10 20 30

50

90

170

ARF

AARF

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Iteración

Loja - 2014

13

Adaptive Auto Rate Fallback (AARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

14

Adaptive Auto Rate Fallback (AARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

15

Adaptive Auto Rate Fallback (AARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

16

Adaptive Auto Rate Fallback (AARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

17

Adaptive Auto Rate Fallback with Collision Detection (AARF-CD)

• Mecanismo RTS/CTS

o se pone en funcionamiento:

• cuando se produce error no estando activado RTS
• después de incrementar la tasa

o se detiene:

error

• después de recibir un cierto número de tramas sin

• después de decrementar la tasa
• después de decrementar la tasa

• El número de tramas correctas consecutivas

necesarias para incrementar la tasa es
adaptativo (AARF)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

18

Adaptive Auto Rate Fallback with Collision Detection (AARF-CD)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

19

Collision-Aware Rate Adaptation (CARA)

• ARF no tiene en cuenta las colisiones que se producen
en entorno multi-usuario (con estaciones escondidas),
y decrementa la tasa cuando se producen los fallos de
transmisión debidos a dichas colisiones

• Distinción entre errores debidos a colisiones y debidos

a pérdidas de propagación para tomar la decisión
correcta de adaptación de tasa de transmisión

• Cuando se producen errores por colisión, el decremento de la
tasa de transmisión puede ser menos agresivo que en el caso
de errores de canal

• Si se producen colisiones, el decremento de la tasa de

transmisión producirá aún más colisiones (mayores tiempos de
transmisión mayor probabilidad de colisionar con estaciones
escondidas)

es necesario distinguir entre fallos por colisiones y fallos por el

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

canal

Loja - 2014

20

Collision-Aware Rate Adaptation (CARA)

• Uso del mecanismo RTS/CTS (Request To Send/Clear

To Send) y de la funcionalidad CCA (Clear Channel
Assessment), incluidos en el estándar IEEE 802.11
• RTS/CTS: acorta el intervalo vulnerable a la colisión,

pero sólo se utiliza para tramas con gran longitud

uso muy marginal en redes inalámbricas
• IEEE 802.11e, 802.11g: se contempla el empleo de las

tramas RTS/CTS, y la consiguiente reserva de un
intervalo de transmisión en el canal, aunque el tamaño
del mensaje a transmitir no supere el umbral (incluyendo
el envío de una trama CTS con dirección igual a la del
transmisor, para compatibilidad hacia atrás de la norma)
• CCA: si se detecta un nivel de energía por encima de un

cierto umbral, se concluye que el canal está ocupado

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

21

Collision-Aware Rate Adaptation (CARA)

RTS Probing:

• La probabilidad de error por pérdidas de propagación del

canal en la transmisión de una trama RTS es
despreciable (pequeña longitud, tasa robusta)

los errores en las tramas RTS siempre se deben a

colisiones

• Los errores de datos posteriores a la transmisión de

RTS/CTS tienen necesariamente que deberse al canal de
propagación, y nunca a colisiones
propagación, y nunca a colisiones

• Aplicando seguidamente ARF, todos los decrementos de

tasa se deberán a errores de propagación, y no habrá
decrementos innecesarios debidos a colisiones

• El envío de tramas RTS/CTS consume ancho de banda y

recursos en la red (habitualmente deshabilitado en las
redes)

Puede limitarse su uso únicamente a los casos en que se

produzcan pérdidas de paquetes

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

22

Collision-Aware Rate Adaptation (CARA)

CARA utiliza el mecanismo CCA para que el transmisor
pueda detecta la colisión de su propia trama con otras
tramas transmitidas

• Se usa como mecanismo suplementario a RTS Probing
• Se trata de estimar el nivel de ocupación del canal
• Cuando el paquete transmitido es muy largo, no se
puede detectar la energía de otra trama más corta
transmitida simultáneamente por otra estación
transmitida simultáneamente por otra estación

Cuando CCA falla, se activa RTS Probing

• No funciona cuando existen estaciones escondidas

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

23

Collision-Aware Rate Adaptation (CARA)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

24

Collision-Aware Rate Adaptation (CARA)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

25

Robust Rate Adaptation Algorithm (RRAA)

ARF, AARF y CARA no pueden adaptarse a todos

los cambios del canal (SNR muy cambiante)

RRAA (Robust Rate Adaptation Algorithm) se

basa en dos principios:

o Obtención de estadísticas a corto plazo (ventana

tem