Procedimiento y nodo de red para establecer una ruta sin bucles en una red ad-hoc reactiva.

Procedimiento para establecer una ruta que une un nodo inicial (Q) con un nodo de destino en una red reactiva,

con las etapas:

a) el nodo inicial inunda la red mediante el procedimiento de broadcast (difusión general) con mensajes desolicitud, RREQ, en los que se incluye al menos una estructura de memoria de datos para coeficientes decaracterísticas de calidad del servicio, a excepción de una magnitud de correlación que describe unacorrelación de distancias entre la ruta de red recorrida por el correspondiente mensaje de solicitud y una rutade referencia en la red;

b) un nodo de red que procesa un mensaje de solicitud actualiza los coeficientes contenidos en el mensaje desolicitud;

c) cada nodo de red (I) distinto del nodo de destino (Z) memoriza transitoriamente un mensaje de solicitudrecibido durante un primer tiempo de recorrido, T1, y durante un segundo tiempo de recorrido, T2, que acabadespués del primer tiempo de recorrido, en el caso de que una valoración de los coeficientes del mensaje desolicitud recibido mediante una regla de valoración dé como resultado que al menos un coeficiente delmensaje de solicitud recibido es mejor que el correspondiente coeficiente de cada mensaje de solicitud yamemorizado transitoriamente, no memorizándose transitoriamente este mensaje de solicitud en el caso deque todos los coeficientes del mensaje de solicitud recibido no sean mejores en cada caso que loscoeficientes de al menos un mensaje de solicitud ya memorizado transitoriamente;

d) cada nodo de red (I) distinto del nodo de destino (Z) aplica a los coeficientes de las características de calidaddel servicio de cada mensaje de solicitud memorizado transitoriamente una primera función de valoraciónpara la valoración ponderada de coeficientes para características de calidad del servicio, con lo que seobtiene para cada mensaje de solicitud un primer resultado de valoración;

e) cada nodo de red (I) distinto del nodo de destino (Z) elige de entre los mensajes de solicitud memorizadostransitoriamente durante el primer tiempo de recorrido un mensaje de solicitud según una primera regla devaloración para los primeros resultados de valoración, enviándose el mismo con sus coeficientesactualizados mediante el procedimiento de broadcast a los nodos contiguos;

f) el nodo de destino (Z) memoriza transitoriamente los mensajes de solicitud recibidos durante un tercertiempo de recorrido, T3, aplica a los coeficientes de las características de calidad del servicio de losmensajes de solicitud memorizados transitoriamente en cada caso una segunda función de valoración parala valoración ponderada de coeficientes para características de calidad del servicio, con lo que para cadamensaje de solicitud memorizado transitoriamente se obtiene un segundo resultado de valoración, elige trastranscurrir el tercer tiempo de recorrido al menos un mensaje de solicitud según una segunda regla deelección para los segundos resultados de valoración y envía un mensaje de respuesta, RREP, a un nodo dered contiguo en la dirección de retorno según la ruta de red recorrida por el mensaje de solicitud elegido;

g) cada nodo de red que recibe el mensaje de respuesta, RREP, comprueba si un mensaje de solicitudmemorizado transitoriamente durante el segundo tiempo de recorrido tiene según la primera regla deelección un mejor resultado de valoración que el mensaje de solicitud enviado una vez transcurrido el primertiempo de recorrido, retransmitiendo el mismo el mensaje de respuesta en dirección de retorno a lo largo dela ruta de red del mensaje de solicitud elegido por el nodo de destino al siguiente nodo de red, en el caso deque en el nodo de red no exista ningún mensaje de solicitud de mejor valoración, y retransmite el mensajede respuesta en la dirección de retorno a lo largo de la ruta de red recorrida por el mensaje de solicitudmejor valorado al siguiente nodo de red, en el caso de que en el nodo de red no exista un mensaje desolicitud de mejor valoración.

Procedimiento y nodo de red para establecer una ruta sin bucles en una red ad-hoc reactiva.

La invención se situa en el sector de la técnica de redes y se refiere a un procedimiento y un nodo de red para establecer una ruta sin bucles en una red ad-hoc reactiva.

Las redes posibilitan la transmisión de información entre nodos de red conectados entre sí mediante técnica de datos. Para aprovechar en redes con conmutación por paquetes las ventajas de una transmisión de datos orientada al enlace, se conoce la utilización de los llamados procedimientos reactivos de transmisión de datos, en los que se establece dinámicamente una vía en la red (ruta) punto-a-punto para la transmisión de información, que desaparece de nuevo una vez realizada la transmisión de la información.

