commit 5ef7b8cb390d3aeb774c552357d4220edd4567e7 Author: Zack Weinberg zackw@cmu.edu Date: Thu Jan 12 17:44:31 2012 +0000
Exponential backoff in chaff transmissions
git-svn-id: svn+ssh://spartan.csl.sri.com/svn/private/DEFIANCE@214 a58ff0ac-194c-e011-a152-003048836090 --- src/connections.cc | 12 +++-- src/protocol/chop.cc | 63 ++++++++++++------------ src/rng.cc | 128 +++++++++++++++++++++++++++++++++++++++++--------- src/test/test_tl.py | 2 +- 4 files changed, 145 insertions(+), 60 deletions(-)
diff --git a/src/connections.cc b/src/connections.cc index f0967a2..6320746 100644 --- a/src/connections.cc +++ b/src/connections.cc @@ -362,9 +362,11 @@ circuit_recv_eof(circuit_t *ckt) void circuit_arm_flush_timer(circuit_t *ckt, unsigned int milliseconds) { + log_debug(ckt, "flush within %u milliseconds", milliseconds); + struct timeval tv; - tv.tv_sec = 0; - tv.tv_usec = milliseconds * 1000; + tv.tv_sec = milliseconds / 1000; + tv.tv_usec = (milliseconds % 1000) * 1000;
if (!ckt->flush_timer) ckt->flush_timer = evtimer_new(ckt->cfg->base, flush_timer_cb, ckt); @@ -382,9 +384,11 @@ circuit_disarm_flush_timer(circuit_t *ckt) void circuit_arm_axe_timer(circuit_t *ckt, unsigned int milliseconds) { + log_debug(ckt, "axe after %u milliseconds", milliseconds); + struct timeval tv; - tv.tv_sec = 0; - tv.tv_usec = milliseconds * 1000; + tv.tv_sec = milliseconds / 1000; + tv.tv_usec = (milliseconds % 1000) * 1000;
if (!ckt->axe_timer) ckt->axe_timer = evtimer_new(ckt->cfg->base, axe_timer_cb, ckt); diff --git a/src/protocol/chop.cc b/src/protocol/chop.cc index 51d3195..6b0d6a4 100644 --- a/src/protocol/chop.cc +++ b/src/protocol/chop.cc @@ -94,6 +94,7 @@ namespace { uint64_t circuit_id; uint32_t send_offset; uint32_t recv_offset; + uint32_t dead_cycles; bool received_syn : 1; bool received_fin : 1; bool sent_syn : 1; @@ -101,6 +102,19 @@ namespace { bool upstream_eof : 1;
CIRCUIT_DECLARE_METHODS(chop); + + uint32_t axe_interval() { + return rng_range_geom(30 * 60 * 1000, + std::min((1 << dead_cycles) * 1000, + 20 * 60 * 1000)) + + 5 * 1000; + } + uint32_t flush_interval() { + return rng_range_geom(20 * 60 * 1000, + std::min((1 << dead_cycles) * 500, + 10 * 60 * 1000)) + + 1000; + } };
struct chop_config_t : config_t @@ -252,7 +266,7 @@ chop_pick_connection(chop_circuit_t *ckt, size_t desired, size_t *blocksize) room = 0; else room -= CHOP_BLOCK_OVERHD; - + if (room > CHOP_MAX_DATA) room = CHOP_MAX_DATA;
@@ -299,7 +313,6 @@ chop_send_block(conn_t *d, chop_header hdr; struct evbuffer_iovec v; uint8_t *p; - struct timeval *exp_time = NULL;
log_assert(evbuffer_get_length(block) == 0); log_assert(evbuffer_get_length(source) >= length); @@ -333,18 +346,6 @@ chop_send_block(conn_t *d, if (evbuffer_commit_space(block, &v, 1)) goto fail;
- /* save the expiration time of the must_transmit_timer in case of failure */ - if (dest->must_transmit_timer) { - exp_time = new struct timeval; - if (evtimer_pending(dest->must_transmit_timer, exp_time)) { - log_debug("saved must_transmit_timer value in case of failure"); - } else { - delete exp_time; - exp_time = NULL; - } - evtimer_del(dest->must_transmit_timer); - } - if (dest->steg->transmit(block, dest)) goto fail_committed;
@@ -352,6 +353,10 @@ chop_send_block(conn_t *d, /* this really should never happen, and we can't recover from it */ log_abort(dest, "evbuffer_drain failed"); /* does not return */
+ /* Cancel the must-transmit timer if it's pending; we have transmitted. */ + if (dest->must_transmit_timer) + evtimer_del(dest->must_transmit_timer); + if (!(flags & CHOP_F_CHAFF)) ckt->send_offset += length; if (flags & CHOP_F_SYN) @@ -361,9 +366,6 @@ chop_send_block(conn_t *d, log_debug(dest, "sent %lu+%u byte block [flags %04hx]", (unsigned long)CHOP_WIRE_HDR_LEN, length, flags);
- if (exp_time != NULL) - delete exp_time; - return 0;
fail: @@ -373,17 +375,6 @@ chop_send_block(conn_t *d, evbuffer_drain(block, evbuffer_get_length(block)); log_warn(dest, "allocation or buffer copy failed");
- /* restore timer if necessary */ - if (exp_time != NULL) { - if (!evtimer_pending(dest->must_transmit_timer, NULL)) { - struct timeval cur_time, timeout; - gettimeofday(&cur_time, NULL); - timeval_subtract(exp_time, &cur_time, &timeout); - evtimer_add(dest->must_transmit_timer, &timeout); - } - delete exp_time; - } - return -1; }
@@ -746,12 +737,14 @@ chop_push_to_upstream(circuit_t *c) chop_reassembly_elt *ready = ckt->reassembly_queue.next; if (!ready->data || ckt->recv_offset != ready->offset) { log_debug(c, "no data pushable to upstream yet"); + ckt->dead_cycles++; return 0; }
if (!ckt->received_syn) { if (!(ready->flags & CHOP_F_SYN)) { log_debug(c, "waiting for SYN"); + ckt->dead_cycles++; return 0; } log_debug(c, "processed SYN"); @@ -765,6 +758,7 @@ chop_push_to_upstream(circuit_t *c) return -1; }
+ ckt->dead_cycles = 0; ckt->recv_offset += ready->length;
if (ready->flags & CHOP_F_FIN) { @@ -1110,7 +1104,7 @@ chop_circuit_t::send() if (this->cfg->mode != LSN_SIMPLE_SERVER) circuit_reopen_downstreams(this); else - circuit_arm_axe_timer(this, 5000); + circuit_arm_axe_timer(this, this->axe_interval()); return 0; }
@@ -1118,9 +1112,11 @@ chop_circuit_t::send() /* must-send timer expired and we still have nothing to say; send chaff */ if (chop_send_chaff(this)) return -1; + this->dead_cycles++; } else { if (chop_send_blocks(this)) return -1; + this->dead_cycles = 0; }
/* If we're at EOF, close all connections (sending first if @@ -1138,7 +1134,7 @@ chop_circuit_t::send() } } else { if (this->cfg->mode != LSN_SIMPLE_SERVER) - circuit_arm_flush_timer(this, 5); + circuit_arm_flush_timer(this, this->flush_interval()); } return 0; } @@ -1332,8 +1328,11 @@ void chop_conn_t::transmit_soon(unsigned long milliseconds) { struct timeval tv; - tv.tv_sec = 0; - tv.tv_usec = milliseconds * 1000; + + log_debug(this, "must transmit within %lu milliseconds", milliseconds); + + tv.tv_sec = milliseconds / 1000; + tv.tv_usec = (milliseconds % 1000) * 1000;
if (!this->must_transmit_timer) this->must_transmit_timer = evtimer_new(this->cfg->base, diff --git a/src/rng.cc b/src/rng.cc index 95bea3a..a42c487 100644 --- a/src/rng.cc +++ b/src/rng.cc @@ -91,34 +91,106 @@ rng_range(unsigned int min, unsigned int max)
/** Internal use only (can be externalized if someone has a good use * for it): generate a random double-precision floating-point number - * in the range [0.0, 1.0). Implementation tactic from "Common Lisp - * the Language, 2nd Edition", section 12.9. Assumes IEEE754. + * in the range (0.0, 1.0] (note that this is _not_ the usual convention, + * but it saves a call to nextafter() in the sole current user). + * + * For what we use this for, it is important that we can, at least + * potentially, generate _every_ representable real number in the + * desired interval, with genuine uniformity. The usual tactic of + * generating a random integer and dividing does not do this, because + * the rational numbers produced by random()/MAX are evenly spaced on + * the real line, but floating point numbers close to zero are *not*. + * + * For the same reason, the trick for avoiding division suggested + * e.g. by "Common Lisp, the Language", generating a random number in + * [1.0, 2.0) by overwriting the mantissa of a 1.0 and then + * subtracting 1.0, does not help -- you can do the first step + * precisely because the representable binary floating point numbers + * between 1.0 and 2.0 *are* evenly spaced on the real line. + * + * The more complicated, but correct, algorithm here was developed by + * Allen B. Downey: http://allendowney.com/research/rand/ + * */ static double rng_double() { + class rngbit { + public: + rngbit(uint32_t bits, unsigned int n) : bits(bits), n(n) {} + + bool get() + { + if (n == 0) { + bits = rng->GenerateByte(); + n = CHAR_BIT; + } + bool rv = bits & 1; + bits >>= 1; + n -= 1; + return rv; + } + private: + uint32_t bits; + unsigned int n; + }; + union ieee754_double { double d; uint64_t i; };
- union ieee754_double n; - - /* This may waste up to 12 bits of randomness on each call, - depending on how clever GenerateWord32 is internally; but the - implementation is much simpler than if we used GenerateBlock. */ try { rng_init(); - n.i = (0x3FF0000000000000ULL | - (uint64_t(rng->GenerateWord32(0, 0x000FFFFFu)) << 32) | - uint64_t(rng->GenerateWord32())); - } CATCH_ALL_EXCEPTIONS(std::numeric_limits<double>::quiet_NaN());
- return n.d - 1.0; + /* Because of how the Crypto++ RNG works, it is convenient to + generate the mantissa first, contra Downey, and use the + leftover bits to seed the bit-generator that we use for the + exponent; this does not change the algorithm fundamentally, + because only the final adjustment step depends on both. */ + + uint64_t mantissa = rng->GenerateWord32(); + uint32_t b = rng->GenerateWord32(); + + mantissa |= uint64_t(b & 0x000FFFFF) << 32; + + /* This is the core of Downey's algorithm: 50% of the time we + should generate the highest exponent of a number in (0,1) (note + that _neither_ endpoint is included right now). 25% of the + time, we should generate the second highest exponent, 12.5% of + the time, we should generate the third highest, and so on. In + other words, we should start with the highest exponent, flip a + coin, and keep subtracting 1 until either we hit zero or the + coin comes up heads. + + If anyone knows how to do this in _constant_ time, instead of + variable time bounded by a constant, please tell me. + */ + + rngbit bits((b & 0xFFF00000) >> 20, 12); + uint32_t exponent = 0x3FE; /* 1111111110 = 2^{-1} */ + do { + if (bits.get()) break; + } while (--exponent); + + /* Finally a slight adjustment: if the mantissa is zero, then + half the time we should increment the exponent by one. + Do this unconditionally if the exponent is also zero + (so we never generate 0.0). */ + if (mantissa == 0 && (exponent == 0 || bits.get())) + exponent++; + + /* Assemble and return the number. */ + union ieee754_double n; + n.i = (uint64_t(exponent) << 52) | mantissa; + return n.d; + } + CATCH_ALL_EXCEPTIONS(std::numeric_limits<double>::quiet_NaN()); }
-/** Return a random integer in the range [0, hi), geometrically - * distributed over that range, with expected value 'xv'. +/** Return a random integer in the range [0, hi), + * from a truncated geometric distribution whose expected value + * (prior to truncation) is 'xv'. * (The rate parameter 'lambda' that's usually used to characterize * the geometric/exponential distribution is equal to 1/xv.) * 'hi' must be no more than INT_MAX+1, as for 'rng_range'. @@ -134,14 +206,24 @@ rng_range_geom(unsigned int hi, unsigned int xv) if (isnan(U)) return -1;
- /* Inverse transform sampling: - T = (-ln U)/lambda; lambda=1/(xv-lo); therefore T = (xv-lo) * -ln(U). - Minor wrinkle: rng_double() produces [0, 1) but we want (0, 1] to - avoid hitting the undefined log(0). This is what nextafter() is for. */ - - double T = -log(nextafter(U, 2.0)) * xv; - - /* Technically we should rejection-sample here instead of clamping, but - that would make this not a constant-time operation. */ + /* The exponential distribution with expected value + xe = 1/log(1 + 1/xv) + can be converted to the desired geometric distribution by + floor(). See http://math.stackexchange.com/questions/97733 */ + double xe = 1./log(1. + 1./xv); + + /* To truncate in constant time, adjust U to be in the range + ( e^{-hi/xe}, 1 ]. Doing this with arithmetic introduces + a slight nonuniformity, but we really want to avoid rejection + sampling here. */ + double ulo = exp(-hi/xe); + U = ulo + U * (1-ulo); + + /* Inverse transform sampling gives us a value for the exponential + distribution with expected value 'xe'. */ + double T = -log(U) * xe; + + /* Round down for the geometric distribution, and clamp to [0, hi) + for great defensiveness. */ return std::min(hi-1, std::max(0U, (unsigned int)floor(T))); } diff --git a/src/test/test_tl.py b/src/test/test_tl.py index c7899b7..2c54228 100644 --- a/src/test/test_tl.py +++ b/src/test/test_tl.py @@ -51,7 +51,7 @@ class TimelineTest(object): ("chop", "server", "127.0.0.1:5001", "127.0.0.1:5010","127.0.0.1:5011", "chop", "client", "127.0.0.1:4999", - "127.0.0.1:5010","x_http","127.0.0.1:5011","x_http", + "127.0.0.1:5010","http","127.0.0.1:5011","http", ))
# Synthesize TimelineTest+TestCase subclasses for every 'tl_*' file in