|
Tor 0.4.9.0-alpha-dev
|
EWMA circuit selection as a circuitmux_t policy. More...
#include "orconfig.h"#include <math.h>#include "core/or/or.h"#include "core/or/circuitmux.h"#include "core/or/circuitmux_ewma.h"#include "lib/crypt_ops/crypto_rand.h"#include "lib/crypt_ops/crypto_util.h"#include "feature/nodelist/networkstatus.h"#include "app/config/or_options_st.h"Go to the source code of this file.
Macros | |
| #define | CIRCUITMUX_EWMA_PRIVATE |
| #define | EWMA_TICK_LEN_DEFAULT 10 |
| #define | EWMA_TICK_LEN_MIN 1 |
| #define | EWMA_TICK_LEN_MAX 600 |
| #define | EWMA_DEFAULT_HALFLIFE 0.0 |
| #define | EPSILON 0.00001 |
| #define | LOG_ONEHALF -0.69314718055994529 |
| #define | CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000 |
| #define | CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1 |
| #define | CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX |
Functions | |
| static void | add_cell_ewma (ewma_policy_data_t *pol, cell_ewma_t *ewma) |
| static int | compare_cell_ewma_counts (const void *p1, const void *p2) |
| static circuit_t * | cell_ewma_to_circuit (cell_ewma_t *ewma) |
| static double | get_scale_factor (unsigned from_tick, unsigned to_tick) |
| static cell_ewma_t * | pop_first_cell_ewma (ewma_policy_data_t *pol) |
| static void | remove_cell_ewma (ewma_policy_data_t *pol, cell_ewma_t *ewma) |
| static void | scale_single_cell_ewma (cell_ewma_t *ewma, unsigned cur_tick) |
| static void | scale_active_circuits (ewma_policy_data_t *pol, unsigned cur_tick) |
| static circuitmux_policy_data_t * | ewma_alloc_cmux_data (circuitmux_t *cmux) |
| static void | ewma_free_cmux_data (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data) |
| static circuitmux_policy_circ_data_t * | ewma_alloc_circ_data (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, cell_direction_t direction, unsigned int cell_count) |
| static void | ewma_free_circ_data (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, circuitmux_policy_circ_data_t *pol_circ_data) |
| static void | ewma_notify_circ_active (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, circuitmux_policy_circ_data_t *pol_circ_data) |
| static void | ewma_notify_circ_inactive (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, circuitmux_policy_circ_data_t *pol_circ_data) |
| static void | ewma_notify_xmit_cells (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, circuitmux_policy_circ_data_t *pol_circ_data, unsigned int n_cells) |
| static circuit_t * | ewma_pick_active_circuit (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data) |
| static int | ewma_cmp_cmux (circuitmux_t *cmux_1, circuitmux_policy_data_t *pol_data_1, circuitmux_t *cmux_2, circuitmux_policy_data_t *pol_data_2) |
| static unsigned int | cell_ewma_get_tick (void) |
| STATIC void | cell_ewma_initialize_ticks (void) |
| STATIC unsigned | cell_ewma_get_current_tick_and_fraction (double *remainder_out) |
| static double | get_circuit_priority_halflife (const or_options_t *options, const networkstatus_t *consensus, const char **source_msg) |
| void | cmux_ewma_set_options (const or_options_t *options, const networkstatus_t *consensus) |
| void | circuitmux_ewma_free_all (void) |
Variables | |
| static int | ewma_tick_len = EWMA_TICK_LEN_DEFAULT |
| static double | ewma_scale_factor = 0.1 |
| circuitmux_policy_t | ewma_policy |
| static int | ewma_ticks_initialized = 0 |
| static monotime_coarse_t | start_of_current_tick |
| static unsigned | current_tick_num |
EWMA circuit selection as a circuitmux_t policy.
The "EWMA" in this module stands for the "exponentially weighted moving average" of the number of cells sent on each circuit. The goal is to prioritize cells on circuits that have been quiet recently, by looking at those that have sent few cells over time, prioritizing recent times more than older ones.
Specifically, a cell sent at time "now" has weight 1, but a time X ticks before now has weight ewma_scale_factor ^ X , where ewma_scale_factor is between 0.0 and 1.0.
For efficiency, we do not re-scale these averages every time we send a cell: that would be horribly inefficient. Instead, we we keep the cell count on all circuits on the same circuitmux scaled relative to a single tick. When we add a new cell, we scale its weight depending on the time that has elapsed since the tick. We do re-scale the circuits on the circuitmux periodically, so that we don't overflow double.
This module should be used through the interfaces in circuitmux.c, which it implements.
Definition in file circuitmux_ewma.c.
| #define CIRCUITMUX_EWMA_PRIVATE |
Definition at line 31 of file circuitmux_ewma.c.
| #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000 |
Definition at line 547 of file circuitmux_ewma.c.
| #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX |
Definition at line 551 of file circuitmux_ewma.c.
| #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1 |
Definition at line 550 of file circuitmux_ewma.c.
| #define EPSILON 0.00001 |
Any halflife smaller than this number of seconds is considered to be "disabled".
Definition at line 61 of file circuitmux_ewma.c.
| #define EWMA_DEFAULT_HALFLIFE 0.0 |
The default per-tick scale factor, if it hasn't been overridden by a consensus or a configuration setting. zero means "disabled".
Definition at line 55 of file circuitmux_ewma.c.
| #define EWMA_TICK_LEN_DEFAULT 10 |
How long does a tick last (seconds)?
Definition at line 48 of file circuitmux_ewma.c.
| #define EWMA_TICK_LEN_MAX 600 |
Definition at line 50 of file circuitmux_ewma.c.
| #define EWMA_TICK_LEN_MIN 1 |
Definition at line 49 of file circuitmux_ewma.c.
| #define LOG_ONEHALF -0.69314718055994529 |
The natural logarithm of 0.5.
Definition at line 63 of file circuitmux_ewma.c.
|
static |
Rescale ewma to the same scale as pol, and add it to pol's priority queue of active circuits
Definition at line 678 of file circuitmux_ewma.c.
Referenced by ewma_notify_circ_active(), and ewma_notify_xmit_cells().
| STATIC unsigned cell_ewma_get_current_tick_and_fraction | ( | double * | remainder_out | ) |
Compute the current cell_ewma tick and the fraction of the tick that has elapsed between the start of the tick and the current time. Return the former and store the latter in *remainder_out.
These tick values are not meant to be shared between Tor instances, or used for other purposes.
Definition at line 524 of file circuitmux_ewma.c.
Referenced by ewma_notify_xmit_cells().
|
inlinestatic |
Compute and return the current cell_ewma tick.
Definition at line 148 of file circuitmux_ewma.c.
| STATIC void cell_ewma_initialize_ticks | ( | void | ) |
Initialize the system that tells which ewma tick we are in.
Definition at line 508 of file circuitmux_ewma.c.
Referenced by cmux_ewma_set_options().
|
static |
Given a cell_ewma_t, return a pointer to the circuit containing it.
Definition at line 462 of file circuitmux_ewma.c.
| void circuitmux_ewma_free_all | ( | void | ) |
Drop all resources held by circuitmux_ewma.c, and deinitialize the module.
Definition at line 727 of file circuitmux_ewma.c.
| void cmux_ewma_set_options | ( | const or_options_t * | options, |
| const networkstatus_t * | consensus | ||
| ) |
Adjust the global cell scale factor based on options
Definition at line 600 of file circuitmux_ewma.c.
|
static |
Helper for sorting cell_ewma_t values in their priority queue.
Definition at line 448 of file circuitmux_ewma.c.
Referenced by add_cell_ewma(), pop_first_cell_ewma(), and remove_cell_ewma().
|
static |
Allocate an ewma_policy_circ_data_t and upcast it to a circuitmux_policy_data_t; this is called when attaching a circuit to a circuitmux_t with ewma_policy.
Definition at line 204 of file circuitmux_ewma.c.
|
static |
Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t; this is called when setting the policy on a circuitmux_t to ewma_policy.
Definition at line 163 of file circuitmux_ewma.c.
|
static |
Compare two EWMA cmuxes, and return -1, 0 or 1 to indicate which should be more preferred - see circuitmux_compare_muxes() of circuitmux.c.
Definition at line 400 of file circuitmux_ewma.c.
|
static |
Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()
Definition at line 245 of file circuitmux_ewma.c.
|
static |
Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
Definition at line 182 of file circuitmux_ewma.c.
|
static |
Handle circuit activation; this inserts the circuit's cell_ewma into the active_circuits_pqueue.
Definition at line 270 of file circuitmux_ewma.c.
|
static |
Handle circuit deactivation; this removes the circuit's cell_ewma from the active_circuits_pqueue.
Definition at line 295 of file circuitmux_ewma.c.
|
static |
Update cell_ewma for this circuit after we've sent some cells, and remove/reinsert it in the queue. This used to be done (brokenly, see bug 6816) in channel_flush_from_first_active_circuit().
Definition at line 321 of file circuitmux_ewma.c.
|
static |
Pick the preferred circuit to send from; this will be the one with the lowest EWMA value in the priority queue. This used to be done in channel_flush_from_first_active_circuit().
Definition at line 373 of file circuitmux_ewma.c.
|
static |
Definition at line 560 of file circuitmux_ewma.c.
|
inlinestatic |
Return the multiplier necessary to convert the value of a cell sent in 'from_tick' to one sent in 'to_tick'.
Definition at line 630 of file circuitmux_ewma.c.
Referenced by scale_active_circuits(), and scale_single_cell_ewma().
|
static |
Remove and return the first cell_ewma_t from pol's priority queue of active circuits. Requires that the priority queue is nonempty.
Definition at line 713 of file circuitmux_ewma.c.
Referenced by ewma_notify_xmit_cells().
|
static |
Remove ewma from pol's priority queue of active circuits
Definition at line 697 of file circuitmux_ewma.c.
Referenced by ewma_notify_circ_inactive().
|
static |
Adjust the cell count of every active circuit on chan so that they are scaled with respect to cur_tick
Ordinarily it isn't okay to change the value of an element in a heap, but it's okay here, since we are preserving the order.
Definition at line 651 of file circuitmux_ewma.c.
Referenced by ewma_notify_xmit_cells().
|
static |
Adjust the cell count of ewma so that it is scaled with respect to cur_tick
Definition at line 641 of file circuitmux_ewma.c.
Referenced by add_cell_ewma().
|
static |
What is the number of the current tick?
Definition at line 142 of file circuitmux_ewma.c.
| circuitmux_policy_t ewma_policy |
Definition at line 124 of file circuitmux_ewma.c.
|
static |
The per-tick scale factor to be used when computing cell-count EWMA values. (A cell sent N ticks before the start of the current tick has value ewma_scale_factor ** N.)
Definition at line 120 of file circuitmux_ewma.c.
Referenced by ewma_notify_xmit_cells(), and get_scale_factor().
|
static |
Definition at line 51 of file circuitmux_ewma.c.
|
static |
Have we initialized the ewma tick-counting logic?
Definition at line 138 of file circuitmux_ewma.c.
Referenced by cell_ewma_initialize_ticks(), and circuitmux_ewma_free_all().
|
static |
At what monotime_coarse_t did the current tick begin?
Definition at line 140 of file circuitmux_ewma.c.
1.9.4