Method and apparatus for automatic sub-division of areas that flood routing information

• US 8,699,410 B2
• Filed: 09/16/2009
• Issued: 04/15/2014
• Est. Priority Date: 08/29/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Retana, Alvaro, White, Russell
• Primary Examiner(s): PHUNKULH, BOB A
• Application Number:
  US12/560,890
• Publication Number:
  US 20100008231A1
• Time in Patent Office: 1,672 Days
• Field of Search: None
• US Class Current: 370/328
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

Techniques for sharing routing information over a network include determining whether the scale of a flooding domain exceeds a threshold. If so, then a router announcement message is sent over a particular link. The message indicates the local router is a flooding domain border router (FDBR). Summary routing information is determined with less than a certain level of detail used in the flooding domain for routers connected to the local router through links different from the particular link. The summary routing information is sent over the particular link in a link state message that includes type data that indicates summary routing information that crosses a FDBR. These techniques allow automatic favorable scaling of domains of shared routing information as the size of a mobile ad hoc network grows.

Claims

1. A method, comprising:

receiving routing information at a certain level of detail for a plurality of routers connected to a local router through a plurality of links, wherein one of the plurality of routers is an area boundary router;

determining a measure of scale of a flooding domain that includes the plurality of routers; and

after determining that the measure of scale of the flooding domain exceeds a threshold;

determining summary routing information with less than the certain level of detail for a group of routers connected to the local router through a set of one or more links of the local router, wherein the set of one or more links are included in the plurality of links;

sending, over a particular link, a router announcement message that indicates the local router is a flooding domain border router, wherein the particular link is different than the set of one or more links; and

sending, over the particular link, the summary routing information in a link state message that indicates summary routing information that crosses a flooding domain border router.

2. The method of claim 1, wherein the determining of the measure is triggered by a packet received by a first router.

3. The method of claim 2, wherein the measure includes whether the first router accepts an invitation to form an adjacency relationship with a second router, which sent the packet.

4. The method of claim 2, wherein the measure is combined with a count field within the packet to determine the measure of the new flooding domain.

5. The method of claim 1, further comprising:

determining whether to divide a particular flooding domain at a particular link if the threshold is exceeded.

6. The method of claim 1, wherein the summary routing information is determined from detailed routing information received for a selected one of a set of divided flooding domains, and wherein the summary routing information includes an Internet protocol (IP) address and a cost associated with packet propagation through the current flooding domain.

7. The method of claim 6, wherein the summary routing information is sent over a link using inter-domain messages.

8. The method of claim 1, further comprising:

sending the summary routing information over the particular link in a link state message that includes type data.

9. Logic encoded in one or more non-transitory tangible media that includes code for execution and when executed by a processor operable to perform operations comprising:

receiving routing information at a certain level of detail for a plurality of routers connected to a local router through a plurality of links of the local router, wherein one of the plurality of routers is an area boundary router;

determining a measure of scale of a flooding domain that includes the plurality of routers; and

after determining that the measure of scale of the flooding domain exceeds a threshold;

determining summary routing information with less than the certain level of detail for a group of routers connected to the local router through a set of one or more links of the local router, wherein the set of one or more links are included in the plurality of links;

sending, over a particular link, a router announcement message that indicates the local router is a flooding domain border router, wherein the particular link is different than the set of one or more links; and

sending, over the particular link, the summary routing information in a link state message that indicates summary routing information that crosses a flooding domain border router.

10. The logic of claim 9 being further operable to perform operations comprising:

designating a second flooding domain border router (FDBR) if the measure exceeds the threshold.

11. The logic of claim 9, wherein the determining of the measure is triggered by a packet received by a first router.

12. The logic of claim 11, wherein the measure includes whether the first router accepts an invitation to form an adjacency relationship with a second router, which sent the packet.

13. The logic of claim 11, wherein the measure is combined with a count field within the packet to determine the measure of the new flooding domain.

14. The logic of claim 9 being further operable to perform operations comprising:

determining whether to divide a particular flooding domain at a particular link if the threshold is exceeded.

15. The logic of claim 9, wherein the summary routing information is determined from detailed routing information received for a selected one of a set of divided flooding domains, and wherein the summary routing information includes an Internet protocol (IP) address and a cost associated with packet propagation through the current flooding domain.

16. The logic of claim 15, wherein the summary routing information is sent over a link using inter-domain messages.

17. An apparatus, comprising:

a memory configured to store data,

a processor operable to execute instructions associated with the data, the apparatus being configured to;

receive routing information at a certain level of detail for a plurality of routers connected to a local router through a plurality of links of the local router, wherein one of the plurality of routers is an area boundary router;

determine a measure of scale of a flooding domain that includes the plurality of routers;

determine summary routing information with less than the certain level of detail for a group of routers connected to the local router through a set of one or more links of the local router when the measure exceeds a threshold;

determine whether to divide a particular flooding domain at a particular link if the threshold is exceeded, wherein the particular link is different than the set of one or more links; and

send, over a particular link, a router announcement message that indicates the local router is a flooding domain border router when the measure exceeds the threshold; and

send, over the particular link, the summary routing information in a link state message that indicates summary routing information that crosses a flooding domain border router.

18. The apparatus of claim 17, being further configured to:

designate a second flooding domain border router (FDBR) if the measure exceeds the threshold.

19. The apparatus of claim 17, wherein the determining of the measure is triggered by a packet received by a first router, and wherein the measure is combined with a count field within the packet to determine the measure of the new flooding domain.

20. The apparatus of claim 19, wherein the measure includes whether the first router accepts an invitation to form an adjacency relationship with a second router, which sent the packet.

21. The apparatus of claim 17, wherein the summary routing information is determined from detailed routing information received for a selected one of a set of divided flooding domains, and wherein the summary routing information includes an Internet protocol (IP) address and a cost associated with packet propagation through the current flooding domain, and wherein the summary routing information is sent over a link using inter-domain messages.