DIRECTED ACYCLIC GRAPH DISCOVERY AND NETWORK PREFIX INFORMATION DISTRIBUTION RELATIVE TO A CLUSTERHEAD IN AN AD HOC MOBILE NETWORK

• US 20110080853A1
• Filed: 11/19/2010
• Published: 04/07/2011
• Est. Priority Date: 06/28/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Ribiere, Vincent Jean, Wetterwald, Patrick
• Granted Patent: US 8,441,958 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

Each mobile router in an ad hoc mobile network is configured for concurrently attaching to multiple parents advertising respective parent depths relative to a clusterhead of the ad hoc mobile network. The mobile router selects an advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths, enabling the mobile routers to form a directed acyclic graph relative to the clusterhead. Each mobile router sends to each of its parents a neighbor advertisement message specifying at least one reachable prefix, a corresponding cost for reaching the reachable prefix, and a corresponding sequence identifier that enables the parents to validate the neighbor advertisement message relative to stored router entries. Hence, mobile routers automatically can form a directed acylic graph relative to the clusterhead, and can distribute routing information with minimal overhead.

Claims

1. A method in a mobile router configured for establishing communications within an ad hoc network, the method including:

establishing concurrent attachments by the mobile router to respective attachment routers based on having received respective advertisement messages specifying respective parent metrics relative to a single clusterhead of the ad hoc network;

selecting by the mobile router an advertised metric relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent metrics, the advertised metric having a maximum cost relative to the parent metrics; and

advertising reachability by the mobile router to reach the single clusterhead based on the mobile router outputting a router advertisement message specifying the advertised metric relative to the single clusterhead, the router advertisement message enabling the mobile router to position itself within a directed acyclic graph directed toward the single clusterhead based on the mobile router providing the directed acyclic graph with concurrent paths toward the single clusterhead using the respective concurrent attachments.

2. The method of claim 1, wherein the establishing includes adding, to a routing table, a first routing table entry for each attachment router and that specifies a corresponding identifier for reaching the corresponding attachment router, and that specifies the corresponding parent metric.

3. The method of claim 2, wherein each identifier is a corresponding selected attachment address used by the mobile router for attachment to the corresponding attachment router, the attachment address within a range of a corresponding address prefix having been advertised within the corresponding advertisement message.

4. The method of claim 3, wherein each identifier is mapped by the mobile router to a corresponding data link to the corresponding attachment router.

5. The method of claim 2, further comprising:

sending, to each of the attachment routers and in response to having established each corresponding attachment, a first neighbor advertisement message specifying a first reachable prefix advertised by the mobile router in the router advertisement message, a corresponding metric for reaching the first reachable prefix, and a corresponding sequence identifier that enables validation of the corresponding first reachable prefix relative to any stored router entries in the attachment routers.

6. The method of claim 5, further comprising:

receiving a second neighbor advertisement message from an attached mobile router having attached to the mobile router, the second neighbor advertisement message specifying at least one second reachable prefix that is reachable via the attached mobile router, a corresponding advertised metric for reaching the at least one second reachable prefix via the attached mobile router, and a corresponding advertised sequence identifier; and

selectively adding the at least one second reachable prefix, the corresponding advertised metric, and the corresponding advertised sequence identifier to the routing table based on at least one of;

(1) determining the advertised sequence identifier identifying the second neighbor advertisement message does not specify an older advertisement of the at least one second reachable prefix relative to any corresponding stored sequence identifiers stored in the routing table for the at least one second reachable prefix, and (2) determining the advertised metric is less than any corresponding stored metric stored in the routing table for the at least one second reachable prefix;

the sending including;

(1) incrementing a minimum of said stored metrics corresponding to the sequence identifier identifying a most recent advertisement of the at least one second reachable prefix, and

(2) adding the at least one second reachable prefix, the increment of the minimum of the corresponding stored metrics, and the corresponding sequence identifier to the first neighbor advertisement message.

9. The method of claim 1, wherein the establishing includes selecting each one of the attachment routers based on the corresponding advertised metric determined to be within a prescribed acceptable range.

10. The method of claim 1, further comprising sending, to each of the attachment routers, a neighbor advertisement message specifying at least one reachable prefix that is reachable by the mobile router, a corresponding metric for reaching at least one reachable prefix by the mobile router, and a corresponding sequence identifier that enables validation of the corresponding at least one reachable prefix relative to any stored router entries in the attachment routers.

51. The method of claim 1, wherein the concurrent paths are unequal cost paths.

7-8. -8. (canceled)

11. An apparatus configured for establishing communications within an ad hoc network, the comprising:

