Joining tree-based networks into an autonomous system using peer connections between the tree-based networks

• US 8,102,775 B2
• Filed: 03/12/2007
• Issued: 01/24/2012
• Est. Priority Date: 03/12/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal
• Primary Examiner(s): Ferris, Derrick
• Assistant Examiner(s): KHIRODHAR, MAHARISHI V
• Application Number:
  US11/716,586
• Publication Number:
  US 20080228940A1
• Time in Patent Office: 1,779 Days
• Field of Search: 370/255, 370/256, 370/238, 370/390, 370/408, 709/238
• US Class Current: 370/238
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• 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/033 by updating distance vector protocols
• 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 61/50 Address allocation

Abstract

In one embodiment, a first router attaches to an attachment router based on detecting a first router advertisement message specifying an attachment prefix and a first tree information option. The first tree information option includes a first IP host address of a first clusterhead having established a first tree topology. The first router receives a second advertisement from a second router specifying a second address prefix, distinct from the attachment prefix and the first address prefix of the first router, and a second tree information option specifying a second IP host address of a second clusterhead having established a second distinct tree topology. If the first and second routers are at equal depths relative to the respective first and second clusterheads, routing information is shared, including first address prefix reachable via the first router, and a host route for reaching the first IP host address via the first router.

Claims

1. A method comprising:

attaching by a first router to an attachment router based on detecting a first router advertisement message from the attachment router, the first router advertisement message specifying an attachment prefix owned by the attachment router and a first tree information option, the attachment prefix distinct from a first address prefix owned by the first router, the first tree information option specifying a depth of the attachment router within a first tree topology and a first IP host address, the first IP host address of a first border router of a first autonomous system and serving as a first clusterhead having established the first tree topology in the first autonomous system, the attaching including attaching to the first tree topology based on selecting a default attachment address within the attachment prefix owned by the attachment router, and identifying the depth of the first router relative to the first clusterhead based on the incrementing the depth specified for the attachment router;

receiving, by the first router, a second advertisement from a second router and specifying a second address prefix and a second tree information option, the second address prefix distinct from the attachment prefix and the first address prefix, the second tree information option specifying a second IP host address, the second IP host address of a second border router of the first autonomous system and serving as a second clusterhead distinct from the first clusterhead and having established a second tree topology in the first autonomous system and distinct from the first tree topology, the second tree information option further specifying the corresponding depth of the second router relative to the second clusterhead; and

selectively sharing routing information, by the first router, with the second router based on the first router determining that the corresponding depth of the first router relative to the first clusterhead equals the corresponding depth of the second router relative to the second clusterhead, the routing information including specifying that the first address prefix is reachable via the first router, the routing information further including a host route for reaching the first IP host address via the first router, enabling the first border router and the second border router to share routing information for reaching a second autonomous system distinct from the first autonomous system.

2. The method of claim 1, further comprising:

receiving by the first router second routing information from the second router, the second routing information including third address prefixes distinct from any one of the attachment prefix, the first address prefix, or the second address prefix and reachable by the second router within the second tree topology and a second host route for reaching the second IP host address via the second router; and

outputting by the first router a neighbor advertisement message to the attachment router, the neighbor advertisement message specifying that the first address prefix is reachable via the default attachment address, and a third host route for reaching the second IP host address via the default attachment address, the neighbor advertisement message not including the third address prefixes.

3. The method of claim 2, further comprising:

receiving by the first router a second neighbor advertisement from an attached router specifying a second attachment address within the first address prefix, the second neighbor advertisement message specifying a fourth address prefix reachable via the second attachment address, the fourth address prefix distinct from any one of the attachment prefix, the first address prefix, the second address prefix, or the third address prefixes;

sharing, by the first router, with the second router that the fourth address prefix is reachable via the first router;

outputting by the first router an updated neighbor advertisement message to the attachment router that specifies that the first address prefix and the fourth address prefix are reachable via the default attachment address, and the third host route that the second IP host address is reachable via the default attachment address within the attachment prefix, the updated neighbor advertisement message not including the third address prefixes.

4. The method of claim 3, wherein:

the second neighbor advertisement specifies a fourth host route for reaching the second IP host address via the second attachment address at a corresponding identified cost,

the third host route in the updated neighbor advertisement message specifying a corresponding cost, and

the updated neighbor advertisement including a third host route for reaching the second IP host address via the second attachment address as a best host route relative to the fourth host route.

