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

Abstract

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.

Description

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 valoración significa la aplicación de una función de valoración que combina entre sí varias características de calidad, ponderándose las correspondientes características de calidad según su importancia. Por ejemplo pueden valorarse las características de calidad longitud de ruta 5, disponibilidad 70% y correlación 4 como sigue: 0,2*5+10*70/100+0,5*4=10. La función de valoración aporta como resultado un valor de valoración. Una función de valoración agrega distintas características de calidad.

En el marco de la invención se muestra un procedimiento para establecer una ruta en una red ad-hoc enmallada con conmutación por paquetes orientada al enlace (red reactiva multisalto) de nodos de red unidos entre sí según técnica de datos.

La ruta a establecer debe unir entre sí un nodo inicial a través de al menos un nodo intermedio con un nodo de destino mediante técnica de datos (enlace punto-a-punto).

En el procedimiento correspondiente a la invención se inunda la red primeramente con un mensaje de solicitud enviado por el nodo inicial según el procedimiento de broadcast. El nodo inicial genera para este fin para cada nodo de red contiguo el correspondiente mensaje de solicitud y envía estos mensajes de solicitud a los nodos de red contiguos. En cada mensaje de solicitud se incluye una estructura de memoria de datos para memorizar coeficientes para características de calidad, a excepción de un parámetro de correlación que describe una correlación de distancia de la ruta de red recorrida por el correspondiente mensaje de solicitud con una ruta de referencia en la red. En los mensajes de solicitud enviados por el nodo inicial se incluyen bien valores de inicialización para los coeficientes de las características de calidad del servicio o bien coeficientes correspondientes a los nodos iniciales. Cada nodo de red (emisor y/o receptor) que procesa un tal mensaje de solicitud actualiza los coeficientes contenidos en el mensaje de solicitud, en particular en forma agregada. Esto significa que el nodo inicial y cada uno de los nodos de red que reciben un mensaje de solicitud a excepción del nodo de destino o alternativamente los nodos de red que reciben un mensaje de solicitud y el nodo de destino actualizan los coeficientes contenidos en el mensaje de solicitud. Al respecto es esencial solamente que una de ambas alternativas se mantenga consecuentemente en el procedimiento correspondiente a la invención.

Cada nodo de red que recibe un mensaje de solicitud y que es distinto del nodo de destino memoriza transitoriamente (bajo la hipótesis de que se cumpla la condición que se indica más abajo) durante un primer tiempo de recorrido (T1) que puede ajustarse previamente y durante un segundo tiempo de recorrido (T2) que puede ajustarse previamente y que finaliza tras el primer tiempo de recorrido, los mensajes de solicitud recibidos en una memoria transitoria de mensajes de solicitud. Para este fin inicia el nodo de red, cuando recibe por primera vez un mensaje de solicitud, un primer reloj con un primer tiempo de recorrido y un segundo reloj con un segundo tiempo de recorrido.

Una memorización transitoria de un mensaje de solicitud recibido se realiza bajo la hipótesis de que la valoración de los coeficientes del mensaje de solicitud recibido mediante una regla de valoración da como resultado que al menos un coeficiente del mensaje de solicitud recibido es mejor (está mejor valorado) que el correspondiente coeficiente de cada uno de los mensajes de solicitud ya memorizados transitoriamente. El mensaje de solicitud recibido no se memoriza transitoriamente en el caso de que la valoración de los coeficientes del mensaje de solicitud recibido mediante la regla de valoración dé como resultado que todos los coeficientes correspondientes del mensaje de solicitud recibido no son mejores (no están mejor valorados) que los correspondientes coeficientes de al menos un mensaje de solicitud ya memorizado transitoriamente. La valoración de los coeficientes del mensaje de solicitud recibido se realiza en una comparación individual con cada mensaje de solicitud memorizado transitoriamente.

Por ejemplo pueden estar realizada la regla de valoración para los coeficientes de una característica de calidad del servicio tal que un coeficiente se valore mejor que otro coeficiente cuando un coeficiente es mayor (o bien no menor) que el otro coeficiente, valorándose peor uno de los coeficientes que el otro coeficiente en el caso de que uno de los coeficientes no sea mayor (o bien sea menor) que el otro coeficiente.

Alternativamente puede estar realizada la regla de valoración para los coeficientes de una característica de calidad del servicio tal que se valore un coeficiente mejor que otro coeficiente en el caso de que un coeficiente sea menor (o bien no mayor) que el otro coeficiente, valorándose uno de los coeficientes peor que el otro coeficiente en el caso de que uno de los coeficientes no sea menor (o bien sea mayor) que el otro coeficiente.

Cada nodo de red distinto del nodo de destino 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 para cada mensaje de solicitud se obtiene un primer resultado de valoración

Cada nodo de red distinto del nodo de destino elige a partir de los mensajes de solicitud memorizados transitoriamente durante el primer tiempo de recorrido un mensaje de solicitud según una primera regla de elección para los primeros resultados de valoración, que se envía con coeficientes actualizados en cada caso mediante el procedimiento de broadcast a los nodos de red contiguos. Por ejemplo se elige mediante la primera regla de elección un mensaje de solicitud en base a una correlación de distancia respecto a una ruta de referencia de la red. En particular se elige un mensaje de solicitud con un mejor resultado de valoración (por ejemplo el máximo o el mínimo).

