Using link state information to discover IP network topology

• US 7,200,122 B2
• Filed: 04/22/2002
• Issued: 04/03/2007
• Est. Priority Date: 09/06/2001
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Laveau, Stephane C., Krumm-Heller, Alex M., Tucker, Luke A., Schreuder, James D., Rankine, Alastair J., Peach, James T., Minhazuddin, Muneyb, Goringe, Christopher M.
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US10/127,967
• Publication Number:
  US 20030043820A1
• Time in Patent Office: 1,807 Days
• Field of Search: 370/254, 370/255, 370/400, 370/401
• US Class Current: 370/255
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A system for determining a topology associated with a network such as an enterprise network. The system includes a data collection agent 204 configured to (a) identify a first set of routers from among a larger, second set of routers in an enterprise network, (b) contact each of the routers in the first set of routers but not each of the other routers in the second set of routers, and (c) load network information maintained by at least some of the contacted routers in the first set of routers. The loaded network information can then be used to form a network or routing topology of the enterprise network.

Claims

1. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

setting a flag value for each of the routers in the first set of routers, wherein the flag value depends upon the state of the contact with the associated router and/or router interface; and

generating a representation of the network topology in the selected network region based on the accessed network information.

2. The method of claim 1, wherein in the contacting step an interface associated with each of the routers in the first set is contacted and wherein the first router is not located on a boundary between adjacent network regions.

3. The method of claim 2, wherein the plurality of network regions correspond with a plurality of areas as defined by the Open Shortest Path First protocol and wherein the network is an enterprise network.

4. The method of claim 3, wherein each of the routers in the first set of routers is an area border router.

5. The method of claim 3, wherein at least some of the routers in the second set of routers are not an area border router.

6. The method of claim 1, wherein the generating step comprises:

maintaining a router table listing one or more attributes of at least one of (i) each of the routers in the first router set and (ii) one or more interfaces associated with each of the routers in the first router set and excluding one or more attributes associated with each of the other routers and/or an interface attached thereto in the second router set.

7. The method of claim 6, wherein the accessing step comprises:

setting a flag for each of the listed routers and/or interfaces indicating an outcome of the contacting step.

8. The method of claim 1, wherein the network information comprises link state advertisements and wherein the generating step comprises:

storing the link state advertisements in a link state advertisement table, wherein the link state advertisements are indexed by an associated area.

9. The method of claim 7, wherein the generating step comprises:

determining a link state advertisement type for a plurality of the link state advertisements in the link state advertisement table, wherein higher numbered link state advertisement types are processed before lower numbered link state advertisement types.

10. The method of claim 1, wherein in the generating step the representation is a listing of routers, links, interfaces, and networks.

11. The method of claim 1, wherein the generating step comprises:

discarding at least some of the information based on at least one of a type of the information and a type of link associated with the information.

12. The method of claim 11, wherein the type of link is a type of state advertisement and the type of information is an extension type associated with a link state advertisement.

13. The method of claim 11, wherein the at least one of a type of the information and a type of link is a type of the information.

14. The method of claim 11, wherein the at least one of a type of the information and a type of link is a type of link.

15. The method of claim 1, wherein the plurality of network regions comprises first network regions and second network regions and wherein the generating step comprises:

discarding network information associated with one or more selected first network regions; and

updating a listing of network information associated with one or more selected second network regions.

16. The method of claim 1, wherein the accessing step outputs a link state advertisement table listing a plurality of link state advertisements and selected network regions associated with link state advertisement and, for each selected network region, interactively performing the following steps:

selecting a link state advertisement associated with the selected network region;

parsing the selected link state advertisement;

constructing at least one of router, interface, link, and network objects referenced in the selected link state advertisement, the object containing information in the selected link state advertisement; and

repeating the selecting, parsing, and constructing steps until each link state advertisement associated with the selected network region has been considered.

17. The method of claim 16, wherein the interactively performed steps further comprise:

comparing a first link state advertisement associated with the selected network region with a second link state advertisement associated with the selected network region; and

when the first and second link state advertisements correspond to one another, constructing an interface object containing information contained in the first and second link state advertisements.

18. The method of claim 16, wherein in the interactively performed steps the following rule is employed:

where a point-to-point link having no corresponding stub network link is assumed to be unnumbered.

19. The method of claim 16, wherein the following additional steps are performed in the interactively performed steps:

comparing a first link state advertisement associated with the selected network region with a second link state advertisement associated with the selected network region; and

when the first and second link state advertisements correspond to one another, identifying at least one attribute of at least one of a router, interface, link, and network.

20. The method of claim 1, wherein, in the thereafter contacting and accessing steps, the plurality of network regions and network region topology are determined, and wherein, in the contacting step and thereafter contacting and accessing steps, signals transmitted to at least some of the contacted routers cross over a boundary between adjacent defined network regions.