5. The method of claim 3, further comprising flooding, by the first router, the attached router specifying that the routing information and the second routing information are reachable via the first router.

6. The method of claim 1, wherein the selectively sharing includes sharing the routing information between the first router and the second router according to an interior border gateway routing protocol, the first and second routers establishing a distinct area within the first autonomous system having been established by the first border router and the second border router.

7. A method comprising:

detecting, by a border router of a first autonomous system, an external router of a second autonomous system distinct from the first autonomous system, and in response sharing routes with the external router according to an exterior border gateway protocol;

outputting, by the border router, a router advertisement message specifying an attachment prefix and a tree information option, the attachment prefix owned by the border router and the tree information option identifying the border router as a first clusterhead of a first tree topology in the first autonomous system based on the tree information option having a depth field specifying a zero depth and a tree identifier field specifying a first IP host address of the border router;

receiving, by the border router, neighbor advertisement messages from attached routers within the first autonomous system and having attached to the border router using respective attachment addresses within an address realm of the attachment prefix, each neighbor advertisement message specifying reachability via the corresponding attachment address of at least one address prefix that is distinct from the attachment prefix and distinct from other address prefixes specified in the neighbor advertisement messages from any other attached router;

detecting, by the border router in at least one of the neighbor advertisement messages, at least a first host route for reaching a second IP host address of a second border router of the first autonomous system via a corresponding at least one of the attachment addresses, the second IP host address not within the address realm of the attachment prefix or any of the address prefixes specified in the neighbor advertisement messages;

storing, by the border router in a routing table in the border router, the address prefixes reachable via the attachment addresses and the first host route based on the received neighbor advertisement messages;

creating a communication path with the second border router at the second IP host address based on the first host route; and

exchanging routing information by the border router with the second border router via the communication path according to an interior border gateway protocol, the routing information specifying that the second autonomous system, the address prefixes specified in the neighbor advertisement messages, and the attachment prefix owned by the border router are reachable via the first IP host address of the border router, the communication path and the exchanging routing information enabling the border router and the second border router to form a backbone area of the first autonomous system.

8. The method of claim 7, wherein the exchanging routing information includes receiving remote reachability information specifying remote prefixes that are reachable via the second IP host addresses, wherein none of the remote prefixes are within the address realm of the attachment prefix or any of the address prefixes specified in the neighbor advertisement messages.

9. The method of claim 7, wherein:

the first host route specifies a corresponding first cost for reaching the second IP host address;

at least another one of the neighbor advertisement messages specifying a second host route for reaching the second IP host address via the corresponding attachment address at a corresponding second cost;

the creating including selecting the first host route for reaching the second IP host address based on the corresponding first cost being less than the second cost.

10. The method of claim 9, wherein the creating further includes storing the first host route and the second host route concurrently in the routing table.

11. The method of claim 7, further comprising:

receiving a data packet from one of the attached routers, the data packet specifying a destination address;

determining from the routing table that the destination address is reachable via the second IP host address; and

forwarding the data packet to the second border router via the communication path.

12. An apparatus comprising:

a network interface circuit configured for receiving;

a first router advertisement message from an attachment router, the first router advertisement message specifying an attachment prefix owned by the attachment router and a first tree information option, the attachment prefix distinct from a first address prefix owned by the apparatus, the first tree information option specifying a depth of the attachment router within a first tree topology and a first IP host address, the first IP host address of a first border router of a first autonomous system and serving as a first clusterhead having established the first tree topology in the first autonomous system, and

a second advertisement from a second router and specifying a second address prefix and a second tree information option, the second address prefix distinct from the attachment prefix and the first address prefix, the second tree information option specifying a second IP host address, the second IP host address of a second border router of the first autonomous system and serving as a second clusterhead distinct from the first clusterhead and having established a second tree topology in the first autonomous system and distinct from the first tree topology, the second tree information option further specifying the corresponding depth of the second router relative to the second clusterhead; and

a routing circuit configured for attaching to the first tree topology based on selecting a default attachment address within the attachment prefix owned by the attachment router, and identifying the depth of the apparatus relative to the first clusterhead based on the incrementing the depth specified for the attachment router, the routing circuit further configured for selectively sharing routing information with the second router based on determining that the corresponding depth of the apparatus relative to the first clusterhead equals the corresponding depth of the second router relative to the second clusterhead, the routing information including specifying that the first address prefix is reachable via the apparatus, the routing information further including a host route for reaching the first IP host address via the apparatus, enabling the first border router and the second border router to share routing information for reaching a second autonomous system distinct from the first autonomous system.