En el caso de que el nodo de destino reciba por primera vez un mensaje de solicitud, memoriza el mismo el mensaje de solicitud y arranca un tercer reloj con un tercer tiempo de recorrido (T3) que puede ajustarse previamente. Los mensajes de solicitud recibidos durante el tercer tiempo de recorrido se memorizan transitoriamente en la memoria transitoria de mensajes de solicitud del nodo de destino.

El nodo de destino 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 se obtiene para cada mensaje de solicitud memorizado transitoriamente un segundo resultado de valoración y 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. Por ejemplo se elige mediante la segunda regla de elección un mensaje de solicitud en base a una correlación de distancias respecto a una ruta de referencia de la red. En particular se elige un mensaje de solicitud con el mejor resultado de valoración (por ejemplo el máximo o el mínimo).

El nodo de destino genera a continuación un mensaje de respuesta y envía el 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. El mensaje de respuesta se retransmite desde este y otros nodos de red correspondientemente hasta el nodo inicial. En el mensaje de respuesta pueden estar contenidos los coeficientes de las características de calidad del servicio del mensaje de solicitud elegido.

Cada nodo de red que recibe el mensaje de respuesta 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 tras transcurrir el primer tiempo de recorrido, y en el caso de que en el nodo de red no exista ningún 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 elegido por el nodo de destino al siguiente nodo de red, y en caso contrario, es decir, que en el nodo de red exista un mensaje de solicitud mejor valorado, retransmite el mensaje de solicitud en la dirección de retorno al siguiente nodo de red a lo largo de la ruta de red recorrida por el mensaje de solicitud mejor valorado.

Cuando recibe el nodo inicial el mensaje de respuesta, se establece mediante el mismo la ruta de red recorrida por el mensaje de respuesta como ruta. Dado el caso puede enviar el nodo inicial para este fin adicionalmente un mensaje de confirmación al nodo de destino a través de la ruta de red recorrida por el mensaje de respuesta. Alternativamente puede confirmarse también la ruta mediante un primer paquete de datos útiles (que es distinto de un mensaje de enrutamiento enviado en el marco del protocolo de red). Esto es procedente, ya que un paquete de datos útiles puede saltarse el mensaje de confirmación o bien puede perderse un mensaje de confirmación.

En el procedimiento correspondiente a la invención puede establecerse mediante una memorización transitoria condicionada de mensajes de solicitud en los nodos de red una ruta sin bucles en una red ad-hoc reactiva.

En el procedimiento correspondiente a la invención se incluyen los coeficientes para características de calidad del servicio preferiblemente de forma agregada en los mensajes de solicitud y de respuesta y son actualizados por los nodos de red con coeficientes agregados.

El procedimiento correspondiente a la invención puede estar configurado tal 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, utilizando el mismo una función de agregación en relación con el coeficiente contenido en el mensaje de solicitud y un coeficiente de la misma característica de calidad del servicio relativo a este nodo de red. Un nodo de red puede actualizar un coeficiente de una característica de calidad del servicio contenido en el mensaje de solicitud, utilizando el mismo una función de agregación en relación con el coeficiente memorizado en el mensaje de solicitud y un coeficiente válido para el enlace de datos de un siguiente salto (hop) del mensaje de solicitud correspondiente a la misma característica de calidad del servicio. Alternativamente puede actualizar el nodo de red un coeficiente de una característica de calidad del servicio contenido en el mensaje de solicitud, utilizando el mismo una función de agregación en relación con el coeficiente memorizado en el mensaje de solicitud y un coeficiente de la misma característica de calidad del servicio válido para el enlace de datos de un salto inmediatamente precedente del mensaje de solicitud. Al respecto es esencial solamente que una de ambas alternativas se mantenga consecuentemente en el procedimiento correspondiente a la invención.

En el procedimiento correspondiente a la invención puede actualizar cada uno de los nodos de red distinto del nodo de destino primeramente los coeficientes de las características de calidad del servicio y a continuación utilizar la primera función de evaluación para la valoración ponderada de coeficientes para características de calidad del servicio en base a los coeficientes actualizados. Alternativamente puede el mismo aplicar primeramente la primera función de valoración para la valoración ponderada de coeficientes para características de calidad del servicio en base a los coeficientes memorizados y actualizar a continuación los coeficientes de las características de calidad del servicio. Al respecto es esencial solamente que se mantenga consecuentemente una de ambas alternativas en el procedimiento.

En el procedimiento correspondiente a la invención puede actualizar el nodo de destino primeramente los coeficientes de las características de calidad del servicio y a continuación aplicar la segunda función de valoración para la valoración ponderada de coeficientes para las características de calidad del servicio en base a los coeficientes actualizados. Alternativamente puede el mismo primeramente aplicar la segunda función de valoración para la valoración ponderada de coeficientes relativos a características de calidad del servicio en base a los coeficientes memorizados y a continuación actualizar los coeficientes de las características de calidad del servicio. Al respecto solamente es esencial que se mantenga consecuentemente una de ambas alternativas en el procedimiento.

