×

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
First Claim
Patent Images

1. A network monitoring method, including steps ofreceiving, 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 ofdetermining 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 2nd specific limited time.

View all claims
  • 11 Assignments
Timeline View
Assignment View
    ×
    ×