Method and apparatus for fetching sparsely indexed MIB tables in managed network systems6766367Abstract A method for fetching sparsely indexed MIB tables for a managed network device using an approximation operation, such as a GetNext SNMP operation, comprises sending a plurality of operations in a first data packet at least one of the plurality of approximation operations specifying a speculative approximation. By using speculative approximations of index values of data to be fetched, it is possible to retrieve MIB table data more quickly and efficiently. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
testTable
testA (index) testB
row 1 2 6
row 2 3 13
row 3 7 9
This MIB table, called "testTable", has two columns, with object identifiers "testA" and "testB" of which "testA" is identified in the MIB as being an index for testTable. Values for testA and testB values are integer values. Thus, the value stored in the "testA" column is the value used to identify (i.e. index) the row in the table. Accordingly, the index which identifies the first row in the table is "2", the index which identifies the second row in the table is "3" and the index which identifies the third row in the table is "7". Thus, the rows of testTable are sparsely indexed as 2, 3 and 7 (instead of the systematically indexed 1, 2 and 3). To fetch the whole of testTable, the network management station will typically send a GETNEXT request for the table root which will retrieve data at the lowest index value, and will then iterate using the previous response as the request each time until all the rows have been fetched. This looks like:
GetNext request: testA testB
response: testA.2 = 2 testB.2 = 6
GetNext request: testA.2 testB.2
response: testA.3 = 3 testB.3 = 13
GetNext request: testA.3 testB.3
response: testA.7 = 7 testB.7 = 9
GetNext request: testA.7 testB.7
response: off end table off end table
<finished>
The main problem with the above described known method is that fetching of sparsely indexed MIB tables by the network management station is very slow, which causes delays and generates a lot of data traffic on the network. Furthermore, the utilisation oft he available byte space in data packets is poor. In network management, it is very common for MIBs to include sparsely indexed MIB tables due to deletions, additions and changes to rows of data which arise during the dynamic operation of a network. Thus, as demands on the network resources increase, the above problems become increasingly significant. It would be desirable to provide a method and apparatus for fetching sparsely indexed MIB tables in a more efficient manner. SUMMARY OF THE INVENTION According to a first aspect, the present invention provides a method for fetching sparsely indexed data for at least one data object in a data communications system using a communications protocol which defines a data packet format and an approximation operation, whereby the approximation operation retrieves the data object which has the closest available index value to, and which is greater than or less than, an approximation of the index value specified in the approximation operation, the method comprising sending a plurality of approximation operations in a first data packet, at least one of the plurality of approximation operations specifying a speculative approximation. By employing speculative approximations of index values of data objects to be fetched, a network management station operating in accordance with the method of the present invention can include a plurality of approximation operations in a data packet, thus improving the speed of retrieving a table of data and utilising more of the byte-space available in a data packet in comparison with the known method. BRIEF DESCRIPTION OF THE DRAWINGS An embodiment oft he present invention will now be described, by way of example, with reference to the accompanying drawings, in which: FIGS. 1a, 1b and 2 together provide a flow chart illustrating one way of programming a processor of a network management system to carry out the method of the present invention. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The following description relates to a sparsely indexed MIB table known as the protocolDistribution table in RMON 2, a MIB containing network management data. The protocolDist table is defined by RFC 2021 which is hereby incorporated by reference. The skilled person will appreciate that the apparatus and method of the present invention has general applicability and can be used in relation to other MIB tables. The protocolDist table is indexed partially by the object called the protocolDirLocalIndex object (referred to herein as "local index"). The set of values for the local index tends to remain static on a given interface of a network device. Generally, in accordance with the present invention, the network management station of the preferred embodiment attempts to fit up to the maximum number of requests into a single GetNext request data packet of standard SNMP PDU size (1500 bytes) (which maximum number can also preferably be returned on a single data packet). As is well known in the art, each individual request is known as a "varbind" and the complete set of requests in a data packet is a "varbind list". The size of each varbind depends upon the data object or objects requested, and thus the maximum possible number of request in the varbind list depends on the MIB table being fetched and is typically between 20 and 40. In the case of the protocolDist table, the maximum number of varbinds possible in a standard SNMP PDU is 32. In accordance with the preferred embodiment oft he present invention, the network management station starts with a set of up to 32 `seed` values between root (-) and 1024. The `seed` values are effectively speculative values used as approximations in GetNext requests, which predict or speculate on the index values present in the table. This set of 32 seed values are preferably based on previous requests for the same MIB table which can be used to predict the index values which will be present in subsequent requests (as will be understood from the following). However, if there are no previous requests, the seed values are taken to be the table root (-) and 31 index values at regular intervals within the expected range of index values. Thus, for the protocolDist table in which the expected index value range is 1 to 1024, the seed values will be: root, 32, 64, 96, 128 . . . 988, the interval between seed values being 32, the result of dividing the highest possible index value (max index=1024) by the number of varbinds per packet (max varbinds=32). Each seed value after the first (which is always root) can be represented by the formula: seed value n=(n-1) (max index/max varbind) (equation 1) Each seed value represents an approximation of index values falling within a range or "thread" of index values, so that the approximations are not confined to a limited part of the possible full range of index values. This is particularly advantageous for sparse tables where a plurality of approximations within a confined range could return the same object instance, which would be inefficient. Assuming a first sample (i.e. no prediction based on previous requests) the network management station sends a GetNext request data packet of 32 GetNext commands using the set of 32 seed values (-, 32, 64, 96, 128 . . . 988) and examines the response to determine the set of values to be used in the subsequent GetNext request. For example, if the response to GetNext 64 is 98, then there are no index values present in the range 65 and 96 and so no further GetNext requests are necessary for that range. However, the response to GetNext 96 would also be 98. It would still be possible for there to be index values present between 98 and 128. Therefore, a further GetNext request specifying the value 98 as the approximation needs to be included in the next data packet sent, along with any other requests within the other ranges or "threads" of 32 index values. The process is repeated until all possible index values have been retrieved. During this process, the network management station stores the indices marked as present in the MIB table for future use in prediction, as explained in more detail below. EXAMPLE 1 Initial Sample To illustrate the above process for an initial sample, assume a simplified MIB table of a maximum of thirty rows (rather than 1024 as in the protocol Dist table) with eight rows present having local indices (on the probe) of: 1 24 7 8 1116 25. For the purposes of this example, the maximum number of varBinds in a PDU is three (rather than the 32 possible varBinds for an SNMP PDU in the embodiment as described above). The first three seed values will be--, 10, 20 in accordance with the above-mentioned calculation using equation 1, where max index=30 and max varbinds=3. The first SNMP data packet sent by the network management station will thus contain the three separate requests GetNext--, GetNext 10 and GetNext 20. If all indices were present, these requests would be expected to return the index values 1, 11, 21. However, in this example, the response will contain data at the index values 1, 11 and 25. The index value in response to GetNext 20 is 25, rather than 21 since index value 21 is not present in the MIB table. The network management station stores the index values 1, 11 and 25 as present, recognising that local indices 21 to 24 are not present. In the second data packet sent by the network management station, the responses to the first request will be used as seed values i.e. 1, 11 and 25. If all indices were present, these requests would be expected to return the index values 2, 12 and 26. The seed values between 21 and 24 are not used since the network manager already knows that these requests will return 25, the same index value returned by GetNext 20. Thus the second packet contains the requests GetNext 1, GetNext 11 and GetNext 25. The response is 2, 16, --since the indices 12 to 15, and indices above 25 are not present in the MIB table. The network management station stores the index values 2 and 16 as present and recognises that indices 12 to 15 are missing and there are no further indices in the range 21 to 30. The process continues as shown in Table 2 below.
TABLE 2
predicted values for next
local Index values sample
1. request: -- 10 20
response: 1 11 25 1 11 25
2. request: 1 11 25
response: 2 16 -- 1 2 11 16 25
3. request: 2 16
response: 4 25 1 2 4 11 16 25
4. request: 4
response: 7 1 2 4 7 11 16 25
5. request: 7
response: 8 1 2 4 7 8 11 16 25
6. request: 8
response: 11 1 2 4 7 8 11 16 25
1. The initial request uses the speculative seed values calculated using equation 1. 2. The second request uses the responses from the first request to advance each request thread. The request GetNext 25 receives no response and the system therefore knows this thread (index values 20 to 30) is complete. 3. The third request uses the responses from the previous request to advance the remaining threads. The response to the request GetNext 16 is 25, which has already been retrieved. The system now knows that there are no index values present between 16 and the start of the next thread (i.e. 20), so this thread is also complete. 4. The fourth request continues with the first thread. 5. And again. 6. The response to GetNext 8 is 11, which has been already retrieved. The system now knows that there are no index values present between 8 and the start of the next thread (i.e. 10), so this thread is complete. This was the final thread, so the system now knows that the complete table has been fetched. Thus, the process in this example uses only six GetNext request data packets to retrieve the eight indexed rows of data present in the MIB table. It will be appreciated that at step 4, where possible index values between 4 and 10 are to be retrieved, an even spread of speculative seed values within the remainder of the thread could be used, as in step 1, to further reduce the time taken for retrieval. Thus, for example, in step 4 the data packet could specify GetNext 4, GetNext 6 and GetNext 8 which would return the indices 7 and 11. Only one further request, GetNext 7 would then be necessary to retrieve index 8, to complete the table. It is possible to further reduce the number of GetNext requests necessary to retrieve a MIB table by using seed values corresponding to the stored indices found to be present during previous fetches of the same MIB table. This is particularly advantageous for MIB tables in which the set of values for the local index tends to remain static, as in the present example of the local index object in the protocolDist table. Accordingly, in the preferred embodiment, for subsequent samples of a MIB table (i.e. where previous requests have been made by the network management station and the results of the local indices present stored), the network management station, uses the first thirty-two indices previously found to be present as the "predicted" values in determining seed values in the first GetNext request data packet. The seed values are thus root and the first thirty-one indices previously found to be present, so that if the indices are unchanged, approximation operations specifying these seed values will retrieve the same thirty-two indices previously retrieved. If the response returns data at the same local Indices values as predicted, the prediction was correct. However, if the response returns a higher index value than predicted, then the predicted row must be missing. The network management station considers the returned higher index and if this was the next predicted index takes no further action. The predicted indexed row has been deleted from the table and this fact is stored for future use. Alternatively, if the higher index value was not predicted, it is marked as new and stored for future use and the network management station must then consider whether any indices should be examined to fetch further rows which may have been added. If the network management station determines that another row may be present, it includes an appropriate GetNext request in the subsequent prediction. Thus, the following second GetNext request consists of any "rollover" requests and enough new predictions to make up the 32 varBinds. The set of new predictions uses any remaining indices from the previous fetch of the MIB table. The process continues until there are no "rollovers" or predictions (based on previously found indices) to process. The new set of returned localIndex values is stored and used as the seed values/predictors for future use when fetching the MIB table. It should be noted that subsequent additions and deletions in the table can be inferred by the network management station. In particular, deletions are inferred when two varBinds return the same value. Additions are inferred when a varbind returns an unpredicted object. EXAMPLE 2 Subsequent Sample #1 Based on the situation described in Example 1, the localIndices previously found in Example 1 are 1 2 4 7 8 11 16 25. These are the predicted values which are stored by the network management station for use as seed values when fetching the same MIB table. In this Example, shown in table 3:
TABLE 3
index values stored as predicted
local Index values values for next sample
request: -- 1 2
response: 1 2 4 1 2 4
request: 4 7 8
response: 7 8 11 1 2 4 7 8 11
request: 11 16 25
response: 16 25 -- 1 2 4 7 8 11 16 25
the prediction is correct; no further rows have been added to the table and there have been no deletions. The number of requests by network management station has been reduced even further to three requests, compared with six in Example 1. EXAMPLE 3 Subsequent Sample #2 Based on the situation described in Example 1, the localIndices previously found in Example 1 are 1 2 4 7 8 11 16 25. These are the predicted values which are stored by the network management station for use as seed values when fetching the same MIB table. In this Example shown in table 4:
TABLE 4
index values stored as predicted
local Index values values for next sample
request: -- 1 2
response: 1 2 4 1 2 4
request: 4 7 8
response: 7 11 11 1 2 4 7 11
request: 11 16 25
response: 16 25 -- 1 2 4 7 11 16 25
the prediction is incorrect. The index value 8 is not returned. However, since the GetNext 7 and GetNext 9 requests both returned the value 11, the network management station infers a deletion of the row at index 8. The index value 8 is not included in the predicted values stored for future use. EXAMPLE 4 Subsequent Sample #3 Based on the situation described in Example 1, the localIndices previously found in EXAMPLE 1 are 1 2 4 7 8 11 16 25. These are the predicted values which are stored by the network management station for use as seed values when fetching the same MIB table. In this Example, shown in table 5:
TABLE 5
Index values stored as predicted
local Index values values for next sample
request: -- 1 2
response: 1 2 4 1 2 4
request: 4 7 8
response: 5 8 11 1 2 4 5 8 11
request: 5 16 25
response: 7 16 25 1 2 4 5 7 8 11 16 25
request: 25
response: --
the prediction is also incorrect. The response to GetNext 4 is index value 5 which was not predicted. This value is therefore an addition which is noted and stored by the network management station. The predicted value 7 has not been returned in response to the second GetNext request and so in the third GetNext request, the network management station adds a new GetNext request GetNext 5, as a "rollover" along with the next two seed values 11 and 16 based on the prediction. Since the response to GetNext 5 is predicted value 7, the network management station recognises that there is no additional row at index value 6, adds the predicted value 7 to store and continues the process as before. The method of fetching MIB tables in accordance with the present invention is preferably implemented in network management software which may be provided in the form of a computer program. The computer program may be carried in a computer readable medium such as a disk or computer system. The computer program steps of the preferred embodiment of the present invention as described above are illustrated in the flow chart of FIGS. 1a, 1b and 2. The program examines the memory of the network management station to determine if a previous fetch of the same MIB table data has taken place and the index values found to be present stored in the memory. If the program determines that no previous request for the same MIB table data has been made, the program sequence begins with step 101 in FIG. 1a. In step 102 the program creates an initial set of speculative index values, including at least the table root and an even spread of subsequent index values up to the relevant maximum number using equation 1. The program sequence continues with steps 113 in FIG. 2. If the program determines that a previous fetch of the same MIB table data has taken place, the program sequence begins with step 104 in FIG. 1b. In step 105 the program retrieves from memory the set of index values retrieved during the previous fetch of the same MIB table. The program sequence continues with step 113 in FIG. 2. In step 113, the program sends a first data packet with a plurality of approximation operations specifying index values created in step 102 or 105. In step 114, the program receives a response to the data packet and stores the index values of the retrieved data in memory. In step 115, the program compares the index values of the retrieved data with the initial index values passed into step 112. Each index value is compared with the next highest or equal index value from the set specified in step 112. If the comparison determines in step 116 that the index values of the retrieved data are the same as the initial index values, the program continues with steps 117 to 120. If the comparison at step 116 determines that the index values of the retrieved data are not the same as the index values of the previous fetch, the program continues with steps 121 to 123, as described in more detail below. Accordingly, if the program determines at step 116 that the comparison of the index values in step 115 is the same, at step 117 the program considers whether the table is complete, and if so the program ends at step 119. Otherwise, the program continues at step 120 by sending a subsequent packet with a second plurality of approximations specifying the index values from the original set, from step 113. The program continues by returning to step 114. Alternatively, if at step 116, the comparison of the index values of the retrieved data is not the same as the initial index values, at step 121 the program determines whether the difference is due to deletion or addition of index values, or both. If at step 122 it is determined that the difference is only due to the deletion of an index value, the program continues with step 117. If at step 122 it is determined that new index values have been found, in step 123 the program sends a subsequent packet with a plurality of approximation operations, the first approximation operation specifying an approximation of the missed index values and the other approximations specifying a second plurality of approximations corresponding to index values from the original set, from step 113. The program then continues with step 114. It will be appreciated from the above description that the method of fetching MIB table data in accordance with the present invention has various applications. Furthermore, it will be understood that the foregoing description is specific to the retrieval of network management data in accordance with the SNMP network management protocol. However, the present invention may be used in other communications protocols, and is not restricted to the particular approximation operation described (ie the GetNext request). For instance, the data may be retrieved from the highest index value to the lowest index value using an approximation operation which retrieves data at the next index value less that the specified approximation of the index value. The present invention is not limited to the described embodiments but rather includes all such modifications and variations which fall within the scope of the invention as defined in the accompanying claims.
|
Same subclass Same class Consider this |
||||||||||