Arrangement for providing network prefix information from attached mobile routers to a clusterhead in a tree-based ad hoc mobile network

• US 20050265259A1
• Filed: 06/01/2004
• Published: 12/01/2005
• Est. Priority Date: 06/01/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Molteni, Marco, Wetterwald, Patrick, Moon, Billy G.
• Granted Patent: US 7,428,221 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/18 Service support devices; Network management devices

Abstract

Mobile routers establish a tree-based network topology in an ad hoc mobile network, the tree-based network topology having a single clusterhead and attached mobile routers. Each attached mobile router has a default egress interface configured for sending messages toward the clusterhead, and ingress interfaces configured for receiving messages from attached network nodes that are away from the clusterhead. A neighbor advertisement message received from an ingress interface away from a clusterhead is used by the attached mobile router to identify specified network prefixes that are reachable via the source of the neighbor advertisement message. The attached mobile router outputs on its default upstream interface a second neighbor advertisement message that specifies the network prefix used by the attached mobile router, and the specified network prefixes from the neighbor advertisement message received on the ingress interface. Hence, connectivity is established with minimal routing overhead.

Claims

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

attaching to an attachment router based on an advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

outputting to the attachment router a neighbor advertisement message specifying that a prescribed address prefix used by the mobile router is reachable via the default attachment address, based on the mobile router having attached to the attachment router, the prescribed address prefix distinct from the attachment prefix.

2. The method of claim 1, further comprising:

outputting a second advertisement message specifying the prescribed address prefix and a tree information option field specifying attributes of the mobile router relative to the tree topology;

receiving via an ingress interface a second neighbor advertisement message that specifies a second address prefix is reachable via a second attachment address within the address space of the prescribed address prefix; and

adding an entry to an ad hoc routing table, the entry specifying that the second address prefix is reachable using the second attachment address via the ingress interface.

3. The method of claim 2, further comprising outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message, the second address prefix distinct from the prescribed address prefix and the attachment prefix.

4. The method of claim 3, further comprising deleting the entry from the ad hoc routing table based on determined absence of activity from the second attachment address via the ingress interface for at least a prescribed time interval.

5. The method of claim 3, further comprising:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix; and

overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on receiving the fourth neighbor advertisement message following reception of the second neighbor advertisement message.

6. The method of claim 5, further comprising outputting on the first and second ingress interfaces a third advertisement message, specifying the prescribed address prefix and the tree information option field, in response to the overwriting of the entry.

7. The method of claim 3, further comprising outputting to the attachment router, in response to a new advertisement message from the attachment router specifying the attachment prefix, a new advertisement message specifying that the prescribed address prefix, and any address prefixes stored in the ad hoc routing table based on respective received neighbor advertisement messages, including the second address prefix, are reachable via the default attachment address.

8. The method of claim 3, further comprising:

receiving via the ingress interface a data packet having a specified destination address;

determining whether the ad hoc routing table includes any one of the specified destination address and an address table entry having a specified address prefix encompassing the specified destination address; and

outputting the data packet to the attachment router based on a determined absence of any one of the specified destination address and the address table entry in the ad hoc routing table.

9. The method of claim 3, wherein:

the outputting of the neighbor advertisement message includes specifying a first unique sequence number for the prescribed address prefix;

the receiving including detecting within the second neighbor advertisement message a second sequence number associated with the second address prefix; and

the outputting of the third neighbor advertisement message includes specifying a third unique sequence number, greater than the first unique sequence number, for the prescribed address prefix.

10. The method of claim 9, further comprising:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix, and a fourth sequence number associated with the second address prefix; and

selectively overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on the fourth sequence number for the second address prefix being greater than the second sequence number.

11. The method of claim 2, further comprising outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message.

12. The method of claim 1, wherein the attaching includes:

detecting within the advertisement router a tree information option field specifying a tree identifier and attributes of the attachment router relative to the tree topology, the attributes including one of a tree depth and a tree preference; and

selecting the attachment router, from a plurality of attachment routers having advertised respective tree identifiers and respective attributes, based on the attributes specified in the tree information option field.

13. The method of claim 1, wherein the neighbor advertisement message is a network node-based advertisement message, the outputting including inserting into the neighbor advertisement message a network-in-node option field that specifies the prescribed address prefix is reachable via the default attachment address.

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

outputting an advertisement message including a tree information option field that specifies a prescribed address prefix used by the mobile router, and a tree attribute field advertising one of a relative position and a relative preference of the mobile router within a tree topology of the ad hoc network;

