Functions |
| int | rte_red_rt_data_init (struct rte_red *red) |
| | Initialises run-time data.
|
| int | rte_red_config_init (struct rte_red_config *red_cfg, const uint16_t wq_log2, const uint16_t min_th, const uint16_t max_th, const uint16_t maxp_inv) |
| | Configures a single RED configuration parameter structure.
|
| static uint32_t | rte_fast_rand (void) |
| | Generate random number for RED.
|
| static uint16_t | __rte_red_calc_qempty_factor (uint8_t wq_log2, uint16_t m) |
| | calculate factor to scale average queue size when queue becomes empty
|
| static int | rte_red_enqueue_empty (const struct rte_red_config *red_cfg, struct rte_red *red, const uint64_t time) |
| | Updates queue average in condition when queue is empty.
|
| static int | __rte_red_drop (const struct rte_red_config *red_cfg, struct rte_red *red) |
| | make a decision to drop or enqueue a packet based on mark probability criteria
|
| static int | rte_red_enqueue_nonempty (const struct rte_red_config *red_cfg, struct rte_red *red, const unsigned q) |
| | Decides if new packet should be enqeued or dropped in queue non-empty case.
|
| static int | rte_red_enqueue (const struct rte_red_config *red_cfg, struct rte_red *red, const unsigned q, const uint64_t time) |
| | Decides if new packet should be enqeued or dropped Updates run time data based on new queue size value. Based on new queue average and RED configuration parameters gives verdict whether to enqueue or drop the packet.
|
| static void | rte_red_mark_queue_empty (struct rte_red *red, const uint64_t time) |
| | Callback to records time that queue became empty.
|
RTE Random Early Detection (RED)
| static uint16_t __rte_red_calc_qempty_factor |
( |
uint8_t |
wq_log2, |
|
|
uint16_t |
m |
|
) |
| |
|
inlinestatic |
calculate factor to scale average queue size when queue becomes empty
- Parameters
-
| [in] | wq_log2,where | EWMA filter weight wq = 1/(2 ^ wq_log2) |
| [in] | m | exponent in the computed value (1 - wq) ^ m |
- Returns
- computed value
- Return values
-
| ((1 | - wq) ^ m) scaled in fixed-point format |
Basic math tells us that: a^b = 2^(b * log2(a) )
in our case: a = (1-Wq) b = m Wq = 1/ (2^log2n)
So we are computing this equation: factor = 2 ^ ( m * log2(1-Wq))
First we are computing: n = m * log2(1-Wq)
To avoid dealing with signed numbers log2 values are positive but they should be negative because (1-Wq) is always < 1. Contents of log2 table values are also scaled for precision.
The tricky part is computing 2^n, for this I split n into integer part and fraction part. f - is fraction part of n n - is integer part of original n
Now using basic math we compute 2^n: 2^(f+n) = 2^f * 2^n 2^f - we use lookup table 2^n - can be replaced with bit shift right oeprations
make a decision to drop or enqueue a packet based on mark probability criteria
Drop probability (Sally Floyd and Van Jacobson):
pb = (1 / maxp_inv) * (avg - min_th) / (max_th - min_th) pa = pb / (2 - count * pb)
(1 / maxp_inv) * (avg - min_th)
---------------------------------
max_th - min_th
pa = -----------------------------------------—— count * (1 / maxp_inv) * (avg - min_th) 2 - -----------------------------------—— max_th - min_th
avg - min_th
pa = -----------------------------------------------------—— 2 * (max_th - min_th) * maxp_inv - count * (avg - min_th)
We define pa_const as: pa_const = 2 * (max_th - min_th) * maxp_inv. Then:
avg - min_th
pa = -----------------------------—— pa_const - count * (avg - min_th)
- Parameters
-
| [in] | config | pointer to structure defining RED parameters |
| [in,out] | data | pointer to RED runtime data |
- Returns
- operation status
- Return values
-
| 0 | enqueue the packet |
| 1 | drop the packet |
| static int rte_red_enqueue_empty |
( |
const struct rte_red_config * |
red_cfg, |
|
|
struct rte_red * |
red, |
|
|
const uint64_t |
time |
|
) |
| |
|
inlinestatic |
Updates queue average in condition when queue is empty.
Note: packet is never dropped in this particular case.
- Parameters
-
| [in] | config | pointer to a RED configuration parameter structure |
| [in,out] | data | pointer to RED runtime data |
| [in] | time | current time stamp |
- Returns
- Operation status
- Return values
-
| 0 | enqueue the packet |
| 1 | drop the packet based on max threshold criterion |
| 2 | drop the packet based on mark probability criterion |
We compute avg but we don't compare avg against min_th or max_th, nor calculate drop probability
m is the number of packets that might have arrived while the queue was empty. In this case we have time stamps provided by scheduler in byte units (bytes transmitted on network port). Such time stamp translates into time units as port speed is fixed but such approach simplifies the code.
Check that m will fit into 16-bit unsigned integer
| static int rte_red_enqueue_nonempty |
( |
const struct rte_red_config * |
red_cfg, |
|
|
struct rte_red * |
red, |
|
|
const unsigned |
q |
|
) |
| |
|
inlinestatic |
Decides if new packet should be enqeued or dropped in queue non-empty case.
- Parameters
-
| [in] | config | pointer to a RED configuration parameter structure |
| [in,out] | data | pointer to RED runtime data |
| [in] | q | current queue size (measured in packets) |
- Returns
- Operation status
- Return values
-
| 0 | enqueue the packet |
| 1 | drop the packet based on max threshold criterion |
| 2 | drop the packet based on mark probability criterion |
EWMA filter (Sally Floyd and Van Jacobson): avg = (1 - wq) * avg + wq * q avg = avg + q * wq - avg * wq
We select: wq = 2^(-n). Let scaled version of avg be: avg_s = avg * 2^(N+n). We get: avg_s = avg_s + q * 2^N - avg_s * 2^(-n)
By using shift left/right operations, we get: avg_s = avg_s + (q << N) - (avg_s >> n) avg_s += (q << N) - (avg_s >> n)