En otra configuración ventajosa del procedimiento correspondiente a la invención elige el nodo de destino, tras transcurrir 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 (RREP) 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 por los mensajes de solicitud elegidos. Según la tercera regla de elección se eligen los mensajes de respuesta por ejemplo en base a una correlación de distancias relativa a una ruta de referencia. En particular pueden elegirse los mensajes de solicitud comenzando con el mensaje de solicitud con el mejor resultado de valoración (por ejemplo el máximo o el mínimo resultado de valoración), siguiendo con un resultado de valoración sucesivamente peor.

Cada nodo de red que recibe un mensaje de respuesta actualiza los coeficientes agregados del mensaje de respuesta y comprueba si un mensaje de solicitud memorizado transitoriamente tras transcurrir 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 tras transcurrir el primer tiempo de recorrido. En el caso de que en el nodo de red no exista ningún mensaje de solicitud mejor valorado, se retransmite al siguiente nodo de red 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. Para el otro caso, es decir, que en el nodo de red exista un mensaje de solicitud mejor valorado, se retransmite al siguiente nodo de red 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.

En este caso arranca el nodo de red, tras la recepción por primera vez de un mensaje de respuesta, un cuarto reloj con un cuarto tiempo de recorrido que puede ajustarse previamente y memoriza transitoriamente los mensajes de respuesta recibidos durante el cuarto tiempo de recorrido. Además, utiliza el nodo inicial una tercera función de valoración para la valoración ponderada de características de calidad del servicio aplicando los coeficientes para características de calidad del servicio de los mensajes de respuesta memorizados transitoriamente, con lo que para cada mensaje de respuesta se recibe un tercer resultado de valoración. Tras transcurrir el cuarto tiempo de recorrido, elige el nodo inicial un mensaje de respuesta según una cuarta regla de elección para los terceros resultados de valoración y envía al nodo de destino un mensaje de confirmación en dirección hacia delante a través de la ruta de red recorrida por el mensaje de respuesta elegido, con lo que se establece la ruta. Por ejemplo se elige mediante la cuarta regla de elección un mensaje de respuesta en base a la correlación de distancias relativa a una ruta de referencia de la red. En particular se elige un mensaje de respuesta con un mejor (por ejemplo máximo o mínimo) resultado de valoración.

En el procedimiento correspondiente a la invención pueden ser iguales entre sí la primera, segunda y tercera función de valoración.

La invención se extiende además a un nodo de red de una red compuesta por nodos de red unidos entre sí según técnica de datos, que está equipado adecuadamente para realizar un procedimiento como el antes descrito.

La invención se describirá ahora más en detalle en base a un ejemplo de ejecución, con referencia a las figuras adjuntas.

La figura 1 muestra en una representación esquemática un ejemplo de ejecución de la invención; La figura 2 muestra en otra representación esquemática el ejemplo de ejecución de la invención.

En las figuras 1 y 2 se muestra una red ad-hoc inalámbrica enmallada de conmutación por paquetes, orientada al enlace, (red multisalto reactiva) con un conjunto de nodos de red unidos entre sí según técnica de datos mediante enlaces de datos punto-a-punto. Los nodos de red, que se designan en cada caso mediante letras indexadas, están dotados de equipos de procesamiento adecuados para el tratamiento de datos, así como de equipos emisores y receptores para enviar y recibir respectivamente paquetes de datos. En los nodos de red está implementado descentralizadamente un sistema de gestión de red, que ejecuta el procedimiento correspondiente a la invención.

En una transmisión de paquetes de datos entre dos nodos de la red unidos entre sí mediante un enlace de datos punto-a-punto, participan varias capas según el modelo de referencia ISO/OSI. Las mismas incluyen en particular una capa de transmisión de bits L1 (Physical Layer, capa física), en la que se realiza la transmisión por bits de los datos a través del medio de transmisión, una capa de enlace de datos L2 (Data Link), en la que por ejemplo está regulado el acceso al medio de transmisión y que está dividida en dos subcapas (LLC = Logical Link Control, control de enlaces lógicos y MAC = Media Access Control, control de acceso a medios) y una capa de conmutación L3 (Network layer, capa de red), en la que se realiza el enrutamiento y una retransmisión de paquetes de datos.

En la red del ejemplo de ejecución de la figura 1 y la figura 2 se realiza una transmisión de paquetes de datos en base a un procedimiento de acceso de multiplexado en el tiempo (TDMA = Time Division Multiple Access) con reserva de anchura de banda, tal como se especifica en el estándar IEEE 802.16. Aquí están previstos determinados espacios de tiempo (ranuras del tiempo) en cada caso de la misma longitud con una anchura de banda reservada para una transmisión de datos. El IEEE 802.16 especifica al respecto solamente ambas capas más inferiores L1 y L2, distribuyéndose mediante la capa MAC las ranuras de tiempo disponibles entre los distintos nodos de red que están unidos en cada caso con el mismo nodo de red mediante un enlace de datos separado.

En el marco de la IEEE 802.16 se tienen en cuenta en la capa MAC las siguientes características de calidad del servicio para un enlace de datos:

la cantidad de ranuras de tiempo (minislots) disponibles para una transmisión en ambas direcciones de transmisión del enlace de datos, pudiendo enviar y recibir en estas ranuras de tiempo un nodo de red paquetes de datos sin verse perjudicado por otro nodo de red,

la cantidad de ranuras del tiempo (minislots) disponible para una transmisión sólo en la dirección de recepción del enlace de datos, pudiendo un nodo de red sólo recibir en estas ranuras de tiempo paquetes de datos sin verse perjudicado por otro nodo de red,

la cantidad de ranuras de tiempo (minislots) disponibles para una transmisión sólo en la dirección de envío del enlace de datos, pudiendo un nodo de red sólo enviar en esta ranuras de tiempo paquetes de datos sin verse perjudicado por otro nodo de red,

la cantidad de ranuras de tiempo (minislots) disponibles para una transmisión a través del enlace de datos, en la que no pueden recibirse o enviarse en la dirección de recepción ni en la dirección de envío respectivamente paquetes de datos sin verse perjudicado por otro nodo de red,

una información de anchura de banda, es decir, la cantidad de ranuras de tiempo (minislots) que están reservadas para el siguiente salto (hop) en la ruta de red, una longitud de cola para el buffer (memoria transitoria) de salida del enlace de datos previsto para el siguiente salto.

En base a una solicitud de enlace (solicitud de una ruta desde un nodo inicial Q hasta un nodo de destino Z), se inicia una secuencia de etapas del proceso para establecer una ruta en la red, que aquí se denomina en su totalidad con el concepto "Route Discovery" (hallazgo de ruta). Una misma Route Discovery puede identificarse inequívocamente mediante las direcciones de los nodos inicial y de destino, una clase de servicio (clase de características de calidad del servicio) y un número de ruta.

La ruta a establecer debe presentar una determinada calidad del servicio (o bien determinadas características de calidad del servicio). Por ejemplo debe la misma tener en particular una distancia de más de tres saltos (hops) a una ruta en paralelo (ruta de referencia) ya existente en la red. Se supone que una tal ruta en paralelo ya existe en la red. La misma puede haberse establecido por ejemplo mediante un precedente Route Discovery del procedimiento correspondiente a la invención.

Para establecer la ruta genera el nodo inicial Q primeramente un mensaje de solicitud RREQ (RREQ = Route Request, solicitud de ruta), que mediante el procedimiento de broadcast se envía a todos los nodos contiguos al nodo inicial Q. Esto se representa esquemáticamente a la izquierda en la figura 1, en la que se muestran el nodo inicial Q y los siguientes nodos contiguos E1 … Ek al nodo inicial Q en base a flechas, que simbolizan el envío del mensaje de solicitud RREQ a cada nodo inmediatamente contiguo.

El mensaje de solicitud RREQ presenta por ejemplo el siguiente formato:

Campo tamaño tipo de mensaje 4 bits dirección inicial 32 bits dirección de destino 32 bits clase de servicio 8 bits número de ruta 8 bits número de solicitud de ruta 16 bits

Informaciones sobre la calidad del servicio: factor de correlación 16 bits longitud de cola cualificada 16 bits anchura de banda mínima reservada 8 bits anchura de banda mínima libre 8 bits longitud de la ruta 8 bits

En consecuencia se incluye en el mensaje de solicitud RREQ un identificador del tipo de mensaje (en el presente caso "mensaje de solicitud"), un identificador del nodo inicial, un identificador del nodo de destino, un identificador de la clase de servicio (clase de características de la calidad del servicio), un número de ruta para identificar la ruta a establecer y un número de solicitud de ruta para identificar el mensaje de solicitud RREQ.

Adicionalmente se incluye en el mensaje de solicitud una estructura de memoria de datos, en la que pueden memorizarse los coeficientes (métricas) para una serie de características de la calidad del servicio, es decir, para un factor de correlación que indica la correlación de distancias de la ruta a establecer respecto a una ruta paralela ya existente en la red, una longitud de cola cualificada para el buffer (memoria transitoria) de salida de un nodo de la red, una anchura de banda mínima reservada para la transmisión de datos, una anchura de banda mínima libre y la longitud de la ruta.

Los coeficientes de las características de la calidad del servicio de los mensajes de solicitud son actualizados en cada caso por los nodos de red. El nodo inicial averigua los valores que le corresponden de los coeficientes para las características de calidad del servicio y memoriza los mismos en las estructuras de memoria de datos de los mensajes de solicitud enviados a sus nodos contiguos.

Cuando un nodo de la red recibe por primera vez un mensaje de solicitud RREQ de una misma Route Discovery, arranca el mismo un primer reloj (timer) con un primer tiempo de recorrido T1 que puede ajustarse previamente, así como un segundo reloj con un segundo tiempo de recorrido T2 que puede ajustarse previamente. El momento del arranque y la longitud de ambos tiempos de recorrido están elegidos tal que el segundo tiempo de recorrido T2 transcurre sólo tras el primer tiempo de recorrido T1.

