rtt.c revision 249140
1198092Srdivacky/* 2198092Srdivacky * util/rtt.c - UDP round trip time estimator for resend timeouts. 3198092Srdivacky * 4198092Srdivacky * Copyright (c) 2007, NLnet Labs. All rights reserved. 5198092Srdivacky * 6198092Srdivacky * This software is open source. 7198092Srdivacky * 8198092Srdivacky * Redistribution and use in source and binary forms, with or without 9198092Srdivacky * modification, are permitted provided that the following conditions 10198092Srdivacky * are met: 11198092Srdivacky * 12198092Srdivacky * Redistributions of source code must retain the above copyright notice, 13198092Srdivacky * this list of conditions and the following disclaimer. 14212904Sdim * 15276479Sdim * Redistributions in binary form must reproduce the above copyright notice, 16198092Srdivacky * this list of conditions and the following disclaimer in the documentation 17198092Srdivacky * and/or other materials provided with the distribution. 18198092Srdivacky * 19206084Srdivacky * Neither the name of the NLNET LABS nor the names of its contributors may 20203955Srdivacky * be used to endorse or promote products derived from this software without 21203955Srdivacky * specific prior written permission. 22198092Srdivacky * 23234353Sdim * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24198092Srdivacky * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25198092Srdivacky * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26198092Srdivacky * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27198092Srdivacky * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28198092Srdivacky * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29198092Srdivacky * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30198092Srdivacky * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31198092Srdivacky * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32198092Srdivacky * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33198092Srdivacky * POSSIBILITY OF SUCH DAMAGE. 34198092Srdivacky */ 35198092Srdivacky 36198092Srdivacky/** 37198092Srdivacky * \file 38280031Sdim * 39280031Sdim * This file contains a data type and functions to help estimate good 40280031Sdim * round trip times for UDP resend timeout values. 41280031Sdim */ 42280031Sdim#include "config.h" 43280031Sdim#include "util/rtt.h" 44280031Sdim#include "util/log.h" 45280031Sdim 46280031Sdim/** calculate RTO from rtt information */ 47280031Sdimstatic int 48280031Sdimcalc_rto(const struct rtt_info* rtt) 49280031Sdim{ 50280031Sdim /* From Stevens, Unix Network Programming, Vol1, 3rd ed., p.598 */ 51280031Sdim int rto = rtt->srtt + 4*rtt->rttvar; 52280031Sdim if(rto < RTT_MIN_TIMEOUT) 53280031Sdim rto = RTT_MIN_TIMEOUT; 54280031Sdim if(rto > RTT_MAX_TIMEOUT) 55280031Sdim rto = RTT_MAX_TIMEOUT; 56280031Sdim return rto; 57280031Sdim} 58280031Sdim 59280031Sdimvoid 60280031Sdimrtt_init(struct rtt_info* rtt) 61280031Sdim{ 62280031Sdim rtt->srtt = 0; 63280031Sdim rtt->rttvar = 94; 64280031Sdim rtt->rto = calc_rto(rtt); 65198092Srdivacky /* default value from the book is 0 + 4*0.75 = 3 seconds */ 66198092Srdivacky /* first RTO is 0 + 4*0.094 = 0.376 seconds */ 67198092Srdivacky} 68249423Sdim 69249423Sdimint 70249423Sdimrtt_timeout(const struct rtt_info* rtt) 71249423Sdim{ 72249423Sdim return rtt->rto; 73249423Sdim} 74249423Sdim 75249423Sdimint 76249423Sdimrtt_unclamped(const struct rtt_info* rtt) 77249423Sdim{ 78249423Sdim if(calc_rto(rtt) != rtt->rto) { 79249423Sdim /* timeout fallback has happened */ 80249423Sdim return rtt->rto; 81249423Sdim } 82198092Srdivacky /* return unclamped value */ 83249423Sdim return rtt->srtt + 4*rtt->rttvar; 84249423Sdim} 85249423Sdim 86249423Sdimvoid 87249423Sdimrtt_update(struct rtt_info* rtt, int ms) 88198092Srdivacky{ 89249423Sdim int delta = ms - rtt->srtt; 90249423Sdim rtt->srtt += delta / 8; /* g = 1/8 */ 91249423Sdim if(delta < 0) 92249423Sdim delta = -delta; /* |delta| */ 93249423Sdim rtt->rttvar += (delta - rtt->rttvar) / 4; /* h = 1/4 */ 94249423Sdim rtt->rto = calc_rto(rtt); 95249423Sdim} 96198092Srdivacky 97249423Sdimvoid 98249423Sdimrtt_lost(struct rtt_info* rtt, int orig) 99249423Sdim{ 100249423Sdim /* exponential backoff */ 101249423Sdim 102249423Sdim /* if a query succeeded and put down the rto meanwhile, ignore this */ 103249423Sdim if(rtt->rto < orig) 104249423Sdim return; 105249423Sdim 106249423Sdim /* the original rto is doubled, not the current one to make sure 107249423Sdim * that the values in the cache are not increased by lots of 108249423Sdim * queries simultaneously as they time out at the same time */ 109249423Sdim orig *= 2; 110249423Sdim if(rtt->rto <= orig) { 111249423Sdim rtt->rto = orig; 112249423Sdim if(rtt->rto > RTT_MAX_TIMEOUT) 113249423Sdim rtt->rto = RTT_MAX_TIMEOUT; 114249423Sdim } 115249423Sdim} 116249423Sdim 117198092Srdivackyint rtt_notimeout(const struct rtt_info* rtt) 118198092Srdivacky{ 119198092Srdivacky return calc_rto(rtt); 120198092Srdivacky} 121198092Srdivacky