21. The method of claim 1, wherein the network topology corresponds to OSI Layer 3 topology.

22. The method of claim 1, wherein the at least some of the contacted routers in the first set of routers exclude at least one router in the first set of routers because the at least one router is configured according to one or more selected routing protocols.

23. The method of claim 1, further comprising:

at least one of not contacting and not accessing network information in a router when the router is associated with an IP address that is not a member of a set of IP addresses.

24. The method of claim 1, further comprising:

at least one of not contacting and not accessing network information in a router when the router is in a network region that is not a member of a set of network regions.

25. The method of claim 1, further comprising:

querying a user whenever a Previously Presented region is discovered to determine whether or not the discovered region is of interest to the user.

26. The method of claim 1, wherein, in the generating step, virtual link information is ignored.

27. The method of claim 1, further comprising:

accessing network information from the at least some of the contacted routers in the first set of routers only when the at least some of the contacted routers use one or more selected routing protocols.

28. A system for determining a topology associated with a distributed processing network, comprising:

means for extracting a first set of routers from among a larger, second set of routers in at least a selected portion of a distributed processing network, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the first set of routers is located in a plurality of network regions, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

means for contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers, and thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers;

means for accessing network information maintained by at least some of the contacted routers in the first set of routers;

means for setting a flag value for each of the routers in the first set of routers, wherein the flag value depends upon the state of the contact with the associated router; and

means for generating a representation of the network topology in the selected portion of the distributed processing network based on the accessed network information.

29. The system of claim 28, wherein the first and second sets of routers are associated with the plurality of regions.

30. The system of claim 28, wherein the plurality of regions are a plurality of areas as defined by the Open Shortest Path First protocol.

31. The system of claim 28, wherein each of the routers in the first set of routers is an area border router.

32. The system of claim 28, wherein at least one of the routers in the second set of routers is not an area border router and wherein the first router is not an area border router.

33. The system of claim 28, further comprising:

a router table listing each of the routers in the first set of routers but not each of the routers in the second set of routers.

34. The system of claim 28, wherein the information comprises link state advertisements and further comprising:

means for storing the link state advertisements in a link state advertisement table, wherein the link state advertisements are indexed by an associated area.

35. The system of claim 34, further comprising:

means for determining a link state advertisement type for a plurality of the link state advertisements in the link state advertisement table, wherein higher numbered link state advertisement types are processed before lower numbered link state advertisement types.

36. The system of claim 28, further comprising:

means for processing the information to form a listing of routers, links, and networks.

37. The system of claim 28, further comprising:

filtering means for discarding at least some of the information based on at least one of a type of the information and a type of link associated with the information.

38. The system of claim 37, wherein the at least one of a type of the information and a type of link is a type of the information.

39. The system of claim 37, wherein the at least some of the information based on at least one of a type of the information and a type of link associated with the information is a type of link.

40. The system of claim 28, wherein the means for contacting transmits signals to at least some of the contacted routers across a boundary between adjacent defined network areas when the means for contacting and means for accessing determine the network regions and topology in each network region.

41. The system of claim 28, wherein the network topology corresponds to OSI Layer 3 topology.

42. A system for determining a topology associated with a distributed processing network, comprising:

a data collection agent to (a) select a first set of routers from among a larger, second set of routers in at least a selected portion of a distributed processing network, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the first set of routers are located in a plurality of network regions, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol, (b) contact a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers, and thereafter contact each of the routers in the first set of routers but not each of the other routers in the second set of routers, and (c)load network information maintained by at least some of the contacted routers in the first set of routers;

a flag value associated with each of the routers in the first set of routers, wherein the flag value depends upon the state of the contact with the associated router; and

a data analyzing agent for generating a representation of the network topology of the selected portion of the distributed processing network based on the loaded network information.

43. The system of claim 42, wherein the first and second sets of routers are associated with the plurality of regions and wherein the first router is not located on a boundary between adjacent network regions.

44. The system of claim 43, wherein the plurality of regions are a plurality of areas as defined by the Open Shortest Path First protocol.

45. The system of claim 42, wherein each of the routers in the first set of routers is an area border router.

46. The system of claim 42, wherein at least one of the routers in the second set of routers is not an area border router.

47. The system of claim 42, further comprising:

a router table listing each of the routers in the first set of routers but not each of the other routers in the second set of routers.

48. The system of claim 42, wherein the information comprises link state advertisements and further comprising:

a link state advertisement table containing a plurality of link state advertisements indexed by an associated area.

49. The system of claim 48, wherein the data analyzing agent is further operable to determine a link state advertisement type for a plurality of the link state advertisements in the link state advertisement table, wherein higher numbered link state advertisement types are processed before lower numbered link state advertisement types, and process each of the link state advertisements based on the determined link state advertisement type.

