Method and apparatus for fetching sparsely indexed MIB tables in managed network systems

[0002] 1. Field of the Invention

[0003] The present invention relates generally to communication systems and more particularly to networks having managed devices.

[0004] 2. Description of the Related Art

[0005] The following description is concerned with a data communications system such as a local area network (LAN), that is an Ethernet network. However, the skilled person will appreciate that the present invention will have more general applicability to other types of managed communications systems including wireless networks.

[0006] A local area network (LAN) typically comprises a plurality of computers, computer systems, workstations and other electronic devices connected together by a common media such as twisted pair or coaxial cable or fibre optic cable. Data can be communicated between devices on the network by means of data packets (or frames) in accordance with a predefined protocol.

[0007] Computers and other devices connected to a network can be managed or unmanaged devices. A managed device has processing capability which enables it to monitor data traffic sent from, received at, and passing through the ports of the device. Monitored data associated with the ports oft he network device is stored in memory on the network device.

[0008] Network devices typically represent data in the form of a MIB (Management Information Base), as is well known in the art. A typical managed device may implement a number of MIBs (defined in RFCs), of which one (or more) represents data used in network management, as described below.

[0009] An example of a MIB containing network management data is MIB-II (formerly MIB-I) as specified by the IETF (Internet Engineering Task Force). MIB-II is common to core managed network devices of most vendors. Another MIB containing more complex management data is RMON (Remote Monitoring). As is well known in the art, each class or type of management information represented in a MIB is called an “object”. A specific instance from a data object is called an “object instance”. An object may be defined to have one instance (a scalar object), or multiple instances (a columnar object). Columnar objects are typically organised into “conceptual tables” (hereinafter referred to as “tables”) and all the objects in a table use the same indexing scheme for identifying instances of that object. Thus, tables can be thought of as an array of rows and columns, each column comprising all instances of a particular object and each row comprising the instances of all objects at a common index (the index for the row).

[0010] It is becoming increasingly common and necessary for an individual to be appointed to manage a network. The appointed network manager (or administrator) utilises a network management station which includes network management hardware and software. In particular, the network management station is able to access management data from managed network devices using an appropriate management protocol (e.g. the SNMP protocol) and display this data for use by the network manager.

[0011] The SNMP (Simple Network Management Protocol) defines the procedure and data packet format for the network management station to access network data from MIBs in managed network devices for TCP/IP-based networks. In SNMP the data packet or PDU (Protocol Data Unit) is defined to have a size of 1500 bytes. The SNMP protocol utilises five main commands: GET, SET, GETNEXT, GETRESPONSE and TRAP.

[0012] The GET request is sent by the network management station to a network device to fetch a value of an object or objects from a MIB. The GET request specifies an object using a unique “object identifier” which is defined in the MIB, which includes an index to identify the required instance of the object.

[0013] The SET request is sent by the network management station to write a value to a MIB. Like the GET request, the SET request specifies an object identifier of the object whose value should be modified and additionally specifies the new value to be written to the object.

[0014] The GETNEXT request, an example of an approximation operation as explained below, is used by the network management station to inter alia fetch object data in MIB tables. The network management station can use the GETNEXT command to fetch the data in a complete MIB table or a part thereof without knowing, in advance, the index values of data stored in the MOB table or part thereof. For example, the network management station will initially send a GETNEXT request specifying the “table root”. The table root can be thought of as the “column titles” since it is a placeholder after which the first row in the table, that is the row having the lowest index value, is guaranteed to appear. Thus, a GETNEXT request specifying the table root retrieves the first row in the table. The network management station will then use the response to this request in the subsequent GETNEXT command to fetch the next row in the table. The network management station will continue to iterate using the GETNEXT command until the data for all the rows in the relevant MIB table have been fetched.

[0015] Thus, because the GETNEXT command is an approximation operation, it does not need to specify the exact index of the object instance to be fetched at each command, as is necessary for the GET and SET commands, but merely an approximation of the index.

[0016] If a MIB table is indexed systematically with all indices within a bounded range present, for example 1 to 10, the network management station can issue a direct SNMP GET request for the values in the indexed rows and can pack the maximum number of requests into a single SNMP data packet (1500 bytes for an SNMP PDU) for transmission to the network device. However, if the table index values are sparse, then in the prior art the management station has no choice but to fetch the rows using the GETNEXT command. Because each GETNEXT request uses the response from the previous request, the management station can only fetch one row at a time, since it must wait for the information (i.e. the index value) contained in the response of the previous request before it can formulate the next request (i.e. using the index value as the approximation).

[0017] By way of example, a simple MIB table is represented in Table 1 below.

[0018] 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).

[0019] 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:

[0020] 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.

[0021] 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.

[0022] It would be desirable to provide a method and apparatus for fetching sparsely indexed MIB tables in a more efficient manner.

[0023] 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.

[0024] 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.

[0025] An embodiment oft he present invention will now be described, by way of example, with reference to the accompanying drawings, in which:

[0026] FIGS. 1a, 1band 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.

[0027] 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.

[0028] 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.

[0029] 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.

[0030] 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).

[0031] Each seed value after the first (which is always root) can be represented by the formula:

[0032] seed value n=(n−1) (max index/max varbind)  (equation 1)

[0033] 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.

[0034] 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.

[0035] 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.

[0036] The process is repeated until all possible index values have been retrieved.

[0037] 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.

[0038] 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.

[0039] 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.

[0040] 1. The initial request uses the speculative seed values calculated using equation 1.

[0041] 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.

[0042] 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.

[0043] 4. The fourth request continues with the first thread.

[0044] 5. And again.

[0045] 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.

[0046] 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.

[0047] 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.

[0048] 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.

[0049] 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.

[0050] If the response returns data at the same local Indices values as predicted, the prediction was correct.

[0051] 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.

[0052] 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.

[0053] 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.

[0054] 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.

[0055] 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:

[0056] 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.

[0057] 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:

[0058] 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.

[0059] 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:

[0060] 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.

[0061] 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.

[0062] The computer program steps of the preferred embodiment of the present invention as described above are illustrated in the flow chart of FIGS. 1a, 1band 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.

[0063] 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.

[0064] 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.

[0065] 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.

[0066] In step 114, the program receives a response to the data packet and stores the index values of the retrieved data in memory.

[0067] 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.

[0068] 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.

[0069] 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.

[0070] The program continues by returning to step 114.

[0071] 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.

[0072] 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.

[0073] 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.

[0074] 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.