Method and apparatus to elect ABRs dynamically and intelligently

• US 20070171845A1
• Filed: 01/24/2006
• Published: 07/26/2007
• 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: Retana, Alvaro, Roy, Abhay, Yang, Yi, Mirtorabi, Sina, Lindem, Alfred
• Granted Patent: US 8,130,638 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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 for electing an area border router from a plurality of potential area border routers, comprising:

determining a full set of all areas attached to a first router;

determining 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 all areas have been examined;

determining 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 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;

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 is 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 to be an area border router, else select new first and second areas from the determined full set of all areas.

2. The method of claim 1, wherein the method is invoked when a pair of areas is added to the determined full set of all areas attached to the first router.

3. The method of claim 1, wherein the method is invoked when one of the determined routers in the first area of the determined full set of areas that are reachable through an intra-area route in the first area is removed.

4. The method of claim 1, wherein the method is invoked when one of the determined routers in the second area of the determined full set of areas that are reachable through an intra-area route in the second area is removed.

5. A computer-readable medium containing instructions, which, when executed by a computer, elect an area border router from a plurality of potential area border routers, by:

determining a full set of all areas attached to a first router;

determining 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 all areas have been examined;

determining 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 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;

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 is 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 to be an area border router, else select new first and second areas from the determined full set of all areas.

6. The computer-readable medium of claim 5, wherein the instructions are executed when a pair of areas is added to the determined full set of all areas attached to the first router.

7. The computer-readable medium of claim 5, wherein the instructions are executed when one of the determined routers in the first area of the determined full set of areas that are reachable through an intra-area route in the first area is removed.

8. The computer-readable medium of claim 5, wherein the instructions are executed when one of the determined routers in the second area of the determined full set of areas that are reachable through an intra-area route in the second area is removed.

9. An apparatus for electing an area border router from a plurality of potential area border routers, comprising:

means for determining a full set of all areas attached to a first router;

means for determining a full set of area pairs from the determined full set of areas; and

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

determining 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 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;

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 is reachable through either an intra-area route in the first area or an intra-area route in the second area, then means for declaring the first router to be an area border router, else selecting new first and second areas from the determined full set of all areas.