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

• US 7,778,235 B2
• Filed: 07/28/2006
• Issued: 08/17/2010
• 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: Berry, Thomas, Retana, Alvaro Enrique, Ribiere, Vincent Jean, Thubert, Pascal, White, Russell Ivan
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Zhao; Wei
• Application Number:
  US11/494,585
• Publication Number:
  US 20070153764A1
• Time in Patent Office: 1,481 Days
• Field of Search: 370/351, 370/328, 370/338, 370/401, 370/466, 709/221
• 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 hop-by-hop path for reaching the mobile ad hoc node within the prescribed distance, the explicit hop-by-hop path including a network address of a next hop network node along the explicit hop-by-hop path for reaching the mobile ad hoc node;

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) compressing a size of the routing header to form the modified routing header based on removing the explicit hop-by-hop 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 explicit hop-by-hop path, or

(2) expanding the routing header to form the modified routing header based on inserting the explicit hop-by-hop path stored in the routing table entry 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 hop-by-hop 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 hop-by-hop path for reaching the mobile ad hoc node within the prescribed distance; and

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

4. The method of claim 3, wherein:

the routing header of the reply specifies a first 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 first 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 hop-by-hop path based on whether the second packet specifies a second corresponding hop count that is less than the first hop count stored in the routing table entry.

5. 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 hop-by-hop path;

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

the removing including removing the explicit hop-by-hop path from the reverse routing header.

6. The method of claim 1, wherein the removing includes replacing the explicit hop-by-hop path in the routing header with an index value that identifies the routing table entry.

7. The method of claim 6, 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 hop-by-hop path, for insertion into the routing header, in response to detecting the corresponding index value in the routing header.

8. 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 hop-by-hop path from the received packet.

18. The method of claim 1, wherein the explicit hop-by-hop path specifies the network address of the next hop network node, and a second network address of a second network node reachable via the next hop network node.

9. 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 hop-by-hop path for reaching the mobile ad hoc node within the prescribed distance, the explicit hop-by-hop path including a network address of a next hop network node along the explicit hop-by-hop path for reaching the mobile ad hoc node;

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

(1) compressing a size of the routing header to form the modified routing header based on removing the explicit hop-by-hop 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 explicit hop-by-hop path, or

(2) expanding the routing header to form the modified routing header based on inserting the explicit hop-by-hop path stored in the routing table entry 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.

10. The mobile ad hoc router of claim 9, 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 hop-by-hop path between an originator of the discovery message and a target of the discovery message, the reply having been sent by the target.

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

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

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

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

the routing header of the reply specifies a first 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 first 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 hop-by-hop path based on whether the second packet specifies a second corresponding hop count that is less than the first hop count stored in the routing table entry.

13. The mobile ad hoc router of claim 9, 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 hop-by-hop path;

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

the routing resource configured for removing the explicit hop-by-hop path from the reverse routing header.

14. The mobile ad hoc router of claim 9, wherein the routing resource is configured for replacing the explicit hop-by-hop path in the routing header with an index value that identifies the routing table entry.

15. The mobile ad hoc router of claim 14, wherein the routing resource is configured for inserting the explicit hop-by-hop 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 hop-by-hop path, for insertion into the routing header, in response to detecting the corresponding index value in the routing header.

16. The mobile ad hoc router of claim 9, 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 hop-by-hop path from the received packet.

19. The mobile ad hoc router of claim 9, wherein the explicit hop-by-hop path specifies the network address of the next hop network node, and a second network address of a second network node reachable via the next hop network node.

17. 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 hop-by-hop path for reaching the mobile ad hoc node within the prescribed distance, the explicit hop-by-hop path including a network address of a next hop network node along the explicit hop-by-hop path for reaching the mobile ad hoc node; and

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

(1) compressing a size of the routing header to form the modified routing header based on removing the explicit hop-by-hop 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 explicit hop-by-hop path, or

(2) expanding the routing header to form the modified routing header based on inserting the explicit hop-by-hop path stored in the routing table entry 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.

20. The mobile router of claim 17, wherein the explicit hop-by-hop path specifies the network address of the next hop network node, and a second network address of a second network node reachable via the next hop network node.