rfc1187.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.


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: [phone]
   EMail: [e-mail]


   Keith McCloghrie
   Hughes LAN Systems
   1225 Charleston Road
   Mountain View, CA 94043

   Phone: [phone]
   EMail: [e-mail]


   James R. Davin
   MIT Laboratory for Computer Science, NE43-507
   545 Technology Square
   Cambridge, MA 02139

   Phone:  [phone]
   EMail:  [e-mail]





Rose, McCloghrie & Davin                                       [Page 12]