13. The apparatus of claim 12, wherein:

the network interface circuit is configured for receiving second routing information from the second router, the second routing information including third address prefixes distinct from any one of the attachment prefix, the first address prefix, or the second address prefix and reachable by the second router within the second tree topology and a second host route for reaching the second IP host address via the second router;

the routing circuit is configured for generating, for output to the attachment router, a neighbor advertisement message specifying that the first address prefix is reachable via the default attachment address, and further specifying a third host route for reaching the second IP host address via the default attachment address, the neighbor advertisement message not including the third address prefixes.

14. The apparatus of claim 13, wherein:

the network interface circuit is configured for receiving a second neighbor advertisement from an attached router specifying a second attachment address within the first address prefix, the second neighbor advertisement message specifying a fourth address prefix reachable via the second attachment address, the fourth address prefix distinct from any one of the attachment prefix, the first address prefix, the second address prefix, or the third address prefixes;

the routing circuit configured for sharing with the second router that the fourth address prefix is reachable via the first router;

the routing circuit further configured for generating, for output to the attachment router, an updated neighbor advertisement message that specifies that the first address prefix and the fourth address prefix are reachable via the default attachment address, and further specifying the third host route that the second IP host address is reachable via the default attachment address within the attachment prefix, the updated neighbor advertisement message not including the third address prefixes.

15. The apparatus of claim 14, wherein:

the second neighbor advertisement specifies a fourth host route for reaching the second IP host address via the second attachment address at a corresponding identified cost,

the routing circuit further configured for specifying for the third host route in the updated neighbor advertisement message a corresponding cost, and

the routing circuit further configured for selecting the third host route for the updated neighbor advertisement message, based on determining the third host route has a best cost for reaching the second IP host address relative to the fourth host route.

16. The apparatus of claim 14, wherein the routing circuit is configured for flooding the attached router with the routing information and the second routing information that are reachable via the first router.

17. The apparatus of claim 12, wherein the routing circuit is configured for sharing the routing information with the second router according to an interior border gateway routing protocol, the apparatus and the second router establishing a distinct area within the first autonomous system having been established by the first border router and the second border router.

18. An apparatus comprising:

a routing table, the apparatus implemented as a border router of a first autonomous system;

a routing circuit configured for sharing routes with an external router of a second autonomous system, distinct from the first autonomous system, according to an exterior border gateway protocol in response to detection of the external router, the routing circuit further configured for generating a router advertisement message specifying an attachment prefix and a tree information option, the attachment prefix owned by the apparatus and the tree information option identifying the apparatus as a first clusterhead router of a first tree topology in the first autonomous system based on the tree information option having a depth field specifying a zero depth and a tree identifier field specifying a first IP host address of the apparatus; and

a network interface circuit configured for outputting the router advertisement message on at least one network link in the first autonomous system, the network interface circuit configured for receiving, via the at least one network link, neighbor advertisement messages from attached routers having attached to the first clusterhead router using respective attachment addresses within an address realm of the attachment prefix, each neighbor advertisement message specifying reachability via the corresponding attachment address of at least one address prefix that is distinct from the attachment prefix and distinct from other address prefixes specified in the neighbor advertisement messages from any other attached router;

the routing circuit further configured for detecting, in at least one of the neighbor advertisement messages, at least a first host route for reaching a second IP host address of a second border router of the first autonomous system via a corresponding at least one of the attachment addresses, the second IP host address not within the address realm of the attachment prefix or any of the address prefixes specified in the neighbor advertisement messages;

the routing circuit further configured for storing, in the routing table, the address prefixes reachable via the attachment addresses and the first host route based on the received neighbor advertisement messages;

the routing circuit further configured for creating a communication path with the second border router at the second IP host address based on the first host route, and exchanging routing information with the second router via the communication path according to an interior gateway protocol, the routing information specifying that the second autonomous system, the address prefixes specified in the neighbor advertisement messages, and the attachment prefix owned by the apparatus are reachable via the first IP host address of the apparatus, the communication path and the exchanging routing information enabling the apparatus and the second border router to form a backbone area of the first autonomous system.

19. The apparatus of claim 18, wherein the routing received from the second router via the communication path includes remote reachability information specifying remote prefixes that are reachable via the second IP host addresses, wherein none of the remote prefixes are within the address realm of the attachment prefix or any of the address prefixes specified in the neighbor advertisement messages.

