diff options
Diffstat (limited to 'hicn-light/src/hicn/strategies/load_balancer.c')
-rw-r--r-- | hicn-light/src/hicn/strategies/load_balancer.c | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/strategies/load_balancer.c b/hicn-light/src/hicn/strategies/load_balancer.c new file mode 100644 index 000000000..0e1a170f7 --- /dev/null +++ b/hicn-light/src/hicn/strategies/load_balancer.c @@ -0,0 +1,148 @@ +/* + * Copyright (c) 2021-2022 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <hicn/hicn-light/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <hicn/core/strategy.h> +#include <hicn/core/strategy_vft.h> +#include <hicn/core/nexthops.h> +#include <hicn/core/fib_entry.h> + +#include "load_balancer.h" + +#define AVG_PI_THRESHOLD 1e-3 +#define AVG_PI_MIN 0.1 + +#define ALPHA 0.9 + +/* Shorthand */ +#define nexthop_state_t strategy_load_balancer_nexthop_state_t +#define nexthop_state(nexthops, i) (&nexthops->state[i].load_balancer) + +static const nexthop_state_t NEXTHOP_STATE_INIT = { + .pi = 0, + .avg_pi = 0.0, + .weight = 1, +}; + +static inline void update_state(nexthop_state_t *state) { + state->avg_pi = (state->avg_pi * ALPHA) + (state->pi * 1 - ALPHA); + if (state->avg_pi < AVG_PI_THRESHOLD) state->avg_pi = AVG_PI_MIN; + state->weight = 1 / state->avg_pi; +} + +static inline void update_state_inc(nexthop_state_t *state) { + state->pi++; + update_state(state); +} + +static inline void update_state_dec(nexthop_state_t *state) { + if (state->pi > 0) state->pi--; + update_state(state); +} + +static inline void reset_all(nexthops_t *nexthops) { + nexthops_enumerate(nexthops, i, nexthop, { + (void)nexthop; + nexthops->state[i].load_balancer = NEXTHOP_STATE_INIT; + }); +} + +static int strategy_load_balancer_initialize(strategy_entry_t *entry, + const void *forwarder) { + /* No reset, this will be done when a nexthop is added */ + entry->forwarder = forwarder; + return 0; +} + +static int strategy_load_balancer_finalize(strategy_entry_t *entry) { + /* Nothing to do */ + return 0; +} + +static int strategy_load_balancer_add_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* We reset the state of all nexthops */ + reset_all(nexthops); + return 0; +} + +static int strategy_load_balancer_remove_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + reset_all(nexthops); + return 0; +} + +static nexthops_t *strategy_load_balancer_lookup_nexthops( + strategy_entry_t *entry, nexthops_t *nexthops, const msgbuf_t *msgbuf) { + if (nexthops_get_curlen(nexthops) == 0) return nexthops; + /* Compute the sum of weights of potential next hops */ + double sum = 0; + nexthops_enumerate(nexthops, i, nexthop, { + (void)nexthop; + sum += nexthops_state(nexthops, i).load_balancer.weight; + }); + + /* Perform weighted random selection */ + double distance = (double)rand() * sum / ((double)RAND_MAX + 1); + + nexthops_enumerate(nexthops, i, nexthop, { + distance -= nexthop_state(nexthops, i)->weight; + if (distance < 0) { + nexthops_select(nexthops, i); + update_state_inc(nexthop_state(nexthops, i)); + break; + } + }); + return nexthops; +} + +static int strategy_load_balancer_on_timeout( + strategy_entry_t *entry, nexthops_t *nexthops, + const nexthops_t *timeout_nexthops) { + /* + * As we have few nexthops in FIB entry, and even fewer selected ones in + * nexthops, we can allow for linear search that will be very efficient + * CPU-wise. + */ + nexthops_foreach(timeout_nexthops, timeout_nexthop, { + nexthops_enumerate(nexthops, i, nexthop, { + if (nexthop == timeout_nexthop) + update_state_dec(nexthop_state(nexthops, i)); + }); + }); + return 0; +} + +static int strategy_load_balancer_on_data(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *data_nexthops, + const msgbuf_t *msgbuf, + Ticks pitEntryCreation, + Ticks objReception) { + return strategy_load_balancer_on_timeout(entry, nexthops, data_nexthops); +} + +#undef nexthop_state_t + +DECLARE_STRATEGY(load_balancer); + +#undef nexthop_state_t |