50. The system of claim 42, wherein the data analyzing agent is further operable to process the network information to form a listing of routers, links, and networks.

51. The system of claim 42, wherein the data analyzing agent is further operable to process the network information and output a network model and wherein at least one of the data collection and data analyzing agents is configured to discard at least some of the information based on at least one of a type of the information and a type of link associated with the information.

52. The system of claim 51, wherein the at least one of a type of the information and a type of link associated with the information is a type of the information.

53. The system of claim 51, wherein the at least one of a type of the information and a type of link associated with the information is a type link.

54. The system of claim 42, wherein the data collection agent transmits signals to at least some of the contacted routers across a boundary between adjacent defined network regions when the data collection agent determines the network regions and topology in each network region.

55. The system of claim 42, wherein the network topology corresponds to OSI Layer 3 topology.

56. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

generating a representation of the network topology in the selected network region based on the accessed network information;

maintaining a router table listing one or more attributes of at least one of (i) each of the routers in the first router set and (ii) one or more interfaces associated with each of the routers in the first router set and excluding one or more attributes associated with each of the other routers and/or an interface attached thereto in the second router set; and

setting a flag for each of the listed routers and/or interfaces indicating an outcome of the contacting step.

57. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers, wherein the network information comprises link state advertisements;

generating a representation of the network topology in the selected network region based on the accessed network information;

storing the link state advertisements in a link state advertisement table, wherein the link state advertisements are indexed by an associated area; and

determining a link state advertisement type for a plurality of the link state advertisements in the link state advertisement table, wherein higher numbered link state advertisement types are processed before lower numbered link state advertisement types.

58. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers, wherein the network information comprises link state advertisements;

wherein the accessing step outputs a link state advertisement table listing a plurality of link state advertisements and selected network regions associated with link state advertisement and, for each selected network region, interactively performing the following steps according to a rule stating where a point-to-point link has no corresponding stub network link the point-to-point link is assumed to be unnumbered;

(i) selecting a link state advertisement associated with the selected network region;

(ii) parsing the selected link state advertisement;

(iii) constructing at least one of router, interface, link, and network objects referenced in the selected link state advertisement, the object containing information in the selected link state advertisement;

(iv) repeating the selecting, parsing, and constructing steps until each link state advertisement associated with the selected network region has been considered; and

generating a representation of the network topology in the selected network region based on the accessed network information.

59. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers, wherein the at least some of the contacted routers in the first set of routers exclude at least one router in the first set of routers because the at least one router is configured according to one or more selected routing protocols;

accessing network information maintained by at least some of the contacted routers in the first set of routers; and

generating a representation of the network topology in the selected network region based on the accessed network information.

60. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

at least one of not contacting and not accessing network information in a router when the router is associated with an IP address that is not a member of a set of IP addresses; and

generating a representation of the network topology in the selected network region based on the accessed network information.

61. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

generating a representation of the network topology in the selected network region based on the accessed network information; and

querying a user whenever a Previously Presented region is discovered to determine whether or not the discovered region is of interest to the user.

62. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

generating a representation of the network topology in the selected network region based on the accessed network information, wherein virtual link information is ignored.

63. A method for determining a topology associated with a distributed processing network, comprising:

selecting a network region from among a plurality of network regions, the network region containing first and second sets of routers, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol;

contacting a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers;

thereafter contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers, the first set of routers having fewer members than the second set of routers;

accessing network information maintained by at least some of the contacted routers in the first set of routers;

accessing network information from the at least some of the contacted routers in the first set of routers only when the at least some of the contacted routers use one or more selected routing protocols; and

generating a representation of the network topology in the selected network region based on the accessed network information.

64. A system for determining a topology associated with a distributed processing network, comprising:

a data collection agent to (a) select a first set of routers from among a larger, second set of routers in at least a selected portion of a distributed processing network, wherein the routers in the first set of routers are also members of the second set of routers, wherein the second set of routers comprises routers that are not in the first set of routers, wherein the first set of routers are located in a plurality of network regions, wherein the plurality of network regions are defined by at least one routing protocol, and wherein at least two of the network regions are defined by a common routing protocol, (b) contact a first router in the second set of routers to determine at least one of the routers in the first set of routers, the first router not being in the first set of routers, and thereafter contact each of the routers in the first set of routers but not each of the other routers in the second set of routers, and (c) load network information maintained by at least some of the contacted routers in the first set of routers, wherein the loaded network information comprises link state advertisements;

a link state advertisement table containing a plurality of link state advertisements indexed by an associated area; and

a data analyzing agent for generating a representation of the network topology of the selected portion of the distributed processing network based on the loaded network information and determining a link state advertisement type for a plurality of the link state advertisements in the link state advertisement table, wherein higher numbered link state advertisement types are processed before lower numbered link state advertisement types, and process each of the link state advertisements based on the determined link state advertisement type.