Backbones Ad Hoc. Aluno: Eduardo Hargreaves Orientador: Luís Felipe M. de Moraes Coppe/UFRJ - Programa de Engenharia de Sistemas e Computação - PDF
Download "Backbones Ad Hoc. Aluno: Eduardo Hargreaves Orientador: Luís Felipe M. de Moraes Coppe/UFRJ - Programa de Engenharia de Sistemas e Computação"
Thalita Camelo Raminhos
1 Backbones Ad Hoc Aluno: Eduardo Hargreaves Orientador: Luís Felipe M. de Moraes Coppe/UFRJ - Programa de Engenharia de Sistemas e Computação
2 Estrutura do Trabalho Motivações MBN TBONE Conclusões
3 Motivações Propostas para tornar as redes Ad Hoc escaláveis Nas redes flat a troca periódica de mensagens de roteamento pode consumir grande parte de banda Solução: protocolos que operam sob demanda. Ex: AODV e DSR
4 Motivações Fase inicial de descobrimento de rotas. Trocas de informação de roteamento apenas durante a comunicação. Funcionam bem com baixo tráfego concentrado em poucos nós.
5 Motivações Mais tráfego, mais fontes, mais rotas a serem descobertas...geralmente a descoberta de rotas é feita través de flooding... As tabelas de roteamento também se tornam maiores Grande latência inicial devido ao período de descobrimento de rotas
6 Motivações Gupta [5] também mostrou que sob condições ideais a capacidade de uma rede Ad Hoc é dada por:
7 Motivações A criação de estruturas hierárquicas é uma solução 2 propostas: MBN e TBONE
8 MBN Supõe nós de maior capacidade Estes nós formam um backbone físico Formação de clusters (sub redes) com um menor número de nós Enlaces de mais alto nível estabelecidos Clusters com multi hops
9 MBN
10 MBN Qual é o número ótimo de backbone nodes?
11 MBN Assumindo tráfego uniforme, para o sistema operar de maneira estável
13 MBN Como eleger líderes? RCC (random competion clustering) Cada nó capaz pede para ser líder Quem escuta um pedido desiste da eleição Contador aleatório para evitar conflitos Funciona com um ou com múltiplos hops
14 TBONE Pretende formar um backbone garantindo QoS e utilização eficiente dos recursos da camada MAC perante a mobilidade e diversos e variados perfis de tráfego
15 TBONE Supõe nós de alta capacidade (BCN) e nós de baixa capacidade (RN) Alta Capacidade: processamento, memória, interesses estratégicos, rádio mais potente BCN: 2 rádios (um de alta capacidade para o backbone) Criação de clusters: RN associados aos BN
16 TBONE: Definições Define 3 sub redes: Bnet: backbone Anet:rede de acesso ao backbone Rede flat convencional
17 TBONE Exemplo
18 TBONE - Hipóteses Todos os cluster transmitem na mesma frequência O backbone tem um canal próprio Nós vizinhos se comunicam (implica em coordenação entre anets vizinhas) MC-Anets MC-Bnets Satélites podem servir para aumentar a cobertura
19 TBONE - Hipóteses Cada BN (cluster Head) controla o acesso ao meio dos seus nós associados A coordenação entre MC-Anets pretende aumentar a eficiência espacial
20 TBONE: Funcionamento 4 etapas: 1)Eleição dos nós de backbone (só participam os nós capazes) 2)Criação dos enlaces de alta capacidade 3)Formação dos clusters 4)Formação da Anets
21 TBONE: Funcionamento Cada BN guarda uma lista local de associados Todos os nós guardam uma lista com seus vizinhos atingidos pelo rádio de baixa capacidade
22 TBONE: Funcionamento Todo BCN guarda uma lista com seus vizinhos atingidos pelo rádio de alta capacidade Mensagens de controle transmitidas periodicamente
23 TBONE: Alocação de recursos Cada BN controla o acesso ao meio de seus associados através de segmentos nos quadros gerados Cada BN transmite mensagens periódicas de sincronização Existe espaço para o acesso aleatório
24 TBONE:Quadro
25 TBONE: Alocação de recursos Cada RN tem um determinado número de segmentos alocados conforme sua demanda Cada BN calcula a capacidade necessária agregada para atravessar a Bnet Deve se verificar também se há recursos na Anet de destino
26 TBONE: Alocação de recursos Cada BN guarda sua lista de métricas contendo: velocidade de processamento indicadores de congestionamento (tamanho da fila, perdas, atraso) Se um não for BCN nem admitido numa Anet ele se comunica da forma convencional
27 TBONE-Eventos 2 Tipos: Causados por modificações topológicas Causados por flutuações no tráfego Cada evento aciona algum mecanismo levando o protocolo a se adaptar a este novo cenário
28 TBONE-Eventos O protocolo é constituído de 4 algoritmos acionados por eventos distintos. Foram definidas 8 classes de eventos: Classe 1 (conectividade) : Verifica (através da lista de vizinho de alta capacidade) se o backbone está conectado
29 TBONE-Eventos Classe 2 (Mínima): verifica se há BN redundantes Classe 3 (eficiência): cada RN verifica se existe algum vizinho com maior capacidade do o que BN Classe 4 (cobertura dos nós de baixa capacidade): cada nó disassociado que encontra um vizinho BN ou um BCN inicia processo de associação
30 TBONE-Eventos Classe 5 ( cobertura dos BCN) : ocorre se um BCN identifica algum vizinho seu como um BN ele associa a este BN vizinho Classe 6 ( cobertura dos BCN) : ocorre se um BCN não escuta nenhuma mensagem de seu BN durante um período pré definido de tempo
31 TBONE-Eventos Classe 7 ( cobertura dos BCN) : ocorre see um BCN desassociado não escuta nenhuma mensagem de um BN por um período pré definido de tempo Classe 8 (adaptabilidade das aplicações): ocorre se o tráfego de alguma estação é alterado
32 TBONE-Ações
33 TBONE-Algoritmos 1) Algoritmo de associação a uma Anet: Critérios de desempenho e topológicos Cada nó escolhe o mais apropriado e envia um join request (ID, vizinhos, aplicações) Passa por um processo de admissão Se não admitido procura outros BNs vizinhos
34 TBONE-Algoritmos 2) Algoritmo de seleção de líder: Ganha quem tiver mais recursos disponíveis Se algum BN enviar alguma mensagem a eleição se encerra
35 TBONE-Algoritmos 3) algoritmo de conversão BN-BCN: Tenta eliminar BNs redundantes Pode ser que uma anet inteira se associe a um outro BN
36 TBONE-Algoritmos 4) Alocação de Alocação de segmentos: Segmentos alocados em função da demanda e dos recursos disponíveis Verifica tanto na sua anet, na bnet, e na anet de destino Sincroniza com vizinhos para reduzir interferências Admite ou não o pedido
37 TBONE-Resultados 3 modelos de mobilidade distintos: Random walk: v max Random movement: v max,a max, θ max Random destination: v max (variável),tempo de pausa(exponencial)
38 TBONE-Resultados Área=LxL (L=500m) R (alcance do rádio de alta capacidade) r (alcance do rádio de baixa capacidade) V max= 4 m/s A max =2m/s 2 θ max = 90 graus #RN=100, R =250, r =120
39 # BNs em função de BCN
40 Área de cobertura x BCN
41 P[Bnet conectada]x BCN
42 taxa de conversão BN-BCN x BCN
43 TX de desconexão RN x BCN
44 Propostas Explorar melhor a mobilidade (modelos de mobilidade em grupo) Usar polling como controle de acesso ao meio(não teria necessidade de sincronismo) Combinar as mensagens de controle do polling com as mensagens de controle do cluster
45 Conclusão A formação dos cluster implica em mais complexidade nas redes Ad Hoc Será que o overhead de controle vale a pena?
46 Referências [1] X. Hong, K. Xu, M.Gerla. Scalable Routing Protocols for Mobile ad Hoc Networks, IEEE Network, Junho 2002, pag. 11 a 21. [2] J. Kurose, K. Ross. Computer Networking: a Top-Down Approach featuring the Internet Addison-Wesley, [3] U.C.Kozat, G.Kondylis, B.Ryu, M. Karina. Virtual Dynamic Backbone for Mobile Ad Hoc Networks [4] S.R.Das, C.E.Perkins, E.M.Royer. Perfomance Comparison of Two On- Demand Routing Protocols Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Março 2000 [5] P.Gupta, P.R.Kumar. The Capacity of Wireless Networks IEEE Trans. On IT, vol IT-46, no2,pag , Março 2000 [6] K. Xu, X. Hong, M. Gerla. An Ad Hoc Network with Mobile Backbone proc. IEEE ICC 2002, Nova York, EUA, abril 2002 [7] I.Rubin, A.Behzad, R.Zhang, H.Luo,E. Caballero. TBONE:A Mobile Backbone Protocol for Ad Hoc Wireless Networks
47 Referências [8] M. Gerla, K.Xu,X. Hong. Exploiting Mobility in Large Scale Ad Hoc Computer networks IEEE 18th Annual Workshop on Computer Communications, Outubro 2003 [9] C. Perkins Ad Hoc Networking, Addison Wesley, 2001 [10] I. Rubin and R. Zhang, "Performance behavior of unmanned vehicle aided mobile backbone based wireless ad hoc network", t in Proceedings of IEEE Vehicular Technology Conference- VTC 2003, Jeju, Korea, Abril 22-25, 2003
Backbones Ad Hoc. Aluno: Eduardo Hargreaves Orientador: Luís Felipe M. de Moraes
Backbones Ad Hoc Aluno: Eduardo Hargreaves Orientador: Luís Felipe M. de Moraes Dezembro de 2003 Resumo O objetivo deste trabalho é apresentar propostas para tornar as redes Ad Hoc escaláveis. As redes
Redes P2P para compartilhamento de arquivos em dispositivos móveis Felipe Freixo Pina 1 1 Departamento de Informática - PUC-Rio fpina@inf.puc-rio.br Abstract. File sharing in wireless mobile P2P networks