ExOR

El enrutamiento extremadamente oportunista (ExOR) es una combinación de protocolo de enrutamiento y control de acceso al medio para una red inalámbrica ad hoc , inventado por Sanjit Biswas y Robert Morris del Laboratorio de Inteligencia Artificial del MIT , y descrito en un artículo de 2005. ^{[ 1 ]}

Las estrategias de transmisión y retransmisión utilizadas por el algoritmo ya se describieron en la literatura. ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]} ExOR es valioso porque puede operar radios digitales disponibles para usar algunas optimizaciones algorítmicas previamente impracticables.

Anteriormente de código abierto, ^{[ 8 ]} ExOR estuvo disponible en 2005 pero ya no se puede obtener.

El algoritmo está diseñado para transmitir paquetes del Protocolo de Internet , lo que permite el máximo número de servicios adicionales. En el momento de su invención, las radios digitales habían reemplazado en gran medida los servicios de internet por cable para dispositivos portátiles. Los circuitos integrados especializados estaban ampliamente disponibles a bajo costo.

En aquel entonces (2005), el MIT participaba en el proyecto «Un portátil por niño» , un intento de crear un ordenador económico y de bajo consumo para ayudar a educar a niños de escasos recursos. Se creía que las ventajas radicaban en la reducción de costes para las copias digitales de libros y consumibles como el papel, con posibles mejoras pedagógicas gracias a la interactividad y la flexibilidad. Una de las características cruciales del portátil sería una red inalámbrica ad hoc que permitiría a los portátiles cooperar para proporcionar más recursos de los que un ordenador individual podría ofrecer. Un algoritmo de red práctico y superior ayudaría directamente a educar a más niños al reducir el coste y el consumo energético del portátil. Una red inalámbrica ad hoc costaría menos y consumiría menos energía si utilizara radios estándar (es decir, con circuitos integrados para 802.11 ) y transfiriera más datos a mayores distancias, con menos radios intermedias.

Este protocolo se probó como prototipo en RoofNet .

La radio de origen emite un lote de paquetes. A medida que expiran los temporizadores de las radios intermedias, las radios más alejadas del destino retransmiten los paquetes que ninguna radio más cercana ha retransmitido todavía.

La mayor parte de la complejidad reside en dar soporte a este esquema básico. Los temporizadores de las radios intermedias se configuran con una estimación del tiempo de transmisión que las radios más cercanas necesitarán para transmitir los paquetes. Esta estimación se calcula en función del número de paquetes del lote y de la probabilidad de una transmisión correcta desde cada radio intermedia.

ExOR utiliza un protocolo de enrutamiento convencional, "RRTc", para recopilar información sobre la probabilidad de una transmisión exitosa entre cada par de radios digitales en la red.

A los autores les preocupaba que la retransmisión de paquetes consumiera demasiado tiempo de radio disponible. Por lo tanto, ExOR intenta reducir las retransmisiones de paquetes al mínimo posible. Esto explica la alta eficiencia de ExOR.

Primero, a partir de la información de enrutamiento, la radio emisora ​​crea una lista de radios que podrían reenviar datos desde la radio emisora ​​al destino. Los números de las radios se colocan en una lista ordenada por distancia al destino, de la más cercana a la más lejana. La radio de destino se encuentra al principio de la lista. Además, la radio de origen inicia una lista de los paquetes del lote para medir su progreso. Este "mapa de lotes" es una matriz de números de radio, uno por paquete. Cada número de radio corresponde a la radio que transmitió ese paquete y que estaba más cerca de la radio de destino. Cada paquete de datos contiene la lista de radios y los paquetes se colocan al principio. La lista ahorra espacio en cada paquete al usar números de radio en lugar de direcciones IP. Luego, la radio emisora ​​transmite el primer lote de paquetes de datos. Se inicia un temporizador. Las radios que reciben un paquete pero no están en la lista del paquete ignoran los paquetes de datos. Estas radios descartan los paquetes tan pronto como los reciben. Las radios que están en la lista de radios del paquete guardan los paquetes de datos que reciben. También actualizan su mapa de lotes. Cuando una radio agota su tiempo de espera, transmite los paquetes que ninguna radio más cercana al destino ha retransmitido. Estos paquetes incluyen la mejor información disponible de la radio sobre el progreso de los paquetes en el lote (es decir, su mapa de lotes). En particular, el mapa de lotes de cada paquete contiene el número de radio del retransmisor para cada paquete que retransmite. Cuando una radio recibe un paquete enviado por una radio más cercana al destino, borra su propia copia de ese paquete. No es necesario que lo retransmita. Sin embargo, también actualiza su mapa de lotes sobre el progreso de los paquetes en el lote. De esta manera, la información sobre el progreso de los paquetes fluye hacia atrás, hacia la fuente, a medida que las radios más alejadas del destino actualizan sus mapas de lotes interceptando las retransmisiones.

Dado que las retransmisiones más cercanas a la radio de origen se producen más tarde, la información de progreso de los paquetes fluye de vuelta a la radio de origen, aunque nunca se transmitan paquetes de confirmación. Al final, suelen quedar algunos paquetes que no llegaron a su destino. Estos se envían por la ruta más fiable, evitando así las rutas poco fiables.

ExOR es más eficiente con grandes bloques de datos. Esto aumenta las posibilidades de que un lote encuentre rutas alternativas. Sin embargo, los mapas de lotes también se hacen más grandes. Por lo tanto, los bloques de datos de más de 100 000 bytes se dividen en grupos de paquetes de datos llamados lotes. Los mensajes más pequeños se envían simplemente por la ruta más fiable. Dado que el protocolo principal de internet, TCP, envía un flujo de datos, ExOR utiliza servidores proxy locales para acumular los bloques de datos.

Cada paquete se retransmite un número mínimo de veces y cubre la mayor distancia posible en cada transmisión. Se pierde algo de tiempo al tener el receptor difundiendo información de paquetes, pero esto es mucho menos que en los esquemas de enrutamiento normales, que pueden retransmitir cuando se pierde un mensaje de confirmación. No hay paquetes de confirmación ni colisiones con ellos. Esto ahorra tiempo de radio. Los autores afirman que el protocolo es aproximadamente el doble de eficiente que los protocolos de enrutamiento normales con enrutamiento "óptimo" fijo. Dicen que la variación en los tiempos de entrega es 1/4 de otras redes ad hoc y lo atribuyen al uso que hace el algoritmo de los mejores tiempos de entrega disponibles. Diseñaron la prueba de manera que el protocolo acumulara grandes bloques de datos para la transmisión. Los datos muestran una compensación entre la velocidad de respuesta de la red y la eficiencia del sistema de radio. El tiempo de respuesta en algunos juegos podría verse afectado por mayores cantidades de almacenamiento en búfer en redes de alta eficiencia.

Las estimaciones de eficiencia de ExOR se basan en una implementación real con un kit de herramientas de enrutamiento de Linux llamado click. Se simularon e instalaron versiones experimentales del software en una red de azotea llamada "RoofNet" en Cambridge, Massachusetts. Estos datos se compararon con datos publicados para una red similar. ^{[ 9 ]}

Un esquema de enrutamiento oportunista muy similar también fue propuesto de forma independiente por Zhenzhen Ye y Yingbo Hua de la Universidad de California, Riverside , y presentado en un artículo en 2005. ^{[ 10 ]}

• AODV – Protocolo de enrutamiento inalámbrico. Páginas que muestran breves descripciones de los destinos de redirección. 
• Enrutamiento por contrapresión : algoritmo en la teoría de colas. 
• Enrutamiento de origen dinámico : protocolo de enrutamiento para redes malladas inalámbricas. 
• Protocolo de enrutamiento de estado de enlace con visión difusa : algoritmo de enrutamiento de redes inalámbricas 
• Lista de protocolos de enrutamiento ad hoc
• OLSR – Protocolo de enrutamiento IP optimizado para redes móviles ad hoc. Páginas que muestran breves descripciones de los destinos de redireccionamiento.