aboutsummaryrefslogtreecommitdiffstats
path: root/hicn-light/src/hicn/strategies/low_latency.c
diff options
context:
space:
mode:
Diffstat (limited to 'hicn-light/src/hicn/strategies/low_latency.c')
-rw-r--r--hicn-light/src/hicn/strategies/low_latency.c783
1 files changed, 783 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/strategies/low_latency.c b/hicn-light/src/hicn/strategies/low_latency.c
new file mode 100644
index 000000000..9f7ecb89c
--- /dev/null
+++ b/hicn-light/src/hicn/strategies/low_latency.c
@@ -0,0 +1,783 @@
+/*
+ * 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.
+ */
+
+#if 0
+
+#include <hicn/hicn-light/config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <math.h>
+
+#include <hicn/base/khash.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 "low_latency.h"
+
+#define STABILITY_FACTOR 15
+#define MAX_SWITCH_TRY 10
+#define MAX_LATENCY_DIFF 10
+#define MAX_TOLLERATED_LATENCY_DIFF 15
+#define MAX_ROUNDS_MP_WITHOUT_CHECK 2
+#define MAX_ROUNDS_AVOIDING_MULTIPATH 40 /* about 20 sec */
+#define MAX_ROUNDS_WITH_ERROR 4
+#define PROBE_LIFETIME 500 /* ms */
+
+#define 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
+ */
+#define MIN_NON_LOSSY_ROUNDS 10
+
+/*
+ * Number of rounds in non lossy mode before switch to no lossy state
+ * Defaults to 10 %
+ */
+#define MAX_LOSS_RATE 0.10
+
+/* Shorthands */
+#define nexthop_state_t strategy_low_latency_nexthop_state_t
+#define state_t strategy_low_latency_state_t
+
+#define NEXTHOP_STATE_INIT { \
+ .in_use = false, \
+ .is_allowed = true, \
+ .sent_packets = 0, \
+ .last_try_to_switch_round = 0, \
+ .try_to_switch_counter = 0, \
+ .recevied_probes = 0, \
+ .rounds_without_probes = 0, \
+ .sent_probes = 0, \
+ .lost_probes = 0, \
+ .non_lossy_rounds = MIN_NON_LOSSY_ROUNDS, \
+ .avg_rtt = -1.0, \
+ .avg_rtt_in_use = -1.0, \
+ .avg_queue = 0.0001, \
+ .avg_loss_rate = 0.0, \
+}
+
+// XXX ????
+#define STATE_INIT { \
+}
+
+static
+ void
+strategy_low_latency_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
+strategy_low_latency_SendMapmeUpdate(StrategyLowLatency *ll,
+ const NumberSet * nexthops){
+ MapMe * mapme = forwarder_getMapmeInstance(ll->forwarder);
+ FIB * fib = forwarder_getFib((Forwarder*) ll->forwarder);
+ for(unsigned i = 0; i < ll->related_prefixes_len; i++){
+ FibEntry *fibEntry = fib_MatchName(fib, ll->related_prefixes[i]);
+ if (!fibEntry)
+ continue;
+ mapme_maybe_send_to_nexthops(mapme, fibEntry, nexthops);
+ }
+}
+
+static
+void
+strategy_low_latency_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]));
+ }
+ strategy_low_latency_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]));
+ strategy_low_latency_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]));
+ strategy_low_latency_SendMapmeUpdate(ll,out);
+ }
+ }
+ }
+ numberSet_Release(&out);
+ }
+ }
+}
+
+static
+void
+strategy_low_latency_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;
+ strategy_low_latency_SelectBestFaces(ll, true);
+
+ struct timeval timeout = {0, 500000};
+ parcEventTimer_Start(ll->computeBestFace, &timeout);
+}
+
+static
+void
+_startTimers(strategy_entry_t * entry)
+{
+ struct timeval timeoutProbes = {0, 10000};
+ struct timeval timeoutBF = {1, 0};
+
+ parcEventTimer_Start(entry->state.sendProbes, &timeoutProbes);
+ parcEventTimer_Start(entry->state.computeBestFace, &timeoutBF);
+}
+
+static
+void
+_stopTimers(strategy_entry_t * entry)
+{
+ parcEventTimer_Stop(entry->state.sendProbes);
+ parcEventTimer_Stop(entry->state.computeBestFace);
+}
+
+static
+void
+strategy_low_latency_initialize(strategy_entry_t * entry)
+{
+ srand((unsigned int)time(NULL));
+
+ /* XXX TODO Three hashmaps to initialize */
+ strategy->strategy_state = parcHashMap_Create();
+ strategy->pending_probes_ticks = parcHashMap_Create();
+ strategy->pending_probes_faces = parcHashMap_Create();
+
+ Dispatcher *dispatcher = forwarder_GetDispatcher((Forwarder *)ll->forwarder);
+ ip_prefix_t address;
+ nameBitvector_ToIPAddress(name_GetContentName(
+ fibEntry_GetPrefix(fibEntry)), &address);
+
+ entry->state = {
+ .probe = messageHandler_CreateProbePacket(HF_INET6_TCP, PROBE_LIFETIME),
+ .name = messageHandler_CreateProbeName(&address);
+ .sendProbes = dispatcher_CreateTimer(dispatcher, false,
+ strategy_low_latency_SendProbesCB, ll);
+ .round = 0;
+ .rounds_in_multipath = 0;
+ .rounds_with_error = 0;
+ .rounds_avoiding_multipath = 0;
+ .use2paths = false;
+ .avoid_multipath = false;
+ .computeBestFace = dispatcher_CreateTimer(dispatcher, false,
+ strategy_low_latency_BestFaceCB, ll);
+ .related_prefixes_len = related_prefixes_len;
+ // XXX TODO
+ .related_prefixes = malloc(sizeof(Name *) * related_prefixes_len);
+ };
+
+ for(unsigned i = 0; i < entry->state.related_prefixes_len; i++){
+ entry->state.related_prefixes[i] = name_Copy(related_prefixes[i]);
+ }
+}
+
+static
+void
+strategy_low_latency_finalize(strategy_entry_t * entry)
+{
+ _stopTimers(entry);
+
+ 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);
+
+ parcMemory_Deallocate((void **)&strategy);
+ parcMemory_Deallocate((void **)&impl);
+ *strategyPtr = NULL;
+}
+
+static
+void
+strategy_low_latency_add_nexthop(strategy_entry_t * entry, unsigned nexthop, nexthop_state_t * state)
+{
+ 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;
+ }
+ }
+
+ if(parcHashMap_Size(ll->strategy_state) >= 2){
+ _startTimers(strategy);
+ }
+
+ parcUnsigned_Release(&cid);
+}
+
+static
+void
+strategy_low_latency_remove_nexthop(strategy_entry_t * entry, unsigned nexthop, nexthop_state_t * state)
+{
+ bool reset_bestFaces = false;
+
+ if((entry->state.bestFaces[0] != NULL &&
+ strategyNexthopStateLL_GetFaceId(entry->state.bestFaces[0]) == connectionId) ||
+ (entry->state.bestFaces[1] != NULL &&
+ strategyNexthopStateLL_GetFaceId(entry->state.bestFaces[1]) == connectionId)){
+ reset_bestFaces = true;
+ }
+
+ PARCUnsigned *cid = parcUnsigned_Create(connectionId);
+
+ if (parcHashMap_Contains(entry->state.strategy_state, cid)) {
+ parcHashMap_Remove(entry->state.strategy_state, cid);
+ }
+
+ if(reset_bestFaces){
+ entry->state.bestFaces[0] = NULL;
+ entry->state.bestFaces[1] = NULL;
+ strategy_low_latency_SelectBestFaces(ll, false);
+ }
+
+ if(parcHashMap_Size(entry->state.strategy_state) < 2){
+ _stopTimers(strategy);
+ }
+
+ parcUnsigned_Release(&cid);
+}
+
+static
+nexthops_t *
+strategy_low_latency_lookup_nexthops(strategy_entry_t * entry,
+ const msgbuf_t * msgbuf)
+{
+ //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
+ strategy_low_latency_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;
+}
+
+
+
+static
+void
+strategy_low_latency_on_data(strategy_entry_t * entry,
+ const nexthops_t * nexthops, const msgbuf_t * msgbuf,
+ Ticks pitEntryCreation, Ticks objReception)
+{
+ if (!msgbuf_is_probe(msgbuf))
+ return;
+
+ uint32_t seq = messageHandler_GetSegment(message_FixedHeader(objectMessage));
+ if (!parcHashMap_Contains(ll->pending_probes_ticks, seq))
+ return; // unexpected
+
+ /* A single nexthop is expected */
+ unsigned nexthop;
+ nexthops_foreach(nexthops, nexthop, {
+ const StrategyNexthopStateLL *state =
+ parcHashMap_Get(ll->strategy_state, nexthop);
+ if (!state)
+ // this may happen if we remove a face/route while downloading a file
+ // we should ignore this timeout
+ continue;
+
+ Ticks time = parcUnsigned_GetUnsigned(
+ parcHashMap_Get(ll->pending_probes_ticks, 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, seq);
+ }
+ };
+}
+
+static
+void
+strategy_low_latency_on_timeout(strategy_entry_t * entry, const nexthops_t * nexthops)
+{
+ /* Nothing to do */
+}
+
+DECLARE_STRATEGY(low_latency);
+
+#undef nexthop_state_t
+#undef state_t
+
+#endif