ES2374687T3 - Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red. - Google Patents

Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red. Download PDF

Info

Publication number
ES2374687T3
ES2374687T3 ES08760631T ES08760631T ES2374687T3 ES 2374687 T3 ES2374687 T3 ES 2374687T3 ES 08760631 T ES08760631 T ES 08760631T ES 08760631 T ES08760631 T ES 08760631T ES 2374687 T3 ES2374687 T3 ES 2374687T3
Authority
ES
Spain
Prior art keywords
node
network
route
data
list
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
ES08760631T
Other languages
English (en)
Inventor
Michael Bahr
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Siemens AG
Siemens Corp
Original Assignee
Siemens AG
Siemens Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens AG, Siemens Corp filed Critical Siemens AG
Application granted granted Critical
Publication of ES2374687T3 publication Critical patent/ES2374687T3/es
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/28—Connectivity information management, e.g. connectivity discovery or connectivity update for reactive routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/26—Route discovery packet
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/246—Connectivity information discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/248—Connectivity information update

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Radio Relay Systems (AREA)

Abstract

Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red (MN), en la que se transmiten tramas de datos desde un nodo de origen (SN) a través de uno o varios nodos intermedios (IN) hasta un nodo de destino (DN), siendo el nodo de origen (SN), el o los distintos nodos intermedios (IN) y el nodo de destino (DN) nodos de red (MN) de la red de datos, caracterizado porque al transmitirse una trama de datos comprueban al menos algunos de los nodos de red (MN) que reciben la trama de datos, en base a una lista de precursores asociada al nodo de destino (DN) de la trama de datos, si el nodo de red (MN) que envía la trama de datos está contenido en la lista de precursores y en caso positivo se transmite la trama de datos a otro nodo de la red (MN) y en caso negativo se desecha la trama de datos o bien se realiza una rutina de tratamiento de faltas, una inscripción en la lista de precursores incluye una dirección de Media Access Control (control de acceso a medios), MAC, o una dirección de IP y un tiempo de validez de la inscripción, así como - una inscripción en la lista de precursores se borra cuando ha transcurrido el tiempo de validez de la inscripción.

Description

Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red
La invención se refiere a un procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red, en la que se transmiten tramas de datos desde un nodo de origen a través de uno o varios nodos intermedios hasta un nodo de destino, siendo el nodo de origen, el o los distintos nodos intermedios y el nodo de destino nodos de red de la red de datos.
La transmisión de tramas de datos entre el nodo de origen y el nodo de destino puede realizarse en redes de datos enmalladas básicamente a través de distintas rutas. Bajo ruta se entiende un cierto número de nodos de red dispuestos contiguos unos a otros y que en sus extremos presentan un enlace de datos con el nodo de origen y el nodo de destino. Para no dejar al azar la transmisión de las tramas de datos desde el nodo de origen hasta en el nodo de destino, se envía desde el nodo de origen un llamado mensaje de solicitud de ruta (el llamado route request) a todos los nodos de red contiguos (el llamado broadcast), que retransmiten el mensaje de solicitud de ruta igualmente en el marco de un broadcast a sus nodos de red contiguos, hasta que el mensaje de solicitud de ruta finalmente alcanza el nodo de destino. El nodo de destino inicia un mensaje de respuesta de ruta (el llamado route reply). En la transmisión del mensaje de solicitud de ruta y en la transmisión de retorno selectiva del mensaje de respuesta de ruta (el llamado unicast) al nodo de origen, se crean sobre cada nodo de red inscripciones en las llamadas tablas de elección de ruta (las llamadas tablas de routing o enrutamiento). De esta manera resulta una ruta definida para la transmisión de tramas de datos entre el nodo de origen y el nodo de destino.
En el marco de la presente invención se entiende por lo tanto bajo ruta o ruta de datos (en inglés: route) la transmisión de tramas de datos a través de uno o varios nodos intermedios determinados entre el nodo de origen y el nodo de destino. Las tramas de datos que se transmiten desde el nodo de origen hasta el nodo de destino a lo largo de la ruta de datos se transmiten sobre una ruta de avance (la llamada forward route). Cuando se transmiten tramas de datos desde el nodo de destino al nodo de origen, esto se denomina en la siguiente descripción ruta de retorno (la llamada reverse route).
En tales redes de datos inalámbricas enmalladas existe el problema de que algunas tramas de datos aisladas pueden conducirse incorrectamente entre el nodo de origen y el nodo de destino, con lo que resultan bucles o bucles de datos. Debido a ello se ve afectada la comunicación de datos entre el nodo de origen y el nodo de destino. La transmisión incorrecta de tramas de datos puede presentarse en todos los protocolos de transmisión conocidos (los llamados routing protocols). La formación de tales bucles de datos indeseados puede resultar debido a nodos de red defectuosos o aleatoriamente o malintencionadamente durante la transmisión de tramas de datos a un nodo de red que se encuentra sobre la ruta en la dirección de transmisión antes del nodo de red transmisor. En la formación de bucles se retransmiten la o las tramas de datos a un nodo de red que se encuentra, en la dirección de avance sobre la ruta, más cerca del nodo de origen. Como resultado puede reducirse así la anchura de banda disponible en la red.
Para evitar el transporte continuo de una trama de datos conducida incorrectamente, se conoce la integración en latrama de datos de una información sobre el tiempo de validez. Ésta se realiza por ejemplo en paquetes de datos según el protocolo de Internet (IP) y en paquetes de datos según la especificación IEEE 802.11s. La información sobre el tiempo de validez se denomina time to live (tt1) o tiempo de vida. Se trata de un valor entero, que usualmente coloca el emisor de la trama de datos en 255. Con cada retransmisión de la trama de datos a un nuevo nodo de red se reduce el valor en 1. Tan pronto como el valor del tiempo de validez es 0, se desecha la trama de datos y ya no se retransmite en la red de datos.
Otro mecanismo de seguridad conocido es el llamado “source routing” (enrutamiento en base al origen). El receptor de una trama de datos puede entonces comprobar si el emisor (transmitter) de la trama de datos posee la autorización para retransmitir esta trama de datos al receptor. La comprobación se basa entonces en una información de ruta que está contenida en la trama de datos.
Además, se conoce la utilización de números secuenciales inequívocos en la transmisión de tramas de datos. De esta manera puede verificarse si determinadas tramas de datos ya han sido transmitidas. En base a los números secuenciales puede así deducirse que se ha formado un bucle cuando una trama de datos llega a un nodo de red por segunda vez o repetidamente.
Por el algoritmo Ad hoc On-demand Distance Vector Routing (AODV) (enrutamiento de vector de distancia sobre demanda ad hoc), tal como se describe para IP MANET Routing en RFC 3561, se conoce la utilización de las llamadas listas de precursores. Las listas de precursores se utilizan para notificaciones de falta de los nodos de red. Al respecto, se crea una lista de precursores tanto para la dirección de avance como también para la dirección de retorno de una ruta de datos. Esto se realiza durante el procesamiento del mensaje de respuesta de ruta, que fue enviado por el nodo de destino. Esta forma de proceder se basa en que ambos sentidos (sentido de avance y sentido de retorno) siguen la misma ruta. No obstante, las listas de precursores utilizadas en el marco del AODV no pueden evitar así que se presenten bucles.
Un documento García-Luna-Aceves J J y colab. “On-Demand Loop Free Routing with Link Vectors” (enrutamiento libre de bucles sobre demanda con vectores de enlace), IEEE Journal On Selected Areas In Communications, IEEE vol. 23, núm. 3, páginas 533-546, ISSN: 0733-8716 describe un protocolo On-Demand Link Vector (de vector de enlace sobre demanda), un protocolo de enrutamiento para redes ad hoc basado en las informaciones Link State (de estado del enlace), que están libres de bucles de enrutamiento y que apoyan una retransmisión de paquetes basada en el destino.
Es por lo tanto tarea de la invención proporcionar un procedimiento con el que puedan evitarse bucles de datos en la transmisión de tramas de datos en una red de datos inalámbrica enmallada. Otra tarea de la invención es proporcionar un procedimiento con el que la transmisión de tramas de datos en una red de datos inalámbrica enmallada permita una utilización lo más eficiente posible de los recursos puestos a disposición por la red de datos.
Estas tareas se resuelven mediante un procedimiento con las características de la reivindicación 1. Ventajosas formas de ejecución de reflejan en las reivindicaciones dependientes.
En el procedimiento correspondiente a la invención para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red, en el que se transmiten tramas de datos desde un nodo de origen a través de uno o varios nodos intermedios hasta un nodo de destino, son el nodo de origen, el o los distintos nodos intermedios y el nodo de destino nodos de red de la red de datos. En la transmisión de una trama de datos comprueban al menos algunos de los nodos de red que reciben la trama de datos, en base a una lista de precursores asociada al nodo de destino de la trama de datos, si el nodo de red que envía la trama de datos que está contenido en la lista de precursores. En caso positivo se transmite la trama de datos a otro nodo de la red. En caso negativo se desecha la trama de datos o bien se realiza una rutina de tratamiento de faltas.
La invención propone utilizar listas de precursores para detectar tramas de datos procedentes de nodos de red que no están autorizados o previstos para transmitir la correspondiente trama de datos. Las listas de precursores son listas con una indicación sobre nodos de red inmediatamente contiguos. De esta manera pueden evitarse bucles de datos en una red de datos inalámbrica enmallada. Al evitarse bucles de datos, puede evitarse desperdiciar una anchura de banda valiosa en la red de datos.
Para que puedan evitarse de manera fiable bucles de espera, deben comprobar los nodos de red si el nodo de red que envía la trama de datos está contenido en la lista de precursores. Es conveniente que la comprobación la realicen todos los nodos de red. La comprobación por parte del nodo de destino no es forzosamente necesaria.
También puede pensarse en una variante en la que se realice la comprobación de todos los nodos de red a excepción del nodo de origen y del nodo de destino y del nodo intermedio inmediatamente anterior al nodo de destino. Correspondientemente, tampoco se realizaría la comprobación en el nodo intermedio inmediatamente anterior al nodo de origen cuando el nodo de origen sea el destino de un mensaje (la llamada ruta de retorno).
Según una evolución, se establecen para el nodo de origen, el nodo de destino y el o los nodos intermedios respectivas tablas de elección de ruta (una llamada tabla de enrutamiento), incluyendo cada una de las tablas de elección de ruta al menos una inscripción. Para cada inscripción de la tabla de elección de ruta se establece la lista de precursores que incluye nodos directamente contiguos que pueden transmitir una trama de datos al correspondiente nodo de red. Para ello se fija para cada uno de los nodos de red desde qué nodos de red contiguos dentro de una ruta de datos pueden recibirse correctamente tramas de datos.
La creación de la tabla de elección de ruta se realiza en el marco de la transmisión de un mensaje de solicitud de ruta iniciado por el nodo de origen y de un mensaje de respuesta de ruta iniciado por el nodo de destino. Un mensaje de solicitud de ruta se denomina también mensaje Route Request. Un mensaje de respuesta de ruta lo conoce el especialista como mensaje Route Reply. Los mensajes de solicitud de ruta se envían como mensaje broadcast desde el nodo de origen. Contrariamente a ello, se realiza el mensaje de respuesta de ruta iniciado por el nodo de destino como mensaje unicast. En las tablas de elección de ruta se establecen inscripciones para el sentido de avance de una ruta de datos, así como también para el sentido de retorno de una ruta de datos. El sentido de avance de una ruta de datos se extiende desde el nodo de origen hasta el nodo de destino. El sentido de retorno está orientado, correspondientemente, desde el nodo de destino hasta el nodo de origen.
La creación y/o actualización de la lista de precursores se realiza según otra evolución en el marco del mensaje de respuesta de ruta iniciado por el nodo de destino.
Según otra evolución, incluye una trama de datos la dirección del nodo de origen, la dirección del nodo de destino, la dirección del nodo de red que envía esta trama de datos y la dirección del nodo de red que recibe esta trama de datos. El nodo de red que recibe la trama de datos comprueba si la dirección que tiene asignada se corresponde con la dirección del nodo de destino en la trama de datos. En caso positivo de la comprobación, se lleva la trama de datos a otra unidad para el procesamiento, en particular a una capa más elevada en el modelo de referencia OSI. Esto significa que la trama de datos ha alcanzado el nodo de destino.
Según otra evolución, incluye una inscripción en la lista de precursores una dirección de Media Accesss Control (de control de acceso a medios) (Media Access Control = MAC) o bien una dirección de IP y un tiempo de validez de la inscripción. Una lista de precursores es así una lista de direcciones MAC o IP. Los elementos de una lista de precursores son vecinos directos (nodos de red) del nodo de red que tienen permitido transmitir la trama de datos a este nodo de red. Esto resulta de que el nodo de red que transmite la trama de datos se encuentra respecto al correspondiente nodo de red en la ruta de datos hacia el nodo de destino. Entonces se crea una lista de precursores por cada inscripción en la tabla de elección de rutas. En muchos protocolos de enrutamiento esto equivale a una inscripción por cada nodo de destino, ya que por cada nodo de destino solamente hay una única inscripción en la tabla de enrutamiento. Como resultado esto significa que una lista de precursores puede tener para un nodo de destino n inscripciones, siendo n s [1, N]. N es la cantidad de orígenes que pueden tener rutas de datos activas sobre este nodo (N ; 1).
Además de la utilización de listas de precursores para detectar tramas de datos erróneamente conducidas, propone la invención una forma de proceder para crear y mantener actualizadas estas listas de precursores utilizadas para ello.
En la invención se memorizan como inscripciones en las listas de precursores pares de valores de una dirección MAC o IP y un tiempo de validez. El tiempo de validez de la inscripción es comparable al valor del tiempo de validez en el algoritmo del AODV. El principio básico reside en que el tiempo de validez de una inscripción de la lista de precursores de un nodo de red se repone a un valor de partida cuando este nodo de red recibe una trama de datos del nodo de red cuya dirección se corresponde con la dirección MAC en la inscripción. Los tiempos de validez se actualizan para inscripciones tanto en el sentido de avance como también en el sentido de retorno cuando también se actualizan los tiempos de validez de las inscripciones en las tablas de enrutamiento tanto en el sentido de avance como también en el sentido de retorno cuando se recibe la correspondiente trama de datos. Además, se borra una inscripción en la lista de precursores cuando el tiempo de validez de la inscripción ha transcurrido ya. De esta manera puede quedar asegurado que se ha minimizado el peligro de la formación de un bucle de datos.
El tiempo de validez de una inscripción en la lista de precursores es como máximo tan largo como un valor del tiempo de validez de la ruta desde el nodo de origen hasta el nodo de destino, estando contenido el valor del tiempo de validez de la ruta como información en la inscripción en las tablas de enrutamiento.
Según una evolución, la actualización del tiempo de validez de una inscripción en la lista de precursores y del valor del tiempo de validez de la ruta en la correspondiente inscripción en las tablas de enrutamiento, se realiza simultáneamente. Una actualización del tiempo de validez pueden por ejemplo realizarse también mediante mensajes de respuesta de ruta (mensajes Route Reply). Por el contrario no está previsto que los mensajes de solicitud de ruta (mensajes Route Request) realicen una actualización de las listas de precursores.
La razón para ello es como sigue: las listas de precursores se crean durante una llamada Route Discovery (descubrimiento de ruta), con la que debe fijarse la ruta de datos entre el nodo de origen y el nodo de destino. Los mecanismos básicos procedían al respecto de la especificación inicial relativa al AODV. Una publicación al respecto se encuentra en [1]. Entonces se complementa el procedimiento conocido por el estado de la técnica añadiendo tiempos de validez a las inscripciones de las listas de precursores. El mensaje de solicitud de ruta enviado por el nodo de origen a todos los nodos de red de la red de datos genera sentidos de retorno desde todos los nodos de red hacia el nodo de origen. Puesto que estas rutas de retorno se forman desde su final, es decir, desde el nodo de destino, se desconocen aún los nodos de red precedentes, con lo que por ello no puede inscribirse nada en la lista de precursores para la inscripción en las tablas de elección de ruta del nodo de red. El mensaje de respuesta de ruta que se transmite desde el nodo de destino hasta el nodo de origen utilizando un mecanismo unicast, da lugar por el contrario a que se generen inscripciones en las listas de precursores, tanto para la ruta de avance como también para la ruta de retorno. Las informaciones “destination_node” (nodo de destino) y “source_node” (nodo de origen) se toman entonces de los correspondientes campos del mensaje de respuesta de ruta.
Para rellenar la tabla de enrutamiento se realizan los siguientes pasos:
•
routingtable(destination_node).create;
•
routingtable(destination_node).lifetime.update (RREP.lifetime)
•
routingtable(destination_node).precursor_list.add (routingtable(source_node).next_hop, RREP.lifetime);
•
routingtable(source_node).precursor_list.add (weg-antwortnachricht.transmitter, routingtable(source_node).lifetime)
(donde routingtable = tabla de enrutamiento; destination = destino; node = nodo; create = crear; lifetime = tiempo de validez; update = actualización; precursor = precursor; list = lista; source = origen; next = siguiente; hop = salto; add = añadir; weg-antwortnachricht = mensaje de respuesta de ruta; transmitter = emisor).
La creación de una lista de precursores para la correspondiente inscripción en la tabla de enrutamiento no es necesaria en un tal nodo intermedio cuando el mismo, en una ruta de transmisión de tramas de datos entre el nodo de destino y el nodo de origen, es contiguo al nodo de origen o bien el mismo es contiguo al nodo de destino en una ruta de transmisión de tramas de datos entre el nodo de origen y el nodo de destino. No obstante, la creación de una lista de precursores también en estos casos simplifica y acelera el procedimiento.
Tanto el AODV como también el HWMP (Hybrid Wireless Mesh Protocol (protocolo híbrido inalámbrico de enmallamiento) permiten al nodo intermedio contestar a un mensaje de solicitud de ruta con un mensaje de respuesta de ruta cuando éstos conocen una ruta válida hasta el nodo de destino. En un tal caso deben realizarse las siguientes actualizaciones en las tablas de elección de ruta del nodo intermedio que genera el mensaje de solicitud de ruta. Al respecto se toman los campos “destination_node” y “source_node” de los correspondientes campos del mensaje de solicitud de ruta:
-
routingtable(destination_node).precursor_list.add (routingtable(source_node).next_hop, rooutingtable (destination_node).lifetime);
-
routingtable(source_node).precursor_list.add routingtable(destination_node).next_hop, routingtable (source_node).lifetime);
(donde routingtable = tabla de enrutamiento; destination = destino; node = nodo; precursor = precursor; lifetime = tiempo de validez; list = lista; source = origen; next = siguiente; hop = salto; add = añadir).
Cuando otro nodo de red que no es el nodo de origen, el nodo de destino ni uno de los nodos intermedios en una ruta de datos entre el nodo de origen y el nodo de destino, tras recibir un mensaje de solicitud de ruta del nodo de origen (pero ningún mensaje de respuesta de ruta) transmite una trama de datos al nodo de origen a través de otro nodo intermedio, nodo intermedio que es el siguiente nodo de red sobre una ruta de retorno hacia el nodo de origen, que no contiene en la lista de precursores de la inscripción de la tabla de enrutamiento para el nodo de origen el otro nodo de red, rechaza el otro nodo intermedio según una forma de ejecución las tramas de datos recibidas del otro nodo de red.
La ruta de datos formada entre el otro nodo de red y el nodo de red de origen, se señala según otra ejecución en el otro nodo de red como inválida. Para evitar el envío innecesario de tramas de datos desde el otro nodo de red hasta el nodo de red de origen, se marca una tal ruta, con lo que el otro nodo de red puede realizar un Route Discovery hacia el nodo de origen. Esto se realiza en lugar de la utilización de la ruta de retorno que se formó en el marco del Route Discovery entre el nodo de origen y el otro nodo de red.
En una configuración alternativa, se rellenan las listas de precursores para la ruta entre el otro nodo de red y el nodo de origen antes de que se transmita la trama de datos desde el otro nodo de red al nodo de origen. Esto puede realizarse por ejemplo enviando un mensaje de respuesta de ruta desde el otro nodo de red al nodo de origen.
En otra forma de configuración alternativa, al recibir un mensaje de solicitud de ruta se inscriben las direcciones de todos los nodos de red contiguos a un nodo de red juntamente con un valor de caducidad al recibir un mensaje de solicitud de ruta en la lista de precursores de este nodo de red como inscripción temporal.
Según otra evolución, no se inscribe entonces en la lista de precursores de este nodo de red el nodo de red contiguo al nodo de red que ha enviado el mensaje de solicitud de ruta.
Otra evolución prevé que la inscripción temporal en la lista de precursores esté dotada de un valor de caducidad (como por ejemplo un TTL, valor de Time-to-Live, tiempo de vida) en la cabecera (header) del protocolo de Internet, por ejemplo IPV4), que presenta el mismo valor que la ruta de retorno que se estableció mediante el mensaje de solicitud de ruta.
En otra evolución opcional pueden borrarse las inscripciones temporales de la lista de precursores cuando se crea una inscripción en la lista de precursores en el marco del mensaje de respuesta de ruta iniciado por el nodo de destino.
El mismo problema existe también con mensajes de solicitud de ruta proactivos en una ampliación proactiva para el llamado Tree Routing (árbol de enrutamiento) en el HWMP. El árbol unidireccional desde el nodo de partida (root tree) se activa mediante un mensaje de solicitud de ruta, transmitiéndose el mensaje de solicitud de ruta a todos los nodos de red conectados con el nodo de partida. Esta forma de proceder genera la ruta de retorno hacia el nodo de red de partida, pero no puede generarse entonces la lista de precursores. El HWMP utiliza entonces una solución similar a la propuesta por la invención. Cuando está activado un flag (indicador) proactivo del mensaje de respuesta de ruta, se envía un mensaje de respuesta de ruta como reacción a un mensaje de solicitud de ruta. De esta manera puede rellenarse la lista de precursores como es usual. Cuando el flag proactivo del mensaje de respuesta de ruta no está activado, puede enviarse un mensaje de respuesta de ruta antes de la trama de datos, con lo que la lista de precursores se crea “just in time” (en el momento preciso).
La invención implica un mecanismo simple para detectar tramas de datos incorrectamente enrutadas, para evitar la generación de bucles de datos debido a una retransmisión intencionada o defectuosa. Esto se realiza utilizando listas de precursores para detectar las tramas de datos incorrectamente enrutadas. Entonces se compara el emisor de la trama de datos con los antecesores (= emisores o transmitters) permitidos que se encuentran en la lista de precursores. La invención amplia entonces el mecanismo de listas de precursores, tal como se especifica el mismo para el AODV. Una inscripción lleva asociado un tiempo de validez en la lista de precursores, con lo que el contenido de la lista de precursores se corresponde ahora con la ruta de datos activa en la red de datos inalámbrica enmallada.
La invención se describirá a continuación más en detalle con referencia a las figuras. Se muestra en:
figura 1 una red de datos enmallada con un conjunto de nodos de red, en base a la cual se describirá el
procedimiento que sirve de base a la invención, figura 2 una representación de la que se deducen las definiciones de conceptos utilizadas en la descripción, figuras 3-8 respectivas tablas de enrutamiento para los nodos de red mostrados en la figura 1, describiéndose el
rellenado de las tablas de enrutamiento, así como de las listas de precursores allí contenidas al
establecerse una ruta de datos entre dos de los nodos de red de la red de datos de la figura 1, y figura 9 la leyenda de las designaciones utilizadas en las figuras 3 a 8.
La figura 1 muestra modo de ejemplo una red de datos enmallada con un conjunto de nodos de red MN. Los nodos de red MN están conectados en parte entre sí mediante tramos de comunicación KS para el intercambio de datos. Los tramos de comunicación KS están configurados inalámbricos. Cada uno de los nodos de red MN lleva asignada una dirección inequívoca, en base a la cual es posible una transmisión de tramas de datos desde un nodo de origen hasta un nodo de destino. En la figura 1 se designan las direcciones de los nodos de red MN con las referencias S, B, A, C, D, F y G. La transmisión de una trama de datos de un nodo de red MN a un nodo de red MN contiguo a través del tramo de comunicación KS se señala mediante una flecha. La transmisión de tramas de datos desde un nodo de origen de la red de datos hasta un nodo de destino de la red de datos a través de uno o varios nodos intermedios, estando formados el nodo de origen, el nodo de destino y los nodos intermedios por nodos de red de la red de datos, se realiza hop-by-hop (a saltos), es decir, de un nodo de red a otro nodo de red.
Si por ejemplo deben transmitirse tramas de datos desde el nodo de origen S hasta el nodo de destino D de la red de datos de la figura 1, entonces debe primeramente determinarse una ruta de datos en la que se determinen los nodos intermedios situados entre el nodo de origen S y el nodo de destino D (en el ejemplo de ejecución los nodos de red B, A y C), estando asignadas al correspondiente nodo de red tablas de elección de ruta. En la siguiente descripción se denominan las tablas de elección de ruta tablas de enrutamiento. Éstas están dotadas en la figura 1 de la referencia RT. En el ejemplo de ejecución representado incluye una inscripción en la tabla de enrutamiento RT tres valores. El primer valor indica la dirección del nodo de destino. El segundo valor representa una métrica de ruta, que equivale a la cantidad de hops (saltos) hasta el nodo de destino a alcanzar. El tercer valor representa la dirección del nodo de red al que debe transmitirse la trama de datos como siguiente paso. Al mismo se le denomina también “next hop”.
La determinación de la ruta de datos se realiza mediante un llamado “route discovery” (descubrimiento de ruta), que se conoce desde hace mucho tiempo por el funcionamiento de una red de datos inalámbrica enmallada. Para ello genera el nodo de origen S un mensaje de solicitud de ruta y se transmite a todos los nodos de red unidos con el nodo de origen. Este procedimiento de transmisión denominado broadcast se realiza igualmente desde los nodos intermedios que han recibido un tal mensaje de solicitud de ruta, denominado a continuación mensaje route request o bien route request. Cuando recibe el nodo de destino D un tal mensaje route request, entonces contesta el mismo con un mensaje de respuesta de ruta, denominado a continuación route reply o mensaje route reply. No obstante, contrariamente al mensaje route request se transmite éste selectivamente al nodo de origen S. Esto se denomina también unicast.
En el marco del route discovery pueden crearse y rellenarse las tablas de enrutamiento de los correspondientes nodos intermedios en una ruta de datos.
La figura 2 muestra una convención usual en la descripción de redes de datos enmalladas. Para simplificar se ha tomado como base al respecto que el nodo de origen SN está unido a través de solamente un nodo intermedio IN con el nodo de destino DN. Entre el nodo de origen SN y el nodo intermedio IN o bien entre el nodo intermedio IN y el nodo de destino DN están configurados respectivos tramos de comunicación inalámbricos KS. Los nodos de red SN, IN y DN se encuentran en una ruta de datos DP a través de la que se transmiten las tramas de datos. La ruta de datos DP se ha determinado mediante el procedimiento route discovery antes descrito. Las tramas de datos que se transmiten desde el nodo de origen SN hasta el nodo de destino DN se transmiten en el sentido de avance o bien sobre una ruta de avance FR. Las tramas de datos que se transmiten desde el nodo de destino DN hasta el nodo de origen SN, se transmiten en el sentido de retorno o sobre una ruta de retorno RR. A continuación nos referiremos a esta convención.
En la siguiente descripción breve de la problemática en base a la figura 1 se parte de que la ruta de datos entre el nodo de red S como nodo de origen y el nodo de red D como nodo de destino es como sigue: S-B-A-C-D. Otra ruta de datos debe estar formada entre el nodo de red G como nodo de origen y el nodo de red D como nodo de destino. La ruta de datos para ello es por ejemplo: G-F-B-A-C-D.
El nodo de red B, que es un nodo intermedio, presenta una inscripción en la tabla de enrutamiento en la que está contenido como nodo de destino el nodo de red D. Hasta alcanzar el nodo de red D son necesarios tres saltos (hops), debiéndose transmitir una trama de datos recibida por B al nodo de red A (igualmente un nodo intermedio). De la manera correspondiente presenta el nodo de red A una inscripción en la tabla de enrutamiento en la que está contenido el nodo de red D como nodo de destino. Hasta alcanzar el nodo de red D son necesarios dos saltos, debiendo transmitirse una trama de datos recibida por A al nodo de red C (un nodo intermedio). De la manera correspondiente presenta el nodo de red C una inscripción en la tabla de enrutamiento en la que está contenido el nodo de red D como nodo de destino. Hasta alcanzar el nodo de destino D es necesario un salto, debiendo transmitirse una trama de datos recibida por C al nodo de red D (el nodo de destino). Cuando recibe el nodo de red F (igualmente un nodo intermedio) una trama de datos para el nodo de destino D, entonces recibe éste de una inscripción en la tabla de enrutamiento la información de que hasta el nodo de destino han de realizarse cuatro saltos. Las tramas de datos recibidas por el nodo de red F deben retransmitirse al nodo de red B.
En un comportamiento incorrecto del nodo de red A, que puede ser intencionado o por error, puede suceder que se transmitan tramas de datos no al nodo de red C, sino al nodo de red F. Esto puede venir apoyado por ejemplo por las informaciones del mensaje de solicitud de ruta que ha recibido el nodo de red A del nodo de red F. De ello resulta el bucle de datos señalado en la figura 1 con la flecha de trazo discontinuo. El nodo de red F retransmitirá precisamente, en base a su inscripción en la tabla de enrutamiento, la trama de datos a B, que a su vez transmite la trama de datos a
A.
Puesto que esta formación de bucles cuesta una valiosa anchura de banda en una red de datos inalámbrica enmallada, se complementan en la invención las inscripciones en la tabla de enrutamiento en cada caso con una lista de precursores. Previendo las listas de precursores, pueden detectarse tramas de datos de aquellos nodos de red que no tienen autorización para enviar las mismas al nodo de red que recibe los datos. De esta manera pueden evitarse bucles de datos.
Cada lista de precursores creada por cada inscripción en la tabla de enrutamiento es una lista de direcciones de Media Access Control (control de acceso a medios), MAC. Los elementos de la lista de precursores son nodos de red directos contiguos al nodo de red que presenta una lista de precursores que correspondientemente transmiten a través de las rutas determinadas por el protocolo de enrutamiento tramas de datos a este nodo de red. Una lista de precursores de una inscripción en la tabla de enrutamiento de un nodo de red puede presentar así n s [1, N] inscripciones, siendo N la cantidad de nodos de origen que tienen una ruta de datos activa a través del correspondiente nodo.
En el estándar IEEE 802.11s (WLAN Mesh Networking, red enmallada WLAN) se define un formato para tramas de datos que incluye seis direcciones. La trama de datos allí definida incluye entre otros la dirección del nodo de red que transmite la trama de datos (transmitter address, dirección del emisor). Este nodo de red es el nodo de red precedente (hop) en la ruta de datos. Este es así, en otras palabras, el precedente o precursor. Esta dirección, es decir la dirección del emisor, se compara con la dirección que está contenida en la lista de precursores sobre la ruta hacia el nodo de destino deseado. Cuando el nodo receptor es el nodo de destino, ya no necesita realizarse la comparación, ya que la transmisión de una trama de datos al nodo de destino no dará lugar a ningún bucle de datos.
Para realizar el procedimiento se necesitan tres direcciones, la dirección del nodo de destino, la dirección del nodo de red que transmite la trama de datos, así como la dirección del nodo de red que recibe la trama de datos. Tal como se ha indicado, se realiza la comparación de si la dirección de destino se corresponde con la dirección del nodo de red que recibe la trama de datos. Si es éste el caso, entonces se lleva la trama de datos recibida a una capa de procesamiento más elevada. Si no corresponde la dirección de destino a la del nodo de red que recibe la trama de datos, entonces se comprueba si la dirección del nodo de red emisor (transmitter) está contenida en la lista de precursores de la inscripción en la tabla de enrutamiento para el nodo de destino. Si es éste el caso, entonces se ha transmitido correctamente la trama de datos. El nodo de red que recibe la trama de datos transmite ésta a continuación al nodo de red que está contenido en la correspondiente inscripción en la tabla de enrutamiento como next hop (siguiente salto). En el caso de una comprobación negativa, se considera la trama de datos como transmitida incorrectamente, ya que el emisor no es el nodo precedente sobre la ruta de datos y por lo tanto no debería haber transmitido la trama de datos a este vecino. Por lo tanto, la trama de datos bien se desecha o bien se lleva a una rutina de tratamiento de faltas.
Las inscripciones de las listas de precursores se complementan además con un valor de tiempo de validez (life time). Una inscripción en esta lista de precursores contiene así el par de valores (dirección MAC, tiempo de validez). El complemento con los valores del tiempo de validez posibilita una correspondencia de las listas de precursores con las rutas de datos activas en la red de datos. Con otras palabras, queda así asegurado que las inscripciones en las listas de precursores también están previstas sólo para rutas de datos activas.
Cuando ha transcurrido el tiempo de validez de una inscripción en la lista de precursores, se borra la correspondiente inscripción de la lista de precursores. La comprobación o actualización de un valor del tiempo de validez se realiza siempre que se reciba una trama de datos en un nodo de red y exista la correspondiente inscripción en la lista de precursores. El tiempo de validez de las inscripciones en las listas de precursores pueden entonces actualizarse en ambos sentidos, es decir, en el sentido de avance y en el sentido de retorno de la ruta de datos. Esto se corresponde con la forma de proceder descrita en AODV/HWMP.
El nuevo valor de una inscripción relativa a un tiempo de validez es el valor máximo posible del tiempo de validez. Convenientemente ningún valor del tiempo de validez de una inscripción en una lista de precursores es mayor que el correspondiente de tiempo de validez de la ruta de datos. Básicamente se realiza una actualización de un valor del tiempo de validez en la lista de precursores juntamente con la actualización del valor del tiempo de validez de una inscripción en la tabla de enrutamiento. Los valores del tiempo de validez de las inscripciones en la lista de precursores se actualizan también cuando discurren mensajes route reply a través de los correspondientes nodos de red. Los mensajes route request no se ocupan por el contrario de una actualización de la inscripción del tiempo de validez en la lista de precursores.
Las listas de precursores asociadas a las inscripciones en las tablas de enrutamiento se generan igualmente en el marco del route discovery. Entonces puede presentarse un caso especial durante el proceso de route discovery. Cuando el nodo de origen S desea comunicar con el nodo de destino D, se inicia mediante el nodo de origen S un route discovery, con lo que se transmitirá un mensaje route request a todos los nodos de red de la red de datos. El mensaje route request genera rutas de retorno desde todos los nodos de red hacia el nodo de origen S. No obstante, tal como se ha indicado al principio, se forma sólo una única ruta de datos entre el nodo de origen S y el nodo de destino D, sobre la cual el nodo de destino D envía de retorno un route reply. Este mensaje route reply da lugar a que se generen la listas de precursores en el nodo de red, realizándose esto solamente en aquellos nodos de red que se encuentran sobre la ruta de datos entre S y D. La ruta de datos es, tal como se indica al principio, S-B-A-C-D. No obstante, en los otros nodos de red, en el ejemplo de ejecución los nodos de red F y G, no se generan tales listas de precursores en las correspondientes inscripciones de las tablas de enrutamiento. Pese a ello, es efectivamente válida una ruta de retorno desde el nodo de red G hasta el nodo de origen S.
Cuando el nodo de red G transmite una trama de datos al nodo de red S sobre esta ruta de retorno, envía el mismo una trama de datos al siguiente nodo de red, que en el ejemplo de ejecución es el nodo de red F. Desde luego no dispone el nodo de red F, que se encuentra contiguo al nodo de red G, de ninguna inscripción en la lista de precursores para el nodo de red G. Por ello se desechan las tramas de datos transmitidas por G en el nodo de red F, aún cuando las mismas se han transmitido sobre una ruta de por sí válida.
Para solucionar este problema, se dispone de tres posibilidades:
1.
La ruta de retorno formada entre G y S se considera ruta inválida. Para evitar un envío inútil de tramas de datos, debe marcarse correspondientemente esta ruta, con lo que el nodo de red G puede iniciar un route discovery hacia el nodo de red S, en vez de utilizar la ruta de retorno hacia S que había iniciado el route discovery iniciado por S.
2.
Pueden generarse listas de precursores, transmitiéndose un mensaje de route reply a S antes de transmitirse las tramas de datos propiamente dichas desde G hasta S.
3.
Alternativamente pueden insertarse las direcciones de todos los nodos de red contiguos en la lista de precursores para la ruta de retorno. Esto no es necesario para el nodo de red que ha enviado el mensaje de route request. Para el nodo de red F se trataría de los nodos de red contiguos A y G. El nodo de red contiguo B no necesita incluirse en la lista de precursores, ya que el mismo ha enviado el mensaje de route request. Estas inscripciones se dotan de un time out (tiempo de espera), que presenta el mismo valor, que la ruta de retorno que se estableció mediante el mensaje de route request. Esta sencilla solución tiene no obstante el inconveniente de que resulta un corto espacio de tiempo durante el route discovery durante el cual no existe ninguna protección frente a la formación de bucles de datos.
En las siguientes figuras 3 a 8 se describirá ahora cómo se generan las inscripciones en las tablas de enrutamiento con las correspondientes listas de precursores asociadas, realizándose esto en la red de datos representada en la figura 1. La figura 9 muestra, para mejor entendimiento, una leyenda para las denominaciones elegidas en las figuras 3 a 8.
Una tabla de enrutamiento RT incluye cinco inscripciones: la dirección de un nodo de destino (“destination”), la cantidad de nodos intermedios (“distance (hops)”) que se encuentran hasta el nodo de destino en la ruta de datos, la dirección del siguiente nodo de red (“next hop”), un valor de tiempo de validez para la inscripción en la tabla de enrutamiento (“time out (life time)”), así como una lista de precursores, incluyendo cada inscripción en la lista de precursores la dirección de un nodo de red, así como una inscripción sobre el tiempo de validez (“precursor list (node, life time)”).
En el marco de la descripción se utilizan dos tipos de mensajes NT. Con RREQ se designa una route request o mensaje de solicitud de ruta. Con RREP se designa un mensaje de route reply o mensaje de respuesta de ruta. Ambos mensajes de enrutamiento RN incluyen los siguientes valores: instante (“time/at”), dirección del nodo de red emisor (“transmitter”), dirección del nodo de red de origen (“source”), dirección del nodo red de destino (“destination”), cantidad de lodos de red hasta el nodo de destino (“hop count”), tiempo de validez (“life time”).
En la figura 3 se representa en las etapas S1 a S6 la estructura de una ruta de datos entre el nodo de red G como nodo de origen y el nodo de red D como nodo de destino. Entonces resulta especialmente claro cómo tras enviar el nodo de origen G un mensaje de route request se generan las tablas de enrutamiento de cada nodo de red S, B, A, C, D, F y G. Los campos resaltados en las distintas tablas muestran el emisor del mensaje de route request y aquellos campos de una tabla de enrutamiento que debido a un procesamiento del mensaje de route request han ocasionado una variación.
En la etapa S1 envía el nodo de red G un mensaje de route request RREQ. El nodo de red G es así el transmitter (emisor) del mensaje. Simultáneamente es G el nodo de origen de la red de datos, con lo que en el campo “source” igualmente está inscrito G. Como destino incluye el mensaje de route request el nodo de red D (destination). Puesto que el emisor y el origen del mensaje son idénticos, se registra para el valor hop count 0. Como valor del tiempo de validez se elige arbitrariamente el valor 8. En las correspondientes tablas de enrutamiento de los nodos de red G y F puede observarse que G es el emisor del mensaje. En la tabla de enrutamiento del nodo de red F, que recibe el mensaje de route request RREQ de G, se memorizan informaciones relativas a la ruta de retorno. Como destino (destination) se registra por lo tanto la dirección del nodo de red G, ya que éste es el nodo de origen del mensaje de route request. La distancia hasta éste es de un hop (salto). Para llegar al destino de la ruta de retorno, el origen, debe alcanzarse como siguiente nodo (next hop) el nodo G. Como tiempo de validez para la inscripción en la tabla de enrutamiento para la ruta de retorno hasta el nodo de red G, se eligen del mensaje de route request las 8 unidades de tiempo.
En la etapa S2 se envía el mensaje de route request RREQ a los nodos de red unidos mediante tramos de comunicación KS con el nodo de red F. En el ejemplo de ejecución de la figura 1 éstos son los nodos de red B, A y G. El mensaje de route request RREQ contiene las siguientes informaciones: emisor, es decir, transmitter, del mensaje es el nodo de red F. El mensaje de route request RREQ fue iniciado por el nodo de origen G, con lo que éste está inscrito en el campo Source. El destino sigue siendo el nodo de destino D, con lo que el mismo está inscrito en el campo Destination. Los nodos de red F y G están alejados entre sí en un hop count. El tiempo de validez permanece en el valor 8 fijado. En cada nodo de red B, A y G que recibe el mensaje de route request de F, se colocan respectivas inscripciones en la tabla de enrutamiento: en los nodos de red B y A tanto para el nodo de red emisor F como también para el nodo de origen G y en el nodo de red G sólo para el nodo de red emisor F. La distancia al destino de la ruta de retorno (source) se adapta al valor 2.
De esta manera se sigue transportando el mensaje de route request RREQ hasta que éste alcanza finalmente en la etapa S6 el nodo de destino D. El nodo de red D presenta dos inscripciones en la tabla de enrutamiento, de las cuales una contiene informaciones para el nodo de red C como destino y otra para el nodo de red G como destino.
En la figura 4 se representan en las etapas S7 a S11 mensajes de route reply, enviados por el nodo de destino D. Aquí es el nodo de origen G receptor del mensaje de route reply. Aquí puede deducirse de las correspondientes tablas de enrutamiento que para varias de las inscripciones en la tabla de enrutamiento se ha inscrito una lista de precursores que incluye la dirección del nodo de red precedente en la ruta de datos, así como un valor del tiempo de validez.
El envío del mensaje de route reply se realiza mediante el nodo de red D. La transmisión del mensaje de route reply se realiza al nodo de red contiguo C. En el campo "source" sigue estando el nodo de red G, que ha iniciado el mensaje de route request. El nodo de destino sigue siendo el nodo de red D, con el que el nodo de red G desearía establecer una ruta de datos. Los hop counts se cuentan desde el punto de vista del emisor del mensaje de route reply, con lo que el valor es 0. El tiempo de validez está colocado en función del tiempo de validez del mensaje de route request en 8, pero básicamente puede elegirse arbitrariamente. El nodo de red C que recibe el mensaje de route reply del nodo de red D puede ahora colocar una nueva inscripción en la tabla de enrutamiento para el nodo de red D. Por otro lado, puede colocarse para las inscripciones en la tabla de enrutamiento en relación con los nodos de red G y D (en cada caso destination o destino) una inscripción en la lista de precursores. Si debe enviarse un mensaje desde el nodo de red C al nodo de red G como destino, entonces es el nodo de red D el precedente en la ruta de datos. Si por el contrario debe enviarse desde el nodo de red G una trama de datos al nodo de red D como receptor, entonces es el nodo de red A el precedente en la ruta de datos. Esta información puede tomarse de la inscripción en la tabla de enrutamiento relativa al nodo de red G como receptor, ya que aquí A esta contenido como next hop (salto siguiente).
De la manera correspondiente se transporta el mensaje de route reply desde el nodo de red C al nodo de red A y desde éste al nodo de red B, así como finalmente al nodo de red F y a continuación al nodo de red G. Aquí se completan en cada caso de la manera descrita las inscripciones en la tabla de enrutamiento y se generan las correspondientes listas de precursores.
Una forma de proceder correspondiente a las figuras 3 y 4 se describe en la figura 5 en relación con la figura 6, así como en la figura 7. No obstante, entonces se envió un mensaje de route request desde el nodo de red S como nodo de origen, estando determinado el nodo de red D como nodo de destino. Tal como por ejemplo se deduce del paso S13 de la figura 5, el tiempo de validez de las inscripciones en la tabla de enrutamiento generadas y actualizadas con este mensaje de route request, es otro (tiempo 11 en lugar de tiempo 8). Al considerar las etapas S18 a S21, se observa
además que en varias inscripciones en la tabla de enrutamiento (ver comparativamente por ejemplo la etapa 20, inscripción en la tabla de enrutamiento para el nodo de red D) la lista de precursores está complementada con una inscripción adicional. Al respecto muestra la etapa S21 en la figura 7 las tablas de enrutamiento definitivas de todos los nodos de red de la red de datos de la figura 1 a modo de ejemplo. En el caso de que ahora, tal como se ha descrito en relación con la figura 1, el nodo de red A envíe incorrectamente datos destinados al nodo de red D al nodo de red F en lugar de al nodo de red C, entonces se desechan estas tramas de datos, con lo que se evita que se presenten bucles de datos.
Las consecuencias del procedimiento correspondiente a la invención se pondrán de relieve claramente de nuevo en base a la siguiente ejecución. Al respecto se utilizan las siguientes abreviaturas:
RA dirección de un nodo de red receptor (“receiver address”) TA dirección del nodo de red que envía una trama de datos (“transmitter address”), DA dirección del nodo de destino (“destination address”) SA dirección desde la que se envió inicialmente la trama de datos (“source address”).
Respecto al nodo de red A:
Etapa 1: El nodo de red A recibe una trama de datos con RA = A, TA=B, DA = D, SA = G ó S; Etapa 2: el nodo de red A no es el destino de la trama de datos (A " D), es decir, la dirección del nodo de destino no se corresponde con la dirección del nodo de red, Etapa 3: la trama de datos se recibió correctamente, ya que el nodo de red emisor B está en la lista de precursores de la inscripción en la tabla de enrutamiento para el nodo de destino D: ([D-2-C-11] – (B, 11)]).
Se supone además que el nodo de red A ha de retransmitir la trama de datos a C (la inscripción en la tabla de enrutamiento para el nodo de red D es: ([D-2-C-11] – (B, 11)]). En realidad se supone que el nodo de red A transmite la trama de datos incorrectamente al nodo de red F.
Respecto al nodo de red F:
Etapa 1: El nodo de red F recibe una trama de datos con: RA = F, TA = A, DA = D, SA = G ó S; Etapa 2: el nodo de red F no es el nodo de destino de la trama de datos (F " D), Etapa 3: la trama de datos se recibió incorrectamente, ya que el emisor (transmitter) B no está en la lista de precursores
de la inscripción en la tabla de enrutamiento para el nodo de destino D: ([D-4-B-8] – (G, 8)]). Esto trae como consecuencia que la trama de datos se deseche.
La invención impide así la formación de bucles de datos cuando un nodo de red defectuoso transmite una trama de datos de retorno al nodo de red del que la recibe.
Supongamos que el nodo de red B de la figura 1 envía de retorno al nodo de red S ó F tramas de datos destinadas al nodo de red D. Tanto S como también F, tienen rutas útiles hacia el nodo de red D, siendo el nodo de red B el siguiente nodo de destino, es decir, el siguiente hop (salto).
Respecto al nodo de red B:
Etapa 1: El nodo de red B recibe una trama de datos con RA = B, TA = S ó F, DA = D, SA = S ó G; Etapa 2: el nodo de red B no es el destino de la trama de datos (B " D), Etapa 3: la trama de datos se recibió correctamente, ya que el emisor S ó F está en la lista de precursores de la
inscripción en la tabla de enrutamiento para el nodo de destino D: ([D-3-A-11] – (F, 8) (S, 11]).
El nodo de red B estaría equipado para transmitir tramas de datos al nodo de red A. Esto resulta de la inscripción en la tabla de enrutamiento para el nodo de red: ([D-3-A-11] – (F, 8) (S, 11]). Se supone en el ejemplo de ejecución que la trama de datos se transmite incorrectamente al nodo de red F ó S.
Respecto al nodo de red S:
Etapa 1: El nodo de red S recibe una trama de datos con RA = S, TA = B, DA = D, SA = S ó G; Etapa 2: el nodo de red S no es el destino para la trama de datos (S " D), Etapa 3: la trama de datos se recibió incorrectamente, ya que el emisor B no está en la lista de precursores de la
inscripción en la tabla de enrutamiento para el nodo de red D: ([D-4-B-11 – ()]). Esto trae como consecuencia que la trama de datos se deseche.
Respecto al nodo de red F:
Etapa 1: El nodo recibe una trama de datos con RA = A, TA = B, DA = D, SA = S ó G;
Etapa 2: el nodo de red F no es el destino de la trama de datos (F " D), Etapa 3: la trama de datos se recibió incorrectamente, ya que el emisor B no está en la lista de precursores de la inscripción en la tabla de enrutamiento para el nodo de red D: ([D-4-B-8] – (G, 8)]).
5 Por lo tanto, la trama de datos se desecha.
En la figura 8 se representa además la actualización permanente de las listas de precursores de rutas de datos que se solapan. Puede deducirse por ejemplo de las tablas de enrutamiento de los nodos de red S, B, A, C, D, F y G que al haber transcurrido el tiempo de validez de inscripciones en la tabla de enrutamiento se borran las correspondientes 10 inscripciones en la lista de precursores. Esto se representa mediante las inscripciones resaltadas, vacías en la tabla. Al transcurrir el tiempo de validez de una inscripción en la tabla de enrutamiento, se eliminan por sí mismas tanto la inscripción en la tabla de enrutamiento como también la inscripción en la lista de precursores. En el ejemplo de ejecución se ha supuesto que la ruta de datos entre los nodos de red G y D ya se ha recorrido. No obstante, la ruta de datos hacia el nodo de destino D en los nodos de red B, A y C no se recorre, ya que aquí existe aún una ruta de datos
15 activa entre los nodos de red S y D. El nodo de red B presenta precursores para su ruta de datos hacia D. precisamente uno para la ruta de datos entre G y D y uno para la ruta de datos entre S y D. Entonces se recorre solamente la primeramente citada y se borra de la lista de precursores.
Literatura
[1] C. E. Perkins, E.M Belding-Royer, S.R. Das: Ad hoc On-demand Distance Vector (AODV) Routing (Enrutamiento de vector de distancia ad hoc sobre demanda), IETF Experimental RFC 3561, julio 2003.

Claims (18)

  1. REIVINDICACIONES
    1. Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red (MN), en la que se transmiten tramas de datos desde un nodo de origen (SN) a través de uno o varios nodos intermedios (IN) hasta un nodo de destino (DN), siendo el nodo de origen (SN), el o los distintos nodos intermedios (IN) y el nodo de destino (DN) nodos de red (MN) de la red de datos, caracterizado porque al transmitirse una trama de datos comprueban al menos algunos de los nodos de red (MN)
    que reciben la trama de datos, en base a una lista de precursores asociada al nodo de destino (DN) de la trama de datos, si el nodo de red (MN) que envía la trama de datos está contenido en la lista de precursores y en caso positivo se transmite la trama de datos a otro nodo de la red (MN) y en caso negativo se desecha la trama de datos
    o bien se realiza una rutina de tratamiento de faltas, una inscripción en la lista de precursores incluye una dirección de Media Access Control (control de acceso a medios), MAC, o una dirección de IP y un tiempo de validez de la inscripción, así como
    -
    una inscripción en la lista de precursores se borra cuando ha transcurrido el tiempo de validez de la inscripción.
  2. 2. Procedimiento según la reivindicación 1, en el que
    -
    para el nodo de origen (SN), el nodo de destino (DN) y el o los nodos intermedios (IN) se establece en cada caso una tabla de elección de ruta (RT), incluyendo cada tabla de elección de ruta (RT) al menos una inscripción y
    -
    para cada inscripción de la tabla de elección de ruta (RT) se establece la lista de precursores, que incluye nodos directamente contiguos que pueden transmitir una trama de datos al correspondiente nodo de red (MN).
  3. 3.
    Procedimiento según la reivindicación 2, en el que la creación de la tabla de elección de ruta (RT) se realiza en el marco de la transmisión de un mensaje de solicitud de ruta iniciado por el nodo de origen (SN) y de un mensaje de respuesta de ruta iniciado por el nodo de destino (DN).
  4. 4.
    Procedimiento según una de las reivindicaciones precedentes, en el que la creación o actualización de la lista de precursores se realiza en el marco del mensaje de respuesta de ruta iniciado por el nodo de destino (DN).
  5. 5.
    Procedimiento según una de las reivindicaciones precedentes, en el que una trama de datos incluye la dirección del nodo de destino (D), la dirección del nodo de red que envía esta trama de datos, la dirección del nodo de red que recibe esta trama de datos y opcionalmente la dirección del nodo de origen (S), comprobando el nodo de red que recibe la trama de datos si la dirección que se le ha asignado se corresponde con la dirección del nodo de destino en la trama de datos y si el resultado de la comprobación es positivo, conduce la trama de datos a otra unidad para el procesamiento, en particular a una capa más elevada en el modelo de referencia OSI.
  6. 6.
    Procedimiento según una de las reivindicaciones precedentes, en el que en el que el tiempo de validez de una inscripción en la lista de precursores de un nodo de red se repone a un valor inicial cuando este nodo de red recibe una trama de datos del nodo de red cuya dirección se corresponde con la dirección MAC ó IP en la inscripción.
  7. 7.
    Procedimiento según una de las reivindicaciones precedentes, en el que el tiempo de validez de una inscripción en la lista de precursores tiene como máximo la longitud de un valor del tiempo de validez de la ruta desde el nodo de origen hasta el nodo de destino, estando contenido el valor del tiempo de validez de la ruta como información en la inscripción en la tabla de enrutamiento.
  8. 8.
    Procedimiento según la reivindicación 7, en el que la actualización del tiempo de validez de una inscripción en la lista de precursores y el valor del tiempo de validez de la ruta en la correspondiente inscripción en la tabla de enrutamiento, se realiza a la vez.
  9. 9.
    Procedimiento según una de las reivindicaciones precedentes, en el que no es necesaria la creación de una lista de precursores para una inscripción en la tabla de enrutamiento para el nodo de destino en un nodo intermedio que -en una ruta de transmisión de tramas de datos entre el nodo de destino (DN) y el nodo de origen (SN), se
    encuentra contiguo al nodo de origen (SN), y -en una ruta de transmisión de tramas de datos entre el nodo de origen (SN) y el nodo de destino (DN), se encuentra contiguo al nodo de destino (DN).
  10. 10.
    Procedimiento según una de las reivindicaciones precedentes, en el que otro nodo de red que no es el nodo de origen (SN), el nodo de destino (DN) o uno de los nodos intermedios (IN) en una ruta de datos (S-B-A-C-D) entre el nodo de origen (SN) y el nodo de destino (DN), tras recibirse un mensaje de solicitud de ruta del nodo de origen, transmite una trama de datos al nodo de origen a través
    de otro nodo intermedio, nodo intermedio que es el siguiente nodo de red sobre una ruta de retorno hacia el nodo de origen y que no contiene el otro nodo de red en la lista de precursores de la inscripción en la tabla de enrutamiento para el nodo de origen (SN) y que desecha la trama de datos recibida del otro nodo de red.
  11. 11.
    Procedimiento según la reivindicación 10, en el que la ruta de datos (G -B -F -S) formada entre el otro nodo de red y el nodo de origen, se señala como inválida.
  12. 12.
    Procedimiento según la reivindicación 11, en el que mediante el otro nodo de red se realiza un route discovery (descubrimiento de ruta) hacia el nodo de origen.
  13. 13.
    Procedimiento según la reivindicación 10, en el que se inscribe el otro nodo de red en la lista de precursores de la inscripción en la tabla de enrutamiento para la ruta de retorno hacia el nodo de origen del otro nodo intermedio, antes de que la trama de datos sea transmitida por el otro nodo de red al nodo de origen (SN).
  14. 14.
    Procedimiento según la reivindicación 13, en el que la inclusión del otro nodo de red en la lista de precursores de la inscripción en la tabla de enrutamiento para la ruta de retorno hacia el nodo de origen del otro nodo intermedio, se realiza mediante el envío de un mensaje de respuesta de ruta al nodo de origen con el otro nodo de red como destino y el nodo de origen como origen (source).
  15. 15.
    Procedimiento según la reivindicación 10, en el que las direcciones de todos los nodos de red contiguos a un nodo de red, juntamente con un valor de caducidad al recibir un mensaje de solicitud de ruta, se inscriben en la lista de precursores de este nodo de red como inscripción temporal.
  16. 16.
    Procedimiento según la reivindicación 15, en el que el nodo de red contiguo al nodo de red que ha enviado el mensaje de solicitud de ruta no se inscribe en la lista de precursores de este nodo de red.
  17. 17.
    Procedimiento según la reivindicación 15 o 16, en el que la inscripción temporal en la lista de precursores se dota de un valor de caducidad que presenta el mismo valor que la ruta de retorno establecida mediante el mensaje de solicitud de ruta.
  18. 18.
    Procedimiento según una de las reivindicaciones 15 a 17, en el que las inscripciones temporales se borran de la lista de precursores cuando se crea una inscripción en la lista de precursores en el marco del mensaje de respuesta de ruta iniciado por el nodo de destino.
ES08760631T 2007-06-25 2008-06-06 Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red. Active ES2374687T3 (es)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
DE102007029120A DE102007029120B4 (de) 2007-06-25 2007-06-25 Verfahren zum Betreiben eines drahtlosen, vermaschten Datennetzes mit einer Mehrzahl an Netzknoten
DE102007029120 2007-06-25
PCT/EP2008/057057 WO2009000630A1 (de) 2007-06-25 2008-06-06 Verfahren zum betreiben eines drahtlosen, vermaschten datennetzes mit einer mehrzahl an netzknoten

Publications (1)

Publication Number Publication Date
ES2374687T3 true ES2374687T3 (es) 2012-02-21

Family

ID=39791043

Family Applications (1)

Application Number Title Priority Date Filing Date
ES08760631T Active ES2374687T3 (es) 2007-06-25 2008-06-06 Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red.

Country Status (10)

Country Link
US (1) US8675645B2 (es)
EP (1) EP2160874B1 (es)
JP (1) JP4971500B2 (es)
KR (1) KR101494818B1 (es)
CN (2) CN101690028A (es)
AT (1) ATE531169T1 (es)
DE (1) DE102007029120B4 (es)
ES (1) ES2374687T3 (es)
PL (1) PL2160874T3 (es)
WO (1) WO2009000630A1 (es)

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101041598B1 (ko) * 2009-02-02 2011-06-15 부산대학교 산학협력단 다중 홉 통신을 갖는 항만 물류용 능동형 ｒｆｉｄ 시스템 및 그 통신 방법
CN101990270B (zh) * 2009-08-06 2014-05-21 华为技术有限公司 建立按需路由的方法、设备及系统
WO2012069950A1 (en) * 2010-11-25 2012-05-31 Koninklijke Philips Electronics N.V. System and method for optimizing data transmission to nodes of a wireless mesh network
US8995454B2 (en) * 2011-01-11 2015-03-31 Mobix Wireless Solutions Ltd. System and method for high throughput communication in a mesh hybrid network
US8656492B2 (en) * 2011-05-16 2014-02-18 General Electric Company Systems, methods, and apparatus for network intrusion detection
US9092427B2 (en) * 2012-06-08 2015-07-28 Lockheed Martin Corporation Dynamic trust session
KR101505617B1 (ko) * 2013-12-13 2015-03-26 경북대학교 산학협력단 6LoWPAN 기반 다중 라우팅 구축 방법 및 시스템
CN110300460B (zh) * 2014-09-16 2023-05-16 华为技术有限公司 通信方法、装置及系统
US9647925B2 (en) 2014-11-05 2017-05-09 Huawei Technologies Co., Ltd. System and method for data path validation and verification
CN106161237B (zh) * 2015-04-17 2020-08-18 富士通株式会社 集中式的路由方法、装置和系统
CN106507507B (zh) * 2016-12-30 2020-03-27 湖南基石通信技术有限公司 一种无线网状网络拓扑结构搭建系统及方法
US11082324B2 (en) 2018-07-27 2021-08-03 goTenna Inc. Vine: zero-control routing using data packet inspection for wireless mesh networks
CN111263443B (zh) * 2018-11-30 2023-06-13 海能达通信股份有限公司 一种动态子帧分配方法及装置
CN115668884A (zh) * 2021-01-29 2023-01-31 北京小米移动软件有限公司 一种数据包发送方法、数据包发送装置及存储介质
CN115769558A (zh) * 2021-05-10 2023-03-07 北京小米移动软件有限公司 一种数据包发送方法、装置及存储介质
CN115767668B (zh) * 2022-10-31 2025-12-30 海尔优家智能科技（北京）有限公司 路由表的查询方法和装置、存储介质及电子装置

Family Cites Families (23)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6535498B1 (en) * 1999-12-06 2003-03-18 Telefonaktiebolaget Lm Ericsson (Publ) Route updating in ad-hoc networks
US20020038419A1 (en) * 2000-03-20 2002-03-28 Garrett John W. Service selection in a shared access network using tunneling
AU2001269827A1 (en) * 2000-06-16 2002-01-02 The Regents Of The University Of California Bandwidth efficient source tracing (best) routing protocol for wireless networks
FI112152B (fi) * 2000-09-29 2003-10-31 Nokia Corp Osoitteistus ja reititys ad hoc-liikkuvuusverkoissa
US7116640B2 (en) * 2000-12-22 2006-10-03 Mitchell Paul Tasman Architecture and mechanism for forwarding layer interfacing for networks
JP2002281042A (ja) 2001-03-15 2002-09-27 Toshiba Corp 無線伝送システムの通信データループ防止方法
JP4715066B2 (ja) 2001-09-06 2011-07-06 ソニー株式会社 無線通信システム、移動体端末、プログラム、およびデータ転送方法
MXPA04004719A (es) * 2003-05-19 2004-09-06 Eaton Corp Red ad-hoc y metodo de enrutar comunicaciones en una red de comunicaciones.
EP1653676B1 (en) * 2003-08-08 2017-12-27 Sony Corporation Communication system, communication method and program
US7415019B2 (en) * 2003-08-22 2008-08-19 Samsung Electronics Co., Ltd. Apparatus and method for collecting active route topology information in a mobile ad hoc network
US7672307B2 (en) * 2003-08-22 2010-03-02 Samsung Electronics Co., Ltd. Apparatus and method for transparent layer 2 routing in a mobile ad hoc network
US7512078B2 (en) * 2003-10-15 2009-03-31 Texas Instruments Incorporated Flexible ethernet bridge
KR100612496B1 (ko) * 2004-05-11 2006-08-14 삼성전자주식회사 이동 임시 네트워크에서의 서비스 탐색 방법
KR100602267B1 (ko) * 2004-07-03 2006-07-19 삼성전자주식회사 통신 시스템에서 라우터 설정 방법 및 시스템
US8185653B2 (en) * 2004-08-09 2012-05-22 Johnny Yau Method and apparatus for ad hoc mesh routing
US7408911B2 (en) * 2004-11-08 2008-08-05 Meshnetworks, Inc. System and method to decrease the route convergence time and find optimal routes in a wireless communication network
US20060274700A1 (en) * 2005-06-02 2006-12-07 Christophe Janneteau Autonomous mode for a plurality of nested mobile networks
PT1952588E (pt) * 2005-11-09 2011-08-25 Thomson Licensing Selecção de percurso em redes sem-fios
US7693146B2 (en) * 2006-03-10 2010-04-06 Cisco Technology, Inc. Method and system for filtering traffic from unauthorized sources in a multicast network
US7567547B2 (en) * 2006-09-07 2009-07-28 Palo Alto Research Center Incorporated Method and system for loop-free ad-hoc routing
US7843833B2 (en) * 2006-11-09 2010-11-30 Avaya Inc. Detection and handling of lost messages during load-balancing routing protocols
US8134995B2 (en) * 2007-01-12 2012-03-13 Samsung Electronics Co., Ltd. Mobile ad-hoc network routing based upon hardware address
US20080316951A1 (en) * 2007-06-20 2008-12-25 Motorola, Inc. Method for discovering a route to an intelligent access point (iap)

Also Published As

Publication number Publication date
CN102364977B (zh) 2016-03-23
JP4971500B2 (ja) 2012-07-11
CN102364977A (zh) 2012-02-29
DE102007029120A1 (de) 2009-01-02
ATE531169T1 (de) 2011-11-15
US20100177753A1 (en) 2010-07-15
EP2160874A1 (de) 2010-03-10
EP2160874B1 (de) 2011-10-26
US8675645B2 (en) 2014-03-18
PL2160874T3 (pl) 2012-03-30
KR101494818B1 (ko) 2015-02-24
JP2010531591A (ja) 2010-09-24
WO2009000630A1 (de) 2008-12-31
DE102007029120B4 (de) 2010-06-17
KR20100053515A (ko) 2010-05-20
CN101690028A (zh) 2010-03-31

Similar Documents

Publication Publication Date Title
ES2374687T3 (es) Procedimiento para operar una red de datos inalámbrica enmallada con un conjunto de nodos de red.
Ogier et al. Topology dissemination based on reverse-path forwarding (TBRPF)
ES2472691T3 (es) Selección de ruta en redes inalámbricas
Clausen et al. Lightweight on-demand ad hoc distance-vector routing-next generation (LOADng): Protocol, extension, and applicability
ES2339782T3 (es) Protocolo hibrido de encaminamiento para una red con topologia de malla.
ES2375227T3 (es) Procedimiento para establecer rutas bidireccionales de transmisión de datos en una red de comunicaciones inalámbrica enmallada.
Clausen et al. RFC3626: Optimized link state routing protocol (OLSR)
US6836463B2 (en) System for communicating labeled routing trees to establish preferred paths and source routes with local identifiers in wireless computer networks
ES2398924T3 (es) Procedimiento de enrutado fiable
US9001645B2 (en) System and method for packet delivery backtracking
US11838850B2 (en) Method for adding redundant relay nodes during path discovery procedure of a mesh network
ES2361545A1 (es) Procedimiento de encaminamiento de tramas de datos y puente de red.
JP2005124195A (ja) 移動アドホックネットワークにおけるブロードキャストデータ処理方法
KR100664953B1 (ko) 모바일 애드 혹 네트워크 환경에서의 멀티캐스트 라우팅방법
ES2638214T3 (es) Método de comunicación de tipo SMF para una red manet, nodo de red y red móvil que implementan este método de comunicación
ES2725780T3 (es) Método y sistema para el enrutamiento por inundación y multidifusión en una red AD-HOC
Ogier et al. RFC3684: Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)
Garcia-Luna-Aceves et al. Simple and efficient loop-free multipath routing in wireless networks
JP2014204437A (ja) ダウンリンクルーティングの取得及び保守の方法及び装置
Holter et al. Design and implementation of wireless OSPF for mobile ad hoc networks
ES3045141T3 (en) Routing data in a communication network
Schmittner Scalable and secure multicast routing for mobile ad-hoc networks
Gupta et al. Secure and Effective Reactive Protocol for Mobile Adhoc Network-AODV
Sousa Virtual One-hop Ad hoc Networks
Garepalli et al. Control Message Reduction Techniques in Backward Learning Ad Hoc Routing Protocols