Passos, D. e Albuquerque, C. V. N.
IEEE/ACM Transactions on Networking - 2011
Gabriel Marçal de Brito - [email protected]
Computação Móvel – 2012.1
Roteiro
 Introdução
 XXXxxxx
Introdução
 Wireless Mesh Networks (WMNs)
 Usualmente soluções baseadas no padrão IEEE 802.11

Múltiplas taxas de transmissão: 1 – 54 Mbit/s
 Seleção da melhor taxa de transmissão não é trivial
 Balanço entre capacidade do enlace e taxa

PER aumenta com a taxa para mesmo SNR
 Roteamento dinâmico baseado em métricas
 Dificuldade em obter métricas consistentes

Características do meio aéreo, avaliadas pelas métricas, dependem
da taxa de transmissão utilizada
Introdução
 Tais questões são, historicamente, tratadas de forma
independente
 Um método cooperativo cross-layer é proposto
 Metric-Aware Rate Adaptation (MARA)


Adaptação de taxa de transmissão baseado em métricas
Ajuste do custo dos enlaces baseado na taxa utilizada
Trabalhos relacionados
 Métricas de Roteamento
 Algoritmos para adaptação de taxa
 Abordagens conjuntas
Trabalhos relacionados
 Métricas de Roteamento
 Hop Count

Não considera enlaces heterogêneos
 Expected Transmission Count (ETX)

Estima a quantidade de transmissões por PER
 Expected Transmission Time (ETT)

Considera como custo o delay no enlace x ETX (PER)
 Minimum Loss (ML)

Considera como custo a própria taxa de erros (PER)
 Outros...
Trabalhos relacionados
 Métricas de Roteamento
 Hop Count

Não considera enlaces heterogêneos
 Expected Transmission Count (ETX)

Estima a quantidade de transmissões por PER
 Expected Transmission Time (ETT)

Considera como custo o delay no enlace x ETX (PER)
 Minimum Loss (ML)

Considera como custo a própria taxa de erros (PER)
 Outros...
Trabalhos relacionados
 Algoritmos para adaptação de taxa
 Auto Rate Fallback (ARF)

Baseado em falhas e sucessos na transmissão de quadros
 SampleRate
 Baseado no registro do menor atraso (retransmissão e overhead)
 SNR
 Baseado na SNR no receptor (ideal, requer informação futura)
 Receiver-Based Auto Rate (RBAR)
 Notifica taxa via CTS (RTS/CTS)
 Snoopy Rate Adaptation (SRA), Robust Rate Adaptation
Algorithm (RRAA) e Collision-Aware Rate Adaptation (CARA)

Diferenciam perdas por colisão e por degradação do canal
Trabalhos relacionados
 Algoritmos para adaptação de taxa
 Auto Rate Fallback (ARF)

Baseado em falhas e sucessos na transmissão de quadros
 SampleRate
 Baseado no registro do menor atraso (retransmissão e overhead)
 SNR
 Baseado na SNR no receptor (ideal, requer informação futura)
 Receiver-Based Auto Rate (RBAR)
 Notifica taxa via CTS (RTS/CTS)
 Snoopy Rate Adaptation (SRA), Robust Rate Adaptation
Algorithm (RRAA) e Collision-Aware Rate Adaptation (CARA)

Diferenciam perdas por colisão e por degradação do canal
Trabalhos relacionados
 Abordagens conjuntas
 Multirate Anypath Routing Problem



Modificação do ETT
PER é considerada a probabilidade de nenhum dos vizinhos
decodificar o pacote de forma correta (anycast routing)
Alto overhead já que é necessário o envio de probes para cada
taxa possível
Trabalhos relacionados
 Abordagens conjuntas
 Multirate Anypath Routing Problem



Modificação do ETT
PER é considerada a probabilidade de nenhum dos vizinhos
decodificar o pacote de forma correta (anycast routing)
Alto overhead já que é necessário o envio de probes para cada
taxa possível
Abordagem MARA
 MARA aborda a métrica de roteamento e a seleção de
taxa de forma coordenada
 A métrica avalia rotas de acordo com o atraso fim-afim esperado:
 MARAab = mini (ETXiab x ps / Ri)



