From c580a00aac271a524e5a75b35f4b91c174ed227b Mon Sep 17 00:00:00 2001 From: michele papalini Date: Thu, 23 Feb 2017 17:01:34 +0100 Subject: Initial commit: sb-forwarder, metis. Change-Id: I65ee3c851a6901929ef4417ad80d34bca0dce445 Signed-off-by: michele papalini --- .../forwarder/metis/strategies/metis_Strategy.h | 33 ++ .../metis/strategies/metis_StrategyImpl.c | 33 ++ .../metis/strategies/metis_StrategyImpl.h | 67 ++++ .../ccnx/forwarder/metis/strategies/strategy_All.c | 102 ++++++ .../ccnx/forwarder/metis/strategies/strategy_All.h | 29 ++ .../metis/strategies/strategy_BestUnipath.h | 26 ++ .../ccnx/forwarder/metis/strategies/strategy_CNF.h | 41 +++ .../metis/strategies/strategy_LoadBalancer.c | 291 +++++++++++++++++ .../metis/strategies/strategy_LoadBalancer.h | 27 ++ .../metis/strategies/strategy_LoadBalancerWithPD.c | 356 +++++++++++++++++++++ .../metis/strategies/strategy_LoadBalancerWithPD.h | 30 ++ .../metis/strategies/strategy_NexthopState.c | 237 ++++++++++++++ .../metis/strategies/strategy_NexthopState.h | 91 ++++++ .../metis/strategies/strategy_NexthopStateWithPD.c | 276 ++++++++++++++++ .../metis/strategies/strategy_NexthopStateWithPD.h | 94 ++++++ .../ccnx/forwarder/metis/strategies/strategy_Rnd.c | 191 +++++++++++ .../ccnx/forwarder/metis/strategies/strategy_Rnd.h | 28 ++ .../metis/strategies/strategy_RndSegment.c | 226 +++++++++++++ .../metis/strategies/strategy_RndSegment.h | 26 ++ .../metis/strategies/strategy_WeightedRoundRobin.h | 28 ++ .../forwarder/metis/strategies/test/CMakeLists.txt | 13 + .../metis/strategies/test/test_strategy_All.c | 132 ++++++++ 22 files changed, 2377 insertions(+) create mode 100644 metis/ccnx/forwarder/metis/strategies/metis_Strategy.h create mode 100644 metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.c create mode 100644 metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_All.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_All.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_BestUnipath.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_CNF.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_Rnd.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_Rnd.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.c create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.h create mode 100644 metis/ccnx/forwarder/metis/strategies/strategy_WeightedRoundRobin.h create mode 100644 metis/ccnx/forwarder/metis/strategies/test/CMakeLists.txt create mode 100644 metis/ccnx/forwarder/metis/strategies/test/test_strategy_All.c (limited to 'metis/ccnx/forwarder/metis/strategies') diff --git a/metis/ccnx/forwarder/metis/strategies/metis_Strategy.h b/metis/ccnx/forwarder/metis/strategies/metis_Strategy.h new file mode 100644 index 00000000..251d4284 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/metis_Strategy.h @@ -0,0 +1,33 @@ +/* + * 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. + */ + + + +/** + * A forwarding strategy for a namespace + */ + +#ifndef Metis_metis_Strategy_h +#define Metis_metis_Strategy_h + +#include + +struct metis_strategy; +typedef struct metis_strategy MetisStrategy; + +MetisStrategy *metisStrategy_Create(MetisStrategyImpl *impl); + +MetisNumberSet *metisStrategy_LookupNexthops(const CCNxName *name, uint32_t ingressInterface); +#endif // Metis_metis_Strategy_h diff --git a/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.c b/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.c new file mode 100644 index 00000000..f383ecd7 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.c @@ -0,0 +1,33 @@ +/* + * 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. + */ + +/** + * @file metis_StrategyImpl.h + * @brief Defines the function structure for a Strategy implementation + * + * <#Detailed Description#> + * + */ + +/** + * A dispatch structure for a concrete implementation of a forwarding strategy. + */ + + +const char *FWD_STRATEGY_LOADBALANCER = "loadbalancer"; +const char *FWD_STRATEGY_RANDOM = "random"; +const char *FWD_STRATEGY_RANDOM_PER_DASH_SEGMENT = "random_per_dash_segment"; +const char *FWD_STRATEGY_LOADBALANCER_WITH_DELAY = "loadbalancer_with_delay"; + diff --git a/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.h b/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.h new file mode 100644 index 00000000..cd93da66 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/metis_StrategyImpl.h @@ -0,0 +1,67 @@ +/* + * 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. + */ + +/** + * @file metis_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 Metis_metis_StrategyImpl_h +#define Metis_metis_StrategyImpl_h + +#include +#include +#include + +struct metis_strategy_impl; +typedef struct metis_strategy_impl MetisStrategyImpl; + +extern const char *FWD_STRATEGY_LOADBALANCER; +extern const char *FWD_STRATEGY_RANDOM; +extern const char *FWD_STRATEGY_RANDOM_PER_DASH_SEGMENT; +extern const char *FWD_STRATEGY_LOADBALANCER_WITH_DELAY; + +/** + * @typedef MetisStrategyImpl + * @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 metis_strategy_impl { + void *context; + void (*receiveObject)(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt); + void (*onTimeout)(MetisStrategyImpl *strategy, const MetisNumberSet *egressId); + MetisNumberSet * (*lookupNexthop)(MetisStrategyImpl * strategy, const MetisMessage * interestMessage); + MetisNumberSet * (*returnNexthops)(MetisStrategyImpl * strategy); + unsigned (*countNexthops)(MetisStrategyImpl *strategy); + void (*addNexthop)(MetisStrategyImpl *strategy, CPIRouteEntry *route); + void (*removeNexthop)(MetisStrategyImpl *strategy, CPIRouteEntry *route); + void (*destroy)(MetisStrategyImpl **strategyPtr); + const char * (*getStrategy)(MetisStrategyImpl * strategy); +}; +#endif // Metis_metis_StrategyImpl_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_All.c b/metis/ccnx/forwarder/metis/strategies/strategy_All.c new file mode 100644 index 00000000..5882b38c --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_All.c @@ -0,0 +1,102 @@ +/* + * 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. + */ + +/** + * THIS STRATEGY IS DEPRECATED + */ + +#include +#include +#include + +#include + +#include + +#include + +static void _strategyAll_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet * egressId, const MetisMessage *objectMessage, MetisTicks rtt); +static MetisNumberSet *_strategyAll_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage); +static void _strategyAll_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyAll_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyAll_ImplDestroy(MetisStrategyImpl **strategyPtr); + +static MetisStrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyAll_ReceiveObject, + .lookupNexthop = &_strategyAll_LookupNexthop, + .addNexthop = &_strategyAll_AddNexthop, + .removeNexthop = &_strategyAll_RemoveNexthop, + .destroy = &_strategyAll_ImplDestroy, +}; + +struct strategy_all; +typedef struct strategy_all StrategyAll; + +struct strategy_all { + int x; +}; + +MetisStrategyImpl * +strategyAll_Create() +{ + StrategyAll *strategy = parcMemory_AllocateAndClear(sizeof(StrategyAll)); + assertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyAll)); + + MetisStrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(MetisStrategyImpl)); + assertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisStrategyImpl)); + memcpy(impl, &_template, sizeof(MetisStrategyImpl)); + impl->context = strategy; + + return impl; +} + +// ======================================================= +// Dispatch API + +static void +_strategyAll_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet * egressId, const MetisMessage *objectMessage, MetisTicks rtt) +{ +} + +static MetisNumberSet * +_strategyAll_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage) +{ + return NULL; +} + +static void +_strategyAll_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ +} + +static void +_strategyAll_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ +} + +static void +_strategyAll_ImplDestroy(MetisStrategyImpl **strategyPtr) +{ + assertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + assertNotNull(*strategyPtr, "Parameter must dereference to non-null pointer"); + + MetisStrategyImpl *impl = *strategyPtr; + StrategyAll *strategy = (StrategyAll *) impl->context; + + parcMemory_Deallocate((void **) &strategy); + parcMemory_Deallocate((void **) &impl); + *strategyPtr = NULL; +} diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_All.h b/metis/ccnx/forwarder/metis/strategies/strategy_All.h new file mode 100644 index 00000000..521e4903 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_All.h @@ -0,0 +1,29 @@ +/* + * 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. + */ + + + +/** + * Forward to all nexthops + * THIS STRATEGY IS DEPRECATED + */ + +#ifndef Metis_strategy_All_h +#define Metis_strategy_All_h + +#include + +MetisStrategyImpl *metisStrategyAll_Create(); +#endif // Metis_strategy_All_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_BestUnipath.h b/metis/ccnx/forwarder/metis/strategies/strategy_BestUnipath.h new file mode 100644 index 00000000..ee36d07d --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_BestUnipath.h @@ -0,0 +1,26 @@ +/* + * 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. + */ + + + +/** + * THIS STRATEGY IS NOT IMPLEMENTED + */ + +#ifndef Metis_strategy_BestUnipath_h +#define Metis_strategy_BestUnipath_h + +#include +#endif // Metis_strategy_BestUnipath_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_CNF.h b/metis/ccnx/forwarder/metis/strategies/strategy_CNF.h new file mode 100644 index 00000000..2fdda7a3 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_CNF.h @@ -0,0 +1,41 @@ +/* + * 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. + */ + + + +/** + * Conjunctive Normal Form forwarding. Nexthops are a conjunctive set of + * disjunctive sets of interface IDs. That is, at the first conjunctive + * level, we have: + * A_1 and A_2 and A_3 and ... and A_m + * + * Each set A_i is made up of a disjunctive set: + * B_(i,1) or B_(i,2) or ... or B_(i,n) + * + * An interest is forwarded to every conjunctive set A_i. If a set A_i has + * more than one B_(i,j), we pick a B_(i,j) using a weighted round robin, but only + * one B_(i,j) is used. + * + * The final set of egress interfaces is the union of B_(i,j) over all i. + * + * + * THIS STRATEGY IS NOT IMPLEMENTED + */ + +#ifndef Metis_strategy_CNF_h +#define Metis_strategy_CNF_h + +#include +#endif // Metis_strategy_CNF_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.c b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.c new file mode 100644 index 00000000..145c9b2a --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.c @@ -0,0 +1,291 @@ +/* + * 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 +#include +#include +#include +#include + +#include + +#include +#include +#include +#include + +#include +#include + + + +static void _strategyLoadBalancer_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt); +static void _strategyLoadBalancer_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId); +static MetisNumberSet *_strategyLoadBalancer_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage); +static MetisNumberSet *_strategyLoadBalancer_ReturnNexthops(MetisStrategyImpl *strategy); +static unsigned _strategyLoadBalancer_CountNexthops(MetisStrategyImpl *strategy); +static void _strategyLoadBalancer_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyLoadBalancer_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyLoadBalancer_ImplDestroy(MetisStrategyImpl **strategyPtr); +static const char *_strategyLoadBalancer_GetStrategy(MetisStrategyImpl *strategy); + +static MetisStrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyLoadBalancer_ReceiveObject, + .onTimeout = &_strategyLoadBalancer_OnTimeout, + .lookupNexthop = &_strategyLoadBalancer_LookupNexthop, + .returnNexthops = &_strategyLoadBalancer_ReturnNexthops, + .countNexthops = &_strategyLoadBalancer_CountNexthops, + .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 { + double weights_sum; + //hash map from connectionId to StrategyNexthopState + PARCHashMap *strategy_state; + MetisNumberSet *nexthops; +}; + +MetisStrategyImpl * +strategyLoadBalancer_Create() +{ + StrategyLoadBalancer *strategy = parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancer)); + assertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyLoadBalancer)); + + strategy->weights_sum = 0.0; + 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; + + return impl; +} + +// ======================================================= +// Dispatch API + + +static const char* +_strategyLoadBalancer_GetStrategy(MetisStrategyImpl *strategy) +{ + return FWD_STRATEGY_LOADBALANCER; +} + +static void +_update_Stats(StrategyLoadBalancer *strategy, StrategyNexthopState *state, bool inc) +{ + const double ALPHA = 0.9; + double w = strategyNexthopState_GetWeight(state); + strategy->weights_sum -= w; + w = strategyNexthopState_UpdateState(state, inc, ALPHA); + strategy->weights_sum += w; +} + +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; +} + + +static void +_strategyLoadBalancer_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt) +{ + _strategyLoadBalancer_OnTimeout(strategy, egressId); +} + +static void +_strategyLoadBalancer_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId) +{ + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) strategy->context; + + for (unsigned i = 0; i < metisNumberSet_Length(egressId); i++) { + unsigned outId = metisNumberSet_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); + } +} + + +//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 * +_strategyLoadBalancer_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage) +{ + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) 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 StrategyNexthopState *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, (StrategyNexthopState *) state, true); + + parcUnsigned_Release(&in); + parcUnsigned_Release(&out); + + metisNumberSet_Add(outList, out_connection); + return outList; +} + +static MetisNumberSet * +_strategyLoadBalancer_ReturnNexthops(MetisStrategyImpl *strategy) +{ + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) strategy->context; + return lb->nexthops; +} + +unsigned +_strategyLoadBalancer_CountNexthops(MetisStrategyImpl *strategy) +{ + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) strategy->context; + return metisNumberSet_Length(lb->nexthops); +} + +static void +_strategyLoadBalancer_resetState(MetisStrategyImpl *strategy) +{ + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) strategy->context; + lb->weights_sum = 0.0; + 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); + lb->weights_sum += strategyNexthopState_GetWeight(elem); + } + + parcIterator_Release(&it); +} + +static void +_strategyLoadBalancer_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! + + + StrategyNexthopState *state = strategyNexthopState_Create(); + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) strategy->context; + + if (!parcHashMap_Contains(lb->strategy_state, cid)) { + parcHashMap_Put(lb->strategy_state, cid, state); + metisNumberSet_Add(lb->nexthops, connectionId); + _strategyLoadBalancer_resetState(strategy); + } +} + +static void +_strategyLoadBalancer_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ + unsigned connectionId = cpiRouteEntry_GetInterfaceIndex(route); + StrategyLoadBalancer *lb = (StrategyLoadBalancer *) 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); + _strategyLoadBalancer_resetState(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void +_strategyLoadBalancer_ImplDestroy(MetisStrategyImpl **strategyPtr) +{ + assertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + assertNotNull(*strategyPtr, "Parameter must dereference to non-null pointer"); + + MetisStrategyImpl *impl = *strategyPtr; + StrategyLoadBalancer *strategy = (StrategyLoadBalancer *) impl->context; + + parcHashMap_Release(&(strategy->strategy_state)); + metisNumberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **) &strategy); + parcMemory_Deallocate((void **) &impl); + *strategyPtr = NULL; +} diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.h b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.h new file mode 100644 index 00000000..cb73d4a9 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancer.h @@ -0,0 +1,27 @@ +/* + * 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. + */ + + +/** + * Forward on the less loaded path + */ + +#ifndef Metis_strategy_LoadBalancer_h +#define Metis_strategy_LoadBalancer_h + +#include + +MetisStrategyImpl *strategyLoadBalancer_Create(); +#endif // Metis_strategy_LoadBalancer_h 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 +#include +#include +#include +#include +#include + +#include + +#include +#include +#include +#include + +#include +#include + +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; +} diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.h b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.h new file mode 100644 index 00000000..434855d7 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_LoadBalancerWithPD.h @@ -0,0 +1,30 @@ +/* + * 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. + */ + + + +/** + * Forward on the less loaded path taking into account the propagation delay of the first hop + */ + +#ifndef Metis_strategy_LoadBalancerWithPD_h +#define Metis_strategy_LoadBalancerWithPD_h + +#include +#include + +MetisStrategyImpl *strategyLoadBalancerWithPD_Create(); +void strategyLoadBalancerWithPD_SetConnectionTable(MetisStrategyImpl *strategy, MetisConnectionTable *connTable); +#endif // Metis_strategy_LoadBalancerWithPD_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.c b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.c new file mode 100644 index 00000000..839ece06 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.c @@ -0,0 +1,237 @@ +/* + * 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 +#include + +#include +#include +#include + +#include + +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, + .toJSON = (PARCObjectToJSON *) strategyNexthopState_ToJSON, + .display = (PARCObjectDisplay *) strategyNexthopState_Display); + +void +strategyNexthopState_AssertValid(const StrategyNexthopState *instance) +{ + assertTrue(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; +} + +PARCJSON * +strategyNexthopState_ToJSON(const StrategyNexthopState *x) +{ + PARCJSON *result = parcJSON_Create(); + + return result; +} + +char * +strategyNexthopState_ToString(const StrategyNexthopState *x) +{ + //this is not implemented + trapNotImplemented("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)); + if (x->avg_pi == 0.0) { + x->avg_pi = 0.1; + } + x->weight = 1 / x->avg_pi; + + return x->weight; +} + diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.h b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.h new file mode 100644 index 00000000..4a3c5de5 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopState.h @@ -0,0 +1,91 @@ +/* + * 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. + */ + +#ifndef Metis_strategy_nexthopstate_h +#define Metis_strategy_nexthopstate_h + +#include +#include +#include + +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); + +/** + */ +PARCJSON *strategyNexthopState_ToJSON(const StrategyNexthopState *instance); + +/** + */ +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/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.c b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.c new file mode 100644 index 00000000..e93c5b6b --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.c @@ -0,0 +1,276 @@ +/* + * 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 +#include +#include +#include + +#include +#include +#include + +#include + +struct strategy_nexthop_state_with_pd { + unsigned int pi; + unsigned delay; + double weight; + double avg_pi; +}; + +static bool +_strategyNexthopStateWithPD_Destructor(StrategyNexthopStateWithPD **instancePtr) +{ + return true; +} + +parcObject_ImplementAcquire(strategyNexthopStateWithPD, StrategyNexthopStateWithPD); + +parcObject_ImplementRelease(strategyNexthopStateWithPD, StrategyNexthopStateWithPD); + +parcObject_Override(StrategyNexthopStateWithPD, PARCObject, + .destructor = (PARCObjectDestructor *) _strategyNexthopStateWithPD_Destructor, + .copy = (PARCObjectCopy *) strategyNexthopStateWithPD_Copy, + .display = (PARCObjectDisplay *) strategyNexthopStateWithPD_Display, + .toString = (PARCObjectToString *) strategyNexthopStateWithPD_ToString, + .equals = (PARCObjectEquals *) strategyNexthopStateWithPD_Equals, + .compare = (PARCObjectCompare *) strategyNexthopStateWithPD_Compare, + .hashCode = (PARCObjectHashCode *) strategyNexthopStateWithPD_HashCode, + .toJSON = (PARCObjectToJSON *) strategyNexthopStateWithPD_ToJSON, + .display = (PARCObjectDisplay *) strategyNexthopStateWithPD_Display); + +void +strategyNexthopStateWithPD_AssertValid(const StrategyNexthopStateWithPD *instance) +{ + assertTrue(strategyNexthopStateWithPD_IsValid(instance), + "StrategyNexthopStateWithPD is not valid."); +} + +StrategyNexthopStateWithPD * +strategyNexthopStateWithPD_Create() +{ + StrategyNexthopStateWithPD *result = parcObject_CreateInstance(StrategyNexthopStateWithPD); + if (result != NULL) { + result->pi = 0; + result->avg_pi = 1.0; + result->weight = 1; + result->delay = 0; + } + return result; +} + +void +strategyNexthopStateWithPD_Reset(StrategyNexthopStateWithPD *x) +{ + x->pi = 0; + x->avg_pi = 1.0; + x->weight = 1; + x->delay = 0; +} + +int +strategyNexthopStateWithPD_Compare(const StrategyNexthopStateWithPD *val, const StrategyNexthopStateWithPD *other) +{ + if (val == NULL) { + if (other != NULL) { + return -1; + } + } else if (other == NULL) { + return 1; + } else { + strategyNexthopStateWithPD_OptionalAssertValid(val); + strategyNexthopStateWithPD_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; + } + + if (val->delay < other->delay) { + return -1; + } else if (val->delay > other->delay) { + return 1; + } + } + + return 0; +} + +StrategyNexthopStateWithPD * +strategyNexthopStateWithPD_Copy(const StrategyNexthopStateWithPD *original) +{ + StrategyNexthopStateWithPD *result = strategyNexthopStateWithPD_Create(); + result->pi = original->pi; + result->avg_pi = original->avg_pi; + result->weight = original->weight; + result->delay = original->delay; + + return result; +} + +void +strategyNexthopStateWithPD_Display(const StrategyNexthopStateWithPD *instance, int indentation) +{ + parcDisplayIndented_PrintLine(indentation, "StrategyNexthopStateWithPD@%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 + 1, "%f", instance->delay); + parcDisplayIndented_PrintLine(indentation, "}"); +} + +bool +strategyNexthopStateWithPD_Equals(const StrategyNexthopStateWithPD *x, const StrategyNexthopStateWithPD *y) +{ + bool result = false; + + if (x == y) { + result = true; + } else if (x == NULL || y == NULL) { + result = false; + } else { + strategyNexthopStateWithPD_OptionalAssertValid(x); + strategyNexthopStateWithPD_OptionalAssertValid(y); + + if (strategyNexthopStateWithPD_Compare(x, y) == 0) { + result = true; + } + } + + return result; +} + +PARCHashCode +strategyNexthopStateWithPD_HashCode(const StrategyNexthopStateWithPD *x) +{ + PARCHashCode result = 0; + char str[128]; + sprintf(str, "PI:%d: AVG_PI:%f: W:%f D:%d", x->pi, x->avg_pi, x->weight, x->delay); + result = parcHashCode_Hash((uint8_t *) &str, strlen(str)); + return result; +} + +bool +strategyNexthopStateWithPD_IsValid(const StrategyNexthopStateWithPD *x) +{ + bool result = false; + + if (x != NULL) { + result = true; + } + + return result; +} + +PARCJSON * +strategyNexthopStateWithPD_ToJSON(const StrategyNexthopStateWithPD *x) +{ + PARCJSON *result = parcJSON_Create(); + //TODO! + + return result; +} + +char * +strategyNexthopStateWithPD_ToString(const StrategyNexthopStateWithPD *x) +{ + //this is not implemented + trapNotImplemented("strategyNexthopStateWithPD_ToString is not implemented"); + return NULL; +} + +unsigned +strategyNexthopStateWithPD_GetPI(const StrategyNexthopStateWithPD *x) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + + return x->pi; +} + +double +strategyNexthopStateWithPD_GetAvgPI(const StrategyNexthopStateWithPD *x) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + + return x->avg_pi; +} + +double +strategyNexthopStateWithPD_GetWeight(const StrategyNexthopStateWithPD *x) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + + return x->weight; +} + +unsigned +strategyNexthopStateWithPD_GetDelay(const StrategyNexthopStateWithPD *x) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + + return x->delay; +} + +void +strategyNexthopStateWithPD_SetDelay(StrategyNexthopStateWithPD *x, unsigned delay) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + if (delay != 0) { + x->delay = delay; + } +} + +double +strategyNexthopStateWithPD_UpdateState(StrategyNexthopStateWithPD *x, bool inc, unsigned min_delay, double alpha) +{ + strategyNexthopStateWithPD_OptionalAssertValid(x); + + if (inc) { + x->pi++; + } else { + if (x->pi > 0) { + x->pi--; + } + } + + x->avg_pi = (x->avg_pi * alpha) + (x->pi * (1 - alpha)); + if (x->avg_pi == 0.0) { + x->avg_pi = 0.1; + } + + double factor = 1.0; + if (min_delay != INT_MAX && x->delay != 0) { + factor = ((double) min_delay / (double) x->delay); + } + + x->weight = 1 / (x->avg_pi * factor); + + return x->weight; +} + diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.h b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.h new file mode 100644 index 00000000..ef248f67 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_NexthopStateWithPD.h @@ -0,0 +1,94 @@ +/* + * 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. + */ + +#ifndef Metis_strategy_nexthopstatewithpd_h +#define Metis_strategy_nexthopstatewithpd_h + +#include +#include +#include + +struct strategy_nexthop_state_with_pd; +typedef struct strategy_nexthop_state_with_pd StrategyNexthopStateWithPD; +extern parcObjectDescriptor_Declaration(StrategyNexthopStateWithPD); + +/** + */ +StrategyNexthopStateWithPD *strategyNexthopStateWithPD_Acquire(const StrategyNexthopStateWithPD *instance); + +#ifdef PARCLibrary_DISABLE_VALIDATION +# define strategyNexthopStateWithPD_OptionalAssertValid(_instance_) +#else +# define strategyNexthopStateWithPD_OptionalAssertValid(_instance_) strategyNexthopStateWithPD_AssertValid(_instance_) +#endif + +/** + */ +void strategyNexthopStateWithPD_AssertValid(const StrategyNexthopStateWithPD *instance); + +/** + */ +StrategyNexthopStateWithPD *strategyNexthopStateWithPD_Create(); + +void strategyNexthopStateWithPD_Reset(StrategyNexthopStateWithPD *x); +/** + */ +int strategyNexthopStateWithPD_Compare(const StrategyNexthopStateWithPD *instance, const StrategyNexthopStateWithPD *other); + +/** + */ +StrategyNexthopStateWithPD *strategyNexthopStateWithPD_Copy(const StrategyNexthopStateWithPD *original); + +/** + */ +void strategyNexthopStateWithPD_Display(const StrategyNexthopStateWithPD *instance, int indentation); + +/** + */ +bool strategyNexthopStateWithPD_Equals(const StrategyNexthopStateWithPD *x, const StrategyNexthopStateWithPD *y); + +/** + */ +PARCHashCode strategyNexthopStateWithPD_HashCode(const StrategyNexthopStateWithPD *instance); + +/** + */ +bool strategyNexthopStateWithPD_IsValid(const StrategyNexthopStateWithPD *instance); + +/** + */ +void strategyNexthopStateWithPD_Release(StrategyNexthopStateWithPD **instancePtr); + +/** + */ +PARCJSON *strategyNexthopStateWithPD_ToJSON(const StrategyNexthopStateWithPD *instance); + +/** + */ +char *strategyNexthopStateWithPD_ToString(const StrategyNexthopStateWithPD *instance); + +/** + */ +unsigned strategyNexthopStateWithPD_GetPI(const StrategyNexthopStateWithPD *x); + +double strategyNexthopStateWithPD_GetAvgPI(const StrategyNexthopStateWithPD *x); + +double strategyNexthopStateWithPD_GetWeight(const StrategyNexthopStateWithPD *x); + +unsigned strategyNexthopStateWithPD_GetDelay(const StrategyNexthopStateWithPD *x); +void strategyNexthopStateWithPD_SetDelay(StrategyNexthopStateWithPD *x, unsigned delay); + +double strategyNexthopStateWithPD_UpdateState(StrategyNexthopStateWithPD *x, bool inc, unsigned min_delay, double alpha); +#endif diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.c b/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.c new file mode 100644 index 00000000..a170b9b7 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.c @@ -0,0 +1,191 @@ +/* + * 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 +#include +#include +#include +#include + +#include + +#include +#include + +#include + + +static void _strategyRnd_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt); +static void _strategyRnd_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId); +static MetisNumberSet *_strategyRnd_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage); +static MetisNumberSet *_strategyRnd_ReturnNexthops(MetisStrategyImpl *strategy); +static unsigned _strategyRnd_CountNexthops(MetisStrategyImpl *strategy); +static void _strategyRnd_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyRnd_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyRnd_ImplDestroy(MetisStrategyImpl **strategyPtr); +static const char *_strategyRnd_GetStrategy(MetisStrategyImpl *strategy); + +static MetisStrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyRnd_ReceiveObject, + .onTimeout = &_strategyRnd_OnTimeout, + .lookupNexthop = &_strategyRnd_LookupNexthop, + .returnNexthops = &_strategyRnd_ReturnNexthops, + .countNexthops = &_strategyRnd_CountNexthops, + .addNexthop = &_strategyRnd_AddNexthop, + .removeNexthop = &_strategyRnd_RemoveNexthop, + .destroy = &_strategyRnd_ImplDestroy, + .getStrategy = &_strategyRnd_GetStrategy, +}; + +struct strategy_rnd; +typedef struct strategy_rnd StrategyRnd; + + +struct strategy_rnd { + MetisNumberSet *nexthops; +}; + +MetisStrategyImpl * +strategyRnd_Create() +{ + StrategyRnd *strategy = parcMemory_AllocateAndClear(sizeof(StrategyRnd)); + assertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyRnd)); + + 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; + + return impl; +} + +// ======================================================= +// Dispatch API + +static const char* +_strategyRnd_GetStrategy(MetisStrategyImpl *strategy) +{ + return FWD_STRATEGY_RANDOM; +} + + +static int +_select_Nexthop(StrategyRnd *strategy) +{ + unsigned len = metisNumberSet_Length(strategy->nexthops); + if (len == 0) { + return -1; + } + + int rnd = (rand() % len); + return metisNumberSet_GetItem(strategy->nexthops, rnd); +} + + +static void +_strategyRnd_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt) +{ +} + +static void +_strategyRnd_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId) +{ +} + +//ATTENTION!! This interface force us to create a MetisNumberSet which need to be delited somewhere (maybe in the FIB where we call this function) +//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 * +_strategyRnd_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage) +{ + StrategyRnd *srnd = (StrategyRnd *) strategy->context; + + unsigned in_connection = metisMessage_GetIngressConnectionId(interestMessage); + unsigned nexthopSize = metisNumberSet_Length(srnd->nexthops); + + MetisNumberSet *out = metisNumberSet_Create(); + if ((nexthopSize == 0) || ((nexthopSize == 1) && metisNumberSet_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; + } + + unsigned out_connection; + do { + out_connection = _select_Nexthop(srnd); + } while (out_connection == in_connection); + + if (out_connection == -1) { + return out; + } + + metisNumberSet_Add(out, out_connection); + return out; +} + +static MetisNumberSet * +_strategyRnd_ReturnNexthops(MetisStrategyImpl *strategy) +{ + StrategyRnd *srnd = (StrategyRnd *) strategy->context; + return srnd->nexthops; +} + +unsigned +_strategyRnd_CountNexthops(MetisStrategyImpl *strategy) +{ + StrategyRnd *srnd = (StrategyRnd *) strategy->context; + return metisNumberSet_Length(srnd->nexthops); +} + +static void +_strategyRnd_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! + + StrategyRnd *srnd = (StrategyRnd *) strategy->context; + if (!metisNumberSet_Contains(srnd->nexthops, connectionId)) { + metisNumberSet_Add(srnd->nexthops, connectionId); + } +} + +static void +_strategyRnd_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ + unsigned connectionId = cpiRouteEntry_GetInterfaceIndex(route); + StrategyRnd *srnd = (StrategyRnd *) strategy->context; + + if (metisNumberSet_Contains(srnd->nexthops, connectionId)) { + metisNumberSet_Remove(srnd->nexthops, connectionId); + } +} + +static void +_strategyRnd_ImplDestroy(MetisStrategyImpl **strategyPtr) +{ + assertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + assertNotNull(*strategyPtr, "Parameter must dereference to non-null pointer"); + + MetisStrategyImpl *impl = *strategyPtr; + StrategyRnd *strategy = (StrategyRnd *) impl->context; + + metisNumberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **) &strategy); + parcMemory_Deallocate((void **) &impl); + *strategyPtr = NULL; +} diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.h b/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.h new file mode 100644 index 00000000..b3d60da5 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_Rnd.h @@ -0,0 +1,28 @@ +/* + * 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. + */ + + + +/** + * Forward randomly + */ + +#ifndef Metis_strategy_Rnd_h +#define Metis_strategy_Rnd_h + +#include + +MetisStrategyImpl * strategyRnd_Create(); +#endif // Metis_strategy_Rnd_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.c b/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.c new file mode 100644 index 00000000..d3fd5dab --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.c @@ -0,0 +1,226 @@ +/* + * 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 +#include +#include +#include +#include + +#include + +#include +#include +#include +#include + + +static void _strategyRndSegment_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt); +static void _strategyRndSegment_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId); +static MetisNumberSet *_strategyRndSegment_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage); +static MetisNumberSet *_strategyRndSegment_ReturnNexthops(MetisStrategyImpl *strategy); +static unsigned _strategyRndSegment_CountNexthops(MetisStrategyImpl *strategy); +static void _strategyRndSegment_AddNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyRndSegment_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route); +static void _strategyRndSegment_ImplDestroy(MetisStrategyImpl **strategyPtr); +static const char *_strategyRndSegment_GetStrategy(MetisStrategyImpl *strategy); + +static MetisStrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyRndSegment_ReceiveObject, + .onTimeout = &_strategyRndSegment_OnTimeout, + .lookupNexthop = &_strategyRndSegment_LookupNexthop, + .returnNexthops = &_strategyRndSegment_ReturnNexthops, + .countNexthops = &_strategyRndSegment_CountNexthops, + .addNexthop = &_strategyRndSegment_AddNexthop, + .removeNexthop = &_strategyRndSegment_RemoveNexthop, + .destroy = &_strategyRndSegment_ImplDestroy, + .getStrategy = &_strategyRndSegment_GetStrategy, +}; + +struct strategy_rnd_segment; +typedef struct strategy_rnd_segment StrategyRndSegment; + + +struct strategy_rnd_segment { + MetisNumberSet *nexthops; + MetisTlvName *segmentName; + int last_used_face; +}; + +MetisStrategyImpl * +strategyRndSegment_Create() +{ + StrategyRndSegment *strategy = parcMemory_AllocateAndClear(sizeof(StrategyRndSegment)); + assertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyRndSegment)); + + strategy->nexthops = metisNumberSet_Create(); + strategy->segmentName = NULL; + strategy->last_used_face = 0; + 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; + + return impl; +} + +// ======================================================= +// Dispatch API + + +static const char* +_strategyRndSegment_GetStrategy(MetisStrategyImpl *strategy) +{ + return FWD_STRATEGY_RANDOM_PER_DASH_SEGMENT; +} + + +static int +_select_Nexthop(StrategyRndSegment *strategy) +{ + unsigned len = metisNumberSet_Length(strategy->nexthops); + if (len == 0) { + return -1; + } + + int rnd = (rand() % len); + return metisNumberSet_GetItem(strategy->nexthops, rnd); +} + + +static void +_strategyRndSegment_ReceiveObject(MetisStrategyImpl *strategy, const MetisNumberSet *egressId, const MetisMessage *objectMessage, MetisTicks rtt) +{ +} + +static void +_strategyRndSegment_OnTimeout(MetisStrategyImpl *strategy, const MetisNumberSet *egressId) +{ +} + +//ATTENTION!! This interface force us to create a MetisNumberSet which need to be delited somewhere (maybe in the FIB where we call this function) +//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 * +_strategyRndSegment_LookupNexthop(MetisStrategyImpl *strategy, const MetisMessage *interestMessage) +{ + StrategyRndSegment *srnd = (StrategyRndSegment *) strategy->context; + + + unsigned in_connection = metisMessage_GetIngressConnectionId(interestMessage); + unsigned nexthopSize = metisNumberSet_Length(srnd->nexthops); + + MetisNumberSet *out = metisNumberSet_Create(); + if ((nexthopSize == 0) || ((nexthopSize == 1) && metisNumberSet_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; + } + + if (metisMessage_HasName(interestMessage)) { + MetisTlvName *interestName = metisMessage_GetName(interestMessage); + size_t sc = metisTlvName_SegmentCount(interestName); + interestName = metisTlvName_Slice(interestName, (sc - 1)); + + if (srnd->segmentName == NULL) { + srnd->segmentName = interestName; + } else if (!metisTlvName_Equals(srnd->segmentName, interestName)) { + metisTlvName_Release(&srnd->segmentName); + srnd->segmentName = interestName; + } else { + //here we need to check if the output face still exists or if someone erase it + if (metisNumberSet_Contains(srnd->nexthops, srnd->last_used_face)) { + // face exists, so keep using it! + metisTlvName_Release(&interestName); + metisNumberSet_Add(out, srnd->last_used_face); + return out; + } else { + //the face does not exists anymore, try to find a new face but keep the name + //of the dash segment + metisTlvName_Release(&interestName); + } + } + } + + int out_connection; + do { + out_connection = _select_Nexthop(srnd); + } while (out_connection == in_connection); + + if (out_connection == -1) { + return out; + } + + srnd->last_used_face = out_connection; + metisNumberSet_Add(out, out_connection); + return out; +} + +static MetisNumberSet * +_strategyRndSegment_ReturnNexthops(MetisStrategyImpl *strategy) +{ + StrategyRndSegment *srnd = (StrategyRndSegment *) strategy->context; + return srnd->nexthops; +} + +unsigned +_strategyRndSegment_CountNexthops(MetisStrategyImpl *strategy) +{ + StrategyRndSegment *srnd = (StrategyRndSegment *) strategy->context; + return metisNumberSet_Length(srnd->nexthops); +} + +static void +_strategyRndSegment_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! + + StrategyRndSegment *srnd = (StrategyRndSegment *) strategy->context; + if (!metisNumberSet_Contains(srnd->nexthops, connectionId)) { + metisNumberSet_Add(srnd->nexthops, connectionId); + } +} + +static void +_strategyRndSegment_RemoveNexthop(MetisStrategyImpl *strategy, CPIRouteEntry *route) +{ + unsigned connectionId = cpiRouteEntry_GetInterfaceIndex(route); + StrategyRndSegment *srnd = (StrategyRndSegment *) strategy->context; + + if (metisNumberSet_Contains(srnd->nexthops, connectionId)) { + metisNumberSet_Remove(srnd->nexthops, connectionId); + } +} + +static void +_strategyRndSegment_ImplDestroy(MetisStrategyImpl **strategyPtr) +{ + assertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + assertNotNull(*strategyPtr, "Parameter must dereference to non-null pointer"); + + MetisStrategyImpl *impl = *strategyPtr; + StrategyRndSegment *strategy = (StrategyRndSegment *) impl->context; + + metisNumberSet_Release(&(strategy->nexthops)); + if (strategy->segmentName != NULL) { + metisTlvName_Release(&strategy->segmentName); + } + + parcMemory_Deallocate((void **) &strategy); + parcMemory_Deallocate((void **) &impl); + *strategyPtr = NULL; +} diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.h b/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.h new file mode 100644 index 00000000..8feed482 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_RndSegment.h @@ -0,0 +1,26 @@ +/* + * 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. + */ + +/** + * Forward randomly, selects a path every time the client ask for a new dash segment + */ + +#ifndef Metis_strategy_Rnd_Segment_h +#define Metis_strategy_Rnd_Segment_h + +#include + +MetisStrategyImpl * strategyRndSegment_Create(); +#endif // Metis_strategy_Rnd_Segment_h diff --git a/metis/ccnx/forwarder/metis/strategies/strategy_WeightedRoundRobin.h b/metis/ccnx/forwarder/metis/strategies/strategy_WeightedRoundRobin.h new file mode 100644 index 00000000..ae44768e --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/strategy_WeightedRoundRobin.h @@ -0,0 +1,28 @@ +/* + * 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. + */ + + +/** + * Weighted round robin on multiple interfaces based on their performance + * THIS STRATEGY IS NOT IMPLEMENTED + */ + +#ifndef Metis_strategy_WeightedRoundRobin_h +#define Metis_strategy_WeightedRoundRobin_h + +#include + +MetisStrategyImpl *metisStrategyWrr_Create(); +#endif // Metis_strategy_WeightedRoundRobin_h diff --git a/metis/ccnx/forwarder/metis/strategies/test/CMakeLists.txt b/metis/ccnx/forwarder/metis/strategies/test/CMakeLists.txt new file mode 100644 index 00000000..5e4f6928 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/test/CMakeLists.txt @@ -0,0 +1,13 @@ +# Enable gcov output for the tests +add_definitions(--coverage) +set(CMAKE_EXE_LINKER_FLAGS ${CMAKE_EXE_LINKER_FLAGS} " --coverage") + +set(TestsExpectedToPass + test_strategy_All +) + + +foreach(test ${TestsExpectedToPass}) + AddTest(${test}) +endforeach() + diff --git a/metis/ccnx/forwarder/metis/strategies/test/test_strategy_All.c b/metis/ccnx/forwarder/metis/strategies/test/test_strategy_All.c new file mode 100644 index 00000000..ef3118a0 --- /dev/null +++ b/metis/ccnx/forwarder/metis/strategies/test/test_strategy_All.c @@ -0,0 +1,132 @@ +/* + * 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 the file(s) containing the functions to be tested. +// This permits internal static functions to be visible to this Test Framework. +#include "../strategy_All.c" +#include + +LONGBOW_TEST_RUNNER(strategy_All) +{ + // The following Test Fixtures will run their corresponding Test Cases. + // Test Fixtures are run in the order specified, but all tests should be idempotent. + // Never rely on the execution order of tests or share state between them. + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Local); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(strategy_All) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(strategy_All) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, strategyAll_Create); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_CASE(Global, strategyAll_Create) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_FIXTURE(Local) +{ + LONGBOW_RUN_TEST_CASE(Local, __llvm_gcov_flush); + LONGBOW_RUN_TEST_CASE(Local, __llvm_gcov_init); + LONGBOW_RUN_TEST_CASE(Local, __llvm_gcov_writeout); + LONGBOW_RUN_TEST_CASE(Local, strategyAll_AddNexthop); + LONGBOW_RUN_TEST_CASE(Local, strategyAll_ImplDestroy); + LONGBOW_RUN_TEST_CASE(Local, strategyAll_LookupNexthop); + LONGBOW_RUN_TEST_CASE(Local, strategyAll_ReceiveObject); + LONGBOW_RUN_TEST_CASE(Local, strategyAll_RemoveNexthop); +} + +LONGBOW_TEST_FIXTURE_SETUP(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_CASE(Local, __llvm_gcov_flush) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, __llvm_gcov_init) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, __llvm_gcov_writeout) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, strategyAll_AddNexthop) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, strategyAll_ImplDestroy) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, strategyAll_LookupNexthop) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, strategyAll_ReceiveObject) +{ + testUnimplemented("This test is unimplemented"); +} + +LONGBOW_TEST_CASE(Local, strategyAll_RemoveNexthop) +{ + testUnimplemented("This test is unimplemented"); +} + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(strategy_All); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} -- cgit 1.2.3-korg