Mientras transcurre el primer tiempo de recorrido T1 y mientras transcurre el segundo tiempo de recorrido T2, se memorizan transitoriamente todos los mensajes de solicitud RREQ que llegan a este nodo de red y que pertenecen al mismo Route Discovery, en la memoria de almacenamiento transitorio de mensajes de solicitud, siempre que se cumpla la siguiente condición:

El mensaje de solicitud recibido se somete a la correspondiente comparación individual con mensajes de solicitud ya memorizados transitoriamente. Entonces se comprueba para cada característica de calidad del servicio del mensaje de solicitud recibido, en base a una regla de valoración que puede elegirse, si esta característica de calidad del servicio es mejor o peor que la correspondiente característica de calidad del servicio de un mismo mensaje de solicitud memorizado transitoriamente. En el caso de que al menos un coeficiente del mensaje de solicitud recibido se valore mejor que el correspondiente coeficiente de cada uno de los mensajes de solicitud memorizados, se memoriza transitoriamente el mensaje de solicitud recibido. En el caso de que todos los coeficientes del mensaje de solicitud recibido no tengan mejor valoración que los correspondientes coeficientes de al menos un mensaje de solicitud memorizado, no se memoriza transitoriamente el mensaje de solicitud recibido.

La regla de valoración se ha elegido por ejemplo tal que se valora un primer coeficiente mejor que un segundo coeficiente cuando el primer coeficiente es mayor que el coeficiente memorizado y que un primer coeficiente se valora como peor que un segundo coeficiente cuando el primer coeficiente no es mayor que el coeficiente memorizado. Esto rige para las características de calidad del servicio de mínima anchura de banda reservada, mínima anchura de banda libre y factor de correlación.

Alternativamente puede haberse elegido la regla de valoración tal que un primer coeficiente se valora como mejor que un segundo coeficiente cuando el primer coeficiente es menor que el coeficiente memorizado y que un primer coeficiente se evalúa como peor que un segundo coeficiente cuando el primer coeficiente no es menor que el coeficiente memorizado. Esto rige para las características de calidad del servicio de longitud de cola cualificada y longitud de la ruta.

Mediante esta medida puede realizarse una ruta libre de bucles.

El algoritmo para comprobar si un mensaje de solicitud se encuentra sobre un bucle o no es por ejemplo como sigue:

Function isNOtONALoop(r)

for all i s Q do // Q es la secuencia de RREQs a comprobar/retransmitida

(for all … do = para todos … ejecutar)

if p1 (i ) : p1 (r) A…A pn(i) then // px (y) es una característica de calidad del servicio

(if…then = si … entonces)

return false (respuesta falso)

end if (finalizar si)

end for (finalizar para)

return true (respuesta verdadero)

end function (finalizar función)

El mensaje de solicitud inicial RREQ, del que procedía el mensaje de solicitud RREQ repetidamente recibido, se encuentra continuamente en la memoria transitoria de mensajes de solicitud. Por esta razón se encuentra al menos un mensaje de solicitud RREQ en la memoria transitoria de mensajes de solicitud, que debido a la monotonía en todas las características de calidad no es peor que el mensaje de solicitud RREQ repetidamente recibido. Un mensaje de solicitud RREQ que se encuentra en un bucle se reconoce así en cualquier caso.

Así se memorizan transitoriamente en la memoria transitoria de mensajes de solicitud también todos los mensajes de solicitud RREQ que llegan tras transcurrir el primer tiempo de recorrido T1 hasta que transcurre el segundo tiempo de recorrido T2 y que pertenecen al mismo Route Discovery, en el caso de que se cumpla la anterior condición.

Una vez transcurrido el primer tiempo de recorrido T1, elige el nodo de red, de entre todos los mensajes de solicitud RREQ memorizados en la memoria transitoria de mensajes de solicitud durante el primer tiempo de recorrido T1, un mensaje de solicitud. La elección se realiza en base a las características de calidad memorizadas en los mensajes de solicitud RREQ.

En el nodo de red se ejecuta para este fin para cada mensaje de solicitud memorizado transitoriamente una primera función de valoración para la valoración ponderada de los coeficientes de las características de calidad del servicio memorizadas en los mensajes de solicitud memorizados transitoriamente. Como resultado proporciona la función de valoración un valor de valoración para cada mensaje de solicitud. La elección de un mensaje de solicitud a partir de los mensajes de solicitud memorizados transitoriamente en el nodo de red se realiza según una primera regla de elección, que puede elegirse, para los resultados de la función de valoración, eligiéndose un mensaje de solicitud en base al factor de correlación agregado, lo cual es ventajoso en cuanto a interferencias locales debidas a nodos de red.

Cada nodo de red determina para el mensaje de solicitud elegido los coeficientes que le afectan de las características de calidad del servicio contenidas en el mensaje de solicitud. Aquí son los coeficientes que se refieren al propio nodo de red por ejemplo los coeficientes de las características de calidad del servicio para aquel enlace de datos sobre el que debe retransmitirse el correspondiente mensaje de solicitud (siguiente salto).

Para determinar los coeficientes que le afectan de las características de calidad del servicio, puede recurrir el nodo de red a las informaciones de calidad del servicio tenidas en cuenta en la capa MAC, que pueden intercambiarse entre las capas (cross-layer) a través de las correspondientes interfaces en los procedimientos de push o pull (de adición o sustracción), por ejemplo mediante mensajes de información regulares.

Así puede determinar el nodo de red a partir del conjunto de ranuras de tiempo reservadas para el siguiente salto del paquete de datos la anchura de banda mínima reservada. A partir de la longitud de la cola (queue) para la memoria transitoria de salida, calcula el nodo de red como coeficiente una llamada longitud de cola cualificada para el siguiente salto a lo largo de la ruta de red, calculándose como longitud de cola cualificada por ejemplo el cociente entre la longitud de la cola y la suma ponderada de la anchura de banda reservada y la anchura de banda disponible. Alternativamente a ello puede utilizarse también la siguiente fórmula para calcular una longitud de cola cualificada L.

Con las abreviaturas:

A: longitud de cola de la memoria transitoria de salida para el siguiente salto

B: cantidad de mini-ranuras (minislots) para ambas direcciones de transmisión

C: cantidad de minislots para la dirección de envío

D: cantidad de minislots para la dirección de recepción

E: cantidad de minislots reservados para el siguiente salto

F: constante arbitraria mayor que cero

resulta la longitud de cola cualificada (L) como:

L = A/(a-B+b-C+c-D+d-E+F).

Además calcula cada nodo de red la longitud de la ruta que corresponde a la cantidad de saltos de la ruta de red recorrida y la correlación de distancias respecto a la ruta de referencia, que describe la distancia entre estas dos rutas de red. La distancia entre dos rutas resulta de la suma de las distancias de cada nodo de la primera ruta al siguiente nodo de la segunda ruta. En este contexto se considera como distancia entre dos nudos la mínima cantidad de saltos entre ambos nodos de red.

Para posibilitar al nodo de red determinar la correlación de distancias con la ruta de referencia, intercambian en el procedimiento correspondiente a la invención todos los nodos de red, mediante mensajes de información de rutas, informaciones sobre rutas en las proximidades de un nodo de red. Esto se realiza tal que cada nodo de red comunica a todos los siguientes nodos contiguos mediante transmisión del mensaje de información de rutas qué rutas le incluyen como nodo de red y qué rutas pasan por nodos de red en su proximidad en 1 salto, 2 saltos y 3 saltos.

A continuación se indica un algoritmo a modo de ejemplo para determinar la correlación en base a informaciones de proximidad:

function CORRELATION(srcAddr, dstAddr, serviceClass, routeNumber) correlationFactor

for all i s <rutas sobre nodos locales> do if is Parallel(srcAddr, dstAddrm, serviceClass) then

correlationFactor correlationFactor + 12

end if end for for all i s <rutas sobre vecinos directos> do if is Parallel(srcAddr, dstAddrm, serviceClass) then

correlationFactor correlationFactor + 3

end if end for for all i s <rutas con una distancia de tres aristas> do if is Parallel(srcAddr, dstAddrm, serviceClass) then

correlationFactor correlationFactor + 3

end if end for for all i s <rutas con una distancia de cuatro aristas> if is Parallel(srcAddr, dstAddrm, serviceClass) then

correlationFactor correlationFactor + 1

end if end for return correlationFactor

end function

En base a los coeficientes determinados, que se refieren al propio nodo de red, calcula cada nodo de red a continuación para el mensaje de solicitud elegido un coeficiente actual para las características de calidad del servicio contenidas en el mensaje de solicitud.

Para este fin ejecuta el nodo de red en cada caso separadamente para cada característica de calidad del servicio una función de agregación. La función de agregación para una característica de calidad del servicio se aplica entonces al coeficiente de la característica de calidad del servicio memorizado en el mensaje de solicitud y al coeficiente averiguado de esta característica de calidad del servicio. La aplicación de la función de agregación aporta para cada característica de calidad del servicio como valor de resultado un coeficiente actual para la característica de calidad del servicio para este nodo de red. Para la anchura de banda reservada y la anchura de banda mínima libre se realiza como función de agregación en cada caso una función de mínimos, que como valor de resultado (coeficiente actual) aporta el mínimo de ambos coeficientes. Para la longitud de la cola, la longitud de la ruta y el factor de correlación, se ejecuta como función de agregación en cada caso una función plus, que como valor de resultado (coeficiente actual) aporta la suma de ambos coeficientes.

A continuación envía el nodo de red el mensaje de solicitud elegido en cada caso a todos sus nodos inmediatamente más próximos mediante el procedimiento de broadcast, sustituyéndose (actualizándose) en los mensajes de solicitud para cada enlace de datos del siguiente salto los coeficientes memorizados por los coeficientes actuales.

En la figura 1 esto se muestra mediante la representación central. La misma muestra un nodo de red I, que recibe de un conjunto de nodos F1 … Fm respectivos mensajes de solicitud RREQ, memoriza transitoriamente los mensajes de solicitud RREQ recibidos en la memoria transitoria de mensajes de solicitud, elige de entre ellos un mensaje de solicitud RREQ, modifica el mensaje de solicitud recibido RREQ en función de sus informaciones relevantes sobre enrutamiento propias y envía este mensaje de solicitud modificado RREQ a todos los nodos de red inmediatamente contiguos G1 … Gn mediante el procedimiento de broadcast.

Cada nodo de red memoriza la información sobre de qué nodo de red ha recibido el mismo el correspondiente mensaje de solicitud RREQ.

Finalmente recibe el nodo de destino Z de sus nodos de red contiguos H1 … Hp respectivos mensajes de solicitud RREQ, lo cual se muestra en la figura 1, representación a la derecha. Con la recepción del primer mensaje de solicitud RREQ de un mismo Route Discovery arranca el nodo de destino Z un tercer temporizador con un tercer tiempo de recorrido T3 previamente ajustable. Mientras transcurre el tercer tiempo de recorrido T3 memoriza transitoriamente el nodo de destino Z todos los mensajes de solicitud RREQ recibidos en una memoria transitoria de mensajes de solicitud.

Una vez transcurrido el tercer tiempo de recorrido T3, elige el nodo de destino Z a partir de los mensajes de solicitud RREQ memorizados en la memoria transitoria de mensajes de solicitud un conjunto de mensajes de solicitud RREQ. La elección de un mensaje de solicitud RREQ se realiza en base a las características de calidad memorizadas como informaciones de calidad del servicio en los mensajes de solicitud RREQ, aplicándose la función de valoración a los coeficientes de los mensajes de solicitud memorizados transitoriamente.

La elección del conjunto de mensajes de solicitud RREQ se realiza según una tercera regla de elección para los segundos resultados de valoración, eligiéndose por ejemplo mensajes de solicitud que comenzando con un resultado de valoración máximo tienen un resultado de valoración progresivamente decreciente. En particular pueden también elegirse mensajes de solicitud en base al factor de correlación.

A continuación genera el nodo de destino Z un mensaje de respuesta (RREP = “Route Reply”, respuesta de ruta), que se envía mediante el procedimiento de unicast en cada caso a todos los nodos de red contiguos de los que se han recibido los mensajes de solicitud RREQ elegidos. Esto se muestra en la figura 2, representación izquierda, representándose allí de manera esquemática que el nodo de destino Z envía un conjunto de mensajes de respuesta a los nodos de red inmediatamente contiguos H1…Hp.

El formato de mensaje correspondiente al mensaje de respuesta RREP es aquí por ejemplo como sigue:

Campo tamaño tipo de mensaje 4 bits dirección inicial 32 bits dirección de destino 32 bits clase de servicio 8 bits número de ruta 8 bits número de solicitud de ruta 16 bits

Informaciones sobre la calidad del servicio: factor de correlación 16 bits longitud de cola cualificada 16 bits anchura de banda mínima reservada 8 bits anchura de banda mínima libre 8 bits longitud de la ruta 8 bits

En consecuencia se incluye en el mensaje de respuesta RREQ un identificador para el tipo de mensaje (en el caso presente "mensaje de respuesta"), un identificador del nodo inicial, un identificador del nodo de destino, un

identificador de una clase de servicio, un número de ruta para identificar la ruta a establecer y un número de solicitud de ruta para identificar el mensaje de respuesta RREQ.

Adicionalmente se incluye en el mensaje de solicitud una estructura de memoria de datos, en la que están memorizados los coeficientes (métricas) para las características de la calidad del servicio del correspondiente mensaje de respuesta elegido.

Cada nodo de red que recibe un mensaje de respuesta RREP actualiza los coeficientes para las características de la calidad del servicio y retransmite este mensaje de respuesta mediante el procedimiento de unicast al siguiente nodo de red del que ha recibido el correspondiente mensaje de solicitud RREQ. La premisa para la retransmisión de un mensaje de respuesta RREP a través de un nodo intermedio es que aún no haya transcurrido el segundo tiempo de recorrido T2 del correspondiente Route Discovery del nodo de red. En el caso de que el correspondiente segundo tiempo de recorrido T2 del correspondiente Route Discovery haya transcurrido ya, no se sigue procesando el mensaje de respuesta RREP.

El mensaje de respuesta RREP se conduce así mediante el procedimiento de unicast en dirección de retorno a lo largo de las rutas de red definidas por los mensajes de solicitud RREQ elegidos hasta el nodo inicial Q.

Puesto que un nodo de red memoriza transitoriamente en la memoria transitoria de mensajes de solicitud los mensajes de solicitud RREQ que llegan hasta que transcurre el segundo tiempo de recorrido T2, es decir, también incluso tras el envío de un mensaje de solicitud RREQ, puede presentarse el caso de que mediante un mensaje de solicitud RREQ recibido una vez transcurrido el primer tiempo de recorrido T1 quede definida una ruta con mejor valoración. En este caso retransmite el nodo de red el mensaje de respuesta RREP a aquellos nodos precedentes de los que ha recibido el mensaje de solicitud RREQ memorizado transitoriamente mejor valorado. De esta manera existe la posibilidad de tener en cuenta mejoras de la ruta a posteriori. La elección del mejor mensaje de solicitud RREQ se realiza mediante la aplicación de la función de valoración y la elección según la primera regla de elección para el resultado de la valoración.

