View
111
Download
3
Category
Preview:
Citation preview
Departamento de Ciência da ComputaçãoInstituto de Computação
Universidade Federal Fluminense
Saching Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
Em IEEE/ACM Transactions on Networking, VOL. 16, NO. 3, Junho 2008
Apresentador: Igor C. G. Ribeiro
XORs in the Air: Practical Wireless Network Coding
Computação Móvel 2012/1
• O artigo introduz o COPE;
• Nova arquitetura de encaminhamento de pacotes;
• Utiliza codificação de redes;
• Aumenta o throughput em redes em malha sem fio estacionárias.
Introdução
Motivação
Como enviar mais informações utilizandomenos transmissões?
Motivação
Redução de 4 transmissões para 3.Pode-se aproveitar a transmissão extra
para enviar mais dados.Seria interessante combinarmos mais
pacotes para reduzir ainda mais o número de transmissões.
Ideia
Nós em modo promíscuo podem capturaro tráfego dentro de sua área de cobertura.
Pacotes capturados são armazenadospor um determinado intervalo de tempo.Resultado: Cada nó conhece um númeromaior de pacotes, favorecendo assim a
codificação.
COPE – Visão Geral
Aplicação
Transporte
Rede
Enlace
Física
Aplicação
Transporte
Rede
Enlace
Física
Codificação
1. Audição Oportunista• Escuta o tráfego nos nós sem fio;
• Guarda os pacotes monitorados por um intervalo de tempo T;
• Cada nó envia em broadcast mensagens de recepção.
COPE – Visão Geral
2. Codificação Oportunista
COPE – Visão Geral
Como combinar os pacotes de modo a obterO maior ganho possível?
2. Codificação Oportunista
COPE – Visão Geral
Regra:
3. Aprendendo o estado dos vizinhos• Através das mensagens de recepção;
• Através da tentativa de adivinhação
COPE – Visão Geral
• O quão benéfico é o COPE?
• Seu ganho de throughput depende das oportunidades de codificação, que por sua depende dos padrões de tráfego.
Entemdendo os Ganhos do COPE
Ganho com a codificação
DefiniçãoRazão entre o número de transmissões requeridas
pela abordagem sem codificação e o númeromínimo de transmissões requeridas pela
abordagem com codificação
Exemplo: Alice e BobSem codificação: 4 transmissõesCom codificação: 3 transmissões
Ganho com a codificação:
• Qual é a capacidade teórica de uma rede wireless que implementa o COPE?
• A capacidade de network coding genérico para tráfego unicast é ainda um problema em aberto.
• Entretanto é possível analisar algumas topologias básicas que revelam alguns fatores que afetam o COPE.
Ganho com a codificação
• Premissas:• Nós identicos;• Rádios omni-direcionais;• Sinal perfeitamente audível dentro
de um raio;• O sinal não é ouvido de forma
alguma fora do raio;• Se dois nós podem ouvir um ao
outro, o algoritmo de roteamento escolherá o link direto.
Ganho com a codificação
Ganho com a codificação
Na ausência de audição oportunista o ganhoMáximo devido a codificação tende a 2 conforme o
Número de nós intermediários aumenta.
Ganho com a codificação
Na ausência de audição oportunista não é possívelobter nenhum ganho pela codificação. Porém, com
a audição oportunista o ganho é igual a 1,33.
Ganho com a codificação
n1,n3 podem escutar n4,n5 e vice-versa.Transmissões sem codificação: 8Transmissões com codificação: 5
Ganho com a codificação: :
n1 n2 n3
n5
n4
Ganho com a codificação + MAC
O MAC tenta ser justo e divide igualmente a largura de banda entre todos os nós.
O nó intermediário tem que enviar o dobro detransmissões que os nós da ponta.
O nó intermediário se torna o gargaloMetade dos pacotes na fila do nó Intermediário são descartados.
Com o uso do COPE, o nó intermediária faz oXOR entre pares de pacotes, permitindo que tais pacotes sejam drenados duas vezes mais rápido.
Dessa maneira, o ganho pela junção entreCodificação e MAC para o exemplo de Alice e Bob
é 2.
Assume-se que todos os nós tem continuamentetráfego para enviar, mas está limitado pela
largura de banda alocada pela camada MAC.
Para topologias com um único gargalo, o ganhode codificação + MAC é calculado como a razão
entre a taxa de drenagem com COPE e a taxade drenagem sem o COPE.
Ganho com a codificação + MAC
Ganho com a codificação + MAC
• Não atrasar o envio de pacotes;• Dar preferência a fazer XOR com
pacotes de mesmo tamanho• XOR com pacotes de tamanhos
diferentes reduz a economia de largura de banda;
• Separa os pacotes nas categorias grande e pequeno;
• No XOR de pacotes de tamanhos diferentes, o menor sofre padding com 0s.
Implementação – Algoritmo deCodificação
• Não fazer XOR de pacotes destinados ao mesmo próximo salto;
• Não fazer XOR de pacotes gerados no próprio nó que está codificando;
• Nos dois casos anteriores o próximo salto não seria capaz de decodificar os pacotes;
• COPE mantêm duas filas virtuais por vizinho, uma para pacotes grandes e outra para pequenos;
Implementação – Algoritmo deCodificação
• Nó codifica n pacotes• é a probabilidade do próximo salto ter
o pacote i• A probabilidade do próximo salto
conseguir decodificar o pacote é:
Implementação – Algoritmo deCodificação
= x x...x
• Resumo:• Cada nó tem uma fila FIFO – Fila de
Saída;• Cada nó tem duas filas virtuais por
vizinho, uma para pacotes pequenos (< 100 bytes) e uma para pacotes grandes;
• As filas para um vizinho A contêm ponteiros para pacotes na file da saída cujo próximo salto é A
Implementação – Algoritmo deCodificação
• Resumo:• Cada nó mantém um Hashtable,
indexado pelo ID do pacote, que contém o packet info. Essa informação fornece a probabilidade de cada vizinho ter esse pacote.
Implementação – Algoritmo deCodificação
Implementação – Algoritmo deCodificação
Id Pacote Probabilidade
.
.
.
Pacotes Grandes
Pacotes Pequenos
Fila de Saída
HashTable
Estrutura dos Nós
• Cada nó mantém um hashtable, indexado pelo ID do pacote, onde os pacotes enviados, recebidos e monitorados pelo nó são guardados;
• De tempos em tempos esse hashtable é limpo;
• Quando um pacote tem que ser decodificado, o nó verifica os IDs dos pacotes que compõem o pacote codificado e recupera os mesmos do hashtable.
Implementação – Algoritmo deDecodificação
• Problema: usar 802.11 em modo broadcast ou unicast?• Broadcast não fornece
confiabilidade;• Broadcast não permite backoff,
reduzindo o throughput em virtude do excesso de colisões.
Implementação – Pseudo-Broadcast
• Solução: Pseudo-broadcasts• Pacotes codificados são enviados
em modo unicast;
• O endereço MAC de destino é setado para um dos destinatários;
• Após o cabeçalho de camada 2, é inserido o cabeçalho XOR que contém todos os destinatários daquele pacote;
Implementação – Pseudo-Broadcast
• Solução: Pseudo-broadcasts• Todos os Nós operam em modo
promíscuo e podem receber o pacote enviado;
• Se o endereço MAC do pacote recebido não bate com o do nó que o recebeu, esse checa o cabeçalho XOR;
• Se o nó for um dos destinatários, o pacote é processado. Caso contrário o pacote é armazenado.
Implementação – Pseudo-Broadcast
• Solução: Pseudo-broadcasts• Assim, o pacote é entregue a todos
os destinatários utilizando o modo unicast.
Implementação – Pseudo-Broadcast
Problema de confiabilidade e backoff resolvidos?
Não!
• Somente a camada MAC do real destinatário do pacote enviará ACK;
• Os pacotes enviados para os outros destinatários também podem ser perdidos.
• Um determinado nó que recebe um pacote codificado pode não ter informações suficientes para decodificar o mesmo e assim esse pacote é perdido.
Implementação – Pseudo-Broadcast
O COPE precisa então prover por contaprópria um sistema de ACKs e
Retransmissões!
• Pacotes nativos utilizam o esquema de ACKs e retransmissões do 802.11;
• Utilizar o mesmo esquema para pacotes codificados acarreta em um overhead excessivo;
• A solução proposta pelo COPE é utilizar ACKs assíncronos.
Implementação – ACKs Assíncronos e Retransmissões
• A utilização de ACKs assíncronos pode acarretar em reordenação dos pacotes;
• A reordenação é para o TCP um sinal de congestionamento;
• Dessa maneira, se muitos pacotes forem reordenados o TCP irá reduzir a taxa, reduzindo assim o throughput.
Implementação – ACKs Assíncronos e Retransmissões
SoluçãoOrdenar os pacotes antes de envia-los
Para a camada de transporte!
• Cada nó mantém um agente que intercepta os pacotes antes de serem enviados para a camada de transporte;
• Caso o pacote pertença a um fluxo TCP e o IP de destino seja o IP do nó em questão:• O agente verifica se o pacote
recebido não causará uma lacuna na sequência de pacotes.
• Caso contrário o pacote é encaminhado normalmente.
Implementação – Prevenção de Reordenação de Pacotes TCP
Implementação – Funcionamento
Resultados Experimentais – Topologias Simples
ObjetivoComparar os ganhos reais com os ganhos
teóricos já analisados.
1) Fluxos TCP: executado em três topologias diferentes (Alice e Bob, “X” e a topologia em curz)• O ganho de throughput foi medido
através de 40 execuções diferentes do experimento;
Resultados Experimentais – Topologias Simples
Resultados Experimentais – Topologias Simples
Alice e Bob
Resultados Experimentais – Topologias Simples
“X”
Resultados Experimentais – Topologias Simples
Cruz
Resultados Experimentais – Topologias Simples
Conclusão dos Experimentos com TCPQuando o tráfego realiza controle de
Congestionamento, o ganho de throughputObtido corresponde ao ganho por codificação e
Não ao ganho por MAC + codificação
2) O mesmo experimento foi realizado nas mesmas topologias, mas agora utilizando fluxos UDP
Resultados Experimentais – Topologias Simples
Resultados Experimentais – Topologias Simples
Alice e Bob
Resultados Experimentais – Topologias Simples
“X”
Resultados Experimentais – Topologias Simples
Cruz
Resultados Experimentais – Rede AD HOC Real
ObjetivoVerificar como o COPE se comporta em
uma rede ad hoc real.
1) Fluxos TCP• Os fluxos chegam de acordo com a
distribuição de Poisson;• A origem e o destino dos pacotes
são escolhidos aleatoriamente dentre os 20 nós possíveis;
Resultados Experimentais – Rede AD HOC Real
1) Fluxos TCP• Foi notado um ganho insignificante
(2-3%)
Resultados Experimentais – Rede AD HOC Real
TerminaisOcultos
Grande n•De Colisões
TCP ReduzA Taxa
Poucas Oportunidades deCodificação
Mau Uso doMeio
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede AD HOC Real
1) Fluxos TCP• Se removermos as perdas devidas a
colisões os fluxos TCP se beneficiariam do COPE?
• Todos os 20 nós da rede foram dispostos de tal forma que estivessem dentro do alcance da detecção de portadora uns dos outros;
• O grafo de roteamento e a taxa de erros dentro dos nós foram mantidas.
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede AD HOC Real
1) Fluxos UDP• Chegadas Poisson;• Origem e destino escolhidos
aleatoriamente;• Carga na rede inserida através do
alteração na taxa de chegada;• Para cada taxa de chegada (25 no
total) foram realizados 10 experimentos com o COPE ligado e 10 com o mesmo desligado.
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede AD HOC Real
Quanto da codificação é devida às mensagens de recepção e quanto é devida
à adivinhação?
Se n pacotes são codificados e desses npacotes, k pacotes são codificados devidoà mensagens de recepção, n-k pacotes são
codificados devido à adivinhação.
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede AD HOC Real
Resultados Experimentais – Rede Mesh Real
ObjetivoVerificar como o COPE se comporta em
uma rede mesh real.
• Fluxos UDP;• De e para o gatway mais próximo• Nós do testbed divididos em quatro
conjunto;• Cada conjunto se comunica com a
Internet através de um nó que faz o papel do gatway;
• Experimento controlado através da variação da razão entre o tráfego de upload e o tráfego de download.
Resultados Experimentais – Rede Mesh Real
Resultados Experimentais – Rede Mesh Real
Resultados Experimentais – Rede Mesh Real
Resultados Experimentais – Rede Mesh Real
• O artigo apresentou o COPE – Sistema que tenta tirar proveito da natureza de trasmissões broadcast presentes nas redes wireless para realizar o processo de codificação de pacotes, com o objetivo de aumentar o throughput.
• Em geral, o COPE apresentou um grande ganho no throughput.
Conclusão
• Alguns comportamentos nos gráficos não foram bem explicados;
• Alguns parâmetros mostrados nos gráficos não foram bem definidos.
Críticas
Recommended