Using link state information to discover IP network topology

• US 20030043820A1
• Filed: 04/22/2002
• Published: 03/06/2003
• Est. Priority Date: 09/06/2001
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Tucker, Luke A., Minhazuddin, Muneyb, Rankine, Alastair J., Schreuder, James D., Goringe, Christopher M., Krumm-Heller, Alex M., Laveau, Stephane C., Peach, James T.
• Granted Patent: US 7,200,122 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• 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:

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

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

2. The method of claim 1, wherein the first and second sets of routers are associated with a plurality of predefined regions and wherein in the contacting step an interface associated with each of the routers in the first set is contacted.

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

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

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

6. The method of claim 1, further comprising:

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 routers and/or an interface attached thereto in the second router set.

7. The method of claim 1, wherein the network information comprises link state advertisements and further comprising:

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

8. The method of claim 1, further comprising:

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.

9. The method of claim 7, further comprising:

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, further comprising:

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

11. The method of claim 1, further comprising:

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 1, wherein the accessing step comprises:

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

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

14. The method of claim 6, further comprising:

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

15. The method of claim 1, wherein the accessing step outputs a link state advertisement table listing a plurality of link state advertisements and areas associated with link state advertisement and for each area iteratively performing the following steps:

selecting a link state advertisement associated with the selected area;

parsing the selected link state advertisement;

constructing at least one of router, interface, link, and network objects referenced in the selected link state advertisement 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 area has been considered.

16. The method of claim 15, wherein the iteratively performed steps comprise:

comparing a first link state advertisement associated with the selected area with a second link state advertisement associated with the selected area; 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.

17. The method of claim 15, wherein in the iteratively performed steps the following rule is employed:

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

18. The method of claim 15, wherein the following additional steps are performed in the iteratively performed steps:

comparing a first link state advertisement associated with a selected area with a second link state advertisement associated with a selected area; 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.

19. 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 portion of a distributed processing network;

means for contacting each of the routers in the first set of routers but not each of the other routers in the second set of routers; and

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

20. The system of claim 19, wherein the first and second sets of routers are associated with a plurality of predefined regions.

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

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

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

24. The system of claim 19, 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.

25. The system of claim 19, 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.

26. The system of claim 19, further comprising:

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.

27. The system of claim 25, 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.

28. The system of claim 19, further comprising:

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

29. The system of claim 19, 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.

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

a data collection agent configured to (a) select a first set of routers from among a larger, second set of routers in at least a portion of a distributed processing 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.

31. The system of claim 30, wherein the first and second sets of routers are associated with a plurality of predefined regions.

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

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

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

35. The system of claim 30, 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.

36. The system of claim 30, 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.

37. The system of claim 30, further comprising:

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

38. The system of claim 36, further comprising:

a data analyzing agent configured 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.

39. The system of claim 30, further comprising:

a data analyzing agent configured to processing the network information to form a listing of routers, links, and networks.

40. The system of claim 30, further comprising a data analyzing agent configured 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.