Compression of a routing header in a packet by a mobile router in an ad hoc network

• US 20070153764A1
• Filed: 07/28/2006
• Published: 07/05/2007
• Est. Priority Date: 01/04/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Retana, Alvaro Enrique, Ribiere, Vincent Jean, White, Russell Ivan, Berry, Thomas, Thubert, Pascal
• Granted Patent: US 7,778,235 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

Each mobile router in a mobile ad hoc network is configured for identifying routes to nearby nodes that are within a prescribed distance, based on storage of explicit paths specified within routing headers of packets transmitted from a host node to a destination node. Each mobile router also can selectively compress the routing header, based on the storage of the explicit path, resulting in a loose source route type routing header in the packet output from the mobile router. In addition, a routing header of a received packet can be expanded based on the mobile router inserting the explicit path, enabling mobile hosts in the explicit path to forward the packet according to strict source routing. The storage and compression of explicit paths also can be applied to packets specifying reverse routing headers, minimizing the size of the reverse routing headers.

Claims

1. A method in a mobile ad hoc router that is within a mobile ad hoc network, the method including:

receiving, by the mobile ad hoc router, routing information that identifies a mobile ad hoc node within the mobile ad hoc network and that is reachable within a prescribed distance of the mobile ad hoc router;

storing by the mobile ad hoc router a routing table entry in response to reception of the routing information and that specifies an explicit path for reaching the mobile ad hoc node within the prescribed distance;

modifying, by the mobile ad hoc router, a routing header of a received packet into a modified routing header, the modifying including one of;

(1) removing an identified path for reaching the mobile ad hoc node from the routing header based on the routing header identifying that the received packet is from the identified path, and

(2) inserting the explicit path into the routing header, based on the routing header identifying the received packet is to be sent via the mobile ad hoc node; and

outputting the received packet, having the modified routing header, toward a destination address specified by the received packet.

2. The method of claim 1, wherein the receiving includes obtaining the routing information from the corresponding routing header of a reply to a discovery message, the discovery message having been sent via the explicit path between an originator of the discovery message and a target of the discovery message, the reply having been sent by the target.

3. The method of claim 2, further comprising:

receiving a second packet that specifies within the corresponding routing header a second explicit path for reaching the mobile ad hoc node within the prescribed distance; and

selectively replacing the explicit path in the routing table entry with the second explicit path based on whether the second explicit path has a corresponding shorter distance to the mobile ad hoc node than the explicit path in the routing table entry.

4. The method of claim 3, wherein:

the routing header of the reply specifies a corresponding hop count identifying a corresponding number of hops between the corresponding target and the corresponding originator;

the storing includes specifying within the routing table entry the corresponding hop count identifying the corresponding number of hops between the target and the originator; and

the selectively replacing including determining whether to replace the explicit path based on whether the second packet specifies a second corresponding hop count that is less than the corresponding hop count stored in the routing table entry.

5. The method of claim 4, wherein the determining includes determining whether the second hop count is less than the corresponding hop count stored in the routing table entry, the second hop count and the corresponding hop count each specifying a corresponding number of hops between the target and the originator.

6. The method of claim 1, wherein:

the receiving includes obtaining the routing information from the routing header of the received packet, the routing header specifying the routing information as a reverse routing header that includes the explicit path;

the storing including storing the explicit path based on the explicit path exceeding a prescribed minimum distance; and

the removing including removing the explicit path, as the identified path, from the reverse routing header.

7. The method of claim 1, wherein the removing includes replacing the identified path in the routing header with an index value that identifies the routing table entry.

8. The method of claim 7, wherein the inserting includes:

detecting the index value within the routing header, the index value identifying the received packet is to be sent via the mobile ad hoc node; and

retrieving the explicit path, for insertion into the routing header, in response to detecting the corresponding index value in the routing header.

9. The method of claim 1, wherein the receiving includes obtaining the routing information from the corresponding routing header of the received packet, the modifying including removing the explicit path, as said identified path, from the received packet.

10. A mobile ad hoc router configured for routing packets within a mobile ad hoc network, the mobile ad hoc router comprising:

