Arrangement for providing optimized connections between peer routers in a tree-based ad hoc mobile network

• US 20060227724A1
• Filed: 04/08/2005
• Published: 10/12/2006
• Est. Priority Date: 04/08/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, Levy-Abegnoli, Eric M.
• Granted Patent: US 7,366,111 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 8/082 for traffic bypassing of mobility servers, e.g. location registers, home PLMNs or home agents
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Mobile routers in a tree-based network topology with a single clusterhead in an ad hoc network establish connectivity based on each attached mobile router sending a neighbor advertisement message to an attachment mobile router via a corresponding egress interface. Any neighbor advertisement message received by a mobile router is used to identify specified network prefixes that are reachable via the source of the neighbor advertisement message. Each attached mobile router outputs to its attachment router another neighbor advertisement message that specifies the network prefix used by the mobile router, and the specified network prefixes from its attached mobile routers. The mobile router also identifies peer mobile routers having the same depth, and selectively shares limited routing information with the peer routers, enabling the mobile router to bypass the clusterhead and reach remote prefixes via the peer routers without burdening the tree.

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, having advertised an attachment prefix, based on selecting a default attachment address within the attachment prefix and according to a protocol requiring establishment in the ad hoc network of a tree topology having a single clusterhead, the mobile router attaching to the attachment router at an identifiable depth relative to the clusterhead and advertising a first address prefix distinct from the attachment prefix;

receiving at least one neighbor advertisement message from at least one corresponding attached mobile router having attached to the mobile router and that specifies a corresponding second address prefix, distinct from the first address prefix, is reachable via a corresponding second attachment address within the address space of the first address prefix;

selectively sharing routing information with a peer mobile router attached within the tree topology at said identifiable depth, including;

(1) sending to the peer mobile router first routing information, composed of the first address prefix and any second address prefixes having been received from neighbor advertisement messages, as reachable via the mobile router, and

(2) receiving from the peer mobile router second routing information specifying at least one remote address prefix is reachable via the peer mobile router, the at least one remote address prefix distinct from any of the attachment prefix, the first address prefix, and any second address prefix; and

outputting to the attachment router a second neighbor advertisement message specifying the first routing information, wherein the second routing information received from any peer mobile router attached at said identifiable depth is not sent to the attachment router.

2. The method of claim 1, wherein the first routing information includes address prefixes of respective mobile routers having attached within the tree topology to reach the clusterhead via the mobile router.

3. The method of claim 2, wherein the selectively sharing further includes:

receiving an advertisement message from the peer mobile router that includes a tree information option field specifying the identifiable depth; and

sending the first routing information to the peer mobile router based on the received advertisement message specifying that the mobile router and the peer mobile router are attached within the tree topology at the identifiable depth.

4. The method of claim 3, wherein the outputting of the second neighbor advertisement message specifying the first routing information is executed according to a first routing protocol, and the selectively sharing of the routing information is executed according to a second routing protocol distinct and independent from the first routing protocol.

5. The method of claim 4, wherein the first routing protocol is any one of OSPF and AODV protocol.

6. The method of claim 1, further comprising:

receiving a packet having a destination address within a destination prefix;

accessing a routing table configured for specifying the first routing information and the second routing information received from said any peer mobile router, and selectively outputting the packet to an identified destination based on a match between the destination prefix and a corresponding entry in the routing table that specifies the destination prefix and the identified destination; and

outputting the packet to the attachment router based on a determined absence of the destination prefix in any one of the first routing table and the second routing table.

7. The method of claim 6, wherein the outputting includes sending within the second neighbor advertisement message the address prefixes received from the neighbor advertisement messages, and not any of the second routing information stored in the routing table.

8. The method of claim 6, further comprising sending to another peer mobile router the first routing information specified in the routing table, and the second routing information consisting of (1) selected address prefixes in the second routing table that are reachable via the mobile router within a prescribed cost attribute, and (2) respective cost attributes of the selected address prefixes in the second routing table.

9. The method of claim 8, further comprising selectively storing the at least one remote address prefix in the routing table based on determining from the corresponding cost attributes that the at least one remote address prefix is reachable within a prescribed network distance.

10. The method of claim 9, wherein the prescribed network distance specifies a prescribed number of hop counts between the mobile router and the one peer mobile router serving as an attachment router for the associated remote address prefix, the prescribed network distance being less than twice the identifiable depth.

11. An ad hoc network comprising:

a plurality of mobile routers having organized into a tree topology having attached mobile routers having attached to attachment routers, one of the attachment routers serving as a clusterhead, each mobile router including;