20. The apparatus of claim 18, wherein:

the first host route specifies a corresponding first cost for reaching the second IP host address;

at least another one of the neighbor advertisement messages specifying a second host route for reaching the second IP host address via the corresponding attachment address at a corresponding second cost;

the routing circuit is configured for selecting the first host route for reaching the second IP host address based on determining that the corresponding first cost being less than the second cost.

21. The apparatus of claim 20, wherein the routing circuit is configured for storing the first host route and the second host route concurrently in the routing table.

22. The apparatus of claim 18, wherein:

the network interface circuit is configured for receiving a data packet from one of the attached routers, the data packet specifying a destination address;

the routing circuit is configured for determining from the routing table that the destination address is reachable via the second IP host address, and in response encapsulating the data packet in an encapsulated packet;

the network interface circuit configured for forwarding the encapsulated packet containing the data packet to the second border router via the communication path.

23. An apparatus comprising:

means for receiving a first router advertisement message from an attachment router, and a second advertisement from a second router, the first router advertisement message specifying an attachment prefix owned by the attachment router and a first tree information option, the attachment prefix distinct from a first address prefix owned by the apparatus, the first tree information option specifying a depth of the attachment router within a first tree topology and a first IP host address of a first border router of a first autonomous system and serving as a first clusterhead having established the first tree topology in the first autonomous system, the second advertisement specifying a second address prefix and a second tree information option, the second address prefix distinct from the attachment prefix and the first address prefix, the second tree information option specifying a second IP host address of a second border router of the first autonomous system and serving as a second clusterhead distinct from the first clusterhead and having established a second tree topology in the first autonomous system and distinct from the first tree topology, the second tree information option further specifying the corresponding depth of the second router relative to the second clusterhead; and

means for attaching to the first tree topology based on selecting a default attachment address within the attachment prefix owned by the attachment router, and identifying the depth of the apparatus relative to the first clusterhead based on the incrementing the depth specified for the attachment router, the means for attaching further configured for selectively sharing routing information with the second router based on determining that the corresponding depth of the apparatus relative to the first clusterhead equals the corresponding depth of the second router relative to the second clusterhead, the routing information including specifying that the first address prefix is reachable via the apparatus, the routing information further including a host route for reaching the first IP host address via the apparatus, enabling the first border router and the second border router to share routing information for reaching a second autonomous system distinct from the first autonomous system.

24. An apparatus comprising:

means for storing routing information, the apparatus implemented as a border router of a first autonomous system

means for generating a router advertisement message, the means for generating further configured for generating routes with an external router of a second autonomous system, distinct from the first autonomous system, according to an exterior border gateway protocol in response to detection of the external router, the router advertisement message specifying an attachment prefix and a tree information option, the attachment prefix owned by the apparatus and the tree information option identifying the apparatus as a first clusterhead router of a first tree topology in the first autonomous system based on the tree information option having a depth field specifying a zero depth and a tree identifier field specifying a first IP host address of the apparatus;

means for outputting the router advertisement message on at least one network link in the first autonomous system, the means for outputting further configured for receiving, via the at least one network link, neighbor advertisement messages from attached routers having attached to the first clusterhead router using respective attachment addresses within an address realm of the attachment prefix, each neighbor advertisement message specifying reachability via the corresponding attachment address of at least one address prefix that is distinct from the attachment prefix and distinct from other address prefixes specified in the neighbor advertisement messages from any other attached router;

the means for generating further configured for detecting, in at least one of the neighbor advertisement messages, at least a first host route for reaching a second IP host address of a second border router of the first autonomous system via a corresponding at least one of the attachment addresses, the second IP host address not within the address realm of the attachment prefix or any of the address prefixes specified in the neighbor advertisement messages;

the means for generating further configured for storing, into the means for storing, the address prefixes reachable via the attachment addresses and the first host route based on the received neighbor advertisement messages;

the means for generating further configured for creating a communication path with the second router at the second IP host address based on the first host route, and exchanging routing information with the second router via the communication path according to an interior gateway protocol, the routing information specifying that the second autonomous system, the address prefixes specified in the neighbor advertisement messages, and the attachment prefix owned by the apparatus are reachable via the first IP host address of the apparatus, the communication path and the exchanging routing information enabling the apparatus and the second border router to form a backbone area of the first autonomous system.