diff options
author | Luca Muscariello <lumuscar+fdio@cisco.com> | 2019-03-23 14:13:53 +0100 |
---|---|---|
committer | Angelo Mantellini <manangel@cisco.com> | 2019-03-24 14:11:17 +0100 |
commit | eb323e056e747d71867cf965434811c1de925de2 (patch) | |
tree | 23a6096823d795efe448559cf0409a18ab47932d /hicn-light/src/strategies | |
parent | 43562f9f02d35e5d540ab4028a0326c0c7cd4898 (diff) |
[HICN-141] Definition of a C API for hicn-light
Change-Id: Id861f0abe58b1e3c9ba8cc76701da0f9c6801748
Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>
Signed-off-by: Angelo Mantellini <manangel@cisco.com>
Diffstat (limited to 'hicn-light/src/strategies')
-rw-r--r-- | hicn-light/src/strategies/CMakeLists.txt | 36 | ||||
-rw-r--r-- | hicn-light/src/strategies/loadBalancer.c | 278 | ||||
-rw-r--r-- | hicn-light/src/strategies/loadBalancer.h | 26 | ||||
-rw-r--r-- | hicn-light/src/strategies/loadBalancerWithPD.c | 368 | ||||
-rw-r--r-- | hicn-light/src/strategies/loadBalancerWithPD.h | 30 | ||||
-rw-r--r-- | hicn-light/src/strategies/nexthopState.c | 206 | ||||
-rw-r--r-- | hicn-light/src/strategies/nexthopState.h | 94 | ||||
-rw-r--r-- | hicn-light/src/strategies/nexthopStateWithPD.c | 254 | ||||
-rw-r--r-- | hicn-light/src/strategies/nexthopStateWithPD.h | 106 | ||||
-rw-r--r-- | hicn-light/src/strategies/rnd.c | 175 | ||||
-rw-r--r-- | hicn-light/src/strategies/rnd.h | 26 | ||||
-rw-r--r-- | hicn-light/src/strategies/rndSegment.c | 207 | ||||
-rw-r--r-- | hicn-light/src/strategies/rndSegment.h | 27 | ||||
-rw-r--r-- | hicn-light/src/strategies/strategyImpl.h | 66 |
14 files changed, 0 insertions, 1899 deletions
diff --git a/hicn-light/src/strategies/CMakeLists.txt b/hicn-light/src/strategies/CMakeLists.txt deleted file mode 100644 index 7f0730b2f..000000000 --- a/hicn-light/src/strategies/CMakeLists.txt +++ /dev/null @@ -1,36 +0,0 @@ -# Copyright (c) 2017-2019 Cisco and/or its affiliates. -# Licensed under the Apache License, Version 2.0 (the "License"); -# you may not use this file except in compliance with the License. -# You may obtain a copy of the License at: -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -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 deleted file mode 100644 index 8dda98603..000000000 --- a/hicn-light/src/strategies/loadBalancer.c +++ /dev/null @@ -1,278 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <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((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - - 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 = (unsigned)parcHashMap_Size(lb->strategy_state); - NumberSet *outList = numberSet_Create(); - - if ((mapSize == 0) || - ((mapSize == 1) && parcHashMap_Contains(lb->strategy_state, in))) { - // there are no output faces or the input face is also the only output face. - // return null to avoid loops - parcUnsigned_Release(&in); - return outList; - } - - unsigned out_connection; - do { - out_connection = _select_Nexthop(lb); - } while (out_connection == in_connection); - - PARCUnsigned *out = parcUnsigned_Create(out_connection); - - const 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 (unsigned)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 deleted file mode 100644 index 1178c30fe..000000000 --- a/hicn-light/src/strategies/loadBalancer.h +++ /dev/null @@ -1,26 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * 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 deleted file mode 100644 index c9c1479a2..000000000 --- a/hicn-light/src/strategies/loadBalancerWithPD.c +++ /dev/null @@ -1,368 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <limits.h> -#include <src/config.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <time.h> - -#include <parc/assert/parc_Assert.h> - -#include <parc/algol/parc_HashMap.h> -#include <parc/algol/parc_Memory.h> -#include <parc/algol/parc_Object.h> -#include <parc/algol/parc_Unsigned.h> - -#include <src/strategies/loadBalancerWithPD.h> -#include <src/strategies/nexthopStateWithPD.h> - -const unsigned PROBE_FREQUENCY = 1024; - -static void _strategyLoadBalancerWithPD_ReceiveObject( - StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); -static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId); -static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( - StrategyImpl *strategy, const Message *interestMessage); -static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( - StrategyImpl *strategy); -static unsigned _strategyLoadBalancerWithPD_CountNexthops( - StrategyImpl *strategy); -static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId); -static void _strategyLoadBalancerWithPD_ImplDestroy(StrategyImpl **strategyPtr); -static strategy_type _strategyLoadBalancerWithPD_GetStrategy( - StrategyImpl *strategy); - -static StrategyImpl _template = { - .context = NULL, - .receiveObject = &_strategyLoadBalancerWithPD_ReceiveObject, - .onTimeout = &_strategyLoadBalancerWithPD_OnTimeout, - .lookupNexthop = &_strategyLoadBalancerWithPD_LookupNexthop, - .returnNexthops = &_strategyLoadBalancerWithPD_ReturnNexthops, - .countNexthops = &_strategyLoadBalancerWithPD_CountNexthops, - .addNexthop = &_strategyLoadBalancerWithPD_AddNexthop, - .removeNexthop = &_strategyLoadBalancerWithPD_RemoveNexthop, - .destroy = &_strategyLoadBalancerWithPD_ImplDestroy, - .getStrategy = &_strategyLoadBalancerWithPD_GetStrategy, -}; - -struct strategy_load_balancer_with_pd; -typedef struct strategy_load_balancer_with_pd StrategyLoadBalancerWithPD; - -struct strategy_load_balancer_with_pd { - double weights_sum; - unsigned min_delay; - // hash map from connectionId to StrategyNexthopState - PARCHashMap *strategy_state; - NumberSet *nexthops; - ConnectionTable *connTable; - bool toInit; - unsigned int fwdPackets; -}; - -StrategyImpl *strategyLoadBalancerWithPD_Create() { - StrategyLoadBalancerWithPD *strategy = - parcMemory_AllocateAndClear(sizeof(StrategyLoadBalancerWithPD)); - parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyLoadBalancerWithPD)); - - strategy->weights_sum = 0.0; - strategy->min_delay = INT_MAX; - strategy->strategy_state = parcHashMap_Create(); - strategy->nexthops = numberSet_Create(); - srand((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - strategy->connTable = NULL; - strategy->fwdPackets = 0; - strategy->toInit = true; - - return impl; -} - -void strategyLoadBalancerWithPD_SetConnectionTable(StrategyImpl *strategy, - ConnectionTable *connTable) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - lb->connTable = connTable; -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyLoadBalancerWithPD_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_LOADBALANCER_WITH_DELAY; -} - -static void _update_Stats(StrategyLoadBalancerWithPD *strategy, - StrategyNexthopStateWithPD *state, bool inc, - Ticks rtt) { - const double ALPHA = 0.9; - double w = strategyNexthopStateWithPD_GetWeight(state); - strategy->weights_sum -= w; - w = strategyNexthopStateWithPD_UpdateState(state, inc, strategy->min_delay, - ALPHA); - strategy->weights_sum += w; -} - -static void _sendProbes(StrategyLoadBalancerWithPD *strategy) { - unsigned size = (unsigned)numberSet_Length(strategy->nexthops); - for (unsigned i = 0; i < size; i++) { - unsigned nhop = numberSet_GetItem(strategy->nexthops, i); - Connection *conn = - (Connection *)connectionTable_FindById(strategy->connTable, nhop); - if (conn != NULL) { - connection_Probe(conn); - unsigned delay = (unsigned)connection_GetDelay(conn); - PARCUnsigned *cid = parcUnsigned_Create(nhop); - StrategyNexthopStateWithPD *elem = - (StrategyNexthopStateWithPD *)parcHashMap_Get( - strategy->strategy_state, cid); - strategyNexthopStateWithPD_SetDelay(elem, delay); - if (delay < strategy->min_delay && delay != 0) { - strategy->min_delay = delay; - } - - parcUnsigned_Release(&cid); - } - } -} - -static unsigned _select_Nexthop(StrategyLoadBalancerWithPD *strategy) { - strategy->fwdPackets++; - if (strategy->toInit || strategy->fwdPackets == PROBE_FREQUENCY) { - strategy->toInit = false; - strategy->fwdPackets = 0; - _sendProbes(strategy); - } - double rnd = (double)rand() / (double)RAND_MAX; - double start_range = 0.0; - - PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); - - unsigned nexthop = 100000; - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - const StrategyNexthopStateWithPD *elem = - parcHashMap_Get(strategy->strategy_state, cid); - - double w = strategyNexthopStateWithPD_GetWeight(elem); - - // printf("next = %u .. pi %u avgpi %f w %f avgrtt - // %f\n",parcUnsigned_GetUnsigned(cid), - // strategyNexthopStateWithPD_GetPI(elem), - // strategyNexthopStateWithPD_GetWeight(elem), - // strategyNexthopStateWithPD_GetWeight(elem), - // strategyNexthopStateWithPD_GetAvgRTT(elem)); - - double prob = w / strategy->weights_sum; - if ((rnd >= start_range) && (rnd < (start_range + prob))) { - nexthop = parcUnsigned_GetUnsigned(cid); - break; - } else { - start_range += prob; - } - } - - parcIterator_Release(&it); - - // if no face is selected by the algorithm (for example because of a wrong - // round in the weights) we may always select the last face here. Double check - // this! - return nexthop; -} - -static void _strategyLoadBalancerWithPD_ReceiveObject( - StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopStateWithPD *state = - parcHashMap_Get(lb->strategy_state, cid); - if (state != NULL) { - _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } -} - -static void _strategyLoadBalancerWithPD_OnTimeout(StrategyImpl *strategy, - const NumberSet *egressId) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - for (unsigned i = 0; i < numberSet_Length(egressId); i++) { - unsigned outId = numberSet_GetItem(egressId, i); - PARCUnsigned *cid = parcUnsigned_Create(outId); - - const StrategyNexthopStateWithPD *state = - parcHashMap_Get(lb->strategy_state, cid); - if (state != NULL) { - _update_Stats(lb, (StrategyNexthopStateWithPD *)state, false, 0); - } else { - // this may happen if we remove a face/route while downloading a file - // we should ignore this timeout - } - parcUnsigned_Release(&cid); - } -} - -// ATTENTION!! This interface force us to create a NumberSet which need to be -// delited somewhere The specification in the interface requires that this -// function never returns NULL. in case we have no output face we need to return -// an empty NumberSet -static NumberSet *_strategyLoadBalancerWithPD_LookupNexthop( - StrategyImpl *strategy, const Message *interestMessage) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - unsigned in_connection = message_GetIngressConnectionId(interestMessage); - PARCUnsigned *in = parcUnsigned_Create(in_connection); - - unsigned mapSize = (unsigned)parcHashMap_Size(lb->strategy_state); - NumberSet *outList = numberSet_Create(); - - if ((mapSize == 0) || - ((mapSize == 1) && parcHashMap_Contains(lb->strategy_state, in))) { - // there are no output faces or the input face is also the only output face. - // return null to avoid loops - parcUnsigned_Release(&in); - return outList; - } - - unsigned out_connection; - do { - out_connection = _select_Nexthop(lb); - } while (out_connection == in_connection); - - PARCUnsigned *out = parcUnsigned_Create(out_connection); - - const StrategyNexthopStateWithPD *state = - parcHashMap_Get(lb->strategy_state, out); - if (state == NULL) { - // this is an error and should not happen! - parcTrapNotImplemented( - "Try to send an interest on a face that does not exists"); - } - - _update_Stats(lb, (StrategyNexthopStateWithPD *)state, true, 0); - - parcUnsigned_Release(&in); - parcUnsigned_Release(&out); - - numberSet_Add(outList, out_connection); - return outList; -} - -static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( - StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - return lb->nexthops; -} - -unsigned _strategyLoadBalancerWithPD_CountNexthops(StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - return (unsigned)numberSet_Length(lb->nexthops); -} - -static void _strategyLoadBalancerWithPD_resetState(StrategyImpl *strategy) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - lb->weights_sum = 0.0; - lb->min_delay = INT_MAX; - lb->toInit = true; - PARCIterator *it = parcHashMap_CreateKeyIterator(lb->strategy_state); - - while (parcIterator_HasNext(it)) { - PARCUnsigned *cid = parcIterator_Next(it); - StrategyNexthopStateWithPD *elem = - (StrategyNexthopStateWithPD *)parcHashMap_Get(lb->strategy_state, cid); - - strategyNexthopStateWithPD_Reset(elem); - lb->weights_sum += strategyNexthopStateWithPD_GetWeight(elem); - } - - parcIterator_Release(&it); -} - -static void _strategyLoadBalancerWithPD_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyNexthopStateWithPD *state = strategyNexthopStateWithPD_Create(); - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - if (!parcHashMap_Contains(lb->strategy_state, cid)) { - parcHashMap_Put(lb->strategy_state, cid, state); - numberSet_Add(lb->nexthops, connectionId); - _strategyLoadBalancerWithPD_resetState(strategy); - } -} - -static void _strategyLoadBalancerWithPD_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { - StrategyLoadBalancerWithPD *lb = - (StrategyLoadBalancerWithPD *)strategy->context; - - PARCUnsigned *cid = parcUnsigned_Create(connectionId); - - if (parcHashMap_Contains(lb->strategy_state, cid)) { - parcHashMap_Remove(lb->strategy_state, cid); - numberSet_Remove(lb->nexthops, connectionId); - _strategyLoadBalancerWithPD_resetState(strategy); - } - - parcUnsigned_Release(&cid); -} - -static void _strategyLoadBalancerWithPD_ImplDestroy( - StrategyImpl **strategyPtr) { - parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*strategyPtr, - "Parameter must dereference to non-null pointer"); - - StrategyImpl *impl = *strategyPtr; - StrategyLoadBalancerWithPD *strategy = - (StrategyLoadBalancerWithPD *)impl->context; - - parcHashMap_Release(&(strategy->strategy_state)); - numberSet_Release(&(strategy->nexthops)); - - parcMemory_Deallocate((void **)&strategy); - parcMemory_Deallocate((void **)&impl); - *strategyPtr = NULL; -} diff --git a/hicn-light/src/strategies/loadBalancerWithPD.h b/hicn-light/src/strategies/loadBalancerWithPD.h deleted file mode 100644 index 6ea7f0785..000000000 --- a/hicn-light/src/strategies/loadBalancerWithPD.h +++ /dev/null @@ -1,30 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * 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 deleted file mode 100644 index ef0ffe982..000000000 --- a/hicn-light/src/strategies/nexthopState.c +++ /dev/null @@ -1,206 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <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 deleted file mode 100644 index 35a9f497b..000000000 --- a/hicn-light/src/strategies/nexthopState.h +++ /dev/null @@ -1,94 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#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 deleted file mode 100644 index 2eecb0c64..000000000 --- a/hicn-light/src/strategies/nexthopStateWithPD.c +++ /dev/null @@ -1,254 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <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 deleted file mode 100644 index 4d8bd6d15..000000000 --- a/hicn-light/src/strategies/nexthopStateWithPD.h +++ /dev/null @@ -1,106 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#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 deleted file mode 100644 index 35b9e87c6..000000000 --- a/hicn-light/src/strategies/rnd.c +++ /dev/null @@ -1,175 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <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((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - return impl; -} - -// ======================================================= -// Dispatch API - -strategy_type _strategyRnd_GetStrategy(StrategyImpl *strategy) { - return SET_STRATEGY_RANDOM; -} - -static int _select_Nexthop(StrategyRnd *strategy) { - unsigned len = (unsigned)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 = (unsigned)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 (unsigned)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 deleted file mode 100644 index 69bedc1a5..000000000 --- a/hicn-light/src/strategies/rnd.h +++ /dev/null @@ -1,26 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * 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 deleted file mode 100644 index 5ed9bf1a9..000000000 --- a/hicn-light/src/strategies/rndSegment.c +++ /dev/null @@ -1,207 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include <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((unsigned int)time(NULL)); - - StrategyImpl *impl = parcMemory_AllocateAndClear(sizeof(StrategyImpl)); - parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(StrategyImpl)); - memcpy(impl, &_template, sizeof(StrategyImpl)); - impl->context = strategy; - - 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 = (unsigned)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 = (unsigned)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 (unsigned)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 deleted file mode 100644 index 0749692f7..000000000 --- a/hicn-light/src/strategies/rndSegment.h +++ /dev/null @@ -1,27 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * 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 deleted file mode 100644 index c089e0b2b..000000000 --- a/hicn-light/src/strategies/strategyImpl.h +++ /dev/null @@ -1,66 +0,0 @@ -/* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * @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 |