receiving a first neighbor advertisement message specifying that at least a second address prefix is reachable via a first attachment address within an address space of the prescribed address prefix, the second address prefix distinct from the prescribed address prefix;

adding a first entry to an ad hoc routing table, the first entry specifying that the second address prefix is reachable via the first attachment address;

receiving a second neighbor advertisement message specifying that at least a third address prefix is reachable via a second attachment address within the address space of the prescribed address prefix, the third address prefix distinct from second address prefix and the prescribed address prefix;

adding a second entry to the ad hoc routing table, the second entry specifying that the third address prefix is reachable via the second attachment address;

receiving a data packet having a specified destination address; and

selectively routing the data packet to one of the first attachment address and the second attachment address based on determining the specified destination address is within the address space of a corresponding one of the second and third address prefixes.

15. The method of claim 14, wherein:

the receiving of the first neighbor advertisement message includes detecting that the first neighbor advertisement message specifies that the second address prefix, and a fourth address prefix are reachable via the first attachment address, the fourth address prefix distinct from the second and third address prefixes and the prescribed address prefix;

the method further comprising adding including adding a third entry to the ad hoc routing table that specifies that the fourth address prefix is reachable via the first attachment address.

16. The method of claim 15, further comprising

receiving a third neighbor advertisement message specifying that the third address prefix and the fourth address prefix are reachable via the second attachment address;

the method further comprising selectively overwriting the third entry to specify that the fourth address prefix is reachable via the second attachment address.

17. The method of claim 16, wherein the selectively overwriting includes overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on receiving the third neighbor advertisement message following reception of the first neighbor advertisement message.

18. The method of claim 16, wherein:

the first neighbor advertisement message specifies first and second unique sequence numbers for the second and fourth address prefixes, respectively;

the third neighbor advertisement specifies a third sequence number for the fourth address prefix;

the selectively overwriting includes overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on the third sequence number being greater than the second sequence number.

19. The method of claim 16, further comprising outputting another advertisement message including the tree information option field in response to overwriting the third entry.

20. The method of claim 14, further comprising deleting one of the first and second entries based on a detecting a corresponding prescribed interval of inactivity from the corresponding attachment address.

21. The method of claim 14, further comprising:

attaching to an attachment router based on a second advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

outputting to the attachment router a third neighbor advertisement message specifying that the prescribed address prefix, the second address prefix, and the third attachment prefix are reachable via the default attachment address, based on the mobile router having attached to the attachment router, each of the prescribed address prefix and the second and third address prefixes being distinct from the attachment prefix.

22. An ad hoc network comprising:

a first router having;

(1) an advertisement resource configured for outputting a first advertisement message including a tree information option field that specifies a prescribed address prefix used by the first router, and a tree attribute field that advertises the first router as a clusterhead of a tree topology in the ad hoc network,

(2) an ad hoc routing table configured for storing respective entries specifying that respective address prefixes are reachable via respective attachment addresses, and

(3) a neighbor discovery resource configured for adding the respective entries based on receiving respective neighbor advertisement message specifying that the respective address prefixes are reachable via the respective attachment addresses, each of the attachment addresses within an address space of the prescribed address prefix, each of the address prefixes distinct from each other and the prescribed address prefix; and

second and third mobile routers, each comprising;

(1) an attachment resource configured for attaching to the first router based on the first advertisement message and according to a protocol requiring establishment of a tree topology in the ad hoc network, and based on selecting the corresponding attachment address within the address space, and

(2) a neighbor advertisement resource configured for outputting the corresponding neighbor advertisement message specifying the corresponding address prefix used by the mobile router is reachable via the corresponding attachment address, based on the mobile router having attached to the first router.

23. The network of claim 22 wherein the first router further includes a routing resource configured for selectively routing a received data packet, having a specified destination address, to an identified one of the attachment addresses based on the destination address being determined to be within the address space of the corresponding address prefix specified in the corresponding entry of the ad hoc routing table.

24. The network of claim 22, further comprising a fourth mobile router having the attachment resource and the neighbor advertisement resource, wherein:

each of the second, third, and fourth mobile routers further includes;

(1) a corresponding advertisement resource for outputting a corresponding second advertisement message having a tree information option field that specifies the corresponding address prefix used by the corresponding mobile router;

(2) an ad hoc routing table; and

(3) the neighbor discovery resource;

the second mobile router, in response to detecting a neighbor advertisement message specifying an address prefix corresponding to the fourth mobile router is reachable via a first attachment address within the address space of the corresponding address prefix of the second mobile router;

(1) adds an entry to its routing table specifying that the address prefix corresponding to the fourth mobile router is reachable via the first attachment address, and

