rtt.c revision 269257
1228753Smm/* 2228753Smm * util/rtt.c - UDP round trip time estimator for resend timeouts. 3228753Smm * 4228753Smm * Copyright (c) 2007, NLnet Labs. All rights reserved. 5228753Smm * 6228753Smm * This software is open source. 7228753Smm * 8228753Smm * Redistribution and use in source and binary forms, with or without 9228753Smm * modification, are permitted provided that the following conditions 10228753Smm * are met: 11228753Smm * 12228753Smm * Redistributions of source code must retain the above copyright notice, 13228753Smm * this list of conditions and the following disclaimer. 14228753Smm * 15228753Smm * Redistributions in binary form must reproduce the above copyright notice, 16228753Smm * this list of conditions and the following disclaimer in the documentation 17228753Smm * and/or other materials provided with the distribution. 18228753Smm * 19228753Smm * Neither the name of the NLNET LABS nor the names of its contributors may 20228753Smm * be used to endorse or promote products derived from this software without 21228753Smm * specific prior written permission. 22228753Smm * 23228753Smm * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24228753Smm * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25228753Smm * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26228753Smm * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27228763Smm * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28228753Smm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29228753Smm * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30228753Smm * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31228753Smm * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32228753Smm * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33228753Smm * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34228753Smm */ 35232153Smm 36232153Smm/** 37232153Smm * \file 38228753Smm * 39228753Smm * This file contains a data type and functions to help estimate good 40228753Smm * round trip times for UDP resend timeout values. 41228753Smm */ 42228753Smm#include "config.h" 43228753Smm#include "util/rtt.h" 44228753Smm 45228753Smm/** calculate RTO from rtt information */ 46228753Smmstatic int 47228753Smmcalc_rto(const struct rtt_info* rtt) 48228753Smm{ 49228753Smm /* From Stevens, Unix Network Programming, Vol1, 3rd ed., p.598 */ 50228753Smm int rto = rtt->srtt + 4*rtt->rttvar; 51228753Smm if(rto < RTT_MIN_TIMEOUT) 52228753Smm rto = RTT_MIN_TIMEOUT; 53228753Smm if(rto > RTT_MAX_TIMEOUT) 54228753Smm rto = RTT_MAX_TIMEOUT; 55228753Smm return rto; 56228753Smm} 57228753Smm 58228753Smmvoid 59228753Smmrtt_init(struct rtt_info* rtt) 60228753Smm{ 61228753Smm rtt->srtt = 0; 62228753Smm rtt->rttvar = 94; 63228753Smm rtt->rto = calc_rto(rtt); 64228753Smm /* default value from the book is 0 + 4*0.75 = 3 seconds */ 65228753Smm /* first RTO is 0 + 4*0.094 = 0.376 seconds */ 66228753Smm} 67228753Smm 68228753Smmint 69228753Smmrtt_timeout(const struct rtt_info* rtt) 70228753Smm{ 71228753Smm return rtt->rto; 72228753Smm} 73228753Smm 74228753Smmint 75228753Smmrtt_unclamped(const struct rtt_info* rtt) 76228753Smm{ 77228753Smm if(calc_rto(rtt) != rtt->rto) { 78228753Smm /* timeout fallback has happened */ 79228753Smm return rtt->rto; 80228753Smm } 81228753Smm /* return unclamped value */ 82228753Smm return rtt->srtt + 4*rtt->rttvar; 83232153Smm} 84232153Smm 85232153Smmvoid 86232153Smmrtt_update(struct rtt_info* rtt, int ms) 87228753Smm{ 88228753Smm int delta = ms - rtt->srtt; 89228753Smm rtt->srtt += delta / 8; /* g = 1/8 */ 90228753Smm if(delta < 0) 91228753Smm delta = -delta; /* |delta| */ 92228753Smm rtt->rttvar += (delta - rtt->rttvar) / 4; /* h = 1/4 */ 93228753Smm rtt->rto = calc_rto(rtt); 94228753Smm} 95228753Smm 96228753Smmvoid 97228753Smmrtt_lost(struct rtt_info* rtt, int orig) 98228753Smm{ 99228753Smm /* exponential backoff */ 100228753Smm 101228753Smm /* if a query succeeded and put down the rto meanwhile, ignore this */ 102228753Smm if(rtt->rto < orig) 103228753Smm return; 104228753Smm 105228753Smm /* the original rto is doubled, not the current one to make sure 106228753Smm * that the values in the cache are not increased by lots of 107228753Smm * queries simultaneously as they time out at the same time */ 108228753Smm orig *= 2; 109228753Smm if(rtt->rto <= orig) { 110228753Smm rtt->rto = orig; 111228753Smm if(rtt->rto > RTT_MAX_TIMEOUT) 112228753Smm rtt->rto = RTT_MAX_TIMEOUT; 113228753Smm } 114228753Smm} 115228753Smm 116228753Smmint rtt_notimeout(const struct rtt_info* rtt) 117228753Smm{ 118228753Smm return calc_rto(rtt); 119228753Smm} 120228753Smm