|
DPDK
21.11.8
|
#include <stdint.h>#include <limits.h>#include <rte_common.h>#include <rte_debug.h>#include <rte_cycles.h>#include <rte_branch_prediction.h>Go to the source code of this file.
Data Structures | |
| struct | rte_red_params |
| struct | rte_red_config |
| struct | rte_red |
Macros | |
| #define | RTE_RED_SCALING 10 |
| #define | RTE_RED_S (1 << 22) |
| #define | RTE_RED_MAX_TH_MAX 1023 |
| #define | RTE_RED_WQ_LOG2_MIN 1 |
| #define | RTE_RED_WQ_LOG2_MAX 12 |
| #define | RTE_RED_MAXP_INV_MIN 1 |
| #define | RTE_RED_MAXP_INV_MAX 255 |
| #define | RTE_RED_2POW16 (1<<16) |
Functions | |
| int | rte_red_rt_data_init (struct rte_red *red) |
| Initialises run-time data. More... | |
| 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. More... | |
| static uint32_t | rte_fast_rand (void) |
| Generate random number for RED. More... | |
| 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 More... | |
| 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. More... | |
| 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 More... | |
| 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 enqueued or dropped in queue non-empty case. More... | |
| 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 enqueued 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. More... | |
| static void | rte_red_mark_queue_empty (struct rte_red *red, const uint64_t time) |
| Callback to records time that queue became empty. More... | |
Variables | |
| uint32_t | rte_red_rand_val |
RTE Random Early Detection (RED)
Definition in file rte_red.h.
| #define RTE_RED_S (1 << 22) |
| #define RTE_RED_MAX_TH_MAX 1023 |
| #define RTE_RED_WQ_LOG2_MIN 1 |
| #define RTE_RED_WQ_LOG2_MAX 12 |
| #define RTE_RED_MAXP_INV_MIN 1 |
| #define RTE_RED_MAXP_INV_MAX 255 |
| int rte_red_rt_data_init | ( | struct rte_red * | red | ) |
Initialises run-time data.
| red | [in,out] data pointer to RED runtime data |
| 0 | success |
| !0 | error |
| 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.
| red_cfg | [in,out] config pointer to a RED configuration parameter structure |
| wq_log2 | [in] log2 of the filter weight, valid range is: RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX |
| min_th | [in] queue minimum threshold in number of packets |
| max_th | [in] queue maximum threshold in number of packets |
| maxp_inv | [in] inverse maximum mark probability |
| 0 | success |
| !0 | error |
|
inlinestatic |
Generate random number for RED.
Implementation based on: http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
10 bit shift has been found through empirical tests (was 16).
|
inlinestatic |
calculate factor to scale average queue size when queue becomes empty
| wq_log2 | [in] where EWMA filter weight wq = 1/(2 ^ wq_log2) |
| m | [in] exponent in the computed value (1 - wq) ^ m |
| ((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 operations
|
inlinestatic |
Updates queue average in condition when queue is empty.
Note: packet is never dropped in this particular case.
| red_cfg | [in] config pointer to a RED configuration parameter structure |
| red | [in,out] data pointer to RED runtime data |
| time | [in] current time stamp |
| 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
|
inlinestatic |
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)
| red_cfg | [in] config pointer to structure defining RED parameters |
| red | [in,out] data pointer to RED runtime data |
| 0 | enqueue the packet |
| 1 | drop the packet |
|
inlinestatic |
Decides if new packet should be enqueued or dropped in queue non-empty case.
| red_cfg | [in] config pointer to a RED configuration parameter structure |
| red | [in,out] data pointer to RED runtime data |
| q | [in] current queue size (measured in packets) |
| 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)
|
inlinestatic |
Decides if new packet should be enqueued 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.
| red_cfg | [in] config pointer to a RED configuration parameter structure |
| red | [in,out] data pointer to RED runtime data |
| q | [in] updated queue size in packets |
| time | [in] current time stamp |
| 0 | enqueue the packet |
| 1 | drop the packet based on max threshold criteria |
| 2 | drop the packet based on mark probability criteria |
|
inlinestatic |
| uint32_t rte_red_rand_val |
Externs
1.8.13