a network interface configured for receiving routing information that identifies a mobile ad hoc node within the mobile ad hoc network and that is reachable within a prescribed distance of the mobile ad hoc router; and

a routing resource configured for storing a routing table entry in response to reception of the routing information and that specifies an explicit path for reaching the mobile ad hoc node within the prescribed distance;

the routing resource configured for modifying a routing header of a received packet into a modified routing header, based on one of;

(1) removing an identified path for reaching the mobile ad hoc node from the routing header based on the routing header identifying that the received packet is from the identified path, and

(2) inserting the explicit path into the routing header, based on the routing header identifying the received packet is to be sent via the mobile ad hoc node;

the network interface configured for outputting the received packet, having the modified routing header, toward a destination address specified by the received packet.

11. The mobile ad hoc router of claim 10, wherein the routing resource is configured for obtaining the routing information from the corresponding routing header of a reply to a discovery message, the discovery message having been sent via the explicit path between an originator of the discovery message and a target of the discovery message, the reply having been sent by the target.

12. The mobile ad hoc router of claim 11, wherein:

the network interface is configured for receiving a second packet that specifies within the corresponding routing header a second explicit path for reaching the mobile ad hoc node within the prescribed distance;

the routing resource configured for selectively replacing the explicit path in the routing table entry with the second explicit path based on whether the second explicit path has a corresponding shorter distance to the mobile ad hoc node than the explicit path in the routing table entry.

13. The mobile ad hoc router of claim 12, wherein:

the routing header of the reply specifies a corresponding hop count identifying a corresponding number of hops between the corresponding target and the corresponding originator;

the routing resource configured for specifying within the routing table entry the corresponding hop count identifying the corresponding number of hops between the target and the originator; and

the routing resource configured for determining whether to replace the explicit path based on whether the second packet specifies a second corresponding hop count that is less than the corresponding hop count stored in the routing table entry.

14. The mobile ad hoc router of claim 13, wherein the routing resource is configured for comparing the second corresponding hop count with the corresponding hop count stored in the routing table entry based on the second hop count and the corresponding hop count each specifying a corresponding number of hops between the target and the originator.

15. The mobile ad hoc router of claim 10, wherein:

the routing resource is configured for obtaining the routing information from the routing header of the received packet, the routing header specifying the routing information as a reverse routing header that includes the explicit path;

the routing resource configured for storing the explicit path based on the explicit path exceeding a prescribed minimum distance; and

the routing resource configured for removing the explicit path, as the identified path, from the reverse routing header.

16. The mobile ad hoc router of claim 10, wherein the routing resource is configured for replacing the identified path in the routing header with an index value that identifies the routing table entry.

17. The mobile ad hoc router of claim 16, wherein the routing resource is configured for inserting the explicit path into the routing header based on:

detecting the index value within the routing header, the index value identifying the received packet is to be sent via the mobile ad hoc node; and

retrieving the explicit path, for insertion into the routing header, in response to detecting the corresponding index value in the routing header.

18. The mobile ad hoc router of claim 10, wherein the routing resource is configured for obtaining the routing information from the corresponding routing header of the received packet, and modifying the routing header by removing the explicit path, as said identified path, from the received packet.

19. A mobile router configured for routing packets within a mobile ad hoc network, the mobile router comprising:

means for receiving routing information that identifies a mobile ad hoc node within the mobile ad hoc network and that is reachable within a prescribed distance of the mobile ad hoc router;

means for storing a routing table entry based on reception of the routing information and that specifies an explicit path for reaching the mobile ad hoc node within the prescribed distance; and

means for modifying a routing header of a received packet into a modified routing header, by one of;

(1) removing an identified path for reaching the mobile ad hoc node from the routing header based on the routing header identifying that the received packet is from the identified path, and

(2) inserting the explicit path into the routing header, based on the routing header identifying the received packet is to be sent via the mobile ad hoc node;

the means for receiving further configured for outputting the received packet, having the modified routing header, toward a destination address specified by the received packet.