Method and system for determining network characteristics using routing protocols

• US 7,423,979 B2
• Filed: 09/26/2003
• Issued: 09/09/2008
• Est. Priority Date: 05/18/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Martin, Daniel J.
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US10/672,303
• Publication Number:
  US 20040233859A1
• Time in Patent Office: 1,810 Days
• Field of Search: 370/401, 370/402, 370/389, 370/254, 370/255, 370/248, 370/395.31, 370/411, 370/400
• US Class Current: 370/255
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method and system are described herein for obtaining IGP network information useful in determining network routing topologies. The method involves querying a router for its router identifier and all its area identifiers, counting the router'"'"'s number of area identifiers to determine whether the router is an ABR or an ASBR, and querying the router'"'"'s link state database for the lowest area identifier on the router. The method further involves importing all Type 1 and Type 2 LSAs for that area into the database of a network discovery software engine, importing from the router'"'"'s link state database only those networks outside the router'"'"'s autonomous system that are also directly connected to an ASBR, then moving to the next highest area identifier in the router'"'"'s database to repeat importing Type 1 and Type 2 LSAs for that area into the database. Next, the method involves importing from the router'"'"'s link state database only those networks outside the router'"'"'s autonomous system that are also directly connected to an ASBR. This process is repeated until there are no more areas on the router that have not been processed. Then, starting with the lowest area-identifier discovered, all networks in the area making LSAs other than Type 1 or Type 2 are swept. The entire process is repeated for every router discovered.

Claims

1. A method for determining a topology of a network, the method comprising:

communicating with a first router in the network;

querying a first link state database of the first router for first Type 1 and Type 2 link state advertisements in a first area;

importing the Type 1 and Type 2 link state advertisement into a network topology information database; and

sweeping all networks in the first area announced by the first router and which make Type 3, Type 4, Type 5 or Type 7 announcements.

2. The method as recited in claim 1, further comprising:

querying the first router for a router identifier; and

determining a number of areas connected to the first router.

3. The method as recited in claim 1, further comprising importing into the network topology information database additional topology information for all networks directly connected to the first router.

4. The method as recited in claim 1, further comprising:

querying the first link state database for each respective area connected to the first router to determine respective Type 1 and Type 2 link advertisements for the respective areas; and

importing into the network topology information database, the respective Type 1 and Type 2 link state advertisements.

5. The method as recited in claim 1, wherein when the sweeping locates a second router, the method further comprises:

communicating with the second router;

querying a second link state database of the second router for second Type 1 and Type 2 link state advertisements in a second area; and

importing the second Type 1 and Type 2 link state advertisements into the network topology information database.

6. The method as recited in claim 1, further comprising sweeping all networks in the first area announced by the first router and which do not make Type 3, Type 4, Type 5 or Type 7 announcements.

7. The method as recited in claim 6, wherein when the sweeping locates a second router, the method further comprises:

communicating with the second router;

querying a second link state database of the second router for second Type 1 and Type 2 link state advertisements in a second area; and

importing the second Type 1 and Type 2 link state advertisements into the network topology information database.

8. The method as recited in claim 5, further comprising sweeping all networks in the second area announced by the second router and which do not make Type 3, Type 4, Type 5 or Type 7 announcements.

9. The method as recited in claim 8, wherein when the sweeping locates a third router, the method further comprises:

communicating with the third router;

querying a third link state database of the third router for third Type 1 and Type 2 link state advertisements in a third area; and

importing the third Type 1 and Type 2 link state advertisements into the network typology information database.

10. A method for determining a topology of a network, the method comprising:

communicating with a first router in the network;

querying a first link state database of the first router for first Type 1 and Type 2 link state advertisements in a first area;

importing the first Type 1 and Type 2 link state advertisements into a network topology information database;

querying the first router for a first area identifier;

determining whether the first router is an autonomous system boundary router based on the first area identifier; and

when the first router is an autonomous system boundary router, querying the first router for networks directly connected to the first router and ignoring all other Type 5 announcements in the first link state database.

11. The method as recited in claim 10, further comprising:

parsing the first link state database for a second router in the first area having a second link state database and providing Type 3, Type 4 or Type 5 announcements in the first area;

communicating with the second router;

when the second router is in a second area,

querying the second link state database of the second router for second Type 1 and Type 2 link state advertisements in the second area, and

importing the second Type 1 and Type 2 link state advertisements into the network topology information database;

querying the second router for a second area identifier;

determining whether the second router is an autonomous system boundary router based on the second area identifier; and

when the second router is an autonomous system boundary router, querying the second router for networks directly connected to the second router and ignoring all other Type 5 announcements in the second link state database.

12. The method as recited in claim 10, further comprising:

parsing the first link state database for a second router in the first area having a second link state database and providing Type 3, Type 4 or Type 5 announcements in the first area;

communicating with the second router;

when the second router is in a second area,

querying the second link state database of the second router for second Type 1 and Type 2 link state advertisements in the second area, and

importing the second Type 1 and Type 2 link state advertisements into the network topology information database;

querying the second router for a second area identifier;

determining whether the second router is an area border router based on the second area identifier; and

when the second router is an area border router, querying the second router for other areas bordered by the second router, and

importing topologies of the networks in the other areas into the network topology information database.

13. A method for determining a topology of a network, the method comprising:

communicating with a first router in the network;

querying a first link state database of the first router for first Type 1 and Type 2 link state advertisements in a first area;

importing the first Type 1 and Type 2 link state advertisements into a first network topology information database;

querying the first router for a first area identifier;

determining whether the first router is an area border router based on the first area identifier; and

when the first router is an area border router, querying the first router for other areas bordered by the first router, and

importing topologies of the networks in the other areas into the network topology information database.

14. The method as recited in claim 13, further comprising:

parsing the first link state database for a second router in the first area having a second link state database and providing Type 3, Type 4 or Type 5 announcements in the first area;

communicating with the second router;

when the second router is in a second area,

querying the second link state database of the second router for second Type 1 and Type 2 link state advertisements in the second area, and

importing the second Type 1 and Type 2 link state advertisements into the second network topology information database;

querying the second router for a second area identifier;

determining whether the second router is an area border router based on the second area identifier;

determining whether the second router is an autonomous system boundary router based on the second area identifier;

when the second router is an autonomous system boundary router, querying the second router for networks directly connected to the first router and ignoring all other Type 5 announcements in the second link state database.

15. The method as recited in claim 13, further comprising:

parsing the first link state database for a second router in the first area having a second link state database and providing Type 3, Type 4 or Type 5 announcements in the first area;

communicating with the second router;

when the second router is in a second area,

querying the second link state database of the second router for second Type 1 and Type 2 link state advertisements in the second area, and

importing the second Type 1 and Type 2 link state advertisements into the network topology information database;

querying the second router for a second area identifier;

determining whether the second router is an autonomous system boundary router based on the second area identifier; and

when the second router is an autonomous system boundary router, querying the second router for networks directly connected to the second router and ignoring all other Type 5 announcements in the second link state database.