Small world models and a compact routing scheme

Abstract

Resumo: Os modelos geradores de redes de mundo pequeno são alternativas aleatorizadas de construção de redes onde os nós estão interligados por caminhos curtos. Nesse contexto, um caminho curto tem o comprimento dado por uma função logarítmica no tamanho da rede. Aplicações em redes peer-to-peer, de sensores sem fio e implementação de redes em chip são alguns exemplos computacionais que utilizam redes geradas por modelos matemáticos de mundo pequeno. Esse trabalho apresenta o modelo de redes de mundo pequeno toroidal não direcionado (UTSW). O modelo gera uma grade bidimensional base para modelar o agrupamento dos nós, e conexões aleatórias para modelar caminhos curtos. A presença de caminhos curtos não implica a existência de um algoritmo de roteamento de mensagens que os encontra. Porém, existe um algoritmo de roteamento guloso na literatura que encontra caminhos curtos em redes UTSW, sendo que um caminho curto tem o comprimento dado por uma função polilogarítmica no tamanho da rede. O modelo de mundo pequeno octaédrico (OSW) também é apresentado. Ele gera um grafo planar base sobre o octaedro, que é provado ser similar à geração sobre esferas. Assim, ele simula pessoas e vizinhanças na superfície do planeta. O modelo OSW também gera conexões aleatórias para modelar caminhos curtos. Um algoritmo de roteamento que encaminha mensagens por caminhos curtos também é definido para esse modelo. Ambos os algoritmos de roteamento utilizam o paradigma guloso e decidem para qual vizinho encaminhar uma mensagem com somente a informação na tabela de roteamento do nó. Esses algoritmos requerem pouca memória por nó, encontram caminhos curtos e executam em tempo constante, nos dois modelos apresentados. Por isso, eles são boas opções em roteamento, além do roteamento por caminhos mínimos. No entanto, ambos necessitam de informações de posicionamento geradas pelo modelo matemático. No caso do modelo UTSW, cada nó possui um par ordenado de números naturais que o posiciona na grade bidimensional. Encontrar essas posições quando elas são desconhecidas é desafiador, pois as conexões geradas aleatoriamente dificultam a identificação da grade. Porém, a conexão aleatória de um nó quebra o padrão de grade em sua vizinhança com baixa probabilidade. Essa propriedade topológica das redes UTSW motivou o projeto de um algoritmo de rotulação que encontra as posições na grade com alta probabilidade. Ele realiza uma busca local em cada nó e remove a conexão aleatória, se ela for identificada. Após a varredura, o algoritmo realiza uma busca em largura global na rede resultante, posicionando cada nó com base nas posições já encontradas de seus vizinhos. Um esquema de roteamento compacto para grafos UTSW é então apresentado. Ele é composto por um algoritmo de pré-processamento que utiliza o algoritmo de rotulação para gerar estruturas de dados de tamanho logarítmico para todos os nós e que executa em tempo linear no tamanho da rede. Com isso, o algoritmo de roteamento guloso encaminha mensagens utilizando as estruturas de dados geradas pelo algoritmo de pré-processamento.

Abstract: Small world networks generative models are randomized alternatives of network building where nodes are interconnected by small paths. In this context, a small path has the length given by a logarithmic function in the size of the network. Applications in peer-to-peer networks, wireless sensors and networks on chip are some computational examples that use networks generated by small world mathematical models. This work presents the undirected toroidal small world networks model (UTSW). The model generates a base two-dimensional grid to model the clustering of the nodes, and random connections to model small paths. The presence of small paths does not imply in the existence of a message routing algorithm that finds them. However, there is a greedy routing algorithm in the literature that finds small paths in UTSW networks, where a small path has the length given by a polylogarithmic function in the size of the network. The octahedral small world model (OSW) is also presented. It generates a base planar graph on the octahedron, which is proved to be similar to the generating on spheres. Then, it simulates people and neighborhoods on the surface of the planet. The OSW model also generates random connections to model small paths. A routing algorithm that routes messages through small paths is also defined for this model. Both routing algorithms use the greedy paradigm and decide to which neighbor to forward a message with only the information in the routing table of the node. These algorithms require small amount of memory per node, find small paths and execute in constant time, in both presented models. So, they are good options in routing, besides the routing thought shortest paths. However, both require positioning information generated by the mathematical model. In the case of UTSW model, each node has an ordered pair of natural numbers that positions it on the two-dimensional lattice. Finding these positions when they are unknown is challenging because the randomly generated connections make the grid identification difficult. However, the random connection of a node breaks the lattice pattern in its neighborhood with small probability. This topological property of UTSW networks motivated the design of a labeling algorithm that finds the positions in the lattice with high probability. It executes a local search on each node and removes the random connection if it is identified. After the sweeping, the algorithm executes a global breadth-first search on the resulting network, positioning each node based on the already found positions of its neighbors. A compact routing scheme for UTSW graphs is then presented. It consists of a preprocessing algorithm that uses the labeling algorithm to generate logarithmic size data structures for all nodes and executes in linear time on the size of the network. Thus, the greedy routing algorithm routes messages using the data structures generated by the preprocessing algorithm.