<< Volver atrás

Tesis:

Construcción y navegación de redes de Pequeño Mundo

  • Autor: SEVILLA DE PABLO, Andrés

  • Título: Construcción y navegación de redes de Pequeño Mundo

  • Fecha: 2020

  • Materia: Sin materia definida

  • Escuela: E.T.S.I. DE SISTEMAS INFORMÁTICOS

  • Departamentos: ARQUITECTURA Y TECNOLOGIA DE COMPUTADORES (E.U. INFORMATICA)

  • Acceso electrónico: http://oa.upm.es/65788/

  • Director/a 1º: FERNÁNDEZ ANTA, Antonio

  • Resumen: Uno de los problemas fundamentales en las redes de ordenadores, por ejemplo Internet, es la localización eficiente de recursos. Una de las formas de abordar el problema es la utilización de redes superpuestas. En esta tesis usamos redes superpuestas en las que los nodos se conectan con una geometría que permita una localización más rápida de los recursos en la red. En la construcción 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 computación epidémica que permite obtener, de forma eficiente, en cada nodo de una red grande el resultado de un cálculo agregado utilizando valores almacenados en todos los nodos de la red. Un segundo paradigma es la asignación de posiciones a los nodos de Internet. Para ello se asignan posiciones a los nodos en un determinado espacio métrico. Las posiciones asignadas a los nodos junto con el concepto de distancia van a permitir la construcción de redes superpuestas y el diseño de algoritmos de encaminamiento geográfico eficientes, ya que la distancia entre dos nodos es una buena estimación de la latencia real entre los mismos. Un tercer paradigma que usado en nuestras redes es la propiedad de “Pequeño Mundo”, que combinada con la utilización de algoritmos de encaminamiento geográfico ávidos permitirá localizar un nodo eficientemente. Un cuarto paradigma es la utilización de algoritmos no deterministas que, en ciertos tipos de redes, no necesiten de la posición de los nodos para localizar un recurso de forma rápida y eficiente. El muestreo (selección) de nodos de una red es la piedra angular para la construcción de redes superpuestas. Se han diseñado y evaluado dos nuevos algoritmos distribuidos de muestreo, BS y RCW. BS permite seleccionar nodos con cualquier distribución de probabilidad utilizando únicamente información local a los nodos. RCW es un paseo aleatorio que proporciona un muestreo exacto con la distribución de probabilidad deseada. En su funcionamiento siempre se aleja de la fuente que lo originó, lo que hace que la longitud del paseo esté acotado por el diámetro de la red. En la tesis también se ha propuesto un nuevo modelo de red que permite construir redes sin escala, además de dos algoritmos que aprovechan la topología de la red para obtener un encaminamiento eficiente. Las redes superpuestas propuestas en esta tesis podrán ser utilizadas en varios ámbitos, 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.