Uma abordagem sobre a otimização do cache em núcleo para a arquitetura de redes NDN com uso do algoritmo VERTEX COVER

Uma abordagem sobre a otimizac¸˜ ao do cache em n´ ucleo para a arquitetura de redes NDN com uso do algoritmo VERTEX COVER 1st Toni Alex Reis Borges Dpto de Ciencia da Computac¸ ˜ ao Universidade Federal da Bahia (UFBA) Salvador, Brasil toni.bor[email protected] 2nd Fabio Santos dos Santos Dpto de Ciencia da Computac¸ ˜ ao Universidade Federal da Bahia (UFBA) Salvador, Brasil [email protected] 3rd Adauto Cavalcante Menezes Dpto de Ciencia da Computac¸ ˜ ao Universidade Federal da Bahia (UFBA) Aracaju, Brasil [email protected] Resumo—A necessidade dos roteadores da arquitetura NDN estabelecer uma comunicac¸˜ ao n˜ ao mais voltada para o destino e sim para a informac¸ ˜ ao desencadeou, ao processamento j´ a existente, uma carga adicional sobre a busca e armazenamento dos dados em uma cache. Com o objetivo de minimizar essa carga adicional, o estudo tem como proposta, a substituic¸ ˜ ao da necessidade da cache para apenas um n´ ucleo espec´ ıfico de roteadores, utilizando o algoritmo VERTEX COVER como base para estabelecer essa cobertura entre as conex˜ oes existentes, que ser´ a definida por qualquer um dos roteadores da rede, reduzindo o tempo de processamento e a necessidade de armazenamento global. Index Terms—Vertex Cover, Named Data Networking (NDN), Cache , Grafo I. INTRODUC¸˜ AO A´ area de rede de computadores tem se apresentado com um volume de dados exponencial, o modelo atual, baseado na fam´ ılia de protocolos do TCP/IP, n˜ ao se consolida mais como um modelo capaz de suprir as diversas demandas decorrentes do encaminhamento de pacotes baseado no protocolo IP. Uma recente publicac¸˜ ao [1] sobre o compartilhamento de tr´ afego de dados na internet, demonstrou que o objetivo de acesso na rede n˜ ao se consolida mais por relac¸˜ ao origem/destino, passando a ser realizada no par consumidor/dados, se considerado um tr´ afego total de downstream de 58% de todo o volume de dados na internet. Diversos estudos [2] est˜ ao sendo realizados com o objetivo de trazer, para a ´ area de rede de computadores, uma abordagem de redes centradas na informac¸˜ ao, onde v´ arias arquiteturas foram desenvolvidas com esse objetivo, entre elas, a arquitetura Named Data Networking (NDN), que tem se consolidado como um potencial substituto do modelo atual e que, atualmente, tem se destacado nas discuss˜ oes sobre esse processo de evoluc¸˜ ao. A partir dessa tem´ atica, v´ arias possibilidades de pesquisa est˜ ao em aberto, dentre elas, protocolos de roteamento de pacotes baseados em “nome” e o armazenamento dos dados nos roteadores da rede, denominado cache. Esse processo se faz presente porque o objetivo agora n˜ ao ´ e mais atingir o destino e sim a informac¸˜ ao, fazendo uso dessas caches nos dispositivos respons´ aveis pelo encaminhamento do pacote, descentralizando e desestimulando a necessidade de atingir o produtor da informac¸˜ ao na rede. Na arquitetura NDN, todo o encaminhamento utiliza caracter´ ısticas de caminhos m´ ultiplos e verificac¸˜ ao da cache, isso em cada dispositivo do tr´ afego passante, devolvendo a requisic¸˜ ao, caso exista o dado, ou, caso contr´ ario, continua o encaminhamento at´ e que essa resposta seja afirmativa sobre os dados solicitados pelo consumidor na rede, gerando assim, uma sobrecarga de processamento proveniente das verificac¸ ˜ oes, mesmo considerando a inexistˆ encia de loops na rede, decorrente das caracter´ ısticas do pr´ oprio padr˜ ao utilizado na arquitetura NDN. Esse efeito negativo na arquitetura, decorrente da sobrecarga de verificac¸˜ ao em todos os dispositivos na rede, que se constituem no aumento do processamento de CPU por conta da verificac¸˜ ao da cache, conforme j´ a mencionado acima, desencadeou a necessidade de produzir algoritmos que minimizem essa sobrecarga nos equipamentos, com o objetivo de reduzir o tempo de convergˆ encia entre os roteadores, mas sem comprometer o tempo de resposta sobre as requisic¸˜ oes realizadas pelos consumidores. Pensando nisso e, fazendo uso dos conceitos existentes na ´ area de grafos, foi poss´ ıvel estabelecer um cen´ ario de verificac¸˜ ao reduzida da cache nesses roteadores, que podem ser identificados como n´ os ou v´ ertices da rede e as suas conex˜ oes, que podem ser identificadas como arestas ou relac¸˜ oes, considerando a busca da cache apenas em um n´ ucleo espec´ ıfico, atrav´ es da apropriac¸˜ ao dos conceitos existentes no problema da cobertura de v´ ertices (VERTEX COVER). Apesar do VERTEX COVER se mostrar como uma soluc¸˜ ao vi´ avel e otimista, faz-se necess´ ario estabelecer uma condic¸˜ ao de implementac¸˜ ao que garanta um tempo de execuc¸˜ ao ´ otimo para o estudo, nesse sentido, o desenvolvimento desse trabalho foi dividido da seguinte forma: Na sec¸˜ ao introdut´ oria, foi realizada uma abordagem sobre a descric¸˜ ao do problema e a justificativa da escolha do tema, destacando os elementos presentes no estudo realizado, em seguida, na sec¸˜ ao II, foi realizada uma abordagem conceitual sobre o VERTEX COVER, destacando a possibilidade de execuc¸˜ ao do problema atrav´ es de uma reduc¸˜ ao polinomial que caracteriza um problema NPCompleto. Na sec¸˜ ao III, foi realizado um levantamento sobre os trabalhos correlatos que atuam em processos de otimizac¸˜ ao da cache em redes NDN. Na sec¸˜ ao IV, ´ e apresentada a metodologia proposta, destacando os elementos que fazem parte de todo o processo de construc¸˜ ao do ambiente. Na sec¸˜ ao V, o experimento com o processo de validac¸˜ ao da soluc¸˜ ao, utilizando o emulador MiniNDN. Na sec¸˜ ao VI, um levantamento sobre os avanc¸os necess´ arios para o estudo identificados como ”trabalhos futuros”, que estar˜ ao presentes nas pesquisas seguintes e, por fim, na sec¸˜ ao VII, ser´ a apresentada as considerac¸˜ oes finais sobre o estudo. II. O PROBLEMA DO VERTEX COVER Segundo [3], problemas sobre grafos est˜ ao sempre presentes em ciˆ encia da computac¸˜ ao, em especial, as redes de computadores apresentam topologias que podem ser representadas por grafos de forma muito semelhantes ao modelo gr´ afico gerado a partir das relac¸˜ oes existentes entre os roteadores. Diversos algoritmos s˜ ao utilizados na resoluc¸˜ ao de problemas em diversas ´ areas e, o problema do VERTEX COVER, traz uma contribuic¸˜ ao para minimizar a quest˜ ao do armazenamento da cache na arquitetura NDN. Considerando a necessidade de reduc¸˜ ao, a cobertura, definida por “conjunto de v´ ertices que contenha pelo menos uma das pontas de cada aresta” [4], representa uma soluc¸˜ ao mas que, para a sua aplicabilidade, demanda a construc¸˜ ao de um modelo poss´ ıvel de ser representado computacionalmente e qual o seu tempo de execuc¸˜ ao, se considerado a necessidade de utilizar esse modelo em recursos computacionais limitados dos roteadores. Decis˜ ao: Dado um grafo G e um inteiro k, existe um subconjunto S ⊆V(G) tal que, para toda aresta uv ∈E(G), u ∈S ou v ∈S e|S| ≤ k? O grafo G, fig.1, nos remete, de forma intuitiva, a uma instˆ ancia “sim” para um k=6 ou {G, 6}, considerando o subconjunto b, c, e, f , g, i de G, assim, obtˆ em-se um certificado positivo em tempo polinomial. Figura 1. Grafo G. No entanto, ´ e necess´ ario estabelecer uma comprovac¸˜ ao do VERTEX COVER para uma classe de problemas NPCompleto, neste sentido, para a construc¸˜ ao da afirmac¸˜ ao, se faz necess´ ario a demonstrac¸˜ ao do problema em duas fases: Fase 1: O VERTEX COVER est´ a em NP. A soluc¸˜ ao, j´ a apresentada sobre o grafo G, fig.1, de que, dados {G, k}e um subconjunto S qualquer de v´ ertices, ´ e poss´ ıvel achar um valor k, de uma sa´ ıda v´ alida para a instˆ ancia do problema e, portanto, um certificado positivo, traz o valor com k=6. Como a simples verificac¸˜ ao do certificado positivo ´ e feito em tempo polinomial, ent˜ ao, VERTEX COVER est´ a em NP. Fase 2: Apresentar uma reduc¸˜ ao polinomial de um problema, comprovadamente, NP-Completo para o VERTEX COVER. O problema CLIQUE ´ e NP-Completo. Essa afirmac¸˜ ao nos permite utilizar essa soluc¸˜ ao – CLIQUE – como parˆ ametro para a demonstrac¸˜ ao, reduzindo polinomialmente o CLIQUE para VERTEX COVER: Nos dois problemas ´ e poss´ ıvel identificar que, para uma determinada entrada k no VERTEX COVER, n˜ ao temos, necessariamente, uma CLIQUE. Isso nos imp˜ oe a necessidade de um algoritmo eficiente, de forma a conseguir uma CLIQUE para todas as entradas k que geram um VERTEX COVER. Uma soluc¸˜ ao ´ e olhar para o complemento do Grafo G, que chamaremos de ¯ G, assim, por definic¸˜ ao, para todo par de v´ ertices que n˜ ao possui aresta em G, teremos arestas em ¯ G e, por outro lado, toda vez que um v´ ertice em G tiver arestas, significa que este mesmo v´ ertice em ¯ G, n˜ ao contar´ a com arestas. De forma a exemplificar a construc¸˜ ao acima, ainda tomando o Grafo G, fig.1, como base para demonstrac¸˜ ao, ´ e poss´ ıvel identificar uma CLIQUE {G, 3}, assim, seria poss´ ıvel identificar em G, tomando os v´ ertices {c, e, f}, o que, pela definic¸˜ ao de complemento, nos diz que em ¯ G n˜ ao existir´ a arestas entre os v´ ertices {c, e, f}, al´ em disso, todas as arestas de ¯ G est˜ ao fora deste conjunto, com arestas em todos os outros v´ ertices, logo, para toda CLIQUE em G, temos um VERTEX COVER em ¯ G , sendo verdade a afirmac¸˜ ao inversa. Formalizac¸˜ ao: Supondo que G cont´ em uma CLIQUE S de tamanho pelo menos k, ent˜ ao, para todo par u,v ∈S teremos uv ∈E(G), o que implica que para todo par de v´ ertices u,v ∈ S temos uv ∈E(G) significando que uv /∈a E( ¯ G). Tamb´ em, para todo par xy ∈E( ¯ G) ´ e verdade a afirmac¸˜ ao de que x /∈ S ou y /∈S, logo, V(G) \S´ e um VERTEX COVER em ¯ G. Como |S| ≥ k, temos |V(G) \S|=|V(G)|-|S|≤|V(G)|- k = t. Por outro lado, supondo que ¯ G´ e um VERTEX COVER S de tamanho no m´ aximo t, teremos que para todo par de arestas uv ∈E( ¯ G), temos u ∈S ou v ∈S, o que ´ e o mesmo que dizer que para todo par de v´ ertices x,y tais que x /∈Sey/∈a S, implica xy ∈E(G). Portanto, temos: Se V(G) \S´ e uma CLIQUE em G, e como S≤t = |V(G)|- k, pode-se concluir que |V(G) \S|=|V(G)| -|S|≥|V(G)|- (|V(G)|- k ) = k, portanto, VERTEX COVER ´ e NP-Completo. III. TRABALHOS CORRELATOS A. On Performance of Cache Policies in Named Data Networking Conforme destacado no estudo [7], a cache tem desempenhado um papel fundamental na arquitetura NDN, a necessidade de otimizac¸˜ ao da cache proporciona um avanc¸o na forma como essa relac¸˜ ao entre consumidor e dado se estabelece e, considerando essa relac¸˜ ao constante, tem a sua expectativa direcionada para a popularidade dos conte´ udos, tendo como estrat´ egia, uma pol´ ıtica de conte´ udo atrelada a substituic¸˜ ao desses dados, uma vez que, o fluxo de informac¸˜ oes que transitam nesse ambiente ´ e um item relevante a considerar. ´ E necess´ ario considerar que existe, dentro do modelo de utilizac¸˜ ao da cache em redes NDN, constantes mudanc¸as decorrente das diversas necessidades de interesse dos consumidores na rede e, esse fator de transic¸˜ ao, n˜ ao pode ser desprezado, para isso, estabelece um m´ etodo para o c´ alculo da popularidade do conte´ udo atrav´ es de um ciclo de contagem que define sobre a substituic¸˜ ao do dado na cache, considerando a maior popularidade entre o estado anterior e o estado atual. Essas mudanc¸as visam o aumento assertivo sobre os conte´ udos que s˜ ao solicitados nas caches e que representa ganhos sobre os conte´ udos que s˜ ao disponibilizados mas, em termos de performance dos equipamentos, est´ a condicionada a uma estrat´ egia de mudanc¸as constantes dentro de um escopo global de armazenamento, o que diferencia da proposta do VERTEX COVER, que possui uma reduc¸˜ ao de equipamentos que executam essa funcionalidade na rede, uma vez que, identificado um n´ ucleo e tendo este n´ ucleo a cobertura sobre todos os roteadores da rede, ´ e poss´ ıvel estabelecer uma relac¸˜ ao de proximidade sobre qualquer outro host. B. Routing Meets Caching in Named Data Networks O presente estudo [6] amplia as discuss˜ oes que envolvem pesquisas voltadas apenas para o encaminhamento de pacotes sem considerar a necessidade de incluir, dentro dessas propostas, quest˜ oes que envolvem uma pol´ ıtica de acesso ao cache que, conforme os autores, limita o potencial e os benef´ ıcios da arquitetura, uma vez que, uma das caracter´ ısticas que diferenciam as redes centradas na informac¸˜ ao do modelo atual ´ e, justamente, a ausˆ encia da necessidade de estabelecer uma comunicac¸˜ ao fim a fim, haja vista que, o objetivo do consumidor n˜ ao ´ e atingir o produtor e sim o seu conte´ udo. Para essa abordagem, os autores buscam um modelo de encaminhamento que melhora a probabilidade de encontrar os conte´ udos armazenados na cache, estabelecendo um novo plano de encaminhamento, fazendo uso do banco de dados de estado do link (LSDB) dos roteadores, que trocam informac¸˜ oes a partir de atualizac¸˜ oes ou alterac¸˜ oes na topologia da rede, com o objetivo de estabelecer um caminho m´ ınimo para a replicac¸˜ ao da cache no ambiente, selecionando sempre o mesmo roteador de borda, definido por uma zona, para encaminhar seus interesses antes de chegar uma nova zona. Ainda segundo os autores, embora essas estrat´ egias possam seguir caminhos mais longos, eles podem reduzir o atraso na recuperac¸˜ ao de conte´ udo, considerando a existˆ encia de uma maior probabilidade de atender a solicitac¸˜ ao por um roteador intermedi´ ario, esse cen´ ario, estabelece um modelo capaz de atender a uma regi˜ ao provida de zoneamento a partir de um protocolo como o Based Routing Protocol for Named Data Networking (OSPFN) [8] criado em 2012, mas que, no ano seguinte, foi descontinuado com o surgimento do Nameddata Link State Routing Protocol NLSR [9], que corresponde ao atual protocolo de roteamento da NDN, implementado e utilizado nos simuladores e emuladores da arquitetura NDN. A soluc¸˜ ao do VERTEX COVER, tamb´ em compat´ ıvel com um modelo de zoneamento, n˜ ao tem o seu foco apenas na recuperac¸˜ ao do conte´ udo mas tamb´ em na capacidade de armazenamento e processamento global sem perda na recuperac¸˜ ao dos dados, uma vez que, n˜ ao existe um host da rede sem cobertura de conex˜ ao pelo n´ ucleo core definido pela soluc¸˜ ao proposta do algoritmo do VERTEX COVER, o que nos remete a um cen´ ario n˜ ao s´ o de recuperac¸˜ ao de dados, considerando a caracter´ ıstica da arquitetura NDN de prover cache em todos os hosts da rede mas tamb´ em, de evitar o desperd´ ıcio de armazenamento e processamento desses hosts na rede. IV. METODOLOGIA O processo de verificac¸˜ ao da soluc¸˜ ao proposta foi realizado utilizando como elemento validador o sistema de emulac¸˜ ao MiniNDN1, amplamente utilizado em pesquisas que envolvem a arquitetura NDN, para isso, a construc¸˜ ao do projeto foi dividido em 03 (trˆ es) partes: i Definic¸˜ ao da Topologia: Foi utilizada a topologia UCLA (minindn.ucla.conf) dispon´ ıvel na instalac¸˜ ao padr˜ ao do MiniNDN e que representa um conjunto de roteadores, tamb´ em identificados como nodes, interligados de forma aleat´ oria, fig.2. A escolha da topologia se deu em func¸˜ ao da compatibilidade com os formatos j´ a existentes no emulador e tamb´ em pela representac¸˜ ao de um cen´ ario conhecido; ii Definic¸˜ ao do Experimento: O experimento (vertexcover.py) consiste na definic¸˜ ao do comportamento dos nodes na inicializac¸˜ ao do ambiente, o objetivo ´ e produzir um ambiente com todos os elementos necess´ arios para a execuc¸˜ ao do algoritmo VERTEX COVER em qualquer um dos nodes do cen´ ario. Para que a integrac¸˜ ao pudesse ter efeito no sistema MiniNDN, foi necess´ ario compilar o ambiente com a classe VertexCover em Python dentro do diret´ orio padr˜ ao de experimentos do emulador; iii Execuc¸˜ ao do VERTEX COVER: Uma vez inicializado o ambiente, trazendo como parˆ ametro na sua inicializac¸˜ ao os itens “i” e “ii”, topologia e experimento, respectivamente, foi necess´ ario criar os elementos que identificassem o VERTEX COVER na topologia, esse processo foi realizado tomando como base a implementac¸˜ ao do Professor [5], do Instituto de Matem´ atica e Ciˆ encias Naturias de Gurgaon. 1https://github.com/named-data/mini-ndn Figura 2. Representac¸˜ ao Gr´ afica da Topologia UCLA. Para que fosse poss´ ıvel a integrac¸˜ ao do ambiente MiniNDN com a soluc¸˜ ao proposta por [5], algumas modificac¸˜ oes no c´ odigo foram necess´ arias visando adequar a soluc¸˜ ao proposta ao sistema de emulac¸˜ ao utilizado na pesquisa, j´ a que n˜ ao existia compatibilidade entre os formatos de entrada existentes. A primeira alterac¸˜ ao foi em func¸˜ ao da impossibilidade de gerar um resultado a partir do formato da topologia adotada pelo MiniNDN, neste sentido, foi utilizado um programa em Python (vertex cover.py) que pudesse converter o formato minindn.ucla.conf para um formato de matriz de adjacˆ encia, gerando assim uma entrada v´ alida para o programa VERTEX COVER (vertex cover.cpp compilado para vertex cover). O resultado obtido, a partir do formato de matriz convertido, gera uma sa´ ıda que ser´ a utilizada para construir o n´ ucleo da rede, fig.3, identificado como CACHE CORE. Esse processo ´ e realizado atrav´ es da transferˆ encia do resultado obtido para o ambiente completo, que ´ e realizada atrav´ es de um outro programa Bash (vertex cover.sh), que tem como func¸˜ ao mapear os nodes identificados e promover a habilitac¸˜ ao desses nodes para a CACHE CORE, fazendo com que apenas eles possam ser utilizados como cache na topologia da rede. Figura 3. Representac¸˜ ao Gr´ afica da Topologia UCLA com os NODES identificados pelo VERTEX COVER. Esse processo de integrac¸˜ ao gerou, como resultado da topologia utilizada, um core representado pelos nodes: arizona, caida, csu, memphis, umich e wustl. Esse subconjunto, apesar de n˜ ao ser o ´ unico subconjunto m´ ınimo poss´ ıvel, representa um dos subconjuntos m´ ınimos poss´ ıveis para comunicac¸˜ ao entre todos os nodes da rede, e que atende ao objetivo da proposta. ´ E poss´ ıvel perceber que a identificac¸˜ ao desses nodes na rede, cobre todas as relac¸˜ oes, ou links, existentes entre eles, permitindo que, seja qual for o caminho utilizado na rede, existir´ a sempre um node que estar´ a conectado ao n´ ucleo ao CACHE CORE. V. EXPERIMENTO O desenvolvimento do ambiente traz como resultado um cen´ ario em que o experimento de validac¸˜ ao do n´ ucleo precisa estar integrado ao sistema de emulac¸˜ ao MiniNDN, esse processo deriva da compilac¸˜ ao do emulador com o experimento vertexcover criado, sendo ele respons´ avel pela construc¸˜ ao do ambiente da rede com a soluc¸˜ ao VERTEX COVER proposta integrada, fig.4. Figura 4. M´ etodo run do experimento vertexcover. Uma vez constru´ ıdo o ambiente nos hosts da rede do emulador para a execuc¸˜ ao do VERTEX COVER na topologia definida, se faz uma marcac¸˜ ao dos a hosts atrav´ es de um token denominado “cachevc”, para isso, foi criado um m´ etodo run, fig.5, que recebe os elementos definidos pela pesquisa e retorna um arquivo cache informando quais s˜ ao os hosts cobertos pelo n´ ucleo para recebimento do token. Figura 5. M´ etodo run no c´ odigo vertex cover.py. O arquivo cache gerado tem como resultado a validac¸˜ ao dos hosts na rede que precisam ser identificados no n´ ucleo CACHE CORE, essa validac¸˜ ao se consolida atrav´ es do recebimento do token “cachevc” ($COVER), fig.6, respons´ avel pela identificac¸˜ ao de pertencimento do host no n´ ucleo CACHE CORE gerado pela aplicac¸˜ ao VERTEX COVER. Para possibilitar a integrac¸˜ ao do padr˜ ao utilizado na topologia das redes do emulador com a soluc¸˜ ao proposta pelo Professor [5], foi necess´ ario realizar uma convers˜ ao da topologia identificada pelos links, fig.7, para o formato de matriz de Figura 6. Marcac¸˜ ao do token “cachevc” nos hosts da rede. adjacˆ encia, fig.8, e a partir desse modelo, gerar os resultados. Figura 7. Padr˜ ao utilizado para conex˜ ao entre os hosts da topologia minindn.ucla.conf. Figura 8. Matriz de adjacˆ encia gerada a partir da topologia minindn.ucla.conf A consolidac¸˜ ao da soluc¸˜ ao verifica primeiro se o host corresponde ao produtor da informac¸˜ ao solicitada na rede, caso afirmativo, retorna o dado pela interface que recebeu a requisic¸˜ ao, registrada na tabela de interesses pendentes (PIT), do inglˆ es [Pending Interest Table], caracter´ ıstica nativa da arquitetura NDN. Caso o host n˜ ao seja o Produtor da informac¸˜ ao, o fluxo do pacote ´ e representado pelo algoritmo de validac¸˜ ao da cache, fig.9, que estabelece primeiro se existe um token de validac¸˜ ao para a realizac¸˜ ao do processamento de busca dessa cache no dispositivo, em seguida, faz a verificac¸˜ ao da existˆ encia do dado solicitado e, caso contr´ ario, ´ e realizado o registro na PIT e o fluxo segue o seu encaminhamento at´ e encontrar uma entrada v´ alida em cache para a informac¸˜ ao solicitada ou at´ e atingir o produtor da informac¸˜ ao. Figura 9. Algoritmo de Validac¸˜ ao da Cache. ´ E importante destacar que o processo de encaminhamento do pacote e verificac¸˜ ao da cache, assim como, registro de interesses pendentes atrav´ es da tabela PIT ´ e intr´ ınseco a arquitetura NDN e que, o nosso estudo busca encontrar um n´ ucleo definido pela soluc¸˜ ao do VERTEX COVER com uma identificac¸˜ ao baseado em token, e que pode ser substitu´ ıda por outro m´ etodo de identificac¸˜ ao, com o objetivo de estabelecer um ganho de processamento e armazenamento global. VI. TRABALHOS FUTUROS As discuss˜ oes trazidas acerca da construc¸˜ ao do ambiente nos remetem a resultados promissores, por´ em, alguns avanc¸os s˜ ao necess´ arios para viabilizar um projeto de implementac¸˜ ao na pr´ atica, dentre esses elementos, vislumbramos a necessidade de produzir um ambiente de autenticac¸˜ ao baseado na gerac¸˜ ao de chaves, atrav´ es do comando ndnsec-key-gen2, que possibilita identificar o host da rede de forma ´ unica, proporcionando uma maior seguranc¸a no processo de composic¸˜ ao e autenticac¸˜ ao do n´ ucleo da cache. Um outro elemento destacado no cen´ ario ´ e a necessidade de comunicac¸˜ ao entre diversas autoridades administrativas diferentes, isso, porque o escopo do estudo est´ a atrelado apenas a uma ´ area espec´ ıfica, cujo o controle da topologia ´ e conhecida e interligada dentro de uma mesma ´ area, restringindo o cen´ ario a um ambiente espec´ ıfico de atuac¸˜ ao. 2https://named-data.net/doc/ndn-cxx/current/manpages/ndnsec-keygen.html Dentro do escopo de rede de computadores, desenvolver estrat´ egias unificadas e automatizadas de propagac¸˜ ao de todo o processo, considerando e identificando correc¸˜ oes autom´ aticas em caso de alterac¸˜ ao na topologia da rede, ´ e tamb´ em um avanc¸o a ser considerado dentro da soluc¸˜ ao proposta, mas que, nesse primeiro momento, por quest˜ oes did´ aticas, foram implementadas de forma separada para expressar todo o processo, destacando o passo a passo da evoluc¸˜ ao do ambiente. VII. CONCLUS ˜ AO Algoritmos que consideram o estado do link, a partir de m´ etricas que influenciam na decis˜ ao sobre o encaminhamento dos pacotes na rede, normalmente, possuem um tempo de convergˆ encia menor, mas exigem um consumo maior de mem´ oria e CPU. Todo o processamento decorrente das caracter´ ısticas presentes nesses algoritmos tem a sua inteligˆ encia centrada nos roteadores que fazem parte da rede, nesta proposta, todo o processamento de construc¸˜ ao de cache na rede NDN ´ e transferido para apenas um roteador da rede, fazendo com que os outros dispositivos possam ter seu processamento utilizado apenas para a construc¸˜ ao da tabela de roteamento. Os ganhos decorrentes dessa implementac¸˜ ao evidenciam resultados que perpassam pela alterac¸˜ ao da necessidade de utilizar e consultar cache em todos os roteadores da rede, com o processo de verificac¸˜ ao da cache agora restrito a apenas um n´ ucleo, obt´ em-se como resultado imediato dessa aplicac¸˜ ao, uma reduc¸˜ ao do processamento, se considerado toda a topologia, al´ em da reduc¸˜ ao da necessidade de armazenamento, se considerado toda a topologia tamb´ em. Como resultado do estudo, ´ e poss´ ıvel identificar que, a VERTEX COVER, se consolida como uma soluc¸˜ ao vi´ avel e otimista para implementac¸˜ oes em redes NDN que tratam como escopo de pesquisa a cache na utilizac¸˜ ao da rede, considerando que essa soluc¸˜ ao ´ e agn´ ostica ao tipo de roteamento utilizado no cen´ ario. REFER ˆ ENCIAS [1] The Global Internet Phenomena Report. SANDVINE. Outubro de 2018. [Online]. Dispon´ ıvel em: ¡https://www.sandvine.com/hubfs/downloads/phenomena/2018phenomena-report.pdf¿. Acesso em: Junho de 2021. [2] Zhang, L. et al. Named Data Networking. ACM SIGCOMM Computer Communication Review Volume 44, N´ umero 3, Julho 2014. [3] Cormem, T et al.; Algoritmos Teoria e Pr´ atica. , Elsevier Editora Ltda. Rio de Janeiro. 2009. [4] Feofiloff, Paulo, Yoshiharu Kohayakawa, and Yoshiko Wakabayashi. ”Uma introduc¸˜ ao sucinta ` a teoria dos grafos.”(2011). [5] Dharwadker, A. The Vertex Cover Algorithm. 2006. [Online]. Dispon´ ıvel em: ¡http://www.dharwadker.org/vertex cover/¿. Acesso em: Junho de 2021. [6] Ghasemi, Chavoosh, et al. ”Routing meets caching in named data networks.”IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). IEEE, 2018. [7] Hua Ran, Jian, et al. ”On performance of cache policies in named data networking.”2013 International Conference on Advanced Computer Science and Electronics Information (ICACSEI 2013). Atlantis Press, 2013. [8] Wang, Lan, et al. OSPFN: An OSPF based routing protocol for named data networking. Technical Report NDN-0003, 2012. [9] Hoque, AKM Mahmudul, et al. ”NLSR: Named-data link state routing protocol.”Proceedings of the 3rd ACM SIGCOMM workshop on Information-centric networking. 2013.