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

• US 20060291404A1
• Filed: 06/28/2005
• Published: 12/28/2006
• 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 7,860,025 B2
• Time in Patent Office: Days
• 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 to respective attachment routers based on having received respective advertisement messages specifying respective parent depths relative to a clusterhead of the ad hoc network;

selecting an advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths, and

advertising reachability to the clusterhead based on outputting a router advertisement message specifying the advertised depth relative to the clusterhead.

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 5, wherein the sending further includes adding, to the first neighbor advertisement message, reachable prefixes that are reachable via attached mobile routers having attached to the mobile router, the first neighbor advertisement message specifying for each reachable prefix a corresponding cost for reaching the corresponding reachable prefix via the mobile router, and a corresponding sequence identifier having been advertised by at least one of the attached mobile routers.

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

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 cost for reaching the 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.

11. 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 clusterhead of the ad hoc network; and

a router advertisement resource configured for advertising reachability to the clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the clusterhead, the router advertisement resource configured for selecting the advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths.

12. The mobile router 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 depth.

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

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

15. The mobile router 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 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.

16. The mobile router 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 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.

17. The mobile router of claim 16, 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.

18. The mobile router of claim 15, wherein the neighbor advertisement resource is configured for adding, to the first neighbor advertisement message, reachable prefixes that are reachable via attached mobile routers having attached to the mobile router, the first neighbor advertisement message specifying for each reachable prefix a corresponding cost for reaching the corresponding reachable prefix via the mobile router, and a corresponding sequence identifier having been advertised by at least one of the attached mobile routers.

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

20. The mobile router 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 mobile router, a corresponding cost for reaching the 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.

21. An ad hoc network comprising:

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

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

a router advertisement resource configured for advertising reachability to the clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the clusterhead, the router advertisement resource configured for selecting the advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths.

22. The network of claim 21, 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.

23. The network of claim 22, 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.

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

25. The network of claim 22, 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.

26. The network of claim 25, 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.

27. The network of claim 26, 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.

28. The network of claim 25, wherein the neighbor advertisement resource of each mobile router is configured for adding, to the first neighbor advertisement message, reachable prefixes that are reachable via attached mobile routers having attached to the mobile router, the first neighbor advertisement message specifying for each reachable prefix a corresponding cost for reaching the corresponding reachable prefix via the mobile router, and a corresponding sequence identifier having been advertised by at least one of the attached mobile routers.

29. The network of claim 21, 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.

30. The network of claim 21, 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 the 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.

31. 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 clusterhead of the ad hoc network; and

means for advertising reachability to the clusterhead based on outputting a router advertisement message specifying an advertised depth relative to the clusterhead, the means for advertising configured for selecting the advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths.

32. The mobile router of claim 31, 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.

33. The mobile router of claim 32, 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.

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

35. The mobile router of claim 32, 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.

36. The mobile router of claim 35, 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.

37. The mobile router of claim 36, 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.

38. The mobile router of claim 35, wherein the means for sending is configured for adding, to the first neighbor advertisement message, reachable prefixes that are reachable via attached mobile routers having attached to the mobile router, the first neighbor advertisement message specifying for each reachable prefix a corresponding cost for reaching the corresponding reachable prefix via the mobile router, and a corresponding sequence identifier having been advertised by at least one of the attached mobile routers.

39. The mobile router of claim 31, 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.

40. The mobile router of claim 31, 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 the 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.

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 to respective attachment routers based on having received respective advertisement messages specifying respective parent depths relative to a clusterhead of the ad hoc network;

selecting an advertised depth relative to the clusterhead based on adding a prescribed increment to a maximum one of the parent depths, and

advertising reachability to the clusterhead based on outputting a router advertisement message specifying the advertised depth relative to the clusterhead.

42. The medium of claim 41, 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.

43. The medium of claim 42, 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.

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

45. The medium of claim 42, 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.

46. The medium of claim 45, 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.

47. The medium of claim 46, 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.

48. The medium of claim 45, wherein the sending further includes adding, to the first neighbor advertisement message, reachable prefixes that are reachable via attached mobile routers having attached to the mobile router, the first neighbor advertisement message specifying for each reachable prefix a corresponding cost for reaching the corresponding reachable prefix via the mobile router, and a corresponding sequence identifier having been advertised by at least one of the attached mobile routers.

49. The medium of claim 41, 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.

50. The medium of claim 41, 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 the 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.