Home | History | Annotate | Line # | Download | only in util 
      1 /*
      2  * util/rtt.c - UDP round trip time estimator for resend timeouts.
      3  *
      4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
      5  *
      6  * This software is open source.
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  *
     12  * Redistributions of source code must retain the above copyright notice,
     13  * this list of conditions and the following disclaimer.
     14  *
     15  * Redistributions in binary form must reproduce the above copyright notice,
     16  * this list of conditions and the following disclaimer in the documentation
     17  * and/or other materials provided with the distribution.
     18  *
     19  * Neither the name of the NLNET LABS nor the names of its contributors may
     20  * be used to endorse or promote products derived from this software without
     21  * specific prior written permission.
     22  *
     23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
     29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     34  */
     35 
     36 /**
     37  * \file
     38  *
     39  * This file contains a data type and functions to help estimate good
     40  * round trip times for UDP resend timeout values.
     41  */
     42 #include "config.h"
     43 #include "util/rtt.h"
     44 #include "iterator/iterator.h"
     45 
     46 /* overwritten by config: infra_cache_min_rtt: */
     47 int RTT_MIN_TIMEOUT = 50;
     48 /* overwritten by config: infra_cache_max_rtt: */
     49 int RTT_MAX_TIMEOUT = 120000;
     50 
     51 /** calculate RTO from rtt information */
     52 static int
     53 calc_rto(const struct rtt_info* rtt)
     54 {
     55 	/* From Stevens, Unix Network Programming, Vol1, 3rd ed., p.598 */
     56 	int rto = rtt->srtt + 4*rtt->rttvar;
     57 	if(rto < RTT_MIN_TIMEOUT)
     58 		rto = RTT_MIN_TIMEOUT;
     59 	if(rto > RTT_MAX_TIMEOUT)
     60 		rto = RTT_MAX_TIMEOUT;
     61 	return rto;
     62 }
     63 
     64 void
     65 rtt_init(struct rtt_info* rtt)
     66 {
     67 	rtt->srtt = 0;
     68 	rtt->rttvar = UNKNOWN_SERVER_NICENESS/4;
     69 	rtt->rto = calc_rto(rtt);
     70 	/* default value from the book is 0 + 4*0.75 = 3 seconds */
     71 	/* first RTO is 0 + 4*0.094 = 0.376 seconds */
     72 }
     73 
     74 int
     75 rtt_timeout(const struct rtt_info* rtt)
     76 {
     77 	return rtt->rto;
     78 }
     79 
     80 int
     81 rtt_unclamped(const struct rtt_info* rtt)
     82 {
     83 	if(calc_rto(rtt) != rtt->rto) {
     84 		/* timeout fallback has happened */
     85 		return rtt->rto;
     86 	}
     87 	/* return unclamped value */
     88 	return rtt->srtt + 4*rtt->rttvar;
     89 }
     90 
     91 void
     92 rtt_update(struct rtt_info* rtt, int ms)
     93 {
     94 	int delta = ms - rtt->srtt;
     95 	rtt->srtt += delta / 8; /* g = 1/8 */
     96 	if(delta < 0)
     97 		delta = -delta; /* |delta| */
     98 	rtt->rttvar += (delta - rtt->rttvar) / 4; /* h = 1/4 */
     99 	rtt->rto = calc_rto(rtt);
    100 }
    101 
    102 void
    103 rtt_lost(struct rtt_info* rtt, int orig)
    104 {
    105 	/* exponential backoff */
    106 
    107 	/* if a query succeeded and put down the rto meanwhile, ignore this */
    108 	if(rtt->rto < orig)
    109 		return;
    110 
    111 	/* the original rto is doubled, not the current one to make sure
    112 	 * that the values in the cache are not increased by lots of
    113 	 * queries simultaneously as they time out at the same time */
    114 	orig *= 2;
    115 	if(rtt->rto <= orig) {
    116 		rtt->rto = orig;
    117 		if(rtt->rto > RTT_MAX_TIMEOUT)
    118 			rtt->rto = RTT_MAX_TIMEOUT;
    119 	}
    120 }
    121 
    122 int rtt_notimeout(const struct rtt_info* rtt)
    123 {
    124 	return calc_rto(rtt);
    125 }
    126