Las redes ad-hoc inalámbricas modernas (redes multi-salto) posibilitan una transmisión de datos entre nodos de red sin una infraestructura central. En tales redes se configura especialmente difícil la determinación de rutas óptimas, debido a que las condiciones de red varían típicamente de forma dinámica. En la práctica se ha comprobado que los procedimientos reactivos de enrutamiento (on-demand, sobre demanda) son muy adecuados para esta tarea.

Los procedimientos reactivos de enrutamiento ejecutan típicamente un proceso de dos etapas para encontrar una ruta entre un nodo inicial y un nodo de destino. En una primera etapa se busca una ruta en sentido "hacia delante" hacia el nodo de destino, inundándose la red con una solicitud de ruta (RREQs = Route Request) generada por el nodo inicial mediante el procedimiento de broadcast (difusión general) . Cada nodo de red que recibe una tal solicitud de ruta memoriza la dirección del nodo contiguo del que ha recibido la solicitud de ruta. Tan pronto como el nodo de destino recibe por primera vez una solicitud de ruta, genera el mismo un mensaje de respuesta (RREP = Route Reply) , que en una segunda etapa del proceso se transmite mediante el procedimiento de unicast (monodifusión) en la dirección de retorno a lo largo de la ruta de red antes recorrida por el mensaje de solicitud, con lo que se establece la ruta en la red.

Los procedimientos de enrutamiento reactivos utilizados hasta ahora, como AODV (AODV = Ad-hoc On-Demand Distance Vector, vector de distancia ad-hoc bajo demanda) y DSDV (Destination-Sequenced Distance Vector, destino secuenciado vector distancia) siguen la regla de que cada nodo de red sólo retransmite a sus nodos contiguos el mensaje de solicitud recibido en cada caso como primero mediante el procedimiento de broadcast. Los mensajes de solicitud que llegan posteriormente ya no son considerados. De esta manera puede garantizarse que cada nodo de red sólo está incluido una vez en una misma ruta entre los nodos inicial y de destino. Mediante la utilización de números de secuencia de destino puede determinarse la llamada “frescura” de una ruta.

En un procedimiento de enrutamiento reactivo no publicado hasta ahora de la entidad solicitante, se tienen en cuenta características de la calidad del servicio de enlaces de datos punto-a-punto entre nodos de red contiguos para la búsqueda y establecimiento de una ruta punto-a-punto entre los nodos inicial y de destino. Para este fin se memorizan en los mensajes de solicitud coeficientes para las características de la calidad del servicio, con lo que el nodo de destino puede determinar una ruta en base a las características de calidad del servicio memorizadas para los mensajes de solicitud.

Para optimizar este procedimiento para encontrar rutas, es ventajoso que cada nodo de red memorice transitoriamente los mensajes de solicitud que le llegan durante un primer tiempo de recorrido, aplique a los coeficientes relativos a las características de calidad de los mensajes de solicitud memorizados transitoriamente una función de evaluación y elija, según una regla de elección que puede elegirse para los resultados de la valoración entonces obtenidos, un mensaje de solicitud que sea el mejor evaluado para la retransmisión mediante el procedimiento de broadcast. Es especialmente ventajoso que un nodo de red también incluso durante un segundo tiempo de recorrido que termina tras el primer tiempo de recorrido memorice transitoriamente mensajes de solicitud en el nodo de red. En este caso pueden también tenerse en cuenta los mensajes de solicitud memorizados transitoriamente tras finalizar el primer tiempo de recorrido para una retransmisión del mensaje de respuesta, con lo que el mensaje de respuesta dado el caso se conduce hacia el nodo inicial por una ruta de red más favorable, en el caso de que tras enviar el mensaje de solicitud haya recibido el nodo de red un mensaje de solicitud valorado como mejor.

No obstante, puede presentarse el problema de que un mensaje de solicitud retransmitido por el nodo de red llegue por segunda vez al nodo de red y con ello retorne sobre una ruta de bucle hacia el nodo de red. El nodo de red no puede detectar sin más la formación del bucle, ya que no está contenida la ruta de red recorrida en un mensaje de solicitud. Cuando el nodo de red recibe en este caso un mensaje de respuesta del nodo de destino y en el caso de que un mensaje de solicitud que retorne sobre una ruta de bucle al nodo de destino se valore como mejor que el mensaje de solicitud enviado, se presenta la indeseada situación de que el mensaje de respuesta se retransmite sobre la ruta de bucle y el mensaje de respuesta circule allí hasta que transcurra el tiempo de validez del mensaje de respuesta.

