Construcción y navegación de redes de pequeño mundo (2020)

Uno de los problemas fundamentales en las redes de ordenadores, por ejemplo Internet, es la localizacion eficiente de recursos. Una de las formas de abordar el problema es la utilizacion de redes superpuestas. En esta tesis usamos redes superpuestas en las que los nodos se conectan con una geometria que permita una localizacion mas rapida de los recursos en la red. En la construccion de estas redes superpuestas se hace uso un conjunto de paradigmas habitualmente utilizados en los sistemas entre pares (peer-to-peer) en Internet. El primer paradigma es la computacion epidemica que permite obtener, de forma eficiente, en cada nodo de una red grande el resultado de un calculo agregado utilizando valores almacenados en todos los nodos de la red. Un segundo paradigma es la asignacion de posiciones a los nodos de Internet. Para ello se asignan posiciones a los nodos en un determinado espacio metrico. Las posiciones asignadas a los nodos junto con el concepto de distancia van a permitir la construccion de redes superpuestas y el diseno de algoritmos de encaminamiento geografico eficientes, ya que la distancia entre dos nodos es una buena estimacion de la latencia real entre los mismos. Un tercer paradigma que usado en nuestras redes es la propiedad de “Pequeno Mundo”, que combinada con la utilizacion de algoritmos de encaminamiento geografico avidos permitira localizar un nodo eficientemente. Un cuarto paradigma es la utilizacion de algoritmos no deterministas que, en ciertos tipos de redes, no necesiten de la posicion de los nodos para localizar un recurso de forma rapida y eficiente. El muestreo (seleccion) de nodos de una red es la piedra angular para la construccion de redes superpuestas. Se han disenado y evaluado dos nuevos algoritmos distribuidos de muestreo, BS y RCW. BS permite seleccionar nodos con cualquier distribucion de probabilidad utilizando unicamente informacion local a los nodos. RCW es un paseo aleatorio que proporciona un muestreo exacto con la distribucion de probabilidad deseada. En su funcionamiento siempre se aleja de la fuente que lo origino, lo que hace que la longitud del paseo este acotado por el diametro de la red. En la tesis tambien se ha propuesto un nuevo modelo de red que permite construir redes sin escala, ademas de dos algoritmos que aprovechan la topologia de la red para obtener un encaminamiento eficiente. Las redes superpuestas propuestas en esta tesis podran ser utilizadas en varios ambitos, como por ejemplo para mejorar los sistemas de “streaming” o facilitar el funcionamiento de las redes que se adaptan a la carga. ----------ABSTRACT---------- One of the fundamental problems in computer networks, for example the Internet, is the efficient location of resources. One of the ways to address the problem is to use overlay networks. In this thesis we use overlay networks in which the nodes are connected with a geometry that will allow faster location of the resources in the network. In the construction of these overlay networks, we use a set of paradigms commonly used in peer-to-peer systems on the Internet. The first paradigm is epidemic computing, which allows obtaining, efficiently, at each node of a large network, the result of an aggregate calculation using values stored at all nodes in the network. A second paradigm is assigning positions to Internet nodes. For this, positions have been assigned to the nodes in a given metric space. The positions assigned to the nodes together with the concept of distance will allow the construction of overlay networks and the design of efficient geographic routing algorithms, since the distance between two nodes is a good estimate of the actual latency between them. A third paradigm that we intend to use in our networks is the “Small-World” property, which, combined with the use of greedy geographic routing algorithms, will allow us to locate a node efficiently. A fourth paradigm is the use of non-deterministic algorithms that, in certain types of networks, do not need the position of the nodes to locate a resource quickly and efficiently. The sampling service (selection) of nodes in a network is the cornerstone for the construction of overlay networks. In this tesis, two new distributed sampling algorithms have been proposed and evaluated, BS and RCW. BS allows you to select nodes with any probability distribution using only local information to the nodes. RCW is a random walk that selects a node with the exact probability distribution. I t always finishes in a number of hops bounded by the network diameter. The thesis also proposed a new network model that allows the construction of scale-free networks, in addition to two algorithms that take advantage of the network topology to obtain an efficient routing. The overlay networks proposed in this thesis may be used in several areas, such as to improve streaming systems or facilitate the operation of networks that adapt to the load.