Determination of network topology using flow-based traffic information

• US 7,864,707 B2
• Filed: 02/24/2009
• Issued: 01/04/2011
• Est. Priority Date: 02/24/2009
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Jansen, Bernhard, Dimitropoulos, Xenofontas, Massar, Jeroen, Kind, Andreas
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Rivas; Salvador E
• Application Number:
  US12/391,556
• Publication Number:
  US 20100214947A1
• Time in Patent Office: 679 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A method for determination of a network topology includes generating a list of device sets for a destination; removing any duplicate device sets from the list; creating a tree for the destination by introducing a root node into the tree; sorting the list of device sets for the destination by length; removing the shortest device set from the list; introducing a new node representing the shortest device set into the tree; determining whether a node in the tree represents a maximum length subset of the shortest device set, and in the event that a node is determined, connecting the new node to the determined node, or else connecting the new node to the root node; setting the identifier of the introduced node to a list of members of the shortest device set that are not included in the maximum length subset of the determined node.

Claims

1. A method for determination of a network topology from a set of traffic records, the method comprising:

generating, by a computer processor, a list of device sets for a destination from the set of traffic records, each device set comprising at least one network device;

removing any duplicate device sets from the list of device sets;

creating a tree for the destination using the list of device sets, wherein creating a tree comprises;

introducing a root node into the tree;

sorting the list of device sets for the destination by length;

removing the shortest device set from the list;

introducing a new node representing the shortest device set into the tree;

determining whether a node in the tree represents a maximum length subset of the shortest device set, and in the event that a node is determined, connecting the new node to the determined node, or else connecting the new node to the root node;

setting the identifier of the introduced node to a list of members of the shortest device set that are not represented in the determined node, or, in the event that the new node is connected to the root node, to a list of members of the shortest device set; and

repeating the removing the shortest device set, introducing, determining, and setting for the next shortest device set in the list, until there are no more device sets remaining for the destination.

2. The method of claim 1, further comprising assuming shortest-path destination routing and static routes to the destination during a time interval during which the traffic records are collected.

3. The method of claim 1, further comprising repeating the method of claim 1 for a plurality of destinations.

4. The method of claim 3, further comprising merging the trees created for the plurality of destinations to determine an overall network topology.

5. The method of claim 4, further comprising:

obtaining a list of source-destination observations from a network device;

building a first directed graph using a first source-destination observation from the list;

adding the first directed graph to a set of all possible graphs for the router;

building a directed graph for each subsequent source-destination observation in the list;

sequentially inserting the built directed graphs into the set of all possible graphs in the event there is no conflict between the directed graph being inserted and the set of all possible graphs;

returning the set of all possible graphs as a topology tree for the network device; and

merging the topology tree for the network device with the overall network topology.

6. The method of claim 1, wherein the set of traffic records are provided by an end-to-end flow-based traffic measurement utility.

7. The method of claim 1, wherein a traffic record comprises a source address, a destination address, and an identification of a measurement point.

8. The method of claim 7, wherein a traffic record further comprises interface information, timing information, and an actual load of a path.

9. A computer program product comprising a non-transitory computer readable storage medium containing computer code that, when executed by a computer, implements a method for determination of a network topology, wherein the method comprises:

generating a list of device sets for a destination from the set of traffic records, each device set comprising at least one network device;

removing any duplicate device sets from the list of device sets;

creating a tree for the destination using the list of device sets, wherein creating a tree comprises;

introducing a root node into the tree;

sorting the list of device sets for the destination by length;

removing the shortest device set from the list;

introducing a new node representing the shortest device set into the tree;

determining whether a node in the tree represents a maximum length subset of the shortest path, and in the event that a node is determined, connecting the new node to the determined node, or else connecting the new node to the root node;

setting the identifier of the introduced node to a list of members of the shortest device set that are not represented in the determined node, or, in the event that the new node is connected to the root node, to a list of members of the shortest device set; and

repeating the removing the shortest device set, introducing, determining, and setting for the next shortest device set in the list, until there are no more device sets remaining for the destination.

10. The computer program product of claim 9, further comprising assuming shortest-path destination routing and static routes to the destination during a time interval during which the traffic records are collected.

11. The computer program product of claim 9, further comprising repeating the method of claim 9 for a plurality of destinations.

12. The computer program product of claim 11, further comprising merging the trees created for the plurality of destinations to determine an overall network topology.

13. The computer program product of claim 12, further comprising:

obtaining a list of source-destination observations from a network device;

building a first directed graph using a first source-destination observation from the list;

adding the first directed graph to a set of all possible graphs for the network device;

building a directed graph for each subsequent source-destination observation in the list;

sequentially inserting the built directed graphs into the set of all possible graphs in the event there is no conflict between the directed graph being inserted and the set of all possible graphs;

returning the set of all possible graphs as a topology tree for the network device; and

merging the topology tree for the network device with the overall network topology.

14. The computer program product of claim 9, wherein the set of traffic records are provided by an end-to-end flow-based traffic measurement utility.

15. The computer program product of claim 9, wherein a traffic record comprises a source address, a destination address, and an identification of a measurement point.

16. The computer program product of claim 9, wherein a traffic record further comprises interface information, timing information, and an actual load of a path.

17. A network comprising:

means for generating a list of device sets for a destination from a set of traffic records, each device set comprising at least one network device;

means for removing any duplicate device sets from the list of device sets;

means for creating a tree for the destination using the list of device sets, wherein creating a tree comprises;

means for introducing a root node into the tree;

means for sorting the list of device sets for the destination by length;

means for removing the shortest device set from the list;

means for introducing a new node representing the shortest device set into the tree;

means for determining whether a node in the tree represents a maximum length subset of the shortest path, and in the event that a node is determined, connecting the new node to the determined node, or else connecting the new node to the root node;

means for setting the identifier of the introduced node to a list of members of the shortest device set that are not represented in the determined node, or, in the event that the new node is connected to the root node, to a list of members of the shortest device set; and

means for repeating the removing the shortest device set, introducing, determining, and setting for the next shortest device set in the list, until there are no more device sets remaining for the destination.

18. The network of claim 17, further comprising means for assuming shortest-path destination routing and static routes to the destination during a time interval during which the traffic records are collected.

19. The network of claim 17, further comprising means for creating a tree using a plurality of lists of device sets for a respective plurality of destinations.

20. The network of claim 19, further comprising means for merging the trees created for the plurality of destinations to determine an overall network topology.