Method and system for determining network characteristics using routing protocols

• US 6,744,739 B2
• Filed: 05/18/2001
• Issued: 06/01/2004
• Est. Priority Date: 05/18/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Micromuse Incorporated (International Business Machines Corporation)
• Inventors: Martin, Daniel J.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Pham, Brenda
• Application Number:
  US09/861,167
• Publication Number:
  US 20030026212A1
• Time in Patent Office: 1,110 Days
• Field of Search: 370/351, 370/389, 370/392, 370/395.3, 370/402, 370/399, 370/401, 370/408, 370/447, 370/461, 370/465, 370/469, 370/395.31, 370/254, 370/395.4, 370/386
• US Class Current: 370/254
• 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 topology of a network, the method comprising:

(a) identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

(b) retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

(c) identifying one or more second routers based upon the retrieved routing announcements and their types; and

(d) storing data representing the retrieved routing announcements and identified second router or routers in a topology database.

2. The method of claim 1, comprising querying whether the first router is a boundary router for any area serviced by the first router.

3. The method of claim 1, wherein identifying the first router comprises identifying a seed router.

4. The method of claim 1, comprising identifying one or more areas serviced by an identified second router and retrieving second routing announcements within the one or more areas serviced by the second router.

5. The method of claim 4, comprising identifying one or more third routers based upon the retrieved second routing announcements.

6. The method of claim 4, comprising storing second data representing the retrieved second routing announcements and identified third router or routers in the network topology database.

7. The method of claim 1, comprising repeating steps (b)-(d) for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved routing announcements.

8. The method of claim 1, wherein retrieving routing announcements comprises retrieving link state advertisements (LSAs).

9. The method of claim 8, wherein retrieving routing announcements comprises separately retrieving LSAs of different types.

10. The method of claim 9, wherein retrieving routing announcements comprises first retrieving LSAs of type 1 and type 2 for any area serviced by the first router and then retrieving LSAs of other types.

11. The method of claim 10, wherein retrieving LSAs of other types comprises retrieving LSAs of types 3, 4, 5, or 7.

12. The method of claim 1, comprising drawing a map of the network using the IGP topology in the topology database and displaying the map on a display device.

13. The method of claim 1, comprising retrieving external gateway protocol (EGP) data and storing the retrieved EGP data in the topology database.

14. The method of claim 13, wherein retrieving the EGP data comprises establishing a peer relationship with an EGP speaking router in the network and loading the EGP database from the EGP speaking router.

15. The method of claim 13, comprising drawing a map of the network using the IGP and EGP topology in the topology database and displaying the map on a display device.

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

obtaining internal gateway protocol data from one or more routers through routing announcements stored in the routers;

obtaining external gateway protocol data from a router; and

determining the network topology using the internal and external gateway protocol data.

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

(a) identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

(b) retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements comprising link state advertisements (LSAs) each having one of a plurality of LSA types;

(c) identifying one or more second routers based upon the retrieved LSAs and their types;

(d) storing data representing the retrieved LSAs and identified second router or routers in a topology database; and

repeating steps (b)-(d) for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved LSAs.

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

identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types;

storing data representing the retrieved routing announcements and identified second router or routers in a topology database; and

querying whether the first router is a boundary router for any area serviced by the first router.

19. The method of claim 18, wherein identifying the first router comprises identifying a seed router.

20. The method of claim 18, comprising identifying one or more areas serviced by an identified second router and retrieving second routing announcements within the one or more areas serviced by the second router.

21. The method of claim 20, comprising identifying one or more third routers based upon the retrieved second routing announcements.

22. The method of claim 20, comprising storing second data representing the retrieved second routing announcements and identified third router or routers in the network topology database.

23. The method of claim 18, comprising repeating the steps of retrieving IGP routing announcements, identifying one or more second routers, and storing data, for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved routing announcements.

24. The method of claim 18, wherein retrieving routing announcements comprises retrieving link state advertisements (LSAs).

25. The method of claim 24, wherein retrieving routing announcements comprises separately retrieving LSAs of different types.

26. The method of claim 25, wherein retrieving routing announcements comprises first retrieving LSAs of type 1 and type 2 for any area serviced by the first router and then retrieving LSAs of other types.

27. The method of claim 26, wherein retrieving LSAs of other types comprises retrieving LSAs of types 3, 4, 5, or 7.

28. The method of claim 18, comprising drawing a map of the network using the IGP topology in the topology database and displaying the map on a display device.

29. The method of claim 18, comprising retrieving external gateway protocol (EGP) data and storing the retrieved EGP data in the topology database.

30. The method of claim 29, wherein retrieving the EGP data comprises establishing a peer relationship with an EGP speaking router in the network and loading the EGP database from the EGP speaking router.

