Otimização de Rotas de Múltiplos Caminhos em Redes de Dados Nomeados Usando Vetor de Caminhos

Otimizac¸˜ ao de Rotas M´ ultiplos Caminhos em Redes de Dados Nomeadas Usando Vetor de Caminhos Fabio Santos dos Santos1 1Programa de P´ os-Graduac¸˜ ao em Ciˆ encia da Computac¸˜ ao (PGCOMP) Instituto de Computac¸˜ ao – Universidade Federal da Bahia (UFBA) Salvador – BA – Brasil {[email protected] Abstract. Named data networks are an internet paradigm of the future characterized by their content-centricity, as opposed to the current architecture, TCP/IP, which is host-centric. Routing protocols in named data networks provide content reachability information, having an important application in this architecture, as it contributes with information that enables greater assertiveness in targeting the reach and return of data. In this context, the NDVR presents itself as a lightweight, safe tool with a simple and efficient synchronization process. NDVR provides support for multiple paths, but encounters difficulties in some topologies with route quality. This article proposes the use of path vectors in order to mitigate these problems. It shows positive results and presents in future work a scalable solution for the use of path vectors in large topologies. Resumo. As redes de dados nomeados s˜ao um paradigma de internet do futuro caracterizadas pela sua centraliza¸c˜ao em conte´udos em oposi¸c˜ao a arquitetura atual TCP/IP, centrada em host. Os protocolos de roteamento em redes de dados nomeados provem informa¸c˜oes de alcan¸cabilidade de conte´udos, tendo importante aplica¸c˜ao nesta arquitetura, por contribuir com informa¸c˜oes que possibilitam maior assertividade no direcionamento para o alcance e retorno dos dados. Neste contexto, o NDVR, apresenta-se como uma ferramenta leve, segura e com um processo de sincroniza¸c˜ao simples e eficiente. O NDVR provˆe suporte a multiplos caminhos, mas encontra dificuldade em algumas topologias com a qualidade das rotas. Este artigo prop˜oe o uso de vetor de caminhos afim de mitigar estes problemas. Mostra os resultados positivos e apresenta em trabalhos futuros uma solu¸c˜ao escal´avel para o uso de vetores de caminhos em grandes topologias. 1. Introduc¸˜ ao A principal abordagem proposta pela comunidade de internet do futuro, a NDN ou Named-Data Network,´ e uma arquitetura centrada no conte´ udo, seguindo o paradigma ICN - Information Centric Networks que prop˜ oe conduzir o tr´ afego da rede baseado no conte´ udo buscado e n˜ ao como na arquitetura atual, TCP/IP, baseada no host que guarda este conte´ udo [Zhang et al. 2014]. Nas redes IP, os protocolos de roteamento tem a func¸˜ ao fundamental de produzir informac¸ ˜ oes de caminho que conduzam a solicitac¸˜ ao de servic¸o ou conte´ udo, do cliente ao servidor que os oferece, recebendo resposta a demanda. Portanto, a func¸˜ ao do protocolo de roteamento em redes IP ´ e entregar rotas entre este host cliente e o host servidor de forma completa, fim a fim. Por outro lado, na arquitetura NDN, n˜ ao ´ e esse o objetivo exatamente. Nesta arquitetura, existem nativamente v´ arias estrat´ egias de encaminhamento, como flooding, onde os interesses s˜ ao encaminhados por inundac¸˜ ao da rede, bestroute, onde ´ e usada a melhor rota informada pelo protocolo de roteamento, multicast, onde m´ ultiplas rotas s˜ ao usadas, e outras t´ ecnicas adaptativas e inteligentes de encaminhar baseadas em RTT (Round Trip Time) tal qual a ASF (Adaptive Smoothed RTT) que leva em conta o Round Trip Time para assegurar a melhor forma de encaminhamento. Ademais, a NDN disponibiliza os conte´ udos em caching atrav´ es da figura da CS (Content Store) em cada n´ o, ou em n´ os estrat´ egicos, facilitando o retorno do conte´ udo, resultando em economia de largura de banda, diminuic¸˜ ao do atraso, e prevenc¸˜ ao de erros. Desta forma, cabe aos protocolos de roteamento a tarefa de auxiliar o plano de encaminhamento, com sugest˜ oes de direc¸ ˜ oes para alcance de prefixos de forma otimizada, inclusive prevendo m´ ultiplos caminhos [Hoque et al. 2013]. Muitas soluc¸ ˜ oes para roteamento em redes NDN tem surgido nos ´ ultimos anos. Protocolos que adotam diversas estrat´ egias de descoberta e entrega de rotas, dos quais alguns possuem a funcionalidade de m´ ultiplos caminhos [Karim et al. 2022]. Exemplos de protocolos que suportam m´ ultiplos caminhos em NDN s˜ ao o NLSR e o MUCA. Ambos apresentam abordagem baseada em estado de enlace [Wang et al. 2018], e no caso do MUCA, estende-se de forma h´ ıbrida, a aplicac¸˜ ao de estado de enlace, vetor de distˆ ancia, e roteamento baseado em caching [Ghasemi et al. 2018]. Neste contexto, o NDVR (do inglˆ es, Named-data Distance Vector Routing), ´ e um protocolo de roteamento leve e eficiente, que atende as demandas acima citadas, por oferecer de maneira assertiva indicac¸ ˜ oes de caminhos para prefixos alcanc¸´ aveis na rede. A sua implementac¸˜ ao inicial j´ a conhecida n˜ ao contava com suporte a Multipath. Este artigo visa apresentar uma nova vers˜ ao que possui esta feature, bem como, descrever os esforc¸os em busca de mais robustez e eficiˆ encia na descoberta e entrega de rotas de qualidade, englobando m´ ultiplos caminhos. Organizamos este documento da seguinte forma: a Sec¸˜ ao 2 apresenta os trabalhos relacionados que abordam multipath em NDN, destacando as suas potencialidades e fragilidades; a Sec¸˜ ao 3 descreve o design do NDVR exibindo um protocolo leve, de r´ apida convergˆ encia e sincronizac¸˜ ao. Sua vers˜ ao mais nova possui a capacidade de trabalhar com m´ ultiplos caminhos sem perder as caracter´ ısticas de leveza. Entretanto, apresenta dificuldade em lidar com loops em algumas topologias. Na sec¸˜ ao 4 n´ os trazemos uma abordagem de vetor de caminhos para o NDVR visando mitigar essas falhas e possibilitando o controle sobre os caminhos dos prefixos; A Sec¸˜ ao 5 apresenta uma avaliac¸˜ ao experimental preliminar do NDVR com PathVector contrastando-o com o sua vers˜ ao atual e avaliando as vantagens do uso desta abordagem; A Sec¸˜ ao 6 apresenta a conclus˜ ao do trabalho e aponta como trabalho futuro a investigac¸˜ ao do uso de hash nos nomes de prefixos e de bloom filter invers´ ıvel como array em lugar de lista melhorando a escalabilidade em grandes topologias. 2. Roteamento com m´ ultiplos caminhos em NDN Roteamento em m´ ultiplos caminhos ´ e um assunto bem conhecido nas pesquisas em redes de computadores. Muitos esforc¸os tˆ em sido aplicados ao longo dos anos a fim de prover mecanismos inteligentes para este fim. De fato, esse tema mostra-se extremamente desafiador em diferentes cen´ arios. [Vutukury and Garcia-Luna-Aceves 1999] propˆ os um algoritmo chamado MPATH baseado em vetor de distˆ ancia que provˆ e m´ ultiplas rotas de diferentes custos, mantendo-se livre de loops mesmo durante mudanc¸as na rede. Mais tarde, com base no algoritmo anterior, um protocolo de m´ ultiplos caminhos, o MDVA, foi proposto [Vutukury and Garcia-Luna-Aceves 2001]. A soluc¸˜ ao MMDV, mostra um protocolo do tipo proativo que calcula rotas para todos os destinos e atualiza periodicamente usando t´ ecnica de MPR (MultiPath Relay) [Mtibaa and Kamoun 2006]. No OLSR vemos o uso da t´ ecnica de MPR para reduc¸˜ ao de overhead pela eleic¸˜ ao de um grupo de roteadores dentre a totalidade da rede para gerar informac¸ ˜ oes de topologia [Yi et al. 2009]. Por outro lado, quest˜ oes relacionadas a m´ ultiplos caminhos no paradigma NDN s˜ ao analisadas em pesquisas mais recentes, mas n˜ ao menos desafiadoras. Um protocolo de roteamento de m´ ultiplos caminhos amplamente usado pela comunidade de redes de dados nomeados em ambientes de experimentac¸˜ ao e testbed ´ e o NLSR (Named-data Link State Routing). Ele ´ e um protocolo de estado de enlace que possui similaridades com outros protocolos desta fam´ ılia usados em IP, mas se utiliza do esquema de nomeac¸˜ ao hier´ arquico, para facilitar a aplicac¸˜ ao do modelo de confianc¸a e divulgac¸˜ ao de informac¸ ˜ oes de roteamento, e do CronoSync, para sincronizac¸˜ ao das aplicac¸ ˜ oes, ambos nativos das redes de dados nomeados. O NLSR traz em seu designer roteamento m´ ultiplos caminhos atrav´ es de um sistema de aprendizado de rotas que ´ e uma extens˜ ao do algoritmo Dijkstra. O n´ o remove temporariamente todos os adjacentes, exceto um, e aplica o dijkstra para calcular o custo at´ e todos os prefixos. Depois, repete o procedimento para cada adjacente. Uma vez sondado todas as rotas poss´ ıveis, ranqueia as melhores. O operador pode definir quantos pr´ oximos saltos ele deseja para evitar que a FIB seja sobrecarregada em seu tamanho dependendo do n´ umero de elementos. Esse processo apresenta um custo computacional elevado, da ´ ordem de Ω(n2) uma vez que o c´ alculo ´ e aplicado em cada n´ o em relac¸˜ ao aos seus adjacentes e para si mesmo [Lehman et al. 2016]. O MUCA (MUltipath forwarding and in-network CAching) possui caracter´ ısticas tanto de estado de enlace como de vetor de distˆ ancia. Ao tempo em que mapeia toda a topologia da rede usando o algoritmo de Dijkstra, ele tamb´ em se vale de atributos do algoritmo Distributed Bellman-Ford para o aprendizado de m´ ultiplas rotas. Em seu c´ alculo de poss´ ıveis caminhos, considera trˆ es principais informac¸ ˜ oes: 1Rotas chamadas de melhor custo aprendidas com o estado de enlace, chamadas de best path (BP), 2Rotas ditas de quase melhor custo geradas pelo vetor de distˆ ancia, ditas Semi Best Path (SBP) e 3as mais prov´ aveis melhores rotas, Most Probable Routes (MPP) obtidas dos CS (Caching System) dos roteadores ao longo da rede. Devido o uso destas v´ arias origens de rotas, ele pode ter m´ ultiplos caminhos para um ´ unico produtor e, m´ ultiplos caminhos para m´ ultiplos produtores de um mesmo prefixo. A estrat´ egia de aprendizado baseado em caching, pode, em alguns casos, diminuir custos computacionais. Todavia, no geral, sua complexidade assemelha-se ao NLSR devido a estrat´ egia de descoberta de rotas e sincronizac¸˜ ao de dados [Ghasemi et al. 2018]. Roteamento por m´ ultiplos caminhos em named-data networks continua sendo objeto de ´ arduos esforc¸os de pesquisa. Diante disso, a nova vers˜ ao do protocolo NDVR com suporte a m´ ultiplas rotas, coloca-se nesse cen´ ario como uma promissora ferramenta uma vez que este protocolo ´ e leve, seguro e possui seu pr´ oprio m´ etodo de sincronizac¸˜ ao como veremos na sec¸˜ ao a seguir. 3. O NDVR O NDVR (Named-data Distance Vector)´ E um protocolo de designer leve, mult´ ıplos caminhos, baseado em vetor de distˆ ancia e com uma estrat´ egia enxuta de sincronizac¸˜ ao, tornando-se eficiente em prover direc¸˜ oes assertivas de prefixos em redes nomeadas. Para isso usa dois tipos de mensagens: EHLO e DVINFO. As mensagens ehlo (Extended Hello) s˜ ao pacotes de interesse usados para divulgar a existˆ encia de um n´ o a seus vizinhos, bem como, solicitar mensagens de atualizac¸ ˜ oes. O DVINFO (Distance Vector Information), ´ e um pacote de dados usado para o envio de atualizac¸ ˜ oes de prefixos alcanc¸´ aveis. Quando um n´ o´ e inicializado, ele envia aos seus vizinhos no escopo local, ou seja, apenas aos diretamente conectados, uma mensagem ehlo informando a sua existˆ encia. Isso ´ e poss´ ıvel, pois a FIB (Forwarding Information Base) dos n´ os rodando o NDVR possui uma entrada de prefixo (/localhop/ndvr/ehlo) pr´ e-configurada que permite que este ehlo seja encaminhado direto para a aplicac¸˜ ao NDVR do n´ o receptor, tornando a este conhecido na rede [Brito 2021]. Uma vez aprendido sobre a existˆ encia da vizinhanc¸a, o n´ o dever´ a divulgar a sua tabela de vetor de distˆ ancia. Devido ` a caracter´ ıstica da arquitetura das redes NDN de ser receiver-driven, o DvInfo deve ser solicitado antes de ser enviado [Brito and Sampaio 2021]. Para este fim, as mensagens ehlo tamb´ em s˜ ao usadas. Quando um n´ o tem informac¸ ˜ oes de atualizac¸˜ ao de rotas, ele envia um ehlo, sinalizando que quer enviar a sua tabela. O n´ o vizinho fica sabendo desta atualizac¸˜ ao dispon´ ıvel no adjacente enviando em seguida um pacote de interesse pelos dados oferecidos. Este processo acontece apenas sob-demanda, ou seja, n˜ ao h´ a atualizac¸ ˜ oes peri´ odicas. O DvInfo ´ e enviado apenas se alguma mudanc¸a operacional na rede for detectada. Toda troca de mensagens acontece de forma segura, pois as mensagens do NDVR s˜ ao assinadas e as suas validac¸ ˜ oes seguem um modelo de confianc¸a baseado nas pol´ ıticas de seguranc¸a definidas nos arquivos de validac¸˜ ao contidos no protocolo [Brito and Sampaio 2021]. Ap´ os a disseminac¸˜ ao dos DvInfo atrav´ es da rede, os n´ os aprendem as direc¸ ˜ oes dos prefixos divulgados. Em outras palavras, as faces conectadas aos caminhos para estes prefixos. O roteamento de m´ ultiplos caminhos oferece ao plano de dados rotas que podem ser usadas como principais e alternativas, ou ainda, para encaminhamento simultˆ aneo de dados, conhecido como balanceamento de carga. Para que isso seja poss´ ıvel, o NDVR foi acrescido, em relac¸˜ ao ` a vers˜ ao inicial novos campos. O campo ORIGINATOR, identifica o roteador que est´ a divulgando determinado prefixo, permitindo assim que mais de um roteador o divulgue simultaneamente. O BEST COST,´ e o melhor custo aprendido por cada face, e o SECOND BEST COST,´ e o segundo melhor caminho aprendido por esta mesma face. Estes campos tornam poss´ ıvel o aprendizado de v´ arias rotas. Outros campos, como n´ umero de sequˆ encia e LEARNED FROM previnem a instalac¸˜ ao de prefixos inv´ alidos atrav´ es de checagens de sanidade de cada entrada contida em um dvinfo recebido. O algoritmo de processamento da entrada DVINFO ´ e mostrado no algoritmo 1. Na figura 1 temos um exemplo do mecanismo de envio e recepc¸˜ ao dos pacotes. Cada n´ o envia sua tabela de prefixos aprendidos aos seus adjacentes contendo o melhor custo (best cost), o segundo melhor custo (second cost), al´ em dos campos de controle, culminando em uma base de informac¸ ˜ oes de roteamento com v´ arios caminhos que ´ e entregue a FIB do n´ o, observada na figura 2. Nela a tabela de encaminhamento com mais de uma rota para cada prefixo. Exemplo do prefixo /ndn/c-site/aprendido pelas duas faces poss´ ıveis, a saber, 256 com custo 2, e pela face 257 com custo 4. Algoritmo 1: Roteador iprocessa DVINFO recebido do roteador j 1houveMudanca =Falso; 2foreach prefixo de nome p ∈DvInfoj do 3custoi ←CalculaCusto(j, p.cost); 4prevp ←ConsultaPrefixoExistente(p); 5if prevp =ϕthen 6InserePrefixo (p, nextHop =j, cust =custoi, seq =p.seq, secCust =∝, originator =j, learnedFrom =j); 7houveMudanca =True 8else 9if newFace ,face Wp.seq >prevp.seq W(p.seq =prevp.seq Vcustoi <prevp.cost) then 10 AtualizaPrefixo (p, nestHop =j, cost =custoi, seq =p.seq, secCost =prevp.cost, originator =j, learnedFrom =j); 11 houveMudanca =True; 12 end 13 end 14 end 15 if houveMudanca then 16 AtualizaVersaoDigest(); 17 EnviaEHLO(); 18 end Figura 1. Envio de Ehlo e recebimento de DvInfo NDVR Figura 2. Exemplo da fib list n ´ o a 3.1. Desafios de Mult´ ıplos caminhos no Protocolo NDVR O NDVR aprende a melhor rota alcanc¸´ avel por cada face em um n´ o. Ou seja, ´ e poss´ ıvel aprender tantos caminhos quantas forem as faces f´ ısicas conectadas a rede e que levem ao n´ o que cont´ em o conte´ udo buscado. Por este motivo algumas topologias favorecem o aparecimento de problemas relacionados a qualidade das rotas, podendo impactar na efic´ acia das mesmas. Al´ em dos problemas cl´ assicos como contagem ao infinito, e loops de roteamento, mitigados pelas regras de checagem de sanidade do NDVR e pelo uso da t´ ecnica de n´ umero de sequˆ encia, outras quest˜ oes surgem quando se trata de roteamento em m´ ultiplos caminhos. Rotas em que os n´ os e/ou links n˜ ao s˜ ao disjuntos, fazendo com que mais de uma rota passe por um ponto comum, gerando fragilidade e/ou sobrecarga ` aquele n´ o ou link conforme vemos na figura 3. Figura 3. Representac¸ ˜ ao de N´ o e Link n˜ ao Disjunto Outra quest˜ ao ´ e a inserc¸˜ ao de rotas que colocam o pr´ oprio n´ o de origem da requisic¸˜ ao, ou consumidor, no caminho para o n´ o onde se encontra o conte´ udo a ser consumido, o n´ o produtor. Olhando a figura 4, tomando por base o n´ o C, infere-se que trˆ es prefixos de alcance ao n´ o D ser˜ ao aprendidos. Um diretamente conectado, aprendido do pr´ oprio D, outro de pr´ oximo salto B e ainda outro via F. O n´ o B possui em sua tabela uma rota para D de custo 2 e uma de custo 5. A de custo 2 n˜ ao ´ e aprendida por C, visto que, o pr´ oximo salto ´ e ele mesmo. Isso ´ e rejeitado pela checagem de sanidade citada na sec¸˜ ao anterior. Todavia, a segunda rota de custo 5 ´ e aprendida. An´ alogo a este pensamento, o n´ o F possui uma rota para D de custo 2 que o roteador C, n˜ ao aprende, pois C ´ e o pr´ oximo salto. Entretanto, o roteador C aprende de roteador F uma outra rota de custo 5. Ap´ os incrementar os custos destas rotas aprendidas dos n´ os B e F, C passa a contar com uma rota de custo 1 direto para D, uma rota de custo 6, que tem como pr´ oximo salto o n´ o F, e outra rota com custo 6 via roteador B. Contudo, as duas entradas de custo 6 passam pelo pr´ oprio n´ o C, que as adiciona erroneamente a sua tabela conforme notamos na figura 5. Note que o n´ o C poderia ter aprendido dos n´ os B e F outras rotas que, embora tenham custos mais elevados, s˜ ao rotas v´ alidas e eficazes. Estas s˜ ao exemplificadas pelas da figura 6 que tem o caminho via F, e como pr´ oximo salto o n´ o G. Neste caso, C instalaria a rota diretamente conectada de custo 1, e mais as rotas com custo 8 e 11, respectivamente tendo F e B, como pr´ oximos saltos. 4. Otimizac¸˜ ao de caminhos no NDVR usando Path Vector Na busca de uma soluc¸˜ ao para as quest˜ oes abordadas na sec¸˜ ao anterior, adotamos a seguinte estrat´ egia: uso de um vetor de caminhos para otimizar as rotas aprendidas. A proposta ´ e adicionar a cada entrada do DvInfo, a informac¸˜ ao de quem s˜ ao os n´ os ao longo do caminho, possibilitando verificar se o pr´ oprio n´ o consumidor encontra-se na rota para o conte´ udo, o que tamb´ em permite identificar pontos em comum de rotas n˜ ao disjuntas, permitindo o desvio da mesma pelo operador. Foram necess´ arias algumas mudanc¸as na estrutura do NDVR. Os campos BestRoute eSecBestRoute foram descontinuados dando Figura 4. n´ o C instala rotas para n ´ o D que passam pelo pr´ oprio C - ´ Area clareada Figura 5. recorte da fib list do n´ o C destacando caminhos inv´ alidos para o prefixo d-site aprendidos pelo n´ o com custo 6 lugar a apenas um campo geral de custo COST. Em relac¸˜ ao ao aprendizado de rotas, outra mudanc¸a. Como o NDVR padr˜ ao propaga seus melhores caminhos por face, ou seja, ele apenas propaga a melhor rota para cada sa´ ıda v´ alida baseado no menor custo, que como vimos na sess˜ ao anterior, nem sempre s˜ ao as mais eficientes ou mesmo, v´ alidas, propomos enviar todas as rotas descobertas. Assim, ´ e poss´ ıvel receber v´ arias rotas pela mesma face e a partir da an´ alise do vetor, definir se a mesma vai ser instalada na RIB ou descartada. Portanto, o aprendizado e divulgac¸˜ ao de prefixos deixa de ser apenas baseado no custo da rota, mas leva em considerac¸˜ ao tamb´ em o Vetor de Caminhos. Ali´ as, outra mudanc¸a importante, ´ e o campo NextHop que ´ e o vetor de caminhos. Esse campo ´ e um vetor de vetores onde ´ e guardado recursivamente os nexhops e seus nexhops. Quando o NDVR envia um DvInfo ele coloca o seu pr´ oprio RouterId e os seus NextHops no vetor. O mesmo acontece durante todo o percurso que o prefixo divulg´ avel passa. Quando o DvInfo contendo um prefixo cujo nome do roteador local ´ e um nexthop contido na lista, este ´ e descartado evitando a rota com loop ou inv´ alida. O formato do DvInfo ´ e visto na figura7. 5. Avaliac¸˜ ao Experimental Esta ´ e uma avaliac¸˜ ao preliminar como prova de conceito feita em ambiente de emulac¸˜ ao de redes ndn, o MiniNDN. A topologia usada ´ e a exibida na figura 4. Para avaliar, verificamos as sa´ ıdas de FIB usando cada uma das vers˜ oes do NDVR. Procurando pelas falhas j´ a detalhadas acima. Tamb´ em comparamos as taxas de perda de pacotes elatˆ encia das duas vers˜ oes, b´ em como o Overhead. Comec¸amos com a convergˆ encia. Ao convergir o protocolo verificamos as rotas instaladas na FIB usando cada vers˜ ao e as comparamos. Figura 6. Vislumbre de fib list do n´ o C com caminhos v´ alidos para o n´ o D de custo 1, 8 e 11 Figura 7. Formato da mensagem DvInfo Figura 8. Topologia de validac¸ ˜ ao da soluc¸ ˜ ao Em seguida, usamos um experimento onde os n´ os enviam pacotes de interesse e recebem conte´ udo na forma de pacotes de dados. Links s˜ ao desligados de forma estrat´ egica a fim de gerarmos instabilidade a rede. Em seguida medimos a taxa de perda de pacote e registramos a latˆ encia. Por ´ ultimo efetuamos os comparativos de OverHead das duas vers˜ oes. 5.1. Planejamento de Experimentos O ambiente de experimentac¸˜ ao usa o emulador MiniNDN na vers˜ ao 0.5.0 e o NDVR nas vers˜ oes original com multipath e o NDVR na vers˜ ao com path vector. Um PC com processador Intel i5, Clock de 3.4 GHZ, 8 GB de mem´ oria RAM, com sistema operacional Linux LTE 20.04. Os pacotes monitorados em quest˜ ao est˜ ao sendo produzidos e consumidos pelas ferramentas ndnpingserver endnping nativas do pr´ oprio MiniNDN. No primeiro experimento, analisamos a convergˆ encia. Aguardamos o protocolo convergir completamente. Usamos esse script para verificar se as rotas instaladas na FIB s˜ ao visualmente rotas v´ alidas. Ap´ os a convergˆ encia, analisamos as sa´ ıdas de n´ os espec´ ıficos onde as rotas ineficazes sabidamente aparecem, e contrastamos com a sa´ ıda gerada pela convergˆ encia da vers˜ ao usando a soluc¸˜ ao. Constatamos a correc¸˜ ao das rotas instaladas. O segundo experimento, usa um cen´ ario de desestabilidade tempor´ aria. Tem durac¸˜ ao de 320 segundos. Ap´ os a convergˆ encia que dura 60 segundos, provocamos a queda de links importantes obrigando o n´ os a buscarem nova convergˆ encia. Os hosts C e D trocam pacotes de interesses e dados entre s´ ı. O n´ o E envia interesses para o n´ o F e recebe dados do mesmo. Analisamos a perda de pacotes, latˆ encia e impacto no overhead. 5.2. Primeiro Experimento - Convergˆ encia - Rotas Otimizadas Neste experimento apenas os pacotes b´ asicos de descoberta e divulgac¸˜ ao de prefixos alcanc¸´ aveis s˜ ao trocados. ´ E puramente a convergˆ encia do protocolo. Exibimos a FIB de cada vers˜ ao escolhendo estrategicamente um n´ o consumidor e um poss´ ıvel produtor onde evidencia o problema de loop em que o consumidor encontra-se no caminho para o produtor detentor do prefixo alcanc¸´ avel. Note que na sa´ ıda da figura 9(a), se tomarmos por base o n´ o C como consumidor e o n´ o D como produtor, temos que o NDVR original instala trˆ es rotas. Uma diretamente conectada, custo 1 face 257 e mais duas rotas, a saber, face 256 custo 6 via n´ o F passando por E, A, B e voltando ao C antes de seguir para o destino final, n´ o D, e uma outra rota pela face 258 com custo 6 via B passando por A, E, F voltando ao C e seguindo para o produtor D. Observando a figura 11, conclu´ ımos que no fim das contas, as trˆ es rotas se resumem a apenas uma, a rota C-D, uma vez que, se esta estiver down as outras duas tamb´ em n˜ ao ter˜ ao continuidade. Por outro lado, se olharmos para a figura 9 ` a direita, veremos que as rotas instaladas al´ em da diretamente conectada tem custo 8 e 11. Recorrendo figura 11 novamente, percebemos que estas s˜ ao justamente, via F, G, H, I, J, K, L seguindo para o destino D, e B, A, E, F, G, H, I, J, K, L seguindo para D, o produtor. Estas rotas n˜ ao passam pelo n´ o C o que as torna eficazes. Poder´ ıamos ainda, impedir que as duas rotas passando por F (n˜ ao disjunc¸˜ ao) fossem instaladas, optando pela de mais baixo custo, ou seja, a de custo 8 via F. Observando as mesmas sa´ ıdas da figura 9 e tendo como base a topologia da figura 11, podemos notar que a rota para o n´ o B do NDVR original pela face 257 com custo 10 ´ e ineficaz pois passa por dentro do pr´ oprio n´ o C. J´ a no NDVR com path vector vemos uma terceira rota via face 257 com custo 11. Rota esta totalmente funcional. Observe na figura 10(a) tomando como base o n´ o g temos situac¸˜ ao an´ aloga a descrita acima. Essa abordagem resolve quest˜ oes de loop e de n˜ ao disjunc¸˜ ao podendo auxiliar no uso do NDVR para balanceamento de carga por exemplo. N˜ ao ´ e dif´ ıcil concluir que nas demandas de dados do n´ o C para o n´ o D, temos que no NDVR original o troughput ´ e igual ao link C-D uma vez que os outros dois caminhos se encontram neste n´ o n˜ ao disjunto. J´ a no NDVR com path vector podemos contar com uma vaz˜ ao em dobro visto que os links C-D e F-G s˜ ao disjuntos e levam ao n´ o D. (a) nfdc fib n´ o C NDVR (b) nfdc fib n´ o C Pathvector Figura 9. sa´ ıdas nfdc fib n´ o C NDVR ` a esquerda e PathVector ` a direita (a) nfdc fib n´ o F NDVR (b) nfdc fib n´ o F Pathvector Figura 10. sa´ ıdas nfdc fib n´ o F NDVR ` a esquerda e PathVector ` a direita