(2) outputs an updated neighbor advertisement message specifying the address prefix of the second mobile router and the address prefix of the fourth mobile router are reachable via the corresponding attachment address of the second mobile router.

25. The network of claim 24, wherein the advertisement resource of the first router, in response to its corresponding neighbor discovery resource detecting the updated neighbor advertisement message and updating the ad hoc routing table to specify that the address prefix of the second mobile router and the address prefix of the fourth mobile router are reachable via the corresponding attachment address of the second mobile router, outputs another first advertisement message.

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

attaching to an attachment router based on an advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

outputting to the attachment router a neighbor advertisement message specifying that a prescribed address prefix used by the mobile router is reachable via the default attachment address, based on the mobile router having attached to the attachment router, the prescribed address prefix distinct from the attachment prefix.

27. The medium of claim 26, further comprising instructions for:

outputting a second advertisement message specifying the prescribed address prefix and a tree information option field specifying attributes of the mobile router relative to the tree topology;

receiving via an ingress interface a second neighbor advertisement message that specifies a second address prefix is reachable via a second attachment address within the address space of the prescribed address prefix; and

adding an entry to an ad hoc routing table, the entry specifying that the second address prefix is reachable using the second attachment address via the ingress interface.

28. The medium of claim 27, further comprising instructions for outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message, the second address prefix distinct from the prescribed address prefix and the attachment prefix.

29. The medium of claim 28, further comprising instructions for deleting the entry from the ad hoc routing table based on determined absence of activity from the second attachment address via the ingress interface for at least a prescribed time interval.

30. The medium of claim 28, further comprising instructions for:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix; and

overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on receiving the fourth neighbor advertisement message following reception of the second neighbor advertisement message.

31. The medium of claim 30, further comprising instructions for outputting on the first and second ingress interfaces a third advertisement message, specifying the prescribed address prefix and the tree information option field, in response to the overwriting of the entry.

32. The medium of claim 28, further comprising instructions for outputting to the attachment router, in response to a new advertisement message from the attachment router specifying the attachment prefix, a new advertisement message specifying that the prescribed address prefix, and any address prefixes stored in the ad hoc routing table based on respective received neighbor advertisement messages, including the second address prefix, are reachable via the default attachment address.

33. The medium of claim 28, further comprising instructions for:

receiving via the ingress interface a data packet having a specified destination address;

determining whether the ad hoc routing table includes any one of the specified destination address and an address table entry having a specified address prefix encompassing the specified destination address; and

outputting the data packet to the attachment router based on a determined absence of any one of the specified destination address and the address table entry in the ad hoc routing table.

34. The medium of claim 28, wherein:

the outputting of the neighbor advertisement message includes specifying a first unique sequence number for the prescribed address prefix;

the receiving including detecting within the second neighbor advertisement message a second sequence number associated with the second address prefix; and

the outputting of the third neighbor advertisement message includes specifying a third unique sequence number, greater than the first unique sequence number, for the prescribed address prefix.

35. The medium of claim 34, further comprising instructions for:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix, and a fourth sequence number associated with the second address prefix; and

selectively overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on the fourth sequence number for the second address prefix being greater than the second sequence number.

36. The medium of claim 27, further comprising instructions for outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message.

37. The medium of claim 26, wherein the attaching includes:

detecting within the advertisement router a tree information option field specifying a tree identifier and attributes of the attachment router relative to the tree topology, the attributes including one of a tree depth and a tree preference; and

selecting the attachment router, from a plurality of attachment routers having advertised respective tree identifiers and respective attributes, based on the attributes specified in the tree information option field.

38. The medium of claim 26, wherein the neighbor advertisement message is a network node-based advertisement message, the outputting including inserting into the neighbor advertisement message a network-in-node option field that specifies the prescribed address prefix is reachable via the default attachment address.

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

outputting an advertisement message including a tree information option field that specifies a prescribed address prefix used by the mobile router, and a tree attribute field advertising one of a relative position and a relative preference of the mobile router within a tree topology of the ad hoc network;

receiving a first neighbor advertisement message specifying that at least a second address prefix is reachable via a first attachment address within an address space of the prescribed address prefix, the second address prefix distinct from the prescribed address prefix;

adding a first entry to an ad hoc routing table, the first entry specifying that the second address prefix is reachable via the first attachment address;

receiving a second neighbor advertisement message specifying that at least a third address prefix is reachable via a second attachment address within the address space of the prescribed address prefix, the third address prefix distinct from second address prefix and the prescribed address prefix;

