Enrutamiento de mundo pequeño

En teoría de redes , el enrutamiento de mundo pequeño se refiere a los métodos de enrutamiento para redes de mundo pequeño . Este tipo de redes se caracteriza por la existencia de caminos relativamente cortos entre cualquier par de nodos. Sin embargo, determinar estos caminos puede ser un problema complejo desde la perspectiva de un nodo de enrutamiento individual si no se dispone de información adicional sobre la red en su conjunto.

Casi todas las soluciones al problema del enrutamiento en mundos pequeños implican la aplicación del enrutamiento voraz . 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 más cercano al destino. Es decir, debe haber algo que motive la búsqueda voraz. Por ejemplo, podría ser la ubicación geográfica, la dirección IP , etc. En el caso del experimento original de Milgram sobre mundos pequeños , los participantes conocían la ubicación y la ocupación del destinatario final y, por lo tanto, podían reenviar mensajes basándose en esos parámetros.

El enrutamiento voraz no funciona fácilmente cuando no hay una base de referencia obvia. Esto puede ocurrir, por ejemplo, en redes superpuestas donde no se dispone de información sobre la ubicación del destino en la red subyacente. Las redes amigo-amigo son un ejemplo particular de este problema. En dichas redes, la confianza se garantiza por el hecho de que solo se conoce información subyacente sobre los nodos con los que ya se tiene una relación de vecindad.

Una solución en este caso consiste en imponer algún tipo de direccionamiento artificial a los nodos, de manera que este pueda ser utilizado eficazmente por métodos de enrutamiento voraces. Un artículo de 2005 de un desarrollador del Proyecto Freenet analiza cómo lograr esto en redes de amigos a amigos . Partiendo de la premisa 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 grafo de mundo pequeño de Kleinberg incrustado . Esto se logra seleccionando pares aleatorios de nodos y, potencialmente, intercambiándolos en función de 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 óptima considerando únicamente un vecindario local, ignorando la posibilidad de una mayor optimalidad resultante de intercambios con nodos distantes. En el artículo mencionado, los autores propusieron un método de recocido simulado donde los intercambios subóptimos se realizaban con una pequeña probabilidad. Esta probabilidad era proporcional al valor de realizar los intercambios. Otro posible método de optimización metaheurística es la búsqueda tabú , que añade una memoria a la decisión de intercambio. En su forma más simple, se recuerda un historial limitado de intercambios pasados ​​para que se excluyan de la lista de posibles nodos de intercambio.

Este método para construir una base de referencia también puede adaptarse a entornos distribuidos, donde las decisiones solo se toman a nivel de nodos individuales que desconocen la red en su conjunto. Resulta que la única modificación necesaria reside en el método de selección de pares de nodos aleatorios. En un entorno distribuido, esto se logra mediante el envío periódico de un caminante aleatorio que finaliza en un nodo que se considera para el intercambio.

El modelo de Kleinberg de una red es eficaz para demostrar la eficacia del enrutamiento voraz de mundo pequeño. El modelo utiliza una cuadrícula de n x n nodos para representar una red, donde cada nodo está conectado con una arista no dirigida a sus vecinos. Para darle el efecto de "mundo pequeño", se agregan a la red varias aristas de largo alcance que tienden a favorecer a los nodos más cercanos en distancia en lugar de los más lejanos. Al agregar aristas, la probabilidad de conectar algún vértice aleatorio${\displaystyle v}$a otro vértice aleatorio w es proporcional a${\displaystyle 1/d(v,w)^{q}}$, dónde${\displaystyle q}$es el exponente de agrupamiento. ^{[ 1 ]}

• Red social – Estructura social compuesta por un conjunto de actores sociales. 
• Red de mundo pequeño : grafo donde la mayoría de los nodos son alcanzables en un número reducido de pasos. 
• Modelo de Watts-Strogatz : método para generar grafos de mundo pequeño aleatorios. Páginas que muestran descripciones breves de destinos de redireccionamiento.