Method and apparatus to facilitate accessing data in network management protocol tables

• US 6,751,627 B2
• Filed: 07/23/2001
• Issued: 06/15/2004
• Est. Priority Date: 07/23/2001
• Status: Expired due to Term

• Current Assignee: Network General Technology
• Original Assignee: Networks Associates Technology, Inc. (McAfee, LLC)
• Inventors: Sternin, Jeffrey Y.
• Primary Examiner(s): Channavajjala, Srirama
• Assistant Examiner(s): PHAM, KHANH B
• Application Number:
  US09/911,887
• Publication Number:
  US 20030018688A1
• Time in Patent Office: 1,058 Days
• Field of Search: 707/100, 707/101, 707/2, 707/3, 707/4, 707/5, 707/10, 709/224, 709/230, 709/242
• US Class Current: 709/225
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 41/022 Multivendor or multi-standard integration
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

One embodiment of the present invention provides a system that facilitates accessing a network management protocol table. The system operates by first collecting a network management protocol tuple that includes data related to a network connection. Next, the system creates a hash index from the network management protocol tuple. This network management protocol tuple is inserted into the network management protocol table. The system then saves a pointer to the row indexed by the hash index in a hash table. The system also forms a search index using data within the network management protocol tuple that identifies the data pointed to by the hash index in the hash table. This search index is inserted into a search tree, so that the hash index provides fast insertion into the network management protocol table and the search index in the search table provides fast ordered retrieval from the network management protocol table.

Claims

1. A method to facilitate accessing a network management protocol table, comprising:

collecting a network management protocol tuple, wherein the network management protocol tuple includes data related to a network connection, wherein the data related to the network connection includes a source address, a destination address, a number of packets, a number of octets, a number of reverse packets, and a number of reverse octets;

creating a hash index from the network management protocol tuple;

inserting the network management protocol tuple into the network management protocol table;

saving a pointer to a row indexed by the hash index in a hash table;

forming a search index using a datum within the network management protocol tuple, wherein the search index identifies data pointed to by the hash index in the hash table;

inserting the pointer to the row indexed by the hash index into a search tree using the search index, whereby the hash index provides fast insertion into the network management protocol table and the search index provides fast ordered retrieval from the network management protocol table;

collecting a second network management protocol tuple;

creating a second hash index from the second network management protocol tuple;

determining if the second hash index relates to the network connection identified by the hash index; and

if the second hash index relates to the network connection identified by the hash index,

updating the number of packets, the number of octets, the number of reverse packets, and the number of reverse octets in the network management protocol tuple in the network management protocol table, so that the network management protocol tuple includes data from the second network management protocol tuple, otherwise

inserting the second network management protocol tuple into the network management protocol table,

saving a pointer to the row indexed by the second hash index in the hash table,

forming a second search index using the datum within the second network management protocol tuple, wherein the second search index points to the second hash index, and

inserting the pointer to the row indexed by the second hash index into the search tree;

wherein data related to the network connection includes a virtual channel identifier.

2. The method of claim 1, wherein the search tree is a balanced search tree, whereby a maximum search depth in a first subtree of a node within the search tree differs from the maximum search depth in a second subtree of the node by no more than one.

3. The method of claim 2, further comprising

receiving a request to read a tuple within the network management protocol table;

searching the search tree for the tuple identified in the request;

locating the tuple within the network management protocol table using the search index within the search tree;

reading the tuple; and

returning the tuple in response to the request.

4. The method of claim 3, further comprising a plurality of search trees, wherein each search tree within the plurality of search trees is sorted on a different datum within the network management protocol tuple.

5. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method to facilitate accessing a network management protocol table, the method comprising:

collecting a network management protocol tuple, wherein the network management protocol tuple includes data related to a network connection, wherein the data related to the network connection includes a source address, a destination address, a number of packets, a number of octets, a number of reverse packets, and a number of reverse octets;

creating a hash index from the network management protocol tuple;

inserting the network management protocol tuple into the network management protocol table;

saving a pointer to a row indexed by the hash index in a hash table;

forming a search index using a datum within the network management protocol tuple, wherein the search index identities data pointed to by the hash index in the hash table;

