Network monitoring using bounded memory data structures

• US 8,645,527 B1
• Filed: 07/25/2008
• Issued: 02/04/2014
• Est. Priority Date: 07/25/2007
• Status: Active Grant

• Current Assignee: Virtual Instruments Worldwide, Inc.
• Original Assignee: Xangati Incorporated (Virtana Corp.)
• Inventors: Lee, Rosanna, Pan, Xiaohong, Jagannathan, Rangaswamy, Sanders, Derek, Kakatkar, Kishor
• Primary Examiner(s): Serrao, Ranodhi
• Assistant Examiner(s): Hussain, Farrukh
• Application Number:
  US12/180,333
• Time in Patent Office: 2,020 Days
• Field of Search: 709/201, 709/205, 709/224, 709/245, 709/246
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0645 by additionally acting on or stimulating the network after receiving notifications
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A network monitoring device includes a data structure for maintaining information about endpoints involved in network flows. Each endpoint, either a source or a destination for a network flow, has information maintained in a modified binary trie, having a branch for each bit of the source or destination address, but with interior nodes having only a single child node elided. A pruning thread is given a limited amount of time for operation, with the effect that the data structure is maintained available for use except for only that limited amount of time. In the event that the pruning thread is unable to prune the entire data structure, it maintains a marker indicating where last it left off, and returns to that location in the data structure at a later pruning operation.

Claims

1. A network monitoring method, including steps of

receiving, at a flow processing engine, flow monitoring information, said flow monitoring information including information describing source addresses and destination addresses for each identified flow, said flow monitoring information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

generating a set of virtual packets for each flow in response to said flow monitoring information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow and representing at least some of said flow monitoring information;

maintaining a data structure including flow monitoring information for each source address and destination address pair, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including flow monitoring information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data;

processing that flow monitoring information using a set of reentrant concurrent threads; and

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

determining an amount of pruning that can be accomplished in a 1^st specific limited time;

when said amount accomplished is sufficient, stopping pruning until a later time; and

when said amount accomplished is not sufficient, continuing pruning for a 2^nd specific limited time.

2. A method as in claim 1, wherein

said virtual packets are responsive to a number of flow packets and a flow duration, determinable from said flow monitoring information, said virtual packets including an equal number of packets as said flow packets and an equal duration as said flow duration.

3. A method as in claim 1, wherein

said virtual packets include no payload information.

4. A method as in claim 1, wherein

said data structure includes, at each leaf node, a reference to a previous leaf node, and a reference to a later leaf node;

whereby said data structure can be traversed from a 1^st leaf node to a 2^nd leaf node without traversal of a common parent node for said 1^st leaf node and said 2^nd leaf node.

6. A method as in claim 1, wherein

said flow monitoring information is responsive to a completion of said flow.

7. A method as in claim 1, wherein

said steps of generating a set of virtual packets for each flow are responsive to a completion of said each flow.

8. A method as in claim 1, wherein

said 2^nd specific limited time differs from said 1^st specific limited time.

5. One or more processor readable storage devices having processor readable code embodied on the processor readable storage devices, said processor readable code for programming one or more processors to perform a method including steps of:

receiving flow information including information describing source addresses and destination addresses for each identified flow, said flow information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

generating a set of virtual packets for each flow in response to said flow information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow;

maintaining a data structure including flow information for each source address and destination address pair, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data; and

processing that flow information using a set of reentrant concurrent threads; and

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

determining an amount of pruning that can be accomplished in a 1st specific limited time;

when said amount accomplished is sufficient, stopping pruning until a later time; and

when said amount accomplished is not sufficient, continuing pruning for a 2^nd specific limited time.

20. A device as in claim 5, wherein

said data structure includes, at each leaf node, a reference to a previous leaf node, and a reference to a later leaf node;

whereby said data structure can be traversed from a 1^st leaf node to a 2^nd leaf node without traversal of a common parent node for said 1^st leaf node and said 2^nd leaf node.

21. A device as in claim 5, wherein

said virtual packets are responsive to a number of flow packets and a flow duration, determinable from said flow information, said virtual packets including an equal number of packets as said flow packets and an equal duration as said flow duration.

22. A device as in claim 5, wherein

said virtual packets include no payload information.

23. A device as in claim 5, wherein

said flow monitoring information is responsive to a completion of said flow.

24. A device as in claim 5, wherein

said steps of generating a set of virtual packets for each flow are responsive to a completion of said each flow.

25. A device as in claim 5, wherein

said 2^nd specific limited time differs from said 1^st specific limited time.

9. A network monitoring method, including steps of

receiving, at a flow processing engine, flow monitoring information, said flow monitoring information including information describing source addresses and destination addresses for each identified flow, said flow monitoring information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

generating a set of virtual packets for each flow in response to said flow monitoring information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow and representing at least some of said flow monitoring information;

maintaining a data structure including flow monitoring information for each source address and destination address pair, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including flow monitoring information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data;

processing that flow monitoring information using a set of reentrant concurrent threads; and

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

