ES2249280T3 - Encaminamiento en una red de conmutacion de paquetes con terminales moviles. - Google Patents

Abstract

Procedimiento para controlar el encaminamiento de paquetes en una red de conmutación de paquetes, que incluye una infraestructura de nodos de conmutación de paquetes interconectados mediante enlaces de transporte de paquetes y una pluralidad de nodos de acceso hacia los cuales una trayectoria de encaminamiento, definida por los datos almacenados en los nodos de conmutación de paquetes situados a lo largo de dicha trayectoria de encaminamiento, puede dirigirse en dicha infraestructura para una dirección de red dada, comprendiendo dicho procedimiento: el encaminamiento de paquetes a lo largo de una primera trayectoria de encaminamiento para una primera dirección de red, en el que dicha primera trayectoria de encaminamiento es una de entre una o más trayectorias de encaminamiento dirigidas hacia un primer nodo de acceso (BS2) para dicha primera dirección de red, y dicho primer nodo de acceso (BB2) presta servicio a un nodo móvil (MH2) utilizando dicha primera dirección de red por medio de un enlace de comunicaciones y la alteración del encaminamiento en una pluralidad de nodos de conmutación de paquetes de dicha infraestructura cuando dicho primer nodo móvil (MH2) recibe servicio desde un segundo nodo de acceso (BS3); caracterizado porque dicha etapa de alteración del encaminamiento comprende la transmisión de mensajes de actualización de encaminamiento dirigidos a un subconjunto limitado de dichos nodos de conmutación de paquetes para crear una segunda trayectoria de encaminamiento para dicha primera dirección de red, estando localizado dicho subconjunto en el área de una trayectoria de conexión entre dicho primer (BS2) y segundo (BS3) nodos de acceso y comprendiendo por lo menos los nodos de conmutación de paquetes (ER2, IR2, ER3) situados a lo largo de dicha trayectoria de conexión, y siendo dicha segunda trayectoria de encaminamiento una de entre una o más trayectorias de encaminamiento dirigidas hacia dicho segundo nodo de acceso (BS3) para dicha primera dirección de red.

Description

Encaminamiento en una red de conmutación de paquetes con terminales móviles.

La presente invención se refiere al encaminamiento de señales de telecomunicaciones y, más particularmente, a un procedimiento de encaminamiento de dichas señales hacia medios de telecomunicaciones fijos y móviles, que permite que los usuarios de cada tipo de medios utilicen servicios similares del mismo modo y que los operadores del sistema reduzcan los costes gracias a la mayor concordancia de la conmutación y otros servicios de la red. La presente invención se refiere al encaminamiento de comunicaciones basadas en paquetes, tales como las establecidas en Internet mediante el denominado "protocolo de Internet" (IP).

En los presentes sistemas de medios móviles, el usuario móvil y los sistemas asociados actúan en colaboración mutua en la interfaz con la red (habitualmente, la estación base de radio) para permitir que un nodo móvil deje de comunicarse con una estación base y empiece a comunicarse con otra, y para permitir que la red actualice los puntos de inteligencia del nuevo emplazamiento. En las redes celulares, estos puntos de inteligencia son el registro de abonados locales y el registro de abonados visitantes (HLR y VLR), mientras que en las redes "IP móviles" estos emplazamientos son los denominados "agente local" y "agente externo". En ambos casos, el registro de abonados visitantes y el agente externo mantienen un registro que incluye sólo los usuarios que cooperan actualmente con las estaciones base supervisadas por éstos, mientras que el registro de abonados locales y el agente local mantienen un registro permanente de los usuarios asociados, incluido un registro del VLR o el agente externo con el que está trabajando actualmente cada uno de ellos. La dirección de un mensaje de entrada indica el HLR/agente local correspondiente al que se hace referencia para indicar el VLR/agente externo adecuado y obtener detalles de encaminamiento más concretos. Esto permite llevar a cabo cambios menores de emplazamiento dentro del VLR/agente externo, de forma local para el emplazamiento actual del usuario, sin tener que comunicar dichos cambios al HLR/agente local (que podría hallarse a cierta distancia del usuario), reduciendo pues en gran medida la carga general de señalización.

El coste adicional de la movilidad viene determinado por la provisión de esta interfaz agente local/agente externo y, en el caso particular de los sistemas de paquetes, por el coste del tunelado (envío de mensajes de una dirección a otra), el desgaste de dirección (incapacidad para utilizar una dirección desde la cual se está efectuando el envío) y el encaminamiento triangular.

En un sistema de medios fijos, el encaminamiento IP se basa en la distribución de bloques o prefijos de direcciones IP, con un coste métrico o de trayectoria asociado, desde destinos potenciales hasta emisores potenciales, de tal forma que éstos y los encaminadores intermedios puedan determinar el siguiente mejor salto (encaminador vecino) hacia uno de esos destinos. Dado que las trayectorias para todos los destinos de la red se calculan previamente, los emisores pueden enviar de inmediato la información que generan. El cálculo previo de trayectorias, y la tecnología de intercambio de encaminamiento utilizada, es posible cuando los orígenes y los destinos presentan un emplazamiento fijo y cuando se dispone de un gran ancho de banda de comunicación para el intercambio exhaustivo de trayectorias. No obstante, debido a que la proporción de itinerancia se incrementa, estos modelos sufren fallos y se plantea pues la necesidad de disponer de un sistema de encaminamiento más dinámico.

La propuesta denominada "HAWAII", publicada el 19 de febrero de 1999 como un borrador de Internet titulado "IP Micro-Mobility Support Using HAWAI", R.Ramjee T. La Por, S. Thuel y K. Varadh, puede consultarse en la página web de Internet Engineering Taskforce HTTP://ww.ieft.org/intenet-drafts/draft-rimjee-micro-mobility-hawaii-00.txt. La propuesta HAWAII utiliza sistemas de establecimiento de trayectorias especializados que instalan entradas de envío basadas en ordenador central en encaminadores específicos cuando se halla en un dominio de encaminamiento compatible con la micromovilidad intradominio, y pasa por omisión a la utilización de una red "IP móvil" para la micromovilidad interdominio. En la propuesta HAWAII, los nodos móviles conservan sus direcciones de red mientras se desplazan dentro del dominio. La arquitectura HAWAII se basa en un encaminador de pasarela a un dominio, denominado encaminador raíz del dominio, hacia el cual se dirigen las trayectorias por omisión dentro del dominio. A cada nodo móvil se le asigna un dominio local, basándose en su dirección IP permanente. El sistema de establecimiento de trayectorias actualiza una sola trayectoria de encaminamiento en un dominio y, de ese modo, la conectividad con el nodo móvil es posible antes y después de la transferencia en la capa de enlace inalámbrico. Sólo los encaminadores situados a lo largo de una única trayectoria de encaminamiento entre el encaminador raíz del dominio y la estación base que presta servicio actualmente al nodo móvil presentan entradas en la tabla de encaminamiento para la dirección IP del nodo móvil. El resto de encaminadores del dominio encamina cualquier paquete dirigido al nodo móvil en sentido ascendente a lo largo de trayectorias por omisión, que se basan en la disposición tipo árbol del dominio de encaminamiento que tiene como origen el encaminador raíz del dominio, para proporcionar una intersección con el encaminamiento descendente hacia el nodo móvil a lo largo de la única trayectoria de encaminamiento con respecto a la cual los encaminadores presentan entradas de nodo individuales para la dirección IP del nodo móvil.

En el sistema HAWAII, la movilidad entre dominios es posible gracias a mecanismos "IP móviles". El encaminador raíz del dominio local se designa como agente local, y los paquetes IP encapsulados se envían por medio del encaminador raíz del dominio externo.

Entre los inconvenientes de las propuestas HAWA
II se incluyen la concentración de túneles IP móviles en algunos nodos del núcleo de la red (los encaminadores raíz del dominio), lo cual puede determinar que el fallo de cualquiera de estos nodos provoque un fallo a mayor escala de todo el estado móvil IP y las sesiones asociadas controladas por el nodo defectuoso. Además, puesto que todo el encaminamiento desde fuera hacia el dominio local (y en el sentido inverso) debe producirse por medio del encaminador raíz del dominio, un fallo en el encaminador raíz del dominio local puede provocar también un fallo a gran escala.

El documento titulado "IP Addressing and Routing in a Local Wireless Network" de Cohen et al., Infocom '92, IEEE describe un sistema de direccionamiento temporal mediante el cual se asigna dinámicamente una dirección IP temporal cuando una unidad móvil se pone en funcionamiento por medio de una estación base desde la cual recibe el servicio. Cada estación base presenta un "banco" de direcciones IP asociado de forma permanente. La ventaja de este sistema es que cuando la unidad móvil se pone en funcionamiento, no se desencadena ninguna actualización de tabla de encaminamiento. No obstante, cuando la unidad móvil se desplaza hacia una estación base diferente, las tablas de encaminamiento de la red se actualizan mediante mensajes de actualización de encaminamiento IP convencionales difundidos a través de la red, o tal vez la subred. Una desventaja de este sistema es que la carga de señalización de encaminamiento es alta, en particular cuando hay un gran número de unidades móviles activas en la red. Además, se proporciona una entidad de consulta de direcciones para determinar si puede reutilizarse o no una dirección IP. Esta entidad de consulta de direcciones contiene el banco de direcciones IP y es informada sobre los movimientos de una unidad móvil entre estaciones base cada vez que éstos se producen. Esto también provoca un incremento de la carga de señalización de encaminamiento de la red.

La patente US nº 5.400.338 describe un sistema de comunicación de paquetes, en el que se asigna una dirección basada en coordenadas absolutas a los nodos estacionarios. El direccionamiento de los nodos itinerantes se realiza adoptando parasitariamente un sistema de encaminamiento basado en coordenadas y utilizado para asignar direcciones a los nodos estacionarios. Cada nodo itinerante selecciona un nodo padre estacionario con el cual el nodo itinerante puede comunicarse directamente. Mientras la red está en funcionamiento, el nodo itinerante puede seleccionar un nuevo nodo padre. En el momento de la reasignación, las coordenadas del nuevo nodo padre, así como la identidad del nodo itinerante, se registrarán en el nodo padre anterior. El envío de paquetes a los nodos estacionarios se realiza según un sistema conocido de encaminamiento basado en coordenadas. Los paquetes dirigidos a un nodo itinerante de destino se envían y dirigen a través del nodo padre estacionario actual de ese momento. Los paquetes se envían a continuación al nodo itinerante de destino.

Según un aspecto de la presente invención, se proporciona un procedimiento para controlar el encaminamiento de paquetes en una red de conmutación de paquetes, que incluye una infraestructura de nodos de conmutación de paquetes interconectados mediante enlaces de transporte de paquetes y una pluralidad de nodos de acceso hacia los cuales una trayectoria de encaminamiento, definida por los datos almacenados en los nodos de conmutación de paquetes situados a lo largo de dicha trayectoria de encaminamiento, puede dirigirse en dicha infraestructura para una dirección de red dada, comprendiendo dicho procedimiento las etapas siguientes:

encaminamiento de paquetes a lo largo de una primera trayectoria de encaminamiento para una primera dirección de red, en el que dicha primera trayectoria de encaminamiento es una de entre una o más trayectorias de encaminamiento dirigidas hacia un primer nodo de acceso (BS2) para dicha primera dirección de red, y dicho primer nodo de acceso (BB2) presta servicio a un nodo móvil (MH2) utilizando dicha primera dirección de red por medio de un enlace de comunicaciones y

alteración del encaminamiento en una pluralidad de nodos de conmutación de paquetes de dicha infraestructura cuando dicho primer nodo móvil (MH2) recibe servicio desde un segundo nodo de acceso (BS3);

caracterizado porque dicha etapa de alteración del encaminamiento comprende transmitir mensajes de actualización de encaminamiento dirigidos a un subconjunto limitado de dichos nodos de conmutación de paquetes para crear una segunda trayectoria de encaminamiento para dicha primera dirección de red, estando localizado dicho subconjunto en el área de una trayectoria de conexión entre dicho primer (BS2) y segundo (BS3) nodos de acceso y comprendiendo por lo menos los nodos de conmutación de paquetes (ER2, IR2 y ER3) situados a lo largo de dicha trayectoria de conexión, y siendo dicha segunda trayectoria de encaminamiento una de entre una o más trayectorias de encaminamiento dirigidas hacia dicho segundo nodo de acceso (BS3) para dicha primera dirección de red.

Por consiguiente, una dirección de red puede asociarse a largo plazo con un nodo de acceso dado, y asignarse a un nodo móvil cuando recibe el servicio en dicho nodo de acceso, siendo posible también al mismo tiempo la movilidad a corto plazo del nodo móvil entre los nodos de acceso. Enviando mensajes de actualización de encaminamiento sólo a un subconjunto limitado de dichos nodos de conmutación de paquetes, localizados en el área de una trayectoria de conexión entre nodos de acceso, podrá reducirse la carga de señalización de encaminamiento de la red debida a la movilidad.

Este aspecto proporciona una forma conveniente y fiable para alterar el encaminamiento en la infraestructura para la primera dirección de red, cuando una pluralidad de trayectorias de encaminamiento de la infraestructura se dirige hacia un solo nodo de acceso para la primera dirección de red.

En las formas de realización preferidas de la presente invención, se proporciona un procedimiento para controlar el encaminamiento de los paquetes en una red de conmutación de paquetes que incluye una infraestructura de nodos de conmutación de paquetes interconectados mediante enlaces de transporte de paquetes, y una pluralidad de nodos de acceso hacia los cuales puede dirigirse una trayectoria de encaminamiento, definida por los datos almacenados en los nodos de conmutación de paquetes localizados a lo largo de dicha trayectoria de encaminamiento, en dicha infraestructura para una dirección de red dada, comprendiendo dicho procedimiento las etapas siguientes:

asignación de una o más direcciones de red a un primer nodo de acceso como una o más direcciones locales de dicho primer nodo de acceso;

asignación dinámica de una primera de dichas direcciones locales a un primer nodo móvil que es servido a través de un enlace de comunicaciones por dicho primer nodo de acceso, dirigiéndose por lo menos una trayectoria de encaminamiento de dicha infraestructura hacia dicho primer nodo de acceso para dicha primera dirección local;

alteración del encaminamiento en dicha infraestructura cuando dicho primer nodo móvil recibe servicio desde un segundo nodo de acceso, de tal forma que por lo menos una trayectoria de encaminamiento de dicha infraestructura se dirija hacia dicho segundo nodo de acceso para dicha primera dirección local y

cuando dicha dirección local queda disponible para la reasignación, alteración del encaminamiento en dicha infraestructura, de tal forma que por lo menos una trayectoria de encaminamiento de dicha infraestructura se dirija hacia dicho primer nodo de acceso para dicha primera dirección local, y transmisión de un mensaje de encaminamiento hacia dicho primer nodo de acceso, que indica que dicha primera dirección local puede asignarse a un segundo nodo móvil que es servido por dicho primer nodo de acceso.

Dirigiendo el encaminamiento hacia el primer nodo de acceso y transmitiendo un mensaje de encaminamiento al primer nodo de acceso, en el que se le indica que puede reasignar la dirección local una vez que ésta esté disponible, será posible obviar la necesidad de disponer de un asistente de direcciones separado que requiere una actualización frecuente debido a los cambios de encaminamiento.

Otros aspectos y ventajas de la presente invención resultarán evidentes a partir de las formas de realización descritas a continuación, a título de ejemplo sólo, en relación con los dibujos adjuntos, en los que:

la Figura 1 ilustra de forma esquemática un ejemplo de una topología fija/móvil según una forma de realización de la presente invención;

las Figuras 2 a 11 ilustran de forma esquemática la transferencia entre estaciones base y las actualizaciones de encaminamiento asociadas según una forma de realización de la presente invención;

las Figuras 12 a 16 ilustran la transferencia entre estaciones base y las actualizaciones de encaminamiento asociadas según otra forma de realización de la presente invención;

las Figuras 17 a 25 ilustran la restauración del encaminamiento hacia una estación base local según una forma de realización de la presente invención;

la Figura 26 ilustra de forma esquemática una tabla de datos de protocolo de encaminamiento almacenada en un nodo de encaminamiento según una forma de realización de la presente invención; y

la Figura 27 ilustra una tabla de envío al siguiente salto almacenada en el nodo de encaminamiento según una forma de realización de la presente invención.

Haciendo referencia a la Figura 1, se representa un ejemplo de una topología fija/móvil según una forma de realización de la presente invención. La topología incluye, a título de ejemplo, tres redes de conmutación de paquetes 2, 4, 6 que forman un sistema autónomo (AS), la extensión del cual se indica esquemáticamente mediante sombreado oscuro en la Figura 1. Una definición dada para el término "sistema autónomo" es "grupo de encaminadores y redes sometidos a la misma administración" ("Routing in the Internet", Christian Huitema, Prentice-Hall, 1995, página 158). En la presente memoria, el término "sistema autónomo", denominado también "dominio de encaminamiento" dentro del ámbito de la técnica, también se aplica a una red, o un grupo de redes, que presentan encaminadores que ejecutan el mismo protocolo de encaminamiento. Un sistema autónomo puede conectarse a otros sistemas autónomos formando una interred global, tal como Internet (utilizada a título de ejemplo en lo sucesivo). El protocolo de encaminamiento es un protocolo de pasarela interior, y las comunicaciones con otros sistemas autónomos se llevan a cabo por medio de protocolos de pasarela exterior, tales como el protocolo de pasarela frontera (BGP). El protocolo de información de encaminamiento (RIP) y el protocolo "abrir primero la trayectoria más corta" (OSPF) constituyen ejemplos de protocolos de pasarela interior conocidos.

Las redes 2, 4, 6 que forman una infraestructura fija del sistema autónomo incluyen una pluralidad de nodos de conmutación de paquetes de protocolo de Internet (IP) en forma de una pluralidad de encaminadores centrales (CR) y una pluralidad de encaminadores frontera (ER) y encaminadores puente (BR) que interconectan las diferentes redes 2, 4, 6 del AS. Todos estos nodos de conmutación de paquetes ejecutan un único protocolo de encaminamiento IP, una de cuyas formas de realización se describirá en mayor detalle a continuación.

El sistema autónomo es conectado a otros sistemas autónomos de la interred global mediante uno o más encaminadores de pasarela exterior (EGR).

El sistema autónomo ilustrado en la Figura 1 lleva a cabo el encaminamiento tanto para los nodos móviles, cuyo encaminamiento dentro del AS es alterado como consecuencia de la movilidad de los nodos móviles, como para los nodos fijos o estacionarios, cuyo encaminamiento no es alterado.

Los nodos móviles pueden conectarse a un encaminador frontera por medio de un enlace inalámbrico que, en el ejemplo representado, es un enlace de radio celular (otro tipo posible de enlace inalámbrico es un enlace infrarrojo), utilizando un encaminador de estación base (BS) proporcionado por un operador de red móvil. El enlace de radio celular puede ser un enlace de sistema de acceso múltiple por división del tiempo (TDMA), tal como el "GSM", o un enlace de sistema de acceso múltiple por división del código (CDMA), tal como el "CDMA 2000". Los nodos móviles adoptan la forma de nodos móviles individuales 14 o de encaminadores móviles 16 que presentan una pluralidad de nodos conectados, que establecen respectivamente la comunicación por radio con uno o varios (por ejemplo, en el caso de una transferencia con continuidad CDMA) de los encaminadores BS en cualquier momento dado. Un encaminador BS puede controlar varias estaciones base transceptoras (BTS) situadas conjuntamente con antenas de radio alrededor de las cuales se forman las "células" individuales del sistema celular.

Los nodos móviles 14, 16 se desplazan entre las células de la red de comunicaciones de radio celular. Si existe un encaminador BS que presta servicio a varias células, cuando un nodo móvil experimente una transferencia entre células, éste podrá continuar recibiendo datos en paquetes por medio del mismo encaminador BS. No obstante, cuando el nodo móvil se desplace y quede fuera del alcance del encaminador BS que le presta servicio, tal vez sea necesario un cambio de encaminamiento dentro del AS para efectuar la transferencia hacia una nueva célula. Los paquetes de datos que tienen como origen y destino el nodo móvil en cuestión, y que son encaminados mediante el identificador de la dirección IP o una de las direcciones IP del nodo a través de un encaminador BS dado antes de la transferencia, pueden precisar encaminamiento para la misma dirección IP a través de un encaminador BS diferente después de la transferencia. Un nodo móvil puede participar en una sesión de comunicaciones con un nodo diferente por medio del AS durante la transferencia de un encaminador BS a otro. Debido a que las conexiones de la capa de transporte (en una conexión TCP/IP por ejemplo) son definidas en parte por la dirección IP del nodo móvil, dicho cambio de encaminamiento es deseable para permitir que dichas conexiones continúen utilizando la misma dirección IP cuando el nodo móvil recibe el servicio de un encaminador BS diferente.

Los nodos fijos pueden conectarse a un encaminador frontera por medio de una red de área local (LAN) 10, ejecutando un protocolo de red de área local, tal como un protocolo Ethernet. Los nodos fijos pueden conectarse asimismo a un encaminador frontera por medio de una red telefónica de servicio público (PSTN) 12, mediante un servidor de acceso a la red (NAS) 20 proporcionado por un proveedor de acceso a Internet. El NAS 20 asigna dinámicamente direcciones IP fijas a través de la red telefónica a los nodos fijos que se conectan con el NAS 20 mediante un protocolo, tal como el PPP o el SLIP, y encamina los paquetes IP con origen o destino en cada nodo fijo por medio de un encaminador frontera asociado. Mientras que el NAS 20 asigna direcciones IP de forma dinámica, el encaminador frontera, por medio del cual se encaminan los paquetes para la dirección IP asignada, no cambia ni durante una sesión de acceso ni durante un período más largo. Por lo tanto, no es necesario cambiar el encaminamiento dentro del sistema autónomo para cada uno de los nodos fijos, a menos que así lo exijan factores internos al AS, tales como un fallo en el enlace o la gestión del tráfico.

El protocolo de pasarela interior, es decir, el único protocolo de encaminamiento IP utilizado en el AS de esta forma de realización de la presente invención, es una versión modificada del protocolo de encaminamiento "Temporally-Ordered Routing Altorithm" (TORA), que se describe en, inter alia, el documento "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks", Vincent D. Park y M. Scott Corson, Proceedings of INFOCOM '97, 7-11 de abril, Kobe, Japón; y el documento "A Performance Comparison of the Temporally-Ordered Routing Algorithm and Ideal Link-State Routing", Vincent D. Park y M. Scott Corson, Proceedings of ISCC '98, 30 de junio-2 de julio, 1999, Atenas, Grecia.

El algoritmo del protocolo de encaminamiento TORA se ejecuta de forma distribuida, proporciona trayectorias sin bucles, proporciona encaminamiento múltiple (para mitigar la congestión), establece trayectorias con rapidez (para que éstas puedan ser utilizadas antes de que la topología cambie) y reduce al mínimo la carga general de comunicación confinando la reacción algorítmica a los cambios topológicos siempre que sea posible (para mantener el ancho de banda disponible e incrementar la escalabilidad).

El algoritmo es distribuido en la medida en que los nodos sólo mantienen información acerca de los nodos adyacentes (es decir, la información de un salto). El algoritmo asegura que todas las trayectorias carezcan de bucles y habitualmente proporciona encaminamiento por trayectorias múltiples para cualquier par origen/destino que requiera una trayectoria. Puesto que habitualmente se establecen varias trayectorias, muchos cambios topológicos no precisan de actualizaciones de encaminamiento dentro del AS, ya que basta con disponer de una única trayectoria. Después de cambios topológicos que sí requieren una reacción, el protocolo reestablece las trayectorias válidas.

El protocolo TORA crea un modelo de red en forma de gráfico G = (N, L), siendo N un grupo finito de nodos y L un grupo de enlaces que inicialmente no presentan ninguna dirección. Cada nodo i \in N presenta un identificador de nodo exclusivo (ID), y cada enlace (i, j) \in L permite la comunicación bidireccional (es decir, los nodos conectados mediante un enlace pueden comunicarse entre sí en ambos sentidos). A cada enlace que carece inicialmente de dirección (i, j) \in L, se le puede asignar uno de tres estados: (1) no dirigido, (2) dirigido del nodo i al nodo j y (3) dirigido del nodo j al nodo i. Si el enlace (i, j) \in L es dirigido del nodo i al nodo j, se dice que el nodo i está situado "aguas arriba" del nodo j, y que el nodo j está situado "aguas abajo" del nodo i. Para cada nodo i, los nodos "vecinos" de i, N_{i} \in N, se definen como el grupo de nodos j que cumple (i, j) \in L. Cada nodo i conoce siempre a sus nodos vecinos del grupo N_{i}.

Se ejecuta una versión lógicamente independiente del protocolo para cada destino (indicado, por ejemplo, mediante una dirección IP de nodo) hacia el cual se requiere encaminamiento.

El protocolo TORA puede dividirse en tres funciones básicas: la creación de trayectorias, el mantenimiento de trayectorias y la supresión de trayectorias. La creación de una trayectoria desde un nodo dado hasta el destino requiere el establecimiento de una secuencia de enlaces dirigidos desde el nodo hasta el destino. La creación de trayectorias se corresponde en esencia con la asignación de direcciones a los enlaces en una red o parte de la red que carece de dirección. El procedimiento utilizado para llevar a cabo esta acción es un procedimiento de pregunta/respuesta que elabora un gráfico dirigido acíclico (DAG) que presenta la raíz en el destino (es decir, el destino es el único nodo que no presenta enlaces aguas abajo). Dicho DAG puede denominarse DAG "orientado hacia el destino". El mantenimiento de las trayectorias conlleva reaccionar a los cambios topológicos de la red, de tal forma que las trayectorias hacia el destino se restablezcan dentro de un tiempo finito. Cuando se detecta una partición de la red, todos los enlaces (de la parte de la red que ha quedado dividida desde el destino) se marcan como "no dirigidos" para suprimir las trayectorias no válidas.

El protocolo lleva a cabo las tres funciones utilizando tres paquetes de control diferenciados: búsqueda (QRY), actualización (UPD) y supresión (CLR). Los paquetes QRY se utilizan para crear trayectorias, los paquetes UPD se utilizan tanto para crear como para mantener trayectorias y los paquetes CLR se utilizan para suprimir trayectorias.

En un momento dado, se asocia un quíntuplo ordenado, denominado "altura", H_{i} = (\tau_{i}, oid_{i}, r_{i}, \delta_{i}, i) a cada nodo i \in N. Conceptualmente, el quíntuplo asociado a cada nodo representa la altura del nodo definida por dos parámetros: un nivel de referencia y una variable delta con respecto al nivel de referencia. El nivel de referencia se representa mediante los tres primeros valores del quíntuplo, mientras que la variable delta se representa mediante los dos últimos valores. Se define un nuevo nivel de referencia cada vez que un nodo pierde su último enlace aguas abajo debido a un fallo del enlace. El primer valor que representa el nivel de referencia, \tau_{i}, es una etiqueta de tiempo que indica el "tiempo" del fallo del enlace. El segundo valor, oid_{i}, es el ID del originador (es decir, el ID exclusivo del nodo que ha definido el nuevo nivel de referencia). De este modo se asegura que los niveles de referencia puedan ordenarse por completo lexicográficamente. El tercer valor, r_{i}, es un solo bit utilizado para dividir cada uno de los niveles de referencia exclusivos en dos subniveles exclusivos. Este bit se utiliza para diferenciar entre el nivel de referencia original y su correspondiente nivel de referencia más alto reflejado. El primer valor que representa la variable delta, \delta_{i}, es un entero utilizado para ordenar los nodos con respecto a un nivel de referencia común. Este valor juega un papel decisivo en la propagación de un nivel de referencia. Por último, el segundo valor que representa la variable delta i, es el ID exclusivo del propio nodo. De este modo se asegura que los nodos con un nivel de referencia común y los mismos valores de \delta_{i} (y, de hecho, todos los nodos) puedan ser ordenados por completo lexicográficamente en todo momento.

Cada nodo i (diferente al de destino) mantiene su altura H_{i}. Inicialmente, la altura de cada nodo de la red (diferente al de destino) se establece en NULO, H_{i} = (-, -, -, -, i). Posteriormente, la altura de cada nodo i puede modificarse según las reglas del protocolo. Aparte de su propia altura, cada nodo i mantiene, en una tabla de datos de protocolo de encaminamiento, entradas situadas junto a las direcciones IP de nodo que presentan un DAG en la red, incluyendo las entradas una secuencia de alturas con una entrada HN_{ij} para cada vecino j \in N_{i}.

Cada nodo i (diferente al de destino) mantiene también, en la tabla de datos de protocolo de encaminamiento, una secuencia de estados de enlaces con una entrada LS_{ij} para cada enlace (i, j) \in L. El estado de los enlaces viene determinado por las alturas H_{i} y HN_{ij} y se dirige desde el nodo más alto hacia el nodo más bajo. Si el nodo vecino j es más alto que el nodo i, el enlace se marca como enlace aguas arriba. Si el nodo vecino j es más bajo que el nodo i, el enlace se marca como enlace aguas abajo.

El protocolo TORA fue diseñado originalmente para su utilización en una red móvil ad hoc (MANET), en la que los encaminadores son móviles y están interconectados por medio de enlaces inalámbricos. No obstante, en esta forma de realización de la presente invención, se utiliza un protocolo TORA modificado en un sistema autónomo que incluye una infraestructura fija de encaminadores fijos interconectados mediante enlaces fijos, tal como la ilustrada en la Figura 1, para permitir las alteraciones de encaminamiento en la infraestructura fija cuando un nodo móvil altera su punto de conexión con la infraestructura.

La Figura 26 ilustra esquemáticamente un ejemplo de tabla de datos de protocolo de encaminamiento que puede almacenarse en un encaminador según esta forma de realización.

Junto a cada dirección IP de nodo (o prefijo de dirección en el caso de un DAG agrupado, descrito en mayor detalle más adelante), IP1, IP2, etc., que presenta un DAG en la red, se almacena la altura del nodo de almacenamiento H_{i}(IP1), H_{i}(IP2), etc. Asimismo, se almacena la identidad de cada nodo vecino adyacente, por ejemplo: w, x, y, z y la altura de dicho nodo vecino HN_{iw}(IP1, IP2, etc.), HN_{ix}(IP1, IP2, etc.), HN_{iy}(IP1, IP2, etc.) y HN_{iz}(IP1, IP2, etc.). Por último, la secuencia de estados de enlace para cada dirección IP (o prefijo) puede almacenarse en forma de marcas que designan un enlace aguas arriba (U), un enlace aguas abajo (D) o un enlace sin dirección (-), junto a cada identidad de enlace (L1, L2, L3, L4) correspondiente a cada nodo vecino.

La secuencia de estados de enlace incluida en la tabla de datos de protocolo de encaminamiento permite tomar localmente una decisión de envío al siguiente salto en el encaminador que mantiene los datos. Para una red suficientemente interconectada, cada encaminador deberá presentar por lo menos un enlace aguas abajo. Si sólo se dispone de un enlace aguas abajo, ese enlace es el seleccionado como enlace de envío al siguiente salto. Si se dispone de más de un enlace aguas abajo, puede seleccionarse el enlace aguas abajo más adecuado, basándose, por ejemplo, en la carga de tráfico actual sobre los dos enlaces. En cualquier caso, el enlace seleccionado se introduce en una tabla de datos de envío al siguiente salto, junto a la dirección IP. En la memoria caché, se almacena una tabla de envío al siguiente salto, tal como la ilustrada en la Figura 27, a la cual puede accederse con rapidez cuando llegan al encaminador paquetes IP que requieren encaminamiento. La tabla contiene el enlace de envío al siguiente salto (L2, L1, etc.) seleccionado, respecto a cada dirección IP (o prefijo) (IP1, IP2, etc.).

La utilización de una infraestructura fija de encaminadores, y otros aspectos de la presente invención que se describirán a continuación, permiten la agrupación de encaminamientos dentro del AS, en particular para las direcciones IP de los nodos móviles. A continuación, se describirá brevemente cómo se efectúa el direccionamiento IP y, en particular, cómo se utilizan los prefijos de longitud variable para proporcionar agrupación de encaminamientos en una red de encaminamiento IP.

Las direcciones IP actualmente constan de un número predeterminado de bits (32). En el pasado, las direcciones IP se asignaban de acuerdo con un sistema no estructurado (denominado plan de direccionamiento "plano"). El direccionamiento con clases introdujo el concepto de jerarquía de encaminamiento de dos niveles, dividiendo las direcciones en un prefijo de red y en campos de nodo. Se asignaba a los usuarios direcciones IP de clase A, clase B o clase C para simplificar el encaminamiento y la administración.

En la clase A, el bit 0 indicaba la clase A, los bits 1 a 7 indicaban la red (126 redes) y los bits 8 a 31 indicaban el nodo (16 millones de nodos).

En la clase B, los bits 0 a 1 indicaban la clase B, los bits 2 a 15 indicaban la red (16.382 redes) y los bits 16 a 31 indicaban el nodo (64.000 nodos).

En la clase C, los bits 0 a 2 indicaban la clase C, los bits 3 a 23 indicaban la red (2.097.152 redes) y los bits 24 a 31 indicaban el nodo (256 nodos).

Una jerarquía de dos niveles todavía proporcionaba una jerarquía de encaminamiento plana entre los nodos de una red. Por ejemplo, un bloque de direcciones de clase A podría incluir 16 millones de nodos, lo cual daría por resultado 16 millones de entradas en las tabla de direccionamiento de todos los encaminadores de la red Las subredes se diseñaron para poder dividir un bloque de direcciones de nodo en un campo de subred de longitud variable y un campo de nodo. Esto permite a los encaminadores de un AS mantener entradas en la tabla de encaminamiento para las subredes sólo (agrupando los encaminamientos para todos los nodos de cada subred). Se utiliza una máscara de subred para permitir que los encaminadores identifiquen la parte de subred de la dirección.

Según esta forma de realización de la presente invención, se proporciona la agrupación de encaminamientos asignando un bloque de direcciones IP de nodos (es decir, una secuencia contigua de direcciones IP que comparten uno o más prefijos) a un nodo de acceso, tal como un encaminador BS, y asignando dinámicamente direcciones IP del bloque a los nodos móviles mientras efectúan sesiones de acceso. Cuando un nodo móvil se registra en la red celular en el momento del encendido, el encaminador BS de servicio asigna una dirección IP y almacena en memoria caché la vinculación entre el identificador del enlace inalámbrico del nodo móvil y la dirección IP asignada. Dentro del AS, se calcula previamente un plan de encaminamientos agrupados, que en esta forma de realización es un DAG agrupado, antes de asignar al nodo móvil la dirección IP que debe utilizar en toda su sesión de acceso. Tras el apagado del nodo móvil, la dirección IP se devuelve al encaminador BS propietario que, a continuación, puede asignar la dirección IP a otro nodo móvil. Las direcciones IP de los nodos móviles asignadas por un encaminador BS presentarán un DAG agrupado, hasta que por lo menos uno de los nodos móviles cambie de lugar, en cuyo caso el DAG agrupado permanecerá en su lugar, mientras se crea una excepción específica para el nodo en los encaminadores que se han visto afectados por un procedimiento de actualización de encaminamiento específico para la movilidad (la actualización sólo cambia el encaminamiento para el nodo móvil que ha cambiado de lugar).

El cálculo previo de trayectorias en un AS para prefijos de dirección pertenecientes a un encaminador BS tiene lugar mediante la inclusión, por el encaminador BS propietario, de un mensaje de actualización, denominado aquí paquete de "optimación" (OPT), para cada prefijo que llega a través del AS y que actúa realmente como una notificación de prefijo, así como mediante la elaboración del DAG agrupado. El paquete OPT es transmitido por el encaminador BS propietario del prefijo o los prefijos de dirección IP y que controla el DAG agrupado. El paquete OPT se distribuye al resto de nodos de la red (independientemente de sus alturas actuales, si es que se han establecido), y establece o restablece estas alturas en el nivel de referencia "todo ceros", es decir, poniendo a cero los tres primeros valores (T_{i}, oid_{i} y n) de las alturas TORA. El cuarto valor de altura, \delta_{i}, adopta el valor del número de saltos efectuados por el paquete OPT desde su transmisión desde el encaminador BS (de forma similar a la propagación de paquetes UPD en los conocidos mecanismos TORA de creación de DAG iniciados por la fuente). Puede añadirse un incremento de 1 para representar el salto desde el encaminador BS hasta el nodo móvil. El quinto valor de altura, i, adopta el valor del ID del nodo.

Una vez se dispone de un DAG agrupado en el AS, cada nodo de conmutación de paquetes del AS presenta una entrada en la tabla de envío al siguiente salto para el prefijo de dirección IP en cuestión. Cuando llega un paquete a un nodo que requiere encaminamiento, el nodo busca en su tabla de envío al siguiente salto la entrada de dirección coincidente más larga que utilizará para tomar la siguiente decisión de encaminamiento que, a condición de que el nodo móvil que utiliza la dirección IP no haya cambiado de lugar respecto del encaminador BS propietario, será el prefijo de dirección IP. Si se proporcionan DAG agrupados dentro del AS, el tamaño de la tabla de encaminamiento y el procesamiento de encaminamiento podrán reducirse al mínimo en cada nodo de conmutación de paquetes.

No obstante, cuando un nodo móvil experimenta una transferencia en la capa de enlace inalámbrico, lejos del encaminador BS donde recibió el servicio por primera vez en la red, se crea una entrada de dirección de nodo individual en la tabla de datos de protocolo de encaminamiento y en la tabla de envío al siguiente salto en (un número limitado de) los nodos de conmutación de paquetes que se han visto afectados por las actualizaciones de encaminamiento ocasionadas por la movilidad del nodo móvil. Estos nodos continúan almacenando las correspondientes entradas de direcciones agrupadas, pero utilizan la entrada de dirección de nodo para encaminar paquetes hacia la dirección IP del nodo móvil, mediante una búsqueda de la dirección coincidente más larga.

El algoritmo de mantenimiento de altura TORA se incluye en la misma clase general de algoritmos definidos inicialmente en el documento "Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology", E. Gafni y D. Bertsekas, IEEE-Trans. Commun., enero de 1991. Dentro de esta clase, un nodo sólo puede "incrementar" su altura y nunca puede reducirla. No obstante, en esta forma de realización de la presente invención, se proporciona una modificación algorítmica para asegurar que, después de una transferencia entre encaminadores BS, si existe una pluralidad de interfaces de encaminamiento con los nodos vecinos, un nodo envíe paquetes, a través de una interfaz de encaminamiento, al nodo vecino desde el cual se ha recibido la actualización de encaminamiento relacionada con la movilidad más reciente. El valor de tiempo \tau del quíntuplo de altura (\tau_{i}, oid_{i}, r_{i}, \delta_{i}, i), almacenado en la tabla de datos de protocolo de encaminamiento del encaminador como una entrada junto a la dirección IP del nodo móvil y el nodo vecino en cuestión, puede adoptar un valor "negativo", es decir, inferior a cero, para indicar que ha tenido lugar una actualización relacionada con la movilidad, y la magnitud del valor de tiempo \tau negativo se incrementa por cada actualización de encaminamiento relacionada con la movilidad para una dirección IP dada. Por lo tanto, la actualización relacionada con la movilidad más reciente viene indicada por el valor de tiempo \tau negativo mayor. Debe observarse que, aunque las actualizaciones de encaminamiento relacionadas con la movilidad se diferencian mediante un valor de tiempo \tau negativo, es posible utilizar otros indicadores, tales como una etiqueta de un bit, en lugar de la etiqueta negativa.

Cuando un nodo móvil cambia su afiliación con un encaminador BS, el nodo móvil reduce su valor de altura aplicando una reducción de un entero, por ejemplo, al valor de tiempo \tau, y el nuevo valor se transmite a un número limitado de nodos del AS como parte de una actualización iniciada por un nodo móvil del DAG asociado a la dirección IP del nodo móvil, que se describirá en mayor detalle más adelante. Un nodo que presenta varios nodos vecinos aguas abajo se encamina hacia el enlace aguas abajo que se ha activado en último lugar. Las alturas todavía están totalmente ordenadas (por consiguiente, se mantiene la libertad del bucle de encaminamiento).

Otro aspecto de esta forma de realización de la presente invención es que, durante la transferencia de un nodo móvil en la capa de enlace inalámbrico, se proporciona un mecanismo de tunelado temporal a corto plazo que permite que los paquetes de datos que llegan al encaminador BS, desde el cual se efectúa la transferencia del nodo móvil, puedan ser enviados al encaminador BS, hasta el cual se efectúa la transferencia del nodo móvil. El tunelado en una red de conmutación de paquetes IP puede llevarse a cabo mediante encapsulado del paquete de datos con una nueva cabecera IP (dirigida hacia la dirección IP del nuevo encaminador BS), denominándose este tipo de tunelado "tunelado IP en IP". En el nuevo encaminador BS, el paquete se desencapsula y se envía hacia el nodo móvil por medio del enlace inalámbrico. Los mecanismos de establecimiento de túneles, señalización y autenticación pueden ser los utilizados en las redes "IP móviles", descritas inter alia en el documento "IP Mobility Support", C. Perkins, ed., 1ETF RFC 2002, octubre de 1996. Si todos los encaminadores BS presentan tecnología "móvil iP", la tecnología "móvil IP" puede utilizarse también para permitir el envío de paquetes a los nodos móviles que se desplazan hacia un AS diferente. Otros protocolos de tunelado posibles incluyen el tunelado UDP (en el que se añade una cabecera UDP a los paquetes de entrada), el tunelado GRE (un protocolo CISCO™), el protocolo de tunelado de capa 2 (L2TP) y modos de túnel IPSEC negociados o configurados.

Cuando debe efectuarse la transferencia de un nodo móvil desde un encaminador BS, dicho encaminador BS interactúa con el nuevo encaminador BS hacia el cual se va a traspasar el nodo móvil, para emprender las etapas siguientes:

(a)

preparación de un túnel unidireccional hacia el nuevo encaminador BS, de tal forma que los paquetes puedan ser enviados al nodo móvil una vez perdido el enlace inalámbrico entre el encaminador BS antiguo y el nodo móvil. El túnel puede prepararse estableciendo la correspondencia con un túnel entre encaminadores BS preexistente, o con un túnel específico para el nodo, negociado dinámicamente por medio de mecanismos IP móvil;

(b)

transferencia del nodo móvil en la capa de enlace inalámbrico;

(c)

inclusión de una actualización de encaminamiento para la dirección IP del nodo móvil (o las direcciones, en el caso de un encaminador móvil) del nuevo encaminador BS;

(d)

envío de paquetes de datos destinados a la dirección IP del nodo móvil, que llegan al encaminador BS antiguo a través de un enlace de túnel, al nuevo encaminador BS;

(e)

actualización del encaminamiento no válido hacia el encaminador BS antiguo;

(f)

supresión del túnel, si es específico para el nodo, o eliminación del estado específico para el nodo en un túnel preexistente, siguiendo la convergencia del encaminamiento.

Antes de la transferencia, todos los paquetes se encaminan directamente hacia el nodo móvil por medio de una trayectoria, o trayectorias, de la infraestructura que pasa por el encaminador BS antiguo. Siguiendo la convergencia del encaminamiento, todos los paquetes se encaminan directamente hacia el nodo móvil por medio de una trayectoria, o trayectorias, de la infraestructura que pasa por el encaminador BS nuevo.

Cuando se comunica la transferencia al nuevo encaminador BS (ya sea desde el encaminador BS antiguo como parte de la organización en túneles, o bien desde el nodo móvil por medio de una transferencia asistida por móvil), el nuevo encaminador BS genera un mensaje de actualización de encaminamiento de unidifusión dirigida al encaminador BS antiguo, utilizando el DAG existente para la dirección IP del nodo móvil (que sigue estando dirigido hacia el encaminador BS antiguo). Esta actualización modifica de forma selectiva el DAG del nodo móvil a lo largo de la trayectoria inversa del nodo vecino de nivel más bajo (la trayectoria más corta aproximada) hacia el encaminador BS antiguo. Al final de esta actualización, el encaminador BS antiguo presentará un nuevo enlace aguas abajo en el DAG para la dirección IP del nodo móvil, después de que el nodo móvil sea traspasado en la capa de enlace de radio. Durante el procedimiento de actualización, un encaminador de cruce recibe la actualización de unidifusión dirigida y, entonces, redirige el flujo de datos existente hacia el encaminador BS nuevo del nodo móvil.

Este procedimiento de actualización no depende de la topología y se emplea independientemente de la distancia topológica entre los encaminadores BS nuevos y antiguos (que puede variar sustancialmente dependiendo de las posiciones relativas de los encaminadores BS).

El túnel a corto plazo evita la pérdida de paquetes en caso de que no se haya establecido el encaminamiento hacia el nuevo encaminador BS antes de producirse la pérdida del enlace inalámbrico con el encaminador BS antiguo, siempre que no haya tenido lugar un almacenamiento significativo en la memoria caché del encaminador BS antiguo.

Sin embargo, la utilización de un túnel a corto plazo tal vez no sea siempre necesaria, dependiendo de la sucesión relativa de los dos eventos siguientes:

(i)

pérdida del enlace inalámbrico entre el encaminador BS y el nodo móvil en el encaminador BS antiguo y

(ii)

llegada de la actualización de encaminamiento dirigida al encaminador BS antiguo.

Si la actualización de encaminamiento llega antes de que se haya perdido el anterior enlace inalámbrico, el túnel no será necesario, puesto que no llegarán más paquetes de datos al encaminador BS antiguo, debido al reencaminamiento (siempre que los paquetes de control y de datos tengan la misma prioridad y el mismo tratamiento para la puesta en cola; en caso contrario, los paquetes de datos que ya se hallan en la cola pueden seguir llegando después de la actualización de encaminamiento), y todos los paquetes de datos pasados habrán sido enviados al nodo móvil a través del enlace inalámbrico antiguo. Si no se necesita ningún túnel, puede impedirse la activación prematura de una actualización TORA en el encaminador BS antiguo, debida a la pérdida de todos los enlaces aguas abajo cuando se pierde el enlace inalámbrico anterior, marcando un enlace aguas abajo virtual en el encaminador BS antiguo hasta que se produzca la convergencia de encaminamiento. Por lo tanto, la retención del encaminamiento en el encaminador BS antiguo puede lograrse simplemente mediante señalización.

La simple retención de encaminamiento mediante señalización puede utilizarse también cuando el encaminador BS antiguo funciona como una memoria caché (por ejemplo, una memoria caché transparente), permitiendo al encaminador BS antiguo almacenar volúmenes relativamente grandes de datos hasta que se produce la convergencia del encaminamiento, y retransmitiendo los datos una vez que se ha producido la convergencia de encaminamiento.

Como se ha mencionado anteriormente, cuando un nodo móvil finaliza su sesión de acceso, el encaminamiento para la dirección IP del nodo móvil puede reenviarse al encaminador BS desde el cual se ha originado, es decir, el encaminador BS local de la dirección IP. Se proporciona un mecanismo para restaurar de forma eficaz el destino del DAG al encaminador BS local, que requiere la participación de sólo un número limitado de nodos del AS.

Cuando un nodo móvil finaliza su sesión de acceso, el encaminador BS actual entra en contacto con el encaminador BS local de la dirección IP e inicia la transferencia de destino del DAG al encaminador BS local. También esta vez, puede utilizarse un enlace de túnel como mecanismo de retención para evitar el inicio de una actualización de encaminamiento en el encaminador BS actual o, todavía más fácil, puede utilizarse un enlace virtual (una marca de enlace aguas abajo inactivo en el encaminador BS actual) si no hay datos para transmitir. El encaminador BS actual establece un enlace de túnel o un enlace aguas abajo virtual dirigido hacia el encaminador BS local. En respuesta, el encaminador BS local genera una actualización de "restauración" dirigida que se envía hacia el encaminador BS actual mediante el DAG existente para la dirección IP del nodo móvil (que sigue estando dirigido hacia el examinador BS actual). Esta actualización suprime todas las entradas de la tabla de datos de protocolo de encaminamiento específicas para el nodo y las entradas de la tabla de envío al siguiente salto creadas como consecuencia de la movilidad anterior del nodo móvil, para restaurar el DAG agrupado calculado previamente como plan de encaminamiento activo para la dirección IP del nodo móvil. La actualización se transmite a través de la trayectoria creada previamente mediante las actualizaciones de encaminamiento provocadas por la movilidad anterior del nodo móvil. Por lo tanto, el grupo de valores negativos de altura generado por las actualizaciones específicas para la movilidad es suprimido, y se reactiva el DAG agrupado con su nivel de referencia "todo ceros" (suponiendo que no se haya producido ningún fallo en la red que haya provocado nuevas generaciones e inversiones de altura). El enlace de túnel o el enlace virtual pueden mantenerse hasta que se reciba la actualización de restauración en el encaminador BS actual, momento en el cual se eliminará el túnel o el enlace virtual.

Cada cierto tiempo, o cuando se detecta un evento desencadenador, el nodo móvil (o un encaminador BS que actúa en representación del nodo móvil) puede reinicializar el DAG para una dirección IP mediante un mecanismo de actualización TORA, con niveles de referencia "todo ceros", eliminando de ese modo todas las entradas de la tabla de encaminamiento relacionadas con la movilidad para el DAG. Los niveles de referencia "todo ceros" transmitidos de ese modo tienen preferencia sobre el resto de valores de altura (tanto positivos como negativos) y pueden propagarse por todo el AS (reoptimización del DAG en todo el AS). Esto proporciona un mecanismo para el mantenimiento de trayectorias de estado flexible, que altera temporalmente el sistema de actualización relacionada con la movilidad.

A continuación, se describirá un ejemplo detallado de transferencia entre BS en la capa de enlace inalámbrico y de actualizaciones de encaminamiento en la infraestructura fija de un AS, en relación con las Figuras 2 a 11. Se describirá otro ejemplo en relación con las Figuras 12 a 16. Por último, se describirá un ejemplo detallado de la restauración del encaminamiento hacia una BS local una vez finalizada una sesión de acceso de un nodo móvil, en relación con las Figuras 17 a 25. En cada uno de los quíntuplos de altura TORA ilustrados en las Figuras 2 a 25, el ID de nodo se representa mediante la referencia i para simplificar. No obstante, se observará que este valor será diferente para cada nodo, para identificar de forma exclusiva los nodos dentro del AS. Asimismo, se observará que sólo se ilustra una parte del AS para simplificar.

En todos los ejemplos siguientes, el AS incluye una pluralidad de encaminadores centrales fijos (CR1, CR2, ...) una pluralidad de encaminadores intermedios fijos (IR1, IR2, ...) y una pluralidad de encaminadores frontera fijos (ER1, ER2, ...), clasificados según su proximidad relativa con la "frontera" topológica de la infraestructura fija. Los encaminadores centrales pueden estar adaptados para procesar cantidades de tráfico superiores a las de los encaminadores intermedios, y los encaminadores intermedios, a su vez, pueden estar adaptados para procesar cantidades de tráfico superiores a las de los encaminadores frontera. Por ejemplo, los encaminadores centrales pueden procesar tráfico nacional, los encaminadores intermedios tráfico regional y los encaminadores frontera tráfico subregional.

Los encaminadores de conmutación de paquetes tienen emplazamientos comunes y se combinan funcionalmente con las estaciones base inalámbricas, denominándose la entidad combinada en la presente memoria "nodo de acceso" (BS1, BS2, ...), aunque deberá observarse que el término "nodo de acceso" no pretende limitarse a un nodo de encaminamiento que incluye funciones de BS inalámbrica. Por ejemplo, puede proporcionarse un "nodo de acceso" en un nodo que está topológicamente alejado de una BS.

En el caso de todos los ejemplos descritos a continuación, la direccionalidad de encaminamiento de salto en salto en las interfaces se indica mediante flechas a lo largo de los enlaces entre los nodos de la red, y entre nodos de acceso y nodos móviles (incluyendo dichos enlaces un enlace inalámbrico). El plan de encaminamiento distribuido adopta la forma de un DAG TORA dirigido en un único nodo móvil receptor, MH2. Antes de que el nodo móvil MH2 empiece una sesión de acceso, y le sea asignada dinámicamente una dirección IP, se dispone de un DAG agrupado y calculado previamente para la dirección IP dentro del AS, que ha sido incluido como una actualización generalizada para todo el AS desde el nodo de acceso que asigna la dirección IP, es decir, el nodo BS2. En las Figuras 2 a 25, los nodos relacionados con las actualizaciones de encaminamiento o el envío de paquetes se marcan con sus quíntuplos de altura TORA (\tau_{i}, oid_{i}, r_{i}, \delta_{i}, i). Como se ha descrito anteriormente, esta altura TORA se almacena también en la tabla de datos de protocolo de encaminamiento de cada nodo vecino, indicándose el nodo al que se aplica la altura.

Cuando el nodo móvil MH2 se registra en el nodo de acceso local BS2, el nodo de acceso local almacena en memoria caché la identidad del nodo móvil en la capa de enlace inalámbrico, junto a la dirección IP le ha sido asignada, creándose de ese modo una entrada específica para el nodo móvil en una tabla de encaminamiento almacenada en el nodo BS2.

La Figura 2 ilustra un ejemplo de sesión de comunicaciones (por ejemplo, una conexión TCP/IP) que tiene lugar entre el nodo móvil MH2 y otro nodo, en este caso el nodo móvil, MH1. En los ejemplos siguientes, no se produce movilidad del correspondiente nodo móvil MH1, aunque dicha movilidad es posible mediante las mismas funciones que se describirán en relación con la movilidad del nodo MH2. También puede efectuarse una sesión de comunicaciones similar con un correspondiente nodo fijo. En particular, existe un DAG separado dentro del AS dirigido hacia el nodo MH1, mediante el cual los paquetes de datos originados en el nodo MH2 se encaminan hacia el nodo MH1. Puesto que este DAG que se dirige hacia el nodo MH1 no se altera, y se dispone de encaminamiento hacia el nodo MH1 desde cada nodo de acceso al que se afilia el nodo MH2, no se proporcionará ninguna descripción más acerca del encaminamiento hacia el nodo MH1.

Los paquetes de datos originados en el nodo MH1 y destinados al nodo MH2 se encaminan en un principio hacia el nodo de acceso local BS2 por medio de su DAG agrupado (por ejemplo, a través de los nodos fijos BS1, ER1, IR1 y ER2), como se representa en la Figura 2.

Haciendo referencia a la Figura 3, el propio nodo MH2, o el nodo BS2, puede tomar una decisión de transferencia entre BS en la capa de enlace inalámbrico. En el caso de una transferencia iniciada por un nodo móvil, la decisión puede tomarse basándose en la comparación de la calidad del enlace inalámbrico entre las señales recibidas desde los nodos BS2 y BS3. Cuando el nodo móvil MH2 se desplaza, la señal recibida desde el nodo de acceso BS3 puede mejorar, mientras que la señal recibida desde el nodo de acceso BS2 empeora, y en un evento de decisión de umbral, el nodo móvil responde iniciando una transferencia entre los nodos BS2 y BS3. En el caso en que la decisión de transferencia se toma en el nodo BS2, la decisión puede tomarse basándose en otras consideraciones, tales como la carga de tráfico. En dicho caso, el nodo de acceso BS2 transmite la orden de transferencia al nodo MH2.

Tanto si la transferencia entre BS es iniciada por el nodo móvil MH2 como por el nodo de acceso local BS2, el nodo móvil MH2 selecciona un nuevo nodo de acceso BS3 y transmite un paquete de iniciación de túnel (TIN) al nodo de acceso local BS2. El paquete TIN incluye la dirección IP del nuevo nodo de acceso BS3, que el nodo móvil lee en un canal de radiobaliza transmitido por el nodo de acceso BS3. El nodo móvil MH2 también calcula una nueva altura, reduciendo el valor de tiempo \tau de su altura hasta un valor negativo -1 (que indica una primera actualización relacionada con la movilidad fuera del nodo de acceso local BS2), y la incluye en el paquete TIN.

Haciendo referencia a la Figura 4, cuando el nodo de acceso local BS2 recibe el paquete TIN desde el nodo móvil MH2, el nodo de acceso local BS2 establece un enlace de túnel IP en IP de corto plazo hacia el nuevo nodo de acceso BS3. El nodo de acceso local BS2 introduce la interfaz de túnel con el nodo de acceso BS3 en su tabla de encaminamiento, estableciéndose la altura TORA del nuevo nodo de acceso en los valores (-1, 0, 0, 1, i) para asegurar que la interfaz de túnel sea marcada como un enlace aguas abajo para el envío de paquetes de datos durante el resto del procedimiento de transferencia.

Una vez que se ha establecido el enlace de túnel de corto plazo entre el nodo de acceso local BS2 y el nodo de acceso nuevo BS3, el nodo de acceso local BS2 envía el paquete TIN recibido desde el nodo móvil MH2 al nuevo nodo de acceso BS3 por medio de la interfaz de túnel.

En el presente ejemplo, el sistema de enlace inalámbrico utilizado es de un tipo que permite que el nodo móvil MH2 se comunique por medio de dos enlaces inalámbricos con cada nodo de acceso BS2 y BS3 durante una transferencia (como sucede en los sistemas de radio celulares CDMA capaces de efectuar transferencias con continuidad). Por lo tanto, a continuación, el nodo móvil MH2 establece un segundo enlace inalámbrico con el nuevo nodo de acceso BS3, y se efectúa una entrada en la tabla de encaminamiento del nodo BS3, que indica un enlace aguas abajo hacia el nodo móvil MH2.

El nuevo nodo de acceso BS3 genera un paquete de actualización de unidifusión dirigida (UUPD) y transmite el paquete a su nodo vecino de la infraestructura fija, es decir, el nodo ER3. El paquete UUPD está destinado a desplazarse por una trayectoria de unidifusión entre el nuevo nodo de acceso BS3 y el nodo de acceso local BS2, actualizando las entradas de las tablas de datos de protocolo de encaminamiento y, por consiguiente, también las entradas de por lo menos algunas de las tablas de envío al siguiente salto, de todos los nodos situados a lo largo de la trayectoria de actualización y todos los nodos inmediatamente adyacentes a los nodos situados a lo largo de dicha trayectoria (los nodos situados a lo largo de la trayectoria transmiten un aviso de sus nuevas alturas a cada nodo inmediatamente adyacente, estando limitada la propagación de los avisos a un salto).

Haciendo referencia a la Figura 6, una vez que el nodo móvil MH2 ha establecido un nuevo enlace inalámbrico con el nuevo nodo de acceso BS3, se suprime el enlace inalámbrico antiguo con el nodo de acceso local BS2. Los paquetes de datos dirigidos hacia el nodo móvil MH2 que llegan al nodo de acceso local BS2 son enviados al nuevo nodo de acceso BS3 por medio del túnel a corto plazo, y hacia delante hasta el nodo móvil MH2 por medio del nuevo enlace inalámbrico.

Aunque ahora no se dispone del enlace inalámbrico antiguo, no se inicia todavía ninguna actualización de encaminamiento en el nodo de acceso local BS2 (como sucedería según el protocolo TORA), puesto que queda una parte del enlace aguas abajo a lo largo del túnel establecido entre el nodo de acceso local BS2 y el nuevo nodo de acceso BS3. Por lo tanto, el encaminamiento hacia el nodo de acceso local BS2 permanece igual hasta que la actualización de encaminamiento iniciada desde el nuevo nodo de acceso BS3 llega al nodo de acceso local BS2. Como se representa en la Figura 6, el paquete UUPD es enviado desde el primer nodo ER3 que recibe el paquete UUPD, que actualiza asimismo su altura con el valor de tiempo \tau negativo asociado a la actualización de movilidad
(-1), hasta el nodo IR2. El nodo IR2, a su vez, actualiza su altura con el valor de tiempo \tau negativo asociado a la actualización relacionada con la movilidad.

Cada nodo situado a lo largo de la trayectoria de actualización de encaminamiento de unidifusión aplica asimismo a su valor \delta del quíntuplo de altura TORA un incremento unitario por cada salto del paquete de actualización de encaminamiento UUPD, de tal forma que el valor \delta representa el número de saltos hasta el nodo móvil por medio del nuevo nodo de acceso BS3, en lugar del valor \delta de la entrada de la tabla de encaminamiento anterior que indicaba el número de saltos hasta el nodo móvil por medio del nodo de acceso local BS2. Cada enlace situado a lo largo de la trayectoria de actualización de unidifusión dirigida es, pues, dirigido de uno en uno hacia el nuevo nodo de acceso BS3.

Haciendo referencia a la Figura 7, el paquete UUPD se envía a continuación al nodo subsiguiente de la trayectoria de actualización de unidifusión, es decir, el nodo ER2. El nodo ER2 es un encaminador que marca el punto de entrecruzamiento entre la trayectoria de encaminamiento seguida desde el nodo transmisor MH1 hasta el nodo de acceso local BS2 y la trayectoria de encaminamiento que va a ser seguida por los paquetes transmitidos desde el nodo MH1 hasta el nuevo nodo de acceso BS3 (la trayectoria de encaminamiento que se está estableciendo). Como se representa en la Figura 8, una vez que las entradas de la tabla de datos de protocolo de encaminamiento del nodo ER2 se han actualizado tras recibirse los paquetes UUPD, el nodo de cruce ER2 presenta dos enlaces aguas abajo, uno dirigido hacia el nodo de acceso local BS2 y el otro dirigido hacia el nuevo nodo de acceso BS3. Sin embargo, debido a que el enlace aguas abajo dirigido hacia el nuevo nodo de acceso BS3 incluye un valor de tiempo \tau negativo que indica una actualización (la más reciente) relacionada con la movilidad, el enlace aguas abajo dirigido hacia el nuevo nodo de acceso BS3 se selecciona preferentemente como enlace de envío al siguiente salto. Los paquetes de datos que llegan al nodo ER2 dirigidos al nodo móvil MH2 son enviados al nodo IR2, a lo largo de la trayectoria de encaminamiento hacia el nuevo nodo de acceso BS3. Después del desvío de la trayectoria de encaminamiento en el encaminador de cruce ER2, no se envía ningún paquete de datos más al BS2 ni se envía ningún paquete de datos más a través de la interfaz de túnel entre el nodo BS2 y el nodo BS3. No obstante, la interfaz de túnel se mantiene entonces igual en el nodo de acceso local BS2, para asegurar que no se genere ninguna actualización de encaminamiento desde el nodo de acceso local BS2 (debido a la pérdida de todos sus enlaces aguas abajo) hasta que el paquete UUPD llegue al nodo de acceso local BS2. Cuando el paquete UUPD llega al nodo de acceso local BS2, se eliminan las entradas del estado del túnel de la tabla de encaminamiento del BS2, eliminándose de ese modo la interfaz de túnel para MH2.

Haciendo referencia a la Figura 9, se observará que la altura del nodo de acceso local BS2 no se redefine tras recibirse el paquete UUPD (no obstante, la dirección del enlace entre el nodo BS2 y ER2 se invierte, debido al valor de tiempo \tau negativo definido en la altura para el nodo ER2, permitiendo de ese modo que otros nodos móviles que reciben el servicio por medio del nodo BS2 transmitan paquetes al nodo MH2), puesto que el nodo de acceso local BS2 constituye el final de la trayectoria de actualización de unidifusión.

Por último, tras recibirse el mensaje UUPD, el nodo de acceso local BS2 puede transmitir un acuse de recibo de actualización completa (UUPD-Ack) hacia el nuevo nodo de acceso BS3. El paquete UUPD-Ack sigue la trayectoria de encaminamiento de unidifusión actualizada establecida en el DAG hacia el nuevo nodo de acceso BS3. Una vez transmitido el paquete UUPD-Ack, el nodo de acceso antiguo BS3 abandona el control provisional del DAG para la dirección IP que asignó en un principio al nodo móvil MH2. Tras recibir el paquete UUPD-Ack, el nuevo nodo de acceso BS3 asume el control provisional del DAG para la dirección IP del nodo móvil.

La actualización de encaminamiento asociada a la transferencia entre BS de la estación móvil en la capa de enlace de radio finaliza ahora, incluyendo la redefinición de la altura de sólo un número limitado de nodos (en el ejemplo representado en la Figura 9, sólo cinco nodos) situados a lo largo de la trayectoria de actualización de unidifusión. Además, la actualización de las entradas de la tabla de datos de protocolo de encaminamiento también está limitada, siendo sólo necesarias dichas actualizaciones en los nodos que reciben el mensaje UUPD y los nodos inmediatamente adyacentes (que reciben un aviso de las nuevas alturas y almacenan las nuevas alturas en sus tablas de encaminamiento). En el ejemplo representado en la Figura 9, las actualizaciones de la tabla de datos de protocolo de encaminamiento también se llevan a cabo en cada uno de los nodos IR1, CR1, CR2 y CR3.

Las Figuras 10 y 11 representan el estado del DAG dentro del AS, antes y después de una subsiguiente actualización relacionada con la movilidad. En este caso, el nodo móvil MH2 es traspasado a un nuevo nodo de acceso BS4 desde el nodo de acceso BS3, al cual el nodo móvil fue traspasado previamente desde el nodo de acceso BS2. El procedimiento empleado es el mismo que el descrito en relación con la actualización relacionada con la movilidad provocada por la primera transferencia del nodo móvil desde el nodo de acceso BS2 hasta el nodo de acceso BS3, excepto en que la nueva altura generada por la actualización de unidifusión enviada desde el nuevo nodo de acceso BS4 incluye otro incremento en el valor de tiempo \tau negativo (que se incrementa en magnitud hasta -2), para diferenciar las alturas que han sido actualizadas en relación con la movilidad producida en segundo lugar de las alturas que han sido actualizadas en relación con la movilidad producida en primer lugar (con un valor de tiempo \tau de -1), y las alturas que han sido actualizadas en relación con la movilidad de las alturas asignadas en el DAG calculado previamente (con un valor de tiempo \tau de 0). Como se representa en la Figura 1, los nodos relacionados con la nueva actualización presentan inicialmente alturas que incluyen un valor de tiempo \tau igual a 0, hecho que indica que las alturas son las definidas en el DAG calculado previamente.

A continuación, se describirá, en relación con las Figuras 12 a 16, otro ejemplo de actualización de encaminamiento relacionada con la movilidad, en el que el nodo móvil es (como en un sistema de radio celular GSM) capaz de comunicarse sólo por medio de un único enlace inalámbrico en cualquier momento particular. En este caso, las etapas descritas en relación con las Figuras 2 a 4 del ejemplo anterior son idénticas. Como se representa en la Figura 12, el paquete UUPD enviado desde el nuevo nodo de acceso BS3 se genera en respuesta a la recepción de un paquete TIN a lo largo de la interfaz de túnel.

Haciendo referencia a la Figura 13, en primer lugar, el nodo móvil MH2 pierde su enlace inalámbrico con el nodo de acceso local BS2, y al cabo de un corto período de tiempo (para permitir la resincronización con el nuevo nodo de acceso BS3 en la capa de enlace inalámbrico, etc.) se puede volver a establecer el nuevo enlace inalámbrico con el nuevo nodo de acceso BS3. Durante el período en que el nodo móvil MH2 no presenta enlaces inalámbricos, los paquetes que llegan al nodo de acceso local BS2 son transmitidos por la interfaz de túnel desde el nodo de acceso local BS2 y puestos en cola en el nuevo nodo de acceso BS3 hasta que se establece el nuevo enlace inalámbrico. A continuación, o bien se establece el nuevo enlace inalámbrico o bien llega el paquete UUPD al nodo de acceso local BS2. Cuando en primer lugar se establece el nuevo enlace inalámbrico, el nuevo nodo de acceso BS3 asume de inmediato el control provisional del DAG para la dirección IP del nodo móvil. En caso contrario, el nuevo nodo de acceso BS3 espera a recibir el mensaje UUPD-Ack desde el nodo de acceso local BS2. El resto de etapas descritas en relación con el ejemplo anterior (eliminación de túnel, movilidad subsiguiente, etc.) también son aplicables al presente ejemplo.

Las Figuras 17 a 25 ilustran un procedimiento por medio del cual, cuando un nodo móvil finaliza una sesión de acceso, se llevan a cabo actualizaciones de encaminamiento que restauran el DAG para la dirección IP del nodo móvil a la condición en la que se hallaba el DAG antes de que la dirección IP se asignara originalmente al nodo móvil. El procedimiento de actualización de encaminamiento incluye la transmisión de las actualizaciones de encaminamiento sólo a un número limitado de nodos del AS (a lo largo de las trayectorias en las que se llevaron a cabo actualizaciones de unidifusión relacionadas con la movilidad), siendo necesarias actualizaciones en las tablas de datos de protocolo de encaminamiento de sólo un número limitado de nodos (los nodos por los cuales pasan los mensajes de actualización de encaminamiento restaurado dirigida y los nodos inmediatamente adyacentes).

Haciendo referencia a la Figura 17, cuando el nodo móvil MH2 finaliza la sesión de acceso, el nodo de acceso actual BS4 transmite una petición de restauración (RR) al nodo de acceso local BS2 para la dirección IP. Esto puede llevarse a cabo conociendo la identidad del nodo de acceso "local" para la dirección IP en el nodo de acceso actual. La información en cuestión puede ser proporcionada transmitiendo la identidad de la BS propietaria cuando se crea el DAG agrupado mediante el mecanismo de actualización de paquetes OPT, y almacenando esta identidad como datos de protocolo de encaminamiento, además del resto de datos de protocolo de encaminamiento almacenados en los nodos de acceso. Otra posibilidad es que esta información sea proporcionada a través del almacenamiento por el nodo móvil de la identidad de la BS local cuando se asigna su dirección IP por primera vez, y la transmisión y el almacenamiento temporal de dicha identidad en cada nodo de acceso, desde el cual el nodo móvil recibe el servicio durante su sesión de acceso. Por lo tanto, cuando el nodo móvil MH2 termina su sesión de acceso, el nodo de acceso actual BS4 transmite el paquete RR, que en un principio lleva la dirección IP del nodo móvil y está encapsulado con la dirección IP del nodo de acceso local BS2, a lo largo de un enlace de túnel IP en IP con el nodo de acceso local BS2.

Como alternativa a la necesidad de obtener información sobre la identidad de la BS local para una dirección IP, el paquete RR puede ser transmitido con la dirección IP del nodo móvil como dirección de destino, aunque con un identificador en la cabecera, que indique a cada nodo transmisor que el paquete debe encaminarse a lo largo de la trayectoria de encaminamiento del DAG agrupado, que sigue manteniendo su dirección en la BS local durante toda la sesión de acceso.

Como respuesta a la recepción del paquete RR, el nodo de acceso local BS2 marca, en sus tablas de encaminamiento, un enlace aguas abajo con el nodo móvil MH2. Este enlace aguas abajo es un enlace virtual, puesto que el nodo móvil no establece actualmente ninguna comunicación inalámbrica con ningún nodo de acceso y, de hecho, está situado en la zona de servicio de un nodo de acceso diferente (la del nodo de acceso BS4). Una vez que el nodo móvil ha finalizado su sesión de acceso, cualquier paquete para el nodo móvil MH2 que llegue al nodo BS4 puede ser enviado a lo largo del túnel hasta el nodo de acceso local BS2, y puede ser almacenado ahí para su posterior envío al nodo móvil MH2 al iniciar éste una nueva sesión de acceso.

Cuando se recibe el paquete RR, el nodo de acceso local BS2 restablece también la altura del nodo móvil MH2 (ahora virtual) en un nivel de referencia "todo ceros", y envía un paquete de actualización de restauración de unidifusión dirigida (UDRU) hacia el nodo de acceso actual BS4, por medio de la infraestructura fija del AS, ilustrada en la Figura 18. El paquete UDRU se envía a lo largo de una trayectoria de unidifusión, que incluye sólo los nodos que tienen alturas redefinidas previamente como resultado de una actualización relacionada con la movilidad. En el ejemplo representado en la Figura 18, estos nodos son los nodos ER2, IR2, ER3, IR3, CR4, IR4, ER4 y BS4.

Cuando el paquete UDRU es recibido en cada uno de los nodos situados a lo largo de la trayectoria de unidifusión, las alturas TORA de cada nodo se restablecen en un nivel de referencia "todo ceros", y los valores \delta de las alturas se redefinen para representar el número de saltos hasta el nodo móvil (ahora virtual) por medio del nodo de acceso local, en lugar de los valores de las entradas previas que indicaban el número de saltos hasta el nodo móvil por medio del nodo de acceso actual. Este procedimiento se ilustra en las Figuras 18 a 22.

Además de la actualización de alturas a lo largo de la trayectoria de actualización de unidifusión, las alturas actualizadas se comunican a cada nodo inmediatamente adyacente. Cualquier nodo que presente un valor de tiempo \tau negativo en su propia altura y que reciba el aviso de que se ha restablecido el valor de tiempo \tau negativo en 0, como en el caso del nodo de acceso BS3 (ilustrado en la Figura 20), también restablecerá su propia altura en un nivel de referencia "todo ceros", definirá su valor \delta para indicar el numero de saltos hasta la estación móvil (ahora virtual) por medio del nodo de acceso local, generará un aviso de su nueva altura y la transmitirá a todos sus vecinos. Todos los vecinos que reciban el aviso de nueva altura y que no restablezcan sus propias alturas no propagarán más el aviso.

Como se ilustra en la Figura 23, cuando el nodo de acceso actual BS4 recibe el paquete UDRU, el nodo de acceso actual suprime el estado asociado al nodo móvil MH2 de sus tablas de encaminamiento y transmite un mensaje UDRU-Ack, a lo largo de la trayectoria de encaminamiento acabada de crear mediante la actualización de unidifusión, hacia el nodo de acceso local BS2, abandonando de ese modo el control provisional del DAG para la dirección IP utilizada previamente por el nodo móvil MH2.

Como se representa en la Figura 24, el paquete UDRU-Ack finalmente llega al nodo de acceso local BS2. Una vez recibido dicho paquete, el nodo de acceso local BS2 elimina todos los estados asociados al nodo móvil MH2 y asume el control del DAG para la dirección IP. A continuación, la dirección IP puede ser asignada dinámicamente una vez más a un nodo móvil MH3 diferente que inicia una sesión de acceso en la zona de servicio del nodo de acceso BS2, como se representa en la Figura 25.

En resumen, las siguientes modificaciones del protocolo de encaminamiento (que pueden utilizarse por sí solas o en cualquier combinación) proporcionadas por la presente invención incluyen:

1.

Almacenamiento de datos de protocolo de encaminamiento distintivos (niveles de referencia de altura "negativos" en el caso del protocolo TORA) generados como consecuencia de la movilidad, de tal forma que los paquetes son enviados hacia el nodo vecino situado aguas abajo asignado en último lugar.

2.

Incorporación de actualizaciones de movilidad de unidifusión dirigidas para ajustar el encaminamiento cuando se produce una transferencia, alterando los datos de protocolo de encaminamiento almacenados en sólo un grupo limitado de nodos de un AS.

3.

Incorporación de actualizaciones de restauración de unidifusión dirigidas para suprimir los efectos de la movilidad basada en una transferencia (niveles de referencia de altura "negativos" en el caso del protocolo TORA).

Debe sobrentenderse que las formas de realización no se limitan a las descritas anteriormente, admitiendo éstas cualquier modificación o variante que pueda ser concebida por las personas expertas en la materia.

Las formas de realización descritas anteriormente describen un protocolo de encaminamiento modificado basado en el protocolo de encaminamiento TORA. No obstante, pueden utilizarse algunos aspectos de la presente invención para modificar otros protocolos de encaminamiento conocidos, tales como el OSPF, el RIP, etc.

Además, aunque en las formas de realización descritas anteriormente la infraestructura del sistema autónomo es fija, debe observarse que uno o varios de los encaminadores de la infraestructura puede ser un encaminador móvil, tal como los utilizados en el campo de las comunicaciones por satélite y en otros sistemas en los que uno o varios encaminadores de la infraestructura presentan movilidad a largo plazo. Además, los nodos móviles también pueden estar conectados a un nodo de acceso por medio de un enlace de comunicaciones móviles no inalámbrico, tal como una conexión por cable enchufable.

Claims (23)

1. Procedimiento para controlar el encaminamiento de paquetes en una red de conmutación de paquetes, que incluye una infraestructura de nodos de conmutación de paquetes interconectados mediante enlaces de transporte de paquetes y una pluralidad de nodos de acceso hacia los cuales una trayectoria de encaminamiento, definida por los datos almacenados en los nodos de conmutación de paquetes situados a lo largo de dicha trayectoria de encaminamiento, puede dirigirse en dicha infraestructura para una dirección de red dada, comprendiendo dicho procedimiento:

el encaminamiento de paquetes a lo largo de una primera trayectoria de encaminamiento para una primera dirección de red, en el que dicha primera trayectoria de encaminamiento es una de entre una o más trayectorias de encaminamiento dirigidas hacia un primer nodo de acceso (BS2) para dicha primera dirección de red, y dicho primer nodo de acceso (BB2) presta servicio a un nodo móvil (MH2) utilizando dicha primera dirección de red por medio de un enlace de comunicaciones y

la alteración del encaminamiento en una pluralidad de nodos de conmutación de paquetes de dicha infraestructura cuando dicho primer nodo móvil (MH2) recibe servicio desde un segundo nodo de acceso (BS3);

caracterizado porque dicha etapa de alteración del encaminamiento comprende la transmisión de mensajes de actualización de encaminamiento dirigidos a un subconjunto limitado de dichos nodos de conmutación de paquetes para crear una segunda trayectoria de encaminamiento para dicha primera dirección de red, estando localizado dicho subconjunto en el área de una trayectoria de conexión entre dicho primer (BS2) y segundo (BS3) nodos de acceso y comprendiendo por lo menos los nodos de conmutación de paquetes (ER2, IR2, ER3) situados a lo largo de dicha trayectoria de conexión, y siendo dicha segunda trayectoria de encaminamiento una de entre una o más trayectorias de encaminamiento dirigidas hacia dicho segundo nodo de acceso (BS3) para dicha primera dirección de red.

2. Procedimiento según la reivindicación 1, en el que dichos mensajes de actualización de encaminamiento se originan en dicho segundo nodo de acceso (BS3).

3. Procedimiento según la reivindicación 1 ó 2, en el que dichos mensajes de actualización de encaminamiento se transmiten a los nodos de conmutación de paquetes adyacentes a dicha trayectoria de conexión, mientras se limita la propagación de dichos mensajes fuera de dicha trayectoria de conexión.

4. Procedimiento según cualquiera de las reivindicaciones anteriores, que comprende las etapas antecedentes siguientes:

asignación de una o más direcciones de red a dicho primer nodo de acceso (BS2);

asignación dinámica de una primera de dichas direcciones de red a dicho nodo móvil (MH2);

comprendiendo además dicho procedimiento:

cuando dicha dirección de red queda disponible para la reasignación, alteración del encaminamiento en dicha infraestructura, de tal forma que por lo menos una trayectoria de encaminamiento de dicha infraestructura se dirija hacia dicho primer nodo de acceso (BS2) para dicha primera dirección de red, y transmisión de un mensaje de encaminamiento hacia dicho primer nodo de acceso (BS2), que indica que dicha primera dirección de red puede asignarse a un segundo nodo móvil (MH3) que es servido por dicho primer nodo de acceso (BS2).

5. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que una pluralidad de dichas direcciones de red presenta una entrada agregada a los datos de encaminamiento almacenados en un primer nodo de conmutación de paquetes de dicha infraestructura, cuando dicha pluralidad de direcciones de red presenta por lo menos una trayectoria de encaminamiento dirigida hacia dicho primer nodo de acceso (BS2).

6. Procedimiento según la reivindicación 5, en el que, cuando una dirección de red de dicha pluralidad presenta una trayectoria de encaminamiento dirigida hacia un segundo nodo de acceso (BS3), dicha entrada agregada de dicho primer nodo de conmutación de paquetes no se utiliza para encaminar paquetes hacia dicha primera dirección de red.

7. Procedimiento según la reivindicación 6, en el que dicha pluralidad de direcciones de red presenta una entrada agregada a los datos de encaminamiento almacenados en un segundo nodo de conmutación de paquetes de dicha infraestructura, cuando dicha pluralidad de direcciones de red presenta por lo menos una trayectoria de encaminamiento dirigida hacia dicho primer nodo de acceso (BS2), y dicha entrada agregada a los datos de encaminamiento almacenados en dicho segundo nodo de conmutación de paquetes se utiliza para encaminar paquetes hacia dicha dirección de red, cuando dicha dirección de red presenta una trayectoria de encaminamiento dirigida hacia dicho segundo nodo de acceso (BS3).

8. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dicho primer (BS2) y dicho segundo (BS3) nodos de acceso se hallan en emplazamientos separados, y en el que se produce un cambio de servicio entre dicho primer (BS2) y dicho segundo (BS3) nodos de acceso, debido a la movilidad de dicho nodo móvil (MH2), que conlleva la transferencia del enlace de comunicaciones de dicho nodo móvil (MH2).

9. Procedimiento según cualquiera de las reivindicaciones 4 a 8, en el que dicha primera dirección de red se asigna a dicho nodo móvil (MH2) durante una sesión de acceso, y dicha etapa de alteración subsiguiente se produce tras la finalización de la sesión de acceso.

10. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dicha red forma un sistema autónomo (AS) en una interred que ejecuta un protocolo de encaminamiento de red sin conexión que es un protocolo de pasarela interior (IGP).

11. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dichos nodos de acceso comprenden estaciones base de un sistema de comunicaciones de radio celulares.

12. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dichos nodos de acceso comprenden un servidor de acceso a la red de un proveedor de acceso a Internet de línea fija.

13. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que los paquetes se transmiten a lo largo de dicha trayectoria de encaminamiento mediante encaminamiento de salto en salto, siendo tomada una decisión de encaminamiento en cada nodo de conmutación de paquetes situado a lo largo de dicha trayectoria de encaminamiento.

14. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dicho nodo móvil (MH2) es un encaminador móvil que presta servicio a un nodo móvil mediante dicha primera dirección de red para las comunicaciones con uno o más nodos diferentes a través de dicha red.

15. Procedimiento según la reivindicación 1, en el que dicho mensaje de actualización de encaminamiento dirigido es un mensaje de actualización de unidifusión.

16. Procedimiento según la reivindicación 15, que comprende:

la transferencia del enlace de comunicaciones del nodo móvil (MH2), de tal forma que el segundo nodo de acceso (BS3) preste servicio a dicho nodo móvil (MH2); y

el encaminamiento de paquetes hacia dicho segundo nodo de acceso (BS3) por medio de dicha segunda trayectoria de encaminamiento.

17. Procedimiento según la reivindicación 16, que comprende además:

la transmisión de otros mensajes de actualización de encaminamiento dirigidos a un subconjunto limitado de dichos nodos de conmutación de paquetes, estando localizado dicho subconjunto en el área de dicha trayectoria de conexión, para crear una tercera trayectoria de encaminamiento para dicha primera dirección de red, dirigiéndose dicha tercera trayectoria de encaminamiento hacia dicho primer nodo de
acceso (BS2).

18. Procedimiento según la reivindicación 17, en el que dichos otros mensajes de actualización de encaminamiento dirigidos se transmiten en respuesta a la finalización de una sesión de acceso para dicho nodo móvil (MH2).

19. Procedimiento según cualquiera de las reivindicaciones 15 a 18, en el que dicha una o más trayectorias de encaminamiento dirigidas hacia dicho primer nodo de acceso (BS2) se calculan previamente en dicha red, y dicha segunda trayectoria de encaminamiento se crea en respuesta a la movilidad de dicho nodo móvil (MH2) entre dicho primer (BS2) y segundo (BS3) nodos de acceso.

20. Procedimiento según la reivindicación 1 ó 15, en el que dicho mensaje de actualización de encaminamiento dirigido se transmite al finalizar una sesión de acceso para dicho nodo móvil (MH2).

21. Procedimiento según la reivindicación 20, en el que dicha segunda trayectoria de encaminamiento corresponde a una trayectoria de encaminamiento calculada previamente en dicha infraestructura para dicha primera dirección de red antes del inicio de dicha sesión de acceso.

22. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dicha dirección de red es una dirección de protocolo de Internet IP.

23. Procedimiento según cualquiera de las reivindicaciones anteriores, en el que dicho enlace de comunicaciones es un enlace inalámbrico.