(1) an attachment resource configured for enabling the corresponding mobile router to attach to one of the attachment routers as a corresponding one of the attached mobile routers;

(2) an advertisement portion configured for enabling the corresponding mobile router to serve as one of the attachment routers for at least one of the attached mobile routers, the advertisement portion further configured for;

(a) outputting a first advertisement message and that includes a tree information option field that specifies a prescribed address prefix used by the corresponding mobile router, and a tree attribute field that identifies a corresponding depth of the corresponding mobile router within the tree topology, the clusterhead specifying a zero depth, and

(b) selectively outputting, to the corresponding attachment router, a neighbor advertisement message based on the corresponding mobile router being one of the attached mobile routers, the neighbor advertisement message specifying that at least the corresponding prescribed address prefix, and any received address prefixes from any received neighbor advertisement messages from respective attached mobile routers, are reachable via a corresponding attachment address used by the corresponding mobile router to attach to the corresponding attachment router, the attachment address of the corresponding mobile router within the prescribed address prefix of the corresponding attachment router;

(3) a peer discovery resource independent of the advertisement portion and configured for enabling the corresponding mobile router, as one of the attached mobile routers, to selectively share routing information with another one of the attached mobile routers having a matching depth within the tree topology, the routing information including that the corresponding address prefix and the received address prefixes are reachable via the corresponding attachment address; and

(4) a routing table configured for storing peer routing information having been received from said another one of the attached mobile routers.

12. The network of claim 11, wherein the peer discovery resource is configured for selectively sharing the routing information based on receiving an advertisement message from said another one of the attached mobile routers that includes a corresponding tree information option field specifying the matching depth.

13. The network of claim 12, wherein the advertisement portion is configured for outputting the neighbor advertisement message without any of the peer routing information.

14. The network of claim 13, wherein the peer discovery resource is configured for sharing the routing information, and receive the peer routing information, according to any one of OSPF and AODV protocol.

15. The network of claim 11, wherein:

the routing table is configured for storing the received address prefixes and respective attachment addresses that are within the corresponding prescribed address prefix; and

each mobile router further includes a routing resource configured for determining a destination for a packet having been received and specifying a destination address within a destination prefix, the corresponding routing resource configured for selecting the egress interface as the destination based on a determined absence of the destination prefix in the corresponding routing table.

16. The network of claim 15, wherein the advertisement portion is configured for specifying within the corresponding neighbor advertisement message the received address prefixes stored in the second table, and not any of the peer routing information stored in the routing table.

17. The network of claim 15, wherein the peer discovery resource is configured for sending to a second one of the attached mobile routers having the matching depth the received address prefixes specified in the routing table, selected remote address prefixes from the peer routing information in the routing table that are reachable via the corresponding mobile router within a prescribed cost attribute, and respective cost attributes of the selected remote address prefixes.

18. The network of claim 17, wherein the peer discovery resource is configured for selectively storing the remote address prefixes in the routing table based on determining from the respective cost attributes that the remote address prefixes are reachable within a prescribed network distance.

19. The network of claim 18, wherein the prescribed network distance specifies a prescribed number of hop counts between the corresponding mobile router and the mobile router serving as an attachment router for the associated remote address prefix, the prescribed network distance being less than twice the identifiable depth.

20. A mobile router comprising:

an advertisement portion configured for;

(a) outputting a first advertisement message that includes a tree information option field that specifies a prescribed address prefix used by the mobile router, and a tree attribute field that identifies a corresponding depth of the mobile router within a tree topology having a plurality of attached mobile routers attached to a plurality of attachment routers, one of the attachment routers being a clusterhead of the tree topology and having a zero depth, and

(b) selectively outputting a neighbor advertisement message based on the mobile router being one of the attached mobile routers, the neighbor advertisement message specifying that at least the prescribed address prefix, and any received address prefixes from any received neighbor advertisement messages from respective attached mobile routers, are reachable via a corresponding attachment address used by the mobile router to attach to a corresponding attachment router, the attachment address of the mobile router within a prescribed address prefix of the corresponding attachment router;

a peer discovery resource independent of the advertisement portion and configured for enabling the mobile router, as one of the attached mobile routers, to selectively share routing information with another one of the attached mobile routers having a matching depth within the tree topology, the routing information including that the corresponding address prefix and the received address prefixes are reachable via the corresponding attachment address; and

a routing table configured for storing peer routing information having been received from said another one of the attached mobile routers.

21. The mobile router of claim 20, wherein the peer discovery resource is configured for selectively sharing the routing information based on receiving an advertisement message from said another one of the attached mobile routers that includes a corresponding tree information option field specifying the matching depth.