limiting a time duration for those steps of pruning to a specified limited time;

setting a marker to indicate where those steps of pruning were only partially completed at an end of that time duration; and

resuming those steps of pruning at a later time beginning at that marker.

10. A method as in claim 9, wherein

said virtual packets are responsive to a number of flow packets and a flow duration, determinable from said flow monitoring information, said virtual packets including an equal number of packets as said flow packets and an equal duration as said flow duration.

11. A method as in claim 9, wherein

said virtual packets include no payload information.

12. A method as in claim 9, wherein

said data structure includes, at each leaf node, a reference to a previous leaf node, and a reference to a later leaf node;

whereby said data structure can be traversed from a 1^st leaf node to a 2^nd leaf node without traversal of a common parent node for said 1^st leaf node and said 2^nd leaf node.

13. A method as in claim 9, wherein

said data structure includes, at each leaf node, a reference to a previous leaf node, and a reference to a later leaf node;

whereby said data structure can be traversed from a 1^st leaf node to a 2^nd leaf node without traversal of a common parent node for said 1^st leaf node and said 2^nd leaf node.

14. A method as in claim 9, wherein

said flow monitoring information is responsive to a completion of said flow.

15. A method as in claim 9, wherein

said steps of generating a set of virtual packets for each flow are responsive to a completion of said each flow.

16. A system comprising:

a flow processor disposed to receive flow monitoring information, said flow monitoring information including source addresses and destination addresses for each identified flow, said flow monitoring information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

a virtual packet generator, said virtual packet generator disposed to generate a set of virtual packets for each flow in response to said flow monitoring information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow and representing at least some of said flow monitoring information;

a memory coupled to the flow processor, the memory including a data structure, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including flow monitoring information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data;

wherein said memory includes instructions interpretable by a computing device to perform a method of;

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

determining an amount of pruning that can be accomplished in a 1^st specific limited time;

when said amount accomplished is sufficient, stopping pruning until a later time; and

when said amount accomplished is not sufficient, continuing pruning for a 2^nd specific limited time.

17. The system of claim 16 further comprising:

a virtual bus coupled to the flow processor through either a discovery engine, a monitoring engine, a profiling engine or a the detection engine.

18. A system as in claim 16, wherein

said flow monitoring information is responsive to a completion of said flow.

19. A system as in claim 16, wherein

said virtual packet generator is responsive to a completion of said each flow.

26. One or more processor readable storage devices having processor readable code embodied on the processor readable storage devices, said processor readable code for programming one or more processors to perform a method including steps of:

receiving flow information including information describing source addresses and destination addresses for each identified flow, said flow information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

generating a set of virtual packets for each flow in response to said flow information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow;

maintaining a data structure including flow information for each source address and destination address pair, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data; and

processing that flow information using a set of reentrant concurrent threads;

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

limiting a time duration for those steps of pruning to a specified limited time;

setting a marker to indicate where those steps of pruning were only partially completed at an end of that time duration; and

resuming those steps of pruning at a later time beginning at that marker.

27. A device as in claim 26, wherein

said virtual packets are responsive to a number of flow packets and a flow duration, determinable from said flow information, said virtual packets including an equal number of packets as said flow packets and an equal duration as said flow duration.

28. A device as in claim 26, wherein

said virtual packets include no payload information.

29. A device as in claim 26, wherein

said flow monitoring information is responsive to a completion of said flow.

30. A device as in claim 26, wherein

said steps of generating a set of virtual packets for each flow are responsive to a completion of said each flow.

31. A device as in claim 26, wherein

said 2^nd specific limited time differs from said 1^st specific limited time.

32. A system comprising:

a flow processor disposed to receive flow monitoring information, said flow monitoring information including source addresses and destination addresses for each identified flow, said flow monitoring information indicating an actual behavior for each identified flow, including a start time and an end time for said flow;

a virtual packet generator, said virtual packet generator disposed to generate a set of virtual packets for each flow in response to said flow monitoring information, said virtual packets being equally distributed over a nonzero duration including said start time and said end time for said flow and representing at least some of said flow monitoring information;

a memory coupled to the flow processor, the memory including a data structure, that data structure including a root and a set of child nodes, each child node indicating its logical distance from that root, each child node being either a leaf or an intermediate node having at least two child nodes itself, each leaf including flow monitoring information relating to an address describing its position in that data structure, that address being either a source address for a flow or a destination address for a flow;

said data structure defining one or more omitted nodes between said root and said child nodes, omitted nodes including those intermediate leaf nodes that have only one child node with data;

wherein said memory includes instructions interpretable by a computing device to perform a method of;

pruning that data structure from time to time, with the effect of that data structure being limited in size;

said steps of pruning including steps of

limiting a time duration for those steps of pruning to a specified limited time;

setting a marker to indicate where those steps of pruning were only partially completed at an end of that time duration; and

resuming those steps of pruning at a later time beginning at that marker.

33. The system of claim 32 further comprising:

a virtual bus coupled to the flow processor through either a discovery engine, a monitoring engine, a profiling engine or a the detection engine.