Method and Apparatus for Automatic Sub-Division of Areas that Flood Routing Information

• US 20100008231A1
• Filed: 09/16/2009
• Published: 01/14/2010
• 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
• Granted Patent: US 8,699,410 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• 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. (canceled)

2. (canceled)

3. (canceled)

4. (canceled)

5. (canceled)

6. (canceled)

7. (canceled)

8. (canceled)

9. (canceled)

10. (canceled)

11. (canceled)

12. (canceled)

13. (canceled)

14. (canceled)

15. (canceled)

16. (canceled)

17. (canceled)

18. (canceled)

19. (canceled)

20. (canceled)

21. (canceled)

22. (canceled)

23. (canceled)

24. (canceled)

25. (canceled)

26. (canceled)

27. (canceled)

28. (canceled)

29. (canceled)

30. (canceled)

31. (canceled)

32. A method, comprising:

receiving routing information for a plurality of routers;

determining a measure of scale of a new flooding domain, which includes at least some of the routers, wherein the scale of the new flooding domain includes a current flooding domain; and

determining whether the measure exceeds a threshold indicative of router performance related to exchanging router data amongst at least some of the routers.

33. The method of claim 32, further comprising:

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

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

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

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

37. The method of claim 32, further comprising:

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

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

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

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

receiving routing information for a plurality of routers;

determining a measure of scale of a new flooding domain, which includes at least some of the routers, wherein the scale of the new flooding domain includes a current flooding domain; and

determining whether the measure exceeds a threshold indicative of router performance related to exchanging router data amongst at least some of the routers.

41. The logic of claim 40 being further operable to perform operations comprising:

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

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

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

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

45. The logic of claim 40 being further operable to perform operations comprising:

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

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

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

48. 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 for a plurality of routers;

determine a measure of scale of a new flooding domain, which includes at least some of the routers, wherein the scale of the new flooding domain includes a current flooding domain;

determine whether the measure exceeds a threshold indicative of router performance related to exchanging router data amongst at least some of the routers; and

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

49. The apparatus of claim 48, being further configured to:

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

50. The method of claim 48, 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.

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

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