Method and apparatus to elect ABRs dynamically and intelligently

• US 8,130,638 B2
• Filed: 01/24/2006
• Issued: 03/06/2012
• Est. Priority Date: 01/24/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yang, Yi, Retana, Alvaro E., Roy, Abhay, Lindem, Alfred C. III, Mirtorabi, Sina
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): SMITH, JOSHUA Y
• Application Number:
  US11/339,791
• Publication Number:
  US 20070171845A1
• Time in Patent Office: 2,233 Days
• Field of Search: None
• US Class Current: 370/219
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

The present invention elects an area border router from a plurality of potential area border routers by determining a full set of all areas attached to a router. A determination is made as to a full set of area pairs from the determined full set of areas. Routers are identified in a first area of the determined full set of areas that are reachable through an intra-area route in the first area, and routers are identified in a second area of the determined full set of areas that are reachable through an intra-area route in the second area. If there is a router that is unreachable through either an intra-area route in the first area or an intra-area route in the second area, then declare the first router to be an area border router, else new first and second areas are selected.

Claims

1. A method comprising:

in response to attachment of a first router to a new area, executing an area border router election algorithm on the first router to determine whether or not the first router should declare itself to be an ABR;

determining, by the area border router election algorithm executing on the first router, a full set of areas attached to the first router;

determining, by the area border router election algorithm executing on the first router, a full set of area pairs from the determined full set of areas; and

until the first router is declared to be an area border router or all areas in the determined full set of areas have been examined;

determining, by the area border router election algorithm executing on the first router, area border routers and potential area border routers in a first area of the determined full set of areas that are reachable through an intra-area route in the first area,

determining, by the area border router election algorithm executing on the first router, area border routers and potential area border routers in a second area of the determined full set of areas that are reachable through an intra-area route in the second area, and

for any area pair in the determined full set of area pairs, if there are less than a predetermined number of area border routers and potential area border routers that are reachable through either an intra-area route in the first area or an intra-area route in the second area, then declaring, by the first router executing the area border router election algorithm, the first router to be an area border router, else selecting new first and second areas from the determined full set of areas.

2. The method of claim 1, wherein the attachment of the first router to the new area causes a new pair of areas to be added to the full set of areas attached to the first router.

3. A non-transitory computer-readable storage medium containing instructions, which, when executed by a processor, are operable to:

in response to attachment of a first router to a new area, initiate an area border router election algorithm to determine whether or not the first router should be declared an area border router;

determine, by the area border router election algorithm, a full set of areas attached to the first router;

determine, by the area border router election algorithm, a full set of area pairs from the determined full set of areas; and

until the first router is declared to be an area border router or all areas in the determined full set of areas have been examined;

determine, by the area border router election algorithm, area border routers and potential area border routers in a first area of the determined full set of areas that are reachable through an intra-area route in the first area,

determine, by the area border router election algorithm, area border routers and potential area border routers in a second area of the determined full set of areas that are reachable through an intra-area route in the second area, and

for any area pair in the determined full set of area pairs, if there are less than a predetermined number of area border routers and potential area border routers that are reachable through either an intra-area route in the first area or an intra-area route in the second area, then declare the first router that is initially a potential area border router to be an area border router, else select new first and second areas from the determined full set of areas.

4. The non-transitory computer-readable medium of claim 3, wherein the attachment of the first router to the new area causes a new pair of areas to be added to the full set of areas attached to the first router.

5. A method comprising:

in response to attachment of a first router to a new area, initiate an area border router (ABR) election algorithm to determine whether or not the first router should declare itself to be an ABR;

determining, by the ABR election algorithm executing on the first router, a plurality of areas attached to the first router;

determining, by the ABR election algorithm executing on the first router, one or more area pairs from the plurality of areas, each area pair including a first area and a second area selected from the plurality of areas;

