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

Sevilla de Pablo, Andrés (2020). Construcción y navegación de redes de Pequeño Mundo. Thesis (Doctoral), E.T.S.I. de Sistemas Informáticos (UPM). https://doi.org/10.20868/UPM.thesis.65788.

Description

Title: Construcción y navegación de redes de Pequeño Mundo
Author/s:
  • Sevilla de Pablo, Andrés
Contributor/s:
  • Fernández Anta, Antonio
Item Type: Thesis (Doctoral)
Date: October 2020
Subjects:
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Arquitectura y Tecnología de Computadores [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only until 18 June 2021 - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB)

Abstract

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.

More information

Item ID: 65788
DC Identifier: http://oa.upm.es/65788/
OAI Identifier: oai:oa.upm.es:65788
DOI: 10.20868/UPM.thesis.65788
Deposited by: Archivo Digital UPM 2
Deposited on: 22 Dec 2020 09:00
Last Modified: 22 Dec 2020 09:00
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM