Enrutamiento de mundo pequeño - Small-world routing

En la teoría de redes , el enrutamiento de mundo pequeño se refiere a métodos de enrutamiento para redes de mundo pequeño . Las redes de este tipo son peculiares porque existen caminos relativamente cortos entre dos nodos cualesquiera. Sin embargo, determinar estas rutas puede ser un problema difícil desde la perspectiva de un nodo de enrutamiento individual en la red si no se conoce más información sobre la red en su conjunto.

Enrutamiento codicioso

Casi todas las soluciones al problema del enrutamiento en un mundo pequeño implican la aplicación de enrutamiento codicioso . Este tipo de enrutamiento depende de un punto de referencia relativo mediante el cual cualquier nodo en la ruta puede elegir el siguiente nodo que cree que está más cerca del destino. Es decir, debe haber algo por lo que ser codicioso. Por ejemplo, esto podría ser la ubicación geográfica, la dirección IP, etc. En el caso del experimento original de Milgram sobre un mundo pequeño , los participantes conocían la ubicación y ocupación del destinatario final y, por lo tanto, podían reenviar mensajes basados ​​en esos parámetros.

Construyendo una base de referencia

El enrutamiento codicioso no funcionará fácilmente cuando no hay una base de referencia obvia. Esto puede ocurrir, por ejemplo, en redes superpuestas donde la información sobre la ubicación del destino en la red subyacente no está disponible. Las redes de amigo a amigo son un ejemplo particular de este problema. En tales redes, la confianza está garantizada por el hecho de que solo conoce la información subyacente sobre los nodos con los que ya es vecino.

Una solución en este caso es imponer algún tipo de direccionamiento artificial en los nodos de tal manera que este direccionamiento pueda ser utilizado eficazmente por métodos de enrutamiento codiciosos. Un artículo de 2005 de un desarrollador del Proyecto Freenet analiza cómo se puede lograr esto en redes de amigos . Dado el supuesto de que estas redes exhiben propiedades de mundo pequeño, a menudo como resultado de relaciones del mundo real o de conocidos, debería ser posible recuperar un gráfico de mundo pequeño integrado de Kleinberg . Esto se logra seleccionando pares aleatorios de nodos y potencialmente intercambiándolos basándose en una función objetivo que minimiza el producto de todas las distancias entre cualquier nodo dado y sus vecinos.

Un problema importante relacionado con esta solución es la posibilidad de mínimos locales . Esto puede ocurrir si los nodos se encuentran en una situación que es óptima solo considerando un vecindario local, mientras se ignora la posibilidad de una optimización más alta resultante de intercambios con nodos distantes. En el artículo anterior, los autores propusieron un método de recocido simulado en el que se realizaron intercambios menos que óptimos con una pequeña probabilidad. Esta probabilidad era proporcional al valor de realizar los cambios. Otro posible método de optimización metaheurística es una búsqueda tabú , que agrega memoria a la decisión de intercambio. En su forma más simplista, se recuerda un historial limitado de intercambios anteriores para que se excluyan de la lista de posibles nodos de intercambio.

Este método para construir una base de referencia también se puede adaptar a configuraciones distribuidas, donde las decisiones solo se pueden tomar a nivel de nodos individuales que no tienen conocimiento de la red en general. Resulta que la única modificación necesaria está en el método para seleccionar pares de nodos aleatorios. En un entorno distribuido, esto se hace haciendo que cada nodo envíe periódicamente un caminante aleatorio que termina en un nodo para ser considerado para el intercambio.

El modelo de Kleinberg

El modelo de Kleinberg de una red es eficaz para demostrar la eficacia del enrutamiento codicioso de pequeños mundos. El modelo utiliza una cuadrícula de nxn de nodos para representar una red, donde cada nodo está conectado con un borde no dirigido a sus vecinos. Para darle el efecto de "mundo pequeño", se agregan a la red una serie de bordes de largo alcance que tienden a favorecer los nodos más cercanos en la distancia que más lejos. Al agregar aristas, la probabilidad de conectar algún vértice aleatorio a otro vértice aleatorio w es proporcional a , donde es el exponente de agrupamiento. ${\ Displaystyle v}$${\ Displaystyle 1 / d (v, w) ^ {q}}$${\ Displaystyle q}$

Enrutamiento codicioso en el modelo de Kleinberg

Es fácil ver que un algoritmo codicioso , sin usar los bordes de largo alcance, puede navegar desde vértices aleatorios en la cuadrícula en el tiempo. Siguiendo las conexiones garantizadas con nuestros vecinos, podemos mover una unidad a la vez en la dirección de nuestro destino. Este también es el caso cuando el componente de agrupamiento es grande y los bordes de "largo alcance" terminan quedándose muy cerca; simplemente no aprovechamos los lazos más débiles en este modelo. Cuando , los bordes de largo alcance están uniformemente conectados al azar, lo que significa que los bordes de largo alcance son "demasiado aleatorios" para usarse de manera eficiente para la búsqueda descentralizada. Kleinberg ha demostrado que el coeficiente de agrupamiento óptimo para este modelo es , o una distribución al cuadrado inverso. ${\ Displaystyle v-> w}$${\ Displaystyle O (n)}$${\ Displaystyle q}$${\ Displaystyle q = 0}$${\ Displaystyle q = 2}$

Para razonar por qué este es el caso, si se dibuja un círculo de radio r alrededor del nodo inicial, tendrá densidad nodal donde n es el número de nodos en el área circular. A medida que este círculo se expande más hacia afuera, el número de nodos en el área dada aumenta proporcionalmente a medida que la probabilidad de tener un enlace aleatorio con cualquier nodo permanece proporcional , lo que significa que la probabilidad de que el nodo original tenga un lazo débil con cualquier nodo a una distancia dada distancia es efectivamente independiente de la distancia. Por lo tanto, se concluye que con los bordes de largo alcance se distribuyen uniformemente en todas las distancias, lo que es efectivo para permitirnos canalizar hacia nuestro destino final. ${\ Displaystyle n / (\ pi r ^ {2})}$${\ Displaystyle r ^ {2}}$${\ Displaystyle 1 / r ^ {2}}$${\ Displaystyle q = 2}$

Algunos sistemas peer-to-peer estructurados basados ​​en DHT a menudo están implementando variantes de la topología Small-World de Kleinberg para permitir un enrutamiento eficiente dentro de la red Peer-to-Peer con grados de nodo limitados.

Ver también

• Red  social: estructura social compuesta por un conjunto de actores sociales
• Red de mundo pequeño  : gráfico matemático en el que se puede llegar a la mayoría de los nodos con una pequeña cantidad de pasos
• Modelo Watts-Strogatz

Referencias