Construcción de redes de pequeño mundo mediante selección sesgada.

Sevilla De Pablo, Andrés and Manzano García, Pilar and Mozo Velasco, Bonifacio Alberto and Lorenzo Prieto, Maria Araceli and López Presa, Jose Luis and Fernández Anta, Antonio (2011). Construcción de redes de pequeño mundo mediante selección sesgada.. In: "JCSD2011: XIX Jornadas de Concurrencia y Sistemas Distribuidos", 08/06/2011 - 10/06/2011, La Granja de San Ildefonso, Segovia. pp. 301-310.

Description

Title: Construcción de redes de pequeño mundo mediante selección sesgada.
Author/s:
  • Sevilla De Pablo, Andrés
  • Manzano García, Pilar
  • Mozo Velasco, Bonifacio Alberto
  • Lorenzo Prieto, Maria Araceli
  • López Presa, Jose Luis
  • Fernández Anta, Antonio
Item Type: Presentation at Congress or Conference (Article)
Event Title: JCSD2011: XIX Jornadas de Concurrencia y Sistemas Distribuidos
Event Dates: 08/06/2011 - 10/06/2011
Event Location: La Granja de San Ildefonso, Segovia
Title of Book: JCSD2011: XIX Jornadas de Concurrencia y Sistemas Distribuidos
Date: 2011
Subjects:
Faculty: E.U. de Informática (UPM)
Department: Informática Aplicada [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (3MB) | Preview

Abstract

En la actualidad las redes de Pequeño Mundo están presentes en muchas aplicaciones distribuidas, pudiéndose construir estas redes añadiendo, a un grafo base, enlaces de largo alcance tomados conforme a una determinada distribución de probabiblidad. Los sistemas distribuidos actuales utilizan soluciones ad hoc específicas para calcular los enlaces de largo alcance. En este artículo proponemos un nuevo algoritmo distribuido llamado Selección Sesgada (SS), que utilizando únicamente un servicio de muestreo uniforme (que puede estar implementado mediante un protocolo gossip), es capaz de seleccionar enlaces largos conforme a cualquier distribución de probabilidad. SS es un algoritmo iterativo que dispone de un único parámetro (r) para indicar el número de iteraciones que debe ejecutarse. Se ha probado que la muestra obtenida con el algoritmo SS converge a la distribución objetivo a medida que aumenta el valor de r. También se ha calculado la cota analítica del error relativo máximo, para un determinado valor de r. Aunque este artículo se propone para el algoritmo SS como una herramienta para tomar muestras de nodos en una red, puede emplearse en cualquier contexto en el que sea necesario realizar un muestreo conforme a una determinada distribución de probabilidad, necesitando para funcionar únicamente un servicio de muestreo uniforme. Se han construido redes de Pequeño Mundo, modelo Kleinberg, utilizando SS para escoger los enlaces (vecinos) de largo alcance en estructuras de tipo toro. Hemos observado que con un número reducido de iteraciones (1) SS tiene un comportamiento muy similar a la distribución armónica de Kleinberg y (2) el número medio de saltos, utilizando enrutamiento ávido, no es peor que en una red construida con la distribución de Leinberg. También se ha observado que antes de obtener la convergencia, el número medio de saltos es menor que en las redes construidas mediante la distribución armónica de Leinberg (14% mejor en un toro de 1000 x 1000).

More information

Item ID: 19263
DC Identifier: http://oa.upm.es/19263/
OAI Identifier: oai:oa.upm.es:19263
Official URL: http://www.yasni.info/ext.php?url=http%3A%2F%2Fjcsd2011.eui.upm.es%2Fprogram&name=Marisa+Llorens&showads=1&lc=es-es&lg=es&rg=es&rip=es
Deposited by: Memoria Investigacion
Deposited on: 25 Mar 2014 12:15
Last Modified: 21 Apr 2016 17:31
  • 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