diff options
author | 2019-01-17 13:47:57 +0100 | |
---|---|---|
committer | 2019-01-17 16:32:51 +0100 | |
commit | bac3da61644515f05663789b122554dc77549286 (patch) | |
tree | 898210bc8e70371d77de7d446a26c5dd4fd1165a /hicn-light/src/strategies | |
parent | d5165246787301d0f13b646fda5e8a8567aef5ac (diff) |
This is the first commit of the hicn projectv19.01
Change-Id: I6f2544ad9b9f8891c88cc4bcce3cf19bd3cc863f
Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>
Diffstat (limited to 'hicn-light/src/strategies')
-rwxr-xr-x | hicn-light/src/strategies/CMakeLists.txt | 36 | ||||
-rwxr-xr-x | hicn-light/src/strategies/loadBalancer.c | 278 | ||||
-rwxr-xr-x | hicn-light/src/strategies/loadBalancer.h | 26 | ||||
-rwxr-xr-x | hicn-light/src/strategies/loadBalancerWithPD.c | 368 | ||||
-rwxr-xr-x | hicn-light/src/strategies/loadBalancerWithPD.h | 30 | ||||
-rwxr-xr-x | hicn-light/src/strategies/nexthopState.c | 206 | ||||
-rwxr-xr-x | hicn-light/src/strategies/nexthopState.h | 94 | ||||
-rwxr-xr-x | hicn-light/src/strategies/nexthopStateWithPD.c | 254 | ||||
-rwxr-xr-x | hicn-light/src/strategies/nexthopStateWithPD.h | 106 | ||||
-rwxr-xr-x | hicn-light/src/strategies/rnd.c | 175 | ||||
-rwxr-xr-x | hicn-light/src/strategies/rnd.h | 26 | ||||
-rwxr-xr-x | hicn-light/src/strategies/rndSegment.c | 207 | ||||
-rwxr-xr-x | hicn-light/src/strategies/rndSegment.h | 27 | ||||
-rwxr-xr-x | hicn-light/src/strategies/strategyImpl.h | 66 |
14 files changed, 1899 insertions, 0 deletions
diff --git a/hicn-light/src/strategies/CMakeLists.txt b/hicn-light/src/strategies/CMakeLists.txt new file mode 100755 index 000000000..7f0730b2f --- /dev/null +++ b/hicn-light/src/strategies/CMakeLists.txt @@ -0,0 +1,36 @@ +# Copyright (c) 2017-2019 Cisco and/or its affiliates. +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +cmake_minimum_required(VERSION 3.5 FATAL_ERROR) + +list(APPEND HEADER_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/strategyImpl.h + ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancer.h + ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancerWithPD.h + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.h + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateWithPD.h + ${CMAKE_CURRENT_SOURCE_DIR}/rnd.h + ${CMAKE_CURRENT_SOURCE_DIR}/rndSegment.h +) + +list(APPEND SOURCE_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancer.c + ${CMAKE_CURRENT_SOURCE_DIR}/loadBalancerWithPD.c + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.c + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateWithPD.c + ${CMAKE_CURRENT_SOURCE_DIR}/rnd.c + ${CMAKE_CURRENT_SOURCE_DIR}/rndSegment.c +) + +set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) +set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE) diff --git a/hicn-light/src/strategies/loadBalancer.c b/hicn-light/src/strategies/loadBalancer.c new file mode 100755 index 000000000..14e907770 --- /dev/null +++ b/hicn-light/src/strategies/loadBalancer.c @@ -0,0 +1,278 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <parc/assert/parc_Assert.h> + +#include <parc/algol/parc_HashMap.h> +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_Unsigned.h> + +#include <src/strategies/loadBalancer.h> +#include <src/strategies/nexthopState.h> + +static void _strategyLoadBalancer_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks rtt); +static void _strategyLoadBalancer_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId); +static NumberSet *_strategyLoadBalancer_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage); +static NumberSet *_strategyLoadBalancer_ReturnNexthops(StrategyImpl *strategy); +static unsigned _strategyLoadBalancer_CountNexthops(StrategyImpl *strategy); +static void _strategyLoadBalancer_AddNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLoadBalancer_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLoadBalancer_ImplDestroy(StrategyImpl **strategyPtr); +static strategy_type _strategyLoadBalancer_GetStrategy(StrategyImpl *strategy); + +static StrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyLoadBalancer_ReceiveObject, + .onTimeout = &_strategyLoadBalancer_OnTimeout, + .lookupNexthop = &_strategyLoadBalancer_LookupNexthop, + .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; + NumberSet *nexthops; +}; + +StrategyImpl *strategyLoadBalancer_Create() { + StrategyLoadBalancer *strategy = + parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancer)); + parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyLoadBalancer)); + + strategy->weights_sum = 0.0; + strategy->strategy_state = parcHashMap_Create(); + strategy->nexthops = numberSet_Create(); + srand(time(NULL)); + + StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); + parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyImpl)); + memcpy(impl, &_template, sizeof(StrategyImpl)); + impl->context = strategy; + + return impl; +} + +// ======================================================= +// Dispatch API + +strategy_type _strategyLoadBalancer_GetStrategy(StrategyImpl *strategy) { + return SET_STRATEGY_LOADBALANCER; +} + +static void _update_Stats(StrategyLoadBalancer *strategy, + StrategyNexthopState *state, bool inc) { + const double ALPHA = 0.9; + 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(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks rtt) { + _strategyLoadBalancer_OnTimeout(strategy, egressId); +} + +static void _strategyLoadBalancer_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId) { + StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; + + for (unsigned i = 0; i < numberSet_Length(egressId); i++) { + unsigned outId = numberSet_GetItem(egressId, i); + PARCUnsigned *cid = parcUnsigned_Create(outId); + + const StrategyNexthopState *state = + parcHashMap_Get(lb->strategy_state, cid); + if (state != NULL) { + _update_Stats(lb, (StrategyNexthopState *)state, false); + } else { + // this may happen if we remove a face/route while downloading a file + // we should ignore this timeout + } + parcUnsigned_Release(&cid); + } +} + +static NumberSet *_strategyLoadBalancer_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage) { + StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; + + unsigned in_connection = message_GetIngressConnectionId(interestMessage); + PARCUnsigned *in = parcUnsigned_Create(in_connection); + + unsigned mapSize = parcHashMap_Size(lb->strategy_state); + NumberSet *outList = numberSet_Create(); + + if ((mapSize == 0) || + ((mapSize == 1) && parcHashMap_Contains(lb->strategy_state, in))) { + // there are no output faces or the input face is also the only output face. + // return null to avoid loops + parcUnsigned_Release(&in); + return outList; + } + + unsigned out_connection; + do { + out_connection = _select_Nexthop(lb); + } while (out_connection == in_connection); + + PARCUnsigned *out = parcUnsigned_Create(out_connection); + + const StrategyNexthopState *state = parcHashMap_Get(lb->strategy_state, out); + if (state == NULL) { + // this is an error and should not happen! + parcTrapNotImplemented( + "Try to send an interest on a face that does not exists"); + } + + _update_Stats(lb, (StrategyNexthopState *)state, true); + + parcUnsigned_Release(&in); + parcUnsigned_Release(&out); + + numberSet_Add(outList, out_connection); + return outList; +} + +static NumberSet *_strategyLoadBalancer_ReturnNexthops(StrategyImpl *strategy) { + StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; + return lb->nexthops; +} + +unsigned _strategyLoadBalancer_CountNexthops(StrategyImpl *strategy) { + StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; + return numberSet_Length(lb->nexthops); +} + +static void _strategyLoadBalancer_resetState(StrategyImpl *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(StrategyImpl *strategy, + unsigned connectionId) { + 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); + numberSet_Add(lb->nexthops, connectionId); + _strategyLoadBalancer_resetState(strategy); + } +} + +static void _strategyLoadBalancer_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyLoadBalancer *lb = (StrategyLoadBalancer *)strategy->context; + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + if (parcHashMap_Contains(lb->strategy_state, cid)) { + parcHashMap_Remove(lb->strategy_state, cid); + numberSet_Remove(lb->nexthops, connectionId); + _strategyLoadBalancer_resetState(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void _strategyLoadBalancer_ImplDestroy(StrategyImpl **strategyPtr) { + parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*strategyPtr, + "Parameter must dereference to non-null pointer"); + + StrategyImpl *impl = *strategyPtr; + StrategyLoadBalancer *strategy = (StrategyLoadBalancer *)impl->context; + + parcHashMap_Release(&(strategy->strategy_state)); + numberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **)&strategy); + parcMemory_Deallocate((void **)&impl); + *strategyPtr = NULL; +} diff --git a/hicn-light/src/strategies/loadBalancer.h b/hicn-light/src/strategies/loadBalancer.h new file mode 100755 index 000000000..1178c30fe --- /dev/null +++ b/hicn-light/src/strategies/loadBalancer.h @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Forward on the less loaded path + */ + +#ifndef loadBalancer_h +#define loadBalancer_h + +#include <src/strategies/strategyImpl.h> + +StrategyImpl *strategyLoadBalancer_Create(); +#endif // loadBalancer_h diff --git a/hicn-light/src/strategies/loadBalancerWithPD.c b/hicn-light/src/strategies/loadBalancerWithPD.c new file mode 100755 index 000000000..1aad8fd89 --- /dev/null +++ b/hicn-light/src/strategies/loadBalancerWithPD.c @@ -0,0 +1,368 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <limits.h> +#include <src/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <parc/assert/parc_Assert.h> + +#include <parc/algol/parc_HashMap.h> +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_Unsigned.h> + +#include <src/strategies/loadBalancerWithPD.h> +#include <src/strategies/nexthopStateWithPD.h> + +const unsigned PROBE_FREQUENCY = 1024; + +static void _strategyLoadBalancerWithPD_ReceiveObject( + StrategyImpl *strategy, const NumberSet *egressId, + const Message *objectMessage, Ticks rtt); +static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId); +static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage); +static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( + StrategyImpl *strategy); +static unsigned _strategyLoadBalancerWithPD_CountNexthops( + StrategyImpl *strategy); +static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLoadBalancerWithPD_ImplDestroy(StrategyImpl **strategyPtr); +static strategy_type _strategyLoadBalancerWithPD_GetStrategy( + StrategyImpl *strategy); + +static StrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyLoadBalancerWithPD_ReceiveObject, + .onTimeout = &_strategyLoadBalancerWithPD_OnTimeout, + .lookupNexthop = &_strategyLoadBalancerWithPD_LookupNexthop, + .returnNexthops = &_strategyLoadBalancerWithPD_ReturnNexthops, + .countNexthops = &_strategyLoadBalancerWithPD_CountNexthops, + .addNexthop = &_strategyLoadBalancerWithPD_AddNexthop, + .removeNexthop = &_strategyLoadBalancerWithPD_RemoveNexthop, + .destroy = &_strategyLoadBalancerWithPD_ImplDestroy, + .getStrategy = &_strategyLoadBalancerWithPD_GetStrategy, +}; + +struct strategy_load_balancer_with_pd; +typedef struct strategy_load_balancer_with_pd StrategyLoadBalancerWithPD; + +struct strategy_load_balancer_with_pd { + double weights_sum; + unsigned min_delay; + // hash map from connectionId to StrategyNexthopState + PARCHashMap *strategy_state; + NumberSet *nexthops; + ConnectionTable *connTable; + bool toInit; + unsigned int fwdPackets; +}; + +StrategyImpl *strategyLoadBalancerWithPD_Create() { + StrategyLoadBalancerWithPD *strategy = + parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancerWithPD)); + parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyLoadBalancerWithPD)); + + strategy->weights_sum = 0.0; + strategy->min_delay = INT_MAX; + strategy->strategy_state = parcHashMap_Create(); + strategy->nexthops = numberSet_Create(); + srand(time(NULL)); + + StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); + parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyImpl)); + memcpy(impl, &_template, sizeof(StrategyImpl)); + impl->context = strategy; + strategy->connTable = NULL; + strategy->fwdPackets = 0; + strategy->toInit = true; + + return impl; +} + +void strategyLoadBalancerWithPD_SetConnectionTable(StrategyImpl *strategy, + ConnectionTable *connTable) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + lb->connTable = connTable; +} + +// ======================================================= +// Dispatch API + +strategy_type _strategyLoadBalancerWithPD_GetStrategy(StrategyImpl *strategy) { + return SET_STRATEGY_LOADBALANCER_WITH_DELAY; +} + +static void _update_Stats(StrategyLoadBalancerWithPD *strategy, + StrategyNexthopStateWithPD *state, bool inc, + Ticks rtt) { + const double ALPHA = 0.9; + double w = strategyNexthopStateWithPD_GetWeight(state); + strategy->weights_sum -= w; + w = strategyNexthopStateWithPD_UpdateState(state, inc, strategy->min_delay, + ALPHA); + strategy->weights_sum += w; +} + +static void _sendProbes(StrategyLoadBalancerWithPD *strategy) { + unsigned size = numberSet_Length(strategy->nexthops); + for (unsigned i = 0; i < size; i++) { + unsigned nhop = numberSet_GetItem(strategy->nexthops, i); + Connection *conn = + (Connection *)connectionTable_FindById(strategy->connTable, nhop); + if (conn != NULL) { + connection_Probe(conn); + unsigned delay = connection_GetDelay(conn); + PARCUnsigned *cid = parcUnsigned_Create(nhop); + StrategyNexthopStateWithPD *elem = + (StrategyNexthopStateWithPD *)parcHashMap_Get( + strategy->strategy_state, cid); + strategyNexthopStateWithPD_SetDelay(elem, delay); + if (delay < strategy->min_delay && delay != 0) { + strategy->min_delay = delay; + } + + parcUnsigned_Release(&cid); + } + } +} + +static unsigned _select_Nexthop(StrategyLoadBalancerWithPD *strategy) { + strategy->fwdPackets++; + if (strategy->toInit || strategy->fwdPackets == PROBE_FREQUENCY) { + strategy->toInit = false; + strategy->fwdPackets = 0; + _sendProbes(strategy); + } + double rnd = (double)rand() / (double)RAND_MAX; + double start_range = 0.0; + + PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); + + unsigned nexthop = 100000; + while (parcIterator_HasNext(it)) { + PARCUnsigned *cid = parcIterator_Next(it); + const StrategyNexthopStateWithPD *elem = + parcHashMap_Get(strategy->strategy_state, cid); + + double w = strategyNexthopStateWithPD_GetWeight(elem); + + // printf("next = %u .. pi %u avgpi %f w %f avgrtt + // %f\n",parcUnsigned_GetUnsigned(cid), + // strategyNexthopStateWithPD_GetPI(elem), + // strategyNexthopStateWithPD_GetWeight(elem), + // strategyNexthopStateWithPD_GetWeight(elem), + // strategyNexthopStateWithPD_GetAvgRTT(elem)); + + double prob = w / strategy->weights_sum; + if ((rnd >= start_range) && (rnd < (start_range + prob))) { + nexthop = parcUnsigned_GetUnsigned(cid); + break; + } else { + start_range += prob; + } + } + + parcIterator_Release(&it); + + // if no face is selected by the algorithm (for example because of a wrong + // round in the weights) we may always select the last face here. Double check + // this! + return nexthop; +} + +static void _strategyLoadBalancerWithPD_ReceiveObject( + StrategyImpl *strategy, const NumberSet *egressId, + const Message *objectMessage, Ticks rtt) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + + for (unsigned i = 0; i < numberSet_Length(egressId); i++) { + unsigned outId = numberSet_GetItem(egressId, i); + PARCUnsigned *cid = parcUnsigned_Create(outId); + + const StrategyNexthopStateWithPD *state = + parcHashMap_Get(lb->strategy_state, cid); + if (state != NULL) { + _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); + } else { + // this may happen if we remove a face/route while downloading a file + // we should ignore this timeout + } + parcUnsigned_Release(&cid); + } +} + +static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + + for (unsigned i = 0; i < numberSet_Length(egressId); i++) { + unsigned outId = numberSet_GetItem(egressId, i); + PARCUnsigned *cid = parcUnsigned_Create(outId); + + const StrategyNexthopStateWithPD *state = + parcHashMap_Get(lb->strategy_state, cid); + if (state != NULL) { + _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); + } else { + // this may happen if we remove a face/route while downloading a file + // we should ignore this timeout + } + parcUnsigned_Release(&cid); + } +} + +// ATTENTION!! This interface force us to create a NumberSet which need to be +// delited somewhere The specification in the interface requires that this +// function never returns NULL. in case we have no output face we need to return +// an empty NumberSet +static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + + unsigned in_connection = message_GetIngressConnectionId(interestMessage); + PARCUnsigned *in = parcUnsigned_Create(in_connection); + + unsigned mapSize = parcHashMap_Size(lb->strategy_state); + NumberSet *outList = numberSet_Create(); + + if ((mapSize == 0) || + ((mapSize == 1) && parcHashMap_Contains(lb->strategy_state, in))) { + // there are no output faces or the input face is also the only output face. + // return null to avoid loops + parcUnsigned_Release(&in); + return outList; + } + + unsigned out_connection; + do { + out_connection = _select_Nexthop(lb); + } while (out_connection == in_connection); + + PARCUnsigned *out = parcUnsigned_Create(out_connection); + + const StrategyNexthopStateWithPD *state = + parcHashMap_Get(lb->strategy_state, out); + if (state == NULL) { + // this is an error and should not happen! + parcTrapNotImplemented( + "Try to send an interest on a face that does not exists"); + } + + _update_Stats(lb, (StrategyNexthopStateWithPD *)state, true, 0); + + parcUnsigned_Release(&in); + parcUnsigned_Release(&out); + + numberSet_Add(outList, out_connection); + return outList; +} + +static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( + StrategyImpl *strategy) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + return lb->nexthops; +} + +unsigned _strategyLoadBalancerWithPD_CountNexthops(StrategyImpl *strategy) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + return numberSet_Length(lb->nexthops); +} + +static void _strategyLoadBalancerWithPD_resetState(StrategyImpl *strategy) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + lb->weights_sum = 0.0; + lb->min_delay = INT_MAX; + lb->toInit = true; + PARCIterator *it = parcHashMap_CreateKeyIterator(lb->strategy_state); + + while (parcIterator_HasNext(it)) { + PARCUnsigned *cid = parcIterator_Next(it); + StrategyNexthopStateWithPD *elem = + (StrategyNexthopStateWithPD *)parcHashMap_Get(lb->strategy_state, cid); + + strategyNexthopStateWithPD_Reset(elem); + lb->weights_sum += strategyNexthopStateWithPD_GetWeight(elem); + } + + parcIterator_Release(&it); +} + +static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyNexthopStateWithPD *state = strategyNexthopStateWithPD_Create(); + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + + if (!parcHashMap_Contains(lb->strategy_state, cid)) { + parcHashMap_Put(lb->strategy_state, cid, state); + numberSet_Add(lb->nexthops, connectionId); + _strategyLoadBalancerWithPD_resetState(strategy); + } +} + +static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyLoadBalancerWithPD *lb = + (StrategyLoadBalancerWithPD *)strategy->context; + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + if (parcHashMap_Contains(lb->strategy_state, cid)) { + parcHashMap_Remove(lb->strategy_state, cid); + numberSet_Remove(lb->nexthops, connectionId); + _strategyLoadBalancerWithPD_resetState(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void _strategyLoadBalancerWithPD_ImplDestroy( + StrategyImpl **strategyPtr) { + parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*strategyPtr, + "Parameter must dereference to non-null pointer"); + + StrategyImpl *impl = *strategyPtr; + StrategyLoadBalancerWithPD *strategy = + (StrategyLoadBalancerWithPD *)impl->context; + + parcHashMap_Release(&(strategy->strategy_state)); + numberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **)&strategy); + parcMemory_Deallocate((void **)&impl); + *strategyPtr = NULL; +} diff --git a/hicn-light/src/strategies/loadBalancerWithPD.h b/hicn-light/src/strategies/loadBalancerWithPD.h new file mode 100755 index 000000000..6ea7f0785 --- /dev/null +++ b/hicn-light/src/strategies/loadBalancerWithPD.h @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Forward on the less loaded path taking into account the propagation delay of + * the first hop + */ + +#ifndef loadBalancerWithPD_h +#define loadBalancerWithPD_h + +#include <src/core/connectionTable.h> +#include <src/strategies/strategyImpl.h> + +StrategyImpl *strategyLoadBalancerWithPD_Create(); +void strategyLoadBalancerWithPD_SetConnectionTable(StrategyImpl *strategy, + ConnectionTable *connTable); +#endif // loadBalancerWithPD_h diff --git a/hicn-light/src/strategies/nexthopState.c b/hicn-light/src/strategies/nexthopState.c new file mode 100755 index 000000000..ef0ffe982 --- /dev/null +++ b/hicn-light/src/strategies/nexthopState.c @@ -0,0 +1,206 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_DisplayIndented.h> +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_Object.h> + +#include <parc/assert/parc_Assert.h> +#include <src/strategies/nexthopState.h> + +struct strategy_nexthop_state { + unsigned int pi; + double avg_pi; + double weight; +}; + +static bool _strategyNexthopState_Destructor( + StrategyNexthopState **instancePtr) { + return true; +} + +parcObject_ImplementAcquire(strategyNexthopState, StrategyNexthopState); + +parcObject_ImplementRelease(strategyNexthopState, StrategyNexthopState); + +parcObject_Override( + StrategyNexthopState, PARCObject, + .destructor = (PARCObjectDestructor *)_strategyNexthopState_Destructor, + .copy = (PARCObjectCopy *)strategyNexthopState_Copy, + .display = (PARCObjectDisplay *)strategyNexthopState_Display, + .toString = (PARCObjectToString *)strategyNexthopState_ToString, + .equals = (PARCObjectEquals *)strategyNexthopState_Equals, + .compare = (PARCObjectCompare *)strategyNexthopState_Compare, + .hashCode = (PARCObjectHashCode *)strategyNexthopState_HashCode, + .display = (PARCObjectDisplay *)strategyNexthopState_Display); + +void strategyNexthopState_AssertValid(const StrategyNexthopState *instance) { + parcAssertTrue(strategyNexthopState_IsValid(instance), + "StrategyNexthopState is not valid."); +} + +StrategyNexthopState *strategyNexthopState_Create() { + StrategyNexthopState *result = + parcObject_CreateInstance(StrategyNexthopState); + if (result != NULL) { + result->pi = 0; + result->avg_pi = 0.0; + result->weight = 1; + } + return result; +} + +void strategyNexthopState_Reset(StrategyNexthopState *x) { + x->pi = 0; + x->avg_pi = 0.0; + x->weight = 1; +} + +int strategyNexthopState_Compare(const StrategyNexthopState *val, + const StrategyNexthopState *other) { + if (val == NULL) { + if (other != NULL) { + return -1; + } + } else if (other == NULL) { + return 1; + } else { + strategyNexthopState_OptionalAssertValid(val); + strategyNexthopState_OptionalAssertValid(other); + + if (val->pi < other->pi) { + return -1; + } else if (val->pi > other->pi) { + return 1; + } + + if (val->avg_pi < other->avg_pi) { + return -1; + } else if (val->avg_pi > other->avg_pi) { + return 1; + } + + if (val->weight < other->weight) { + return -1; + } else if (val->weight > other->weight) { + return 1; + } + } + + return 0; +} + +StrategyNexthopState *strategyNexthopState_Copy( + const StrategyNexthopState *original) { + StrategyNexthopState *result = strategyNexthopState_Create(); + result->pi = original->pi; + result->avg_pi = original->avg_pi; + result->weight = original->weight; + + return result; +} + +void strategyNexthopState_Display(const StrategyNexthopState *instance, + int indentation) { + parcDisplayIndented_PrintLine(indentation, "StrategyNexthopState@%p {", + instance); + parcDisplayIndented_PrintLine(indentation + 1, "%d", instance->pi); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_pi); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->weight); + parcDisplayIndented_PrintLine(indentation, "}"); +} + +bool strategyNexthopState_Equals(const StrategyNexthopState *x, + const StrategyNexthopState *y) { + bool result = false; + + if (x == y) { + result = true; + } else if (x == NULL || y == NULL) { + result = false; + } else { + strategyNexthopState_OptionalAssertValid(x); + strategyNexthopState_OptionalAssertValid(y); + + if (strategyNexthopState_Compare(x, y) == 0) { + result = true; + } + } + + return result; +} + +PARCHashCode strategyNexthopState_HashCode(const StrategyNexthopState *x) { + PARCHashCode result = 0; + char str[128]; + sprintf(str, "PI:%d: AVG_PI:%f: W:%f", x->pi, x->avg_pi, x->weight); + result = parcHashCode_Hash((uint8_t *)&str, strlen(str)); + return result; +} + +bool strategyNexthopState_IsValid(const StrategyNexthopState *x) { + bool result = false; + + if (x != NULL) { + result = true; + } + + return result; +} + +char *strategyNexthopState_ToString(const StrategyNexthopState *x) { + // this is not implemented + parcTrapNotImplemented("strategyNexthopState_ToString is not implemented"); + return NULL; +} + +unsigned strategyNexthopState_GetPI(const StrategyNexthopState *x) { + strategyNexthopState_OptionalAssertValid(x); + + return x->pi; +} + +double strategyNexthopState_GetAvgPI(const StrategyNexthopState *x) { + strategyNexthopState_OptionalAssertValid(x); + + return x->avg_pi; +} + +double strategyNexthopState_GetWeight(const StrategyNexthopState *x) { + strategyNexthopState_OptionalAssertValid(x); + + return x->weight; +} + +double strategyNexthopState_UpdateState(StrategyNexthopState *x, bool inc, + double alpha) { + if (inc) { + x->pi++; + } else { + if (x->pi > 0) { + x->pi--; + } + } + x->avg_pi = (x->avg_pi * alpha) + (x->pi * (1 - alpha)); + if (x->avg_pi == 0.0) { + x->avg_pi = 0.1; + } + x->weight = 1 / x->avg_pi; + + return x->weight; +} diff --git a/hicn-light/src/strategies/nexthopState.h b/hicn-light/src/strategies/nexthopState.h new file mode 100755 index 000000000..35a9f497b --- /dev/null +++ b/hicn-light/src/strategies/nexthopState.h @@ -0,0 +1,94 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef nexthopstate_h +#define nexthopstate_h + +#include <parc/algol/parc_HashCode.h> +#include <parc/algol/parc_Object.h> + +struct strategy_nexthop_state; +typedef struct strategy_nexthop_state StrategyNexthopState; +extern parcObjectDescriptor_Declaration(StrategyNexthopState); + +/** + */ +StrategyNexthopState *strategyNexthopState_Acquire( + const StrategyNexthopState *instance); + +#ifdef PARCLibrary_DISABLE_VALIDATION +#define strategyNexthopState_OptionalAssertValid(_instance_) +#else +#define strategyNexthopState_OptionalAssertValid(_instance_) \ + strategyNexthopState_AssertValid(_instance_) +#endif + +/** + */ +void strategyNexthopState_AssertValid(const StrategyNexthopState *instance); + +/** + */ +StrategyNexthopState *strategyNexthopState_Create(); + +void strategyNexthopState_Reset(StrategyNexthopState *x); +/** + */ +int strategyNexthopState_Compare(const StrategyNexthopState *instance, + const StrategyNexthopState *other); + +/** + */ +StrategyNexthopState *strategyNexthopState_Copy( + const StrategyNexthopState *original); + +/** + */ +void strategyNexthopState_Display(const StrategyNexthopState *instance, + int indentation); + +/** + */ +bool strategyNexthopState_Equals(const StrategyNexthopState *x, + const StrategyNexthopState *y); + +/** + */ +PARCHashCode strategyNexthopState_HashCode( + const StrategyNexthopState *instance); + +/** + */ +bool strategyNexthopState_IsValid(const StrategyNexthopState *instance); + +/** + */ +void strategyNexthopState_Release(StrategyNexthopState **instancePtr); + +/** + */ +char *strategyNexthopState_ToString(const StrategyNexthopState *instance); + +/** + */ +unsigned strategyNexthopState_GetPI(const StrategyNexthopState *x); + +double strategyNexthopState_GetAvgPI(const StrategyNexthopState *x); + +double strategyNexthopState_GetWeight(const StrategyNexthopState *x); + +double strategyNexthopState_UpdateState(StrategyNexthopState *x, bool inc, + double alpha); +#endif diff --git a/hicn-light/src/strategies/nexthopStateWithPD.c b/hicn-light/src/strategies/nexthopStateWithPD.c new file mode 100755 index 000000000..2eecb0c64 --- /dev/null +++ b/hicn-light/src/strategies/nexthopStateWithPD.c @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <float.h> +#include <limits.h> +#include <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_DisplayIndented.h> +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_Object.h> +#include <parc/assert/parc_Assert.h> + +#include <src/strategies/nexthopStateWithPD.h> + +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, + .display = (PARCObjectDisplay *)strategyNexthopStateWithPD_Display); + +void strategyNexthopStateWithPD_AssertValid( + const StrategyNexthopStateWithPD *instance) { + parcAssertTrue(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; +} + +char *strategyNexthopStateWithPD_ToString(const StrategyNexthopStateWithPD *x) { + // this is not implemented + parcTrapNotImplemented( + "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/hicn-light/src/strategies/nexthopStateWithPD.h b/hicn-light/src/strategies/nexthopStateWithPD.h new file mode 100755 index 000000000..4d8bd6d15 --- /dev/null +++ b/hicn-light/src/strategies/nexthopStateWithPD.h @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef nexthopstatewithpd_h +#define nexthopstatewithpd_h + +#include <parc/algol/parc_HashCode.h> +#include <parc/algol/parc_Object.h> + +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); + +/** + */ +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/hicn-light/src/strategies/rnd.c b/hicn-light/src/strategies/rnd.c new file mode 100755 index 000000000..37f3f6f30 --- /dev/null +++ b/hicn-light/src/strategies/rnd.c @@ -0,0 +1,175 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <parc/assert/parc_Assert.h> + +#include <parc/algol/parc_HashMap.h> +#include <parc/algol/parc_Memory.h> + +#include <src/strategies/rnd.h> + +static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, Ticks rtt); +static void _strategyRnd_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId); +static NumberSet *_strategyRnd_LookupNexthop(StrategyImpl *strategy, + const Message *interestMessage); +static NumberSet *_strategyRnd_ReturnNexthops(StrategyImpl *strategy); +static unsigned _strategyRnd_CountNexthops(StrategyImpl *strategy); +static void _strategyRnd_AddNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyRnd_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyRnd_ImplDestroy(StrategyImpl **strategyPtr); +static strategy_type _strategyRnd_GetStrategy(StrategyImpl *strategy); + +static StrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyRnd_ReceiveObject, + .onTimeout = &_strategyRnd_OnTimeout, + .lookupNexthop = &_strategyRnd_LookupNexthop, + .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 { + NumberSet *nexthops; +}; + +StrategyImpl *strategyRnd_Create() { + StrategyRnd *strategy = parcMemory_AllocateAndClear(sizeof(StrategyRnd)); + parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyRnd)); + + strategy->nexthops = numberSet_Create(); + srand(time(NULL)); + + StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); + parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyImpl)); + memcpy(impl, &_template, sizeof(StrategyImpl)); + impl->context = strategy; + return impl; +} + +// ======================================================= +// Dispatch API + +strategy_type _strategyRnd_GetStrategy(StrategyImpl *strategy) { + return SET_STRATEGY_RANDOM; +} + +static int _select_Nexthop(StrategyRnd *strategy) { + unsigned len = numberSet_Length(strategy->nexthops); + if (len == 0) { + return -1; + } + + int rnd = (rand() % len); + return numberSet_GetItem(strategy->nexthops, rnd); +} + +static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks rtt) {} + +static void _strategyRnd_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId) {} + +static NumberSet *_strategyRnd_LookupNexthop(StrategyImpl *strategy, + const Message *interestMessage) { + StrategyRnd *srnd = (StrategyRnd *)strategy->context; + + unsigned in_connection = message_GetIngressConnectionId(interestMessage); + unsigned nexthopSize = numberSet_Length(srnd->nexthops); + + NumberSet *out = numberSet_Create(); + if ((nexthopSize == 0) || + ((nexthopSize == 1) && + numberSet_Contains(srnd->nexthops, in_connection))) { + // there are no output faces or the input face is also the only output face. + // return null to avoid loops + return out; + } + + unsigned out_connection; + do { + out_connection = _select_Nexthop(srnd); + } while (out_connection == in_connection); + + if (out_connection == -1) { + return out; + } + + numberSet_Add(out, out_connection); + return out; +} + +static NumberSet *_strategyRnd_ReturnNexthops(StrategyImpl *strategy) { + StrategyRnd *srnd = (StrategyRnd *)strategy->context; + return srnd->nexthops; +} + +unsigned _strategyRnd_CountNexthops(StrategyImpl *strategy) { + StrategyRnd *srnd = (StrategyRnd *)strategy->context; + return numberSet_Length(srnd->nexthops); +} + +static void _strategyRnd_AddNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyRnd *srnd = (StrategyRnd *)strategy->context; + if (!numberSet_Contains(srnd->nexthops, connectionId)) { + numberSet_Add(srnd->nexthops, connectionId); + } +} + +static void _strategyRnd_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyRnd *srnd = (StrategyRnd *)strategy->context; + + if (numberSet_Contains(srnd->nexthops, connectionId)) { + numberSet_Remove(srnd->nexthops, connectionId); + } +} + +static void _strategyRnd_ImplDestroy(StrategyImpl **strategyPtr) { + parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*strategyPtr, + "Parameter must dereference to non-null pointer"); + + StrategyImpl *impl = *strategyPtr; + StrategyRnd *strategy = (StrategyRnd *)impl->context; + + numberSet_Release(&(strategy->nexthops)); + + parcMemory_Deallocate((void **)&strategy); + parcMemory_Deallocate((void **)&impl); + *strategyPtr = NULL; +} diff --git a/hicn-light/src/strategies/rnd.h b/hicn-light/src/strategies/rnd.h new file mode 100755 index 000000000..69bedc1a5 --- /dev/null +++ b/hicn-light/src/strategies/rnd.h @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Forward randomly + */ + +#ifndef rnd_h +#define rnd_h + +#include <src/strategies/strategyImpl.h> + +StrategyImpl* strategyRnd_Create(); +#endif // rnd_h diff --git a/hicn-light/src/strategies/rndSegment.c b/hicn-light/src/strategies/rndSegment.c new file mode 100755 index 000000000..2000ed7b7 --- /dev/null +++ b/hicn-light/src/strategies/rndSegment.c @@ -0,0 +1,207 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <parc/assert/parc_Assert.h> + +#include <parc/algol/parc_HashMap.h> +#include <parc/algol/parc_Memory.h> +#include <src/core/nameBitvector.h> +#include <src/strategies/rndSegment.h> + +static void _strategyRndSegment_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks rtt); +static void _strategyRndSegment_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId); +static NumberSet *_strategyRndSegment_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage); +static NumberSet *_strategyRndSegment_ReturnNexthops(StrategyImpl *strategy); +static unsigned _strategyRndSegment_CountNexthops(StrategyImpl *strategy); +static void _strategyRndSegment_AddNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyRndSegment_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyRndSegment_ImplDestroy(StrategyImpl **strategyPtr); +static strategy_type _strategyRndSegment_GetStrategy(StrategyImpl *strategy); + +static StrategyImpl _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 { + NumberSet *nexthops; + NameBitvector *segmentName; + int last_used_face; +}; + +StrategyImpl *strategyRndSegment_Create() { + StrategyRndSegment *strategy = + parcMemory_AllocateAndClear(sizeof(StrategyRndSegment)); + parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyRndSegment)); + + strategy->nexthops = numberSet_Create(); + strategy->segmentName = NULL; + strategy->last_used_face = 0; + srand(time(NULL)); + + StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); + parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyImpl)); + memcpy(impl, &_template, sizeof(StrategyImpl)); + impl->context = strategy; + + return impl; +} + +// ======================================================= +// Dispatch API + +strategy_type _strategyRndSegment_GetStrategy(StrategyImpl *strategy) { + return SET_STRATEGY_RANDOM_PER_DASH_SEGMENT; +} + +static int _select_Nexthop(StrategyRndSegment *strategy) { + unsigned len = numberSet_Length(strategy->nexthops); + if (len == 0) { + return -1; + } + + int rnd = (rand() % len); + return numberSet_GetItem(strategy->nexthops, rnd); +} + +static void _strategyRndSegment_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks rtt) {} + +static void _strategyRndSegment_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId) {} + +static NumberSet *_strategyRndSegment_LookupNexthop( + StrategyImpl *strategy, const Message *interestMessage) { + StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; + + unsigned in_connection = message_GetIngressConnectionId(interestMessage); + unsigned nexthopSize = numberSet_Length(srnd->nexthops); + + NumberSet *out = numberSet_Create(); + if ((nexthopSize == 0) || + ((nexthopSize == 1) && + numberSet_Contains(srnd->nexthops, in_connection))) { + // there are no output faces or the input face is also the only output face. + // return null to avoid loops + return out; + } + + NameBitvector *interestName = + name_GetContentName(message_GetName(interestMessage)); + + if (srnd->segmentName == NULL) { + srnd->segmentName = nameBitvector_Copy(interestName); + } else if (!nameBitvector_Equals(srnd->segmentName, interestName)) { + nameBitvector_Destroy(&srnd->segmentName); + srnd->segmentName = nameBitvector_Copy(interestName); + } else { + // here we need to check if the output face still exists or if someone erase + // it + if (numberSet_Contains(srnd->nexthops, srnd->last_used_face)) { + // face exists, so keep using it! + numberSet_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 + } + } + + 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; + numberSet_Add(out, out_connection); + return out; +} + +static NumberSet *_strategyRndSegment_ReturnNexthops(StrategyImpl *strategy) { + StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; + return srnd->nexthops; +} + +unsigned _strategyRndSegment_CountNexthops(StrategyImpl *strategy) { + StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; + return numberSet_Length(srnd->nexthops); +} + +static void _strategyRndSegment_AddNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; + if (!numberSet_Contains(srnd->nexthops, connectionId)) { + numberSet_Add(srnd->nexthops, connectionId); + } +} + +static void _strategyRndSegment_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; + + if (numberSet_Contains(srnd->nexthops, connectionId)) { + numberSet_Remove(srnd->nexthops, connectionId); + } +} + +static void _strategyRndSegment_ImplDestroy(StrategyImpl **strategyPtr) { + parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*strategyPtr, + "Parameter must dereference to non-null pointer"); + + StrategyImpl *impl = *strategyPtr; + StrategyRndSegment *strategy = (StrategyRndSegment *)impl->context; + + numberSet_Release(&(strategy->nexthops)); + if (strategy->segmentName != NULL) { + nameBitvector_Destroy(&strategy->segmentName); + } + + parcMemory_Deallocate((void **)&strategy); + parcMemory_Deallocate((void **)&impl); + *strategyPtr = NULL; +} diff --git a/hicn-light/src/strategies/rndSegment.h b/hicn-light/src/strategies/rndSegment.h new file mode 100755 index 000000000..0749692f7 --- /dev/null +++ b/hicn-light/src/strategies/rndSegment.h @@ -0,0 +1,27 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Forward randomly, selects a path every time the client ask for a new dash + * segment + */ + +#ifndef rnd_Segment_h +#define rnd_Segment_h + +#include <src/strategies/strategyImpl.h> + +StrategyImpl* strategyRndSegment_Create(); +#endif // rnd_Segment_h diff --git a/hicn-light/src/strategies/strategyImpl.h b/hicn-light/src/strategies/strategyImpl.h new file mode 100755 index 000000000..c089e0b2b --- /dev/null +++ b/hicn-light/src/strategies/strategyImpl.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file strategyImpl.h + * @brief Defines the function structure for a Strategy implementation + * + * <#Detailed Description#> + * + */ + +/** + * A dispatch structure for a concrete implementation of a forwarding strategy. + */ + +#ifndef strategyImpl_h +#define strategyImpl_h + +#include <src/core/message.h> +#include <src/core/numberSet.h> + +struct strategy_impl; +typedef struct strategy_impl StrategyImpl; + +/** + * @typedef StrategyImpl + * @abstract Forwarding strategy implementation + * @constant receiveObject is called when we receive an object and have a + * measured round trip time. This allows a strategy to update its performance + * data. + * @constant lookupNexthop Find the set of nexthops to use for the Interest. + * May be empty, should not be NULL. Must be destroyed. + * @constant addNexthop Add a nexthop to the list of available nexthops with a + * routing protocol-specific cost. + * @constant destroy cleans up the strategy, freeing all memory and state. A + * strategy is reference counted, so the final destruction only happens after + * the last reference is released. + * @discussion <#Discussion#> + */ +struct strategy_impl { + void *context; + void (*receiveObject)(StrategyImpl *strategy, const NumberSet *egressId, + const Message *objectMessage, Ticks rtt); + void (*onTimeout)(StrategyImpl *strategy, const NumberSet *egressId); + NumberSet *(*lookupNexthop)(StrategyImpl *strategy, + const Message *interestMessage); + NumberSet *(*returnNexthops)(StrategyImpl *strategy); + unsigned (*countNexthops)(StrategyImpl *strategy); + void (*addNexthop)(StrategyImpl *strategy, unsigned connectionId); + void (*removeNexthop)(StrategyImpl *strategy, unsigned connectionId); + void (*destroy)(StrategyImpl **strategyPtr); + strategy_type (*getStrategy)(StrategyImpl *strategy); +}; +#endif // strategyImpl_h |