Directed acyclic graph discovery and network prefix information distribution relative to a clusterhead in an ad hoc mobile network

• US 7,860,025 B2
• Filed: 06/28/2005
• Issued: 12/28/2010
• 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: Ribiere, Vincent Jean, Thubert, Pascal, Wetterwald, Patrick
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Rivas; Salvador E
• Application Number:
  US11/167,240
• Publication Number:
  US 20060291404A1
• Time in Patent Office: 2,009 Days
• Field of Search: 370/389, 370/392, 370254-256, 370/338, 370400-401, 709/238, 709/242
• US Class Current: 370/254
• 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 depths relative to a single clusterhead of the ad hoc network;

selecting by the mobile router an advertised depth relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent depths, 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 depth 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.

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 depth.

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 cost 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 cost 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 cost, 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 cost is less than any corresponding stored cost stored in the routing table for the at least one second reachable prefix;

the sending including;

(1) incrementing a minimum of said stored costs 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 costs, and the corresponding sequence identifier to the first neighbor advertisement message.

7. The method of claim 6, further comprising receiving a third neighbor advertisement message from a second attached mobile router having attached to the mobile router, the third neighbor advertisement message specifying the at least one second reachable prefix that is reachable via the second attached mobile router, a corresponding advertised cost for reaching the at least one second reachable prefix via the second attached mobile router, and a corresponding advertised sequence identifier;

selectively updating the routing table to specify that the at least one second reachable prefix is reachable via the second attached mobile router at the corresponding advertised cost relative to the corresponding advertised sequence identifier;

outputting an updated first neighbor advertisement message specifying that the at least one second reachable prefix is reachable via the mobile router at the increment of the minimum of the corresponding stored costs, relative to the corresponding advertised sequence identifier.

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

9. 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 cost 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.

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

10. A mobile router configured for establishing communications within an ad hoc network, the mobile router comprising:

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

a router advertisement resource configured for advertising reachability to reach the single clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the single clusterhead, the router advertisement resource configured for selecting the advertised depth relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent depths, 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.

11. The mobile router of claim 10, 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 depth.

12. The mobile router of claim 11, 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.

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

14. The mobile router of claim 11, 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 mobile router in the router advertisement message, a corresponding cost 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.

15. The mobile router of claim 14, 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 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 cost 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 cost, 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 cost is less than any corresponding stored cost 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 costs 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 costs, and the corresponding sequence identifier to the first neighbor advertisement message.

16. The mobile router of claim 15, wherein:

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

the neighbor discovery resource configured for selectively updating the routing table to specify that the at least one second reachable prefix is reachable via the second attached mobile router at the corresponding advertised cost relative to the corresponding advertised sequence identifier;

the neighbor advertisement resource configured for outputting an updated first neighbor advertisement message specifying that the at least one second reachable prefix is reachable via the mobile router at the increment of the minimum of the corresponding stored costs, relative to the corresponding advertised sequence identifier.

17. The mobile router of claim 10, wherein the establishing includes selecting each one of the attachment routers based on the corresponding advertised depth determined to be within a prescribed acceptable range.

18. The mobile router of claim 10, 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 mobile router, a corresponding cost 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.

47. The mobile router of claim 10, wherein the concurrent paths are unequal cost paths.

19. An ad hoc network comprising:

a plurality of mobile routers having organized into a directed acyclic graph directed toward a single clusterhead, one of the mobile routers serving as the single clusterhead, the directed acyclic graph having attached mobile routers that have attached to attachment routers, each mobile router including;

an attachment resource configured for selectively establishing concurrent attachments, as an attached mobile router, to selected attachment routers from the attachment routers based on the mobile router having received respective advertisement messages from the selected attachment routers, the advertisement messages specifying respective parent depths relative to the single clusterhead of the ad hoc network, and

a router advertisement resource configured for advertising reachability to reach the single clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the single clusterhead, the router advertisement resource configured for selecting the advertised depth relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent depths, enabling the mobile router to position itself within the 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.

20. The network of claim 19, wherein each mobile router further comprises 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 selected attachment router and that specifies a corresponding identifier for reaching the corresponding selected attachment router, and that specifies the corresponding parent depth.

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

22. The network of claim 21, wherein each mobile router is configured for mapping each identifier to a corresponding data link to the corresponding selected attachment router.

23. The network of claim 20, wherein each mobile router further comprises:

a neighbor advertisement resource configured for sending, to each of the selected 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 mobile router in the router advertisement message, a corresponding cost 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 selected attachment routers.

24. The network of claim 23, wherein each mobile router further comprises:

a neighbor discovery resource configured for parsing a second neighbor advertisement message having been received 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 cost 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 cost, 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 cost is less than any corresponding stored cost 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 costs 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 costs, and the corresponding sequence identifier to the first neighbor advertisement message.

25. The network of claim 24, wherein:

the neighbor discovery resource of each mobile router is configured for parsing a third neighbor advertisement message received from a second attached mobile router having attached to said each mobile router, the third neighbor advertisement message specifying the at least one second reachable prefix that is reachable via the second attached mobile router, a corresponding advertised cost for reaching the at least one second reachable prefix via the second attached mobile router, and a corresponding advertised sequence identifier;

the neighbor discovery resource of said each mobile router configured for selectively updating the routing table to specify that the at least one second reachable prefix is reachable via the second attached mobile router at the corresponding advertised cost relative to the corresponding advertised sequence identifier;

the neighbor advertisement resource of said each mobile router is configured for outputting an updated first neighbor advertisement message specifying that the at least one second reachable prefix is reachable via the mobile router at the increment of the minimum of the corresponding stored costs, relative to the corresponding advertised sequence identifier.

26. The network of claim 19, wherein the attachment resource is configured for selecting each one of the selected attachment routers based on the corresponding advertised depth determined to be within a prescribed acceptable range.

27. The network of claim 19, wherein each mobile router further comprising a neighbor advertisement resource configured for sending, to each of the selected attachment routers, a neighbor advertisement message specifying at least one reachable prefix that is reachable by the mobile router, a corresponding cost 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.

48. The network of claim 19, wherein the concurrent paths are unequal cost paths.

28. A mobile router configured for establishing communications within an ad hoc network, the mobile router comprising:

means for establishing concurrent attachments to respective attachment routers based on having received respective advertisement messages specifying respective parent depths relative to a single clusterhead of the ad hoc network; and

means for advertising reachability to reach the single clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the single clusterhead, the means for advertising configured for selecting the advertised depth relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent depths, 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.

29. The mobile router of claim 28, further comprising means for storing routing table entries, the means for establishing configured for adding, to the means for storing, a first entry for each attachment router and that specifies a corresponding identifier for reaching the corresponding attachment router, and that specifies the corresponding parent depth.

30. The mobile router of claim 29, 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.

31. The mobile router of claim 30, wherein the mobile router is configured for mapping each identifier to a corresponding data link to the corresponding attachment router.

32. The mobile router of claim 29, further comprising:

means 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 mobile router in the router advertisement message, a corresponding cost 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.

33. The mobile router of claim 32, further comprising:

discovery means for parsing a second neighbor advertisement message having been received 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 cost for reaching the at least one second reachable prefix via the attached mobile router, and a corresponding advertised sequence identifier;

the discovery means configured for selectively adding the at least one second reachable prefix, the corresponding advertised cost, and the corresponding advertised sequence identifier to the means for storing 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 cost is less than any corresponding stored cost stored in the routing table for the at least one second reachable prefix;

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

(1) incrementing a minimum of said stored costs 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 costs, and the corresponding sequence identifier to the first neighbor advertisement message.

34. The mobile router of claim 32, wherein:

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

the discovery means configured for selectively updating the means for storing to specify that the at least one second reachable prefix is reachable via the second attached mobile router at the corresponding advertised cost relative to the corresponding advertised sequence identifier;

the means for sending configured for outputting an updated first neighbor advertisement message specifying that the at least one second reachable prefix is reachable via the mobile router at the increment of the minimum of the corresponding stored costs, relative to the corresponding advertised sequence identifier.

35. The mobile router of claim 28, wherein the means for establishing is configured for selecting each one of the attachment routers based on the corresponding advertised depth determined to be within a prescribed acceptable range.

36. The mobile router of claim 28, further comprising a means for 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 cost 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.

49. The mobile router of claim 28, wherein the concurrent paths are unequal cost paths.

37. A non-transitory 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 depths relative to a single clusterhead of the ad hoc network;

selecting by the mobile router an advertised depth relative to the single clusterhead based on adding a prescribed increment to a maximum one of the parent depths, 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 depth 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.

38. The medium of claim 37, 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 depth.

39. The medium of claim 38, 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.

40. The medium of claim 39, wherein each identifier is mapped by the mobile router to a corresponding data link to the corresponding attachment router.

41. The medium of claim 38, further comprising instructions for:

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 cost 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.

42. The medium of claim 41, further comprising instructions for:

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 cost 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 cost, 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 cost is less than any corresponding stored cost stored in the routing table for the at least one second reachable prefix;

the sending including;

(1) incrementing a minimum of said stored costs 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 costs, and the corresponding sequence identifier to the first neighbor advertisement message.

43. The medium of claim 42, further comprising instructions for:

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

selectively updating the routing table to specify that the at least one second reachable prefix is reachable via the second attached mobile router at the corresponding advertised cost relative to the corresponding advertised sequence identifier;

outputting an updated first neighbor advertisement message specifying that the at least one second reachable prefix is reachable via the mobile router at the increment of the minimum of the corresponding stored costs, relative to the corresponding advertised sequence identifier.

44. The medium of claim 37, wherein the establishing includes selecting each one of the attachment routers based on the corresponding advertised depth determined to be within a prescribed acceptable range.

45. The medium of claim 37, further comprising instructions for 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 cost 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.

50. The medium of claim 37, wherein the concurrent paths are unequal cost paths.