22. The mobile router of claim 21, wherein the advertisement portion is configured for outputting the neighbor advertisement message without any of the peer routing information.

23. The mobile router of claim 22, wherein the peer discovery resource is configured for sharing the routing information, and receive the peer routing information, according to any one of OSPF and AODV protocol.

24. The mobile router of claim 20, wherein:

the routing table is configured for storing the received address prefixes and respective attachment addresses that are within the prescribed address prefix;

the mobile router further comprising a routing resource configured for determining a destination for a packet having been received and specifying a destination address within a destination prefix, the routing resource configured for selecting the attachment router as the destination based on a determined absence of the destination prefix in the routing table.

25. The mobile router of claim 24, wherein the advertisement portion is configured for specifying within the neighbor advertisement message the received address prefixes stored in the routing table, and not any of the peer routing information stored in the routing table.

26. The mobile router of claim 24, wherein the peer discovery resource is configured for sending to a second one of the attached mobile routers having the matching depth the received address prefixes specified in the routing table, selected remote address prefixes from the peer routing information in the routing table that are reachable via the corresponding mobile router within a prescribed cost attribute, and respective cost attributes of the selected remote address prefixes.

27. The mobile router of claim 26, wherein the peer discovery resource is configured for selectively storing the remote address prefixes in the routing table based on determining from the respective cost attributes that the remote address prefixes are reachable within a prescribed network distance.

28. The mobile router of claim 27, wherein the prescribed network distance specifies a prescribed number of hop counts between the mobile router and the mobile router serving as an attachment router for the associated remote address prefix, the prescribed network distance being less than twice the identifiable depth.

29. A mobile router comprising:

advertisement means for outputting a first advertisement message that includes a tree information option field that specifies a prescribed address prefix used by the mobile router, and a tree attribute field that identifies a corresponding depth of the mobile router within a tree topology having a plurality of attached mobile routers attached to a plurality of attachment routers, one of the attachment routers being a clusterhead of the tree topology and having a zero depth;

the advertisement means further configured for selectively outputting a neighbor advertisement message based on the mobile router being one of the attached mobile routers, the neighbor advertisement message specifying that at least the prescribed address prefix, and any received address prefixes from any received neighbor advertisement messages from respective attached mobile routers, are reachable via a corresponding attachment address used by the mobile router to attach to a corresponding attachment router, the attachment address of the mobile router within a prescribed address prefix of the corresponding attachment router;

peer discovery means, independent of the advertisement means, for enabling the mobile router, as one of the attached mobile routers, to selectively share routing information with another one of the attached mobile routers having a matching depth within the tree topology, the routing information including that the corresponding address prefix and the received address prefixes are reachable via the corresponding attachment address; and

storage means for storing peer routing information having been received from said another one of the attached mobile routers.

30. The mobile router of claim 29, wherein the peer discovery means is configured for selectively sharing the routing information based on receiving an advertisement message from said another one of the attached mobile routers that includes a corresponding tree information option field specifying the matching depth.

31. The mobile router of claim 30, wherein the advertisement means is configured for outputting the neighbor advertisement message without any of the peer routing information.

32. The mobile router of claim 31, wherein the peer discovery means is configured for sharing the routing information, and receive the peer routing information, according to any one of OSPF and AODV protocol.

33. The mobile router of claim 29, wherein:

the storage means is configured for storing the received address prefixes and respective attachment addresses that are within the prescribed address prefix;

the mobile router further comprising routing means for determining a destination for a packet having been received and specifying a destination address within a destination prefix, the routing means configured for selecting the egress interface as the destination based on a determined absence of the destination prefix in the storage means.

34. The mobile router of claim 33, wherein the advertisement means is configured for specifying within the neighbor advertisement message the received address prefixes stored in the storage means, and not any of the peer routing information stored in the storage means.

35. The mobile router of claim 34, wherein the peer discovery means is configured for sending to a second one of the attached mobile routers having the matching depth the received address prefixes specified in the storage means, selected remote address prefixes from the peer routing information in the storage means that are reachable via the corresponding mobile router within a prescribed cost attribute, and respective cost attributes of the selected remote address prefixes.

36. The mobile router of claim 35, wherein the peer discovery means is configured for selectively storing the remote address prefixes in the storage means based on determining from the respective cost attributes that the remote address prefixes are reachable within a prescribed network distance.

37. The mobile router of claim 36, wherein the prescribed network distance specifies a prescribed number of hop counts between the mobile router and the mobile router serving as an attachment router for the associated remote address prefix, the prescribed network distance being less than twice the identifiable depth.