La solicitud de patente internacional de publicación posterior WO 2009/013201 A1 describe un procedimiento para establecer una ruta en una red en el que un nodo inicial inunda la red mediante el procedimiento de broadcast con mensajes de solicitud, en los que se incluyen características de calidad del servicio que contienen al menos una magnitud de correlación que describe una correlación de distancia de las rutas de red recorridas por los mensajes de solicitud respecto una ruta de referencia en la red.

Otros planteamientos se describen en los documentos EP1 564938 y WO 2007/055689.

Por el contrario consiste la tarea de la presente invención en proporcionar un procedimiento para establecer una ruta libre de bucles en una red ad-hoc reactiva con el que se evite el problema de una posible formación de bucles como consecuencia de una memorización transitoria de mensajes de solicitud.

Esta tarea se resuelve según la propuesta de la invención mediante un procedimiento y un nodo de red para establecer una ruta libre de bucles en una red ad-hoc reactiva con las características de las reivindicaciones independientes. Ventajosas configuraciones mejoradas de la invención se indican mediante las características de las reivindicaciones subordinadas.

Se definirán primeramente conceptos que tienen un determinado sentido en el contexto de la descripción.

Concepto “enlace”

Un enlace en una red viene determinado inequívocamente por A) un 2-tuplo de los correspondientes identificadores para nodos inicial y de destino o B) un 3-tuplo de los correspondientes identificadores para nodos inicial y de destino y clase de servicio.

La utilización de un n-tuplo implica que cada elemento del tuplo tiene un lugar inequívoco. Es decir, en un 2-tuplo según A) no sería un enlace R1 = (X, Y) idéntico a un enlace R2 = (Y, X) . Una ruta es un enlace punto-a-punto según técnica de datos entre dos nodos de red. Un enlace de datos une entre sí dos nodos contiguos según técnica de datos.

Concepto “característica de calidad”

Una característica de calidad (característica de calidad del servicio) es una característica según la cual puede dictaminarse la calidad de un enlace de datos o de una ruta. Ejemplos de características de calidad son la anchura de banda mínima de reserva, el jitter (fluctuación de fase) tolerado, la longitud de la cola para un buffer (memoria transitoria) de salida de un nodo de red o la longitud de la ruta. Una característica de la calidad del servicio puede describirse mediante un coeficiente, por ejemplo la cantidad de hops (saltos) de una ruta.

Concepto “agregación”

Agregación significa la aplicación de una función de agregación que combina entre sí coeficientes de una misma característica de calidad para al menos dos nodos de red.

Concepto “valoración”

La... [Seguir leyendo]

1. Procedimiento para establecer una ruta que une un nodo inicial (Q) con un nodo de destino en una red reactiva, con las etapas:

a) el nodo inicial inunda la red mediante el procedimiento de broadcast (difusión general) con mensajes de solicitud, RREQ, en los que se incluye al menos una estructura de memoria de datos para coeficientes de características de calidad del servicio, a excepción de una magnitud de correlación que describe una correlación de distancias entre la ruta de red recorrida por el correspondiente mensaje de solicitud y una ruta de referencia en la red;

b) un nodo de red que procesa un mensaje de solicitud actualiza los coeficientes contenidos en el mensaje de solicitud;

c) cada nodo de red (I) distinto del nodo de destino (Z) memoriza transitoriamente un mensaje de solicitud recibido durante un primer tiempo de recorrido, T1, y durante un segundo tiempo de recorrido, T2, que acaba después del primer tiempo de recorrido, en el caso de que una valoración de los coeficientes del mensaje de solicitud recibido mediante una regla de valoración dé como resultado que al menos un coeficiente del mensaje de solicitud recibido es mejor que el correspondiente coeficiente de cada mensaje de solicitud ya memorizado transitoriamente, no memorizándose transitoriamente este mensaje de solicitud en el caso de que todos los coeficientes del mensaje de solicitud recibido no sean mejores en cada caso que los coeficientes de al menos un mensaje de solicitud ya memorizado transitoriamente;

