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

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

Descripción

Título: Construcción de redes de pequeño mundo mediante selección sesgada.
Autor/es:
  • 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
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: JCSD2011: XIX Jornadas de Concurrencia y Sistemas Distribuidos
Fechas del Evento: 08/06/2011 - 10/06/2011
Lugar del Evento: La Granja de San Ildefonso, Segovia
Título del Libro: JCSD2011: XIX Jornadas de Concurrencia y Sistemas Distribuidos
Fecha: 2011
Materias:
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Informática Aplicada [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (3MB) | Vista Previa

Resumen

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).

Más información

ID de Registro: 19263
Identificador DC: http://oa.upm.es/19263/
Identificador OAI: oai:oa.upm.es:19263
URL Oficial: 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
Depositado por: Memoria Investigacion
Depositado el: 25 Mar 2014 12:15
Ultima Modificación: 21 Abr 2016 17:31
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM