CN1471784A - Telecom Routing - Google Patents

Abstract

A method of controlling routing of packets in a packet switched network including an infrastructure of packet switching nodes interconnected by packet transport links, and a plurality of access nodes to which a routing path, defined by routing entries held in packet switching nodes located along said routing path, may be directed in said infrastructure for a given network address, said method comprising: allocating a first said network address to a first mobile node being served via a communications link by a first access node, at least a first routing path in said infrastructure being directed to said first access node for said first network address; altering routing in said infrastructure when said first mobile node receives service from a second access node, such that at least a second routing path in said infrastructure is directed to said second access node for said first network address, said second routing path being defined at least in part by one or more host-specific routing entries; during a period of subsequent inactivity, removing said one or more host-specific routing entries from said infrastructure such that said mobile node has no current routing path in said network; and during during said period of inactivity, providing two separate states for said mobile node: a) a state in which said mobile node retains said first network address; and b) a state in which said first network address may be reallocated to a different mobile node.

Description

Telecom Routing

technical field

The present invention relates to the routing of telecommunication signals, and in particular to the routing of packet-based communications, such as those used in the "Internet" using the so-called "Internet Protocol" (IP). The present invention, in one embodiment, relates to a method of routing such communications to fixed and mobile telecommunications mediums so that users can use similar services in the same manner on either medium, and through switching equipment and other network-based Greater versatility of equipment allows system operators to reduce costs.

Background technique

Current mobile media systems are designed in such a way that mobile users and associated systems cooperate at a network interface (usually a radio base station) to enable a mobile node to change from communicating with one base station to another, and to enable the network to update The smart point for this new location. In cellular networks these smart points are Home Location Register and Visitor Location Register (HLR and VLR), while in "Mobile IP" these locations are called Home Agent and Foreign Agent. In both cases, "visitor" location registers or "foreign" agents maintain a record relating only to those users who are cooperating with base stations under their supervision, while their corresponding "home" location registers or "local "Agents then maintain a permanent record of their associated users, including a record of which VLR or external agent each "local" unit is working with. The address in an incoming message identifies the associated HLR/Home Agent, this information is consulted to identify the appropriate VLR/Foreign Agent for more specific routing details. This allows small location changes within the VLR/foreign agent close to the user's current location without informing the HLR/home agent further away, thus greatly reducing signaling overhead.

Other costs of mobility are providing this Home Agent/Foreign Agent interface, especially for packet systems, also including the cost of tunneling (forwarding messages from one address to another), address exhaustion (failure to reuse a forwarding address), and triangular routing.

In fixed-media systems, IP routing is based on the assignment of IP address blocks or prefixes (with associated metrics or routing costs) from potential destinations to potential senders, such that senders and intermediate routers can determine the best route to a destination. next hop (adjacent router). These routes are precomputed for all destinations in the network, allowing senders to send messages as soon as they are generated. Precomputation of routes and configured routing switching techniques are possible when the source and destination have fixed locations and the communication bandwidth is sufficient for an exhaustive exchange of routes. However, as the roaming ratio increases, this model tends to fail and a more dynamic routing approach is required.

R. Ramjee, T. La Por, S. Thuel, K. Varadh published a proposal called "HAWAII" as an Internet-Draft on February 19, 1999, titled "IP Micromobility Support Using HAWAII" , published on the Internet Engineering Task Force website http://www.ietf.org/internet-drafts/draft-rimjee-micro-mobility-hawaii-00.txt. HAWAII uses a dedicated path establishment scheme to install host-based forwarding records in specific routers when in a routing domain to support intra-domain micro-mobility, and uses "Mobile IP" for inter-domain micro-mobility by default. In HAWAII, mobile hosts retain their network addresses as they move within the domain. The HAWAII architecture relies on a gateway router in the domain (called the domain root router) to which the default route in the domain is pointed. Each mobile host is assigned a home domain based on its permanent IP address. The path establishment scheme updates a single routing path in a domain so that connection to the mobile host is possible both before and after handoff at the radio link layer. Only those routers located along the single routing path between the domain root router and the base station currently serving the mobile host have routing table entries for the mobile host's IP address. The rest of the routers in the domain route any packets addressed to the mobile host upstream along a default route (rooted at the domain root router) that relies on the tree-like nature of the routing domain to provide the same routing Intersection of downstream routing of paths (for which the router has a separate host record for the mobile host IP address) to the mobile host for the single routing path.

In HAWAII, mobility between domains is supported by a "Mobile IP" mechanism. The root router of the local domain is designated as a local agent, forwarding encapsulated IP packets through the root router of the external domain.

The deficiencies proposed by HAWAII include the concentration of Mobile IP tunnels in a few nodes in the core of the network (domain root routers), such that failure of any of these nodes may result in the loss of all Mobile IP state and associated sessions handled by the failed node. Massive failure. Furthermore, since all routing from outside the local domain to within the local domain and vice versa must occur through the local domain root router, failure of the local domain root router can also lead to large-scale failures.

The inventor's proposal, called "Edge Mobility Architecture" (EMA), provides "Mobility Enhanced Routing" (MER), thereby allowing The movement of the IP address assigned to the mobile node. One proposed type of routing update limits the amount of signaling required to change the route of an IP address by propagating unicast update messages between the mobile node's new and old access routers. As the mobile station moves between access nodes, the resulting routing paths are less efficient.

Contents of the invention

It is desirable to provide an improved method and apparatus for changing routing in the infrastructure of a packet communication network.

In another aspect of the invention there is provided a method of controlling the routing of packets in a packet switched network comprising an infrastructure of packet switched nodes interconnected by packet transport links and a plurality of access nodes, A routing path may be directed to said access node for a given network address in said infrastructure, said routing path being defined by routing records maintained in packet switching nodes arranged along it, said Methods include:

allocating a first of said network addresses to a first mobile node served by a first access node over a communication link, at least one first routing path in said infrastructure being directed to said first access node to for said first network address;

When said first mobile node receives service from a second access node, changing routing in said infrastructure such that at least one second routing path in said infrastructure is directed to said second access node an ingress node for the first network address, the second routing path being defined at least in part by one or more host-specific routing records;

During a subsequent period of inactivity, removing the one or more host-specific routing records from the infrastructure such that the mobile node has no current routing path in the network; and

During the period of inactivity, two separate states are provided for the mobile node:

a) said mobile node retains state of said first network address; and

b) A state in which the first network address can be reassigned to a different mobile node.

By providing these two separate states when host-specific routing has been removed, with state a) the process of re-establishing host-specific routing can be made more efficient, while with state b) the utilization of network addresses can be kept at higher level.

Description of drawings

Other aspects and advantages of the present invention will be better understood from the following embodiments described by way of example with reference to the accompanying drawings, in which:

Figure 1 schematically represents an example of a fixed/mobile topology according to one embodiment of the invention;

Figures 2 to 11 schematically represent an inter-base station handover and accompanying routing update according to one embodiment of the present invention;

Figures 12 to 16 illustrate an inter-base station handover and accompanying routing update according to another embodiment of the present invention;

Figures 17 to 25 illustrate reverting routing to a distribution access node according to one embodiment of the present invention;

Figure 26 schematically represents a routing protocol data table maintained in routing nodes according to an embodiment of the present invention;

Fig. 27 shows a next hop forwarding table maintained in routing node according to one embodiment of the present invention;

28 to 38 represent routing update procedures according to an embodiment of the present invention;

Figure 39 is a state diagram schematically representing different possible states of a mobile node;

Figure 40 represents a loop prevention procedure (loop prevention procedure) according to one embodiment of the present invention; and

Figure 41 shows a network arrangement according to one embodiment of the present invention.

Detailed ways

Referring now to FIG. 1 , an example of a fixed/mobile topology according to one embodiment of the present invention is shown. The topology comprises, for example, three packet-switched networks 2, 4, 6 forming an Autonomous System (AS), the extent of which is schematically indicated by the dark shading in FIG. 1 . One definition of the term "autonomous system" is "a group of routers and networks under the same management" ("Routing in the Internet", Christian Huitema, Prentice-Hall, 1995, page 158). Here, the term "autonomous system" also denotes a routing domain in the art, and also denotes a network, or a group of networks, having routers running the same routing protocol. An autonomous system can connect to other autonomous systems to form a global interconnected network, such as the Internet (this is used as an example below). The routing protocol is an interior gateway protocol, and communication with other autonomous systems is via an exterior gateway protocol such as the Border Gateway Protocol (BGP). Examples of known interior gateway protocols are Routing Information Protocol (RIP) and Open Shortest Path First (OSPF).

The networks 2, 4, 6 forming the fixed infrastructure of the autonomous system comprise a number of Internet Protocol (IP) packet-switching nodes in the form of core routers (CRs) interconnecting the different networks 2, 4, 6 in the AS , multiple edge routers (ER) and bridge routers (BR). All these packet switching nodes in the AS run a single internal IP routing protocol, one embodiment of which is described in more detail below.

One or more Exterior Gateway Routers (EGRs) connect the autonomous system to other autonomous systems on the global Internet.

The autonomous system shown in Figure 1 performs routing for both mobile hosts and stationary hosts (i.e., stationary hosts). For mobile hosts, the routing within the AS is changed as a result of the mobility of the mobile host. No such routing change occurs.

The mobile node may be connected to the network infrastructure by a wireless link, in the example shown, a cellular radio link using a base station provided by the network operator (another A possible type of wireless link is an infrared link). The cellular radio link may be a Time Division Multiple Access (TDMA) system link, such as "GSM", or a Code Division Multiple Access (CDMA) system link, such as "CDMA2000". A mobile node is in the form of a single mobile host 14, and/or a mobile router 16 with multiple hosts connected to it, each communicating with one or more (e.g., in CDMA "soft handoff" ” case) the access node performs radio communication. A base station may be connected to one or more Base Transceiver Stations (BTS), including radio antennas, around which the individual "cells" of the cellular system are formed.

Mobile nodes 14, 16 move between cells of a cellular radio communication network. If an access node serves multiple cells, a mobile node that is handed off between cells can continue to receive packet data through the same access node. However, once a mobile node moves out of range of the access node it is serving from, handover to a new cell may require a change in routing within the AS. Data packets originating from and destined for the mobile node and routed through a given access node prior to handoff using an identifier for that node's IP address may require Routing is performed for the same IP address via a different access node after the handover. A mobile node may join a communication session with a different host through the AS during handoff from one access node to another. Because the connection at the transport layer (for example, in a TCP/IP connection) is defined in part by the IP address of the mobile node, when a mobile node receives service from a different access node, it is desirable that such routing A change to allow this connection to continue using the same IP address.

Stationary hosts may be connected to an access node via a local area network (LAN) 10 running a LAN protocol such as the Ethernet protocol. Stationary hosts can also connect to an access node through the Public Service Telephone Network (PSTN) 12 using a Network Access Server (NAS) 20 provided by an Internet access provider. NAS20 uses a protocol such as PPP or SLIP to dynamically assign fixed IP addresses to fixed hosts connected to NAS20 on a dial-up basis, and originate from or go to each fixed host through a related access node pair. IP grouping of fixed hosts for routing. Although the NAS 20 assigns IP addresses on a dynamic basis, the access nodes used to route packets for the assigned IP addresses do not change during an access session or over an extended period of time. Therefore, routing within an autonomous system does not need to be changed for each stationary host unless due to factors internal to the AS (such as link failure or traffic management).

The Interior Gateway Protocol, the single IP routing protocol used in the AS in this embodiment of the invention, is a revised version of the Time Ordered Routing Algorithm (TORA) routing protocol described in the following reference: Vincent "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks" INFOCOM'97 conference paper by D Park and M Scott Corson, April 7-11, Kobe, Japan; Vincent D Park and M Scott Corson at ISCC "Performance Comparison of Time-Sequenced Routing Algorithms and Ideal Link-State Routing" Presented in '98 Conference Paper, Athens, Greece, June 30-July 2, 1999.

The TORA routing algorithm is executed in a distributed manner, providing loop-free routing, providing multiple routing options (to alleviate congestion), fast route establishment (so that the route can be used before the topology changes), and by In some cases, localize the algorithm's response to topology changes to minimize communication overhead (conserve available bandwidth and improve scalability).

Distribute the algorithm among nodes that only need to maintain information about neighboring nodes (ie, knowledge of one hop). This ensures that all routes are loop-free and generally provides multipath routing for any source/destination pair that requires one. Since multiple routes are usually established, many topology changes do not require routing updates within the AS, since a single route is sufficient. The protocol re-establishes valid routing after a topology change that needs to be reacted.

The TORA protocol models a network as a graph G=(N, L), where N is a finite set of nodes and L is an initial set of undirected links. Each node i ∈ N has a unique node identifier (ID), and each link (i, j) ∈ L allows bidirectional communication (i.e., nodes connected by a link can be in either direction communicate with each other). One of the following three states can then be assigned to each initially undirected link (i, j) ∈ L: (1) undirected, (2) pointing from node i to node j, or (3) pointing from node j to node i. If a link (i, j) ∈ L points from node i to node j, it can be said that node i comes from "upstream" of node j, and node j comes from "downstream" of node i. For each node i, i's "neighbors" N _i ∈ N are defined as the set of nodes j such that (i, j) ∈ L. Each node i always knows its neighbors in the set N _i .

Run a logically separate version of the protocol for each destination (eg, identified by a host IP address) that requires routing.

The TORA protocol can be separated into three basic functions: generating routes, maintaining routes, and deleting routes. Generating a route from a given node to a destination requires building a sequence of directional links from that node to that destination. Generating a route essentially corresponds to assigning directions to links in an undirected network or network portion. The method used to accomplish this task is a query/response process that builds a Directed Acyclic Graph (DAG) rooted at the destination (ie, the destination is the only node with no downstream links). Such a DAG may be called a "destination-oriented" DAG. Maintaining a route involves reacting to topology changes in the network in such a way that the route to that destination is re-established within a finite period of time. When a network partition is detected, all links (in the part of the network that have been separated from the destination) are marked as undirected to remove invalid routes.

The protocol accomplishes these three functions by using three distinct control packets: query (QRY), update (UPD), and clear (CLR). QRY packets are used to generate routes, UPD packets are used to generate and maintain routes, and CLR packets are used to delete routes.

At any given time, for each destination, associate an ordered quintuple called "height" H _i = (τ _i , oid _i , _ri , δ _i , i) with each node i∈N Associated. Conceptually, the five-tuple associated with each node represents the height of the node defined by two parameters: a reference level and a delta relative to that reference level. The reference level is represented by the first three values in the quintuple, while the increment is represented by the last two values. A new reference level is defined whenever a node loses its last downstream link due to a link failure. The first value τ _i representing the reference level is a marker set as the "time" of the link failure. The second value oid _i is the originator ID (ie, the unique ID of the node defining this new reference level). This ensures that reference levels can be sorted exactly lexicographically. The third value _ri is a single bit used to divide each unique reference level into two unique sub-levels. This bit is used to differentiate the original reference level from its corresponding, higher reflected reference level. The first value, _δi, representing the increment, is an integer used to order the nodes relative to a common reference level. This value helps in the propagation of the reference level. Finally, the second value i representing the increment is the node's own unique ID. This ensures that nodes (and indeed all nodes) with a common reference level and the same value of _δi can always be sorted exactly lexicographically.

Each node i maintains its height H _i . Initially, the height of each node in the network (except the destination) is set to NULL, H _i = (-, -, -, -, i). Subsequently, the height of each node i can be modified according to the rules of the protocol. In addition to its own height, each node i maintains records in a routing protocol data table for the IP addresses of hosts with an existing DAG in the network, these records include an array of heights, where each neighbor j∈ N _i has a record HN _ij .

Each node i (except the destination) also maintains a link state array in the routing protocol data table, where there is one record LS _ij for each link (i, j)∈L. The state of the link is determined by the heights H _i and HN _ij and points from higher nodes to lower nodes. If a neighbor j is higher than node i, then mark the link as upstream. If a neighbor j is lower than node i, then mark the link as downstream.

The TORA protocol was originally designed for Mobile Ad-Hoc Networks (MANET), where routers are mobile and interconnected by wireless links. However, in this embodiment of the invention, a modified TORA protocol is used in an autonomous system of fixed infrastructure (such as the system shown in FIG. 1 ) comprising fixed routers interconnected by fixed links, so that Routing changes in the autonomous system are specified when the host changes its point of attachment to the autonomous system, ie an access node.

Fig. 26 schematically shows an example of a routing protocol data table that may be maintained in the packet switching node according to this embodiment.

For each host IP address in the network (or, in the case of the aggregated DAG described in detail below, for each address prefix) IP1, IP2, etc., store the storage node's height _Hi (IP1), _Hi (IP2) and so on. Also, store the identity of each neighboring neighbor (eg w, x, y, z) and the height HN _iw (IP1, IP2, ...), HN _ix (IP1, IP2, ...), HN _iy (IP1, IP2 ,…) and HN _iz (IP1, IP2,…). Finally, for each link identity (L1, L2, L3, L4) corresponding to each neighbor, the link state array for each IP address (or prefix) can be stored in the form of multiple labels, which are used for Indicates an upstream link (U), a downstream link (D), or an undirected link (-).

The link state array maintained in the routing protocol data table allows next-hop forwarding decisions to be made locally in the router maintaining the data. For a fully interconnected network, each router should have at least one downstream link. If there is only one downstream link, select this link as the next hop forwarding link. If there is more than one downstream link, the best downstream link can be selected, for example based on the current traffic load on the two links. In any case, the selected link is entered into the next hop forwarding data table listed by IP address. For example, the next-hop forwarding table shown in FIG. 27 is maintained in a cache memory for quick access when an IP packet requiring routing arrives at the router. The table stores the selected next-hop forwarding links (L2, L1, . . . ) per IP address (or prefix) IP1, IP2, and so on.

The use of a fixed infrastructure of routers, as well as other aspects of the invention described below, can allow aggregation of routing within an AS, especially for IP addresses of mobile hosts. A brief description of IP addressing is given below, in particular how variable length prefixes are used to provide routing aggregation in IP routing networks.

An IP address currently consists of a predetermined number (32) of bits. In the past, IP addresses were assigned on an unstructured basis (known as a "flat" addressing scheme). Class addressing introduces the concept of a two-level routing hierarchy by splitting addresses into network prefix and host fields. Users are assigned Class A, B or C IP addresses to simplify routing and management.

In class A, bit 0 identifies class A, bits 1-7 identify networks (126 networks), and bits 8-31 identify hosts (16 million hosts).

In Class B, bits 0-1 identify Class B, bits 2-15 identify networks (16,382 networks), and bits 16-31 identify hosts (64,000 hosts).

In Class C, bits 0-2 identify Class C, bits 3-23 identify networks (2,097,152 networks), and bits 24-31 identify hosts (256 hosts).

A two-level hierarchy still leaves a flat routing hierarchy between hosts in the network. For example, a class A address block with 16 million hosts would result in all routers in the network containing 16 million routing table entries. Subnetting has been developed to allow a block of host addresses to be split into a variable-length subnet field and host field. This allows routers in the AS to keep only routing table records for subnets (providing routing aggregation for all hosts on each subnet). Use a subnet mask to enable routers to recognize the subnet portion of an address.

According to this embodiment of the invention, by assigning a block of host IP addresses (i.e., a contiguous sequence of IP addresses sharing one or more prefixes) to an access node, e.g., for all IP addresses from within the block Access nodes, referred to herein as allocation access nodes, provide routing aggregation. IP addresses from within the block can be dynamically assigned to the mobile host during an access session of the mobile host, or over a longer period, ie without reallocation between access sessions. In the case of dynamic assignment when a mobile host registers with the cellular network after power-up, when the mobile host is assigned an IP address, the serving access node caches the mobile host's radio link identifier with the assigned IP address. Binding between addresses. An aggregate routing plan (an aggregate DAG in this embodiment) is precomputed within the AS before the mobile host is assigned an IP address. When an IP address is unassigned, in the case of dynamic assignment after a mobile host is powered off, the IP address is returned to the allocating access node, which can then assign the IP address to another mobile host. A mobile host IP address assigned by an access node will have an aggregated DAG until at least one mobile host moves away, in which case the aggregated DAG will remain in place, but will be subject to a mobility-specific routing update procedure. A host-specific exception will be raised on the router (the update only changes routing for a single mobile that has moved away).

Route precomputation in the AS for address prefixes owned by an access node is accomplished by injecting an update message per prefix (herein referred to as an "optimized" (OPT) packet) and building an aggregate DAG of the owned access nodes. Implemented by nodes, the update message overflows across the AS and is effectively advertised as a prefix. The OPT packet is sent by the access node that owns the IP address prefix and controls the aggregated DAG. The OPT packet propagates to all other nodes in the network (regardless of their current altitudes (if set)), and sets (resets) these altitudes to the "all zero" reference level, the first three values of TORA altitude (τ _i , oid _i , r _i ) are all set to zero. The fourth height value _δi is set as the number of hops that the OPT packet has experienced since the access node was sent (this is similar to the UPD packet propagation in the known TORA source-initiated DAG generation mechanism). An increment of 1 can be added to indicate a hop from an access node to a mobile node. The fifth height value i is set as the node ID.

Once an aggregated DAG exists in the AS, each packet-switching node in the AS has a next-hop forwarding table entry for the IP address prefix of interest. When a packet arrives at a node that needs routing, the node searches for the longest matching address record in its next-hop forwarding table, and the next routing decision is based on the longest matching address record. If the mobile node of the address is not far away from the owning access node, then the longest matching address record will be the IP address prefix. By specifying an aggregate DAG within an AS, the routing table size and routing processing on each packet switching node can be minimized.

However, when a mobile node is handed off at the radio link layer from the access node it first received service in the network, among the (limited number of) packet-switched nodes affected by the routing update caused by the mobility of the mobile node A separate host address record is generated in the routing protocol data table and the next hop forwarding table. These nodes continue to store the corresponding aggregate address records, but use the host address records to route packets to the mobile node's IP address according to the longest match search.

The TORA height-preserving algorithm belongs to the same class originally defined by E Gafni and D Bertsekas in "A Distributed Algorithm for Producing Cycle-Free Routing in Networks with Frequently Changing Topologies," published in IEEE Communications Transactions, January 1991 Algorithm category. Within this category, a node can only "increase" its height; it cannot decrease its height. However, in this embodiment of the invention, an algorithm improvement is provided to ensure that after a handover between an access node, the forwarding behavior of a node is such that when there are multiple routing interfaces of neighboring nodes, it passes A routing interface forwards the packet to a neighbor node from which a mobility-related routing update was last received. Time value of τ in height quintuple (τ _i , oid _i , _ri , δ _i , i) stored in router's routing protocol data table (as a record listed by mobile node's IP address and neighbors) is allowed to become "negative", i.e., less than zero, to indicate that a mobility-related update has occurred, and the value of the negative τ time value follows each mobility-related routing update for a given IP address. And increase. Therefore, the most recent mobility-related update is indicated by a large negative τ time value. It should be noted that although mobility-related routing updates are differentiated by a negative τ time value, other indicators, such as a one-bit flag, could be used instead of the negative flag.

When a mobile node changes access node affiliation, it decreases its altitude value by decreasing the τ time value by, for example, an integer, and uses this new value as an index of the DAG associated with the mobile node's IP address. Part of a station-initiated update is propagated to a limited number of nodes in the AS, as described further below. A node with multiple downstream neighbors routes to the most recently activated downstream link. The heights are still all sorted (thus protecting routing loop freedom).

Another aspect of the present invention is to provide a temporary short-term tunneling mechanism during the handover of the mobile node at the wireless link layer, so that the data packets arriving at the access node from which the mobile node is handed over can be is forwarded to the access node to which the mobile node was handed off. Tunneling in an IP packet switched network can be achieved by encapsulating the data packet with a new IP header (addressed to the IP address of the new access node), called "IP-in-IP tunneling". At the new access node, the packet is decapsulated and forwarded over the wireless link to the mobile node. Tunnel setup, signaling and authentication mechanisms may be those used in "Mobile IP" described by C Perkins in "IP Mobility Support" published in 1ETF RFC2002, October 1996. With all access nodes having "Mobile IP" functionality, "Mobile IP" can also be used to allow forwarding of packets to a mobile node moving to a different AS. Other possible tunneling protocols include UDP tunneling (where a UDP header is added to an incoming packet), GRE tunneling (a CISCO(TM) protocol), Layer 2 Tunneling Protocol (L2TP), and negotiated or configured IPSEC tunnel mode.

When a mobile node is to be handed off from an access node, the access node interacts with the new access node to which the mobile node is handed off to perform the following steps:

(a) Prepare a unidirectional tunnel to the new access node so that packets can be forwarded to the mobile node after the wireless link between the old access node and the mobile node is lost. Tunnels can be provisioned by mapping to a pre-existing inter-access-node tunnel or a host-specific tunnel and dynamically negotiated through Mobile IP mechanisms.

(b) Handover the mobile node at the radio link layer.

(c) Inject a routing update for the mobile node's IP address (or addresses, in the case of a mobile router) from the new access node.

(d) forwarding data packets destined for the IP address of the mobile node and arriving at the old access node through a tunnel link to the new access node.

(e) Update invalid routing to old access node.

(f) Break down the tunnel if host-only, or remove the host-only state from a pre-existing tunnel after convergence of routing.

Prior to handover, all packets are routed directly to the mobile node by one or more routes in the infrastructure passing through the old access node. After the convergence of the routes, all packets are routed directly to the mobile node via one or more routes in the infrastructure of the new access node.

When the new access node is notified of the handoff (either from the old access node as part of tunnel establishment, or from the mobile node via a mobile assisted handoff), the new access node generates a directed routing update message, which is unicast to the old access node using the existing DAG for the mobile node's IP address (which still remains pointed to the old access node). The update selectively modifies the mobile station's DAG along the reverse lowest neighbor path (an approximate shortest path) to the old access node. At the end of the update, after the mobile node is handed off at the radio link layer, the old access node will have a new downstream link in the DAG for the mobile node's IP address. A crossover router will receive unicast directed updates during the update process, when an existing data stream is redirected to the mobile node's new access node.

The update procedure is topology independent and can be used regardless of the topological distance between the new and old access nodes (which can vary substantially depending on the relative positions of the access nodes).

This short-term tunnel avoids packet loss in case no routing to the new access node is established when the wireless link to the old access node is lost, and or there is no significant amount of caching in the old access node.

However, the use of short-lived tunnels does not always have to be required, depending on the relative ordering of the following two events:

(i) Loss of the access node to mobile node radio link at the old access node

(ii) Directed routing updates arrive at the old access node.

If the routing update arrives before the old radio link is lost, there is no need for a tunnel since no further data packets will reach the old access node due to rerouting (providing control and data packets with the same queuing priority and processing; If not, data packets already queued will still arrive after the routing update), and all past data packets will be forwarded to the mobile station via the old radio link. If tunneling is not required, a TORA update at the old access node due to loss of all downstream links upon loss of the old radio link can be prevented by marking a dummy downstream link at the old access node until routing converges triggered prematurely. Therefore, routing suppression at the old access node can be achieved only by signaling.

Signaling-only route suppression can also be used where the old access node is used as a cache (e.g. a transparent cache), allowing the old access node to store a relatively large amount of data until routing converges, and once Routing convergence then resends the data.

As mentioned above, when a mobile node ends its access session, the routing of the mobile node's IP address can be returned to the access node that originated the routing, ie the IP address allocating access node. A mechanism is provided to efficiently restore the DAG's destination to the assigned access node, which requires only the participation of a limited number of nodes in the AS.

When a mobile node ends its access session, the current access node contacts the allocating access node for the IP address and initiates the transfer of the DAG's destination to the allocating access node. Likewise, a tunnel link can be used as a suppression mechanism to suppress the initiation of routing updates at the current access node, or more simply, a virtual link (one at the current access node) can be used if no inactive downstream link flag of the ingress node). The current access node establishes a tunnel link or virtual downstream link pointing to the assigned access node. In response, the allocating access node generates a directed "recovery" update that is sent to the current access node using the existing DAG for the mobile node's IP address (which remains pointed to the current access node). This update deletes all host-specific routing protocol data table records and next-hop forwarding table records generated by the mobile node's previous mobility to restore the precomputed aggregated DAG as a valid route for the mobile node's IP address Options. The update travels through the path previously generated by the routing update caused by the mobile node's past mobility. Consequently, the collection of negative altitude values produced by mobility-specific updates is removed, and the aggregate DAG with "all zero" reference levels (assuming there are no glitches in the network that cause new altitudes to be generated and reversed) is reactivated. The tunnel link or virtual link may be maintained until a restoration update is received at the current access node, at which point the tunnel is released or the virtual link is removed.

Periodically, or upon detection of a triggering event, the mobile node or an access node acting as a mobile node can use the TORA update mechanism to reinitialize the DAG for an IP address with an "all zero" reference level, thereby eliminating the DAG Any routing table records related to mobility. An "all zero" reference level propagated in this way takes precedence over all other altitude values (both positive and negative) and can be propagated throughout the AS (an AS-wide DAG reoptimization). This provides a mechanism for soft state routing maintenance that overrides the mobility-related update mechanism.

A detailed example of inter-BS handover at the radio link layer and routing update within the fixed infrastructure of the AS is described below with reference to FIGS. 2 to 11 . Another example is explained with reference to FIGS. 12 to 16 . A detailed example of reverting routing to the allocating access node after the end of the mobile host access session will be described with reference to FIGS. 17 to 25. FIG. A detailed example of routing updates within the fixed infrastructure of an AS is described with reference to FIGS. 28 to 31 . Another such embodiment is described with reference to FIGS. 32 and 33 . The host specific routing data deletion procedure will be described with reference to FIGS. 34 and 35. FIG. The host-specific routing injection procedure will be described with reference to FIGS. 36 to 38.

In each TORA height quintuple shown in Figs. 2 to 25 and Figs. 28 to 38, the symbol i is used to denote the node ID for simplicity. However, it should be understood that this value is different for each node in order to uniquely identify the node within the AS. It should also be noted that, for simplicity, only a portion of AS is shown.

In all the following examples, the AS consists of multiple fixed core routers (CR1, CR2...), multiple fixed intermediate routers (IR1, IR2,...), and multiple fixed edge routers (ER1, ER2,...), according to their The relative proximity of topological "edges" to the fixed infrastructure of the AS is classified. The core router is suitable for handling a larger amount of traffic than the intermediate routers, and the intermediate router is suitable for handling a larger amount of traffic than the edge routers. For example, core routers can handle national traffic, intermediate routers can handle regional traffic, and edge routers can handle sub-regional traffic.

A packet-switched router is combined or associated with a wireless base station to form an embodiment of an entity referred to herein as an access node (BS1, BS2, ...), although it will be understood that the term "access node" is not intended to be limited to A routing node including the functionality of a radio base station. An "access node" may be provided at a node topologically remote from a radio base station, see for example the arrangement described below with reference to Figure 40 .

In the case of all the examples described below, the hop-by-hop routing directionality at the interface is determined by the links (including wireless links) between nodes along the network and between the access node and the mobile node. ) marked by an arrow. The distributed routing scheme is in the form of a TORA DAG pointing to a single receiving mobile host MH2. Before mobile host MH2 starts an access session and is dynamically assigned an IP address, there exists within the AS a precomputed and aggregated DAG for that IP address, which is taken as an AS-wide update from the IP address assigned Injected by the access node (node BS2). In Figures 2 to 25 and Figures 28 to 38, at least those nodes involved in routing updates or packet forwarding are labeled with their TORA height quintuple (τ _i , oid _i , _ri , δ _i , i). As mentioned earlier, this TORA height is also stored in the routing protocol data table of each neighbor node, having been advertised from the node to which it is applied.

When the mobile node MH2 registers with the allocating access node BS2, the allocating access node caches the identity of the mobile host at the wireless link layer according to the allocated IP address, thus forming a mobile host in a routing table maintained in node BS2. Station-specific records.

Figure 2 shows an example communication session (eg a TCP/IP connection) taking place between mobile node MH2 and another host, in this case a mobile host MH1. In the following example, the mobility of the corresponding mobile host MH1 does not take place, although such mobility is possible using the same functionality to be described with respect to the mobility of node MH2. A similar communication session can also be conducted with a corresponding stationary host. It should be noted that there is a separate DAG in the AS pointing to node MH1, thus data packets originating from node MH2 are routed to node MH1. Since this DAG pointing to node MHI does not change, and there is a routing to node MH1 from each access node that node MH2 is affiliated with, no further explanation of the routing to node MH1 will be provided.

As shown in Figure 2, data packets originating from node MH1 and destined for node MH2 are initially routed through its aggregate DAG (eg through fixed nodes BS1, ER1, IR1 and ER2) to distribution access node BS2.

Referring now to FIG. 3, the radio link layer inter-BS handover decision may be made by the node MH2 itself or by the node BS2. In the case of a handover initiated by a mobile node, the decision may be made on the basis of a comparison of the radio link quality between the signals received from nodes BS2 and BS3. As the mobile node MH2 moves, the signal received from the access node BS3 may improve, while the signal received from the access node BS2 deteriorates, and at a threshold decision event, the mobile host initiates a handoff between nodes BS2 and BS3 by Toggle to respond. If the handover decision is made at node BS2, the decision may be made based on other factors such as traffic load. In this case, the access node BS2 sends a handover instruction to the node MH2.

Regardless of whether the inter-BS handover is initiated by the mobile node MH2 or the assigning access node BS2, the mobile node MH2 selects a new access node BS3 and sends a tunnel initiation (TIN) packet to the assigning access node BS2. The TIN packet includes the IP address of the new access node BS3, which is read by the mobile node from a beacon channel broadcast by the access node BS3. Mobile node MH2 also calculates a new altitude by reducing its altitude's τ time value to a negative value, -1 (indicating a first mobility-related routing update away from the assigned access node BS2), and It is included in the TIN packet.

Referring now to FIG. 4, when the allocating access node BS2 receives the TIN packet from the mobile node MH2, the allocating access node BS2 establishes a short-term IP-in-IP tunnel link to the new access node BS3. Allocating access node BS2 to enter the tunnel interface to BS3 into its routing table, the TORA height of the new access node BS3 is set equal to (-1, 0, 0, 1, i) to ensure that the tunnel interface is marked For the downstream link for data packet forwarding during the remainder of the handover procedure.

When a short-term tunnel link has been established from the allocating access node BS2 to the new access node BS3, the allocating access node BS2 forwards the TIN packets received from the mobile node MH2 to the new access node BS3 through the tunnel interface.

In this embodiment, the nature of the radio link system used is such that mobile node MH2 can (as in a CDMA cellular radio system allowing soft handoff) pass to each access node BS2 during handover Communicate with two simultaneous wireless links to BS3. Therefore, next, the mobile node MH2 establishes a second radio link with the new access node BS3, and creates a routing table entry in node BS3 to indicate a downstream link to the mobile node MH2.

The new access node BS3 generates a Unicast Directed Update (UUPD) packet with the address of the assigned access node BS2 as destination. This address is a prefix of its IP address block, so the UUPD packet follows the aggregate DAG existing in the AS for allocating the access node BS2. Therefore, the UUPD packet is to travel along the unicast path between the new access node BS3 and the assigned access node BS2. The processing of the UUPD grouping makes the records in the routing protocol data tables and at least some next-hop point forwarding tables of all nodes along the update path and all nodes adjacent to the nodes along the path get updated (the nodes along the path Their new heights are advertised to every immediately adjacent node, the propagation of which is limited to one hop).

Referring now to FIG. 6, after the mobile host MH2 has established a new radio link with the new access node BS3, the old radio link to the assigned access node BS2 is canceled. The data packets directed to the mobile node MH2 are forwarded to the new access node BS3 through the short-term tunnel after arriving at the allocated access node BS2, and forwarded to the mobile node MH2 through the new wireless link.

Even though the old radio link is now lost, no routing update has been triggered at the allocating access node BS2 (which would have happened according to the TORA protocol), since the allocating access node BS2 and the new access node BS3 along There is a remaining downstream link between the established tunnels. Thus, the routing to the allocating access node BS2 remains in place until a routing update initiated from the new access node BS3 reaches the allocating access node BS2. As shown in Figure 6, the UUPD packet is forwarded to node IR2 from the first node ER3 that received the UUPD packet, and the first node ER3 also updates its altitude with a negative τ time value (-1) associated with the mobility update . Node IR2 in turn updates its altitude with the negative τ time value associated with the mobility-related update.

Each node along the routing update unicast route also increments the delta value in its TORA height quintuple by 1 for each hop of the routing update UUPD packet, so that the delta value represents The number of hops to the mobile node to replace the δ value recorded in the previous routing table (representing the number of hops to the mobile node by assigning the access node BS2). Thus, each link along the unicast-directed update route is in turn directed to the new access node BS3.

Referring now to Figure 7, the UUPD packet is then forwarded to the next node along the unicast update route, node ER2. The node ER2 is a router which marks the routing path from the sending node MH1 to the distribution access node BS2 and the routing path to be passed by the packet sent from the node MH1 to the new access node BS3 (currently established routing path) intersection between. As shown in Figure 8, once the routing protocol data table record in node ER2 is updated upon receiving the UUPD packet, the cross node ER2 has two downstream links, one pointing to the allocation access node BS2 and one downstream link The link points to the new access node BS3. However, since the downstream link towards the new access node BS3 includes a (highest) negative τ time value representing a (recent) mobility-related update, it is better to choose the downstream link towards the new access node BS3 The link is used as the next hop to forward the link. Data packets destined for mobile host MH2 arriving at node ER2 are forwarded to node IR2 along the routing path to the new access node BS3. After the diversion of the routing path at the cross router ER2, no more data packets are forwarded to BS2 and no more data packets are forwarded through the tunnel interface between node BS2 and node BS3. However, the tunnel interface is still in place at the distribution access node BS2 at this time in order to ensure that no routing updates are generated (due to the loss of all its downstream links) from the distribution access node BS2 until the UUPD packet arrives at the distribution access node BS2. When the UUPD packet arrives at the distribution access node BS2, the tunnel state record in the routing table of BS2 is deleted, thereby releasing the tunnel interface of MH2.

Referring now to FIG. 9, note that since the assigning access node BS2 forms the end of the unicast update path, the height of the assigning access node BS2 is not redefined upon receipt of the UUPD packet (however, since the height of the assigning access node BS2 is defined in For a negative τ time value, the link direction between nodes BS2 and ER2 is reversed, thus allowing other mobile hosts receiving service through BS2 to send packets to MH2).

Finally, upon receipt of the UUPD message, the allocating access node BS2 can send an update completion acknowledgment (UUPD-Ack) to the new access node BS3. The UUPD-Ack packet follows the established unicast update routing path in the DAG to the new access node BS3. When sending the UUPD-Ack packet, the old access node BS2 relinquishes the tentative control of routing for the IP address it originally assigned to the mobile node MH2. Upon receipt of the UUPD-Ack packet, the new access node BS3 starts tentatively controlling the routing for the mobile node's IP address.

The routing update associated with the inter-BS handover of the mobile station is now done at the radio link layer, involving only a limited number of nodes along the unicast update path (in the example shown in Figure 9, only 5 node) height redefinition. In addition, updates to routing protocol data table records are restricted to only the node receiving the UUPD message and each of its immediate neighbors (which receive notification of the new altitude and store the new altitude in their routing tables) is needed. In the example shown in FIG. 9, routing protocol data table updates are also performed within each of nodes IR1, CR1, CR2, and CR3.

Figures 10 and 11 show the state of the host-specific DAG (including aggregated DAG components at nodes that have not yet undergone a mobility-related update) within the AS before and after a subsequent mobility-related update. In this case, the mobile node MH2 is handed over from the access node BS3 to another access node BS4 from which the mobile node was previously handed over. The procedure used here is the same as that described in the description regarding the mobility-related update caused by the first handover of the mobile node from access node BS2 to access node BS3, except that the UUPD packet puts the access node BS3 as its destination. Also, the new altitude resulting from the unicast update sent from the new access node BS4 includes yet another increment in the negative τ time value (thus, the τ time value is increased to -2) so that the second The mobility-related update height resulting from the second occurrence, the mobility-related update height for the first occurrence of the mobility (with τtime value -1), and the mobility-related update height from the height specified in the aggregation DAG (with a τtime value of 0). As shown in Figure 1, the nodes involved in the new update initially have a height that includes a τtime value of 0, indicating the same height as defined in the aggregated DAG.

Another embodiment of mobility-related routing updates is described below with reference to Figures 12 to 16, where a mobile node (as in the GSM cellular radio system) is able to communicate over only a single radio link at any given time. In this case, the steps explained with reference to FIGS. 2 to 4 in the previous example are the same. As shown in Figure 12, a UUPD packet sent from the new access node BS3 is generated in response to a TIN packet received along the tunnel interface.

Referring now to FIG. 13, the mobile node MH2 first loses its radio link with the assigned access node BS2, and after a short period of time (to allow resynchronization with the new access node BS3 at the radio link layer etc.), it can A new radio link is established with the new access node BS3. During the period when the mobile node MH2 has no radio link, data packets arriving at the allocating access node BS2 are forwarded from the allocating access node BS2 via the tunnel interface and queued at the new access node BS3 until a new radio link is established. Then, either a new radio link is established, or the UUPD packet arrives at the allocating access node BS2. If a new radio link is established first, the new access node BS3 immediately takes tentative control over routing for the mobile node's IP address. Otherwise, the new access node BS3 will wait until it receives a UUPD-Ack message from the allocating access node BS2. The remaining steps described in the previous example (tunnel release, subsequent mobility, etc.) also apply to this example.

Figures 17 to 25 show a procedure used in the case where an IP address is dynamically assigned to a mobile node. When a mobile node ends an access session, a routing update can be performed to restore the DAG of the mobile node's IP address to the state of the DAG before the IP address was initially assigned to the mobile node, that is, fully restore the aggregation DAG. The routing update procedure involves sending routing updates to only a limited number of nodes in the AS (along the path of the previous unicast mobility-related update), and only to a limited number of nodes (recovered directed routing update messages The routing protocol data tables of the nodes passed through and each adjacent node) need to be updated.

Referring to FIG. 17, when the mobile node MH2 ends the access session, the current access node BS4 sends a recovery request (RR) packet to the assigning access node BS2 for the IP address. The RR packet is destined for the assigned IP address of the access node BS2, which is a prefix of the mobile node's IP address.

Therefore, the RR packet is to be routed along the aggregate DAG routing path for the mobile node's IP address, which remains directed to the allocating access node during the entire access session.

In response to receipt of the RR packet, the allocating access node BS2 marks a downstream link to the mobile host MH2 in its routing table. The downstream link is a virtual link because the mobile host is not currently in wireless communication with any access node and is actually located in the service area of a different access node (access node BS4). Any packets arriving at BS4 after the mobile node MH2 ends its access session can be forwarded along the tunnel to the allocating access node BS2, and can be stored for retrieval when the mobile node MH2 starts a new access session in the future. Forward to mobile node MH2.

As shown in Figure 18, upon receipt of the RR packet, the allocating access node BS2 also resets the height of the (now virtual) mobile node MH2 to a reference level of "all zeros" and sends a single A Point Delivery Directed Recovery Update (UDRU) packet is sent to the current access node BS4. The UDRU packets are forwarded along a unicast route that includes only nodes whose height was previously redefined due to mobility-related updates. In the example of FIG. 18, these nodes are nodes ER2, IR2, ER3, IR3, CR4, IR4, ER4 and BS4.

When a UDRU packet is received at each node along the unicast path, the TORA height of each node is reset to the value present in the aggregate DAG, ie: the "all zero" reference level. The delta value for height is redefined to represent the number of hops to the (now virtual) mobile node via the assigned access node, replacing the previously recorded value representing the number of hops to the mobile node via the current access node. This process is represented in each of Figures 18 to 22.

In addition to updating the altitude along the unicast update route, the updated altitude is advertised to each immediately adjacent node. Any node with a negative τ time value in its own altitude, when it receives an advertisement indicating to reset the negative τ time value to 0, as in the case of access node BS3 (as shown in Figure 20), also resets its own altitude to an "all-zero" reference level, defines its delta value to represent the number of hops to reach the (now virtual) mobile station via the assigned access node, and generates an advertisement of its own new altitude, and send this advertisement to all its own neighbors. Any neighbor that receives an advertised new altitude and does not reset its own altitude does not propagate the advertisement further.

As shown in Figure 23, upon receipt of the UDRU packet at the current access node BS4, the current access node deletes the state associated with the mobile node MH2 in its routing table and follows the path just created by the unicast update. The routing path sends a UDRU-Ack message to the allocating access node BS2, thereby relinquishing the tentative control of routing for the previously used IP address of the mobile node MH2.

As shown in Figure 24, the UDRU-Ack packet is finally propagated to the allocating access node BS2. On receipt, the allocating access node BS2 deletes all state associated with the mobile node MH2 and resumes control of the routing for the IP address. Then, as shown in FIG. 25, the IP address can again be dynamically assigned to a different mobile node MH3 which starts an access session in the service area of the access node BS2.

In Figures 28 to 38, see below, the heights of the nodes in the aggregate DAG pointing to the assigned access node BS2 of said IP address are shown. Where host-specific DAG heights are defined for the mobile node's IP address (due to mobility-related updates having occurred), these negative heights are represented as being lower than the aggregate DAG height.

Figures 28 to 31 show a procedure, when a mobile node has been handed over between a plurality of access nodes due to being assigned an IP address at the assigning access node BS2, by making the new or current access Routing updates between the nodes in the infrastructure linking the ingress node BS5 and the assigned access node BS2 route routing updates redirecting links to improve routing within the infrastructure. In the example shown, mobile node MH2 is handing over between old access node BS4 and new access node BS5. The handoff may be performed according to any of the procedures described with reference to FIGS. 2 to 11 or FIGS. 12 to 16 . The unicast update packet UUPD sent from the new access node BS5 into the infrastructure ER5 may be the same as described with reference to the procedures of FIGS. 2 to 11 or FIGS. the same as mentioned.

The sending of the UUPD packet initiates a routing update procedure in the infrastructure, which constitutes another instance of the mobility of the mobile node MH2. Therefore, the updated altitude on mobility uses the τ value -3 used in the newly defined TORA altitude to indicate the third occurrence of mobility. As shown in Fig. 28, both the mobile node MH2 and the new access node BS5 update their heights with a value of -3 before generating a UUPD packet and sending the packet to node ER5. The UUPD is addressed to the old access node BS4, and the UUPD passes along the unicast routing update path between the new access node BS5 and the old access node BS4. This can be achieved by forwarding the UUPD packets along the DAG defined in the AS for the old access node BS4 itself.

As shown in Figure 29, the UUPD packet is forwarded from node ER5 (which updates its own altitude upon receiving the UUPD packet) to the next node, node IR4, along the unicast path. In this embodiment, the nodes of the AS are arranged to process unicast directed routing update messages, such as UUPD packets, by deciding whether the UUPD packets indicate that mobility occurs above a predetermined threshold. In this example, the threshold is set at two cases of mobility. Therefore, the mobility of the third case represented by UUPD packets is above a predetermined threshold. If a node detects a situation where a UUPD packet indicates mobility above a threshold, the node determines whether the next node along the unicast update path towards the old access node BS4 is compatible with the aggregated DAG towards the allocating access node BS2 The next node in is coincident.

For node IR4, the next node along the unicast update path is ER4, and the next node in the aggregation DAG is node CR3. Therefore, the nodes do not coincide in this case. Node IR4 still forwards the UUPD packet to the next node ER4 along the unicast path between the new access node BS5 and the old access node BS4. However, in response to the detected non-coincidence, node IR4 also generates a new message (referred to herein as an Optimized Unicast Update (OUUPD) message) and addresses the message to the allocating access node BS2 such that the message Proceed along the aggregated DAG for the mobile node IP address pointing to the allocation of access node BS2. This situation is shown in FIG. 30 . UUPD packets are forwarded and processed as described above. The OUUPD packet is forwarded along the aggregated DAG to the allocating access node BS2 and processed by appending a host-specific negative TORA height at each node traversed in order to redirect the link to the new access node BS5, where the height has The value of τ is equal to the value of τ injected by the original UUPD packet.

In effect, the OUUPD packet defines a routing path between the allocating access node BS2 and the new access node BS5, which follows (in the reverse direction) what was previously done when the aggregation DAG was started as the allocating access node BS2 and the new access node BS5. The routing path calculated based on the optimal route between ingress nodes BS5. This is in contrast to the routing path defined by the respective mobility-related updates caused by subsequent UUPD packet updates, so that routing packets from all nodes in the AS will not be routed by multiple separate mobility-related updates. The defined routing paths are well optimized. Take the data packet arriving at the AS via the core router node CR1 as an example. Referring to Figure 28, if only links close to the path located between the new access node BS5 and the old access node BS4 are redirected in terms of the mobility of the mobile node MH2, packets arriving via node CR1 will pass through node IR2, Each of ER3, IR3, CR4, IR4 and ER5 is routed to the new access node BS5. The improved routing path would be a routing path that traverses only nodes CR2, CR3, IR4 and ER5 respectively. As shown in Figure 31, the effect of the OUUPD message is to make the links within the AS, especially (but not exclusively) those between nodes higher in the network hierarchy such as node CR2 and node CR3 Link redirection. The effect of the multiple individual UUPD packet updates is to redirect links close to the shortest path between adjacent access nodes, such as BS4 and BS5, which are often at the topological "edge" of the AS. Therefore, UUPD packet updates may be referred to as "shallow" routing updates. On the other hand, the effect of the OUUPD packet update is to redirect the link along an optimized path connecting topologically distant access nodes, such as the current access node BS5 and the assigned access node BS2. If the ASs are structured in a hierarchical manner, the optimized paths between these topologically distant access nodes will likely include nodes higher in the infrastructure hierarchy, such as CR2 and CR3. Accordingly, OUUPD packet updates may be referred to as "deep" routing updates.

As shown in Figure 31, the final recipient of the OUUPD packet is the allocating access node BS2. Once the allocating access node BS2 receives the OUUPD packet, the allocating access node BS2 can end the procedure according to a variant of the routing protocol and thus allow OUUPD messages to be unacknowledged (by default) for signaling efficiency. Although in most cases the OUUPD message will reach its destination safely, the OUUPD message can be lost during its transmission to the allocating access node BS2 for some reason, eg due to a link failure or network overload. However, minor losses of OUUPD packets will not affect service in the AS since the routes provided by shallow routing updates still exist.

In the alternative routing protocol according to the invention, OUUPD messages are acknowledged as default by sending OUUPD-ack messages along the newly defined routing path between the assigned access node BS2 and the new access node BS5. This allows the new access node BS5 to monitor the receipt of the OUUPD-ack packet, and if no acknowledgment is received within the timeout period, allows the new access node BS5 to resend the OUUPD packet, thereby making deep routing updates reliable. In another alternative, it may be determined at the allocating access node BS2 whether to acknowledge the OUUPD packet according to the characteristics of the OUUPD packet. This characteristic may be update heights represented by OUUPD packets, which indicate that mobility of higher instances is acknowledged, while updates of lower-instances are not. Another or alternative characteristic may be the type of OUUPD packets sent by the new access node BS5. For example, a first type of OUUPD packet may be a packet containing a flag indicating that an acknowledgment is required, while another type may be a packet containing a flag indicating that no such acknowledgment is required. Other such characteristics include the amount of time elapsed since the packet was sent, the distance or number of hops at which the sending occurred, the sequence number of the packet (e.g., every nth OUUPD packet is acknowledged at the assigned access node), the selection from near-routing area or location area to reach. Validation decisions may also be based on customer profiles.

In one embodiment of the invention, host-specific routing records are maintained in the AS's routing nodes as soft-state records, and the soft-state timer is triggered after a predetermined period of time so that routes injected due to shallow routing updates The selection record is deleted. In conjunction with this, a periodic routing update (which generates an OUUPD message at the current access node which is preferably unacknowledged as described above) can be used such that in a single soft state timeout period Perform multiple OUUPD message update procedures. This ensures that deep-injected routing will gradually replace shallow routing.

Although in the process described above, deep routing updates are triggered together with shallow routing updates, these two types of updates can be additionally or alternately triggered separately. The triggering of the deep routing update is performed according to the number of mobility instances (ie, the number of handovers between access nodes) in the above process. A deep routing update may additionally or alternatively be triggered by: one or more timers in the mobile node or the current access node (deep routing updates are triggered at regular intervals); sub-area) in which the mobile node is receiving service; a separate routing control node (which can determine the optimal time to trigger a deep routing update based on knowledge of traffic volume or routing performance) and/or Quality of service monitoring program in the mobile node. Quality of service or other user profile requirements may be used to determine the frequency of deep routing updates. Triggering in conjunction with a shallow routing update according to any of the above alternative triggers may be implemented using a dedicated tag appended to the UUPD message by the mobile node or the current access node.

Figures 32 and 33 show variations of the routing update procedure described with reference to Figures 28 to 31. In this variant, when an OUUPD packet update is performed, another routing update message is generated to delete the previously sub-optimal route due to the mobility of the mobile node. In order to ensure that the routing path to the new access node BS5 is preserved, the UUPD packet generated at the new access node BS5 is a packet indicating that an acknowledgment from the allocating access node BS2 is required when the OUUPD packet is received (or, the routing protocol can set to cause all OUUPD packets to be acknowledged). In this embodiment, upon receipt of the OUUPD-ack packet, a Unicast Undirected Partial Erase (UUPE) message is generated by the new access node BS5. UUPE packets are transmitted to any neighbor nodes that have a host-specific altitude that has been generated due to mobility-related updates (any "negative" altitude nodes). A UUPE message is sent to each such node in order to delete "intermediate" negative altitudes, ie altitudes other than the last mobility-related update altitude. In the example shown in Figures 32 and 33, the height resulting from the last UUPD and OUUPD packet includes a value of -3 for τ. Thus, a UUPE packet or UUPE packets generated and forwarded within an AS have the effect of deleting one or more host-specific altitudes with a non-zero τ value greater than a specified value (in this case -3 ), that is: -2 or -1 (the maximum deletion height is -2).

Therefore, UUPEs are routed along the aggregate DAG to any neighbors with negative heights. Therefore, node IR4 not only forwards the UUPE packet to the next node in the aggregate DAG, but also sends the UUPE packet to nodes CR4 and ER4. Each node that has an intermediate negative altitude and receives a UUPE packet deletes the host-specific altitude from its routing data table to then use the aggregate DAG altitude to compute the directionality of its link, and forwards the UUPE message to each neighbor it detects has a negative height. On receipt, nodes BS3 and BS4 delete the host-specific altitude value from their routing data tables and stop any further transmission of UUPE packets.

UUPE packets are forwarded in an undirected manner such that no final destination for the UUPE packet is defined when the packet is originally generated. The deletion is only partial so that other host-specific heights can be preserved, or at least the mobile node MH2 retains the IP address and can then inject the host-specific height. The effect of UUPE updates is to remove the state provided by previous routing updates, thereby reducing the amount of host-specific data that needs to be kept in the AS. The UUPE update generally also improves the routing path in the AS to the new access node BS5. After a UUPE update, routing will initially be performed along the aggregated DAG of said IP addresses from e.g. an intermediate access node, e.g. Or the new access node BS5 is a node BS3 that is farther away but was involved in a previous mobility-related update. Since the routing paths defined by OUUPD packet updates are generally optimized routing paths, the routing provided by removing shallow routing paths that were and are now unnecessary is generally improved. The further the mobile node MH2 travels from its assigned access node BS2, the generally greater the improvement.

Figures 34 and 35 show another update procedure which is initiated due to inactivity of the mobile node MH2. For example, the wireless link to mobile node MH2 may be lost due to the mobile node entering an area not covered by the radio access network. Alternatively, the mobile node MH2 may be powered off for a given period. And alternatively, the mobile node MH2 may remain powered on, but may not receive any packet data for a considerable period of time. In the current access node BS4 and/or in the mobile node MH2 there is an inactivity timer which triggers a deletion procedure whereby the host-specific routing data table entry is deleted from the AS. UUPE messages are used for this purpose, and the specified maximum deletion height is set to the previous lowest value of τ. Initially, once the inactivity timer has detected that a predetermined period has elapsed, a trigger is started, which causes the original current access node BS4 to delete its host-specific routing data table record, thereby redefining the relative height of the mobile node MH2 as The height of the access node BS4 in the aggregate DAG for the mobile node IP address ("all zeros" setting). The current access node BS4 also sends one or more UUPE messages. As shown in Figure 35, the UUPE packet update passes through all nodes that previously had a host-specific height stored in the routing table (in the example shown, BS4, ER4, IR4, CR4, IR3, ER3, BS3, IR2, and ER2) proceed, and these host-specific heights are deleted. Note that in contrast to the aforementioned UDRU packet update procedure, the IP address of the mobile node MH2 is not released in this procedure for reassignment by the allocating access node BS2. Instead, the mobile node MH2 retains the IP address originally assigned by the allocating access node BS2, so that it can reuse the same IP address anytime the mobile node MH2 is subsequently active. Alternatively, a second, more extended inactivity timer at the allocating access node BS2 may initiate the reassignment of the IP address after another predetermined period followed by deletion of host-specific routing at that address behind.

Figures 36 to 38 show a procedure whereby the temporarily inactive mobile node MH2 can initiate a routing update which causes routing in the AS to be redirected towards the access node BS5, where the mobile node MH2 will pass through the access node BS5 BS5 receiving service. In the examples shown in Figures 36 to 38, the mobile node MH2 temporarily lost its radio link due to a power outage or due to lack of coverage after previously receiving service in the AS via the access node BS3. As shown in Figure 36, a mobility-related update by means of the UUPE routing update is previously performed in the AS and is removed due to inactivity after the loss of the radio link with the previous access node BS3.

When mobile node MH2 experiences loss of its radio link due to power outage or lack of coverage, it stores the IP address of its last access node, the time of the loss and at least a previous An indicator of the number of instances so that the next update initiated when it connects over a new radio link can easily be denoted as the most recent mobility-related update. Therefore, as shown in Figure 37, mobile node MH2, when forming a new radio link to the radio access network and to access node BS5, reduces its τ time value to -2 and its new TORA height value It is sent to the new access node BS5 together with the IP address of its last access node and the time of loss. On reception, the new access node BS5 initiates a UUPD update. The destination of this UUPD packet depends on the time elapsed since the last link loss, which is calculated by the new access node BS5.

If this elapsed time is significantly greater than the preset time after which the inactivity timer triggers partial deletion, so that it can be assumed that no master-specific altitude remains, then the destination is the allocation of access node BS2. The UUPD message follows the path defined by the aggregate DAG of the mobile node's IP address to the allocating access node BS2. As shown in Figure 38, each subsequent node receiving the UUPD message sets the new host-specific altitude in its routing protocol data based on the data received in the UUPD message. Therefore, after the UUPD update, all nodes in the AS have a routing path defined by the host-specific DAG to the new access node and BS5.

If the elapsed time is not significantly greater (allowing any deviation between timers), the chosen destination for the UUPD packet is the last access node BS3. If there is still host-specific routing for the last access node BS3 when the UUPD packet is received, the routing in the entire AS is correctly directed to the new access node BS5. On the other hand, if the host-specific routing has been deleted, the last access node BS3 sends a negative acknowledgment (N-ack) to the new access node BS5, which sends another UUPD packet to Access node BS2 is assigned to react to this negative acknowledgment in order to establish correct routing throughout the AS.

Figure 39 shows five states (active; hot standby; warm standby; cold standby; disconnected) that a mobile node can be in, and the arrows indicate the state transitions that the MN can perform. The MN is in an active state when sending and receiving data with the AR in an active manner. Its radio link level interface is sending data traffic (radio link up); it has an assigned IP address; and host-specific routing exists in the domain for routing data packets to the MN. When the MN no longer transmits and receives data traffic with the AR in an active mode (that is, when the IP activity timer has expired), it is in a hot standby state when the route hold timer has not expired. The MN has an IP address and host-specific routing within the network infrastructure, however, the MN does not have a radio interface link to the AR. Movement between access nodes generates handoff processing and injection of host-specific routes in active and hot standby states.

When the network node no longer maintains the MN's host-specific routing (ie: when the soft-state routing retention timer has expired or when the host-specific routing has been deleted), the MN is in the warm standby state. The MN still has an IP address, ie reallocation of the IP address is prevented in this state, but movement of the mobile node between access nodes does not generate a handover process. Instead, the MN generates location updates periodically (ie, upon expiration of the location update timer) or based on the distance traveled from the cell whose location was last updated. When incoming data needs to be delivered to the MN, the MN must be paged. The MN is in a cold standby state when it does not have an IP address because the previously assigned address was returned due to inactivity (i.e. the IP address hold timer expired at the last access node and/or mobile node) for Redistributed to the distribution access router (using the method above). When data is incoming, the MN must be paged using a static identity such as the International Mobile Subscriber Identity (IMSI). Also, the MN must register with a new access node and must be assigned an IP address. Finally, a MN is in the disconnected state when it has lost power, or is unreachable (eg due to prolonged loss of network coverage). The MN cannot be paged in this state.

Figure 40 shows a program executed in a node undergoing a host-specific route deletion process, such as a program generated by a UUPE update, which prevents unwanted loops in the AS during the process. During the deletion process, a particular node (node i in this case) receives a UUPE message from the original downstream neighbor, node j. Figure 39 shows with dashed arrow 100 the initial downstream direction of the link. Before receiving the UUPE message, node i also has one or more upstream neighbors, denoted by node k. The initial direction of the link is indicated by arrow 102 . When node i deletes its host-specific height when it receives a UUPE message, its routing table record indicates node k as a downstream node because node k's host-specific height is due to a previous mobility-related update And defined. From the point of view of node i, the direction of the link is indicated by arrow 104 . On the other hand, until node k receives the UUPE message and updates its own routing table, the direction of the link remains downstream towards i, indicated by arrow 102, according to node k's perspective. Thus, a data packet received at node k will be sent to node i, which will resend the packet back to node k until node k redefines its own height. Therefore, the program creates unwanted loops in the network. To solve this problem, upon receiving a UUPE message, a node (node i in this case) redefines its own TORA height on all interfaces of the node that originally knew the height of the deleted host (in this case, i A temporary block is imposed on the host-specific forwarding of the host on the interface of node k). When blocking, this can be achieved by node i by caching all packets received on those interfaces of the host by node i, and/or discarding (or causing subsequent delays, e.g., by shortening the time-to-live (TTL) value) discard) these packets. As soon as node i receives an acknowledgment from the relevant node (node k in this case) that a UUPE message forwarded from node i has been received, the blocked state of node i is removed. The interface blocking procedure is performed in each node where the host-specific height is removed, thereby redirecting the link.

Figure 41 represents an embodiment of the invention applicable to the proposed third generation mobile communication system (known as UMTS) (ETSI (European Telecommunications Standards Institute) standard. Regarding the current version of the standard, an IP packet data network is provided (referred to as GPRS (General Packet Radio Service) network) is used to route data packets between Serving GPRS Service Node (SGSN) and Gateway GPRS Service Node (GGSN), which divides the network into Layer structure is arranged to approximate radio access base station, gateway GPRS service node (GGSN) realizes access to other data networks such as the Internet.A tunneling agreement, namely: GPRS tunneling protocol (GTP) is used in SGSN and Send data packet between GGSN.On the other hand, the present invention allows to use local routing protocol to carry out routing to data packet between SGSN and GGSN.The above-mentioned improved TORA routing protocol can be used to make SGSN 202 and GGSN 204 The connection is used within IP network 200 and/or radio access network (RAN) 206 for providing a radio interface for mobile node 208 .

FIG. 41 shows an embodiment using the modified TORA routing protocol in IP network 200 only. A separate part 210 of the radio access network is associated with each SGSN 202. Thus, the first part 210A is associated with the first SGSN 202A, the second part 210B is associated with the second SGSN 202B, and the third part 210C is associated with the third SGSN 202C. A mobile station 208 receiving service at any point in the radio access network 206 may receive service from an external packet data network through any GGSN, 204A or 204B.

Figure 41 shows another example of the mobility of the mobile station 208 from the first part 210A to the second part 210B, and from the second part 210B to the third part 210C. Each of these mobility instances requires handover between SGSNs. The aforementioned handover procedure can be used in the local routing protocol network 200, and all the aforementioned routing update procedures can be set, and the SGSN 202 serves as the access node. The packet routing nodes within IP network 200 are not shown in FIG. 41 , but it should be understood that multiple packet routing nodes are arranged between SGSN 202 and GGSN 204 in a hierarchical manner.

Thick arrow 212 schematically represents a shallow routing update that occurs in IP network 200 in response to the mobility of mobile node 208 from radio network part 210A to radio network part 210B according to the aforementioned procedure. Thick arrow 214 schematically represents a similar shallow routing update occurring in IP network 200 due to another example of mobility of mobile node 208 from radio access network part 210B to radio access network part 210C. Thick arrow 216 schematically represents a deep routing update taking place in IP network 200 after a subsequent instance of mobility into radio access network part 210C using a procedure similar to that described above. Thin arrow 218 schematically represents the routing path within IP network 200 after deep routing update 216 .

In summary, the routing protocol improvements provided by the present invention that can be used individually or in any combination include:

1. Store different routing protocol data generated as a result of mobility ("negative" altitude reference levels in the case of the TORA protocol) to forward packets to the nearest designated downstream neighbor.

2. Incorporate unicast directed mobility updates to adjust routing at handover by changing routing protocol data stored in only a limited set of nodes in the AS.

3. Incorporate recovery updates to at least partially eliminate the impact of handover-based mobility ("negative" altitude reference levels in the case of TORA).

It should be understood that the above-described embodiments are not intended to be limiting, and those skilled in the art may conceive improvements and modifications.

The above embodiments describe an improved routing protocol based on the TORA routing protocol. However, other known routing protocols such as OSPF, RIP, etc. can be improved using aspects of the present invention.

In addition, although the infrastructure of the autonomous system is fixed in the above-described embodiments, it should be understood that one or more routers in the infrastructure may be mobile routers, such as in the field of satellite communications and other systems (where one or more routers in the infrastructure or multiple routers exhibiting long-term mobility).

Claims (11)

1. in packet switching network, control the method for routing of dividing into groups for one kind, this packet switching network comprises by the foundation structure of the Packet Switch Node of transmitted in packets link interconnect and a plurality of access node, in described foundation structure can for a given network address a described access node of Route Selection path point, described Route Selection path is write down by the Route Selection that keeps in the Packet Switch Node of its layout and is defined, and described method comprises:

First described network address is distributed to by first mobile node of first access node by the communication link service, and directed described first access node at least one first Route Selection path in the described foundation structure is to be used for described first network address;

When described first mobile node receives service from one second access node, change the Route Selection in the described foundation structure, make at least one secondary route in the described foundation structure select directed described second access node in path to be used for described first network address, described secondary route selection path is write down by one or more host-specific Route Selection at least in part and is defined;

During the non-movable period subsequently, from described foundation structure, remove described one or more host-specific Route Selection record, make described mobile node not have the current Route Selection path in the described network; And

During the described non-movable period, for described mobile node provides two independent states:

A) described mobile node keeps the state of described first network address; With

B) described first network address can be reallocated the state to different mobile nodes.

2. method according to claim 1, wherein said step of removing the host-specific Route Selection are to be carried out by a Route Selection deletion message of propagating from described second access node.

3. method according to claim 2, wherein said step of removing the host-specific Route Selection is started by second access node.

4. method according to claim 2, wherein said step of removing the host-specific Route Selection is started by mobile node.

5. according to any one described method in the claim 1 to 4, wherein state a) in, when mobile node became activity once more, mobile node was set to rebulid the host-specific Route Selection by start a route refusal process at a new access node.

6. according to any one described method in the claim 1 to 5, wherein at state b) in, when mobile node became activity once more, mobile node was set to ask the distribution of a new network address.

7. according to any one described method in the claim 1 to 6, wherein by the timer state of a control a) and b) enter.

8. method according to claim 7, wherein state a) is set at state b) before.

9. according to the described method of above-mentioned any one claim, wherein said communication link is a Radio Link.

10. according to the described method of above-mentioned any one claim, the wherein said network address is Internet Protocol (IP) address.

11. be used to carry out routing arrangement according to the step of the method for any aforesaid right requirement.

Images