Orientador: Maurício Ferreira Magalhães

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação

Resumo: Roteamento é uma das principais funções em redes de computadores, sendo responsável pelo encaminhamento de tráfego entre todos os pares de nós de origem e destino. O princípio de roteamento comum a protocolos usados mundialmente requer a presença de informação sobre todos os destinos...

Resumo: Roteamento é uma das principais funções em redes de computadores, sendo responsável pelo encaminhamento de tráfego entre todos os pares de nós de origem e destino. O princípio de roteamento comum a protocolos usados mundialmente requer a presença de informação sobre todos os destinos disponíveis, em todos os roteadores compondo a rede, de tal forma a garantir a entrega de tráfego. Desta forma, construir redes em grande escala usando tal princípio de roteamento é amplamente aceito como não escalável. O problema intrínseco destes mecanismos está relacionado ao fato de que as tabelas de roteamento acompanham o crescimento da informação de roteamento presente na rede. Por outro lado, existem mecanismos de roteamento disponíveis na literatura que requerem apenas uma fração de toda a informação de roteamento presente na rede, provendo um melhor controle para a taxa à qual as tabelas de roteamento crescem. Neste cenário, um espaço de identificação plano é usado para identificar, univocamente, todos os nós presentes na rede e relações de vizinhança no espaço de identificação plano são estabelecidas através de uma rede sobreposta, construída sob um substrato de rede, como, por exemplo, uma rede IP. Entretanto, manter a coerência desta rede sobreposta é desafiador, uma vez que os nós podem mudar seus pontos de conexão no substrato de rede, resultando no uso de diferentes endereços (IPs) e requerendo mecanismos para manter ativa a associação entre a rede sobreposta e o substrato de rede. Neste contexto, este trabalho propõe o uso de uma organização de rede alternativa, onde nenhum substrato de rede é necessário para prover a comunicação entre nós no espaço de identificação. O mecanismo de roteamento plano proposto é baseado em uma métrica de ou-exclusivo (XOR) e no conceito de visibilidade local. Tal combinação acarreta a criação de uma estrutura de rede em malha e promove a integração entre o espaço de identificação plano e a estrutura física da rede. Basicamente, o mecanismo de roteamento baseado em operações de XOR efetua roteamento diretamente sob identificadores planos. Este trabalho apresenta a especificação completa do protocolo, descrevendo suas principais propriedades relacionadas ao tamanho das tabelas de roteamento, à quantidade de mensagens de sinalização necessárias para convergir o sistema de roteamento e os caminhos obtidos. Além disso, este trabalho detalha a instanciação do mecanismo de roteamento plano proposto em três diferentes cenários: 1) redes de data centers, 2) redes veiculares ad hoc (VANETs) e 3) o sistema de roteamento entre domínios da Internet

Abstract: Routing is one of the main functions of computer networks, being responsible for traffic forwarding between all pairs of source and destination nodes. The common routing principle of protocols used in networks worldwide requires the presence of information about all available destinations,...

Abstract: Routing is one of the main functions of computer networks, being responsible for traffic forwarding between all pairs of source and destination nodes. The common routing principle of protocols used in networks worldwide requires the presence of information about all available destinations, in all routers composing the network, in order to assure traffic delivery. In this way, building large scale networks using such routing principle is widely regarded as non scalable. The intrinsic problem of such mechanisms is related to the fact that routing tables follow the growth of the routing information present in the network. Conversely, there are routing mechanisms available in the literature which require just a fraction of the overall routing information present in the network, providing a better control for the rate at which the routing tables grow. In such scenario, a flat identity space is used to uniquely refer to all nodes present in the network, and neighborhood relations at the flat identity space are established through an overlay network, built on top of a substrate network, such as an IP network. However, maintaining the correctness of the overlay network is challenging, since nodes can change their attachment points at the substrate network, resulting in the use of different addresses (IPs), and requiring mechanisms to keep the association between the overlay network and the substrate network active. In this context, this work proposes the usage of an alternative network organization, where no substrate network is required to provide the communication between nodes at the flat identity space. The proposed flat routing mechanism is based on the bitwise exclusive or (XOR) metric and in the concept of local visibility. Such combination leads to the creation of a mesh network structure and promotes the integration between the flat identity space and the physical network structure. Basically, the proposed XOR-based routing mechanism performs routing directly on top of flat identifiers. This work presents the entire protocol specification, describing its main properties related to the size of the required routing tables, the amount of signaling messages needed to converge the routing system, and the obtained paths. Afterwards, this work also details the instantiation of the proposed flat routing mechanism in three different scenarios: 1) data center networks, 2) ad hoc vehicular networks (VANETs) and 3) the inter-domain Internet routing system