Named data networking with programmable switches

Tese de mestrado em Engenharia Informática (Arquitectura, Sistemas e Redes de Computadores) Universidade de Lisboa, Faculdade de Ciências, 2017

As redes IP, que são universais atualmente, apresentam um conjunto de problemas que encontra a sua génese nos seus propósitos originais. Na génese do IP, o objetivo era a partilha de recursos. Hoje em dia, as redes de computadores já não se baseiam num computador mainframe a disponibilizar recursos de hardware. São usadas como meio de disseminação alargada de uma panóplia de média, como ficheiros de hipertexto, imagens e vídeos. Grande parte das dificuldades no uso das redes IP advém do uso de endereços. A necessidade do enderenço como identificador indispensável à comunicação obrigou ao aparecimento de esquemas complexos à medida que as redes cresceram: refere-se o DNS, o DHCP e a gestão de prefixos associada às unidades autónomas (autonomous systems, conhecidas também pela sigla AS). Já quase se esgotou o espaço público de endereços, para além de que a gestão dos reservatórios públicos e privados é um processo complicado e propenso a erros. A par deste panorama, o hardware da rede foi otimizado para desempenho e os dispositivos de encaminhamento (routers) e comutação (switches) tornaram-se caixas negras fechadas, correndo vários protocolos em hardware para maximizar o desempenho. O software dos hospedeiros (hosts), por seu turno, materializou-se na API de sockets que usamos até hoje. As redes baseadas em nomes (named data networks, ou NDN) divergem fundamentalmente da rede IP. Enquanto que a última tem como objectivo transportar um pacote para um destino com base no seu endereço, as NDN não fazem qualquer uso de endereços. O problema é reformulado em como levar dados com um determinado nome de um produtor para os consumidores. Assim, na rede NDN circulam apenas dois tipos de pacotes: Interest e Data. Os pacotes Interest são emitidos por consumidores que procuram dados. Estes dados estão globalmente e univocamente ligados a um pedaço de informação. A rede NDN trata de encaminhar o pedido Interest até um produtor. Em resposta, o produtor emite um pacote Data, que alberga, no seu interior, o pedaço de informação correspondente ao que foi pedido no Interest. Os nomes são o centro da NDN. Podem ser flat, mas também podem ser utilizados de forma hierárquica. Por exemplo, “ulisboa/fciencias/index.html”´e um nome hierárquico. Cada troço do nome separado por ‘/’ chama-se um componente. Esta hierarquia é fundamental para conferir contexto ao nome e escalar a NDN. Esta mudança de paradigma oferece vantagens. Desde logo, o endereço torna-se desnecessário, evitando assim processos de gestão intermédios, exaustão do reservatório de endereços públicos e o uso dos Network Address Translators (NATs). Para além disso, todos os pacotes Data vêm assinados, pelo que as NDN dispõem de segurança inerente e, a par disto, de uma maior dificuldade em atacar alvos específicos, dado que todos os dispositivos na rede, quer nós intermediários quer hospedeiros, estão desprovidos de identificação. Os problemas de segurança existem, mas reduzem-se, desta forma, a distribuição de chaves segura, buracos negros (black holes) e ataques distributed denial of service (DDoS). O encaminhamento em NDN é semelhante ao que ocorre no IP, mas, em vez de manter endereços de 32 bits nas tabelas de comutação, os encaminhadores utilizam os nomes, de comprimento arbitrário para decidir por onde encaminhar os pacotes. As tabelas são populadas de modo análogo ao que acontece no IP, por exemplo através de um protocolo link-state para NDN, homólogo do OSPF. As tabelas de comutação têm, portanto, pares (string, integer), associando um nome a uma dada interface (que pode ser física ou lógica) do dispositivo. Quando um nome faz match com mais de uma entrada, é selecionada aquela que tiver maior número de componentes (e, portanto, for o prefixo mais comprido). Quando recebe um pacote Interest, o encaminhador consulta a sua content store para verificar se pode servir o conteúdo diretamente. Nesse sentido, a content store é uma funcionalidade absolutamente fundamental neste paradigma, pois permite trazer o conteúdo para perto dos consumidores. Este caching feito ao nível da rede é considerado uma das grandes mais-valias das NDN. Se puder servir diretamente, fá-lo. Caso contr´ario, o Interest segue para a Tabela de Interests Pendentes (Pending Interest Table, ou PIT), onde se mantém registo dos pedidos na forma de uma lista de interfaces que pediram um determinado nome. Se esta lista está vazia, então este Interest é o primeiro pedido para este nome. Será assim encaminhado para uma interface do dispositivo determinada pela FIB (forwarding information base). A FIB mantém associações (nome,interface) e comuta o pacote se encontrar um nome que seja prefixo do nome inscrito no Interest em processamento; realiza, deste modo, um longest prefix matching de nomes à granularidade do componente. Se a lista não está vazia, então outra interface já requisitou os mesmos dados. Nesse caso, o encaminhador pode descartar o Interest que acabou de receber, pois o pedido para esse nome já foi anteriormente lançado. Apenas adiciona à lista a interface de onde veio este Interest repetido. Quando recebe um pacote Data, o encaminhador consulta a PIT para verificar se está à espera de dados para este nome. Se não, então descarta o pacote. Se está, efetua uma difusão multicast para todas as interfaces que registou na lista para o respetivo nome. Desta forma se consegue garantir que os conteúdos requisitados chegam a todos os consumidores que os pediram. Se os campos de metadados do Data assim o permitirem, o encaminhador também armazenará o Data na content store. Um dos grandes problemas deste novo paradigma é a sua materialização prática. Como vimos, um encaminhador NDN é fundamentalmente diferente do seu homólogo em IP, ou de qualquer outro tipo de comutador de pacotes, e por isso não é possível adaptar equipamento tradicional para NDN. Recentemente, porém, foram propostos comutadores programáveis, alguns já em produção (e.g., Tofino da Barefoot Networks). Estes dispositivos permitem definir precisamente o modo como o equipamento de rede processa pacotes, e reprogramá-lo sempre que necessário. Todavia, programar estes dispositivos, utilizando a sua interface de baixo nível, é quase como programar em microcódigo, e portanto não se trata de uma tarefa fácil. Esta lacuna foi uma das motivações para a linguagem de alto-nível, P4. A linguagem P4 surge no seio das redes programáveis, bem como das redes definidas por software, propiciada pela rigidez do OpenFlow quanto ao conjunto de protocolos que suporta. No entender dos seus criadores, um OpenFlow ideal seria aquele que permitisse ao operador de rede definir os seus próprios cabeçalhos e criar os seus próprios protocolos. Assim, a linguagem P4 tem três grandes objetivos. Primeiro, não estar dependente de nenhum protocolo específico, permitindo, pelo contrário, que estes sejam definidos pelo controlador. Segundo, poder ser reconfigurada pelo plano de controlo a qualquer momento. Terceiro, não estar dependente de nenhuma arquitetura subjacente; isto é, poder ser escrita (e depois compilada) para um qualquer dispositivo da mesma maneira que um programa escrito na linguagem C pode ser escrito sem preocupações relativamente à arquitetura de processador subjacente. O consórcio P4 oferece um compilador front-end que transforma a linguagem P4 numa representação intermédia (IR), enquanto que o vendedor do dispositivo disponibiliza um compilador back-end que processa a IR e traduz para a linguagem própria do aparelho. Um dispositivo assim concebido ´e compatível com P4 (P4-compatible). Com P4, é assim possível definir cabeçalhos, parsers e uma sequência de tabelas de matchaction à escolha para um qualquer aparelho compatível e definir as ações a partir de um conjunto de primitivas oferecidas pela linguagem. Neste trabalho, propomos a conceção de um router NDN utilizando a linguagem P4. O nosso trabalho parte de um anterior chamado NDN.p4 por Signorello et al, que foi implementado na versão 14 do P4 (abreviado P4-14). É um protótipo do encaminhador NDN, proporcionando uma tabela de interesses pendentes (PIT) e uma FIB. A PIT é descrita utilizando registos, que mantém estado no comutador P4. A capacidade de ter estado e de o manusear é indispensável para implementar um encaminhador NDN, como se deduz da nossa anterior descrição sobre o respetivo funcionamento. O trabalho anterior tem, no entanto, limitações. Em primeiro lugar, não dispõe de uma content store, uma das peças principais deste paradigma. Para além disso, o recurso a matching ternário e exato tem problemas de escalabilidade e não há suporte a multicast de pacotes Data. Nesta dissertação, desenhámos e construímos, da forma mais modular e genérica possível, um encaminhador NDN utilizando a versão mais recente do P4, P4-16, providenciando, para além da PIT e da FIB—que faz longest prefix matching utilizando um método inovador —, uma content store implementada quer em registos, quer diretamente no switch P4. As principais inovações são as seguintes:_ Implementação da content store, que armazena pacotes e permite ao encaminhador NDN servir pedidos de imediato. Numa primeira versão, concebêmo-la em registos P4. A segunda versão é editada diretamente num target, o simple switch. _ Utilização de um método inovador para conseguir longest prefix matching (lpm) em redes NDN. O método proposto por Signorello et al apoia-se num mecanismo relativamente complicado de matchings ternário e exato que não escala bem. Optámos por utilizar diretamente o método lpm, mantendo a ideia de efetuar hashing dos componentes do nome. Os resultados dos cálculos de dispersão dos componentes são concatenados pela mesma ordem em que aparecem os componentes respectivos. O produto final desta concatenação figura assim como entrada na tabela, com uma máscara de rede que será o comprimento do resultado da função vezes o número de componentes._ Realização de multicast, quer em linguagem P4 (neste caso, para um número máximo de portos, devido à falta de mecanismos de iteração), quer diretamente no software switch. Finalmente, avaliámos a nossa solução através de vários testes de funcionalidade e comparámos ao NDN.p4 em termos de espaço ocupado pelas entradas da FIB.