31. The method of claim 29, comprising drawing a map of the network using the IGP and EGP topology in the topology database and displaying the map on a display device.

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

identifying a seed router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types; and

storing data representing the retrieved routing announcements and identified second router or routers in a topology database.

33. The method of claim 32, comprising querying whether the first router is a boundary router for any area serviced by the first router.

34. The method of claim 32, comprising identifying one or more areas serviced by an identified second router and retrieving second routing announcements within the one or more areas serviced by the second router.

35. The method of claim 34, comprising identifying one or more third routers based upon the retrieved second routing announcements.

36. The method of claim 34, comprising storing second data representing the retrieved second routing announcements and identified third router or routers in the network topology database.

37. The method of claim 32, comprising repeating the steps of retrieving IGP routing announcements, identifying one or more second routers, and storing data, for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved routing announcements.

38. The method of claim 32, wherein retrieving routing announcements comprises retrieving link state advertisements (LSAs).

39. The method of claim 38, wherein retrieving routing announcements comprises separately retrieving LSAs of different types.

40. The method of claim 39, wherein retrieving routing announcements comprises first retrieving LSAs of type 1 and type 2 for any area serviced by the first router and then retrieving LSAs of other types.

41. The method of claim 40, wherein retrieving LSAs of other types comprises retrieving LSAs of types 3, 4, 5, or 7.

42. The method of claim 32, comprising drawing a map of the network using the IGP topology in the topology database and displaying the map on a display device.

43. The method of claim 32, comprising retrieving external gateway protocol (EGP) data and storing the retrieved EGP data in the topology database.

44. The method of claim 43, wherein retrieving the EGP data comprises establishing a peer relationship with an EGP speaking router in the network and loading the EGP database from the EGP speaking router.

45. The method of claim 43, comprising drawing a map of the network using the IGP and EGP topology in the topology database and displaying the map on a display device.

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

identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types;

storing data representing the retrieved routing announcements and identified second router or routers in a topology database; and

identifying one or more areas serviced by an identified second router and retrieving second routing announcements within the one or more areas serviced by the second router.

47. The method of claim 46, comprising identifying one or more third routers based upon the retrieved second routing announcements.

48. The method of claim 46, comprising storing second data representing the retrieved second routing announcements and identified third router or routers in the network topology database.

49. The method of claim 46, comprising querying whether the first router is a boundary router for any area serviced by the first router.

50. The method of claim 46, wherein identifying the first router comprises identifying a seed router.

51. The method of claim 46, comprising repeating the steps of retrieving IGP routing announcements, identifying one or more second routers, and storing data, for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved routing announcements.

52. The method of claim 46, wherein retrieving routing announcements comprises retrieving link state advertisements (LSAs).

53. The method of claim 52, wherein retrieving routing announcements comprises separately retrieving LSAs of different types.

54. The method of claim 53, wherein retrieving routing announcements comprises first retrieving LSAs of type 1 and type 2 for any area serviced by the first router and then retrieving LSAs of other types.

55. The method of claim 54, wherein retrieving LSAs of other types comprises retrieving LSAs of types 3, 4, 5, or 7.

56. The method of claim 46, comprising drawing a map of the network using the IGP topology in the topology database and displaying the map on a display device.

57. The method of claim 46, comprising retrieving external gateway protocol (EGP) data and storing the retrieved EGP data in the topology database.

58. The method of claim 57, wherein retrieving the EGP data comprises establishing a peer relationship with an EGP speaking router in the network and loading the EGP database from the EGP speaking router.

59. The method of claim 57, comprising drawing a map of the network using the IGP and EGP topology in the topology database and displaying the map on a display device.

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

(a) identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

(b) retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

(c) identifying one or more second routers based upon the retrieved routing announcements and their types;

(d) storing data representing the retrieved routing announcements and identified second router or routers in a topology database; and

(e) repeating steps (b)-(d) for all areas serviced by any identified router until no additional routers are identified by virtue of retrieved routing announcements.

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

identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) link state advertisements (LSAs) within the one or more areas serviced by the first router, the LSAs each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types; and

storing data representing the retrieved routing announcements and identified second router or routers in a topology database.

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

identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types;

storing data representing the retrieved routing announcements and identified second router or routers in a topology database; and

drawing a map of the network using the IGP topology in the topology database and displaying the map on a display device.

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

identifying a first router which routes data traffic in the network and one or more areas serviced by the first router;

retrieving internal gateway protocol (IGP) routing announcements within the one or more areas serviced by the first router, the routing announcements each having one of a plurality of announcement types;

identifying one or more second routers based upon the retrieved routing announcements and their types;

storing data representing the retrieved routing announcements and identified second router or routers in a topology database; and

retrieving external gateway protocol (EGP) data and storing the retrieved EGP data in the topology database.