adding a second entry to the ad hoc routing table, the second entry specifying that the third address prefix is reachable via the second attachment address;

receiving a data packet having a specified destination address; and

selectively routing the data packet to one of the first attachment address and the second attachment address based on determining the specified destination address is within the address space of a corresponding one of the second and third address prefixes.

40. The medium of claim 39, wherein:

the receiving of the first neighbor advertisement message includes detecting that the first neighbor advertisement message specifies that the second address prefix, and a fourth address prefix are reachable via the first attachment address, the fourth address prefix distinct from the second and third address prefixes and the prescribed address prefix;

the method further comprising adding including adding a third entry to the ad hoc routing table that specifies that the fourth address prefix is reachable via the first attachment address.

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

receiving a third neighbor advertisement message specifying that the third address prefix and the fourth address prefix are reachable via the second attachment address;

the method further comprising selectively overwriting the third entry to specify that the fourth address prefix is reachable via the second attachment address.

42. The medium of claim 41, wherein the selectively overwriting includes overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on receiving the third neighbor advertisement message following reception of the first neighbor advertisement message.

43. The medium of claim 41, wherein:

the first neighbor advertisement message specifies first and second unique sequence numbers for the second and fourth address prefixes, respectively;

the third neighbor advertisement specifies a third sequence number for the fourth address prefix;

the selectively overwriting includes overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on the third sequence number being greater than the second sequence number.

44. The medium of claim 41, further comprising instructions for outputting another advertisement message including the tree information option field in response to overwriting the third entry.

45. The medium of claim 39, further comprising instructions for deleting one of the first and second entries based on a detecting a corresponding prescribed interval of inactivity from the corresponding attachment address.

46. The medium of claim 39, further comprising instructions for:

attaching to an attachment router based on a second advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

outputting to the attachment router a third neighbor advertisement message specifying that the prescribed address prefix, the second address prefix, and the third attachment prefix are reachable via the default attachment address, based on the mobile router having attached to the attachment router, each of the prescribed address prefix and the second and third address prefixes being distinct from the attachment prefix.

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

means for attaching to an attachment router based on an advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

first outputting means for outputting to the attachment router a neighbor advertisement message specifying that a prescribed address prefix used by the mobile router is reachable via the default attachment address, based on the mobile router having attached to the attachment router, the prescribed address prefix distinct from the attachment prefix.

48. The mobile router of claim 47, further comprising:

second outputting means for outputting a second advertisement message specifying the prescribed address prefix and a tree information option field specifying attributes of the mobile router relative to the tree topology;

an ad hoc routing table; and

means for receiving via an ingress interface a second neighbor advertisement message that specifies a second address prefix is reachable via a second attachment address within the address space of the prescribed address prefix, the means for receiving configured for adding an entry to the ad hoc routing table specifying that the second address prefix is reachable using the second attachment address via the ingress interface.

49. The mobile router of claim 48, wherein the first outputting means is configured for outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message, the second address prefix distinct from the prescribed address prefix and the attachment prefix.

50. The mobile router of claim 49, wherein the means for receiving is configured for deleting the entry from the ad hoc routing table based on determined absence of activity from the second attachment address via the ingress interface for at least a prescribed time interval.

51. The mobile router of claim 49, wherein the means for receiving is configured for:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix; and

overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on receiving the fourth neighbor advertisement message following reception of the second neighbor advertisement message.

52. The mobile router of claim 51, wherein the second outputting means is configured for outputting on the first and second ingress interfaces a third advertisement message, specifying the prescribed address prefix and the tree information option field, in response to the overwriting of the entry.

53. The mobile router of claim 49, wherein the first outputting means is configured for outputting to the attachment router, in response to a new advertisement message from the attachment router specifying the attachment prefix, a new advertisement message specifying that the prescribed address prefix, and any address prefixes stored in the ad hoc routing table based on respective received neighbor advertisement messages, including the second address prefix, are reachable via the default attachment address.

54. The mobile router of claim 49, further comprising routing means for determining whether the ad hoc routing table includes any one of a specified destination address, having been specified in data packet having been received via the ingress interface, and an address table entry having a specified address prefix encompassing the specified destination address, the routing means configured for outputting the data packet to the attachment router based on a determined absence of any one of the specified destination address and the address table entry in the ad hoc routing table.

55. The mobile router of claim 49, wherein:

the first outputting means is configured for specifying in the neighbor advertisement message a first unique sequence number for the prescribed address prefix;

the receiving means configured for detecting within the second neighbor advertisement message a second sequence number associated with the second address prefix; and