Named data networks (NDN) differ substantially from traditional TCP/IP networks. Whereas the TCP/IP communications stack focuses on delivering a packet to a destination based on its address, NDN abolishes the use of addresses and reformulates the problem as how to fetch data with a given name and bring it closer to its consumers. For this purpose, consumers emit Interest packets, writing the name for the resource they desire. The network routes that packet to a producer of the data uniquely associated to that name. NDNs achieve this by employing routers whose functions are similar to those of traditional networks, with a central difference: they route Interests based not on an address, but on a name. Another fundamental innovation of this paradigm is the introduction of a content store in NDN routers. This gives the ability to perform caching in the network, and as such is key to improve network efficiency. The main challenge of NDN is that of deployment. As the design is radically different, current routers and switches cannot be “extended” to offer NDN. Fortunately, the emergence of programmable switches, and of a high-language level to program them (such as P4), gives hope for the state of affairs to change. With P4 it is possible to define precisely how packets are processed in these programmable switches, allowing the definition of headers, parsers, match-action tables, and the entire control flow of packets in the switch. In this dissertation we propose the design of an NDN router and implement it using the P4 language. We improve over previous work in two main aspects: our solution includes, for the first time, a content store. In addition, we propose an innovative method to perform longest prefix matching that requires significantly less memory per route than the former, allowing the FIB to scale more easily. We evaluate our solution using P4 switches, in terms of the main NDN functionality required.