d) cada nodo de red (I) distinto del nodo de destino (Z) aplica a los coeficientes de las características de calidad del servicio de cada mensaje de solicitud memorizado transitoriamente una primera función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio, con lo que se obtiene para cada mensaje de solicitud un primer resultado de valoración;

e) cada nodo de red (I) distinto del nodo de destino (Z) elige de entre los mensajes de solicitud memorizados transitoriamente durante el primer tiempo de recorrido un mensaje de solicitud según una primera regla de valoración para los primeros resultados de valoración, enviándose el mismo con sus coeficientes actualizados mediante el procedimiento de broadcast a los nodos contiguos;

f) el nodo de destino (Z) memoriza transitoriamente los mensajes de solicitud recibidos durante un tercer tiempo de recorrido, T3, aplica a los coeficientes de las características de calidad del servicio de los mensajes de solicitud memorizados transitoriamente en cada caso una segunda función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio, con lo que para cada mensaje de solicitud memorizado transitoriamente se obtiene un segundo resultado de valoración, elige tras transcurrir el tercer tiempo de recorrido al menos un mensaje de solicitud según una segunda regla de elección para los segundos resultados de valoración y envía un mensaje de respuesta, RREP, a un nodo de red contiguo en la dirección de retorno según la ruta de red recorrida por el mensaje de solicitud elegido;

g) cada nodo de red que recibe el mensaje de respuesta, RREP, comprueba si un mensaje de solicitud memorizado transitoriamente durante el segundo tiempo de recorrido tiene según la primera regla de elección un mejor resultado de valoración que el mensaje de solicitud enviado una vez transcurrido el primer tiempo de recorrido, retransmitiendo el mismo el mensaje de respuesta en dirección de retorno a lo largo de la ruta de red del mensaje de solicitud elegido por el nodo de destino al siguiente nodo de red, en el caso de que en el nodo de red no exista ningún mensaje de solicitud de mejor valoración, y retransmite el mensaje de respuesta en la dirección de retorno a lo largo de la ruta de red recorrida por el mensaje de solicitud mejor valorado al siguiente nodo de red, en el caso de que en el nodo de red no exista un mensaje de solicitud de mejor valoración.

2. Procedimiento según la reivindicación 1, en el que un nodo de red que procesa un mensaje de solicitud actualiza un coeficiente de una característica de calidad del servicio contenido en el mensaje de solicitud aplicando una función de agregación al coeficiente contenido en el mensaje de solicitud y a un coeficiente de la misma característica de calidad del servicio relativo a este nodo de red.

3. Procedimiento según la reivindicación 2, en el que un nodo de red que procesa un mensaje de solicitud actualiza un coeficiente de una característica de calidad del servicio contenido en el mensaje de solicitud aplicando una función de agregación al coeficiente memorizado en el mensaje de solicitud y a un coeficiente de la misma característica de calidad del servicio válido para el enlace de datos del siguiente salto de un mensaje de solicitud.

4. Procedimiento según la reivindicación 2, en el que un nodo de red que procesa un mensaje de solicitud actualiza un coeficiente de una característica de calidad del servicio contenido en el mensaje de solicitud aplicando una función de agregación al coeficiente memorizado en el mensaje de solicitud y a un coeficiente de la misma característica de calidad del servicio válido para el enlace de datos del salto inmediatamente precedente del mensaje de solicitud.

5. Procedimiento según una de las reivindicaciones 1 a 4,

en el que un nodo de red distinto del nodo de destino actualiza los coeficientes de las características de calidad del servicio y a continuación aplica la primera función de valoración para la valoración ponderada de coeficientes para características de la calidad del servicio.

6. Procedimiento según una de las reivindicaciones 1 a 4, en el que un nodo de red distinto del nodo de destino aplica la primera función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio y a continuación actualiza los coeficientes de las características de calidad del servicio.

7. Procedimiento según una de las reivindicaciones 1 a 6, en el que el nodo de destino actualiza los coeficientes de las características de calidad del servicio y a continuación aplica la segunda función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio.

8. Procedimiento según una de las reivindicaciones 1 a 6, en el que el nodo de destino aplica la segunda función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio y a continuación actualiza los coeficientes de las características de calidad del servicio.

9. Procedimiento según una de las reivindicaciones 1 a 8, en el que se valora un coeficiente como mejor que otro coeficiente en el caso de que el primer coeficiente sea mayor que el segundo coeficiente, valorándose el primer coeficiente como peor que el segundo coeficiente en el caso de que el primer coeficiente no sea mayor que el segundo coeficiente.

