In Search of Simplicity: Self-Organizing Multi-Source Multicast Overlay

Para empezar mi participación en el blog os comentaré brevemente el artículo que leí, comprendí (con ciertas salvedades :-D) y conté a los asistentes a la reunión del dia 9/03/2007.

Dejo el título en inglés, así como algunos términos usados en dicho artículo porque su traducción en muchos casos suena peor que el término anglosajón. ;)

Link al artículo: http://arxiv.org/abs/cs.DC/0702157

Título: In Search of Simplicity: Self-Organizing Multi-Source Multicast Overlay

Autores: M. Ripeanu, I. Foster, A. Iamnitchi, A. Rogers

Abstract: Multicast communication primitives have broad utility as building blocks for distributed applications. The challenge is to create and maintain the distributed structures that support these primitives while accounting for volatile end-nodes and variable network characteristics. Most solutions proposed to date rely on complex algorithms or global information, thus limiting the scale of deployments and acceptance outside the academic realm.
This article introduces a low-complexity, self-organizing solution for maintaining multicast trees, that we refer to as UMM (Unstructured Multi-source Multicast). UMM uses traditional distributed systems techniques: layering, soft-state, and passive data collection to adapt to the dynamics of the physical network and maintain data dissemination trees. The result is a simple, adaptive system with lower overheads than more complex alternatives. We have implemented UMM and evaluated it on a 100-node PlanetLab testbed and on up to 1024-node emulated ModelNet networks Extensive experimental evaluations demonstrate UMM’s low overhead, efficient network usage compared to alternative solutions, and ability to quickly adapt to network changes and to recover from failures.

Temas Relacionados: Sistemas distribuidos (distributed systems), Autoorganización (Self-Organizing), Redes de recubrimiento (overlay networks), multicast.

RESUMEN:

En el artículo se presenta un nuevo modelo de sistema distribuido para hacer multicast desde muchas fuentes (multisource), basado en una red overlay, cuyos nodos son capaces de tomar ‘decisiones’ basándose únicamente en información a nivel local (no necesitan conocer datos de toda la red). Dichas ‘decisiones’ repercuten en una autoorganización del sistema a nivel global y lo dotan de varias propiedades muy importantes.

El sistema descrito es el llamado UMM (Unstructured Multisource Multicast), el cual, como su nombre indica, tiene una topología no estructurada a nivel de red overlay. Entre sus propiedades se encuentran (aparte de la autoorganización):

  • baja complejidad: los datos a nivel de nodo son soft-state (se actualizan cada cierto tiempo)
  • escalable: es independiente del número de nodos, dado que cada nodo se ‘autogestiona’
  • robusto: se recupera rápidamente de errores y se adapta rápidamente y de forma transparente a cambios en la red
  • adaptativo: al tipo de nodo y a su ‘potencia’ o posibilidades

Además, UMM utiliza árboles de distribución o diseminación (distribution/dissemination trees) para gestionar las conexiones entre nodos. Dichos árboles han demostrado ser muy eficientes a la par que fáciles de construir.

La estructura del sistema consta de 3 capas:

Arquitectura UMM

  • Capa Física: corresponde a las conexiones físicas entre los nodos de la red (equipos reales sobre internet).
  • Capa Base (overlay): conjunto de ‘túneles lógicos’ (tunnels).
  • Árboles de Distribución: hay uno por cada nodo fuente y considera únicamente los túneles necesarios para conectar con cualquiera de los demás nodos de la red.

La construcción de las 2 capas superiores de UMM se hace:

  • Capa Base: es inicialmente aleatoria y se optimiza incrementalmente (en varias iteraciones). Cada nodo tiene asociado un número fijo de túneles cortos (consideran la latencia) y túneles largos (consideran el ancho de banda), que depende de la ‘potencia’ de dicho nodo y de sus conexiones (el sistema se adapta a las posibilidades de los nodos heterogéneos). Para mejorar las conexiones de cada nodo, se elige otro nodo al azar y se considera la latencia y ancho de banda del túnel que los conecta. Si la latencia es menor que la del peor túnel corto del nodo en cuestión, se sustituye por éste. Si el ancho de banda asociado al túnel es mayor que el del peor túnel largo, se hace esta sustitución.
  • Capa de Árboles de Distribución: para cada nodo se construye un árbol que discrimina los túneles innecesarios de la Capa Base (filtros). Para ésto se considera el conjunto de todos los túneles posibles entre el nodo del que construimos el árbol y los demás. Para determinar si un tunel es innecesario (supérfluo), se lanza un mensaje desde el nodo elegido a todos los que tenga conectados (mediante flooding (inundación)). En ellos también se hace flooding del mensaje a los que tengan conectados (excepto áquel desde el que les llegó el mensaje), y así sucesivamente. Los túneles por los que pase más de una vez el mensaje, será innecesarios y se creará una regla en el árbol de distribución del nodo inicial que hará que dicho túnel no sea considerado para mensajes con ese nodo como fuente. Estos árboles se crean una vez al principio y se recalculan si cambia algo en la red y además cada cierto tiempo (normalmente 10 minutos).

En cuanto al funcionamiento del sistema a nivel de nodo, se tienen en cuenta varios factores:

  • Errores en nodos y túneles: para detectar errores, cada nodo envía mensajes a los demás indicando que sigue activo (alive). Si un nodo no recibe este mensaje por parte de alguno de los que tiene conectados (tras cierto tiempo), lanza un mensaje a sus nodos cercanos mediante flooding con un tiempo de vida corto (time-to-live), para que recalculen los filtros de sus árboles de distribución que incluyan al nodo caido.
  • Mantenimiento de conexión de la red base: existe un nodo especial en la red que manda un mensaje cada cierto tiempo llamado latido (heartbeat). Si un nodo cualquiera no recibe dicho mensaje, concluirá que no está conectado a la red e intentará unirse de nuevo. Para ello dispone de una lista de nodos ‘cercanos’ (la cual se pasan entre ellos al establecer los túneles) a los que intentará unirse. en cualquier caso también existe un nodo raiz (bootstrap) que todos conocen en la red y al que se unirán en caso de no poder hacerlo con otro.

En los experimentos se ha probado el sistema en el simulador ModelNet y se ha comparado con otros sistema overlay con diferentes topologías (estructurados, árbol) y siguiendo diferentes metodologías (Narada, DHT), obteniendo unos resultados muy satisfactorios, mejorando en la gran mayoría de casos a los demás sistemas y mostrando un buen comportamiento en los casos en que no mejora (buen resultado también si tenemos en cuenta la sencillez y demás ventajas del modelo UMM).

En lo referente a experimentos realizados sobre una red real (hechos sobre la WAN PlanetLab), el sistema también ha obtenido resultados satisfactorios.

Por tanto UMM se muestra como un sistema bastante sencillo en general, y cuyos nodos actúan considerando información a nivel local obteniendo una autoorganización del sistema a nivel global. Debido a este factor, ofrece numerosas ventajas y cumple muchos de los requisitos de una buena red overlay como son: escalabilidad, aguante (resilence), tolerancia a fallos y cambios en la red y uso eficiente de los recursos (garantizando una penalización por retardo relativo (relative delay penalty) y una sobrecarga de enlaces de red (network stress) bajos).

Aquí finaliza el resumencillo, para ver más detalles os insto a leer el artículo en el enlace que os pongo al principio.

¡Queda oficialmente inaugurado el blog de Geneura con contenido ‘serio’ (:-D)!

Saludos.

2 thoughts on “In Search of Simplicity: Self-Organizing Multi-Source Multicast Overlay

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s