From f060064e388f5d3bced31d44abf8c2c5eec7197d Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Mon, 14 May 2007 13:22:02 +0000 Subject: [PATCH] timeout estimation code. git-svn-id: file:///svn/unbound/trunk@317 be551aaa-1e26-0410-a405-d3ace91eadb9 --- doc/Changelog | 1 + testcode/checklocks.c | 3 +- testcode/unitmain.c | 25 ++++++++++++ util/rtt.c | 92 +++++++++++++++++++++++++++++++++++++++++++ util/rtt.h | 89 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 209 insertions(+), 1 deletion(-) create mode 100644 util/rtt.c create mode 100644 util/rtt.h diff --git a/doc/Changelog b/doc/Changelog index daa586b22..347ad94d8 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -1,6 +1,7 @@ 14 May 2007: Wouter - Port to OS/X and Dec Alpha. Printf format and alignment fixes. - extensive lock debug report on join timeout. + - proper RTT calculation, in utility code. 11 May 2007: Wouter - iterator/iterator.c module. diff --git a/testcode/checklocks.c b/testcode/checklocks.c index 77e5a7901..61996227e 100644 --- a/testcode/checklocks.c +++ b/testcode/checklocks.c @@ -756,7 +756,8 @@ thread_debug_info(struct thr_check* thr) (thr->arg?*(int*)thr->arg:0)); log_info("thread num is %d", thr->num); log_info("locks created %d", thr->locks_created); - log_info("FILE for lockinfo: %x. flushing.", (int)thr->order_info); + log_info("open file for lockinfo: %s", + thr->order_info?"yes, flushing":"no"); fflush(thr->order_info); w = thr->waiting; f = thr->holding_first; diff --git a/testcode/unitmain.c b/testcode/unitmain.c index d8a28e0ad..82041d0e3 100644 --- a/testcode/unitmain.c +++ b/testcode/unitmain.c @@ -119,6 +119,30 @@ net_test() unit_assert( !is_pow2(259) ); } +#include "util/rtt.h" +/** test RTT code */ +static void +rtt_test() +{ + int i; + struct rtt_info r; + rtt_init(&r); + /* initial value sensible */ + unit_assert( rtt_timeout(&r) == 3000 ); + rtt_lost(&r); + unit_assert( rtt_timeout(&r) == 6000 ); + rtt_lost(&r); + unit_assert( rtt_timeout(&r) == 12000 ); + rtt_update(&r, 4000); + unit_assert( rtt_timeout(&r) >= 5000 ); + rtt_lost(&r); + for(i=0; i<100; i++) { + rtt_lost(&r); + unit_assert( rtt_timeout(&r) > RTT_MIN_TIMEOUT-1); + unit_assert( rtt_timeout(&r) < RTT_MAX_TIMEOUT+1); + } +} + /** * Main unit test program. Setup, teardown and report errors. * @param argc: arg count. @@ -137,6 +161,7 @@ main(int argc, char* argv[]) checklock_start(); net_test(); dname_test(); + rtt_test(); alloc_test(); lruhash_test(); slabhash_test(); diff --git a/util/rtt.c b/util/rtt.c new file mode 100644 index 000000000..3cf1986ab --- /dev/null +++ b/util/rtt.c @@ -0,0 +1,92 @@ +/* + * util/rtt.c - UDP round trip time estimator for resend timeouts. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * + * This file contains a data type and functions to help estimate good + * round trip times for UDP resend timeout values. + */ +#include "config.h" +#include "util/rtt.h" +#include "util/log.h" + +/** calculate RTO from rtt information */ +static int +calc_rto(const struct rtt_info* rtt) +{ + /* From Stevens, Unix Network Programming, p.598 */ + int rto = rtt->srtt + 4*rtt->rttvar; + if(rto < RTT_MIN_TIMEOUT) + rto = RTT_MIN_TIMEOUT; + if(rto > RTT_MAX_TIMEOUT) + rto = RTT_MAX_TIMEOUT; + return rto; +} + +void +rtt_init(struct rtt_info* rtt) +{ + rtt->srtt = 0; + rtt->rttvar = 750; + rtt->rto = calc_rto(rtt); + /* first RTO is 0 + 4*0.75 = 3 seconds */ +} + +int +rtt_timeout(const struct rtt_info* rtt) +{ + return rtt->rto; +} + +void +rtt_update(struct rtt_info* rtt, int ms) +{ + int delta = ms - rtt->srtt; + rtt->srtt += delta / 8; /* g = 1/8 */ + if(delta < 0) + delta = -delta; /* |delta| */ + rtt->rttvar += (delta - rtt->rttvar) / 4; /* h = 1/4 */ + rtt->rto = calc_rto(rtt); +} + +void +rtt_lost(struct rtt_info* rtt) +{ + /* exponential backoff */ + rtt->rto *= 2; + if(rtt->rto > RTT_MAX_TIMEOUT) + rtt->rto = RTT_MAX_TIMEOUT; +} diff --git a/util/rtt.h b/util/rtt.h new file mode 100644 index 000000000..76be0b467 --- /dev/null +++ b/util/rtt.h @@ -0,0 +1,89 @@ +/* + * util/rtt.h - UDP round trip time estimator for resend timeouts. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * + * This file contains a data type and functions to help estimate good + * round trip times for UDP resend timeout values. + */ + +#ifndef UTIL_RTT_H +#define UTIL_RTT_H + +/** + * RTT information. Keeps packet Round Trip Time. + */ +struct rtt_info { + /** smoothed rtt estimator, in milliseconds */ + int srtt; + /** smoothed mean deviation, in milliseconds */ + int rttvar; + /** current RTO in use, in milliseconds */ + int rto; +}; + +/** min retransmit timeout value, in milliseconds */ +#define RTT_MIN_TIMEOUT 2000 +/** max retransmit timeout value, in milliseconds */ +#define RTT_MAX_TIMEOUT 120000 + +/** + * Initialize RTT estimators. + * @param rtt: The structure. Caller is responsible for allocation of it. + */ +void rtt_init(struct rtt_info* rtt); + +/** + * Get timeout to use for sending a UDP packet. + * @param rtt: round trip statistics structure. + * @return: timeout to use in milliseconds. Relative time value. + */ +int rtt_timeout(const struct rtt_info* rtt); + +/** + * Update the statistics with a new roundtrip estimate observation. + * @param rtt: round trip statistics structure. + * @param ms: estimate of roundtrip time in milliseconds. + */ +void rtt_update(struct rtt_info* rtt, int ms); + +/** + * Update the statistics with a new timout expired observation. + * @param rtt: round trip statistics structure. + */ +void rtt_lost(struct rtt_info* rtt); + +#endif /* UTIL_RTT_H */ -- 2.47.2