diff options
Diffstat (limited to 'hicn-light/src/hicn/strategies')
24 files changed, 1307 insertions, 2212 deletions
diff --git a/hicn-light/src/hicn/strategies/CMakeLists.txt b/hicn-light/src/hicn/strategies/CMakeLists.txt index 886aa137c..754974ee4 100644 --- a/hicn-light/src/hicn/strategies/CMakeLists.txt +++ b/hicn-light/src/hicn/strategies/CMakeLists.txt @@ -1,4 +1,4 @@ -# Copyright (c) 2017-2019 Cisco and/or its affiliates. +# 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: @@ -12,20 +12,23 @@ # limitations under the License. list(APPEND HEADER_FILES - ${CMAKE_CURRENT_SOURCE_DIR}/strategyImpl.h - ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancer.h - ${CMAKE_CURRENT_SOURCE_DIR}/lowLatency.h - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.h - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateLowLatency.h - ${CMAKE_CURRENT_SOURCE_DIR}/rnd.h + ${CMAKE_CURRENT_SOURCE_DIR}/load_balancer.h + ${CMAKE_CURRENT_SOURCE_DIR}/random.h + ${CMAKE_CURRENT_SOURCE_DIR}/replication.h + ${CMAKE_CURRENT_SOURCE_DIR}/best_path.h + ${CMAKE_CURRENT_SOURCE_DIR}/local_prefixes.h + ${CMAKE_CURRENT_SOURCE_DIR}/probe_generator.h + ${CMAKE_CURRENT_SOURCE_DIR}/local_remote.h ) list(APPEND SOURCE_FILES - ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancer.c - ${CMAKE_CURRENT_SOURCE_DIR}/lowLatency.c - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.c - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateLowLatency.c - ${CMAKE_CURRENT_SOURCE_DIR}/rnd.c + ${CMAKE_CURRENT_SOURCE_DIR}/load_balancer.c + ${CMAKE_CURRENT_SOURCE_DIR}/random.c + ${CMAKE_CURRENT_SOURCE_DIR}/replication.c + ${CMAKE_CURRENT_SOURCE_DIR}/best_path.c + ${CMAKE_CURRENT_SOURCE_DIR}/local_prefixes.c + ${CMAKE_CURRENT_SOURCE_DIR}/probe_generator.c + ${CMAKE_CURRENT_SOURCE_DIR}/local_remote.c ) set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) diff --git a/hicn-light/src/hicn/strategies/best_path.c b/hicn-light/src/hicn/strategies/best_path.c new file mode 100644 index 000000000..9223cc8ac --- /dev/null +++ b/hicn-light/src/hicn/strategies/best_path.c @@ -0,0 +1,353 @@ +/* + * 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 <math.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <hicn/hicn-light/config.h> + +#include <hicn/core/forwarder.h> +#include <hicn/core/nexthops.h> +#include <hicn/core/strategy.h> +#include <hicn/core/strategy_vft.h> + +#include "best_path.h" + +#define MAX_NEXTHOP_COST 100 +#define MAX_RTT_ALLOWED 300.0 // ms +#define MAX_LOSSES_ALLOWED 0.4 // 40% + +#define MAX_PROBING_DURATION 5000 // ticks (= ms) +#define PROBES_WAINTING_TIME 500 // ticks (= ms) +#define MAX_PROBES 50 + +/* Shorthand */ +#define nexthop_state_t strategy_bestpath_nexthop_state_t +#define strategy_state_t strategy_bestpath_state_t +#define nexthop_state(nexthops, i) (&nexthops->state[i].bestpath) + +// nexthop state functions + +static const nexthop_state_t NEXTHOP_STATE_INIT = { + .sent_probes = 0, + .recv_probes = 0, + .rtt_sum = 0, +}; + +static inline unsigned int get_sent_probes(nexthop_state_t *state) { + return state->sent_probes; +} + +static inline unsigned int inc_sent_probes(nexthop_state_t *state) { + state->sent_probes++; + return state->sent_probes; +} + +static inline void add_rtt_sample(nexthop_state_t *state, Ticks rtt) { + state->recv_probes++; + state->rtt_sum += rtt; +} + +static inline unsigned int get_nexthop_cost(nexthop_state_t *state) { + if (state->recv_probes == 0) + return 100; // we have no info for this nexthop, return max cost + + assert(state->recv_probes <= state->sent_probes); + + double rtt = (double)state->rtt_sum / (double)state->recv_probes; + double delay_cost = rtt / MAX_RTT_ALLOWED; + if (delay_cost > 1) delay_cost = 1; + + double loss_rate = (double)(state->sent_probes - state->recv_probes) / + (double)state->sent_probes; + double loss_cost = loss_rate / MAX_LOSSES_ALLOWED; + if (loss_cost > 1) loss_cost = 1; + + double total_cost = delay_cost * 0.5 + loss_cost * 0.5; + return round(total_cost * 100); +} + +// options functions +static void bestpath_update_remote_node(strategy_entry_t *entry, + nexthops_t *nexthops) { + strategy_state_t *state = &entry->state.bestpath; + strategy_bestpath_options_t *options = &entry->options.bestpath; + off_t offset = nexthops_find(nexthops, state->best_nexthop); + + /* Backup flags and cur_len: because our code is called from + * strategy_on_data / check_stop_probing / stop_probing + * which does not expect the nexthop flags to be modified. + */ + uint_fast32_t flags = nexthops->flags; + size_t cur_len = nexthops_get_curlen(nexthops); + + nexthops_select(nexthops, offset); + update_remote_node_paths(nexthops, entry->forwarder, options->local_prefixes); + + /* Restore flags & curlen */ + nexthops->flags = flags; + nexthops->cur_elts = cur_len; +} + +// probing functions + +static void start_probing(strategy_entry_t *entry) { + strategy_state_t *state = &entry->state.bestpath; + if (state->probing_state == PROBING_OFF) { + state->probing_state = PROBING_ON; + state->probing_time = ticks_now(); + } +} + +static void stop_probing(strategy_entry_t *entry, nexthops_t *nexthops) { + strategy_state_t *state = &entry->state.bestpath; + nexthop_t best_nexthop; + best_nexthop = state->best_nexthop; + unsigned int min_cost = ~0; + unsigned current_nexthop_cost = ~0; + + nexthops_enumerate(nexthops, i, nexthop, { + unsigned int cost = get_nexthop_cost(nexthop_state(nexthops, i)); + if (cost < min_cost) { + min_cost = cost; + best_nexthop = nexthop; + } + if (nexthop == state->best_nexthop) current_nexthop_cost = cost; + + nexthops->state[i].bestpath = NEXTHOP_STATE_INIT; + }); + + if (best_nexthop != state->best_nexthop) { + if (current_nexthop_cost > min_cost) { + // update best face + state->best_nexthop = best_nexthop; + } + } + + // always update remote node + bestpath_update_remote_node(entry, nexthops); + + state->probing_state = PROBING_OFF; + delete_all_probes(state->pg); +} + +static void check_stop_probing(strategy_entry_t *entry, nexthops_t *nexthops) { + strategy_state_t *state = &entry->state.bestpath; + if (state->probing_state == PROBING_OFF) return; + + if (state->probing_state == PROBING_ON) { + Ticks probing_duration = ticks_now() - state->probing_time; + if (probing_duration >= MAX_PROBING_DURATION) { + state->probing_state = PROBING_ENDING; + state->probing_time = ticks_now(); + } + return; + } + + if (state->probing_state == SENT_MAX_PROBES) { + state->probing_state = PROBING_ENDING; + state->probing_time = ticks_now(); + return; + } + + if (state->probing_state == PROBING_ENDING) { + Ticks ending_duration = ticks_now() - state->probing_time; + if (ending_duration >= PROBES_WAINTING_TIME) stop_probing(entry, nexthops); + } +} + +static void send_probes(strategy_entry_t *entry, nexthops_t *nexthops, + const msgbuf_t *msgbuf) { + strategy_state_t *state = &entry->state.bestpath; + + bool sent_max_probes = false; + nexthops_enumerate(nexthops, i, nexthop, { + if (get_sent_probes(nexthop_state(nexthops, i)) < MAX_PROBES) { + int res = generate_probe(state->pg, msgbuf, entry->forwarder, nexthop); + if (res >= 0) inc_sent_probes(nexthop_state(nexthops, i)); + } else { + sent_max_probes = true; + } + }); + + if (sent_max_probes) { + state->probing_state = SENT_MAX_PROBES; + check_stop_probing(entry, nexthops); + } +} + +static void init_strategy_state(strategy_state_t *state) { + state->best_nexthop = ~0; + state->probing_state = PROBING_OFF; + state->pg = create_probe_generator(); +} + +// strategy functions +static int strategy_bestpath_initialize(strategy_entry_t *entry, + const void *forwarder) { + if (entry->forwarder == NULL) { + srand((unsigned int)time(NULL)); + entry->forwarder = forwarder; + init_strategy_state(&entry->state.bestpath); + } else { + strategy_state_t *state = &entry->state.bestpath; + if (!state->pg) { + // the previous strategy was a different one + init_strategy_state(state); + } else { + // all set, start probing + start_probing(entry); + } + } + return 0; +} + +static int strategy_bestpath_finalize(strategy_entry_t *entry) { + strategy_state_t *state = &entry->state.bestpath; + free_local_prefixes(entry->options.bestpath.local_prefixes); + destroy_probe_generator(state->pg); + return 0; +} + +static int strategy_bestpath_add_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, off_t offset) { + // reset the strategy state + nexthops->state[offset].bestpath = NEXTHOP_STATE_INIT; + return 0; +} + +static int strategy_bestpath_remove_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* Nothing to do */ + return 0; +} + +static nexthops_t *strategy_bestpath_lookup_nexthops(strategy_entry_t *entry, + nexthops_t *nexthops, + const msgbuf_t *msgbuf) { + size_t nexthops_len = nexthops_get_curlen(nexthops); + if (nexthops_len == 0) { + // nexthops is empty, return + return nexthops; + } + + strategy_state_t *state = &entry->state.bestpath; + off_t best_nexthop_offset = nexthops_find(nexthops, state->best_nexthop); + + // TODO explain the purpose of this test + if (nexthops_len == 1) { + nexthop_t nh = nexthops_get_one(nexthops); + if (state->best_nexthop != nh) { + state->best_nexthop = nh; + bestpath_update_remote_node(entry, nexthops); + } + return nexthops; + } + + if (state->best_nexthop == ~0 || best_nexthop_offset == INVALID_NEXTHOP) { + state->best_nexthop = nexthops_get_one(nexthops); + best_nexthop_offset = nexthops_find(nexthops, state->best_nexthop); + bestpath_update_remote_node(entry, nexthops); + // we have probe only in case the number of face is > 1 + start_probing(entry); + // bestpath_update_remote_node sets the nexthops. in case of probing we want + // to send the packets on all faces, so we reset the nexthops here + nexthops_reset(nexthops); + } + + if (state->probing_state == PROBING_ON) { + // send a probe for each interest received + send_probes(entry, nexthops, msgbuf); + + uint32_t suffix = hicn_name_get_suffix(msgbuf_get_name(msgbuf)); + if (suffix >= MIN_PROBE_SUFFIX && suffix <= MAX_PROBE_SUFFIX) { + // this packet is a probe from the transport, so register it + Ticks time = get_probe_send_time(state->pg, suffix); + if (time == 0) { + // a probe with the same seq number is not pending, send the packet + // the stats for this probe will be collected by the transport + register_probe(state->pg, suffix); + } else { + // this probe is already pending. avoid duplicates and drop it + nexthops->flags = ~0; + nexthops->cur_elts = 0; + } + } + } else { + // we are not probing anymore. if in probing ending state (wait for probes + // to come back) keep replicating traffic, otherwise and on best path + if (state->probing_state != PROBING_ENDING) + nexthops_select(nexthops, best_nexthop_offset); + } + + // in case we are still probing send all interest on all paths + // so do not select any next hop. + // XXX in this transition phase should we replicate also at the + // server side? + return nexthops; +} + +static int strategy_bestpath_on_data(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *data_nexthops, + const msgbuf_t *msgbuf, + Ticks pitEntryCreation, + Ticks objReception) { + strategy_state_t *state = &entry->state.bestpath; + if (state->probing_state == PROBING_OFF) return 0; + + uint32_t seq = hicn_name_get_suffix(msgbuf_get_name(msgbuf)); + if (seq >= MIN_PROBE_SUFFIX && seq <= MAX_PROBE_SUFFIX) { + if (pitEntryCreation != 0) { + // this is not a probe sent by the forwader. do not use it in the probing + // statisitcs but remove it from the map if it exists + delete_probe(state->pg, seq); + return 0; + } + + Ticks send_time = get_probe_send_time(state->pg, seq); + if (send_time != 0) { + Ticks rtt = ticks_now() - send_time; + delete_probe(state->pg, seq); + nexthops_enumerate(data_nexthops, i, nexthop, { + off_t pos = nexthops_find(nexthops, nexthop); + add_rtt_sample(nexthop_state(nexthops, pos), rtt); + }); + } + } + + check_stop_probing(entry, nexthops); + + return 0; +} + +static int strategy_bestpath_on_timeout(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *timeout_nexthops) { + /* Nothing to do */ + return 0; +} + +#undef nexthop_state_t +#undef strategy_state_t + +DECLARE_STRATEGY(bestpath); + +#undef nexthop_state_t +#undef strategy_state_t diff --git a/hicn-light/src/hicn/strategies/best_path.h b/hicn-light/src/hicn/strategies/best_path.h new file mode 100644 index 000000000..206214579 --- /dev/null +++ b/hicn-light/src/hicn/strategies/best_path.h @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * Forward on a single path. Every time the strategy is reset with a command the + * forwarder starts to probe the available paths matching the probes on the + * original flow. if after the probing phase a better path exists (lower + * latency, less losses) the forwarder switch path, otherwise does nothing + */ + +#ifndef HICNLIGHT_STRATEGY_BESTPATH_H +#define HICNLIGHT_STRATEGY_BESTPATH_H + +#include "probe_generator.h" +#include "local_prefixes.h" + +typedef enum { + PROBING_OFF, + PROBING_ON, + SENT_MAX_PROBES, + PROBING_ENDING, // waiting for probes to come back + UNKWNOWN, +} probing_state_t; + +typedef struct { + // number or probes sent during a probing phase + unsigned int sent_probes; + // number or probes received during a probing phase + unsigned int recv_probes; + // sum of all rtt collected + Ticks rtt_sum; +} strategy_bestpath_nexthop_state_t; + +typedef struct { + unsigned best_nexthop; + Ticks probing_time; + probing_state_t probing_state; + probe_generator_t *pg; +} strategy_bestpath_state_t; + +typedef struct { + local_prefixes_t *local_prefixes; +} strategy_bestpath_options_t; + +#endif /* HICNLIGHT_STRATEGY_BESTPATH_H */ diff --git a/hicn-light/src/hicn/strategies/loadBalancer.c b/hicn-light/src/hicn/strategies/loadBalancer.c deleted file mode 100644 index 82b5a6103..000000000 --- a/hicn-light/src/hicn/strategies/loadBalancer.c +++ /dev/null @@ -1,369 +0,0 @@ -/* - * Copyright (c) 2017-2019 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 <parc/assert/parc_Assert.h> - -#include <parc/algol/parc_HashMap.h> -#include <parc/algol/parc_Memory.h> -#include <parc/algol/parc_Object.h> -#include <parc/algol/parc_Unsigned.h> - -#include <hicn/strategies/loadBalancer.h> -#include <hicn/strategies/nexthopState.h> - -static void _strategyLoadBalancer_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception); -static void _strategyLoadBalancer_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId); -static NumberSet *_strategyLoadBalancer_LookupNexthop( - StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage); -#ifndef WITH_POLICY -static NumberSet *_strategyLoadBalancer_ReturnNexthops(StrategyImpl *strategy); -static unsigned _strategyLoadBalancer_CountNexthops(StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ -static void _strategyLoadBalancer_AddNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancer_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancer_ImplDestroy(StrategyImpl **strategyPtr); -static strategy_type _strategyLoadBalancer_GetStrategy(StrategyImpl *strategy); - -static StrategyImpl _template = { - .context = NULL, - .receiveObject = &_strategyLoadBalancer_ReceiveObject, - .onTimeout = &_strategyLoadBalancer_OnTimeout, - .lookupNexthop = &_strategyLoadBalancer_LookupNexthop, -#ifndef WITH_POLICY - .returnNexthops = &_strategyLoadBalancer_ReturnNexthops, - .countNexthops = &_strategyLoadBalancer_CountNexthops, -#endif /* ! WITH_POLICY */ - .addNexthop = &_strategyLoadBalancer_AddNexthop, - .removeNexthop = &_strategyLoadBalancer_RemoveNexthop, - .destroy = &_strategyLoadBalancer_ImplDestroy, - .getStrategy = &_strategyLoadBalancer_GetStrategy, -}; - -struct strategy_load_balancer; -typedef struct strategy_load_balancer StrategyLoadBalancer; - -struct strategy_load_balancer { -#ifndef WITH_POLICY - double weights_sum; -#endif /* ! WITH_POLICY */ - // hash map from connectionId to StrategyNexthopState - PARCHashMap *strategy_state; -#ifndef WITH_POLICY - NumberSet *nexthops; -#endif /* ! WITH_POLICY */ -}; - -StrategyImpl *strategyLoadBalancer_Create() { - StrategyLoadBalancer *strategy = - parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancer)); - parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyLoadBalancer)); - -#ifndef WITH_POLICY - strategy->weights_sum = 0.0; -#endif /* ! WITH_POLICY */ - strategy->strategy_state = parcHashMap_Create(); -#ifndef WITH_POLICY - strategy->nexthops = numberSet_Create(); -#endif /* ! WITH_POLICY */ - srand((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - - return impl; -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyLoadBalancer_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_LOADBALANCER; -} - -static void _update_Stats(StrategyLoadBalancer *strategy, - StrategyNexthopState *state, bool inc) { - const double ALPHA = 0.9; -#ifdef WITH_POLICY - strategyNexthopState_UpdateState(state, inc, ALPHA); -#else - double w = strategyNexthopState_GetWeight(state); - strategy->weights_sum -= w; - w = strategyNexthopState_UpdateState(state, inc, ALPHA); - strategy->weights_sum += w; -#endif /* WITH_POLICY */ -} - -#ifndef WITH_POLICY -static unsigned _select_Nexthop(StrategyLoadBalancer *strategy) { - double rnd = (double)rand() / (double)RAND_MAX; - double start_range = 0.0; - - PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); - - unsigned nexthop = 100000; - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - const StrategyNexthopState *elem = - parcHashMap_Get(strategy->strategy_state, cid); - - double w = strategyNexthopState_GetWeight(elem); - - double prob = w / strategy->weights_sum; - if ((rnd >= start_range) && (rnd <= (start_range + prob))) { - nexthop = parcUnsigned_GetUnsigned(cid); - break; - } else { - start_range += prob; - } - } - - parcIterator_Release(&it); - - // if no face is selected by the algorithm (for example because of a wrong - // round in the weights) we may always select the last face here. Double check - // this! - return nexthop; -} -#endif /* ! WITH_POLICY */ - -static void _strategyLoadBalancer_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception) { - _strategyLoadBalancer_OnTimeout(strategy, egressId); -} - -static void _strategyLoadBalancer_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopState *state = - parcHashMap_Get(lb->strategy_state, cid); - if (state != NULL) { - _update_Stats(lb, (StrategyNexthopState *)state, false); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } -} - -static NumberSet *_strategyLoadBalancer_LookupNexthop( - StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - NumberSet *outList = numberSet_Create(); - -#ifdef WITH_POLICY - /* Compute the sum of weights of potential next hops */ - double sum = 0; - for (unsigned i = 0; i < numberSet_Length(nexthops); i++) { - PARCUnsigned *cid = parcUnsigned_Create(numberSet_GetItem(nexthops, i)); - const StrategyNexthopState *elem = - parcHashMap_Get(lb->strategy_state, cid); - parcUnsigned_Release(&cid); - if (!elem) - continue; - sum += strategyNexthopState_GetWeight(elem); - } - - /* Perform weighted random selection */ - double distance = (double)rand() * sum / ((double)RAND_MAX + 1); - - for (unsigned i = 0; i < numberSet_Length(nexthops); i++) { - PARCUnsigned *cid = parcUnsigned_Create(numberSet_GetItem(nexthops, i)); - const StrategyNexthopState *state = - parcHashMap_Get(lb->strategy_state, cid); - if (!state) { - parcUnsigned_Release(&cid); - continue; - } - distance -= strategyNexthopState_GetWeight(state); - if (distance < 0) { - numberSet_Add(outList, parcUnsigned_GetUnsigned(cid)); - _update_Stats(lb, (StrategyNexthopState *)state, true); - parcUnsigned_Release(&cid); - break; - } - parcUnsigned_Release(&cid); - } -#else - unsigned in_connection = message_GetIngressConnectionId(interestMessage); - PARCUnsigned *in = parcUnsigned_Create(in_connection); - - unsigned mapSize = (unsigned)parcHashMap_Size(lb->strategy_state); - - if ((mapSize == 0) || - ((mapSize == 1) && parcHashMap_Contains(lb->strategy_state, in))) { - // there are no output faces or the input face is also the only output face. - // return null to avoid loops - parcUnsigned_Release(&in); - return outList; - } - - unsigned out_connection; - do { - out_connection = _select_Nexthop(lb); - } while (out_connection == in_connection); - - PARCUnsigned *out = parcUnsigned_Create(out_connection); - - const StrategyNexthopState *state = parcHashMap_Get(lb->strategy_state, out); - if (state == NULL) { - // this is an error and should not happen! - parcTrapNotImplemented( - "Try to send an interest on a face that does not exists"); - } - - _update_Stats(lb, (StrategyNexthopState *)state, true); - - parcUnsigned_Release(&in); - parcUnsigned_Release(&out); - - numberSet_Add(outList, out_connection); -#endif /* WITH_POLICY */ - - return outList; -} - -#ifndef WITH_POLICY -static NumberSet *_strategyLoadBalancer_ReturnNexthops(StrategyImpl *strategy) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - return lb->nexthops; -} - -unsigned _strategyLoadBalancer_CountNexthops(StrategyImpl *strategy) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - return (unsigned)numberSet_Length(lb->nexthops); -} -#endif /* ! WITH_POLICY */ - -static void _strategyLoadBalancer_resetState(StrategyImpl *strategy) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; -#ifndef WITH_POLICY - lb->weights_sum = 0.0; -#endif/* ! WITH_POLICY */ - PARCIterator *it = parcHashMap_CreateKeyIterator(lb->strategy_state); - - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - StrategyNexthopState *elem = - (StrategyNexthopState *)parcHashMap_Get(lb->strategy_state, cid); - - strategyNexthopState_Reset(elem); -#ifndef WITH_POLICY - lb->weights_sum += strategyNexthopState_GetWeight(elem); -#endif /* ! WITH_POLICY */ - } - - parcIterator_Release(&it); -} - -static void _strategyLoadBalancer_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - - if (!parcHashMap_Contains(lb->strategy_state, cid)) { - StrategyNexthopState *state = strategyNexthopState_Create(); - parcHashMap_Put(lb->strategy_state, cid, state); -#ifndef WITH_POLICY - numberSet_Add(lb->nexthops, connectionId); -#endif /* WITH_POLICY */ - _strategyLoadBalancer_resetState(strategy); - } - parcUnsigned_Release(&cid); -} - -static void _strategyLoadBalancer_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - if (parcHashMap_Contains(lb->strategy_state, cid)) { - StrategyNexthopState *state = - (StrategyNexthopState *)parcHashMap_Get(lb->strategy_state, cid); - parcObject_Release((void**)&state); - - parcHashMap_Remove(lb->strategy_state, cid); -#ifndef WITH_POLICY - numberSet_Remove(lb->nexthops, connectionId); -#endif /* WITH_POLICY */ - _strategyLoadBalancer_resetState(strategy); - } - - parcUnsigned_Release(&cid); -} - -static void _strategyLoadBalancer_ImplDestroy(StrategyImpl **strategyPtr) { - parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*strategyPtr, - "Parameter must dereference to non-null pointer"); - - StrategyImpl *impl = *strategyPtr; - StrategyLoadBalancer *strategy = (StrategyLoadBalancer *)impl->context; - if (parcHashMap_Size(strategy->strategy_state) > 0) { - PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - StrategyNexthopState *state = - (StrategyNexthopState *) parcHashMap_Get(strategy->strategy_state, cid); - parcObject_Release((void **) &state); - } - parcIterator_Release(&it); - } - - parcHashMap_Release(&(strategy->strategy_state)); -#ifndef WITH_POLICY - numberSet_Release(&(strategy->nexthops)); -#endif /* ! WITH_POLICY */ - - parcMemory_Deallocate((void **) &strategy); - parcMemory_Deallocate((void **) &impl); - *strategyPtr = NULL; -} 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 diff --git a/hicn-light/src/hicn/strategies/loadBalancer.h b/hicn-light/src/hicn/strategies/load_balancer.h index 74920768d..f7447d928 100644 --- a/hicn-light/src/hicn/strategies/loadBalancer.h +++ b/hicn-light/src/hicn/strategies/load_balancer.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -17,11 +17,21 @@ * Forward on the less loaded path */ -#ifndef loadBalancer_h -#define loadBalancer_h +#ifndef HICNLIGHT_STRATEGY_LOAD_BALANCER_H +#define HICNLIGHT_STRATEGY_LOAD_BALANCER_H -#include <hicn/strategies/strategyImpl.h> +typedef struct { + unsigned int pi; + double avg_pi; + double weight; +} strategy_load_balancer_nexthop_state_t; -StrategyImpl *strategyLoadBalancer_Create(); +typedef struct { + void *_; +} strategy_load_balancer_state_t; -#endif // loadBalancer_h +typedef struct { + void *_; +} strategy_load_balancer_options_t; + +#endif /* HICNLIGHT_STRATEGY_LOAD_BALANCER_H */ diff --git a/hicn-light/src/hicn/strategies/local_prefixes.c b/hicn-light/src/hicn/strategies/local_prefixes.c new file mode 100644 index 000000000..fb161ab2a --- /dev/null +++ b/hicn-light/src/hicn/strategies/local_prefixes.c @@ -0,0 +1,82 @@ +/* + * Copyright (c) 2021-2023 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 "local_prefixes.h" +#include <hicn/core/forwarder.h> +#include <hicn/core/nexthops.h> +#include <hicn/core/mapme.h> + +#define MAX_PREFIXES 10 + +struct local_prefixes_s { + hicn_prefix_t local_prefixes[MAX_PREFIXES]; + unsigned len; +}; + +local_prefixes_t *create_local_prefixes() { + local_prefixes_t *lp = calloc(1, sizeof(local_prefixes_t)); + if (!lp) return NULL; + return lp; +} + +void free_local_prefixes(local_prefixes_t *lp) { free(lp); } + +unsigned local_prefixes_get_len(local_prefixes_t *prefixes) { + return prefixes->len; +} + +bool contain_prefix(const local_prefixes_t *prefixes, + const hicn_prefix_t *prefix) { + for (unsigned i = 0; i < prefixes->len; i++) { + if (hicn_prefix_equals(&(prefixes->local_prefixes[i]), prefix)) return true; + } + return false; +} + +void local_prefixes_add_prefixes(local_prefixes_t *prefixes, + local_prefixes_t *new_prefixes) { + // if there is not enough space for the new prefixes they are not added + unsigned i = 0; + while ((i < new_prefixes->len) && (prefixes->len < MAX_PREFIXES)) { + if (!contain_prefix(prefixes, &(new_prefixes->local_prefixes[i]))) { + hicn_prefix_copy(&prefixes->local_prefixes[prefixes->len], + &new_prefixes->local_prefixes[i]); + prefixes->len++; + } + i++; + } +} + +void local_prefixes_add_prefix(local_prefixes_t *prefixes, + const hicn_prefix_t *prefix) { + if (prefixes->len >= MAX_PREFIXES) return; + if (!contain_prefix(prefixes, prefix)) { + hicn_prefix_copy(&(prefixes->local_prefixes[prefixes->len]), prefix); + prefixes->len++; + } +} + +void update_remote_node_paths(const void *nexthops, const void *forwarder, + local_prefixes_t *prefixes) { + if (!prefixes) return; + struct mapme_s *mapme = forwarder_get_mapme((forwarder_t *)forwarder); + fib_t *fib = forwarder_get_fib((forwarder_t *)forwarder); + for (unsigned i = 0; i < prefixes->len; i++) { + fib_entry_t *entry = fib_match_prefix(fib, &prefixes->local_prefixes[i]); + if (!entry) continue; + // XXX we don't want to force + mapme_set_adjacencies(mapme, entry, (nexthops_t *)nexthops, NULL); + } +} diff --git a/hicn-light/src/hicn/strategies/local_prefixes.h b/hicn-light/src/hicn/strategies/local_prefixes.h new file mode 100644 index 000000000..9d7d8ec78 --- /dev/null +++ b/hicn-light/src/hicn/strategies/local_prefixes.h @@ -0,0 +1,46 @@ +/* + * 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. + */ + +/** + * struct used to store prefixes that are served locally. + * these prefixes are used in mapme messages to tell to the server which + * path to use to retrive the content produced locally. + * using this strategy the path selection done by the client can be + * replicated at the server + */ + +#ifndef HICNLIGHT_LOCAL_PREFIXES_H +#define HICNLIGHT_LOCAL_PREFIXES_H + +#include <hicn/name.h> + +typedef struct local_prefixes_s local_prefixes_t; + +local_prefixes_t* create_local_prefixes(); + +void free_local_prefixes(local_prefixes_t* lp); + +unsigned local_prefixes_get_len(local_prefixes_t* prefixes); + +void local_prefixes_add_prefixes(local_prefixes_t* prefixes, + local_prefixes_t* new_prefixes); + +void local_prefixes_add_prefix(local_prefixes_t* prefixes, + const hicn_prefix_t* prefix); + +void update_remote_node_paths(const void* nexthops, const void* forwarder, + local_prefixes_t* prefixes); + +#endif /* HICNLIGHT_LOCAL_PREFIXES */ diff --git a/hicn-light/src/hicn/strategies/local_remote.c b/hicn-light/src/hicn/strategies/local_remote.c new file mode 100644 index 000000000..7edf62643 --- /dev/null +++ b/hicn-light/src/hicn/strategies/local_remote.c @@ -0,0 +1,105 @@ +/* + * Copyright (c) 2021 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/core/nexthops.h> +#include <hicn/core/forwarder.h> + +#include "local_remote.h" + +static int strategy_local_remote_initialize(strategy_entry_t *entry, + const void *forwarder) { + printf("INIT FWD STRATEGY REMOTE LOCAL\n"); + srand((unsigned int)time(NULL)); + entry->forwarder = forwarder; + return 0; +} + +static int strategy_local_remote_finalize(strategy_entry_t *entry) { + /* Nothing to do */ + return 0; +} + +static int strategy_local_remote_add_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* Nothing to do */ + return 0; +} + +static int strategy_local_remote_remove_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* Nothing to do */ + return 0; +} + +static nexthops_t *strategy_local_remote_lookup_nexthops( + strategy_entry_t *entry, nexthops_t *nexthops, const msgbuf_t *msgbuf) { + if (!entry->forwarder) { + // the forwarder does not exists, drop packet + nexthops_disable_all(nexthops); + return nexthops; + } + + unsigned cid = msgbuf_get_connection_id(msgbuf); + connection_table_t *table = forwarder_get_connection_table(entry->forwarder); + if (!table) { + // the connection table does not exists, drop packet. + nexthops_disable_all(nexthops); + return nexthops; + } + + connection_t *in = connection_table_get_by_id(table, cid); + if (!in) { + // the ingress connection does not exists, drop packet. + nexthops_disable_all(nexthops); + return nexthops; + } + + bool in_is_local = connection_is_local(in); + nexthops_enumerate(nexthops, i, nexthop, { + connection_t *out = connection_table_get_by_id(table, nexthop); + if (out) { + if (connection_is_local(out) != in_is_local) { + // this connection satisfies the requirements, send the intetest here. + nexthops_select(nexthops, i); + return nexthops; + } + } + }); + + // no out connection satisfies the requirements, drop packet. + nexthops_disable_all(nexthops); + return nexthops; +} + +static int strategy_local_remote_on_data(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *data_nexthops, + const msgbuf_t *msgbuf, + Ticks pitEntryCreation, + Ticks objReception) { + /* Nothing to do */ + return 0; +} + +static int strategy_local_remote_on_timeout( + strategy_entry_t *entry, nexthops_t *nexthops, + const nexthops_t *timeout_nexthops) { + /* Nothing to do */ + return 0; +} + +DECLARE_STRATEGY(local_remote); diff --git a/hicn-light/src/hicn/strategies/local_remote.h b/hicn-light/src/hicn/strategies/local_remote.h new file mode 100644 index 000000000..58ca5abc3 --- /dev/null +++ b/hicn-light/src/hicn/strategies/local_remote.h @@ -0,0 +1,40 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * Forward on a single path. If the incoming interest arrives from a local face, + * the interest shuold be forwarded only on a remote face. Viceversa, if the + * interest comes from remote it should be sent to a local face. Notice that if + * the condition cannot be satified (e.g. an interest comes from a local face + * and only an other local face can be satified to send the interest) the + * interest is dropped + */ + +#ifndef HICNLIGHT_STRATEGY_LOCAL_REMOTE_H +#define HICNLIGHT_STRATEGY_LOCAL_REMOTE_H + +typedef struct { + void *_; +} strategy_loc_rem_nexthop_state_t; + +typedef struct { + void *_; +} strategy_loc_rem_state_t; + +typedef struct { + void *_; +} strategy_loc_rem_options_t; + +#endif /* HICNLIGHT_STRATEGY_LOCAL_REMOTE_H */ diff --git a/hicn-light/src/hicn/strategies/lowLatency.c b/hicn-light/src/hicn/strategies/lowLatency.c deleted file mode 100644 index 61bffe243..000000000 --- a/hicn-light/src/hicn/strategies/lowLatency.c +++ /dev/null @@ -1,851 +0,0 @@ -/* - * Copyright (c) 2017-2019 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 <math.h> - -#include <parc/assert/parc_Assert.h> - -#include <parc/algol/parc_HashMap.h> -#include <parc/algol/parc_Memory.h> -#include <parc/algol/parc_Object.h> -#include <parc/algol/parc_Unsigned.h> - -#include <hicn/core/messageHandler.h> - -#include <hicn/strategies/lowLatency.h> -#include <hicn/strategies/nexthopStateLowLatency.h> - -const unsigned STABILITY_FACTOR = 15; -const unsigned MAX_SWITCH_TRY = 10; -const unsigned MAX_LATENCY_DIFF = 10; -const unsigned MAX_TOLLERATED_LATENCY_DIFF = 15; -const unsigned MAX_ROUNDS_MP_WITHOUT_CHECK = 2; -const unsigned MAX_ROUNDS_AVOIDING_MULTIPATH = 40; //about 20 sec -const unsigned MAX_ROUNDS_WITH_ERROR = 4; -const unsigned PROBE_LIFETIME = 500; //ms - -static void _strategyLowLatency_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception); -static void _strategyLowLatency_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId); -static NumberSet *_strategyLowLatency_LookupNexthop( - StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage); -#ifndef WITH_POLICY -static NumberSet *_strategyLowLatency_ReturnNexthops(StrategyImpl *strategy); -static unsigned _strategyLowLatency_CountNexthops(StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ -static void _strategyLowLatency_AddNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLowLatency_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLowLatency_ImplDestroy(StrategyImpl **strategyPtr); -static strategy_type _strategyLowLatency_GetStrategy(StrategyImpl *strategy); - -static StrategyImpl _template = { - .context = NULL, - .receiveObject = &_strategyLowLatency_ReceiveObject, - .onTimeout = &_strategyLowLatency_OnTimeout, - .lookupNexthop = &_strategyLowLatency_LookupNexthop, -#ifndef WITH_POLICY - .returnNexthops = &_strategyLowLatency_ReturnNexthops, - .countNexthops = &_strategyLowLatency_CountNexthops, -#endif /* ! WITH_POLICY */ - .addNexthop = &_strategyLowLatency_AddNexthop, - .removeNexthop = &_strategyLowLatency_RemoveNexthop, - .destroy = &_strategyLowLatency_ImplDestroy, - .getStrategy = &_strategyLowLatency_GetStrategy, -}; - -struct strategy_low_latency; -typedef struct strategy_low_latency StrategyLowLatency; - -struct strategy_low_latency { - // hash map from connectionId to StrategyNexthopStateLL - PARCHashMap *strategy_state; - //hash map from sequence number to ticks (sent time) - PARCHashMap *pending_probes_ticks; - //hash map from sequence number to face id - PARCHashMap *pending_probes_faces; - const Forwarder * forwarder; - PARCEventTimer *sendProbes; - PARCEventTimer *computeBestFace; - uint8_t * probe; - hicn_name_t * name; - StrategyNexthopStateLL * bestFaces[2]; - unsigned round; - unsigned rounds_in_multipath; - unsigned rounds_with_error; - unsigned rounds_avoiding_multipath; - bool use2paths; - bool avoid_multipath; - unsigned related_prefixes_len; - Name **related_prefixes; -#ifndef WITH_POLICY - NumberSet *nexthops; -#endif /* ! WITH_POLICY */ -}; - -static void strategyLowLatency_SendProbesCB(int fd, PARCEventType which_event, - void *data){ - parcAssertTrue(which_event & PARCEventType_Timeout, - "Event incorrect, expecting %X set, got %X", - PARCEventType_Timeout, which_event); - - StrategyLowLatency *ll = (StrategyLowLatency *) data; - - //delete old pending probes - if(parcHashMap_Size(ll->pending_probes_ticks) != 0){ - Ticks now = forwarder_GetTicks(ll->forwarder); - PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->pending_probes_ticks); - NumberSet *to_remove = numberSet_Create(); - while(parcIterator_HasNext(iterator)) { - PARCUnsigned *parc_seq = (PARCUnsigned *) parcIterator_Next(iterator); - PARCUnsigned *parc_time = (PARCUnsigned *) parcHashMap_Get(ll->pending_probes_ticks, parc_seq); - Ticks sent_time = parcUnsigned_GetUnsigned(parc_time); - if((now - sent_time) > PROBE_LIFETIME){ - //probes to delete - numberSet_Add(to_remove, parcUnsigned_GetUnsigned(parc_seq)); - } - } - parcIterator_Release(&iterator); - - for(int i = 0; i < numberSet_Length(to_remove); i++){ - PARCUnsigned *prob_seq = parcUnsigned_Create(numberSet_GetItem(to_remove,i)); - PARCUnsigned *cid = (PARCUnsigned *) parcHashMap_Get(ll->pending_probes_faces, prob_seq); - StrategyNexthopStateLL *state = - (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); - strategyNexthopStateLL_LostProbe(state); - parcHashMap_Remove(ll->pending_probes_ticks, prob_seq); - parcHashMap_Remove(ll->pending_probes_faces, prob_seq); - parcUnsigned_Release(&prob_seq); - } - numberSet_Release(&to_remove); - } - - ConnectionTable * ct = forwarder_GetConnectionTable(ll->forwarder); - - PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - while(parcIterator_HasNext(iterator)){ - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - Connection *conn = - (Connection *)connectionTable_FindById(ct, - parcUnsigned_GetUnsigned(cid)); - if(!conn) - continue; - - StrategyNexthopStateLL *state = - (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); - - //probe only usable paths - if(!strategyNexthopStateLL_IsAllowed(state)) - continue; - - uint32_t seq = rand(); - messageHandler_SetProbeName(ll->probe, HF_INET6_TCP, - ll->name, seq); - connection_Probe(conn, ll->probe); - - PARCUnsigned *parc_seq = parcUnsigned_Create(seq); - Ticks now = forwarder_GetTicks(ll->forwarder); - PARCUnsigned *parc_time = parcUnsigned_Create((unsigned int)now); - parcHashMap_Put(ll->pending_probes_ticks, parc_seq, parc_time); - parcHashMap_Put(ll->pending_probes_faces, parc_seq, cid); - strategyNexthopStateLL_SentProbe(state); - parcUnsigned_Release(&parc_seq); - parcUnsigned_Release(&parc_time); - } - parcIterator_Release(&iterator); - - struct timeval timeout = {0,50000}; - parcEventTimer_Start(ll->sendProbes, &timeout); -} - -static void strategyLowLatency_SendMapmeUpdate(StrategyLowLatency *ll, - const NumberSet * nexthops){ - MapMe * mapme = forwarder_getMapmeInstance(ll->forwarder); - FIB * fib = forwarder_getFib((Forwarder*) ll->forwarder); - if(fib != NULL){ - for(unsigned i = 0; i < ll->related_prefixes_len; i++){ - FibEntry *fibEntry = fib_MatchName(fib, ll->related_prefixes[i]); - if(fibEntry != NULL){ - mapme_maybe_send_updates(mapme, fibEntry, nexthops); - } - } - } -} - -static void strategyLowLatency_SelectBestFaces(StrategyLowLatency *ll, - bool new_round){ - - StrategyNexthopStateLL * old_faces[2]; - old_faces[0] = ll->bestFaces[0]; - old_faces[1] = ll->bestFaces[1]; - - if(new_round){ - ll->round++; - } - - if(parcHashMap_Size(ll->strategy_state) == 0){ - ll->bestFaces[0] = NULL; - ll->bestFaces[1] = NULL; - ll->use2paths = false; - goto NEW_ROUND; - } - - if(ll->use2paths && ll->bestFaces[0] != NULL && ll->bestFaces[1] != NULL){ - //multipath case - - if(!strategyNexthopStateLL_IsLossy(ll->bestFaces[0]) - && !strategyNexthopStateLL_IsLossy(ll->bestFaces[1]) - && strategyNexthopStateLL_IsAllowed(ll->bestFaces[0]) - && strategyNexthopStateLL_IsAllowed(ll->bestFaces[1])){ - - if(ll->rounds_in_multipath < MAX_ROUNDS_MP_WITHOUT_CHECK){ - //we are at the first rounds of the multipath let's wait a bit - //(MAX_ROUNDS_MP_WITHOUT_CHECK) to make the queuing converge - ll->rounds_in_multipath++; - goto NEW_ROUND; - } - - //we need to decide if we want ot keep using two paths or not - ll->rounds_in_multipath++; - double rtt0 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]); - double rtt1 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]); - double diff = fabs(rtt0 - rtt1); - - if(diff < MAX_LATENCY_DIFF){ - //everything is working, keep using the two paths - ll->rounds_with_error = 0; - goto NEW_ROUND; - } - - //check for how many rounds we had problems - if(ll->rounds_with_error < MAX_ROUNDS_WITH_ERROR && - diff < MAX_TOLLERATED_LATENCY_DIFF){ - //we can tollerate few round with errors - ll->rounds_with_error++; - goto NEW_ROUND; - } - - //prevent the usage of multiple paths - ll->rounds_with_error = 0; - ll->avoid_multipath = true; - ll->rounds_avoiding_multipath = 0; - } //else - //at least one of the two path is lossy - //or it is not allowed by the policies. - //search for a better possibility - } - - ll->bestFaces[0] = NULL; - ll->bestFaces[1] = NULL; - - //check if there is at least one non lossy connection - PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - bool check_losses = true; - bool found_good_face = false; - while(parcIterator_HasNext(iterator) && !found_good_face){ - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - const StrategyNexthopStateLL *state = parcHashMap_Get(ll->strategy_state, cid); - if(!strategyNexthopStateLL_IsLossy(state) && - strategyNexthopStateLL_IsAllowed(state)){ - found_good_face = true; - } - } - parcIterator_Release(&iterator); - if(!found_good_face){ - // all the available faces are lossy, so we take into account only - // the latency computed with the probes - check_losses = false; - } - - if(ll->bestFaces[0] == NULL){ - //try to take a random face - PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - bool face_found = false; - while(parcIterator_HasNext(iterator) && !face_found) { - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) - parcHashMap_Get(ll->strategy_state, cid); - - if((check_losses && strategyNexthopStateLL_IsLossy(state)) || - !strategyNexthopStateLL_IsAllowed(state)){ - //skip the face - continue; - } - - ll->bestFaces[0] = state; - face_found = true; - } - parcIterator_Release(&iterator); - } - - if(ll->bestFaces[0] == NULL){ - //no usable face exists - ll->bestFaces[0] = NULL; - ll->bestFaces[1] = NULL; - ll->use2paths = false; - goto NEW_ROUND; - } - - double bestRtt = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]); - - if(ll->avoid_multipath) - ll->rounds_avoiding_multipath++; - - if(ll->rounds_avoiding_multipath > MAX_ROUNDS_AVOIDING_MULTIPATH){ - ll->avoid_multipath = false; - ll->rounds_avoiding_multipath = 0; - } - - iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - while (parcIterator_HasNext(iterator)) { - - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) - parcHashMap_Get(ll->strategy_state, cid); - double rtt = strategyNexthopStateLL_GetRTTLive(state); - - if((check_losses && strategyNexthopStateLL_IsLossy(state)) || - !strategyNexthopStateLL_IsAllowed(state)){ - //skip the face - continue; - } - - if(rtt + STABILITY_FACTOR < bestRtt){ - //maybe we found a better face - double rttInUse = strategyNexthopStateLL_GetRTTInUse(state); - unsigned try = strategyNexthopStateLL_GetTryToSwitch(state); - - //we check the rtt in use to check if the new face that we found - //gets congested when we use it to send the traffic - if(rttInUse < bestRtt || try > MAX_SWITCH_TRY){ - //we have a new best face! - strategyNexthopStateLL_ResetTryToSwitch((StrategyNexthopStateLL*) state); - bestRtt = rtt; - if(ll->bestFaces[0] != NULL) - strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[0]); - ll->bestFaces[0] = (StrategyNexthopStateLL*) state; - }else{ - //in this case we should switch but we wait MAX_SWITCH_TRY - //before switch to avoid ossillations between different paths - strategyNexthopStateLL_IncreaseTryToSwitch( - (StrategyNexthopStateLL*) state, ll->round); - } - } - } - - parcIterator_Release(&iterator); - - if(ll->bestFaces[0] == NULL){ - //we found no face so return - ll->bestFaces[0] = NULL; - ll->bestFaces[1] = NULL; - ll->use2paths = false; - goto NEW_ROUND; - } - - if(parcHashMap_Size(ll->strategy_state) == 1 || ll->avoid_multipath){ - //in this case (one face available or avoid multipath) we stop the - //search here. Just reset face 1 if needed - if(ll->bestFaces[1] != NULL){ - strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); - ll->bestFaces[1] = NULL; - } - ll->use2paths = false; - goto NEW_ROUND; - } - - //if we are here we have more than 1 interface, so we search for a second one - //to use in case of multipath - iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - while (parcIterator_HasNext(iterator)) { - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - if(parcUnsigned_GetUnsigned(cid) != - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])){ - - StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) - parcHashMap_Get(ll->strategy_state, cid); - - if((check_losses && strategyNexthopStateLL_IsLossy(state)) || - !strategyNexthopStateLL_IsAllowed(state)){ - //skip the face - continue; - } - - if(ll->bestFaces[1] == NULL){ - //in case of 2 faces we should pass always here - ll->bestFaces[1] = state; - }else{ - //TODO this must be tested with more then 2 faces - double rtt1 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]); - double rttNewFace = strategyNexthopStateLL_GetRTTLive(state); - if(rttNewFace + STABILITY_FACTOR < rtt1){ - strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); - ll->bestFaces[1] = state; - } - } - } - } - parcIterator_Release(&iterator); - - if(ll->bestFaces[1] != NULL){ - //we are not using the second face yet so we use the normal rtt for comparison - double rtt0 = strategyNexthopStateLL_GetRTTProbe(ll->bestFaces[0]); - double rtt1 = strategyNexthopStateLL_GetRTTProbe(ll->bestFaces[1]); - double diff = fabs(rtt0 - rtt1); - if(diff < MAX_LATENCY_DIFF) { - //let's start to use 2 paths - ll->rounds_with_error = 0; - ll->use2paths = true; - ll->rounds_in_multipath = 0; - }else{ - //we use only one path - strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); - ll->bestFaces[1] = NULL; - ll->use2paths = false; - } - }else{ - ll->use2paths = false; - } - - NEW_ROUND: - { - Logger * log = forwarder_GetLogger(ll->forwarder); - if(log != NULL && - logger_IsLoggable(log, LoggerFacility_Strategy, PARCLogLevel_Info)){ - if(ll->use2paths){ - logger_Log(log, LoggerFacility_Strategy, PARCLogLevel_Info, - __func__, "use 2 paths. rtt face %d = %f queue = %f is_lossy = %d," - "rtt face %d = %f queue = %f is_lossy = %d\n", - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]), - strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]), - strategyNexthopStateLL_GetQueuing(ll->bestFaces[0]), - strategyNexthopStateLL_IsLossy(ll->bestFaces[0]), - strategyNexthopStateLL_GetFaceId(ll->bestFaces[1]), - strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]), - strategyNexthopStateLL_GetQueuing(ll->bestFaces[1]), - strategyNexthopStateLL_IsLossy(ll->bestFaces[1])); - }else{ - if(ll->bestFaces[0] != NULL){ - logger_Log(log, LoggerFacility_Strategy, - PARCLogLevel_Info, __func__, - "use 1 path. rtt face %d = %f is_lossy = %d, " - "(avoid multipath = %d)\n", - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]), - strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]), - strategyNexthopStateLL_IsLossy(ll->bestFaces[0]), - ll->avoid_multipath); - }else{ - logger_Log(log, LoggerFacility_Strategy, PARCLogLevel_Info, - __func__, "no face to use!\n"); - } - } - } - } - - //update the round only at the end for all the faces - if(new_round){ - PARCIterator * iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - while (parcIterator_HasNext(iterator)) { - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - strategyNexthopStateLL_StartNewRound((StrategyNexthopStateLL *) - parcHashMap_Get(ll->strategy_state, cid)); - } - parcIterator_Release(&iterator); - } - - //mapme updates - //if ll->bestFaces[0] == NULL we don't have any output faces - //so don't need to send any updates since we are disconnected - if(ll->related_prefixes_len != 0){ - if(ll->bestFaces[0] != NULL){ - NumberSet *out = numberSet_Create(); - if(old_faces[0] == NULL || - (strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]) != - strategyNexthopStateLL_GetFaceId(old_faces[0]))){ - //there is a new face 0 so we need a map me update - //if ll->bestFaces[1] != NULL we need to send the update - //even if it is the same as before - numberSet_Add(out, - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - if(ll->bestFaces[1] != NULL){ - numberSet_Add(out, - strategyNexthopStateLL_GetFaceId(ll->bestFaces[1])); - } - strategyLowLatency_SendMapmeUpdate(ll,out); - }else{ - if(ll->bestFaces[1] != NULL){ - if(old_faces[1] == NULL || - (strategyNexthopStateLL_GetFaceId(ll->bestFaces[1]) != - strategyNexthopStateLL_GetFaceId(old_faces[1]))){ - //send a mapme both with face 0 and face 1 - numberSet_Add(out, - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - numberSet_Add(out, - strategyNexthopStateLL_GetFaceId(ll->bestFaces[1])); - strategyLowLatency_SendMapmeUpdate(ll,out); - } - }else{ - if(old_faces[1] != NULL){ - //in the previuos round we were using two faces, now only one - //send update with only face 0 - numberSet_Add(out, - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - strategyLowLatency_SendMapmeUpdate(ll,out); - } - } - } - numberSet_Release(&out); - } - } -} - -static void strategyLowLatency_BestFaceCB(int fd, PARCEventType which_event, - void *data){ - parcAssertTrue(which_event & PARCEventType_Timeout, - "Event incorrect, expecting %X set, got %X", - PARCEventType_Timeout, which_event); - - StrategyLowLatency * ll = (StrategyLowLatency *) data; - strategyLowLatency_SelectBestFaces(ll, true); - - struct timeval timeout = {0, 500000}; - parcEventTimer_Start(ll->computeBestFace, &timeout); -} - -StrategyImpl *strategyLowLatency_Create() { - StrategyLowLatency *strategy = - parcMemory_AllocateAndClear(sizeof(StrategyLowLatency)); - parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyLowLatency)); - - strategy->strategy_state = parcHashMap_Create(); - strategy->pending_probes_ticks = parcHashMap_Create(); - strategy->pending_probes_faces = parcHashMap_Create(); -#ifndef WITH_POLICY - strategy->nexthops = numberSet_Create(); -#endif /* ! WITH_POLICY */ - srand((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - - return impl; -} - -void strategyLowLatency_SetStrategy(StrategyImpl *strategy, - const Forwarder * forwarder, - const FibEntry * fibEntry, - unsigned related_prefixes_len, - Name **related_prefixes) { - StrategyLowLatency *ll = - (StrategyLowLatency *)strategy->context; - ll->forwarder = forwarder; - - //create probe packet - ll->probe = messageHandler_CreateProbePacket(HF_INET6_TCP, PROBE_LIFETIME); - ip_prefix_t address; - nameBitvector_ToIPAddress(name_GetContentName( - fibEntry_GetPrefix(fibEntry)), &address); - ll->name = messageHandler_CreateProbeName(&address); - - - Dispatcher *dispatcher = forwarder_GetDispatcher((Forwarder *)ll->forwarder); - ll->sendProbes = dispatcher_CreateTimer(dispatcher, false, - strategyLowLatency_SendProbesCB, ll); - - ll->round = 0; - ll->rounds_in_multipath = 0; - ll->rounds_with_error = 0; - ll->rounds_avoiding_multipath = 0; - ll->use2paths = false; - ll->avoid_multipath = false; - - ll->related_prefixes_len = related_prefixes_len; - ll->related_prefixes = malloc(sizeof(Name *) * ll->related_prefixes_len); - for(unsigned i = 0; i < ll->related_prefixes_len; i++){ - ll->related_prefixes[i] = name_Copy(related_prefixes[i]); - } - - ll->computeBestFace = dispatcher_CreateTimer(dispatcher, false, - strategyLowLatency_BestFaceCB, ll); -} - -void _startTimers(StrategyImpl *strategy){ - StrategyLowLatency *ll = - (StrategyLowLatency *)strategy->context; - - struct timeval timeoutProbes = {0,10000}; - parcEventTimer_Start(ll->sendProbes, &timeoutProbes); - struct timeval timeoutBF = {1,0}; - parcEventTimer_Start(ll->computeBestFace, &timeoutBF); -} - -void _stopTimers(StrategyImpl *strategy){ - StrategyLowLatency *ll = - (StrategyLowLatency *)strategy->context; - - parcEventTimer_Stop(ll->sendProbes); - parcEventTimer_Stop(ll->computeBestFace); -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyLowLatency_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_LOW_LATENCY; -} - -static void _strategyLowLatency_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception) { - StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; - - if(!messageHandler_IsAProbe(message_FixedHeader(objectMessage))) - return; - - uint32_t seq = messageHandler_GetSegment(message_FixedHeader(objectMessage)); - PARCUnsigned *parc_seq = parcUnsigned_Create(seq); - if (!parcHashMap_Contains(ll->pending_probes_ticks, parc_seq)){ - parcUnsigned_Release(&parc_seq); - return; - } - - //here numberSet_Length(egressId) should be 1 - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopStateLL *state = - parcHashMap_Get(ll->strategy_state, cid); - if (state != NULL) { - Ticks time = parcUnsigned_GetUnsigned( - parcHashMap_Get(ll->pending_probes_ticks, parc_seq)); - Ticks now = forwarder_GetTicks(ll->forwarder); - Ticks RTT = now - time; - if(RTT <= 0) - RTT = 1; - strategyNexthopStateLL_AddRttSample( - (StrategyNexthopStateLL *) state, (unsigned int)RTT); - parcHashMap_Remove(ll->pending_probes_ticks, parc_seq); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } - parcUnsigned_Release(&parc_seq); -} - -static void _strategyLowLatency_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId) {} - -static NumberSet *_strategyLowLatency_LookupNexthop(StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage) { - //unsigned out_connection; - NumberSet *out = numberSet_Create(); - - StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; - - //update is_allowed flag of all the next hops - PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); - while(parcIterator_HasNext(iterator)){ - PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); - StrategyNexthopStateLL *state = - (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); - if(numberSet_Contains(nexthops, parcUnsigned_GetUnsigned(cid))){ - strategyNexthopStateLL_SetIsAllowed(state,true); - }else{ - strategyNexthopStateLL_SetIsAllowed(state,false); - } - } - parcIterator_Release(&iterator); - - if(ll->bestFaces[0] != NULL && - !strategyNexthopStateLL_IsAllowed(ll->bestFaces[0])){ - //if ll->bestFaces[0] is not allowed we need to find a new face - strategyLowLatency_SelectBestFaces(ll, false); - } - - //at this point ll->bestFaces[0] must be allowed - //single path case - if(ll->bestFaces[0] != NULL && (ll->bestFaces[1] == NULL || !ll->use2paths)){ - strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); - numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - - //multipath case - }else if(ll->bestFaces[0] != NULL && ll->bestFaces[1] != NULL && ll->use2paths){ - //it may happen that ll->bestFaces[1] is not allowed, in that case we send on - //ll->bestFaces[0] until the next best face selection - if(!strategyNexthopStateLL_IsAllowed(ll->bestFaces[1])){ - strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); - numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - }else{ - double queue0 = strategyNexthopStateLL_GetQueuing(ll->bestFaces[0]); - double queue1 = strategyNexthopStateLL_GetQueuing(ll->bestFaces[1]); - double prob0 = 0.5; - if(queue0 > 1 || queue1 > 1){ - prob0 = 1.0 - (queue0 / (queue0 + queue1)); - } - double coin = ((double) rand() / (RAND_MAX)); - if(coin < prob0){ - strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); - numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); - }else{ - strategyNexthopStateLL_SendPacket(ll->bestFaces[1]); - numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[1])); - } - } - } - return out; -} - - -#ifndef WITH_POLICY -static NumberSet *_strategyLowLatency_ReturnNexthops(StrategyImpl *strategy) { - StrategyLoadBalancerLL *ll = (StrategyLoadBalancerLL *)strategy->context; - return ll->nexthops; -} - -unsigned _strategyLowLatency_CountNexthops(StrategyImpl *strategy) { - StrategyLoadBalancerLL *ll = (StrategyLoadBalancerLL *)strategy->context; - return (unsigned)numberSet_Length(ll->nexthops); -} -#endif /* ! WITH_POLICY */ - -static void _strategyLowLatency_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; - - if (!parcHashMap_Contains(ll->strategy_state, cid)) { - StrategyNexthopStateLL *state = strategyNexthopStateLL_Create(connectionId); - parcHashMap_Put(ll->strategy_state, cid, state); - if(ll->bestFaces[0] == NULL){ - ll->bestFaces[0] = state; - } -#ifndef WITH_POLICY - numberSet_Add(ll->nexthops, connectionId); -#endif /* WITH_POLICY */ - } - - if(parcHashMap_Size(ll->strategy_state) >= 2){ - _startTimers(strategy); - } - - parcUnsigned_Release(&cid); -} - -static void _strategyLowLatency_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; - - bool reset_bestFaces = false; - - if((ll->bestFaces[0] != NULL && - strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]) == connectionId) || - (ll->bestFaces[1] != NULL && - strategyNexthopStateLL_GetFaceId(ll->bestFaces[1]) == connectionId)){ - reset_bestFaces = true; - } - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - if (parcHashMap_Contains(ll->strategy_state, cid)) { - parcHashMap_Remove(ll->strategy_state, cid); -#ifndef WITH_POLICY - numberSet_Remove(lb->nexthops, connectionId); -#endif /* WITH_POLICY */ - } - - if(reset_bestFaces){ - ll->bestFaces[0] = NULL; - ll->bestFaces[1] = NULL; - strategyLowLatency_SelectBestFaces(ll, false); - } - - if(parcHashMap_Size(ll->strategy_state) < 2){ - _stopTimers(strategy); - } - - parcUnsigned_Release(&cid); -} - -static void _strategyLowLatency_ImplDestroy(StrategyImpl **strategyPtr) { - parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*strategyPtr, - "Parameter must dereference to non-null pointer"); - - StrategyImpl *impl = *strategyPtr; - StrategyLowLatency *strategy = (StrategyLowLatency *)impl->context; - - _stopTimers(impl); - - parcEventTimer_Destroy(&(strategy->sendProbes)); - parcEventTimer_Destroy(&(strategy->computeBestFace)); - - if (parcHashMap_Size(strategy->strategy_state) > 0) { - PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - StrategyNexthopStateLL *state = - (StrategyNexthopStateLL *)parcHashMap_Get(strategy->strategy_state, cid); - parcObject_Release((void**)&state); - } - parcIterator_Release(&it); - } - - parcHashMap_Release(&(strategy->strategy_state)); - parcHashMap_Release(&(strategy->pending_probes_ticks)); - parcHashMap_Release(&(strategy->pending_probes_faces)); - - parcMemory_Deallocate(&(strategy->probe)); - parcMemory_Deallocate(&(strategy->name)); - - for(unsigned i = 0; i < strategy->related_prefixes_len; i++){ - name_Release(&(strategy->related_prefixes[i])); - } - free(strategy->related_prefixes); - -#ifndef WITH_POLICY - numberSet_Release(&(strategy->nexthops)); -#endif /* ! WITH_POLICY */ - - parcMemory_Deallocate((void **)&strategy); - parcMemory_Deallocate((void **)&impl); - *strategyPtr = NULL; -} diff --git a/hicn-light/src/hicn/strategies/lowLatency.h b/hicn-light/src/hicn/strategies/lowLatency.h deleted file mode 100644 index 736c8783d..000000000 --- a/hicn-light/src/hicn/strategies/lowLatency.h +++ /dev/null @@ -1,33 +0,0 @@ -/* - * Copyright (c) 2017-2019 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. - */ - -/** - * Forward on the path with lowest latency - */ - -#ifndef lowLatency_h -#define lowLatency_h - -#include <hicn/strategies/strategyImpl.h> -#include <hicn/core/forwarder.h> - -StrategyImpl *strategyLowLatency_Create(); - -void strategyLowLatency_SetStrategy(StrategyImpl *strategy, - const Forwarder * forwarder, - const FibEntry * fibEntry, - unsigned related_prefixes_len, - Name **related_prefixes); -#endif // lowLatency_h diff --git a/hicn-light/src/hicn/strategies/nexthopState.c b/hicn-light/src/hicn/strategies/nexthopState.c deleted file mode 100644 index 40af14832..000000000 --- a/hicn-light/src/hicn/strategies/nexthopState.c +++ /dev/null @@ -1,212 +0,0 @@ -/* - * Copyright (c) 2017-2019 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 <parc/algol/parc_DisplayIndented.h> -#include <parc/algol/parc_Memory.h> -#include <parc/algol/parc_Object.h> - -#include <parc/assert/parc_Assert.h> -#include <hicn/strategies/nexthopState.h> - -#define AVG_PI_THRESHOLD 1e-3 - -struct strategy_nexthop_state { - unsigned int pi; - double avg_pi; - double weight; -}; - -static bool _strategyNexthopState_Destructor( - StrategyNexthopState **instancePtr) { - return true; -} - -parcObject_ImplementAcquire(strategyNexthopState, StrategyNexthopState); - -parcObject_ImplementRelease(strategyNexthopState, StrategyNexthopState); - -parcObject_Override( - StrategyNexthopState, PARCObject, - .destructor = (PARCObjectDestructor *)_strategyNexthopState_Destructor, - .copy = (PARCObjectCopy *)strategyNexthopState_Copy, - .display = (PARCObjectDisplay *)strategyNexthopState_Display, - .toString = (PARCObjectToString *)strategyNexthopState_ToString, - .equals = (PARCObjectEquals *)strategyNexthopState_Equals, - .compare = (PARCObjectCompare *)strategyNexthopState_Compare, - .hashCode = (PARCObjectHashCode *)strategyNexthopState_HashCode, - .display = (PARCObjectDisplay *)strategyNexthopState_Display); - -void strategyNexthopState_AssertValid(const StrategyNexthopState *instance) { - parcAssertTrue(strategyNexthopState_IsValid(instance), - "StrategyNexthopState is not valid."); -} - -StrategyNexthopState *strategyNexthopState_Create() { - StrategyNexthopState *result = - parcObject_CreateInstance(StrategyNexthopState); - if (result != NULL) { - result->pi = 0; - result->avg_pi = 0.0; - result->weight = 1; - } - return result; -} - -void strategyNexthopState_Reset(StrategyNexthopState *x) { - x->pi = 0; - x->avg_pi = 0.0; - x->weight = 1; -} - -int strategyNexthopState_Compare(const StrategyNexthopState *val, - const StrategyNexthopState *other) { - if (val == NULL) { - if (other != NULL) { - return -1; - } - } else if (other == NULL) { - return 1; - } else { - strategyNexthopState_OptionalAssertValid(val); - strategyNexthopState_OptionalAssertValid(other); - - if (val->pi < other->pi) { - return -1; - } else if (val->pi > other->pi) { - return 1; - } - - if (val->avg_pi < other->avg_pi) { - return -1; - } else if (val->avg_pi > other->avg_pi) { - return 1; - } - - if (val->weight < other->weight) { - return -1; - } else if (val->weight > other->weight) { - return 1; - } - } - - return 0; -} - -StrategyNexthopState *strategyNexthopState_Copy( - const StrategyNexthopState *original) { - StrategyNexthopState *result = strategyNexthopState_Create(); - result->pi = original->pi; - result->avg_pi = original->avg_pi; - result->weight = original->weight; - - return result; -} - -void strategyNexthopState_Display(const StrategyNexthopState *instance, - int indentation) { - parcDisplayIndented_PrintLine(indentation, "StrategyNexthopState@%p {", - instance); - parcDisplayIndented_PrintLine(indentation + 1, "%d", instance->pi); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_pi); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->weight); - parcDisplayIndented_PrintLine(indentation, "}"); -} - -bool strategyNexthopState_Equals(const StrategyNexthopState *x, - const StrategyNexthopState *y) { - bool result = false; - - if (x == y) { - result = true; - } else if (x == NULL || y == NULL) { - result = false; - } else { - strategyNexthopState_OptionalAssertValid(x); - strategyNexthopState_OptionalAssertValid(y); - - if (strategyNexthopState_Compare(x, y) == 0) { - result = true; - } - } - - return result; -} - -PARCHashCode strategyNexthopState_HashCode(const StrategyNexthopState *x) { - PARCHashCode result = 0; - char str[128]; - sprintf(str, "PI:%d: AVG_PI:%f: W:%f", x->pi, x->avg_pi, x->weight); - result = parcHashCode_Hash((uint8_t *)&str, strlen(str)); - return result; -} - -bool strategyNexthopState_IsValid(const StrategyNexthopState *x) { - bool result = false; - - if (x != NULL) { - result = true; - } - - return result; -} - -char *strategyNexthopState_ToString(const StrategyNexthopState *x) { - // this is not implemented - parcTrapNotImplemented("strategyNexthopState_ToString is not implemented"); - return NULL; -} - -unsigned strategyNexthopState_GetPI(const StrategyNexthopState *x) { - strategyNexthopState_OptionalAssertValid(x); - - return x->pi; -} - -double strategyNexthopState_GetAvgPI(const StrategyNexthopState *x) { - strategyNexthopState_OptionalAssertValid(x); - - return x->avg_pi; -} - -double strategyNexthopState_GetWeight(const StrategyNexthopState *x) { - strategyNexthopState_OptionalAssertValid(x); - - return x->weight; -} - -double strategyNexthopState_UpdateState(StrategyNexthopState *x, bool inc, - double alpha) { - if (inc) { - x->pi++; - } else { - if (x->pi > 0) { - x->pi--; - } - } - x->avg_pi = (x->avg_pi * alpha) + (x->pi * (1 - alpha)); -#ifdef WITH_POLICY - if (x->avg_pi < AVG_PI_THRESHOLD) { -#else - if (x->avg_pi == 0.0) { -#endif /* WITH_POLICY */ - x->avg_pi = 0.1; - } - x->weight = 1 / x->avg_pi; - - return x->weight; -} diff --git a/hicn-light/src/hicn/strategies/nexthopState.h b/hicn-light/src/hicn/strategies/nexthopState.h deleted file mode 100644 index 35a9f497b..000000000 --- a/hicn-light/src/hicn/strategies/nexthopState.h +++ /dev/null @@ -1,94 +0,0 @@ -/* - * Copyright (c) 2017-2019 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. - */ - -#ifndef nexthopstate_h -#define nexthopstate_h - -#include <parc/algol/parc_HashCode.h> -#include <parc/algol/parc_Object.h> - -struct strategy_nexthop_state; -typedef struct strategy_nexthop_state StrategyNexthopState; -extern parcObjectDescriptor_Declaration(StrategyNexthopState); - -/** - */ -StrategyNexthopState *strategyNexthopState_Acquire( - const StrategyNexthopState *instance); - -#ifdef PARCLibrary_DISABLE_VALIDATION -#define strategyNexthopState_OptionalAssertValid(_instance_) -#else -#define strategyNexthopState_OptionalAssertValid(_instance_) \ - strategyNexthopState_AssertValid(_instance_) -#endif - -/** - */ -void strategyNexthopState_AssertValid(const StrategyNexthopState *instance); - -/** - */ -StrategyNexthopState *strategyNexthopState_Create(); - -void strategyNexthopState_Reset(StrategyNexthopState *x); -/** - */ -int strategyNexthopState_Compare(const StrategyNexthopState *instance, - const StrategyNexthopState *other); - -/** - */ -StrategyNexthopState *strategyNexthopState_Copy( - const StrategyNexthopState *original); - -/** - */ -void strategyNexthopState_Display(const StrategyNexthopState *instance, - int indentation); - -/** - */ -bool strategyNexthopState_Equals(const StrategyNexthopState *x, - const StrategyNexthopState *y); - -/** - */ -PARCHashCode strategyNexthopState_HashCode( - const StrategyNexthopState *instance); - -/** - */ -bool strategyNexthopState_IsValid(const StrategyNexthopState *instance); - -/** - */ -void strategyNexthopState_Release(StrategyNexthopState **instancePtr); - -/** - */ -char *strategyNexthopState_ToString(const StrategyNexthopState *instance); - -/** - */ -unsigned strategyNexthopState_GetPI(const StrategyNexthopState *x); - -double strategyNexthopState_GetAvgPI(const StrategyNexthopState *x); - -double strategyNexthopState_GetWeight(const StrategyNexthopState *x); - -double strategyNexthopState_UpdateState(StrategyNexthopState *x, bool inc, - double alpha); -#endif diff --git a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c index a3953987f..3caed8130 100644 --- a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c +++ b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -24,303 +24,17 @@ #include <parc/assert/parc_Assert.h> #include <hicn/strategies/nexthopStateLowLatency.h> -const unsigned MAX_ROUNS_WITHOUT_PROBES = 4; - //if we do not receives probes for 4 rounds it means - //that we had no responce from any producer for 2 sec - //we can say that this interface is daed -const unsigned MIN_NON_LOSSY_ROUNDS = 10; - //number of rounds in non lossy mode before switch to - //no lossy state -const double MAX_LOSS_RATE = 0.10; //10% - -struct strategy_nexthop_state_ll { - bool in_use; - bool is_allowed; // the policy may not allow the use of this face - unsigned face_id; - unsigned sent_packets; - //switch metrics - unsigned last_try_to_switch_round; - unsigned try_to_switch_counter; - //probes counters - unsigned recevied_probes; - unsigned rounds_without_probes; - unsigned sent_probes; - unsigned lost_probes; - unsigned non_lossy_rounds; - //avgs - double avg_rtt; - double avg_rtt_in_use; - double avg_queue; - double avg_loss_rate; - -}; - -static bool _strategyNexthopStateLL_Destructor( - StrategyNexthopStateLL **instancePtr) { - return true; -} - -parcObject_ImplementAcquire(strategyNexthopStateLL, StrategyNexthopStateLL); - -parcObject_ImplementRelease(strategyNexthopStateLL, StrategyNexthopStateLL); - -parcObject_Override( - StrategyNexthopStateLL, PARCObject, - .destructor = (PARCObjectDestructor *)_strategyNexthopStateLL_Destructor, - .copy = (PARCObjectCopy *)strategyNexthopStateLL_Copy, - .display = (PARCObjectDisplay *)strategyNexthopStateLL_Display, - .toString = (PARCObjectToString *)strategyNexthopStateLL_ToString, - .equals = (PARCObjectEquals *)strategyNexthopStateLL_Equals, - .compare = (PARCObjectCompare *)strategyNexthopStateLL_Compare, - .hashCode = (PARCObjectHashCode *)strategyNexthopStateLL_HashCode, - .display = (PARCObjectDisplay *)strategyNexthopStateLL_Display); - -void strategyNexthopStateLL_AssertValid(const StrategyNexthopStateLL *instance) { - parcAssertTrue(strategyNexthopStateLL_IsValid(instance), - "StrategyNexthopState is not valid."); -} - -StrategyNexthopStateLL *strategyNexthopStateLL_Create(unsigned face_id) { - StrategyNexthopStateLL *result = - parcObject_CreateInstance(StrategyNexthopStateLL); - if (result != NULL) { - result->in_use = false; - result->is_allowed = true; - result->face_id = face_id; - result->sent_packets = 0; - result->last_try_to_switch_round = 0; - result->try_to_switch_counter = 0; - result->recevied_probes = 0; - result->rounds_without_probes = 0; - result->sent_probes = 0; - result->lost_probes = 0; - result->non_lossy_rounds = MIN_NON_LOSSY_ROUNDS; - result->avg_rtt = -1.0; - result->avg_rtt_in_use = -1.0; - result->avg_queue = 0.0001; - result->avg_loss_rate = 0.0; - } - return result; -} - -void strategyNexthopStateLL_Reset(StrategyNexthopStateLL *x) { - x->in_use = false; - x->is_allowed = true; - x->sent_packets = 0; - x->last_try_to_switch_round = 0; - x->try_to_switch_counter = 0; - x->recevied_probes = 0; - x->rounds_without_probes = 0; - x->sent_probes = 0; - x->lost_probes = 0; - x->non_lossy_rounds = MIN_NON_LOSSY_ROUNDS; - x->avg_rtt = -1.0; - x->avg_rtt_in_use = -1.0; - x->avg_queue = 0.0001; - x->avg_loss_rate = 0.0; -} - - -int strategyNexthopStateLL_Compare(const StrategyNexthopStateLL *val, - const StrategyNexthopStateLL *other) { - if (val == NULL) { - if (other != NULL) { - return -1; - } - } else if (other == NULL) { - return 1; - } else { - strategyNexthopStateLL_OptionalAssertValid(val); - strategyNexthopStateLL_OptionalAssertValid(other); - - if (val->in_use < other->in_use){ - return -1; - }else if (val->in_use > other->in_use){ - return 1; - } - - if (val->is_allowed < other->is_allowed){ - return -1; - }else if (val->is_allowed> other->is_allowed){ - return 1; - } - - if (val->face_id < other->face_id) { - return -1; - } else if (val->face_id > other->face_id) { - return 1; - } - - if (val->sent_packets < other->sent_packets){ - return -1; - } else if (val->sent_packets > other->sent_packets){ - return 1; - } - - if (val->last_try_to_switch_round < - other->last_try_to_switch_round) { - return -1; - } else if (val->last_try_to_switch_round > - other->last_try_to_switch_round) { - return 1; - } - - if (val->try_to_switch_counter < - other->try_to_switch_counter) { - return -1; - } else if (val->try_to_switch_counter > - other->try_to_switch_counter) { - return 1; - } - - if (val->recevied_probes < other->recevied_probes) { - return -1; - } else if (val->recevied_probes > other->recevied_probes) { - return 1; - } - - if (val->rounds_without_probes < other->rounds_without_probes) { - return -1; - } else if (val->rounds_without_probes > other->rounds_without_probes) { - return 1; - } - - if (val->sent_probes < other->sent_probes) { - return -1; - } else if (val->sent_probes > other->sent_probes) { - return 1; - } - - if (val->lost_probes < other->lost_probes) { - return -1; - } else if (val->lost_probes > other->lost_probes) { - return 1; - } - - if (val->non_lossy_rounds < other->non_lossy_rounds) { - return -1; - } else if (val->non_lossy_rounds > other->non_lossy_rounds) { - return 1; - } - - if (val->avg_rtt < other->avg_rtt) { - return -1; - } else if (val->avg_rtt > other->avg_rtt) { - return 1; - } - - if (val->avg_rtt_in_use < other->avg_rtt_in_use) { - return -1; - } else if (val->avg_rtt_in_use > other->avg_rtt_in_use) { - return 1; - } - - if (val->avg_queue < other->avg_queue) { - return -1; - } else if (val->avg_queue > other->avg_queue) { - return 1; - } - - if (val->avg_loss_rate < other->avg_loss_rate) { - return -1; - } else if (val->avg_loss_rate > other->avg_loss_rate) { - return 1; - } - } - - return 0; -} - -StrategyNexthopStateLL *strategyNexthopStateLL_Copy( - const StrategyNexthopStateLL *original) { - StrategyNexthopStateLL *result = strategyNexthopStateLL_Create(original->face_id); - result->in_use = original->in_use; - result->is_allowed = original->is_allowed; - result->sent_packets = original->sent_packets; - result->last_try_to_switch_round = original->last_try_to_switch_round; - result->try_to_switch_counter = original->try_to_switch_counter; - result->recevied_probes = original->recevied_probes; - result->rounds_without_probes = original->rounds_without_probes; - result->sent_probes = original->sent_probes; - result->lost_probes = original->lost_probes; - result->non_lossy_rounds = original->non_lossy_rounds; - result->avg_rtt = original->avg_rtt; - result->avg_rtt_in_use = original->avg_rtt_in_use; - result->avg_queue = original->avg_queue; - result->avg_loss_rate = original->avg_loss_rate; - return result; -} - -void strategyNexthopStateLL_Display(const StrategyNexthopStateLL *instance, - int indentation) { - parcDisplayIndented_PrintLine(indentation, "StrategyNexthopStateLL@%p {", - instance); - parcDisplayIndented_PrintLine(indentation + 1, "%d", instance->face_id); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_rtt); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_rtt_in_use); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_queue); - parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_loss_rate); - parcDisplayIndented_PrintLine(indentation, "}"); -} - - -bool strategyNexthopStateLL_Equals(const StrategyNexthopStateLL *x, - const StrategyNexthopStateLL *y) { - bool result = false; - - if (x == y) { - result = true; - } else if (x == NULL || y == NULL) { - result = false; - } else { - strategyNexthopStateLL_OptionalAssertValid(x); - strategyNexthopStateLL_OptionalAssertValid(y); - - if (strategyNexthopStateLL_Compare(x, y) == 0) { - result = true; - } - } - - return result; -} - -PARCHashCode strategyNexthopStateLL_HashCode(const StrategyNexthopStateLL *x) { - PARCHashCode result = 0; - char str[128]; - sprintf(str, "ID:%d: RTT:%f: RTTUSE:%f: Q:%f L:%f", x->face_id, x->avg_rtt, - x->avg_rtt_in_use, x->avg_queue, x->avg_loss_rate); - result = parcHashCode_Hash((uint8_t *)&str, strlen(str)); - return result; -} - -bool strategyNexthopStateLL_IsValid(const StrategyNexthopStateLL *x) { - bool result = false; - - if (x != NULL) { - result = true; - } - - return result; -} - -char *strategyNexthopStateLL_ToString(const StrategyNexthopStateLL *x) { - // this is not implemented - parcTrapNotImplemented("strategyNexthopStateLL_ToString is not implemented"); - return NULL; -} - double strategyNexthopStateLL_GetRTTProbe(StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); - if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) - return DBL_MAX; + if (x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) return DBL_MAX; - if(x->avg_rtt == -1.0){ - if(x->avg_rtt_in_use == -1.0){ + if (x->avg_rtt == -1.0) { + if (x->avg_rtt_in_use == -1.0) { return 0.0; - }else{ - //this happens if the face recevied probes only in in_use mode - //we set the avf_rtt with rtt_in_use + } else { + // this happens if the face recevied probes only in in_use mode + // we set the avf_rtt with rtt_in_use x->avg_rtt = x->avg_rtt_in_use; } } @@ -331,11 +45,9 @@ double strategyNexthopStateLL_GetRTTProbe(StrategyNexthopStateLL *x) { double strategyNexthopStateLL_GetRTTInUse(StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); - if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) - return DBL_MAX; + if (x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) return DBL_MAX; - if(x->avg_rtt_in_use == -1.0) - return strategyNexthopStateLL_GetRTTProbe(x); + if (x->avg_rtt_in_use == -1.0) return strategyNexthopStateLL_GetRTTProbe(x); return x->avg_rtt_in_use; } @@ -343,9 +55,9 @@ double strategyNexthopStateLL_GetRTTInUse(StrategyNexthopStateLL *x) { double strategyNexthopStateLL_GetRTTLive(StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); - if(x->in_use){ + if (x->in_use) { return strategyNexthopStateLL_GetRTTInUse(x); - }else{ + } else { return strategyNexthopStateLL_GetRTTProbe(x); } } @@ -353,46 +65,45 @@ double strategyNexthopStateLL_GetRTTLive(StrategyNexthopStateLL *x) { double strategyNexthopStateLL_GetQueuing(const StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); - if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) - return 0.0; + if (x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) return 0.0; return x->avg_queue; } void strategyNexthopStateLL_AddRttSample(StrategyNexthopStateLL *x, - unsigned int rtt){ + unsigned int rtt) { strategyNexthopStateLL_OptionalAssertValid(x); x->recevied_probes++; - //form uint to double + // form uint to double double drtt = rtt; - if(x->in_use){ - if(x->avg_rtt_in_use == -1.0){ + if (x->in_use) { + if (x->avg_rtt_in_use == -1.0) { x->avg_rtt_in_use = drtt; - }else{ + } else { x->avg_rtt_in_use = (x->avg_rtt_in_use * 0.9) + (drtt * 0.1); } - }else{ - if(x->avg_rtt == -1.0){ - x->avg_rtt = drtt; - }else{ + } else { + if (x->avg_rtt == -1.0) { + x->avg_rtt = drtt; + } else { x->avg_rtt = (x->avg_rtt * 0.9) + (drtt * 0.1); } } - if(x->avg_rtt_in_use == -1.0 || x->avg_rtt == -1.0){ + if (x->avg_rtt_in_use == -1.0 || x->avg_rtt == -1.0) { x->avg_queue = 0.0001; - }else{ + } else { double queue = x->avg_rtt_in_use - x->avg_rtt; - if(queue < 0){ + if (queue < 0) { queue = 0.0001; } x->avg_queue = (x->avg_queue * 0.95) + (0.05 * queue); } } -void strategyNexthopStateLL_SetUnusedFace(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_SetUnusedFace(StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); x->in_use = false; } @@ -403,75 +114,76 @@ unsigned strategyNexthopStateLL_GetFaceId(StrategyNexthopStateLL *x) { } void strategyNexthopStateLL_IncreaseTryToSwitch(StrategyNexthopStateLL *x, - unsigned round){ - if(x->try_to_switch_counter == 0 || - round == (x->last_try_to_switch_round + 1)){ + unsigned round) { + if (x->try_to_switch_counter == 0 || + round == (x->last_try_to_switch_round + 1)) { x->last_try_to_switch_round = round; x->try_to_switch_counter++; - }else{ + } else { x->try_to_switch_counter = 0; } } -unsigned strategyNexthopStateLL_GetTryToSwitch(const StrategyNexthopStateLL *x){ +unsigned strategyNexthopStateLL_GetTryToSwitch( + const StrategyNexthopStateLL *x) { return x->try_to_switch_counter; } -void strategyNexthopStateLL_ResetTryToSwitch(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_ResetTryToSwitch(StrategyNexthopStateLL *x) { x->try_to_switch_counter = 0; } -void strategyNexthopStateLL_SendPacket(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_SendPacket(StrategyNexthopStateLL *x) { x->in_use = true; x->sent_packets++; } -void strategyNexthopStateLL_SentProbe(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_SentProbe(StrategyNexthopStateLL *x) { x->sent_probes++; } -void strategyNexthopStateLL_LostProbe(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_LostProbe(StrategyNexthopStateLL *x) { x->lost_probes++; } -bool strategyNexthopStateLL_IsLossy(const StrategyNexthopStateLL *x){ - if(x->non_lossy_rounds < 10 || - x->avg_loss_rate > MAX_LOSS_RATE){ +bool strategyNexthopStateLL_IsLossy(const StrategyNexthopStateLL *x) { + if (x->non_lossy_rounds < 10 || x->avg_loss_rate > MAX_LOSS_RATE) { return true; } return false; } -void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, bool allowed){ +void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, + bool allowed) { x->is_allowed = allowed; } -bool strategyNexthopStateLL_IsAllowed(const StrategyNexthopStateLL *x){ +bool strategyNexthopStateLL_IsAllowed(const StrategyNexthopStateLL *x) { return x->is_allowed; } -void strategyNexthopStateLL_StartNewRound(StrategyNexthopStateLL *x){ +void strategyNexthopStateLL_StartNewRound(StrategyNexthopStateLL *x) { strategyNexthopStateLL_OptionalAssertValid(x); - if(x->sent_packets == 0) //the face was not used in the last round + if (x->sent_packets == 0) // the face was not used in the last round x->in_use = false; x->sent_packets = 0; - if(x->recevied_probes == 0){ + if (x->recevied_probes == 0) { x->rounds_without_probes++; - }else{ + } else { x->rounds_without_probes = 0; } x->recevied_probes = 0; - //compute losses in this round - if(x->sent_probes != 0){ - double loss_rate = (double) x->lost_probes / (double) x->sent_probes; + // compute losses in this round + if (x->sent_probes != 0) { + double loss_rate = (double)x->lost_probes / (double)x->sent_probes; x->avg_loss_rate = x->avg_loss_rate * 0.7 + loss_rate * 0.3; - if(x->avg_loss_rate > MAX_LOSS_RATE){ + if (x->avg_loss_rate > MAX_LOSS_RATE) { x->non_lossy_rounds = 0; - }else{ + } else { x->non_lossy_rounds++; } } diff --git a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h index 34dbb8262..7f4181d44 100644 --- a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h +++ b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -47,7 +47,7 @@ void strategyNexthopStateLL_Reset(StrategyNexthopStateLL *x); /** */ int strategyNexthopStateLL_Compare(const StrategyNexthopStateLL *instance, - const StrategyNexthopStateLL *other); + const StrategyNexthopStateLL *other); /** */ @@ -57,12 +57,12 @@ StrategyNexthopStateLL *strategyNexthopStateLL_Copy( /** */ void strategyNexthopStateLL_Display(const StrategyNexthopStateLL *instance, - int indentation); + int indentation); /** */ bool strategyNexthopStateLL_Equals(const StrategyNexthopStateLL *x, - const StrategyNexthopStateLL *y); + const StrategyNexthopStateLL *y); /** */ @@ -88,11 +88,10 @@ double strategyNexthopStateLL_GetRTTInUse(StrategyNexthopStateLL *x); double strategyNexthopStateLL_GetRTTLive(StrategyNexthopStateLL *x); double strategyNexthopStateLL_GetQueuing(const StrategyNexthopStateLL *x); void strategyNexthopStateLL_AddRttSample(StrategyNexthopStateLL *x, - unsigned int rtt); - + unsigned int rtt); void strategyNexthopStateLL_IncreaseTryToSwitch(StrategyNexthopStateLL *x, - unsigned round); + unsigned round); unsigned strategyNexthopStateLL_GetTryToSwitch(const StrategyNexthopStateLL *x); void strategyNexthopStateLL_ResetTryToSwitch(StrategyNexthopStateLL *x); @@ -108,7 +107,8 @@ void strategyNexthopStateLL_LostProbe(StrategyNexthopStateLL *x); bool strategyNexthopStateLL_IsLossy(const StrategyNexthopStateLL *x); -void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, bool allowed); +void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, + bool allowed); bool strategyNexthopStateLL_IsAllowed(const StrategyNexthopStateLL *x); diff --git a/hicn-light/src/hicn/strategies/probe_generator.c b/hicn-light/src/hicn/strategies/probe_generator.c new file mode 100644 index 000000000..fd0bf5471 --- /dev/null +++ b/hicn-light/src/hicn/strategies/probe_generator.c @@ -0,0 +1,113 @@ +/* + * 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 "probe_generator.h" + +#include <hicn/core/forwarder.h> +#include <hicn/core/nexthops.h> + +// map functions +static void add_to_map(probe_generator_t *pg, unsigned seq, Ticks now) { + khiter_t k; + int ret; + k = kh_put_bp_map(pg->ticks_by_seq, seq, &ret); + kh_value(pg->ticks_by_seq, k) = now; +} + +static Ticks get_from_map(probe_generator_t *pg, unsigned seq) { + khiter_t k; + k = kh_get_bp_map(pg->ticks_by_seq, seq); + if (k == kh_end(pg->ticks_by_seq)) return 0; + Ticks t = kh_value(pg->ticks_by_seq, k); + return t; +} + +static void remove_from_map(probe_generator_t *pg, unsigned seq) { + khiter_t k; + k = kh_get_bp_map(pg->ticks_by_seq, seq); + if (k != kh_end(pg->ticks_by_seq)) kh_del_bp_map(pg->ticks_by_seq, k); +} + +static void clear_map(probe_generator_t *pg) { + kh_clear(bp_map, pg->ticks_by_seq); +} + +// seq number generator + +static uint32_t get_seq_number(probe_generator_t *pg) { + uint32_t seq = 0; + uint32_t try = 0; + while (try < 3) { // try up to 3 times + seq = + (rand() % (MAX_PROBE_SUFFIX - MIN_PROBE_SUFFIX + 1)) + MIN_PROBE_SUFFIX; + Ticks time = get_from_map(pg, seq); + if (time == 0) return seq; // seq does not exists + try++; + } + return 0; +} + +// probing functions + +probe_generator_t *create_probe_generator() { + probe_generator_t *pg = calloc(1, sizeof(probe_generator_t)); + if (!pg) return NULL; + + pg->ticks_by_seq = kh_init_bp_map(); + return pg; +} + +void destroy_probe_generator(probe_generator_t *pg) { + kh_destroy_bp_map(pg->ticks_by_seq); + free(pg); +} + +int generate_probe(probe_generator_t *pg, const msgbuf_t *msgbuf, + const forwarder_t *forwarder, nexthop_t nexthop) { + msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); + connection_table_t *table = forwarder_get_connection_table(forwarder); + connection_t *conn = connection_table_get_by_id(table, nexthop); + if (!conn) return -1; + + msgbuf_t *probe; + off_t msg_id = msgbuf_pool_get_id(msgbuf_pool, (msgbuf_t *)msgbuf); + off_t probe_offset = msgbuf_pool_clone(msgbuf_pool, &probe, msg_id); + + uint32_t seq = get_seq_number(pg); + if (seq == 0) return -1; + msgbuf_modify_suffix(probe, seq); + connection_send(conn, probe_offset, true); + connection_flush(conn); + add_to_map(pg, seq, ticks_now()); + msgbuf_pool_put(msgbuf_pool, probe); + + return 0; +} + +Ticks register_probe(probe_generator_t *pg, unsigned seq) { + Ticks now = ticks_now(); + add_to_map(pg, seq, now); + return now; +} + +Ticks get_probe_send_time(probe_generator_t *pg, unsigned seq) { + return get_from_map(pg, seq); +} + +void delete_probe(probe_generator_t *pg, unsigned seq) { + remove_from_map(pg, seq); +} + +void delete_all_probes(probe_generator_t *pg) { clear_map(pg); } diff --git a/hicn-light/src/hicn/strategies/probe_generator.h b/hicn-light/src/hicn/strategies/probe_generator.h new file mode 100644 index 000000000..065d824a1 --- /dev/null +++ b/hicn-light/src/hicn/strategies/probe_generator.h @@ -0,0 +1,49 @@ +/* + * 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. + */ + +#ifndef HICNLIGHT_PROBE_GENERATOR +#define HICNLIGHT_PROBE_GENERATOR + +#include <hicn/util/khash.h> +#include <hicn/core/ticks.h> +#include <hicn/core/msgbuf.h> + +#define MIN_PROBE_SUFFIX 0xefffffff +#define MAX_PROBE_SUFFIX 0xffffffff - 1 + +KHASH_MAP_INIT_INT64(bp_map, Ticks); + +struct forwarder_s; + +typedef struct probe_generator { + kh_bp_map_t *ticks_by_seq; +} probe_generator_t; + +probe_generator_t *create_probe_generator(); + +void destroy_probe_generator(probe_generator_t *pg); + +int generate_probe(probe_generator_t *pg, const msgbuf_t *msgbuf, + const struct forwarder_s *forwarder, unsigned nexthop); + +Ticks register_probe(probe_generator_t *pg, unsigned seq); + +Ticks get_probe_send_time(probe_generator_t *pg, unsigned seq); + +void delete_probe(probe_generator_t *pg, unsigned seq); + +void delete_all_probes(probe_generator_t *pg); + +#endif /* HICNLIGHT_PROBE_GENERATOR */ diff --git a/hicn-light/src/hicn/strategies/random.c b/hicn-light/src/hicn/strategies/random.c new file mode 100644 index 000000000..aabae73bc --- /dev/null +++ b/hicn-light/src/hicn/strategies/random.c @@ -0,0 +1,77 @@ +/* + * Copyright (c) 2021 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 <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <hicn/hicn-light/config.h> + +#include <hicn/core/nexthops.h> +#include <hicn/core/strategy.h> +#include <hicn/core/strategy_vft.h> + +#include "random.h" + +static int strategy_random_initialize(strategy_entry_t *entry, + const void *forwarder) { + srand((unsigned int)time(NULL)); + entry->forwarder = forwarder; + return 0; +} + +static int strategy_random_finalize(strategy_entry_t *entry) { + /* Nothing to do */ + return 0; +} + +static int strategy_random_add_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, off_t offset) { + /* Nothing to do */ + return 0; +} + +static int strategy_random_remove_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, off_t offset) { + /* Nothing to do */ + return 0; +} + +static nexthops_t *strategy_random_lookup_nexthops(strategy_entry_t *entry, + nexthops_t *nexthops, + const msgbuf_t *msgbuf) { + if (nexthops_get_curlen(nexthops) == 0) return nexthops; + nexthops_select(nexthops, rand() % nexthops_get_len(nexthops)); + return nexthops; +} + +static int strategy_random_on_data(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *data_nexthops, + const msgbuf_t *msgbuf, + Ticks pitEntryCreation, Ticks objReception) { + /* Nothing to do */ + return 0; +} + +static int strategy_random_on_timeout(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *timeout_nexthops) { + /* Nothing to do */ + return 0; +} + +DECLARE_STRATEGY(random); diff --git a/hicn-light/src/hicn/strategies/rnd.h b/hicn-light/src/hicn/strategies/random.h index 78fb34758..bdea5e4dd 100644 --- a/hicn-light/src/hicn/strategies/rnd.h +++ b/hicn-light/src/hicn/strategies/random.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2021 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: @@ -17,11 +17,19 @@ * Forward randomly */ -#ifndef rnd_h -#define rnd_h +#ifndef HICNLIGHT_STRATEGY_RANDOM_H +#define HICNLIGHT_STRATEGY_RANDOM_H -#include <hicn/strategies/strategyImpl.h> +typedef struct { + void *_; +} strategy_random_nexthop_state_t; -StrategyImpl* strategyRnd_Create(); +typedef struct { + void *_; +} strategy_random_state_t; -#endif // rnd_h +typedef struct { + void *_; +} strategy_random_options_t; + +#endif /* HICNLIGHT_STRATEGY_RANDOM_H */ diff --git a/hicn-light/src/hicn/strategies/replication.c b/hicn-light/src/hicn/strategies/replication.c new file mode 100644 index 000000000..86a3e3431 --- /dev/null +++ b/hicn-light/src/hicn/strategies/replication.c @@ -0,0 +1,98 @@ +/* + * Copyright (c) 2021 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 <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <hicn/hicn-light/config.h> + +#include <hicn/core/nexthops.h> +#include <hicn/core/strategy.h> +#include <hicn/core/strategy_vft.h> + +#include "replication.h" + +/* Shorthand */ +#define strategy_state_t strategy_replication_state_t + +static int strategy_replication_initialize(strategy_entry_t *entry, + const void *forwarder) { + entry->forwarder = forwarder; + strategy_state_t *state = &entry->state.replication; + state->prev_nexthops = malloc(sizeof(nexthops_t)); + *((nexthops_t *)state->prev_nexthops) = NEXTHOPS_EMPTY; + return 0; +} + +static int strategy_replication_finalize(strategy_entry_t *entry) { + /* Nothing to do */ + strategy_state_t *state = &entry->state.replication; + free(state->prev_nexthops); + return 0; +} + +static int strategy_replication_add_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* Nothing to do */ + return 0; +} + +static int strategy_replication_remove_nexthop(strategy_entry_t *entry, + nexthops_t *nexthops, + off_t offset) { + /* Nothing to do */ + return 0; +} + +static nexthops_t *strategy_replication_lookup_nexthops( + strategy_entry_t *entry, nexthops_t *nexthops, const msgbuf_t *msgbuf) { + // if nexthops is different from prev_nexthops send updates + strategy_state_t *state = &entry->state.replication; + + if (!nexthops_equal((nexthops_t *)state->prev_nexthops, nexthops)) { + // send updates + strategy_replication_options_t *options = &entry->options.replication; + update_remote_node_paths(nexthops, entry->forwarder, + options->local_prefixes); + + // update next hops + nexthops_copy(nexthops, (nexthops_t *)state->prev_nexthops); + } + + // Return all next hops + return nexthops; +} + +static int strategy_replication_on_data(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *data_nexthops, + const msgbuf_t *msgbuf, + Ticks pitEntryCreation, + Ticks objReception) { + /* Nothing to do */ + return 0; +} + +static int strategy_replication_on_timeout(strategy_entry_t *entry, + nexthops_t *nexthops, + const nexthops_t *timeout_nexthops) { + /* Nothing to do */ + return 0; +} + +DECLARE_STRATEGY(replication); diff --git a/hicn-light/src/hicn/strategies/replication.h b/hicn-light/src/hicn/strategies/replication.h new file mode 100644 index 000000000..753ae4744 --- /dev/null +++ b/hicn-light/src/hicn/strategies/replication.h @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2021 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. + */ + +/** + * Forward replication of the interest on all the paths + */ + +#ifndef HICNLIGHT_STRATEGY_REPLICATION_H +#define HICNLIGHT_STRATEGY_REPLICATION_H + +#include "local_prefixes.h" + +typedef struct { + void *_; +} strategy_replication_nexthop_state_t; + +typedef struct { + void *prev_nexthops; +} strategy_replication_state_t; + +typedef struct { + local_prefixes_t *local_prefixes; +} strategy_replication_options_t; + +#endif /* HICNLIGHT_STRATEGY_REPLICATION_H */ diff --git a/hicn-light/src/hicn/strategies/rnd.c b/hicn-light/src/hicn/strategies/rnd.c deleted file mode 100644 index 064f3965b..000000000 --- a/hicn-light/src/hicn/strategies/rnd.c +++ /dev/null @@ -1,211 +0,0 @@ -/* - * Copyright (c) 2017-2019 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 <parc/assert/parc_Assert.h> - -#include <parc/algol/parc_HashMap.h> -#include <parc/algol/parc_Memory.h> - -#include <hicn/strategies/rnd.h> - -static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception); -static void _strategyRnd_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId); - -static NumberSet *_strategyRnd_LookupNexthop(StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage); -#ifndef WITH_POLICY -static NumberSet *_strategyRnd_ReturnNexthops(StrategyImpl *strategy); -static unsigned _strategyRnd_CountNexthops(StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ -static void _strategyRnd_AddNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyRnd_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyRnd_ImplDestroy(StrategyImpl **strategyPtr); -static strategy_type _strategyRnd_GetStrategy(StrategyImpl *strategy); - -static StrategyImpl _template = { - .context = NULL, - .receiveObject = &_strategyRnd_ReceiveObject, - .onTimeout = &_strategyRnd_OnTimeout, - .lookupNexthop = &_strategyRnd_LookupNexthop, -#ifndef WITH_POLICY - .returnNexthops = &_strategyRnd_ReturnNexthops, - .countNexthops = &_strategyRnd_CountNexthops, -#endif /* ! WITH_POLICY */ - .addNexthop = &_strategyRnd_AddNexthop, - .removeNexthop = &_strategyRnd_RemoveNexthop, - .destroy = &_strategyRnd_ImplDestroy, - .getStrategy = &_strategyRnd_GetStrategy, -}; - -#ifndef WITH_POLICY -struct strategy_rnd; -typedef struct strategy_rnd StrategyRnd; - -struct strategy_rnd { - NumberSet *nexthops; -}; -#endif /* ! WITH_POLICY */ - -StrategyImpl *strategyRnd_Create() { -#ifndef WITH_POLICY - StrategyRnd *strategy = parcMemory_AllocateAndClear(sizeof(StrategyRnd)); - parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyRnd)); - - strategy->nexthops = numberSet_Create(); -#endif /* ! WITH_POLICY */ - srand((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); -#ifndef WITH_POLICY - impl->context = strategy; -#endif /* ! WITH_POLICY */ - return impl; -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyRnd_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_RANDOM; -} - -#ifndef WITH_POLICY -static int _select_Nexthop(StrategyRnd *strategy) { - unsigned len = (unsigned)numberSet_Length(strategy->nexthops); - if (len == 0) { - return -1; - } - - int rnd = (rand() % len); - return numberSet_GetItem(strategy->nexthops, rnd); -} -#endif /* ! WITH_POLICY */ - -static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, - const NumberSet *egressId, - const Message *objectMessage, - Ticks pitEntryCreation, - Ticks objReception) {} - -static void _strategyRnd_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId) {} - -static NumberSet *_strategyRnd_LookupNexthop(StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage) { - unsigned out_connection; - NumberSet *out = numberSet_Create(); - -#ifdef WITH_POLICY - // We return one next hop at random - out_connection = numberSet_GetItem(nexthops, rand() % numberSet_Length(nexthops)); - -#else - StrategyRnd *srnd = (StrategyRnd *)strategy->context; - unsigned in_connection = message_GetIngressConnectionId(interestMessage); - unsigned nexthopSize = (unsigned)numberSet_Length(srnd->nexthops); - - if ((nexthopSize == 0) || - ((nexthopSize == 1) && - numberSet_Contains(srnd->nexthops, in_connection))) { - // there are no output faces or the input face is also the only output face. - // return null to avoid loops - return out; - } - - do { - out_connection = _select_Nexthop(srnd); - } while (out_connection == in_connection); - - if (out_connection == -1) { - return out; - } -#endif /* WITH_POLICY */ - - numberSet_Add(out, out_connection); - return out; -} - -#ifndef WITH_POLICY -static NumberSet *_strategyRnd_ReturnNexthops(StrategyImpl *strategy) { - StrategyRnd *srnd = (StrategyRnd *)strategy->context; - return srnd->nexthops; -} - -unsigned _strategyRnd_CountNexthops(StrategyImpl *strategy) { - StrategyRnd *srnd = (StrategyRnd *)strategy->context; - return (unsigned)numberSet_Length(srnd->nexthops); -} -#endif /* ! WITH_POLICY */ - -static void _strategyRnd_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { -#ifndef WITH_POLICY - StrategyRnd *srnd = (StrategyRnd *)strategy->context; - if (!numberSet_Contains(srnd->nexthops, connectionId)) { - numberSet_Add(srnd->nexthops, connectionId); - } -#endif /* ! WITH_POLICY */ -} - -static void _strategyRnd_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { -#ifndef WITH_POLICY - StrategyRnd *srnd = (StrategyRnd *)strategy->context; - - if (numberSet_Contains(srnd->nexthops, connectionId)) { - numberSet_Remove(srnd->nexthops, connectionId); - } -#endif /* ! WITH_POLICY */ -} - -static void _strategyRnd_ImplDestroy(StrategyImpl **strategyPtr) { - parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*strategyPtr, - "Parameter must dereference to non-null pointer"); - - StrategyImpl *impl = *strategyPtr; - -#ifndef WITH_POLICY - StrategyRnd *strategy = (StrategyRnd *)impl->context; - numberSet_Release(&(strategy->nexthops)); - parcMemory_Deallocate((void **)&strategy); -#endif /* ! WITH_POLICY */ - - parcMemory_Deallocate((void **)&impl); - *strategyPtr = NULL; -} diff --git a/hicn-light/src/hicn/strategies/strategyImpl.h b/hicn-light/src/hicn/strategies/strategyImpl.h deleted file mode 100644 index 140da5bf8..000000000 --- a/hicn-light/src/hicn/strategies/strategyImpl.h +++ /dev/null @@ -1,73 +0,0 @@ -/* - * Copyright (c) 2017-2019 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. - */ - -/** - * @file strategyImpl.h - * @brief Defines the function structure for a Strategy implementation - * - * <#Detailed Description#> - * - */ - -/** - * A dispatch structure for a concrete implementation of a forwarding strategy. - */ - -#ifndef strategyImpl_h -#define strategyImpl_h - -#include <hicn/core/message.h> -#include <hicn/core/numberSet.h> - -struct strategy_impl; -typedef struct strategy_impl StrategyImpl; - -/** - * @typedef StrategyImpl - * @abstract Forwarding strategy implementation - * @constant receiveObject is called when we receive an object and have a - * measured round trip time. This allows a strategy to update its performance - * data. - * @constant lookupNexthop Find the set of nexthops to use for the Interest. - * May be empty, should not be NULL. Must be destroyed. - * @constant addNexthop Add a nexthop to the list of available nexthops with a - * routing protocol-specific cost. - * @constant destroy cleans up the strategy, freeing all memory and state. A - * strategy is reference counted, so the final destruction only happens after - * the last reference is released. - * @discussion <#Discussion#> - */ -struct strategy_impl { - void *context; - void (*receiveObject)(StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks pitEntryCreation, - Ticks objReception); - void (*onTimeout)(StrategyImpl *strategy, const NumberSet *egressId); - NumberSet *(*lookupNexthop)(StrategyImpl *strategy, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage); -#ifndef WITH_POLICY - NumberSet *(*returnNexthops)(StrategyImpl *strategy); - unsigned (*countNexthops)(StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ - void (*addNexthop)(StrategyImpl *strategy, unsigned connectionId); - void (*removeNexthop)(StrategyImpl *strategy, unsigned connectionId); - void (*destroy)(StrategyImpl **strategyPtr); - strategy_type (*getStrategy)(StrategyImpl *strategy); -}; - -#endif // strategyImpl_h |