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 . Las redes de este tipo son peculiares porque existen rutas relativamente cortas 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.
Casi todas las soluciones al problema del enrutamiento en un mundo pequeño implican la aplicación de un enrutamiento codicioso . Este tipo de enrutamiento depende de un punto de referencia relativo por el cual cualquier nodo en la ruta puede elegir el siguiente nodo que crea 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 mundo pequeño de Milgram , los participantes conocían la ubicación y la ocupación del destinatario final y, por lo tanto, podían reenviar mensajes en función de esos parámetros. [ cita requerida ]
El enrutamiento voraz no funcionará fácilmente cuando no exista 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 de amigos son un ejemplo particular de este problema. En dichas redes, la confianza está garantizada por el hecho de que solo se conoce la información subyacente sobre los nodos con los que ya se es vecino. [ cita requerida ]
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 efectivamente por métodos de enrutamiento codiciosos. Un artículo de 2005 escrito por un desarrollador del Proyecto Freenet analiza cómo se puede lograr esto en redes de amigo a amigo . 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 de Kleinberg incorporado . Esto se logra seleccionando pares aleatorios de nodos y potencialmente intercambiándolos en función de una función objetivo que minimice el producto de todas las distancias entre cualquier nodo dado y sus vecinos. [ cita requerida ]
Un problema importante relacionado con esta solución es la posibilidad de mínimos locales . Esto puede ocurrir si los nodos están en una situación que es óptima considerando solo un vecindario local, mientras que se ignora la posibilidad de una mayor optimalidad resultante de intercambios con nodos distantes. En el artículo anterior, los autores propusieron un método de recocido simulado donde 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 una memoria a la decisión de intercambio. En su forma más simplista, se recuerda un historial limitado de intercambios pasados para que se excluyan de la lista de posibles nodos de intercambio. [ cita requerida ]
Este método para construir una base de referencia también se puede adaptar a entornos distribuidos, donde las decisiones solo se pueden tomar a nivel de nodos individuales que no tienen conocimiento de la red en su conjunto. 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 termine en un nodo que se va a considerar para el intercambio. [ cita requerida ]
El modelo de red de Kleinberg es eficaz para demostrar la eficacia del enrutamiento voraz en mundos pequeños. El modelo utiliza una cuadrícula de nxn 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 a los nodos más cercanos en distancia en lugar de los más lejanos. Al agregar bordes, la probabilidad de conectar un vértice aleatorio con otro vértice aleatorio w es proporcional a , donde es el exponente de agrupamiento. [1]
Es fácil ver que un algoritmo voraz , sin utilizar los bordes de largo alcance, puede navegar desde vértices aleatorios en la cuadrícula en el tiempo. Al seguir las conexiones garantizadas a nuestros vecinos, podemos movernos 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 manteniéndose muy cerca; simplemente no aprovechamos los lazos más débiles en este modelo. Cuando , los bordes de largo alcance están conectados uniformemente al azar, lo que significa que los bordes de largo alcance son "demasiado aleatorios" para ser utilizados 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 cuadrada inversa. [2]
Para explicar por qué esto es así, si se dibuja un círculo de radio r alrededor del nodo inicial, tendrá una densidad nodal donde n es el número de nodos en el área circular. A medida que este círculo se expande más, el número de nodos en el área dada aumenta proporcionalmente a ya que la probabilidad de tener un vínculo aleatorio con cualquier nodo sigue siendo proporcional a , lo que significa que la probabilidad de que el nodo original tenga un vínculo débil con cualquier nodo a una distancia dada 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 eficaz para permitirnos llegar a nuestro destino final. [ cita requerida ]
Algunos sistemas Peer-to-peer estructurados basados en DHT a menudo implementan variantes de la topología Small-World de Kleinberg para permitir un enrutamiento eficiente dentro de una red Peer-to-peer con grados de nodos limitados. [3]