10. Procedimiento según una de las reivindicaciones 1 a 8, en el que un coeficiente se valora como mejor que otro coeficiente en el caso de que el primer coeficiente sea menor que el segundo coeficiente, valorándose el primer coeficiente como peor que el segundo coeficiente en el caso de que el primer coeficiente no sea inferior al otro coeficiente.

11. Procedimiento según una de la reivindicaciones 1 a 10, en el que el nodo inicial genera, tras recibir el mensaje de respuesta, un mensaje de confirmación, que se envía al nodo de destino.

12. Procedimiento según una de las reivindicaciones 1 a 11, en el que un mensaje de respuesta recibido por un nodo de red sólo se retransmite en el caso de que aún no haya corrido el segundo tiempo de recorrido.

13. Procedimiento según una de las reivindicaciones 1 a 12, en el que a) el nodo de destino elige una vez transcurrido el tercer tiempo de recorrido un conjunto de mensajes de solicitud según una tercera regla de elección para los segundos resultados de valoración y envía en cada caso un mensaje de respuesta dotado de las correspondientes características de calidad del servicio de los mensajes de solicitud elegidos a los nodos de red contiguos en la dirección de retorno, según las rutas de red recorridas en cada caso por los mensajes de solicitud elegidos; b) cada nodo de red que recibe un mensaje de respuesta actualiza los coeficientes de los mensajes de respuesta y comprueba si un mensaje de solicitud memorizado transitoriamente una vez transcurrido el primer tiempo de recorrido tiene según la primera regla de elección un mejor resultado de valoración que el mensaje de solicitud enviado una vez transcurrido el primer tiempo de recorrido, retransmitiendo el mismo, en el caso de que en el nodo de red no exista ningún mensaje de solicitud mejor valorado, el mensaje de respuesta en la dirección de retorno a lo largo de la ruta de red recorrida por el mensaje de solicitud elegido por el nodo de destino al siguiente nodo de red y en el caso de que en el nodo de red exista un mensaje de solicitud mejor valorado, retransmite el mensaje de respuesta en la dirección de retorno a lo largo de la ruta de red recorrida por el mensaje de solicitud mejor valorado al siguiente nodo de red;

c) el nodo inicial memoriza transitoriamente los mensajes de respuesta recibidos durante un cuarto tiempo de recorrido, aplica una tercera función de valoración para la valoración ponderada de características de calidad del servicio a los coeficientes para características de la calidad del servicio de los mensajes de respuesta memorizados transitoriamente, con lo que para cada mensaje de respuesta se obtiene un cuarto resultado de valoración, elige una vez transcurrido el cuarto tiempo de recorrido un mensaje de respuesta según una cuarta regla de elección para los cuartos resultados de valoración y envía un mensaje de confirmación en dirección hacia delante al nodo de destino a través de la ruta de red recorrida por el mensaje de respuesta elegido.

14. Procedimiento según una de las reivindicaciones 1 a 13, en el que cada nodo de red intercambia con todos sus nodos de red contiguos mensajes de información de rutas, estando incluidos en cada mensaje de información de rutas de datos que describen si un nodo de red que envía el mensaje de información de rutas es parte de una ruta establecida en la red.

15. Procedimiento según una de las reivindicaciones 1 a 13, en el que cada nodo de red intercambia con sus nodos de red contiguos mensajes de información de rutas, estando incluidos en cada mensaje de información de rutas datos que describen si un nodo de red contiguo al nodo de red que envía el mensaje de información de rutas es parte de una ruta establecida en la red.

16. Procedimiento según una de las reivindicaciones 1 a 13,

en el que cada nodo de red intercambia con sus nodos de red contiguos mensajes de información de rutas, incluyendo cada mensaje de información de rutas datos que describen si un nodo contiguo al nodo de red que envía el mensaje de información de rutas dentro de una vecindad de 1 salto, 2 saltos ó 3 saltos es parte de una

ruta establecida en la red.

17. Procedimiento según una de las reivindicaciones 1 a 16, en el que la primera, segunda y tercera función de valoración son iguales.

18. Nodo de red de una red compuesta por nodos de red unidos entre sí mediante técnica de datos, que está equipado de manera adecuada para realizar un procedimiento según una de las reivindicaciones 1 a 17.