From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc1187.txt | 675 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 675 insertions(+) create mode 100644 doc/rfc/rfc1187.txt (limited to 'doc/rfc/rfc1187.txt') diff --git a/doc/rfc/rfc1187.txt b/doc/rfc/rfc1187.txt new file mode 100644 index 0000000..aa30ac8 --- /dev/null +++ b/doc/rfc/rfc1187.txt @@ -0,0 +1,675 @@ + + + + + + +Network Working Group M. Rose +Request for Comments: 1187 Performance Systems International, Inc. + K. McCloghrie + Hughes LAN Systems + J. Davin + MIT Laboratory for Computer Science + October 1990 + + + Bulk Table Retrieval with the SNMP + +1. Status of this Memo + + This memo reports an interesting family of algorithms for bulk table + retrieval using the Simple Network Management Protocol (SNMP). This + memo describes an Experimental Protocol for the Internet community, + and requests discussion and suggestions for improvements. This memo + does not specify a standard for the Internet community. Please refer + to the current edition of the "IAB Official Protocol Standards" for + the standardization state and status of this protocol. Distribution + of this memo is unlimited. + +Table of Contents + + 1. Status of this Memo .................................. 1 + 2. Abstract ............................................. 1 + 3. Bulk Table Retrieval with the SNMP ................... 2 + 4. The Pipelined Algorithm .............................. 3 + 4.1 The Maximum Number of Active Threads ................ 4 + 4.2 Retransmissions ..................................... 4 + 4.3 Some Definitions .................................... 4 + 4.4 Top-Level ........................................... 5 + 4.5 Wait for Events ..................................... 6 + 4.6 Finding the Median between two OIDs ................. 8 + 4.7 Experience with the Pipelined Algorithm ............. 10 + 4.8 Dynamic Range of Timeout Values ..................... 10 + 4.9 Incorrect Agent Implementations ..................... 10 + 5. The Parallel Algorithm ............................... 11 + 5.1 Experience with the Parallel Algorithm .............. 11 + 6. Acknowledgements ..................................... 11 + 7. References ........................................... 12 + Security Considerations.................................. 12 + Authors' Addresses....................................... 12 + +2. Abstract + + This memo reports an interesting family of algorithms for bulk table + retrieval using the Simple Network Management Protocol (RFC 1157) [1]. + + + +Rose, McCloghrie & Davin [Page 1] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + The reader is expected to be familiar with both the Simple Network + Management Protocol and SNMP's powerful get-next operator. Please + send comments to: Marshall T. Rose . + +3. Bulk Table Retrieval with the SNMP + + Empirical evidence has shown that SNMP's powerful get-next operator is + effective for table traversal, particularly when the management + station is interested in well-defined subsets of a particular table. + There has been some concern that bulk table retrieval can not be + efficiently accomplished using the powerful get-next operator. Recent + experience suggests otherwise. + + In the simplest case, using the powerful get-next operator, one can + traverse an entire table by retrieving one object at a time. For + example, to traverse the entire ipRoutingTable, the management station + starts with: + + get-next (ipRouteDest) + + which might return + + ipRouteDest.0.0.0.0 + + The management station then continues invoking the powerful get-next + operator, using the value provided by the previous response, e.g., + + get-next (ipRouteDest.0.0.0.0) + + As this sequence continues, each column of the ipRoutingTable can be + retrieved, e.g., + + get-next (ipRouteDest.192.33.4.0) + + which might return + + ipRouteIfIndex.0.0.0.0 + + Eventually, a response is returned which is outside the table, e.g., + + get-next (ipRouteMask.192.33.4.0) + + which might return + + ipNetToMediaIfIndex.192.33.4.1 + + So, using this scheme, O(rows x columns) management operations are + required to retrieve the entire table. + + + +Rose, McCloghrie & Davin [Page 2] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + This approach is obviously sub-optimal as the powerful get-next + operator can be given several operands. Thus, the first step is to + retrieve an entire row of the table with each operation, e.g., + + get-next (ipRouteDest, ipRouteIfIndex, ..., ipRouteMask) + + which might return + + ipRouteDest.0.0.0.0 + ipRouteIfIndex.0.0.0.0 + ipRouteMask.0.0.0.0 + + The management station can then continue invoking the powerful get- + next operator, using the results of the previous operation as the + operands to the next operation. Using this scheme O(rows) management + operations are required to retrieve the entire table. + + Some have suggested that this is a weakness of the SNMP, in that + O(rows) serial operations is time-expensive. The problem with such + arguments however is that implicit emphasis on the word "serial". In + fact, there is nothing to prevent a clever management station from + invoking the powerful get-next operation several times, each with + different operands, in order to achieve parallelism and pipelining in + the network. Note that this approach requires no changes in the + SNMP, nor does it add any significant burden to the agent. + +4. The Pipelined Algorithm + + Let us now consider an algorithm for bulk table retrieval with the + SNMP. In the interests of brevity, the "pipelined algorithm" will + retrieve only a single column from the table; without loss of + generality, the pipelined algorithm can be easily extended to + retrieve all columns. + + The algorithm operates by adopting a multi-threaded approach: each + thread generates its own stream of get-next requests and processes + the resulting stream of responses. For a given thread, a request + will correspond to a different row in the table. + + Overall retrieval efficiency is improved by being able to keep + several transactions in transit, and by having the agent and + management station process transactions simultaneously. + + The algorithm will adapt itself to varying network conditions and + topologies as well as varying loads on the agent. It does this both + by varying the number of threads that are active (i.e., the number of + transactions that are being processed and in transit) and by varying + the retransmission timeout. These parameters are varied based on the + + + +Rose, McCloghrie & Davin [Page 3] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + transaction round-trip-time and on the loss/timeout of transactions. + +4.1. The Maximum Number of Active Threads + + One part of the pipelined algorithm which must be dynamic to get best + results is the determination of how many threads to have active at a + time. With only one thread active, the pipelined algorithm + degenerates to the serial algorithm mentioned earlier. With more + threads than necessary, there is a danger of overrunning the agent, + whose only recourse is to drop requests, which is wasteful. The + ideal number is just enough to have the next request arrive at the + agent, just as it finishes processing the previous request. This + obviously depends on the round-trip time, which not only varies + dynamically depending on network topology and traffic-load, but can + also be different for different tables in the same agent. + + With too few threads active, the round-trip time barely increases + with each increase in the number of active threads; with too many, + the round-trip time increases by the amount of time taken by the + agent to process one request. The number is dynamically estimated by + calculating the round-trip-time divided by the number of active + threads; whenever this value takes on a new minimum value, the limit + on the number of threads is adjusted to be the number of threads + active at the time the corresponding request was sent (plus one to + allow for loss of requests). + +4.2. Retransmissions + + When there are no gateways between the manager and agent, the + likelihood of in-order arrival of requests and responses is quite + high. At present, the decision to retransmit is based solely on the + timeout. One possible optimization is for the manager to remember + the order in which requests are sent, and correlate this to incoming + responses. If one thread receives a response before another thread + which sent an earlier request, then lossage could be assumed, and a + retransmission made immediately. + +4.3. Some Definitions + + To begin, let us define a "thread" as some state information kept in + the management station which corresponds to a portion of the table to + be retrieved. A thread has several bits of information associated + with it: + + (1) the range of SNMP request-ids which this thread can use, + along with the last request-id used; + + (2) last SNMP message sent, the number of times it has been + + + +Rose, McCloghrie & Davin [Page 4] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + (re)sent, the time it was (re)sent; + + (3) the inclusive lower-bound and exclusive upper-bound of + the object-instance for the portion of the table that + this thread will retrieve, along with the current + object-instance being used; + + (4) the number of threads which were active at the time it + was last sent; + + When a thread is created, it automatically sends a get-next message + using its inclusive lower-bound OID. Further, it is placed at the + end of the "thread queue". + + Let us also define an OID as a concrete representation of an object + identifier which contains two parts: + + (1) the number of sub-identifiers present, "nelem"; + + (2) the sub-identifiers themselves in an array, "elems", + indexed from 1 up to (and including) "nelem". + +4.4. Top-Level + + The top-level consists of starting three threads, and then entering a + loop. As long as there are existing threads, the top-level waits for + events (described next), and then acts upon the incoming messages. + For each thread which received a response, a check is made to see if + the OID of the response is greater than or equal to the exclusive + upper-bound of the thread. If so, the portion of the table + corresponding to the thread has been completely retrieved, so the + thread is destroyed. + + Otherwise, the variable bindings in the response are stored. + Following this, if a new thread should be created, then the portion + of the table corresponding to the thread is split accordingly. + Regardless, another powerful get-next operator is issued on behalf of + the thread. + + The initial starting positions (column, column.127, and column.192), + were selected to form optimal partitions for tables which are indexed + by IP addresses. The algorithm could easily be modified to choose + other partitions; however, it must be stressed that the current + choices work for any tabular object. + + pipelined_algorithm (column) + OID column; + { + + + +Rose, McCloghrie & Davin [Page 5] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + timeout ::= some initial value; + + start new thread for [column, column.127); + start new thread for [column.127, column.192); + start new thread for [column.192, column+1); + + while (threads exist) { + wait for events; + foreach (thread that has an incoming message, + examined in order from the thread queue) { + OID a; + + if (message's OID >= thread's upper-bound) { + destroy thread; + continue; + } + + store variable-bindings from message; + + if (number of simultaneous threads does NOT + exceed a maximum number + && NOT backoff + && (a ::= oid_median (message's OID, + thread's + upper-bound))) { + start new thread for [a, thread's upper-bound); + thread's upper-bound ::= a; + place thread at end of thread queue; + backoff ::= TRUE; + } + do another get-next for thread; + } + } + } + + +4.5. Wait for Events + + Waiting for events consists of waiting a small amount of time or + until at least one message is received. + + Any messages encountered are then collated with the appropriate + thread. In addition, the largest round-trip time for + request/responses is measured, and the maximum number of active + threads is calculated. + + Next, the timeout is adjusted: if no responses were received, then + the timeout is doubled; otherwise, a timeout-adjustment is calculated + + + +Rose, McCloghrie & Davin [Page 6] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + as 1.5 times the largest observed round-trip time. If the timeout- + adjustment is greater than the current timeout, the current timeout + is set to the timeout-adjustment. Otherwise, the current timeout is + averaged with the timeout-adjustment. + + Finally, if at least one thread did not receive a response, then the + thread is identified which has waited the longest. If the elapsed + time (with noise factor) since the last request (or retransmission) + is greater than the current timeout value, another retransmission is + attempted. + + wait for events () + { + backoff ::= TRUE, maxrtt ::= 0; + find the thread which has been waiting the longest + for a response; + timedelta = timeout + - time since request was sent for thread; + wait up to timedelta seconds or until some messages arrive; + + if (least one message arrived) { + discard any messages which aren't responses; + foreach (response which corresponds to a thread) { + if (the response is a duplicate) + drop it and continue; + + if (this response is for a message that was + not retransmitted) { + if (the round-trip time is larger than maxrtt) + set maxrtt to the new round-trip time; + if (round-trip time / number of active threads + < minimum previous round-trip time / number + of active threads) { + set new minimum round-trip time per number of + active threads + set new maximum number of threads + } + backoff ::= FALSE; + } + } + } + if (backoff) + double timeout; + elsif (maxrtt > 0) { + timeadjust ::= maxrtt * 3 / 2; + if (timeadjust > timeout) + timeout ::= timeadjust; backoff ::= TRUE; + else + + + +Rose, McCloghrie & Davin [Page 7] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + timeout ::= (timeout + timeadjust) / 2; + } + if (timeout exceeds some threshold) + set timeout to that threshold; + elsif (timeout is smaller than some threshold) + set timeout to that threshold; + + if (at least one thread didn't receive a response) { + find the thread which has been waiting the longest + for a response, + and determine the elapsed time since a message + was sent; + if (the elapsed time with noise is greater than timeout) { + if (the number of retransmissions for this thread + exceeds a threshold) + abort the algorithm; + retransmit the request; + backoff ::= TRUE; + } + } + } + +4.6. Finding the Median between two OIDs + + The object identifier space is neither uniform nor continuous. As + such, it is not always possible to choose an object identifier which + is lexicographically-between two arbitrary object identifiers. In + view of this, the pipelined algorithm makes a best-effort attempt. + + Starting from the beginning, each sub-identifier of the two OIDs is + scanned until a difference is encountered. At this point there are + several possible conditions: + + (1) The upper OID has run out of sub-identifiers. In this + case, either the two OIDs are are identical or the lower + OID is greater than the upper OID (an interface error), + so no OID is returned. + + (2) The lower OID has run out of sub-identifiers. In this + case, the first subsequent non-zero sub-identifier from + the upper OID is located. If no such sub-identifier is + found, then no OID exists between the lower and upper + OIDs, and no OID is returned. Otherwise, a copy of the + upper OID is made, but truncated at this non-zero + sub-identifier, which is subsequently halved, and the + resulting OID is returned. + + (3) Otherwise, a copy of the lower OID is made, but truncated + + + +Rose, McCloghrie & Davin [Page 8] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + at the point of difference. This last sub-identifier is + then set to the arithmetic mean of the difference. In + the case where the difference is only 1 (so the last + sub-identifier remains the same) then a new sub- + identifier is added, taking care to be larger than a + possible sub-identifier present in the lower OID. + Regardless, the resulting OID is returned. + + oid_median (lower, upper) + OID lower, + upper; + { + for (i ::= 1; i < upper:nelem; i++) { + if (i > lower:nelem) { + while (upper:elems[i] == 0) + if (++i > upper:nelem) + return NULL; + median ::= copy of upper; + median:nelem ::= i; + median:elems[i] ::= upper:elems[i] / 2; + + return median; + } + + if (lower:elems[i] == upper:elems[i]) + continue; + + median ::= copy of lower; + median:nelem ::= i; + median:elems[i] ::= (lower:elems[i]+upper:elems[i])/2; + if (median:elems[i] == lower:elems[i]) { + median:nelem ::= (i + 1); + if (lower:nelem < i) + median:elems[median:nelem] ::= 127; + elsif ((x ::= lower:elems[i + 1]) >= 16383) + median:elems[median:nelem] ::= x + 16383; + elsif (x >= 4095) + median:elems[median:nelem] ::= x + 4095; + elsif (x >= 1023) + median:elems[median:nelem] ::= x + 1023; + elsif (x >= 255) + median:elems[median:nelem] ::= x + 255; + else median:elems[median:nelem] ::= + (x / 2) + 128; + } + + return median; + } + + + +Rose, McCloghrie & Davin [Page 9] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + return NULL; + } + +4.7. Experience with the Pipelined Algorithm + + This pipelined algorithm has been implemented and some + experimentation has been performed. It would be premature to provide + extensive performance figures at this time, as the pipelined + algorithm is still being tuned, and is implemented only in a + prototype setting. However, on tables of size O(2500), performance + of 121 entries/second has been observed. In contrast, the serial + algorithm has performance of roughly 56 entries/second for the same + table. + +4.8. Dynamic Range of Timeout Values + + It should be noted that the pipelined algorithm takes a simplistic + approach with the timeout value: it does not maintain a history of + the value and act accordingly. + + For example, if the timeout reaches the maximum timeout limit, and + then latches for some period of time, this indicates a resource + (either the network or the agent) is saturated. Unfortunately, a + solution is difficult: an elegant approach would be to combine two + threads (but it is quite possible that no two consecutive threads + exist when this determination is made). Another approach might be to + delay the transmission for threads which are ready to issue a new + get-next operation. + + Similarly, if the timeout drops to the minimum value and subsequently + latches, more threads should be started. + +4.9. Incorrect Agent Implementations + + An interesting result is that many agents do not properly implement + the powerful get-next operator. In particular, when a get-next + request contains an operand with an arbitrarily-generated suffix, + some agent implementations will handle this improperly, and + ultimately return a result which is lexicographically less than the + operand! + + A typical cause of this is when the instance-identifier for a + columnar object is formed by a MAC or IP address, so each octet of + the address forms a sub-identifier of the instance-identifier. In + such circumstances, the incorrect agent implementations compare + against only the least significant octet of the sub-identifiers in + the operand, instead of the full value of the sub-identifiers. + + + + +Rose, McCloghrie & Davin [Page 10] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + Upon encountering such an interaction, the pipelined algorithm + implementation declares the thread dead (noting a possible gap in the + table), and continues. + +5. The Parallel Algorithm + + One interesting optimization is to view the problem in two steps: in + the first step, one column of the table is traversed to determine the + full range of instances identifiers meaningful in the table. + (Indeed, although as described above, the pipelined algorithm + retrieves a single column, the prototype implementation can retrieve + multiple columns). In the second step, additional columns can be + retrieved using the SNMP get operation, since the instance + identifiers are already known. Further, the manager can dynamically + determine how many variables can be placed in a single SNMP get + operation in order to minimize the number of requests. Of course, + since the agent's execution of the get operation is often less + expensive than execution of the powerful get-next operation, when + multiple columns are request, this two-step process requires less + execution time on the agent. + + A second algorithm can be developed, the "parallel algorithm". At + present, each thread is mapped onto a single SNMP operation. A + powerful insight is to suggest mapping several threads onto a single + SNMP operation: the manager must dynamically determine how many + variables can be placed in a single powerful get-next operation. + This has the advantage of reducing traffic, at the expense of + requiring the agent to utilize more resources for each request. + + Earlier it was noted that the serial retrieval of objects could be + viewed as a degenerate case of the pipelined algorithm, in which the + number of active threads was one. Similarly, the pipelined algorithm + is a special case of the parallel algorithm, in which the number of + threads per SNMP operation is one. + +5.1. Experience with the Parallel Algorithm + + The parallel algorithm has been implemented and some experimentation + has been performed. It would be premature to provide extensive + performance figures at this time, as the algorithm is still being + tuned, and is implemented only in a prototype setting. However, on + tables of size O(2500), performance of 320 entries/second has been + observed, a performance improvement of 571% over the serial + algorithm. + +6. Acknowledgements + + A lot of the ideas on pipelining are motivated by Van Jacobson's work + + + +Rose, McCloghrie & Davin [Page 11] + +RFC 1187 Bulk Table Retrieval with the SNMP October 1990 + + + on adaptive timers in TCP. The parallelization modifications were + originally suggested by Jeffrey D. Case. + + Finally, the comments of the following individual is acknowledged: + + Frank Kastenholz, Racal-Interlan + +7. References + + [1] Case, J., Fedor, M., Schoffstall, M., and J. Davin, Simple + Network Management Protocol (SNMP), RFC 1157, SNMP Research, + Performance Systems International, Performance Systems + International, MIT Laboratory for Computer Science, May 1990. + +Security Considerations + + Security issues are not discussed in this memo. + +Authors' Addresses + + Marshall T. Rose + PSI, Inc. + PSI California Office + P.O. Box 391776 + Mountain View, CA 94039 + + Phone: (415) 961-3380 + EMail: mrose@PSI.COM + + + Keith McCloghrie + Hughes LAN Systems + 1225 Charleston Road + Mountain View, CA 94043 + + Phone: (415) 966-7934 + EMail: KZM@HLS.COM + + + James R. Davin + MIT Laboratory for Computer Science, NE43-507 + 545 Technology Square + Cambridge, MA 02139 + + Phone: (617) 253-6020 + EMail: jrd@ptt.lcs.mit.edu + + + + + +Rose, McCloghrie & Davin [Page 12] + \ No newline at end of file -- cgit v1.2.3