diff options
author | 2019-03-23 14:13:53 +0100 | |
---|---|---|
committer | 2019-03-24 14:11:17 +0100 | |
commit | eb323e056e747d71867cf965434811c1de925de2 (patch) | |
tree | 23a6096823d795efe448559cf0409a18ab47932d /hicn-light/src/strategies/loadBalancerWithPD.c | |
parent | 43562f9f02d35e5d540ab4028a0326c0c7cd4898 (diff) |
[HICN-141] Definition of a C API for hicn-light
Change-Id: Id861f0abe58b1e3c9ba8cc76701da0f9c6801748
Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>
Signed-off-by: Angelo Mantellini <manangel@cisco.com>
Diffstat (limited to 'hicn-light/src/strategies/loadBalancerWithPD.c')
-rw-r--r-- | hicn-light/src/strategies/loadBalancerWithPD.c | 368 |
1 files changed, 0 insertions, 368 deletions
diff --git a/hicn-light/src/strategies/loadBalancerWithPD.c b/hicn-light/src/strategies/loadBalancerWithPD.c deleted file mode 100644 index c9c1479a2..000000000 --- a/hicn-light/src/strategies/loadBalancerWithPD.c +++ /dev/null @@ -1,368 +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 <limits.h> -#include <src/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 <src/strategies/loadBalancerWithPD.h> -#include <src/strategies/nexthopStateWithPD.h> - -const unsigned PROBE_FREQUENCY = 1024; - -static void _strategyLoadBalancerWithPD_ReceiveObject( - StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); -static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId); -static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( - StrategyImpl *strategy, const Message *interestMessage); -static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( - StrategyImpl *strategy); -static unsigned _strategyLoadBalancerWithPD_CountNexthops( - StrategyImpl *strategy); -static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancerWithPD_ImplDestroy(StrategyImpl **strategyPtr); -static strategy_type _strategyLoadBalancerWithPD_GetStrategy( - StrategyImpl *strategy); - -static StrategyImpl _template = { - .context = NULL, - .receiveObject = &_strategyLoadBalancerWithPD_ReceiveObject, - .onTimeout = &_strategyLoadBalancerWithPD_OnTimeout, - .lookupNexthop = &_strategyLoadBalancerWithPD_LookupNexthop, - .returnNexthops = &_strategyLoadBalancerWithPD_ReturnNexthops, - .countNexthops = &_strategyLoadBalancerWithPD_CountNexthops, - .addNexthop = &_strategyLoadBalancerWithPD_AddNexthop, - .removeNexthop = &_strategyLoadBalancerWithPD_RemoveNexthop, - .destroy = &_strategyLoadBalancerWithPD_ImplDestroy, - .getStrategy = &_strategyLoadBalancerWithPD_GetStrategy, -}; - -struct strategy_load_balancer_with_pd; -typedef struct strategy_load_balancer_with_pd StrategyLoadBalancerWithPD; - -struct strategy_load_balancer_with_pd { - double weights_sum; - unsigned min_delay; - // hash map from connectionId to StrategyNexthopState - PARCHashMap *strategy_state; - NumberSet *nexthops; - ConnectionTable *connTable; - bool toInit; - unsigned int fwdPackets; -}; - -StrategyImpl *strategyLoadBalancerWithPD_Create() { - StrategyLoadBalancerWithPD *strategy = - parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancerWithPD)); - parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyLoadBalancerWithPD)); - - strategy->weights_sum = 0.0; - strategy->min_delay = INT_MAX; - strategy->strategy_state = parcHashMap_Create(); - strategy->nexthops = numberSet_Create(); - 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; - strategy->connTable = NULL; - strategy->fwdPackets = 0; - strategy->toInit = true; - - return impl; -} - -void strategyLoadBalancerWithPD_SetConnectionTable(StrategyImpl *strategy, - ConnectionTable *connTable) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - lb->connTable = connTable; -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyLoadBalancerWithPD_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_LOADBALANCER_WITH_DELAY; -} - -static void _update_Stats(StrategyLoadBalancerWithPD *strategy, - StrategyNexthopStateWithPD *state, bool inc, - Ticks rtt) { - const double ALPHA = 0.9; - double w = strategyNexthopStateWithPD_GetWeight(state); - strategy->weights_sum -= w; - w = strategyNexthopStateWithPD_UpdateState(state, inc, strategy->min_delay, - ALPHA); - strategy->weights_sum += w; -} - -static void _sendProbes(StrategyLoadBalancerWithPD *strategy) { - unsigned size = (unsigned)numberSet_Length(strategy->nexthops); - for (unsigned i = 0; i < size; i++) { - unsigned nhop = numberSet_GetItem(strategy->nexthops, i); - Connection *conn = - (Connection *)connectionTable_FindById(strategy->connTable, nhop); - if (conn != NULL) { - connection_Probe(conn); - unsigned delay = (unsigned)connection_GetDelay(conn); - PARCUnsigned *cid = parcUnsigned_Create(nhop); - StrategyNexthopStateWithPD *elem = - (StrategyNexthopStateWithPD *)parcHashMap_Get( - strategy->strategy_state, cid); - strategyNexthopStateWithPD_SetDelay(elem, delay); - if (delay < strategy->min_delay && delay != 0) { - strategy->min_delay = delay; - } - - parcUnsigned_Release(&cid); - } - } -} - -static unsigned _select_Nexthop(StrategyLoadBalancerWithPD *strategy) { - strategy->fwdPackets++; - if (strategy->toInit || strategy->fwdPackets == PROBE_FREQUENCY) { - strategy->toInit = false; - strategy->fwdPackets = 0; - _sendProbes(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 StrategyNexthopStateWithPD *elem = - parcHashMap_Get(strategy->strategy_state, cid); - - double w = strategyNexthopStateWithPD_GetWeight(elem); - - // printf("next = %u .. pi %u avgpi %f w %f avgrtt - // %f\n",parcUnsigned_GetUnsigned(cid), - // strategyNexthopStateWithPD_GetPI(elem), - // strategyNexthopStateWithPD_GetWeight(elem), - // strategyNexthopStateWithPD_GetWeight(elem), - // strategyNexthopStateWithPD_GetAvgRTT(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; -} - -static void _strategyLoadBalancerWithPD_ReceiveObject( - StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopStateWithPD *state = - parcHashMap_Get(lb->strategy_state, cid); - if (state != NULL) { - _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } -} - -static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopStateWithPD *state = - parcHashMap_Get(lb->strategy_state, cid); - if (state != NULL) { - _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } -} - -// ATTENTION!! This interface force us to create a NumberSet which need to be -// delited somewhere The specification in the interface requires that this -// function never returns NULL. in case we have no output face we need to return -// an empty NumberSet -static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( - StrategyImpl *strategy, const Message *interestMessage) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - unsigned in_connection = message_GetIngressConnectionId(interestMessage); - PARCUnsigned *in = parcUnsigned_Create(in_connection); - - unsigned mapSize = (unsigned)parcHashMap_Size(lb->strategy_state); - NumberSet *outList = numberSet_Create(); - - 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 StrategyNexthopStateWithPD *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, (StrategyNexthopStateWithPD *)state, true, 0); - - parcUnsigned_Release(&in); - parcUnsigned_Release(&out); - - numberSet_Add(outList, out_connection); - return outList; -} - -static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( - StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - return lb->nexthops; -} - -unsigned _strategyLoadBalancerWithPD_CountNexthops(StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - return (unsigned)numberSet_Length(lb->nexthops); -} - -static void _strategyLoadBalancerWithPD_resetState(StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - lb->weights_sum = 0.0; - lb->min_delay = INT_MAX; - lb->toInit = true; - PARCIterator *it = parcHashMap_CreateKeyIterator(lb->strategy_state); - - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - StrategyNexthopStateWithPD *elem = - (StrategyNexthopStateWithPD *)parcHashMap_Get(lb->strategy_state, cid); - - strategyNexthopStateWithPD_Reset(elem); - lb->weights_sum += strategyNexthopStateWithPD_GetWeight(elem); - } - - parcIterator_Release(&it); -} - -static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyNexthopStateWithPD *state = strategyNexthopStateWithPD_Create(); - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - if (!parcHashMap_Contains(lb->strategy_state, cid)) { - parcHashMap_Put(lb->strategy_state, cid, state); - numberSet_Add(lb->nexthops, connectionId); - _strategyLoadBalancerWithPD_resetState(strategy); - } -} - -static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - if (parcHashMap_Contains(lb->strategy_state, cid)) { - parcHashMap_Remove(lb->strategy_state, cid); - numberSet_Remove(lb->nexthops, connectionId); - _strategyLoadBalancerWithPD_resetState(strategy); - } - - parcUnsigned_Release(&cid); -} - -static void _strategyLoadBalancerWithPD_ImplDestroy( - StrategyImpl **strategyPtr) { - parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*strategyPtr, - "Parameter must dereference to non-null pointer"); - - StrategyImpl *impl = *strategyPtr; - StrategyLoadBalancerWithPD *strategy = - (StrategyLoadBalancerWithPD *)impl->context; - - parcHashMap_Release(&(strategy->strategy_state)); - numberSet_Release(&(strategy->nexthops)); - - parcMemory_Deallocate((void **)&strategy); - parcMemory_Deallocate((void **)&impl); - *strategyPtr = NULL; -} |