Esto se visualiza en la figura 2, en la representación central, que muestra un nodo intermedio I, que recibe de un conjunto de nodos intermedios G¡…Gj respectivos mensajes de respuesta RREP y envía los mismos a un nodo de red Fi del que ha recibido el mensaje de solicitud RREQ de mejor valoración.

Cuando el nodo inicial Q recibe el primer mensaje de respuesta RREP del Route Discovery, arranca el mismo un cuarto reloj con un cuarto tiempo de recorrido T4 de libre elección. Mientras transcurre el cuarto tiempo de recorrido T4 se memorizan transitoriamente otros mensajes de respuesta RREP que lleguen en una memoria transitoria de mensajes de respuesta del nodo inicial Q.

Una vez transcurrido el cuarto tiempo de recorrido T4 elige el nodo inicial Q un mensaje de solicitud de entre los mensajes de solicitud RREQ memorizados en la memoria transitoria de mensajes de solicitud. La elección de un mensaje de solicitud RREQ se realiza en base a las características de calidad del servicio memorizadas como informaciones de calidad del servicio en los mensajes de solicitud RREQ, aplicándose para ello la misma función de valoración que se ha aplicado ya en los otros nodos de red (inclusive el nodo de destino), con lo que se obtiene un tercer resultado de valoración. Una vez transcurrido el cuarto tiempo de recorrido, elige el nodo inicial un mensaje de respuesta según una cuarta regla de elección para los terceros resultados de valoración, eligiéndose por ejemplo aquel mensaje de respuesta con el máximo resultado de valoración. La elección puede realizarse en particular en base al factor de correlación agregado. A continuación genera el nodo inicial un mensaje de confirmación y envía el mismo en dirección hacia delante al nodo de destino a través de la ruta de la red recorrida por el mensaje de respuesta elegido.

El formato del mensaje de confirmación es aquí por ejemplo como sigue:

Campo tamaño tipo de mensaje 4 bits dirección inicial 32 bits dirección de destino 32 bits clase de servicio 8 bits número de ruta 8 bits

Para cada nodo de red rige: En el caso de que el mismo reciba un tal mensaje de confirmación, inserta la correspondiente inscripción en su tabla de enrutamiento. Esta inscripción contiene la dirección del nodo inicial, la dirección del nodo de destino, la clase de servicio, el número de la ruta, la dirección del nodo de red que envía el mensaje de confirmación (dirección precedente) y la dirección del nodo de red siguiente (dirección siguiente). Mediante la inscripción de la dirección precedente es posible también una transmisión de datos en la dirección de retorno desde el nodo de destino hasta el nodo inicial, con lo que se establece una ruta de unión bidireccional. Una transmisión de datos en dirección hacia el nodo inicial es en particular importante cuando el nodo inicial debe ser informado sobre un empeoramiento de la calidad del servicio.

Cuando el nodo de destino Z recibe el mensaje de confirmación, queda establecida la nueva ruta en la red.

La ruta establecida puede deshacerse mediante un mensaje de destrucción (Route Destruction) conducido desde el nodo inicial hasta el nodo de destino.

El formato de un tal mensaje de destrucción es por ejemplo como sigue:

Campo tamaño tipo de mensaje 4 bits dirección inicial 32 bits clase de servicio 8 bits número de ruta 8 bits

En el procedimiento correspondiente a la invención gestiona cada nodo de red una tabla de enrutamiento para la retransmisión bidireccional de paquetes de datos que llegan. La tabla de enrutamiento asigna a un 4-tuplo a partir del nodo inicial, la dirección del nodo de destino, la clase de servicio y el número de ruta, una dirección para el siguiente salto del paquete de datos. Las direcciones del nodo inicial y del nodo de destino se toman de los correspondientes campos de la cabecera de IP del paquete de datos. La clase de servicio y el número de ruta se toman del campo ToS de la cabecera de IP. Para ello deben estar memorizados ambos valores en forma codificada en binario. La asignación de un paquete de datos que llega a un nodo intermedio a una ruta es necesaria, ya que pueden pasar varias rutas a través del mismo nodo de red y con ello existe la posibilidad de que se retransmitan paquetes de datos a través de nodos contiguos incorrectos.

El procedimiento correspondiente a la invención es capaz de optimizar rutas en cuanto a cualesquiera características de calidad para las que está definida la correspondiente álgebra. Mediante una comprobación de las características de calidad arrastradas de los mensajes de solicitud RREQ puede enjuiciarse si los mismos han sido retransmitidos ya por el correspondiente nodo de red, con lo que pueden evitarse rutas con bucles.

El procedimiento correspondiente a la invención puede asignar paquetes L3, es decir, paquetes de datos de la capa 3 (capa de conmutación o de red) del modelo de capas OSI a un enlace. Las características de calidad del servicio de una ruta son típicamente características del enlace de la capa 1 (capa de transmisión de bits) y la capa 2 (capa de enlace de datos) del modelo OSI. En los mensajes de enrutamiento del protocolo de red están memorizadas las características de calidad del servicio de una ruta de manera agregada en un contenedor de datos con al menos una estructura de memoria de datos.

Claims (17)

1. REIVINDICACIONES

   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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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

    10 ruta establecida en la red.
17. 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.

    15 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.