circuitmux_ewma.c File Reference

EWMA circuit selection as a circuitmux_t policy. More...

#include "orconfig.h"
#include <math.h>
#include "or.h"
#include "circuitmux.h"
#include "circuitmux_ewma.h"
#include "crypto_rand.h"
#include "networkstatus.h"

Include dependency graph for circuitmux_ewma.c:

Data Structures
struct	cell_ewma_s
struct	ewma_policy_data_s
struct	ewma_policy_circ_data_s

Macros
#define	CIRCUITMUX_EWMA_PRIVATE
#define	EWMA_TICK_LEN   10
#define	EWMA_DEFAULT_HALFLIFE   0.0
#define	EPSILON   0.00001
#define	LOG_ONEHALF   -0.69314718055994529
#define	EWMA_POL_DATA_MAGIC   0x2fd8b16aU
#define	EWMA_POL_CIRC_DATA_MAGIC   0x761e7747U
#define	CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT   30000
#define	CMUX_PRIORITY_HALFLIFE_MSEC_MIN   1
#define	CMUX_PRIORITY_HALFLIFE_MSEC_MAX   INT32_MAX

Typedefs
typedef struct cell_ewma_s	cell_ewma_t
typedef struct ewma_policy_data_s	ewma_policy_data_t
typedef struct ewma_policy_circ_data_s	ewma_policy_circ_data_t

Functions
STATIC void	cell_ewma_initialize_ticks (void)
STATIC unsigned	cell_ewma_get_current_tick_and_fraction (double *remainder_out)
void	cmux_ewma_set_options (const or_options_t *options, const networkstatus_t *consensus)
void	circuitmux_ewma_free_all (void)

Variables
circuitmux_policy_t	ewma_policy

Detailed Description

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.

Macro Definition Documentation

EPSILON

#define EPSILON   0.00001

Any halflife smaller than this number of seconds is considered to be "disabled".

EWMA_DEFAULT_HALFLIFE

#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".

EWMA_TICK_LEN

#define EWMA_TICK_LEN   10

How long does a tick last (seconds)?

LOG_ONEHALF

#define LOG_ONEHALF   -0.69314718055994529

The natural logarithm of 0.5.

Function Documentation

cell_ewma_get_current_tick_and_fraction()

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.

cell_ewma_initialize_ticks()

STATIC void cell_ewma_initialize_ticks

(

void

)

Initialize the system that tells which ewma tick we are in.

Here is the caller graph for this function:

circuitmux_ewma_free_all()

void circuitmux_ewma_free_all

(

void

)

Drop all resources held by circuitmux_ewma.c, and deinitialize the module.

cmux_ewma_set_options()

void cmux_ewma_set_options	(	const or_options_t *	options,
		const networkstatus_t *	consensus
	)

Adjust the global cell scale factor based on options

Here is the call graph for this function:

Variable Documentation

ewma_policy

circuitmux_policy_t ewma_policy

Initial value:

= {
   ewma_alloc_cmux_data,
   ewma_free_cmux_data,
   ewma_alloc_circ_data,
   ewma_free_circ_data,
   ewma_notify_circ_active,
   ewma_notify_circ_inactive,
   NULL, 
   ewma_notify_xmit_cells,
   ewma_pick_active_circuit,
   ewma_cmp_cmux
}