inserting the pointer to the row indexed by the hash index into a search tree using the search index, whereby the hash index provides fast insertion into the network management protocol table and the search index provides fast ordered retrieval from the network management protocol table;

collecting a second network management protocol tuple;

creating a second hash index from the second network management protocol tuple;

determining if the second hash index relates to the network connection identified by the hash index; and

if the second hash index relates to the network connection identified by the hash index,

updating the number of packets, the number of octets, the number of reverse packets, and the number of reverse octets in the network management protocol tuple in the network management protocol table, so that the network management protocol tuple includes data from the second network management protocol tuple, otherwise

inserting the second network management protocol tuple into the network management protocol table,

saving a pointer to the row indexed by the second hash index in the hash table,

forming a second search index using the datum within the second network management protocol tuple, wherein the second search index points to the second hash index, and

inserting the pointer to the row indexed by the second hash index into the search tree;

wherein data related to the network connection includes a virtual channel identifier.

6. The computer-readable storage medium of claim 5, wherein the search tree is a balanced search tree, whereby a maximum search depth in a first subtree of a node within the search tree differs from the maximum search depth in a second subtree of the node by no more than one.

7. The computer-readable storage medium of claim 6, the method further comprising

receiving a request to read a tuple within the network management protocol table;

searching the search tree for the tuple identified in the request;

locating the tuple within the network management protocol table using the search index within the search tree;

reading the tuple; and

returning the tuple in response to the request.

8. The computer-readable storage medium of claim 7, the method further comprising a plurality of search trees, wherein each search tree within the plurality of search trees is sorted on a different datum within the network management protocol tuple.

9. An apparatus that facilitates accessing a network management protocol table, comprising:

a collecting mechanism that is configured to collect a network management protocol tuple, wherein the network management protocol tuple includes data related to a network connection, wherein the data related to the network connection includes a source address, a destination address, a number of packets, a number of octets, a number of reverse packets, and a number of reverse octets;

a creating mechanism that is configured to create a hash index from the network management protocol tuple;

an inserting mechanism that is configured to insert the network management protocol tuple into the network management protocol table;

a saving mechanism that is configured to save a pointer to a row indexed by the hash index in a hash table;

a forming mechanism that is configured to form a search index using a datum within the network management protocol tuple, wherein the search index identifies data pointed to by the hash index in the hash table;

a search tree insertion mechanism that is configured to insert the pointer to the row indexed by the hash index into a search tree using the search index, whereby the hash index provides fast insertion into the network management protocol table and the search index provides fast ordered retrieval from the network management protocol table;

wherein the collecting mechanism is further configured to collect a second network management protocol tuple;

wherein the creating mechanism is further configured to create a second hash index from the second network management protocol tuple;

a determining mechanism that is configured to determine if the second hash index relates to the network connection identified by the hash index; and

an updating mechanism that is configured to update the number of packets, the number of octets, the number of reverse packets, and the number of reverse octets in the network management protocol tuple in the network management protocol table, so that the network management protocol tuple includes data from the second network management protocol tuple;

wherein the inserting mechanism is further configured to insert the second network management protocol tuple into the network management protocol table;

wherein the saving mechanism is further configured to save a pointer to the row indexed by the second hash index in the hash table;

wherein the forming mechanism is further configured to form a second search index using the datum within the second network management protocol tuple, wherein the second search index points to the second hash index;

wherein the search tree insertion mechanism is further configured to insert the pointer to the row indexed by the second hash index into the search tree;

wherein data related to the network connection includes a virtual channel identifier.

10. The apparatus of claim 9, wherein the search tree is a balanced search tree, whereby a maximum search depth in a first subtree of a node within the search tree differs from the maximum search depth in a second subtree of the node by no more than one.

11. The apparatus of claim 10, further comprising

a receiving mechanism that is configured to receive a request to read a tuple within the network management protocol table;

a searching mechanism that is configured to search the search tree for the tuple identified in the request;

a locating mechanism that is configured to locate the tuple within the network management protocol table using the search index within the search tree;

a reading mechanism that is configured to read the tuple; and

a returning mechanism that is configured to return the tuple in response to the request.

12. The apparatus of claim 11, including a plurality of search trees, wherein each search tree within the plurality of search trees is sorted on a different datum within the network management protocol tuple.