diff options
author | Luca Muscariello <lumuscar+fdio@cisco.com> | 2017-02-24 07:59:45 +0000 |
---|---|---|
committer | Gerrit Code Review <gerrit@fd.io> | 2017-02-24 07:59:45 +0000 |
commit | e0ec678c016fbce560e7f94973d4fada3ba5e799 (patch) | |
tree | a171ed331a830510f3064a6ad99b296ac1b2d2bc /metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c | |
parent | f28308bd99381ef5f1e178e2e1f870f245e35873 (diff) | |
parent | c580a00aac271a524e5a75b35f4b91c174ed227b (diff) |
Merge "Initial commit: sb-forwarder, metis." into sb-forwarder/master
Diffstat (limited to 'metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c')
-rw-r--r-- | metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c | 356 |
1 files changed, 356 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c new file mode 100644 index 00000000..7aee000a --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c @@ -0,0 +1,356 @@ +/* + * Copyright (c) 2017 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 <config.h> +#include <stdio.h> +#include <string.h> +#include <time.h> +#include <stdlib.h> +#include <limits.h> + +#include <LongBow/runtime.h> + +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_HashMap.h> +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_Unsigned.h> + +#include <ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.h> +#include <ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.h> + +const unsigned PROBE_FREQUENCY = 1024; + +static void _strategyLoadBalancerWithPD_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt); +static void _strategyLoadBalancerWithPD_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId); +static MetisNumberSet *_strategyLoadBalancerWithPD_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage); +static MetisNumberSet *_strategyLoadBalancerWithPD_ReturnNexthops(MetisStrategyImpl *strategy); +static unsigned _strategyLoadBalancerWithPD_CountNexthops(MetisStrategyImpl *strategy); +static void _strategyLoadBalancerWithPD_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyLoadBalancerWithPD_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyLoadBalancerWithPD_ImplDestroy(MetisStrategyImpl **strategyPtr); +static const char *_strategyLoadBalancerWithPD_GetStrategy(MetisStrategyImpl *strategy); + + +static MetisStrategyImpl _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; + MetisNumberSet *nexthops; + MetisConnectionTable *connTable; + bool toInit; + unsigned int fwdPackets; +}; + +MetisStrategyImpl * +strategyLoadBalancerWithPD_Create() +{ + StrategyLoadBalancerWithPD *strategy = parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancerWithPD)); + assertNotNull(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 = metisNumberSet_Create(); + srand(time(NULL)); + + MetisStrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(MetisStrategyImpl)); + assertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisStrategyImpl)); + memcpy(impl, &_template, sizeof(MetisStrategyImpl)); + impl->context = strategy; + strategy->connTable = NULL; + strategy->fwdPackets = 0; + strategy->toInit = true; + + return impl; +} + +void +strategyLoadBalancerWithPD_SetConnectionTable(MetisStrategyImpl *strategy, MetisConnectionTable *connTable) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + lb->connTable = connTable; +} + +// ======================================================= +// Dispatch API + + +static const char* +_strategyLoadBalancerWithPD_GetStrategy(MetisStrategyImpl *strategy) +{ + return FWD_STRATEGY_LOADBALANCER_WITH_DELAY; +} + +static void +_update_Stats(StrategyLoadBalancerWithPD *strategy, StrategyNexthopStateWithPD *state, bool inc, MetisTicks 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 = metisNumberSet_Length(strategy->nexthops); + for (unsigned i = 0; i < size; i++) { + unsigned nhop = metisNumberSet_GetItem(strategy->nexthops, i); + MetisConnection *conn = (MetisConnection *) metisConnectionTable_FindById(strategy->connTable, nhop); + if (conn != NULL) { + metisConnection_Probe(conn); + unsigned delay = metisConnection_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(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + + for (unsigned i = 0; i < metisNumberSet_Length(egressId); i++) { + unsigned outId = metisNumberSet_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(MetisStrategyImpl *strategy, const MetisNumberSet *egressId) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + + for (unsigned i = 0; i < metisNumberSet_Length(egressId); i++) { + unsigned outId = metisNumberSet_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 MetisNumberSet 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 MetisNumberSet +static MetisNumberSet * +_strategyLoadBalancerWithPD_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + + unsigned in_connection = metisMessage_GetIngressConnectionId(interestMessage); + PARCUnsigned *in = parcUnsigned_Create(in_connection); + + unsigned mapSize = parcHashMap_Size(lb->strategy_state); + MetisNumberSet *outList = metisNumberSet_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! + trapNotImplemented("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); + + metisNumberSet_Add(outList, out_connection); + return outList; +} + +static MetisNumberSet * +_strategyLoadBalancerWithPD_ReturnNexthops(MetisStrategyImpl *strategy) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + return lb->nexthops; +} + +unsigned +_strategyLoadBalancerWithPD_CountNexthops(MetisStrategyImpl *strategy) +{ + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + return metisNumberSet_Length(lb->nexthops); +} + +static void +_strategyLoadBalancerWithPD_resetState(MetisStrategyImpl *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(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ + unsigned connectionId = cpiRouteEntry_GetInterfaceIndex(route); //this returns what in all the rest of the ccnx code is called connection id! + + + 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); + metisNumberSet_Add(lb->nexthops, connectionId); + _strategyLoadBalancerWithPD_resetState(strategy); + } +} + +static void +_strategyLoadBalancerWithPD_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ + unsigned connectionId = cpiRouteEntry_GetInterfaceIndex(route); + StrategyLoadBalancerWithPD *lb = (StrategyLoadBalancerWithPD *) strategy->context; + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + if (parcHashMap_Contains(lb->strategy_state, cid)) { + parcHashMap_Remove(lb->strategy_state, cid); + metisNumberSet_Remove(lb->nexthops, connectionId); + _strategyLoadBalancerWithPD_resetState(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void +_strategyLoadBalancerWithPD_ImplDestroy(MetisStrategyImpl **strategyPtr) +{ + assertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + assertNotNull(*strategyPtr, "Parameter must dereference to non-null pointer"); + + MetisStrategyImpl *impl = *strategyPtr; + StrategyLoadBalancerWithPD *strategy = (StrategyLoadBalancerWithPD *) impl->context; + + parcHashMap_Release(&(strategy->strategy_state)); + metisNumberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **) &strategy); + parcMemory_Deallocate((void **) &impl); + *strategyPtr = NULL; +} |