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"

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	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 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

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.

Definition in file circuitmux_ewma.c.

Macro Definition Documentation

◆ EPSILON

#define EPSILON 0.00001

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

Definition at line 58 of file circuitmux_ewma.c.

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

Definition at line 52 of file circuitmux_ewma.c.

◆ EWMA_TICK_LEN

#define EWMA_TICK_LEN 10

How long does a tick last (seconds)?

Definition at line 48 of file circuitmux_ewma.c.

◆ LOG_ONEHALF

#define LOG_ONEHALF -0.69314718055994529

The natural logarithm of 0.5.

Definition at line 60 of file circuitmux_ewma.c.

Function Documentation

◆ add_cell_ewma()

static void add_cell_ewma	(	ewma_policy_data_t *	pol,
		cell_ewma_t *	ewma
	)

static

Rescale ewma to the same scale as pol, and add it to pol's priority queue of active circuits

Definition at line 670 of file circuitmux_ewma.c.

Referenced by ewma_notify_circ_active(), and ewma_notify_xmit_cells().

◆ 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.

Definition at line 521 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells().

◆ cell_ewma_get_tick()

static unsigned int cell_ewma_get_tick ( void )

inlinestatic

Compute and return the current cell_ewma tick.

Definition at line 145 of file circuitmux_ewma.c.

◆ cell_ewma_initialize_ticks()

STATIC void cell_ewma_initialize_ticks ( void )

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

Definition at line 505 of file circuitmux_ewma.c.

Referenced by cmux_ewma_set_options().

◆ cell_ewma_to_circuit()

static circuit_t * cell_ewma_to_circuit ( cell_ewma_t * ewma )

static

Given a cell_ewma_t, return a pointer to the circuit containing it.

Definition at line 459 of file circuitmux_ewma.c.

◆ circuitmux_ewma_free_all()

void circuitmux_ewma_free_all ( void )

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

Definition at line 719 of file circuitmux_ewma.c.

◆ 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

Definition at line 597 of file circuitmux_ewma.c.

◆ compare_cell_ewma_counts()

static int compare_cell_ewma_counts	(	const void *	p1,
		const void *	p2
	)

static

Helper for sorting cell_ewma_t values in their priority queue.

Definition at line 445 of file circuitmux_ewma.c.

Referenced by add_cell_ewma(), pop_first_cell_ewma(), and remove_cell_ewma().

◆ ewma_alloc_circ_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

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 201 of file circuitmux_ewma.c.

◆ ewma_alloc_cmux_data()

static circuitmux_policy_data_t * ewma_alloc_cmux_data ( circuitmux_t * cmux )

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 160 of file circuitmux_ewma.c.

◆ ewma_cmp_cmux()

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

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 397 of file circuitmux_ewma.c.

◆ ewma_free_circ_data()

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

Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()

Definition at line 242 of file circuitmux_ewma.c.

◆ ewma_free_cmux_data()

static void ewma_free_cmux_data	(	circuitmux_t *	cmux,
		circuitmux_policy_data_t *	pol_data
	)

static

Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()

Definition at line 179 of file circuitmux_ewma.c.

◆ ewma_notify_circ_active()

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

Handle circuit activation; this inserts the circuit's cell_ewma into the active_circuits_pqueue.

Definition at line 267 of file circuitmux_ewma.c.

◆ ewma_notify_circ_inactive()

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

Handle circuit deactivation; this removes the circuit's cell_ewma from the active_circuits_pqueue.

Definition at line 292 of file circuitmux_ewma.c.

◆ ewma_notify_xmit_cells()

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

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 318 of file circuitmux_ewma.c.

◆ ewma_pick_active_circuit()

static circuit_t * ewma_pick_active_circuit	(	circuitmux_t *	cmux,
		circuitmux_policy_data_t *	pol_data
	)

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 370 of file circuitmux_ewma.c.

◆ get_scale_factor()

static double get_scale_factor	(	unsigned	from_tick,
		unsigned	to_tick
	)

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 622 of file circuitmux_ewma.c.

Referenced by scale_active_circuits(), and scale_single_cell_ewma().

◆ pop_first_cell_ewma()

static cell_ewma_t * pop_first_cell_ewma ( ewma_policy_data_t * pol )

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 705 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells().

◆ remove_cell_ewma()

static void remove_cell_ewma	(	ewma_policy_data_t *	pol,
		cell_ewma_t *	ewma
	)

static

Remove ewma from pol's priority queue of active circuits

Definition at line 689 of file circuitmux_ewma.c.

Referenced by ewma_notify_circ_inactive().

◆ scale_active_circuits()

static void scale_active_circuits	(	ewma_policy_data_t *	pol,
		unsigned	cur_tick
	)

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 643 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells().

◆ scale_single_cell_ewma()

static void scale_single_cell_ewma	(	cell_ewma_t *	ewma,
		unsigned	cur_tick
	)

static

Adjust the cell count of ewma so that it is scaled with respect to cur_tick

Definition at line 633 of file circuitmux_ewma.c.

Referenced by add_cell_ewma().

Variable Documentation

◆ current_tick_num

unsigned current_tick_num

static

What is the number of the current tick?

Definition at line 139 of file circuitmux_ewma.c.

◆ 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
}

Definition at line 121 of file circuitmux_ewma.c.

◆ ewma_scale_factor

double ewma_scale_factor = 0.1

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 117 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells(), and get_scale_factor().

◆ ewma_ticks_initialized

int ewma_ticks_initialized = 0

static

Have we initialized the ewma tick-counting logic?

Definition at line 135 of file circuitmux_ewma.c.

Referenced by cell_ewma_initialize_ticks(), and circuitmux_ewma_free_all().

◆ start_of_current_tick

monotime_coarse_t start_of_current_tick

static

At what monotime_coarse_t did the current tick begin?

Definition at line 137 of file circuitmux_ewma.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ EPSILON

◆ EWMA_DEFAULT_HALFLIFE

◆ EWMA_TICK_LEN

◆ LOG_ONEHALF

Function Documentation

◆ add_cell_ewma()

◆ cell_ewma_get_current_tick_and_fraction()

◆ cell_ewma_get_tick()

◆ cell_ewma_initialize_ticks()

◆ cell_ewma_to_circuit()

◆ circuitmux_ewma_free_all()

◆ cmux_ewma_set_options()

◆ compare_cell_ewma_counts()

◆ ewma_alloc_circ_data()

◆ ewma_alloc_cmux_data()

◆ ewma_cmp_cmux()

◆ ewma_free_circ_data()

◆ ewma_free_cmux_data()

◆ ewma_notify_circ_active()

◆ ewma_notify_circ_inactive()

◆ ewma_notify_xmit_cells()

◆ ewma_pick_active_circuit()

◆ get_scale_factor()

◆ pop_first_cell_ewma()

◆ remove_cell_ewma()

◆ scale_active_circuits()

◆ scale_single_cell_ewma()

Variable Documentation

◆ current_tick_num

◆ ewma_policy

◆ ewma_scale_factor

◆ ewma_ticks_initialized

◆ start_of_current_tick