Ri representa a i-ésima taxa disponível;
ETXiab representa a métrica ETX na rota a-b na taxa Ri;
ps é o tamanho do pacote de probe.
 O mecanismo de adaptação de taxa seleciona Ri que
minimiza o atraso
Abordagem MARA
 ETX em cada uma das taxas Ri é necessário
 Probes em todas as taxas aumentariam overhead
 MARA utiliza uma conversão de probabilidades de
sucesso de transmissão:






Relaciona SNR, taxa de transmissão, tamanho da probe e PER
a partir de dados experimentais;
!Pab = 1 – Pab (idem para ba)
SNRab = findSNR(!Pab;sourceRate;probeSize) (idem para ba)
!newPab = findPER(SNRab;targetRate;probeSize) (idem para ba)
newPab = 1 - !newPab (idem para ba)
newETX = 1 / (newPab * newPba)
Abordagem MARA
 Comportamento assintótico da função SNR x PER
 PER tende a 1 quando SNR diminui
 PER tende a 0 quando SNR aumenta
 Muitos valores de SNR podem ser mapeados para
valores de PER extremos
Abordagem MARA
Abordagem MARA
 MARA utiliza probes em 1, 18, 36 e 54 Mbit/s
 Curvas PER x SNR cruzam-se em intervalos úteis
 O algoritmo escolhe a taxa de probe mais alta cujo PER
é menor do que 1 (interseção)
 MARA envia 1 probe/período , partindo de 1 Mbit/s até
54 Mbit/s
 Ainda menos overhead pois bloqueia o meio aéreo por
menos tempo
Abordagem MARA
 Limitação na granularidade de dados (tabelas) requer
o uso de funções de interpolação dos dados:
Variações: MARA-P e MARA-RP
 MARA-P considera o tamanho do pacote a ser
transmitido no processo de adaptação de taxa
 Classes de pacotes são definidas de acordo com
intervalos de tamanho (ex.: 1-300 bytes)
 Usa métrica MARA para o maior valor do intervalo
 MARA-RP considera o tamanho do pacote a ser
transmitido no processo de atribuição de custo
 Mesmo processo de MARA-P
 Cria k grafos para k classes de pacotes

Shortest-path resulta em k tabelas de roteamento
Simulações
 Cenários utilizados no ns-2:
 300 segundos de fluxo TCP entre nós específicos (runs)
 Benchmarks: todas as combinações de métricas Hop Count,
ETX, ML, ETT, com os mecanismos de adaptação ARF,
SampleRate e SNR
 Topologias: indoor (ReMoTE), grid e random
 Modelo de propagação de sombreamento (probabilístico)
 Compara-se MARA aos demais mecanismos em relação:



Throughput
Atraso fim-a-fim
Perda de pacotes fim-a-fim
Simulações
 Implementação como extensões do OLSR em ns-2
 Versão modificada do OLSR


MPRs reduzem o overhead, porém só funcionam para a
métrica Hop Count
MPRs foram removidos do protocolo OLSR para propiciar
utilização de outras métricas
Simulações - Indoor
 Topologia utilizada e identificação dos nós:
Simulações - Indoor
 Tput TCP (nós 0-1 x nós 0-9):
 Atraso e perda de pacotes médios
Simulações – Grid e Random
 Topologias (grid x random, nós 0-48)
 Tput TCP (grid x random)
Simulações – Roteamento
 Rotas (grid – ETT, ML, ETX, Hop Count, MARA)
Simulações – MARA-P e MARA-RP
 Comparação de atraso e perda de pacotes médios
 Atraso fim-a-fim de cada pacote de áudio (120B, 48kb/s)
Experimento – Indoor
 Tput e RTT dos fluxos TCP e ICMP (nós 0-9)
Experimento – Indoor
 Comparação entre MARA, MARA-P e MARA-RP no
experimento:
Conclusões
 A abordagem coordenada de seleção de taxa e cálculo
de métricas de roteamento conferem melhor
desempenho às WMNs
 O modelo de estimação de PER baseado na taxa de
transmissão permite obter estatísticas válidas com
baixo overhead
 MARA provê ganhos expressivos em relação aos
mecanismos tradicionais utilizados
 As variações de MARA não oferecem melhorias
significativas em relação à abordagem original