Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-07-23
2004-06-15
Channavajjala, Srirama (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S224000, C709S230000, C709S242000
Reexamination Certificate
active
06751627
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to computer network management. More specifically, the present invention relates to a method and an apparatus that facilitates accessing network management protocol tables.
2. Related Art
Network management database servers typically maintain tables related to network traffic. For example, a network management database server can maintain a table for transactions, which includes columns for virtual channel number, source Internet protocol (IP) address, destination IP address, number of packets transmitted, number of octets—8-bit bytes—transmitted, number of reverse packets transmitted, and number of reverse octets transmitted. In general, the network management database server can maintain multiple tables, wherein each table includes columns for different sets of data.
Each row within these tables contains the data, or tuple, related to an individual network connection. A network connection is identified by source IP address and destination IP address, and for connections using virtual channels, the channel number.
During operation, a monitor, for example a remote monitor (RMON), collects a tuple for each transaction on the monitored network. If the connection does not have an entry in the table, an entry is added to the table for the connection, otherwise, the existing entry is updated with respect to the number of packets and number of octets being transferred in each direction.
In order to facilitate rapidly entering data into rows within the tables, these tables are typically accessed using a hash code. A hash code is generated using the connection information—source IP address, destination IP address, and possibly the virtual channel number—and is used as an index to locate the correct row within the table. Hash code generators are well known in the art and will not be discussed further herein. The hash code points to where the tuple resides, or should reside if it is in the table. However, one consequence of using the hash code is that the entries in the table are in a random order which can create problems in performing some tasks.
Operators access these tuples using a network management protocol agent to determine the operating condition of the network. Typically, the operator requests the next row within the table. To determine the next row in the table, the system first sorts the table, and then accesses the row following the current row in the table. This procedure works well for small tables. However, as the table grows large, the time to sort the table increases. With very large tables, the sort time becomes quite large and exceeds the time between transactions on the network, thus interfering with the data collection process.
What is needed is a method and an apparatus that facilitates accessing network management protocol tables without the problems listed above.
SUMMARY
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.
In one embodiment of the present invention, 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.
In one embodiment of the present invention, the data related to the network connection includes a virtual channel identifier.
In one embodiment of the present invention, the system collects a second network management protocol tuple from the network. The system then creates a second hash index from the second network management protocol tuple. Next, the system determines if the second hash index relates to the network connection identified by the previous hash index. If the second hash index relates to the network connection identified by the previous hash index, the system updates 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 previous network management protocol tuple includes data from the second network management protocol tuple. If the second hash index does not relate to the network connection identified by the previous hash index, the system inserts the second network management protocol tuple into the network management protocol table and saves a pointer to the row indexed by the second hash index in the hash table. The system also forms a second search index using the data within the second network management protocol tuple that points to the second hash index. The system then inserts a pointer to the row indexed by the second hash index into the search tree.
In one embodiment of the present invention, the search tree is a balanced search tree, whereby the maximum search depth in one subtree of a node within the search tree differs from the maximum search depth in another subtree of the same node by no more than one.
In one embodiment of the present invention, the system receives a request to read a tuple within the network management protocol table. The system then searches the search tree for the tuple identified in the request. Next, the system locates the tuple within the network management protocol table using the search index within the search tree. The system then reads the tuple and returns the tuple in response to the request.
In one embodiment of the present invention, the system uses multiple search trees, wherein each search tree is sorted on different data within the network management protocol tuple.
REFERENCES:
patent: 5204958 (1993-04-01), Cheng et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5594899 (1997-01-01), Knudsen et al.
patent: 5917821 (1999-06-01), Gobuyan et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6032216 (2000-02-01), Schmuck et al.
patent: 6047283 (2000-04-01), Braun
patent: 6185569 (2001-02-01), East et al.
patent: 6266660 (2001-07-01), Liu et al.
patent: 6651099 (2003-11-01), Dietz et al.
patent: 6665725 (2003-12-01), Dietz et al.
patent: 2003/0023605 (2003-01-01), Sternin et al.
patent: 0621706 (1994-10-01), None
Channavajjala Srirama
Hamaty Christopher J.
Networks Associates Technology Inc.
Pham Khanh
Silicon Valley IP Group PC
LandOfFree
Method and apparatus to facilitate accessing data in network... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to facilitate accessing data in network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to facilitate accessing data in network... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3366307