an attachment resource configured for establishing concurrent attachments to respective attachment routers based on the apparatus having received respective advertisement messages specifying respective parent metrics relative to a single clusterhead of the ad hoc network; and

a router advertisement resource configured for advertising the apparatus as a mobile router providing reachability to reach the single clusterhead based on outputting a router advertisement message specifying an advertised metric relative to the single clusterhead, the router advertisement resource configured for selecting the advertised metric relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent metrics, the advertised metric having a maximum cost relative to the parent metrics, the router advertisement message enabling the apparatus to position itself within a directed acyclic graph directed toward the single clusterhead based on the apparatus providing the directed acyclic graph with concurrent paths toward the single clusterhead using the respective concurrent attachments.

12. The apparatus of claim 11, further comprising a routing table configured for storing routing table entries, the attachment resource configured for adding, to the routing table, a first routing table entry for each attachment router and that specifies a corresponding identifier for reaching the corresponding attachment router, and that specifies the corresponding parent metric.

13. The apparatus of claim 12, wherein each identifier is a corresponding selected attachment address used by the apparatus for attachment to the corresponding attachment router, the attachment address within a range of a corresponding address prefix having been advertised within the corresponding advertisement message.

14. The apparatus of claim 13, wherein the apparatus is configured for mapping each identifier to a corresponding data link to the corresponding attachment router.

15. The apparatus of claim 12, further comprising:

a neighbor advertisement resource configured for sending, to each of the attachment routers and in response to the attachment resource having established each corresponding attachment, a first neighbor advertisement message specifying a first reachable prefix advertised by the apparatus in the router advertisement message, a corresponding metric for reaching the first reachable prefix, and a corresponding sequence identifier that enables validation of the corresponding first reachable prefix relative to any stored router entries in the attachment routers.

16. The apparatus of claim 15, further comprising:

a neighbor discovery resource configured for parsing a second neighbor advertisement message having been received from an attached mobile router having attached to the apparatus, the second neighbor advertisement message specifying at least one second reachable prefix that is reachable via the attached mobile router, a corresponding advertised metric for reaching the at least one second reachable prefix via the attached mobile router, and a corresponding advertised sequence identifier;

the neighbor discovery resource selectively adding the at least one second reachable prefix, the corresponding advertised metric, and the corresponding advertised sequence identifier to the routing table based on at least one of;

(1) determining the advertised sequence identifier identifying the second neighbor advertisement message does not specify an older advertisement of the at least one second reachable prefix relative to any corresponding stored sequence identifiers stored in the routing table for the at least one second reachable prefix, and (2) determining the advertised metric is less than any corresponding stored metric stored in the routing table for the at least one second reachable prefix;

the neighbor advertisement resource configured for sending the first neighbor advertisement message based on;

(1) incrementing a minimum of said stored metrics corresponding to the sequence identifier identifying a most recent advertisement of the at least one second reachable prefix, and

(2) adding the at least one second reachable prefix, the increment of the minimum of the corresponding stored metrics, and the corresponding sequence identifier to the first neighbor advertisement message.

19. The apparatus of claim 11, wherein the establishing includes selecting each one of the attachment routers based on the corresponding advertised metric determined to be within a prescribed acceptable range.

20. The apparatus of claim 11, further comprising a neighbor advertisement resource configured for sending, to each of the attachment routers, a neighbor advertisement message specifying at least one reachable prefix that is reachable by the apparatus, a corresponding metric for reaching at least one reachable prefix by the apparatus, and a corresponding sequence identifier that enables validation of the corresponding at least one reachable prefix relative to any stored router entries in the attachment routers.

52. The apparatus of claim 11, wherein the concurrent paths are unequal cost paths.

17-18. -18. (canceled)

21-40. -40. (canceled)

41. A computer readable medium having stored thereon sequences of instructions for a mobile router to establish communications within an ad hoc network, the sequences of instructions including instructions for:

establishing concurrent attachments by the mobile router to respective attachment routers based on having received respective advertisement messages specifying respective parent metrics relative to a single clusterhead of the ad hoc network;

selecting by the mobile router an advertised metric relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent metrics, the advertised metric having a maximum cost relative to the parent metrics, and

advertising reachability by the mobile router to reach the single clusterhead based on the mobile router outputting a router advertisement message specifying the advertised metric relative to the single clusterhead, enabling the mobile router to position itself within a directed acyclic graph directed toward the single clusterhead based on the mobile router providing the directed acyclic graph with concurrent paths toward the single clusterhead using the respective concurrent attachments.

53. The medium of claim 41, wherein the concurrent paths are unequal cost paths.

42-50. -50. (canceled)