for each area pair of the one or more area pairs, determining, by the ABR election algorithm executing on the first router, whether there is a predetermined number of qualified routers that are reachable both via intra-area routes within the first area of the area pair and via intra-area routes within the second area of the area pair, wherein a particular router is considered a qualified router if the particular router has declared itself to be an ABR or has a higher priority to be an ABR than the first router; and

provided there is an area pair of the one or more area pairs that does not have the predetermined number of qualified routers, declaring, by the first router executing the ABR election algorithm, that the first router is an ABR.

6. The method of claim 5 wherein attachment of the first router to the new area causes one or more new area pairs to be added to the one or more area pairs.

7. The method of claim 5 wherein the predetermined number is one or more.

8. The method of claim 5 further comprising:

determining the first router is a potential area border router (PABR); and

executing the determining a plurality of areas attached to the first router, the determining one or more area pairs, and the determining whether there is a predetermined number of qualified routers, in response to the first router being determined to be a PABR.

9. The method of claim 5 further comprising:

advertising, by the first router, the first router'"'"'s priority to be an ABR by including an ABR priority in a link-state advertisement (LSA).

10. The method of claim 9 wherein the ABR priority is included in a type-length-value (TLV) in the LSA.

11. The method of claim 5 wherein the plurality of areas attached to the first router form a mobile ad-hoc network (MANET).

12. An apparatus comprising:

one or more communication connections;

a memory; and

a processor configured to execute an area border router (ABR) election algorithm in response to attachment of the apparatus to a new area, the ABR election algorithm to;

determine a plurality of areas attached to the apparatus,

determine one or more area pairs from the plurality of areas, each area pair including a first area and a second area selected from the plurality of areas,

for each area pair of the one or more area pairs, determine whether there is a predetermined number of qualified routers that are reachable both via intra-area routes within the first area of the area pair and via intra-area routes within the second area of the area pair, wherein a particular router is considered a qualified router if the particular router has declared itself to be an area border router (ABR) or has a higher priority to be an ABR than the apparatus, and

provided there is an area pair of the one or more area pairs that does not have the predetermined number of qualified routers, declare that the apparatus is an ABR.

13. The apparatus of claim 12 wherein the predetermined number is one or more.

14. The apparatus of claim 12 wherein the processor is further configured to advertise the apparatus'"'"'s priority to be an ABR by including an ABR priority in a link-state advertisement (LSA).

15. The apparatus of claim 14 wherein the ABR priority is included in a type-length-value (TLV) in the LSA.

16. A method comprising:

in response to attachment of a first router to a new area of an open shortest path first (OSPF) autonomous system (AS), executing an area border router (ABR) election algorithm on the first router to determine whether or not the first router should declare itself to be an ABR;

determining, by the ABR election algorithm executing on the first router, a plurality of areas of the OSPF AS that are attached to the first router;

determining, by the ABR election algorithm executing on the first router, one or more area pairs from the plurality of areas of the OSPF AS, each area pair including a first area of the OSPF AS and a second area OSPF AS selected from the plurality of areas of the OSPF AS;

for each area pair of the one or more area pairs, determining, by the ABR election algorithm executing on the first router, whether there is a predetermined number of qualified routers that are reachable both via intra-area routes within the first area of the OSPF AS of the area pair and via intra-area routes within the second area of the OSPF AS of the area pair, wherein a particular router is considered a qualified router if the particular router has declared itself to be an ABR or has a higher priority to be an ABR than the first router; and

in response to there being an area pair of the one or more area pairs that does not have the predetermined number of qualified routers, declaring, by the first router executing the ABR election algorithm, that the first router is an ABR.

17. The method of claim 16 wherein the predetermined number is one or more.

18. The method of claim 16 further comprising:

advertising the first router'"'"'s priority to be an ABR by including an ABR priority in a link-state advertisement (LSA).

19. The method of claim 18 wherein the ABR priority is included in a type-length-value (TLV) in the LSA.