the first outputting means is configured for specifying in the third neighbor advertisement message a third unique sequence number, greater than the first unique sequence number, for the prescribed address prefix.

56. The mobile router of claim 55, wherein the receiving means is configured for:

receiving via a second ingress interface a fourth neighbor advertisement message that specifies the second address prefix is reachable via a third attachment address within the address space of the prescribed address prefix, and a fourth sequence number associated with the second address prefix; and

selectively overwriting the entry in the ad hoc routing table to specify that the second address prefix is reachable using the third attachment address via the second ingress interface, based on the fourth sequence number for the second address prefix being greater than the second sequence number.

57. The mobile router of claim 48, wherein the first outputting means is configured for outputting to the attachment router a third neighbor advertisement message, specifying that the prescribed address prefix and the second address prefix are reachable via the default attachment address, in response to reception of the second neighbor advertisement message.

58. The mobile router of claim 47, wherein the means for attaching is configured for:

detecting within the advertisement router a tree information option field specifying a tree identifier and attributes of the attachment router relative to the tree topology, the attributes including one of a tree depth and a tree preference; and

selecting the attachment router, from a plurality of attachment routers having advertised respective tree identifiers and respective attributes, based on the attributes specified in the tree information option field.

59. The mobile router of claim 47, wherein the neighbor advertisement message is a network node-based advertisement message, the first outputting means configured for inserting into the neighbor advertisement message a network-in-node option field that specifies the prescribed address prefix is reachable via the default attachment address.

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

means for outputting an advertisement message including a tree information option field that specifies a prescribed address prefix used by the mobile router, and a tree attribute field advertising one of a relative position and a relative preference of the mobile router within a tree topology of the ad hoc network;

an ad hoc routing table;

means for receiving a first neighbor advertisement message specifying that at least a second address prefix is reachable via a first attachment address within an address space of the prescribed address prefix, the second address prefix distinct from the prescribed address prefix, the receiving means further configured for;

(1) adding a first entry to the ad hoc routing table, the first entry specifying that the second address prefix is reachable via the second attachment address,

(2) receiving a second neighbor advertisement message specifying that at least a third address prefix is reachable via a second attachment address within the address space of the prescribed address prefix, the third address prefix distinct from second address prefix and the prescribed address prefix, and

(3) adding a second entry to the ad hoc routing table, the second entry specifying that the third address prefix is reachable via the second attachment address; and

means for selectively routing a data packet having a specified destination address, by selectively routing the data packet to one of the first attachment address and the second attachment address based on determining the specified destination address is within the address space of a corresponding one of the second and third address prefixes.

61. The mobile router of claim 60, wherein:

receiving means is configured for detecting that the first neighbor advertisement message specifies that the second address prefix, and a fourth address prefix are reachable via the first attachment address, the fourth address prefix distinct from the second and third address prefixes and the prescribed address prefix;

receiving means is configured for adding a third entry to the ad hoc routing table that specifies that the fourth address prefix is reachable via the first attachment address.

62. The mobile router of claim 61, wherein:

receiving means is configured for receiving a third neighbor advertisement message specifying that the third address prefix and the fourth address prefix are reachable via the second attachment address;

receiving means is configured for selectively overwriting the third entry to specify that the fourth address prefix is reachable via the second attachment address.

63. The mobile router of claim 62, wherein the receiving means is configured for overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on receiving the third neighbor advertisement message following reception of the first neighbor advertisement message.

64. The mobile router of claim 62, wherein:

the first neighbor advertisement message specifies first and second unique sequence numbers for the second and fourth address prefixes, respectively;

the third neighbor advertisement specifies a third sequence number for the fourth address prefix;

the receiving means is configured for overwriting the third entry to specify that the fourth address is reachable via the second attachment address based on the third sequence number being greater than the second sequence number.

65. The mobile router of claim 62, wherein the means for outputting is configured for outputting another advertisement message including the tree information option field in response to the receiving means overwriting the third entry.

66. The mobile router of claim 60, wherein the receiving means is configured for deleting one of the first and second entries based on a detecting a corresponding prescribed interval of inactivity from the corresponding attachment address.

67. The mobile router of claim 60, further comprising:

means for attaching to an attachment router based on a second advertisement message from the attachment router that specifies an attachment prefix, and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, and based on selecting a default attachment address within an address space of the attachment prefix; and

means for outputting to the attachment router a third neighbor advertisement message specifying that the prescribed address prefix, the second address prefix, and the third attachment prefix are reachable via the default attachment address, based on the mobile router having attached to the attachment router, each of the prescribed address prefix and the second and third address prefixes being distinct from the attachment prefix.