+/**
+ * When FPS checks to see which mode it should be operating in
+ * (over limit vs under limit), we don't want it to actually look to
+ * see if we're at the limit. Instead, we want to see if we're getting
+ * close to the limit. This defines how close is "close enough".
+ *
+ * For example, if the limit is 50000 and we're sending 49000, we probably
+ * want to be in the over limit mode, even if we aren't actually over the limit
+ * in order to switch to the more aggressive weight calculations.
+ */
+static inline uint32_t close_enough(uint32_t limit) {
+ uint32_t difference = limit - (limit * CLOSE_ENOUGH);
+
+ if (difference < 2500) {
+ return (limit - 2500);
+ } else {
+ return (limit * CLOSE_ENOUGH);
+ }
+}
+
+static void print_statistics(identity_t *ident, const double ideal_weight,
+ const double total_weight, const double localweight,
+ const char *identifier, common_accounting_t *table,
+ const uint32_t resulting_limit) {
+ struct timeval tv;
+ double time_now;
+
+ gettimeofday(&tv, NULL);
+ time_now = (double) tv.tv_sec + (double) ((double) tv.tv_usec / (double) 1000000);
+
+ printlog(LOG_WARN, "%.2f %d %.2f %.2f %.2f %d %d %d %d %d %d %d %d %d %s:%d ",
+ time_now, table->inst_rate, ideal_weight, localweight, total_weight,
+ table->num_flows, table->num_flows_5k, table->num_flows_10k,
+ table->num_flows_20k, table->num_flows_50k, table->avg_rate,
+ table->max_flow_rate, table->max_flow_rate_flow_hash, resulting_limit,
+ identifier, ident->id);
+
+ if (table->max_flow_rate > 0) {
+ printlog(LOG_WARN, "%.3f\n", (double) table->rate / (double) table->max_flow_rate);
+ } else {
+ printlog(LOG_WARN, "0\n");
+ }
+
+ /* Print to the screen in debug mode. */
+ if (system_loglevel == LOG_DEBUG) {
+ printf("Local Rate: %d, Ideal Weight: %.3f, Local Weight: %.3f, Total Weight: %.3f\n",
+ table->rate, ideal_weight, ident->localweight, total_weight);
+ }
+}
+
+static uint32_t allocate_fps(identity_t *ident, double total_weight,
+ common_accounting_t *table, const char *identifier) {
+
+ uint32_t resulting_limit = 0;
+ double ideal_weight = 0.0;
+ double peer_weights = total_weight - ident->last_localweight;
+
+ /* Keep track of these for measurements & comparisons only. */
+ double ideal_under = 0.0;
+ double ideal_over = 0.0;
+
+ /* Weight sanity. */
+ if (peer_weights < 0.0) {
+ peer_weights = 0.0;
+ }
+
+ if (ident->dampen_state == DAMPEN_TEST) {
+ int64_t rate_delta = (int64_t) table->inst_rate - (int64_t) table->last_inst_rate;
+ double threshold = (double) ident->limit * (double) LARGE_INCREASE_PERCENTAGE / 10;
+
+ if (rate_delta > threshold) {
+ ident->dampen_state = DAMPEN_PASSED;
+ } else {
+ ident->dampen_state = DAMPEN_FAILED;
+ }
+ }
+
+ /* Rate/weight sanity. */
+ if (table->rate <= 0) {
+ ideal_weight = 0.0;
+ }
+
+ /* Under the limit OR we failed our dampening test OR our current
+ * outgoing traffic rate is under the low "flowstart" watermark. */
+ else if (ident->dampen_state == DAMPEN_FAILED ||
+ table->rate < close_enough(ident->locallimit)) {
+#if 0
+ || ident->flowstart) {
+ uint32_t target_rate = table->rate;
+
+ if (ident->flowstart) {
+ target_rate *= 4;
+
+ if (table->rate >= FLOW_START_THRESHOLD) {
+ ident->flowstart = false;
+ }
+ } else {
+ /* June 16, 2008 (KCW)
+ * ident->flowstart gets set initially to one, but it is never set again. However,
+ * if a limiter gets flows and then the number of flows drops to zero, it has trouble
+ * increasing the limit again. */
+ if (table->rate < FLOW_START_THRESHOLD) {
+ ident->flowstart = true;
+ }
+ }
+ Old flowstart code.
+#endif
+
+ /* Boost low-limits so that they have room to grow. */
+ if (table->rate < FLOW_START_THRESHOLD) {
+ ideal_weight = ideal_under = allocate_fps_under_limit(ident, table->rate * 4, peer_weights);
+ } else {
+ ideal_weight = ideal_under = allocate_fps_under_limit(ident, table->rate, peer_weights);
+ }
+
+ ideal_over = allocate_fps_over_limit(ident);
+
+ if (ideal_over < ideal_under) {
+ /* Degenerate case in which the agressive weight calculation was
+ * actually less than the under-the-limit case. Use it instead
+ * and skip the dampening check in the next interval. */
+ ideal_weight = ideal_over;
+ ident->dampen_state = DAMPEN_SKIP;
+ } else {
+ ident->dampen_state = DAMPEN_NONE;
+ }
+
+ /* Apply EWMA. */
+ ident->localweight = (ident->localweight * ident->ewma_weight +
+ ideal_weight * (1 - ident->ewma_weight));
+ }
+
+ /* At or over the limit. Use the aggressive weight calculation. */
+ else {
+ double portion_last_interval = 0.0;
+ double portion_this_interval = 0.0;
+
+ ideal_weight = ideal_over = allocate_fps_over_limit(ident);
+ ideal_under = allocate_fps_under_limit(ident, table->rate, peer_weights);
+
+ /* Apply EWMA. */
+ ident->localweight = (ident->localweight * ident->ewma_weight +
+ ideal_weight * (1 - ident->ewma_weight));
+
+ /* Now check whether the result of the aggressive weight calculation
+ * increases our portion of the weight "too much", in which case we
+ * dampen it. */
+
+ /* Our portion of weight in the whole system during the last interval.*/
+ portion_last_interval = ident->last_localweight / total_weight;
+
+ /* Our proposed portion of weight for the current interval. */
+ portion_this_interval = ident->localweight / (peer_weights + ident->localweight);
+
+ if (ident->dampen_state == DAMPEN_NONE &&
+ (portion_this_interval - portion_last_interval > LARGE_INCREASE_PERCENTAGE)) {
+ ident->localweight = ident->last_localweight + (LARGE_INCREASE_PERCENTAGE * total_weight);
+ ident->dampen_state = DAMPEN_TEST;
+ } else {
+ ident->dampen_state = DAMPEN_SKIP;
+ }
+ }
+
+ /* Add the weight calculated in this interval to the total. */
+ ident->total_weight = total_weight = ident->localweight + peer_weights;
+
+ /* Convert weight value into a rate limit. If there is no measureable
+ * weight, do a L/n allocation. */
+ if (total_weight > 0) {
+ resulting_limit = (uint32_t) (ident->localweight * ident->limit / total_weight);
+ } else {
+ resulting_limit = (uint32_t) (ident->limit / (ident->comm.remote_node_count + 1));
+ }
+
+ print_statistics(ident, ideal_weight, total_weight, ident->localweight,
+ identifier, table, resulting_limit);
+
+ return resulting_limit;
+}
+
+#ifdef SHADOW_ACCTING
+
+/* Runs through the allocate functionality without making any state changes to
+ * the identity. Useful for comparisons, especially for comparing standard
+ * and sample&hold accounting schemes. */
+static void allocate_fps_pretend(identity_t *ident, double total_weight,
+ common_accounting_t *table, const char *identifier) {
+
+ uint32_t resulting_limit = 0;
+ double ideal_weight = 0.0;
+ double peer_weights = total_weight - ident->last_localweight_copy;
+ double ideal_under = 0.0;
+ double ideal_over = 0.0;
+
+ if (peer_weights < 0.0) {
+ peer_weights = 0.0;
+ }
+
+ if (ident->dampen_state_copy == DAMPEN_TEST) {
+ int64_t rate_delta = (int64_t) table->inst_rate - (int64_t) table->last_inst_rate;
+ double threshold = (double) ident->limit * (double) LARGE_INCREASE_PERCENTAGE / 10;
+
+ if (rate_delta > threshold) {
+ ident->dampen_state_copy = DAMPEN_PASSED;
+ } else {
+ ident->dampen_state_copy = DAMPEN_FAILED;
+ }
+ }
+
+ /* Rate/weight sanity. */
+ if (table->rate <= 0) {
+ ideal_weight = 0.0;
+ }
+
+ /* Under the limit OR we failed our dampening test OR our current
+ * outgoing traffic rate is under the low "flowstart" watermark. */
+ else if (ident->dampen_state_copy == DAMPEN_FAILED ||
+ table->rate < close_enough(ident->locallimit)) {
+
+ /* Boost low-limits so that they have room to grow. */
+ if (table->rate < FLOW_START_THRESHOLD) {
+ ideal_weight = ideal_under = allocate_fps_under_limit(ident, table->rate * 4, peer_weights);
+ } else {
+ ideal_weight = ideal_under = allocate_fps_under_limit(ident, table->rate, peer_weights);
+ }
+
+ ideal_over = allocate_fps_over_limit(ident);
+
+ if (ideal_over < ideal_under) {
+ /* Degenerate case in which the agressive weight calculation was
+ * actually less than the under-the-limit case. Use it instead
+ * and skip the dampening check in the next interval. */
+ ideal_weight = ideal_over;
+ ident->dampen_state_copy = DAMPEN_SKIP;
+ } else {
+ ident->dampen_state_copy = DAMPEN_NONE;
+ }
+
+ /* Apply EWMA. */
+ ident->localweight_copy = (ident->localweight_copy * ident->ewma_weight +
+ ideal_weight * (1 - ident->ewma_weight));
+ }
+
+ /* At or over the limit. Use the aggressive weight calculation. */
+ else {
+ double portion_last_interval = 0.0;
+ double portion_this_interval = 0.0;
+
+ ideal_weight = ideal_over = allocate_fps_over_limit(ident);
+ ideal_under = allocate_fps_under_limit(ident, table->rate, peer_weights);
+
+ /* Apply EWMA. */
+ ident->localweight_copy = (ident->localweight_copy * ident->ewma_weight +
+ ideal_weight * (1 - ident->ewma_weight));
+
+ /* Now check whether the result of the aggressive weight calculation
+ * increases our portion of the weight "too much", in which case we
+ * dampen it. */
+
+ /* Our portion of weight in the whole system during the last interval.*/
+ portion_last_interval = ident->last_localweight / total_weight;
+
+ /* Our proposed portion of weight for the current interval. */
+ portion_this_interval = ident->localweight_copy / (peer_weights + ident->localweight_copy);
+
+ if (ident->dampen_state_copy == DAMPEN_NONE &&
+ (portion_this_interval - portion_last_interval > LARGE_INCREASE_PERCENTAGE)) {
+ ident->localweight_copy = ident->last_localweight + (LARGE_INCREASE_PERCENTAGE * total_weight);
+ ident->dampen_state_copy = DAMPEN_TEST;
+ } else {
+ ident->dampen_state_copy = DAMPEN_SKIP;
+ }
+ }
+
+ /* Add the weight calculated in this interval to the total. */
+ total_weight = ident->localweight_copy + peer_weights;
+
+ /* Convert weight value into a rate limit. If there is no measureable
+ * weight, do a L/n allocation. */
+ if (total_weight > 0) {
+ resulting_limit = (uint32_t) (ident->localweight_copy * ident->limit / total_weight);
+ } else {
+ resulting_limit = (uint32_t) (ident->limit / (ident->comm.remote_node_count + 1));
+ }
+
+ print_statistics(ident, ideal_weight, total_weight, ident->localweight_copy,
+ identifier, table, resulting_limit);
+}
+
+#endif
+