diff options
author | michele papalini <micpapal@cisco.com> | 2019-12-10 13:40:16 +0100 |
---|---|---|
committer | michele papalini <micpapal@cisco.com> | 2020-01-21 10:26:25 +0100 |
commit | 43980f3096655df2b2ecec50e700dd6989b0e0d6 (patch) | |
tree | 1a8e23e6fe645d8d1951b84f14e4123f17d4efe9 /hicn-light | |
parent | de13ed1c3155f699cb1e322dcd4d64a06ae00bb9 (diff) |
[HICN-442] new forwarding strategy
Signed-off-by: michele papalini <micpapal@cisco.com>
Change-Id: I62c03bddedc83e523fc60f4b50d2c69e38b50318
Signed-off-by: Angelo Mantellini <angelo.mantellini@cisco.com>
Signed-off-by: michele papalini <micpapal@cisco.com>
Diffstat (limited to 'hicn-light')
34 files changed, 1622 insertions, 1459 deletions
diff --git a/hicn-light/README.md b/hicn-light/README.md index 559659dd1..f18de0df5 100644 --- a/hicn-light/README.md +++ b/hicn-light/README.md @@ -202,22 +202,19 @@ cache clear implemented in hicn-light: - random: each interest is forwarded randomly to one of the available output connections -- random_per_dash_segment: the output connection is selected randomly for each DASH segment. - This can be used only for DASH video streams. - loadbalancer: each interest is forwarded toward the output connection with the lowest number of pending interests. The pending interest are the interest sent on a certain connection but not yet satisfied. More information are available in: G. Carofiglio, M. Gallo, L. Muscariello, M. Papalini, S. Wang, "Optimal multipath congestion control and request forwarding in information-centric networks", ICNP 2013. -- loadbalancer_with_delay: implements the same strategy as loadbalancer but it takes into account - also the propagation delay behind each connections. +- low_latency: uses the face with the lowest latency. In case more faces have similar latency the strategy uses them in parallel ``` set strategy <prefix> <strategy> <preifx> : the prefix to which apply the forwarding strategy - <strategy> : random | random_per_dash_segment | loadbalancer | loadbalancer_with_delay + <strategy> : random | loadbalancer | low_latency ``` `set wldr`: turns on/off WLDR on the specified connection. WLDR (Wireless Loss Detiection and Recovery) is a protocol that can be used to recover losses generated by unreliable wireless diff --git a/hicn-light/src/hicn/config/configurationFile.c b/hicn-light/src/hicn/config/configurationFile.c index 3cce740ac..5f9c9ce9d 100644 --- a/hicn-light/src/hicn/config/configurationFile.c +++ b/hicn-light/src/hicn/config/configurationFile.c @@ -288,6 +288,9 @@ bool configurationFile_Process(ConfigurationFile *configFile) { } success = false; } + for(int i = 0; i < parcList_Size(args); i++){ + free(parcList_GetAtIndex(args, i)); + } parcList_Release(&args); parcMemory_Deallocate((void **)©); } diff --git a/hicn-light/src/hicn/config/controlAddListener.c b/hicn-light/src/hicn/config/controlAddListener.c index d4537b855..2f0fd3f67 100644 --- a/hicn-light/src/hicn/config/controlAddListener.c +++ b/hicn-light/src/hicn/config/controlAddListener.c @@ -119,7 +119,13 @@ static CommandReturn _CreateListener(CommandParser *parser, CommandOps *ops, } // Fill remaining payload fields - memcpy(addListenerCommand->interfaceName, interfaceName, SYMBOLIC_NAME_LEN); + size_t name_size = strlen((const char *)interfaceName); + if(name_size > SYMBOLIC_NAME_LEN){ + //cut the string + name_size = SYMBOLIC_NAME_LEN; + } + + memcpy(addListenerCommand->interfaceName, interfaceName, name_size); addListenerCommand->listenerMode = mode; addListenerCommand->connectionType = type; addListenerCommand->port = htons((uint16_t)atoi(port)); diff --git a/hicn-light/src/hicn/config/controlSetStrategy.c b/hicn-light/src/hicn/config/controlSetStrategy.c index 5357a413e..10fec964b 100644 --- a/hicn-light/src/hicn/config/controlSetStrategy.c +++ b/hicn-light/src/hicn/config/controlSetStrategy.c @@ -45,8 +45,7 @@ static const char *_commandSetStrategyHelp = "help set strategy"; static const char *_commandSetStrategyOptions[LAST_STRATEGY_VALUE] = { "loadbalancer", "random", - "random_per_dash_segment", - "loadbalancer_with_delay", + "low_latency", }; // ==================================================== @@ -151,8 +150,7 @@ static CommandReturn _controlSetStrategy_HelpExecute(CommandParser *parser, printf("available strategies:\n"); printf(" random\n"); printf(" loadbalancer\n"); - printf(" random_per_dash_segment\n"); - printf(" loadbalancer_with_delay\n"); + printf(" low_latency\n"); printf("\n"); return CommandReturn_Success; } diff --git a/hicn-light/src/hicn/core/connection.c b/hicn-light/src/hicn/core/connection.c index c1d143f70..c2ac71a5f 100644 --- a/hicn-light/src/hicn/core/connection.c +++ b/hicn-light/src/hicn/core/connection.c @@ -38,11 +38,7 @@ struct connection { unsigned refCount; - bool probing_active; - unsigned probing_interval; unsigned counter; - Ticks last_sent; - Ticks delay; bool wldrAutoStart; // if true, wldr can be set automatically // by default this value is set to true. @@ -66,13 +62,9 @@ Connection *connection_Create(IoOperations *ops) { conn->ops = ops; conn->refCount = 1; conn->wldr = NULL; - conn->probing_active = false; conn->wldrAutoStart = true; - conn->probing_interval = 0; conn->counter = 0; - conn->last_sent = 0; - conn->delay = INT_MAX; /* By default, a connection will aim at the UP state */ connection_SetAdminState(conn, CONNECTION_STATE_UP); @@ -138,19 +130,6 @@ bool connection_SendIOVBuffer(const Connection *conn, struct iovec *msg, return ioOperations_SendIOVBuffer(conn->ops, msg, size); } -static void _sendProbe(Connection *conn, unsigned probeType, uint8_t *message) { - parcAssertNotNull(conn, "Parameter conn must be non-null"); - - if (probeType == PACKET_TYPE_PROBE_REQUEST) { - Ticks now = ioOperations_SendProbe(conn->ops, probeType, message); - if (now != 0) { - conn->last_sent = now; - } - } else { - ioOperations_SendProbe(conn->ops, probeType, message); - } -} - bool connection_SendBuffer(const Connection *conn, u8 * buffer, size_t length) { struct iovec iov[1]; @@ -159,33 +138,20 @@ bool connection_SendBuffer(const Connection *conn, u8 * buffer, size_t length) return connection_SendIOVBuffer(conn, iov, 1); } -void connection_Probe(Connection *conn) { - _sendProbe(conn, PACKET_TYPE_PROBE_REQUEST, NULL); +void connection_Probe(Connection *conn, uint8_t * probe) { + ioOperations_SendProbe(conn->ops, probe); } -void connection_HandleProbe(Connection *conn, uint8_t *probe, - Ticks actualTime) { +void connection_HandleProbe(Connection *conn, uint8_t *probe){ parcAssertNotNull(conn, "Parameter conn must be non-null"); parcAssertNotNull(probe, "Parameter pkt must be non-null"); - uint8_t probeType = messageHandler_GetProbePacketType(probe); - if (probeType == PACKET_TYPE_PROBE_REQUEST) { - _sendProbe(conn, PACKET_TYPE_PROBE_REPLY, probe); - } else if (probeType == PACKET_TYPE_PROBE_REPLY) { - Ticks delay = actualTime - conn->last_sent; - if (delay == 0) { - delay = 1; - } - if (delay < conn->delay) { - conn->delay = delay; - } - } else { - printf("receivde unkwon probe type\n"); + if(messageHandler_IsInterest(probe)){ + messageHandler_CreateProbeReply(probe, HF_INET6_TCP); + ioOperations_SendProbe(conn->ops, probe); } } -uint64_t connection_GetDelay(Connection *conn) { return (uint64_t)conn->delay; } - IoOperations *connection_GetIoOperations(const Connection *conn) { return conn->ops; } diff --git a/hicn-light/src/hicn/core/connection.h b/hicn-light/src/hicn/core/connection.h index d0d093064..b6513ea1a 100644 --- a/hicn-light/src/hicn/core/connection.h +++ b/hicn-light/src/hicn/core/connection.h @@ -46,10 +46,6 @@ typedef enum { #include <hicn/policy.h> #endif /* WITH_POLICY */ -// packet types for probing -#define PACKET_TYPE_PROBE_REQUEST 5 -#define PACKET_TYPE_PROBE_REPLY 6 - struct connection; typedef struct connection Connection; @@ -156,12 +152,9 @@ const void *connection_Class(const Connection *conn); bool connection_ReSend(const Connection *conn, Message *message, bool notification); -void connection_Probe(Connection *conn); - -void connection_HandleProbe(Connection *conn, uint8_t *message, - Ticks actualTime); +void connection_Probe(Connection *conn, uint8_t *probe); -uint64_t connection_GetDelay(Connection *conn); +void connection_HandleProbe(Connection *conn, uint8_t *message); void connection_AllowWldrAutoStart(Connection *conn, bool allow); diff --git a/hicn-light/src/hicn/core/messageHandler.h b/hicn-light/src/hicn/core/messageHandler.h index e2f0140e5..0bf6bebbe 100644 --- a/hicn-light/src/hicn/core/messageHandler.h +++ b/hicn-light/src/hicn/core/messageHandler.h @@ -63,6 +63,8 @@ #define CONNECTION_ID_UNDEFINED -1 +#define BFD_PORT 3784 + static inline uint8_t messageHandler_GetIPPacketType(const uint8_t *message) { return HICN_IP_VERSION(message); } @@ -491,23 +493,6 @@ static inline bool messageHandler_HasWldr(const uint8_t *message) { return false; } -static inline uint8_t messageHandler_GetProbePacketType( - const uint8_t *message) { - const uint8_t *icmp_ptr; - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - icmp_ptr = message + IPV6_HDRLEN; - break; - case IPv4_TYPE: - icmp_ptr = message + IPV4_HDRLEN; - break; - default: - return 0; - } - - return ((_icmp_header_t *)icmp_ptr)->code; -} - static inline uint32_t messageHandler_GetPathLabel(const uint8_t *message) { if (!messageHandler_IsTCP(message)) return 0; @@ -707,31 +692,77 @@ static inline void messageHandler_SetWldrNotification(uint8_t *notification, } } -static inline void messageHandler_SetProbePacket(uint8_t *message, - uint8_t probeType, - struct in6_addr *src, - struct in6_addr *dst) { - hicn_header_t *h = (hicn_header_t *)message; - *h = (hicn_header_t){ - .v6 = { - .ip = - { - .version_class_flow = - htonl((IPV6_DEFAULT_VERSION << 28) | - (IPV6_DEFAULT_TRAFFIC_CLASS << 20) | - (IPV6_DEFAULT_FLOW_LABEL & 0xfffff)), - .len = htons(ICMP_HDRLEN), - .nxt = IPPROTO_ICMPV6, - .hlim = 5, // this should be 1, but ... just to be safe - }, - .icmp = - { - .type = ICMP_LB_TYPE, - .code = probeType, - }, - }}; - messageHandler_SetSource_IPv6(message, src); - messageHandler_SetDestination_IPv6(message, dst); +static inline uint8_t * messageHandler_CreateProbePacket(hicn_format_t format, + uint32_t probe_lifetime){ + size_t header_length; + hicn_packet_get_header_length_from_format(format, &header_length); + + uint8_t *pkt = parcMemory_AllocateAndClear(header_length); + + hicn_packet_init_header(format, (hicn_header_t *) pkt); + + hicn_packet_set_dst_port((hicn_header_t *) pkt, BFD_PORT); + hicn_interest_set_lifetime ((hicn_header_t *) pkt, probe_lifetime); + + return pkt; +} + +static inline void messageHandler_CreateProbeReply(uint8_t * probe, + hicn_format_t format){ + + hicn_name_t probe_name; + hicn_interest_get_name (format, + (const hicn_header_t *) probe, &probe_name); + ip_address_t probe_locator; + hicn_interest_get_locator (format, + (const hicn_header_t *) probe, &probe_locator); + + uint16_t src_prt; + uint16_t dst_prt; + hicn_packet_get_src_port((const hicn_header_t *) probe, &src_prt); + hicn_packet_get_dst_port((const hicn_header_t *) probe, &dst_prt); + hicn_packet_set_src_port((hicn_header_t *) probe, dst_prt); + hicn_packet_set_dst_port((hicn_header_t *) probe, src_prt); + + hicn_data_set_name (format, (hicn_header_t *) probe, &probe_name); + hicn_data_set_locator (format, (hicn_header_t *) probe, &probe_locator); + hicn_data_set_expiry_time ((hicn_header_t *) probe, 0); +} + +static inline hicn_name_t * messageHandler_CreateProbeName(const ip_prefix_t *address){ + hicn_name_t * name = parcMemory_AllocateAndClear(sizeof(hicn_name_t)); + hicn_name_create_from_ip_prefix(address, 0, name); + return name; +} + +static inline void messageHandler_SetProbeName(uint8_t * probe, hicn_format_t format, + hicn_name_t * name, uint32_t seq){ + hicn_name_set_seq_number (name, seq); + hicn_interest_set_name(format, (hicn_header_t *) probe, name); +} + +static inline bool messageHandler_IsAProbe(const uint8_t *packet){ + uint16_t src_prt; + uint16_t dst_prt; + hicn_packet_get_src_port ((const hicn_header_t *) packet, &src_prt); + hicn_packet_get_dst_port ((const hicn_header_t *) packet, &dst_prt); + + if(dst_prt == BFD_PORT){ + //interest probe + return true; + } + + if(src_prt == BFD_PORT){ + //data (could be a probe) + uint32_t expiry_time; + hicn_data_get_expiry_time ((const hicn_header_t *) packet, &expiry_time); + if(expiry_time == 0){ + //this is a probe + return true; + } + } + + return false; } #endif // Metis_metis_MessageHandler diff --git a/hicn-light/src/hicn/io/hicnConnection.c b/hicn-light/src/hicn/io/hicnConnection.c index e35454438..646cea990 100644 --- a/hicn-light/src/hicn/io/hicnConnection.c +++ b/hicn-light/src/hicn/io/hicnConnection.c @@ -56,18 +56,6 @@ typedef struct hicn_state { struct sockaddr *localAddress; socklen_t localAddressLength; - // this address contains one of the content names reachable - // throught the connection peer. We need this address beacuse it is - // the only way we have to conntact the next hop, since the main tun - // does not have address. Notice that a connection that sends probes - // is a connection that sends interest. In a "data" connection this - // value will remain NULL. We refresh the content address every time - // we send a probe, in this way we don't need to waste to much time in - // copy the address, but we can also react to the routing changes - struct sockaddr *probeDestAddress; - socklen_t probeDestAddressLength; - bool refreshProbeDestAddress; - bool isLocal; bool isUp; unsigned id; @@ -94,8 +82,7 @@ static bool _isUp(const IoOperations *ops); static bool _isLocal(const IoOperations *ops); static void _destroy(IoOperations **opsPtr); static list_connections_type _getConnectionType(const IoOperations *ops); -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message); +static void _sendProbe(IoOperations *ops, uint8_t *message); static connection_state_t _getState(const IoOperations *ops); static void _setState(IoOperations *ops, connection_state_t state); static connection_state_t _getAdminState(const IoOperations *ops); @@ -147,8 +134,6 @@ static IoOperations _template = { static void _setConnectionState(_HicnState *Hicn, bool isUp); static bool _saveSockaddr(_HicnState *hicnConnState, const AddressPair *pair); -static void _refreshProbeDestAddress(_HicnState *hicnConnState, - const uint8_t *message); IoOperations *hicnConnection_Create(Forwarder *forwarder, const char * interfaceName, int fd, const AddressPair *pair, bool isLocal) { @@ -225,8 +210,6 @@ static void _destroy(IoOperations **opsPtr) { addressPair_Release(&hicnConnState->addressPair); parcMemory_Deallocate((void **)&(hicnConnState->peerAddress)); parcMemory_Deallocate((void **)&(hicnConnState->localAddress)); - if (hicnConnState->probeDestAddress != NULL) - parcMemory_Deallocate((void **)&(hicnConnState->probeDestAddress)); messenger_Send( forwarder_GetMessenger(hicnConnState->forwarder), @@ -328,12 +311,6 @@ static bool _send(IoOperations *ops, const Address *dummy, Message *message) { &(((struct sockaddr_in *)hicnConnState->localAddress) ->sin_addr.s_addr)); } - - // only in this case we may need to set the probeDestAddress - if (hicnConnState->refreshProbeDestAddress) { - _refreshProbeDestAddress(hicnConnState, message_FixedHeader(message)); - } - } else if (message_GetType(message) == MessagePacketType_WldrNotification) { // here we don't need to do anything for now } else { @@ -395,64 +372,31 @@ static list_connections_type _getConnectionType(const IoOperations *ops) { return CONN_HICN; } -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message) { +static void _sendProbe(IoOperations *ops, uint8_t *message) { parcAssertNotNull(ops, "Parameter ops must be non-null"); - _HicnState *hicnConnState = (_HicnState *)ioOperations_GetClosure(ops); - - if ((hicnConnState->peerAddressLength == sizeof(struct sockaddr_in)) || - (hicnConnState->localAddressLength == sizeof(struct sockaddr_in))) - return false; - - if (hicnConnState->probeDestAddress == NULL && - probeType == PACKET_TYPE_PROBE_REPLY) { - uint8_t *pkt = parcMemory_AllocateAndClear( - messageHandler_GetICMPPacketSize(IPv6_TYPE)); - messageHandler_SetProbePacket( - pkt, probeType, - (struct in6_addr *)messageHandler_GetDestination(message), - (struct in6_addr *)messageHandler_GetSource(message)); - - ssize_t writeLength = write(hicnConnState->hicnListenerSocket, pkt, - messageHandler_GetICMPPacketSize(IPv6_TYPE)); - parcMemory_Deallocate((void **)&pkt); + _HicnState *hicnConnState = (_HicnState *)ioOperations_GetClosure(ops); - if (writeLength < 0) { - return 0; + if(messageHandler_IsInterest(message)){// + // this is an interest packet. We need to put the local address in the + // source field + if (messageHandler_GetIPPacketType(message) == IPv6_TYPE) { + messageHandler_SetSource_IPv6(message, + &((struct sockaddr_in6 *)hicnConnState->localAddress)->sin6_addr); + } else { + messageHandler_SetSource_IPv4(message, + &(((struct sockaddr_in *)hicnConnState->localAddress) + ->sin_addr.s_addr)); } + }//if is a data packet the packet is already set (see + //messageHandler_CreateProbeReply) - } else if (hicnConnState->probeDestAddress != NULL && - probeType == PACKET_TYPE_PROBE_REQUEST) { - hicnConnState->refreshProbeDestAddress = true; - - uint8_t *pkt = parcMemory_AllocateAndClear( - messageHandler_GetICMPPacketSize(IPv6_TYPE)); - messageHandler_SetProbePacket( - pkt, probeType, - &((struct sockaddr_in6 *)hicnConnState->localAddress)->sin6_addr, - &((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_addr); - - ssize_t writeLength = write(hicnConnState->hicnListenerSocket, pkt, - messageHandler_GetICMPPacketSize(IPv6_TYPE)); - - parcMemory_Deallocate((void **)&pkt); + ssize_t writeLength = write(hicnConnState->hicnListenerSocket, message, + messageHandler_GetTotalPacketLength(message)); - if (writeLength < 0) { - return 0; - } - - } else { - if (hicnConnState->probeDestAddress == NULL && - probeType == PACKET_TYPE_PROBE_REQUEST) { - // this happen for the first probe - hicnConnState->refreshProbeDestAddress = true; - } - // do nothing - return 0; + if (writeLength < 0) { + return; } - - return forwarder_GetTicks(hicnConnState->forwarder); } // ================================================================= @@ -481,11 +425,6 @@ static bool _saveSockaddr(_HicnState *hicnConnState, const AddressPair *pair) { addressGetInet(localAddress, (struct sockaddr_in *)hicnConnState->localAddress); hicnConnState->localAddressLength = (socklen_t)bytes; - - hicnConnState->probeDestAddress = NULL; - hicnConnState->probeDestAddressLength = (socklen_t)bytes; - hicnConnState->refreshProbeDestAddress = false; - success = true; break; } @@ -507,11 +446,6 @@ static bool _saveSockaddr(_HicnState *hicnConnState, const AddressPair *pair) { addressGetInet6(localAddress, (struct sockaddr_in6 *)hicnConnState->localAddress); hicnConnState->localAddressLength = (socklen_t)bytes; - - hicnConnState->probeDestAddress = NULL; - hicnConnState->probeDestAddressLength = (socklen_t)bytes; - hicnConnState->refreshProbeDestAddress = false; - success = true; break; } @@ -529,31 +463,6 @@ static bool _saveSockaddr(_HicnState *hicnConnState, const AddressPair *pair) { return success; } -static void _refreshProbeDestAddress(_HicnState *hicnConnState, - const uint8_t *message) { - if ((hicnConnState->peerAddressLength == sizeof(struct sockaddr_in)) || - (hicnConnState->localAddressLength == sizeof(struct sockaddr_in))) - return; - - if (hicnConnState->probeDestAddress == NULL) { - hicnConnState->probeDestAddress = - parcMemory_AllocateAndClear(sizeof(struct sockaddr_in6)); - parcAssertNotNull(hicnConnState->probeDestAddress, - "parcMemory_Allocate(%zu) returned NULL", - sizeof(struct sockaddr_in6)); - } - - ((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_family = - AF_INET6; - ((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_port = - htons(1234); - ((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_scope_id = 0; - ((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_flowinfo = 0; - ((struct sockaddr_in6 *)hicnConnState->probeDestAddress)->sin6_addr = - *((struct in6_addr *)messageHandler_GetDestination(message)); - hicnConnState->refreshProbeDestAddress = false; -} - static void _setConnectionState(_HicnState *hicnConnState, bool isUp) { parcAssertNotNull(hicnConnState, "Parameter HICN must be non-null"); diff --git a/hicn-light/src/hicn/io/hicnListener.c b/hicn-light/src/hicn/io/hicnListener.c index 5a47982ff..bc49f4cee 100644 --- a/hicn-light/src/hicn/io/hicnListener.c +++ b/hicn-light/src/hicn/io/hicnListener.c @@ -85,7 +85,6 @@ static const Connection * _lookupConnection(ListenerOps * listener, const Addres static Message *_readMessage(ListenerOps * listener, int fd, uint8_t *msgBuffer); static void _hicnListener_readcb(int fd, PARCEventType what, void *listener_void); static Address *_createAddressFromPacket(uint8_t *msgBuffer); -static void _handleProbeMessage(ListenerOps * listener, uint8_t *msgBuffer); static void _handleWldrNotification(ListenerOps *listener, uint8_t *msgBuffer); static void _readFrameToDiscard(HicnListener *hicn, int fd); @@ -182,8 +181,6 @@ static Message *_readMessage(ListenerOps * listener, int fd, uint8_t *msgBuffer) } } else if (messageHandler_IsWldrNotification(msgBuffer)) { _handleWldrNotification(listener, msgBuffer); - } else if (messageHandler_IsLoadBalancerProbe(msgBuffer)) { - _handleProbeMessage(listener, msgBuffer); } else { messageHandler_handleHooks(hicn->forwarder, msgBuffer, listener, fd, NULL); parcMemory_Deallocate((void **)&msgBuffer); @@ -639,29 +636,6 @@ static Address *_createAddressFromPacket(uint8_t *msgBuffer) { return packetAddr; } -static void _handleProbeMessage(ListenerOps * listener, uint8_t *msgBuffer) { - HicnListener * hicn = (HicnListener *)listener->context; - - Address *packetAddr = _createAddressFromPacket(msgBuffer); - AddressPair * pair = addressPair_Create(packetAddr, /* dummy */ hicn->localAddress); - - if (!packetAddr) - goto DROP; - - // we drop all the probes for a connection that does not exists - const Connection *conn = _lookupConnection(listener, pair); - if (!conn) - goto DROP; - - connection_HandleProbe((Connection *)conn, msgBuffer, - forwarder_GetTicks(hicn->forwarder)); - -DROP: - addressPair_Release(&pair); - addressDestroy(&packetAddr); - parcMemory_Deallocate((void **)&msgBuffer); -} - static void _handleWldrNotification(ListenerOps *listener, uint8_t *msgBuffer) { HicnListener * hicn = (HicnListener *)listener->context; @@ -693,8 +667,3 @@ static void _handleWldrNotification(ListenerOps *listener, uint8_t *msgBuffer) { message_Release(&message); } - - - - - diff --git a/hicn-light/src/hicn/io/ioOperations.c b/hicn-light/src/hicn/io/ioOperations.c index 336e9f12e..0087b320a 100644 --- a/hicn-light/src/hicn/io/ioOperations.c +++ b/hicn-light/src/hicn/io/ioOperations.c @@ -64,9 +64,8 @@ list_connections_type ioOperations_GetConnectionType(const IoOperations *ops) { return ops->getConnectionType(ops); } -Ticks ioOperations_SendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message) { - return ops->sendProbe(ops, probeType, message); +void ioOperations_SendProbe(IoOperations *ops, uint8_t *message) { + ops->sendProbe(ops, message); } diff --git a/hicn-light/src/hicn/io/ioOperations.h b/hicn-light/src/hicn/io/ioOperations.h index ee8720e77..5d9befac3 100644 --- a/hicn-light/src/hicn/io/ioOperations.h +++ b/hicn-light/src/hicn/io/ioOperations.h @@ -84,7 +84,7 @@ struct io_ops { void (*destroy)(IoOperations **opsPtr); const void *(*class)(const IoOperations *ops); list_connections_type (*getConnectionType)(const IoOperations *ops); - Ticks (*sendProbe)(IoOperations *ops, unsigned probeType, uint8_t *message); + void (*sendProbe)(IoOperations *ops, uint8_t *message); connection_state_t (*getState)(const IoOperations *ops); void (*setState)(IoOperations *ops, connection_state_t state); connection_state_t (*getAdminState)(const IoOperations *ops); @@ -382,8 +382,7 @@ const void *ioOperations_Class(const IoOperations *ops); */ list_connections_type ioOperations_GetConnectionType(const IoOperations *ops); -Ticks ioOperations_SendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message); +void ioOperations_SendProbe(IoOperations *ops, uint8_t *message); /** diff --git a/hicn-light/src/hicn/io/streamConnection.c b/hicn-light/src/hicn/io/streamConnection.c index 27ec45d48..00298d1b0 100644 --- a/hicn-light/src/hicn/io/streamConnection.c +++ b/hicn-light/src/hicn/io/streamConnection.c @@ -88,8 +88,7 @@ static void _streamConnection_DestroyOperations(IoOperations **opsPtr); static void _setConnectionState(_StreamState *stream, bool isUp); static list_connections_type _streamConnection_GetConnectionType( const IoOperations *ops); -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message); +static void _sendProbe(IoOperations *ops, uint8_t *message); static connection_state_t _streamConnection_getState(const IoOperations *ops); static void _streamConnection_setState(IoOperations *ops, connection_state_t state); static connection_state_t _streamConnection_getAdminState(const IoOperations *ops); @@ -437,10 +436,8 @@ list_connections_type _streamConnection_GetConnectionType( return CONN_TCP; } -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message) { +static void _sendProbe(IoOperations *ops, uint8_t *message) { // we don't need to implemet this here, it is a local connection - return 0; } // ================================================================= diff --git a/hicn-light/src/hicn/io/udpConnection.c b/hicn-light/src/hicn/io/udpConnection.c index 4e29eba7d..b22b1227f 100644 --- a/hicn-light/src/hicn/io/udpConnection.c +++ b/hicn-light/src/hicn/io/udpConnection.c @@ -79,8 +79,7 @@ static bool _isUp(const IoOperations *ops); static bool _isLocal(const IoOperations *ops); static void _destroy(IoOperations **opsPtr); static list_connections_type _getConnectionType(const IoOperations *ops); -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message); +static void _sendProbe(IoOperations *ops, uint8_t *message); static connection_state_t _getState(const IoOperations *ops); static void _setState(IoOperations *ops, connection_state_t state); static connection_state_t _getAdminState(const IoOperations *ops); @@ -350,10 +349,22 @@ static list_connections_type _getConnectionType(const IoOperations *ops) { return CONN_UDP; } -static Ticks _sendProbe(IoOperations *ops, unsigned probeType, - uint8_t *message) { - //TODO - return 0; +static void _sendProbe(IoOperations *ops, uint8_t *message) { + parcAssertNotNull(ops, "Parameter ops must be non-null"); + parcAssertNotNull(message, "Parameter message must be non-null"); + _UdpState *udpConnState = (_UdpState *)ioOperations_GetClosure(ops); + + if(udpConnState->isLocal) + return; + + ssize_t writeLength = + sendto(udpConnState->udpListenerSocket, message, + messageHandler_GetTotalPacketLength(message), 0, udpConnState->peerAddress, + udpConnState->peerAddressLength); + + if (writeLength < 0) { + return; + } } // ================================================================= diff --git a/hicn-light/src/hicn/io/udpListener.c b/hicn-light/src/hicn/io/udpListener.c index ebb24022e..21b4f6190 100644 --- a/hicn-light/src/hicn/io/udpListener.c +++ b/hicn-light/src/hicn/io/udpListener.c @@ -476,11 +476,6 @@ static unsigned _createNewConnection(ListenerOps * listener, int fd, return connid; } -static void _handleProbeMessage(UdpListener *udp, uint8_t *msgBuffer) { - // TODO - parcMemory_Deallocate((void **)&msgBuffer); -} - static void _handleWldrNotification(UdpListener *udp, unsigned connId, uint8_t *msgBuffer) { const Connection *conn = connectionTable_FindById( @@ -547,16 +542,8 @@ static Message *_readMessage(ListenerOps * listener, int fd, } else if (messageHandler_IsWldrNotification(packet)) { *processed = true; _handleWldrNotification(udp, connid, packet); - } else if (messageHandler_IsLoadBalancerProbe(packet)) { - *processed = true; - _handleProbeMessage(udp, packet); } else { -#if 0 - if (!foundConnection) - connid = _createNewConnection(listener, fd, pair); -#endif - *processed = messageHandler_handleHooks(udp->forwarder, packet, listener, fd, pair); } diff --git a/hicn-light/src/hicn/processor/fib.c b/hicn-light/src/hicn/processor/fib.c index c67bc6773..8822134fe 100644 --- a/hicn-light/src/hicn/processor/fib.c +++ b/hicn-light/src/hicn/processor/fib.c @@ -200,8 +200,10 @@ void fib_Add(FIB *fib, FibEntry *entry) { nameBitvector_clear(name_GetContentName(inner_prefix), match_len); name_setLen(inner_prefix, match_len); - FibEntry * inner_entry = fibEntry_Create(inner_prefix, SET_STRATEGY_LOADBALANCER, - fib->forwarder); + //this is an inner node, we don't want an acctive strategy + //like low_latency that sends probes in this node + FibEntry * inner_entry = fibEntry_Create(inner_prefix, + SET_STRATEGY_LOADBALANCER, fib->forwarder); FibNode * inner_node = _createNode(NULL, NULL, inner_entry, false); FibNode * new_node = _createNode(NULL, NULL, entry, true); diff --git a/hicn-light/src/hicn/processor/fib.h b/hicn-light/src/hicn/processor/fib.h index 7507bb85c..ef9e121b8 100644 --- a/hicn-light/src/hicn/processor/fib.h +++ b/hicn-light/src/hicn/processor/fib.h @@ -23,7 +23,7 @@ struct fib; typedef struct fib FIB; -FIB *fib_Create(); +FIB *fib_Create(Forwarder *forwarder); void fib_Destroy(FIB **fibPtr); diff --git a/hicn-light/src/hicn/processor/fibEntry.c b/hicn-light/src/hicn/processor/fibEntry.c index fe32ada8d..be7278987 100644 --- a/hicn-light/src/hicn/processor/fibEntry.c +++ b/hicn-light/src/hicn/processor/fibEntry.c @@ -22,9 +22,8 @@ #include <hicn/core/nameBitvector.h> #include <hicn/strategies/loadBalancer.h> -#include <hicn/strategies/loadBalancerWithPD.h> +#include <hicn/strategies/lowLatency.h> #include <hicn/strategies/rnd.h> -#include <hicn/strategies/rndSegment.h> #include <hicn/strategies/strategyImpl.h> #ifdef WITH_MAPME #include <parc/algol/parc_HashMap.h> @@ -80,34 +79,23 @@ FibEntry *fibEntry_Create(Name *name, strategy_type fwdStrategy) { sizeof(FibEntry)); fibEntry->name = name_Acquire(name); - if (fwdStrategy) { - switch (fwdStrategy) { - case SET_STRATEGY_LOADBALANCER: - fibEntry->fwdStrategy = strategyLoadBalancer_Create(); - break; - - case SET_STRATEGY_RANDOM: - fibEntry->fwdStrategy = strategyRnd_Create(); - break; - - case SET_STRATEGY_RANDOM_PER_DASH_SEGMENT: - fibEntry->fwdStrategy = strategyRndSegment_Create(); - break; - - case SET_STRATEGY_LOADBALANCER_WITH_DELAY: - fibEntry->fwdStrategy = strategyLoadBalancerWithPD_Create(); - break; - - default: - // LB is the default strategy - fibEntry->fwdStrategy = strategyLoadBalancer_Create(); - // the LB strategy is the default one - // other strategies can be set using the appropiate function - break; - } + switch (fwdStrategy) { + case SET_STRATEGY_LOADBALANCER: + fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + break; - } else { - fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + case SET_STRATEGY_RANDOM: + fibEntry->fwdStrategy = strategyRnd_Create(); + + case SET_STRATEGY_LOW_LATENCY: + fibEntry->fwdStrategy = strategyLowLatency_Create(); + break; + + default: + // LB is the default strategy + fwdStrategy = SET_STRATEGY_LOADBALANCER; + fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + break; } fibEntry->refcount = 1; @@ -124,6 +112,10 @@ FibEntry *fibEntry_Create(Name *name, strategy_type fwdStrategy) { fibEntry->policy_counters = POLICY_COUNTERS_NONE; #endif /* WITH_POLICY */ + if(fwdStrategy == SET_STRATEGY_LOW_LATENCY){ + strategyLowLatency_SetStrategy(fibEntry->fwdStrategy, + fibEntry->forwarder, fibEntry); + } return fibEntry; } @@ -166,20 +158,20 @@ void fibEntry_SetStrategy(FibEntry *fibEntry, strategy_type strategy) { fwdStrategyImpl = strategyRnd_Create(); break; - case SET_STRATEGY_RANDOM_PER_DASH_SEGMENT: - fwdStrategyImpl = strategyRndSegment_Create(); - break; - - case SET_STRATEGY_LOADBALANCER_WITH_DELAY: - fwdStrategyImpl = strategyLoadBalancerWithPD_Create(); + case SET_STRATEGY_LOW_LATENCY: + fwdStrategyImpl = strategyLowLatency_Create(); break; default: - // LB is the defualt strategy + // LB is the default strategy + strategy = SET_STRATEGY_LOADBALANCER; fwdStrategyImpl = strategyLoadBalancer_Create(); - // the LB strategy is the default one - // other strategies can be set using the appropiate function break; + } + + if(strategy == SET_STRATEGY_LOW_LATENCY){ + strategyLowLatency_SetStrategy(fwdStrategyImpl, + fibEntry->forwarder, fibEntry); } const NumberSet *nexthops = fibEntry_GetNexthops(fibEntry); @@ -613,7 +605,9 @@ void fibEntry_ReceiveObjectMessage(FibEntry *fibEntry, void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, #endif /* WITH_POLICY */ const NumberSet *egressId, - const Message *objectMessage, Ticks rtt) { + const Message *objectMessage, + Ticks pitEntryCreation, + Ticks objReception) { parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); #ifdef WITH_POLICY @@ -622,6 +616,7 @@ void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, /* Update statistic counters : */ size_t msg_size = message_Length(objectMessage); + Ticks rtt = objReception - pitEntryCreation; for (unsigned i = 0; i < numberSet_Length(egressId); i++) { unsigned conn_id = numberSet_GetItem(egressId, i); @@ -666,7 +661,7 @@ void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, #endif /* WITH_POLICY */ fibEntry->fwdStrategy->receiveObject(fibEntry->fwdStrategy, egressId, - objectMessage, rtt); + objectMessage, pitEntryCreation, objReception); } #ifdef WITH_POLICY diff --git a/hicn-light/src/hicn/processor/fibEntry.h b/hicn-light/src/hicn/processor/fibEntry.h index 7ec771b4c..1bd917bc2 100644 --- a/hicn-light/src/hicn/processor/fibEntry.h +++ b/hicn-light/src/hicn/processor/fibEntry.h @@ -110,7 +110,9 @@ void fibEntry_ReceiveObjectMessage(FibEntry *fibEntry, void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, #endif /* WITH_POLICY */ const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); + const Message *objectMessage, + Ticks pitEntryCreation, + Ticks objReception); #ifdef WITH_POLICY policy_t fibEntry_GetPolicy(const FibEntry *fibEntry); @@ -125,16 +127,10 @@ void fibEntry_OnTimeout(FibEntry *fibEntry, const NumberSet *egressId); const NumberSet *fibEntry_GetNexthopsFromForwardingStrategy( FibEntry *fibEntry, const Message *interestMessage, bool is_retransmission); -void fibEntry_ReceiveObjectMessage(FibEntry *fibEntry, - const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); #else void fibEntry_OnTimeout(const FibEntry *fibEntry, const NumberSet *egressId); const NumberSet *fibEntry_GetNexthopsFromForwardingStrategy( const FibEntry *fibEntry, const Message *interestMessage); -void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, - const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); #endif /* WITH_POLICY */ diff --git a/hicn-light/src/hicn/processor/messageProcessor.c b/hicn-light/src/hicn/processor/messageProcessor.c index c989f8cb6..e38a3d558 100644 --- a/hicn-light/src/hicn/processor/messageProcessor.c +++ b/hicn-light/src/hicn/processor/messageProcessor.c @@ -34,9 +34,8 @@ #include <hicn/content_store/contentStoreLRU.h> #include <hicn/strategies/loadBalancer.h> -#include <hicn/strategies/loadBalancerWithPD.h> +#include <hicn/strategies/lowLatency.h> #include <hicn/strategies/rnd.h> -#include <hicn/strategies/rndSegment.h> #include <hicn/strategies/strategyImpl.h> #include <hicn/io/streamConnection.h> @@ -48,6 +47,7 @@ #include <hicn/utils/utils.h> #include <hicn/utils/address.h> +#include <hicn/core/messageHandler.h> #ifdef WITH_POLICY #define STATS_INTERVAL 1000 /* ms */ @@ -160,7 +160,7 @@ MessageProcessor *messageProcessor_Create(Forwarder *forwarder) { processor->logger = logger_Acquire(forwarder_GetLogger(forwarder)); processor->pit = pitStandard_Create(forwarder); - processor->fib = fib_Create(); + processor->fib = fib_Create(forwarder); if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug)) { @@ -304,18 +304,13 @@ bool messageProcessor_AddOrUpdateRoute(MessageProcessor *processor, control->addressType, &control->address, &control->len); strategy_type fwdStrategy = configuration_GetForwardingStrategy(config, prefixStr); - if (fwdStrategy == LAST_STRATEGY_VALUE) { - fwdStrategy = SET_STRATEGY_LOADBALANCER; - } Name *prefix = name_CreateFromAddress(control->addressType, control->address, control->len); FibEntry *entry = fib_Contains(processor->fib, prefix); - bool newEntry = false; if (entry != NULL) { fibEntry_AddNexthop(entry, ifidx); } else { - newEntry = true; #ifdef WITH_POLICY entry = fibEntry_Create(prefix, fwdStrategy, processor->forwarder); #else @@ -328,14 +323,6 @@ bool messageProcessor_AddOrUpdateRoute(MessageProcessor *processor, free(prefixStr); name_Release(&prefix); - /* For policy implementation, we need access to the ConnectionTable in all - * Forwarding Strategies, so it is setup during FIB Entry creation */ - if (newEntry && (fwdStrategy == SET_STRATEGY_LOADBALANCER_WITH_DELAY)) { - strategyLoadBalancerWithPD_SetConnectionTable( - fibEntry_GetFwdStrategy(entry), - forwarder_GetConnectionTable(processor->forwarder)); - } - return true; } @@ -365,9 +352,6 @@ bool messageProcessor_AddOrUpdatePolicy(MessageProcessor *processor, if (!entry) { strategy_type fwdStrategy = configuration_GetForwardingStrategy(config, prefixStr); - if (fwdStrategy == LAST_STRATEGY_VALUE) { - fwdStrategy = SET_STRATEGY_LOADBALANCER; - } entry = fibEntry_Create(prefix, fwdStrategy, processor->forwarder); fib_Add(processor->fib, entry); } @@ -407,11 +391,6 @@ void processor_SetStrategy(MessageProcessor *processor, Name *prefix, FibEntry *entry = fib_Contains(processor->fib, prefix); if (entry != NULL) { fibEntry_SetStrategy(entry, strategy); - if (strategy == SET_STRATEGY_LOADBALANCER_WITH_DELAY) { - strategyLoadBalancerWithPD_SetConnectionTable( - fibEntry_GetFwdStrategy(entry), - forwarder_GetConnectionTable(processor->forwarder)); - } } } @@ -572,6 +551,34 @@ static bool messageProcessor_ForwardViaFib(MessageProcessor *processor, return false; } + if(messageHandler_IsAProbe(message_FixedHeader(interestMessage))){ + bool reply_to_probe = false; + ConnectionTable * ct = forwarder_GetConnectionTable(processor->forwarder); + const NumberSet * nexthops = fibEntry_GetNexthops(fibEntry); + unsigned size = (unsigned) numberSet_Length(nexthops); + + for (unsigned i = 0; i < size; i++) { + unsigned nhop = numberSet_GetItem(nexthops, i); + Connection *conn = + (Connection *)connectionTable_FindById(ct, nhop); + if (!conn) + continue; + bool isLocal = connection_IsLocal(conn); + if(isLocal){ + Connection * replyConn = + (Connection *)connectionTable_FindById(ct, + message_GetIngressConnectionId(interestMessage)); + connection_HandleProbe(replyConn, + (uint8_t *) message_FixedHeader(interestMessage)); + reply_to_probe = true; + break; + } + } + if(reply_to_probe) + return false; + } + + PitEntry *pitEntry = pit_GetPitEntry(processor->pit, interestMessage); if (pitEntry == NULL) { return false; @@ -709,6 +716,20 @@ static void messageProcessor_ReceiveContentObject(MessageProcessor *processor, (void *)message, processor->stats.countDroppedNoReversePath); } + //if the packet is a probe we need to analyze it + if(messageHandler_IsAProbe(message_FixedHeader(message))){ + FibEntry *fibEntry = fib_MatchMessage(processor->fib, message); + if(fibEntry && + fibEntry_GetFwdStrategyType(fibEntry) == SET_STRATEGY_LOW_LATENCY){ + unsigned connid = message_GetIngressConnectionId(message); + NumberSet *outFace = numberSet_Create(); + numberSet_Add(outFace, connid); + fibEntry_ReceiveObjectMessage(fibEntry, outFace, message, 0, + forwarder_GetTicks(processor->forwarder)); + numberSet_Release(&(outFace)); + } + } + // we store the packets in the content store enven in the case where there // is no match in the PIT table in this way the applications can push the // content in the CS of the forwarder. We allow this only for local faces diff --git a/hicn-light/src/hicn/processor/pitStandard.c b/hicn-light/src/hicn/processor/pitStandard.c index edf0b5e98..d4961cdba 100644 --- a/hicn-light/src/hicn/processor/pitStandard.c +++ b/hicn-light/src/hicn/processor/pitStandard.c @@ -159,7 +159,6 @@ static PITVerdict _pitStandard_ReceiveInterest(PIT *generic, ") and reverse path, forwarding", (void *)interestMessage, pitEntry_GetExpiryTime(pitEntry)); } - #ifdef WITH_POLICY return PITVerdict_Retransmit; #else @@ -215,12 +214,10 @@ static NumberSet *_pitStandard_SatisfyInterest(PIT *generic, // PIT entry is not expired, use it FibEntry *fibEntry = pitEntry_GetFibEntry(pitEntry); if (fibEntry != NULL) { - // this is a rough estimation of the residual RTT - Ticks rtt = forwarder_GetTicks(pit->forwarder) - - pitEntry_GetCreationTime(pitEntry); fibEntry_ReceiveObjectMessage(fibEntry, pitEntry_GetEgressSet(pitEntry), objectMessage, - rtt); // need to implement RTT + forwarder_GetTicks(pit->forwarder), + pitEntry_GetCreationTime(pitEntry)); } const NumberSet *is = pitEntry_GetIngressSet(pitEntry); numberSet_AddSet(ingressSet, is); // with this we do a copy so we can diff --git a/hicn-light/src/hicn/strategies/CMakeLists.txt b/hicn-light/src/hicn/strategies/CMakeLists.txt index 7f0730b2f..400efcde9 100644 --- a/hicn-light/src/hicn/strategies/CMakeLists.txt +++ b/hicn-light/src/hicn/strategies/CMakeLists.txt @@ -16,20 +16,18 @@ 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}/lowLatency.h ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.h - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateWithPD.h + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateLowLatency.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}/lowLatency.c ${CMAKE_CURRENT_SOURCE_DIR}/nexthopState.c - ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateWithPD.c + ${CMAKE_CURRENT_SOURCE_DIR}/nexthopStateLowLatency.c ${CMAKE_CURRENT_SOURCE_DIR}/rnd.c - ${CMAKE_CURRENT_SOURCE_DIR}/rndSegment.c ) set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) diff --git a/hicn-light/src/hicn/strategies/loadBalancer.c b/hicn-light/src/hicn/strategies/loadBalancer.c index 35d64e763..878a58515 100644 --- a/hicn-light/src/hicn/strategies/loadBalancer.c +++ b/hicn-light/src/hicn/strategies/loadBalancer.c @@ -32,7 +32,8 @@ static void _strategyLoadBalancer_ReceiveObject(StrategyImpl *strategy, const NumberSet *egressId, const Message *objectMessage, - Ticks rtt); + Ticks pitEntryCreation, + Ticks objReception); static void _strategyLoadBalancer_OnTimeout(StrategyImpl *strategy, const NumberSet *egressId); static NumberSet *_strategyLoadBalancer_LookupNexthop( @@ -161,7 +162,8 @@ static unsigned _select_Nexthop(StrategyLoadBalancer *strategy) { static void _strategyLoadBalancer_ReceiveObject(StrategyImpl *strategy, const NumberSet *egressId, const Message *objectMessage, - Ticks rtt) { + Ticks pitEntryCreation, + Ticks objReception) { _strategyLoadBalancer_OnTimeout(strategy, egressId); } diff --git a/hicn-light/src/hicn/strategies/loadBalancerWithPD.c b/hicn-light/src/hicn/strategies/loadBalancerWithPD.c deleted file mode 100644 index dac759053..000000000 --- a/hicn-light/src/hicn/strategies/loadBalancerWithPD.c +++ /dev/null @@ -1,468 +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 <hicn/hicn-light/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 <hicn/strategies/loadBalancerWithPD.h> -#include <hicn/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, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif - const Message *interestMessage); -#ifndef WITH_POLICY -static NumberSet *_strategyLoadBalancerWithPD_ReturnNexthops( - StrategyImpl *strategy); -static unsigned _strategyLoadBalancerWithPD_CountNexthops( - StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ -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, -#ifndef WITH_POLICY - .returnNexthops = &_strategyLoadBalancerWithPD_ReturnNexthops, - .countNexthops = &_strategyLoadBalancerWithPD_CountNexthops, -#endif /* ! WITH_POLICY */ - .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; -#ifndef WITH_POLICY - NumberSet *nexthops; -#endif /* ! WITH_POLICY */ - const 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(); -#ifndef WITH_POLICY - strategy->nexthops = numberSet_Create(); -#endif /* ! WITH_POLICY */ - 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; -} - -#ifdef WITH_POLICY -static void _sendProbes(StrategyLoadBalancerWithPD *strategy, NumberSet * nexthops) { - unsigned size = (unsigned)numberSet_Length(nexthops); - for (unsigned i = 0; i < size; i++) { - unsigned nhop = numberSet_GetItem(nexthops, i); - Connection *conn = - (Connection *)connectionTable_FindById(strategy->connTable, nhop); - if (!conn) - continue; - - 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); - } -} -#else -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); - } - } -} -#endif /* WITH_POLICY */ - -#ifdef WITH_POLICY -static unsigned _select_Nexthop(StrategyLoadBalancerWithPD *strategy, NumberSet * nexthops) { - strategy->fwdPackets++; - if (strategy->toInit || strategy->fwdPackets == PROBE_FREQUENCY) { - strategy->toInit = false; - strategy->fwdPackets = 0; - _sendProbes(strategy, nexthops); - } - 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; -} -#else -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; -} -#endif /* WITH_POLICY */ - -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, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif - 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 { -#ifdef WITH_POLICY - out_connection = _select_Nexthop(lb, nexthops); -#else - out_connection = _select_Nexthop(lb); -#endif /* WITH_POLICY */ - } 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; -} - -#ifndef WITH_POLICY -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); -} -#endif /* WITH_POLICY */ - -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); -#ifndef WITH_POLICY - numberSet_Add(lb->nexthops, connectionId); -#endif /* ! WITH_POLICY */ - _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); -#ifndef WITH_POLICY - numberSet_Remove(lb->nexthops, connectionId); -#endif /* ! WITH_POLICY */ - _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)); -#ifndef WITH_POLICY - numberSet_Release(&(strategy->nexthops)); -#endif /* ! WITH_POLICY */ - - parcMemory_Deallocate((void **)&strategy); - parcMemory_Deallocate((void **)&impl); - *strategyPtr = NULL; -} diff --git a/hicn-light/src/hicn/strategies/loadBalancerWithPD.h b/hicn-light/src/hicn/strategies/loadBalancerWithPD.h deleted file mode 100644 index a6ad94ab8..000000000 --- a/hicn-light/src/hicn/strategies/loadBalancerWithPD.h +++ /dev/null @@ -1,31 +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 <hicn/strategies/strategyImpl.h> -#include <hicn/core/connectionTable.h> - -StrategyImpl *strategyLoadBalancerWithPD_Create(); - -void strategyLoadBalancerWithPD_SetConnectionTable(StrategyImpl *strategy, - ConnectionTable *connTable); -#endif // loadBalancerWithPD_h diff --git a/hicn-light/src/hicn/strategies/lowLatency.c b/hicn-light/src/hicn/strategies/lowLatency.c new file mode 100644 index 000000000..a96b7b0af --- /dev/null +++ b/hicn-light/src/hicn/strategies/lowLatency.c @@ -0,0 +1,765 @@ +/* + * 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 <hicn/hicn-light/config.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <math.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 <hicn/core/messageHandler.h> + +#include <hicn/strategies/lowLatency.h> +#include <hicn/strategies/nexthopStateLowLatency.h> +#include <hicn/processor/fibEntry.h> + +const unsigned STABILITY_FACTOR = 15; +const unsigned MAX_SWITCH_TRY = 10; +const unsigned MAX_LATENCY_DIFF = 10; +const unsigned MAX_TOLLERATED_LATENCY_DIFF = 15; +const unsigned MAX_ROUNDS_MP_WITHOUT_CHECK = 2; +const unsigned MAX_ROUNDS_AVOIDING_MULTIPATH = 40; //about 20 sec +const unsigned MAX_ROUNDS_WITH_ERROR = 4; +const unsigned PROBE_LIFETIME = 500; //ms + +static void _strategyLowLatency_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks pitEntryCreation, + Ticks objReception); +static void _strategyLowLatency_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId); +static NumberSet *_strategyLowLatency_LookupNexthop( + StrategyImpl *strategy, +#ifdef WITH_POLICY + NumberSet * nexthops, +#endif /* WITH_POLICY */ + const Message *interestMessage); +#ifndef WITH_POLICY +static NumberSet *_strategyLowLatency_ReturnNexthops(StrategyImpl *strategy); +static unsigned _strategyLowLatency_CountNexthops(StrategyImpl *strategy); +#endif /* ! WITH_POLICY */ +static void _strategyLowLatency_AddNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLowLatency_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId); +static void _strategyLowLatency_ImplDestroy(StrategyImpl **strategyPtr); +static strategy_type _strategyLowLatency_GetStrategy(StrategyImpl *strategy); + +static StrategyImpl _template = { + .context = NULL, + .receiveObject = &_strategyLowLatency_ReceiveObject, + .onTimeout = &_strategyLowLatency_OnTimeout, + .lookupNexthop = &_strategyLowLatency_LookupNexthop, +#ifndef WITH_POLICY + .returnNexthops = &_strategyLowLatency_ReturnNexthops, + .countNexthops = &_strategyLowLatency_CountNexthops, +#endif /* ! WITH_POLICY */ + .addNexthop = &_strategyLowLatency_AddNexthop, + .removeNexthop = &_strategyLowLatency_RemoveNexthop, + .destroy = &_strategyLowLatency_ImplDestroy, + .getStrategy = &_strategyLowLatency_GetStrategy, +}; + +struct strategy_low_latency; +typedef struct strategy_low_latency StrategyLowLatency; + +struct strategy_low_latency { + // hash map from connectionId to StrategyNexthopStateLL + PARCHashMap *strategy_state; + //hash map from sequence number to ticks (sent time) + PARCHashMap *pending_probes_ticks; + //hash map from sequence number to face id + PARCHashMap *pending_probes_faces; + const Forwarder * forwarder; + const FibEntry * fibEntry; + PARCEventTimer *sendProbes; + PARCEventTimer *computeBestFace; + uint8_t * probe; + hicn_name_t * name; + StrategyNexthopStateLL * bestFaces[2]; + unsigned round; + unsigned rounds_in_multipath; + unsigned rounds_with_error; + unsigned rounds_avoiding_multipath; + bool use2paths; + bool avoid_multipath; +#ifndef WITH_POLICY + NumberSet *nexthops; +#endif /* ! WITH_POLICY */ +}; + +static void strategyLowLatency_SendProbesCB(int fd, PARCEventType which_event, + void *data){ + parcAssertTrue(which_event & PARCEventType_Timeout, + "Event incorrect, expecting %X set, got %X", + PARCEventType_Timeout, which_event); + + StrategyLowLatency *ll = (StrategyLowLatency *) data; + + //delete old pending probes + if(parcHashMap_Size(ll->pending_probes_ticks) != 0){ + Ticks now = forwarder_GetTicks(ll->forwarder); + PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->pending_probes_ticks); + NumberSet *to_remove = numberSet_Create(); + while(parcIterator_HasNext(iterator)) { + PARCUnsigned *parc_seq = (PARCUnsigned *) parcIterator_Next(iterator); + PARCUnsigned *parc_time = (PARCUnsigned *) parcHashMap_Get(ll->pending_probes_ticks, parc_seq); + Ticks sent_time = parcUnsigned_GetUnsigned(parc_time); + if((now - sent_time) > PROBE_LIFETIME){ + //probes to delete + numberSet_Add(to_remove, parcUnsigned_GetUnsigned(parc_seq)); + } + } + parcIterator_Release(&iterator); + + for(int i = 0; i < numberSet_Length(to_remove); i++){ + PARCUnsigned *prob_seq = parcUnsigned_Create(numberSet_GetItem(to_remove,i)); + PARCUnsigned *cid = (PARCUnsigned *) parcHashMap_Get(ll->pending_probes_faces, prob_seq); + StrategyNexthopStateLL *state = + (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); + strategyNexthopStateLL_LostProbe(state); + parcHashMap_Remove(ll->pending_probes_ticks, prob_seq); + parcHashMap_Remove(ll->pending_probes_faces, prob_seq); + parcUnsigned_Release(&prob_seq); + } + numberSet_Release(&to_remove); + } + + ConnectionTable * ct = forwarder_GetConnectionTable(ll->forwarder); + + PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + while(parcIterator_HasNext(iterator)){ + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + Connection *conn = + (Connection *)connectionTable_FindById(ct, + parcUnsigned_GetUnsigned(cid)); + if(!conn) + continue; + + StrategyNexthopStateLL *state = + (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); + + //probe only usable paths + if(!strategyNexthopStateLL_IsAllowed(state)) + continue; + + uint32_t seq = rand(); + messageHandler_SetProbeName(ll->probe, HF_INET6_TCP, + ll->name, seq); + connection_Probe(conn, ll->probe); + + PARCUnsigned *parc_seq = parcUnsigned_Create(seq); + Ticks now = forwarder_GetTicks(ll->forwarder); + PARCUnsigned *parc_time = parcUnsigned_Create(now); + parcHashMap_Put(ll->pending_probes_ticks, parc_seq, parc_time); + parcHashMap_Put(ll->pending_probes_faces, parc_seq, cid); + strategyNexthopStateLL_SentProbe(state); + parcUnsigned_Release(&parc_seq); + parcUnsigned_Release(&parc_time); + } + parcIterator_Release(&iterator); + + struct timeval timeout = {0,50000}; + parcEventTimer_Start(ll->sendProbes, &timeout); +} + +static void strategyLowLatency_SelectBestFaces(StrategyLowLatency *ll, + bool new_round){ + + if(new_round){ + ll->round++; + } + + if(parcHashMap_Size(ll->strategy_state) == 0){ + ll->bestFaces[0] = NULL; + ll->bestFaces[1] = NULL; + ll->use2paths = false; + goto NEW_ROUND; + } + + if(ll->use2paths && ll->bestFaces[0] != NULL && ll->bestFaces[1] != NULL){ + //multipath case + + if(!strategyNexthopStateLL_IsLossy(ll->bestFaces[0]) + && !strategyNexthopStateLL_IsLossy(ll->bestFaces[1]) + && strategyNexthopStateLL_IsAllowed(ll->bestFaces[0]) + && strategyNexthopStateLL_IsAllowed(ll->bestFaces[1])){ + + if(ll->rounds_in_multipath < MAX_ROUNDS_MP_WITHOUT_CHECK){ + //we are at the first rounds of the multipath let's wait a bit + //(MAX_ROUNDS_MP_WITHOUT_CHECK) to make the queuing converge + ll->rounds_in_multipath++; + goto NEW_ROUND; + } + + //we need to decide if we want ot keep using two paths or not + ll->rounds_in_multipath++; + double rtt0 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]); + double rtt1 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]); + double diff = fabs(rtt0 - rtt1); + + if(diff < MAX_LATENCY_DIFF){ + //everything is working, keep using the two paths + ll->rounds_with_error = 0; + goto NEW_ROUND; + } + + //check for how many rounds we had problems + if(ll->rounds_with_error < MAX_ROUNDS_WITH_ERROR && + diff < MAX_TOLLERATED_LATENCY_DIFF){ + //we can tollerate few round with errors + ll->rounds_with_error++; + goto NEW_ROUND; + } + + //prevent the usage of multiple paths + ll->rounds_with_error = 0; + ll->avoid_multipath = true; + ll->rounds_avoiding_multipath = 0; + } //else + //at least one of the two path is lossy + //or it is not allowed by the policies. + //search for a better possibility + } + + ll->bestFaces[0] = NULL; + ll->bestFaces[1] = NULL; + + //check if there is at least one non lossy connection + PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + bool check_losses = true; + bool found_good_face = false; + while(parcIterator_HasNext(iterator) && !found_good_face){ + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + const StrategyNexthopStateLL *state = parcHashMap_Get(ll->strategy_state, cid); + if(!strategyNexthopStateLL_IsLossy(state) && + strategyNexthopStateLL_IsAllowed(state)){ + found_good_face = true; + } + } + parcIterator_Release(&iterator); + if(!found_good_face){ + // all the available faces are lossy, so we take into account only + // the latency computed with the probes + check_losses = false; + } + + if(ll->bestFaces[0] == NULL){ + //try to take a random face + PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + bool face_found = false; + while(parcIterator_HasNext(iterator) && !face_found) { + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) + parcHashMap_Get(ll->strategy_state, cid); + + if((check_losses && strategyNexthopStateLL_IsLossy(state)) || + !strategyNexthopStateLL_IsAllowed(state)){ + //skip the face + continue; + } + + ll->bestFaces[0] = state; + face_found = true; + } + parcIterator_Release(&iterator); + } + + if(ll->bestFaces[0] == NULL){ + //no usable face exists + ll->bestFaces[0] = NULL; + ll->bestFaces[1] = NULL; + ll->use2paths = false; + goto NEW_ROUND; + } + + double bestRtt = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]); + + if(ll->avoid_multipath) + ll->rounds_avoiding_multipath++; + + if(ll->rounds_avoiding_multipath > MAX_ROUNDS_AVOIDING_MULTIPATH){ + ll->avoid_multipath = false; + ll->rounds_avoiding_multipath = 0; + } + + iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + while (parcIterator_HasNext(iterator)) { + + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) + parcHashMap_Get(ll->strategy_state, cid); + double rtt = strategyNexthopStateLL_GetRTTLive(state); + + if((check_losses && strategyNexthopStateLL_IsLossy(state)) || + !strategyNexthopStateLL_IsAllowed(state)){ + //skip the face + continue; + } + + if(rtt + STABILITY_FACTOR < bestRtt){ + //maybe we found a better face + double rttInUse = strategyNexthopStateLL_GetRTTInUse(state); + unsigned try = strategyNexthopStateLL_GetTryToSwitch(state); + + //we check the rtt in use to check if the new face that we found + //gets congested when we use it to send the traffic + if(rttInUse < bestRtt || try > MAX_SWITCH_TRY){ + //we have a new best face! + strategyNexthopStateLL_ResetTryToSwitch((StrategyNexthopStateLL*) state); + bestRtt = rtt; + if(ll->bestFaces[0] != NULL) + strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[0]); + ll->bestFaces[0] = (StrategyNexthopStateLL*) state; + }else{ + //in this case we should switch but we wait MAX_SWITCH_TRY + //before switch to avoid ossillations between different paths + strategyNexthopStateLL_IncreaseTryToSwitch( + (StrategyNexthopStateLL*) state, ll->round); + } + } + } + + parcIterator_Release(&iterator); + + if(ll->bestFaces[0] == NULL){ + //we found no face so return + ll->bestFaces[0] = NULL; + ll->bestFaces[1] = NULL; + ll->use2paths = false; + goto NEW_ROUND; + } + + if(parcHashMap_Size(ll->strategy_state) == 1 || ll->avoid_multipath){ + //in this case (one face available or avoid multipath) we stop the + //search here. Just reset face 1 if needed + if(ll->bestFaces[1] != NULL){ + strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); + ll->bestFaces[1] = NULL; + } + ll->use2paths = false; + goto NEW_ROUND; + } + + //if we are here we have more than 1 interface, so we search for a second one + //to use in case of multipath + iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + while (parcIterator_HasNext(iterator)) { + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + if(parcUnsigned_GetUnsigned(cid) != + strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])){ + + StrategyNexthopStateLL *state = (StrategyNexthopStateLL *) + parcHashMap_Get(ll->strategy_state, cid); + + if((check_losses && strategyNexthopStateLL_IsLossy(state)) || + !strategyNexthopStateLL_IsAllowed(state)){ + //skip the face + continue; + } + + if(ll->bestFaces[1] == NULL){ + //in case of 2 faces we should pass always here + ll->bestFaces[1] = state; + }else{ + //TODO this must be tested with more then 2 faces + double rtt1 = strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]); + double rttNewFace = strategyNexthopStateLL_GetRTTLive(state); + if(rttNewFace + STABILITY_FACTOR < rtt1){ + strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); + ll->bestFaces[1] = state; + } + } + } + } + parcIterator_Release(&iterator); + + if(ll->bestFaces[1] != NULL){ + //we are not using the second face yet so we use the normal rtt for comparison + double rtt0 = strategyNexthopStateLL_GetRTTProbe(ll->bestFaces[0]); + double rtt1 = strategyNexthopStateLL_GetRTTProbe(ll->bestFaces[1]); + double diff = fabs(rtt0 - rtt1); + if(diff < MAX_LATENCY_DIFF) { + //let's start to use 2 paths + ll->rounds_with_error = 0; + ll->use2paths = true; + ll->rounds_in_multipath = 0; + }else{ + //we use only one path + strategyNexthopStateLL_SetUnusedFace(ll->bestFaces[1]); + ll->bestFaces[1] = NULL; + ll->use2paths = false; + } + }else{ + ll->use2paths = false; + } + + NEW_ROUND: +#if 1 + if(ll->use2paths){ + printf("use 2 paths. rtt face %d = %f queue = %f is_lossy = %d," + "rtt face %d = %f queue = %f is_lossy = %d\n", + strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]), + strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]), + strategyNexthopStateLL_GetQueuing(ll->bestFaces[0]), + strategyNexthopStateLL_IsLossy(ll->bestFaces[0]), + strategyNexthopStateLL_GetFaceId(ll->bestFaces[1]), + strategyNexthopStateLL_GetRTTLive(ll->bestFaces[1]), + strategyNexthopStateLL_GetQueuing(ll->bestFaces[1]), + strategyNexthopStateLL_IsLossy(ll->bestFaces[1])); + }else{ + if(ll->bestFaces[0] != NULL){ + printf("use 1 path. rtt face %d = %f is_lossy = %d (avoid multipath = %d)\n", + strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]), + strategyNexthopStateLL_GetRTTLive(ll->bestFaces[0]), + strategyNexthopStateLL_IsLossy(ll->bestFaces[0]), + ll->avoid_multipath); + }else{ + printf("no face to use!\n"); + } + } +#endif + //update the round only at the end for all the faces + if(new_round){ + PARCIterator * iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + while (parcIterator_HasNext(iterator)) { + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + strategyNexthopStateLL_StartNewRound((StrategyNexthopStateLL *) + parcHashMap_Get(ll->strategy_state, cid)); + } + parcIterator_Release(&iterator); + } +} + +static void strategyLowLatency_BestFaceCB(int fd, PARCEventType which_event, + void *data){ + parcAssertTrue(which_event & PARCEventType_Timeout, + "Event incorrect, expecting %X set, got %X", + PARCEventType_Timeout, which_event); + + StrategyLowLatency * ll = (StrategyLowLatency *) data; + strategyLowLatency_SelectBestFaces(ll, true); + + struct timeval timeout = {0, 500000}; + parcEventTimer_Start(ll->computeBestFace, &timeout); +} + +StrategyImpl *strategyLowLatency_Create() { + StrategyLowLatency *strategy = + parcMemory_AllocateAndClear(sizeof(StrategyLowLatency)); + parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(StrategyLowLatency)); + + strategy->strategy_state = parcHashMap_Create(); + strategy->pending_probes_ticks = parcHashMap_Create(); + strategy->pending_probes_faces = parcHashMap_Create(); +#ifndef WITH_POLICY + strategy->nexthops = numberSet_Create(); +#endif /* ! WITH_POLICY */ + 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; +} + +void strategyLowLatency_SetStrategy(StrategyImpl *strategy, + const Forwarder * forwarder, + const FibEntry * fibEntry){ + StrategyLowLatency *ll = + (StrategyLowLatency *)strategy->context; + ll->forwarder = forwarder; + ll->fibEntry = fibEntry; + + //create probe packet + ll->probe = messageHandler_CreateProbePacket(HF_INET6_TCP, PROBE_LIFETIME); + ip_prefix_t address; + nameBitvector_ToIPAddress(name_GetContentName( + fibEntry_GetPrefix(fibEntry)), &address); + ll->name = messageHandler_CreateProbeName(&address); + + + Dispatcher *dispatcher = forwarder_GetDispatcher((Forwarder *)ll->forwarder); + ll->sendProbes = dispatcher_CreateTimer(dispatcher, false, + strategyLowLatency_SendProbesCB, ll); + + ll->round = 0; + ll->rounds_in_multipath = 0; + ll->rounds_with_error = 0; + ll->rounds_avoiding_multipath = 0; + ll->use2paths = false; + ll->avoid_multipath = false; + + ll->computeBestFace = dispatcher_CreateTimer(dispatcher, false, + strategyLowLatency_BestFaceCB, ll); +} + +void _startTimers(StrategyImpl *strategy){ + StrategyLowLatency *ll = + (StrategyLowLatency *)strategy->context; + + struct timeval timeoutProbes = {0,10000}; + parcEventTimer_Start(ll->sendProbes, &timeoutProbes); + struct timeval timeoutBF = {1,0}; + parcEventTimer_Start(ll->computeBestFace, &timeoutBF); +} + +void _stopTimers(StrategyImpl *strategy){ + StrategyLowLatency *ll = + (StrategyLowLatency *)strategy->context; + + parcEventTimer_Stop(ll->sendProbes); + parcEventTimer_Stop(ll->computeBestFace); +} + +// ======================================================= +// Dispatch API + +strategy_type _strategyLowLatency_GetStrategy(StrategyImpl *strategy) { + return SET_STRATEGY_LOW_LATENCY; +} + +static void _strategyLowLatency_ReceiveObject(StrategyImpl *strategy, + const NumberSet *egressId, + const Message *objectMessage, + Ticks pitEntryCreation, + Ticks objReception) { + StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; + + if(!messageHandler_IsAProbe(message_FixedHeader(objectMessage))) + return; + + uint32_t seq = messageHandler_GetSegment(message_FixedHeader(objectMessage)); + PARCUnsigned *parc_seq = parcUnsigned_Create(seq); + if (!parcHashMap_Contains(ll->pending_probes_ticks, parc_seq)){ + parcUnsigned_Release(&parc_seq); + return; + } + + //here numberSet_Length(egressId) should be 1 + for (unsigned i = 0; i < numberSet_Length(egressId); i++) { + unsigned outId = numberSet_GetItem(egressId, i); + PARCUnsigned *cid = parcUnsigned_Create(outId); + + const StrategyNexthopStateLL *state = + parcHashMap_Get(ll->strategy_state, cid); + if (state != NULL) { + Ticks time = parcUnsigned_GetUnsigned( + parcHashMap_Get(ll->pending_probes_ticks, parc_seq)); + Ticks now = forwarder_GetTicks(ll->forwarder); + Ticks RTT = now - time; + if(RTT <= 0) + RTT = 1; + strategyNexthopStateLL_AddRttSample( + (StrategyNexthopStateLL *) state, RTT); + parcHashMap_Remove(ll->pending_probes_ticks, parc_seq); + } else { + // this may happen if we remove a face/route while downloading a file + // we should ignore this timeout + } + parcUnsigned_Release(&cid); + } + parcUnsigned_Release(&parc_seq); +} + +static void _strategyLowLatency_OnTimeout(StrategyImpl *strategy, + const NumberSet *egressId) {} + +static NumberSet *_strategyLowLatency_LookupNexthop(StrategyImpl *strategy, +#ifdef WITH_POLICY + NumberSet * nexthops, +#endif /* WITH_POLICY */ + const Message *interestMessage) { + //unsigned out_connection; + NumberSet *out = numberSet_Create(); + + StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; + + //update is_allowed flag of all the next hops + PARCIterator *iterator = parcHashMap_CreateKeyIterator(ll->strategy_state); + while(parcIterator_HasNext(iterator)){ + PARCUnsigned *cid = (PARCUnsigned *) parcIterator_Next(iterator); + StrategyNexthopStateLL *state = + (StrategyNexthopStateLL *) parcHashMap_Get(ll->strategy_state, cid); + if(numberSet_Contains(nexthops, parcUnsigned_GetUnsigned(cid))){ + strategyNexthopStateLL_SetIsAllowed(state,true); + }else{ + strategyNexthopStateLL_SetIsAllowed(state,false); + } + } + parcIterator_Release(&iterator); + + if(ll->bestFaces[0] != NULL && + !strategyNexthopStateLL_IsAllowed(ll->bestFaces[0])){ + //if ll->bestFaces[0] is not allowed we need to find a new face + strategyLowLatency_SelectBestFaces(ll, false); + } + + //at this point ll->bestFaces[0] must be allowed + //single path case + if(ll->bestFaces[0] != NULL && (ll->bestFaces[1] == NULL || !ll->use2paths)){ + strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); + numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); + + //multipath case + }else if(ll->bestFaces[0] != NULL && ll->bestFaces[1] != NULL && ll->use2paths){ + //it may happen that ll->bestFaces[1] is not allowed, in that case we send on + //ll->bestFaces[0] until the next best face selection + if(!strategyNexthopStateLL_IsAllowed(ll->bestFaces[1])){ + strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); + numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); + }else{ + double queue0 = strategyNexthopStateLL_GetQueuing(ll->bestFaces[0]); + double queue1 = strategyNexthopStateLL_GetQueuing(ll->bestFaces[1]); + double prob0 = 0.5; + if(queue0 > 1 || queue1 > 1){ + prob0 = 1.0 - (queue0 / (queue0 + queue1)); + } + double coin = ((double) rand() / (RAND_MAX)); + if(coin < prob0){ + strategyNexthopStateLL_SendPacket(ll->bestFaces[0]); + numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[0])); + }else{ + strategyNexthopStateLL_SendPacket(ll->bestFaces[1]); + numberSet_Add(out, strategyNexthopStateLL_GetFaceId(ll->bestFaces[1])); + } + } + } + return out; +} + + +#ifndef WITH_POLICY +static NumberSet *_strategyLowLatency_ReturnNexthops(StrategyImpl *strategy) { + StrategyLoadBalancerLL *ll = (StrategyLoadBalancerLL *)strategy->context; + return ll->nexthops; +} + +unsigned _strategyLowLatency_CountNexthops(StrategyImpl *strategy) { + StrategyLoadBalancerLL *ll = (StrategyLoadBalancerLL *)strategy->context; + return (unsigned)numberSet_Length(ll->nexthops); +} +#endif /* ! WITH_POLICY */ + +static void _strategyLowLatency_AddNexthop(StrategyImpl *strategy, + unsigned connectionId) { + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; + + if (!parcHashMap_Contains(ll->strategy_state, cid)) { + StrategyNexthopStateLL *state = strategyNexthopStateLL_Create(connectionId); + parcHashMap_Put(ll->strategy_state, cid, state); + if(ll->bestFaces[0] == NULL){ + ll->bestFaces[0] = state; + } +#ifndef WITH_POLICY + numberSet_Add(ll->nexthops, connectionId); +#endif /* WITH_POLICY */ + } + + if(parcHashMap_Size(ll->strategy_state) >= 2){ + _startTimers(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void _strategyLowLatency_RemoveNexthop(StrategyImpl *strategy, + unsigned connectionId) { + StrategyLowLatency *ll = (StrategyLowLatency *)strategy->context; + + bool reset_bestFaces = false; + + if((ll->bestFaces[0] != NULL && + strategyNexthopStateLL_GetFaceId(ll->bestFaces[0]) == connectionId) || + (ll->bestFaces[1] != NULL && + strategyNexthopStateLL_GetFaceId(ll->bestFaces[1]) == connectionId)){ + reset_bestFaces = true; + } + + PARCUnsigned *cid = parcUnsigned_Create(connectionId); + + if (parcHashMap_Contains(ll->strategy_state, cid)) { + parcHashMap_Remove(ll->strategy_state, cid); +#ifndef WITH_POLICY + numberSet_Remove(lb->nexthops, connectionId); +#endif /* WITH_POLICY */ + } + + if(reset_bestFaces){ + ll->bestFaces[0] = NULL; + ll->bestFaces[1] = NULL; + strategyLowLatency_SelectBestFaces(ll, false); + } + + if(parcHashMap_Size(ll->strategy_state) < 2){ + _stopTimers(strategy); + } + + parcUnsigned_Release(&cid); +} + +static void _strategyLowLatency_ImplDestroy(StrategyImpl **strategyPtr) { + parcAssertNotNull(strategyPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*strategyPtr, + "Parameter must dereference to non-null pointer"); + + StrategyImpl *impl = *strategyPtr; + StrategyLowLatency *strategy = (StrategyLowLatency *)impl->context; + + _stopTimers(impl); + + parcEventTimer_Destroy(&(strategy->sendProbes)); + parcEventTimer_Destroy(&(strategy->computeBestFace)); + + if (parcHashMap_Size(strategy->strategy_state) > 0) { + PARCIterator *it = parcHashMap_CreateKeyIterator(strategy->strategy_state); + while (parcIterator_HasNext(it)) { + PARCUnsigned *cid = parcIterator_Next(it); + StrategyNexthopStateLL *state = + (StrategyNexthopStateLL *)parcHashMap_Get(strategy->strategy_state, cid); + parcObject_Release((void**)&state); + } + parcIterator_Release(&it); + } + + parcHashMap_Release(&(strategy->strategy_state)); + parcHashMap_Release(&(strategy->pending_probes_ticks)); + parcHashMap_Release(&(strategy->pending_probes_faces)); + + parcMemory_Deallocate(&(strategy->probe)); + parcMemory_Deallocate(&(strategy->name)); +#ifndef WITH_POLICY + numberSet_Release(&(strategy->nexthops)); +#endif /* ! WITH_POLICY */ + + parcMemory_Deallocate((void **)&strategy); + parcMemory_Deallocate((void **)&impl); + *strategyPtr = NULL; +} diff --git a/hicn-light/src/hicn/strategies/rndSegment.h b/hicn-light/src/hicn/strategies/lowLatency.h index 6694f03e5..f82a576f1 100644 --- a/hicn-light/src/hicn/strategies/rndSegment.h +++ b/hicn-light/src/hicn/strategies/lowLatency.h @@ -14,15 +14,18 @@ */ /** - * Forward randomly, selects a path every time the client ask for a new dash - * segment + * Forward on the path with lowest latency */ -#ifndef rnd_Segment_h -#define rnd_Segment_h +#ifndef lowLatency_h +#define lowLatency_h #include <hicn/strategies/strategyImpl.h> +#include <hicn/core/forwarder.h> -StrategyImpl *strategyRndSegment_Create(); +StrategyImpl *strategyLowLatency_Create(); -#endif // rnd_Segment_h +void strategyLowLatency_SetStrategy(StrategyImpl *strategy, + const Forwarder * forwarder, + const FibEntry * fibEntry); +#endif // lowLatency_h diff --git a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c new file mode 100644 index 000000000..fd83bb072 --- /dev/null +++ b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.c @@ -0,0 +1,481 @@ +/* + * 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 <hicn/hicn-light/config.h> +#include <stdio.h> +#include <float.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 <hicn/strategies/nexthopStateLowLatency.h> + +const unsigned MAX_ROUNS_WITHOUT_PROBES = 4; + //if we do not receives probes for 4 rounds it means + //that we had no responce from any producer for 2 sec + //we can say that this interface is daed +const unsigned MIN_NON_LOSSY_ROUNDS = 10; + //number of rounds in non lossy mode before switch to + //no lossy state +const double MAX_LOSS_RATE = 0.15; //15% + +struct strategy_nexthop_state_ll { + bool in_use; + bool is_allowed; // the policy may not allow the use of this face + unsigned face_id; + unsigned sent_packets; + //switch metrics + unsigned last_try_to_switch_round; + unsigned try_to_switch_counter; + //probes counters + unsigned recevied_probes; + unsigned rounds_without_probes; + unsigned sent_probes; + unsigned lost_probes; + unsigned non_lossy_rounds; + //avgs + double avg_rtt; + double avg_rtt_in_use; + double avg_queue; + double avg_loss_rate; + +}; + +static bool _strategyNexthopStateLL_Destructor( + StrategyNexthopStateLL **instancePtr) { + return true; +} + +parcObject_ImplementAcquire(strategyNexthopStateLL, StrategyNexthopStateLL); + +parcObject_ImplementRelease(strategyNexthopStateLL, StrategyNexthopStateLL); + +parcObject_Override( + StrategyNexthopStateLL, PARCObject, + .destructor = (PARCObjectDestructor *)_strategyNexthopStateLL_Destructor, + .copy = (PARCObjectCopy *)strategyNexthopStateLL_Copy, + .display = (PARCObjectDisplay *)strategyNexthopStateLL_Display, + .toString = (PARCObjectToString *)strategyNexthopStateLL_ToString, + .equals = (PARCObjectEquals *)strategyNexthopStateLL_Equals, + .compare = (PARCObjectCompare *)strategyNexthopStateLL_Compare, + .hashCode = (PARCObjectHashCode *)strategyNexthopStateLL_HashCode, + .display = (PARCObjectDisplay *)strategyNexthopStateLL_Display); + +void strategyNexthopStateLL_AssertValid(const StrategyNexthopStateLL *instance) { + parcAssertTrue(strategyNexthopStateLL_IsValid(instance), + "StrategyNexthopState is not valid."); +} + +StrategyNexthopStateLL *strategyNexthopStateLL_Create(unsigned face_id) { + StrategyNexthopStateLL *result = + parcObject_CreateInstance(StrategyNexthopStateLL); + if (result != NULL) { + result->in_use = false; + result->is_allowed = true; + result->face_id = face_id; + result->sent_packets = 0; + result->last_try_to_switch_round = 0; + result->try_to_switch_counter = 0; + result->recevied_probes = 0; + result->rounds_without_probes = 0; + result->sent_probes = 0; + result->lost_probes = 0; + result->non_lossy_rounds = MIN_NON_LOSSY_ROUNDS; + result->avg_rtt = -1.0; + result->avg_rtt_in_use = -1.0; + result->avg_queue = 0.0001; + result->avg_loss_rate = 0.0; + } + return result; +} + +void strategyNexthopStateLL_Reset(StrategyNexthopStateLL *x) { + x->in_use = false; + x->is_allowed = true; + x->sent_packets = 0; + x->last_try_to_switch_round = 0; + x->try_to_switch_counter = 0; + x->recevied_probes = 0; + x->rounds_without_probes = 0; + x->sent_probes = 0; + x->lost_probes = 0; + x->non_lossy_rounds = MIN_NON_LOSSY_ROUNDS; + x->avg_rtt = -1.0; + x->avg_rtt_in_use = -1.0; + x->avg_queue = 0.0001; + x->avg_loss_rate = 0.0; +} + + +int strategyNexthopStateLL_Compare(const StrategyNexthopStateLL *val, + const StrategyNexthopStateLL *other) { + if (val == NULL) { + if (other != NULL) { + return -1; + } + } else if (other == NULL) { + return 1; + } else { + strategyNexthopStateLL_OptionalAssertValid(val); + strategyNexthopStateLL_OptionalAssertValid(other); + + if (val->in_use < other->in_use){ + return -1; + }else if (val->in_use > other->in_use){ + return 1; + } + + if (val->is_allowed < other->is_allowed){ + return -1; + }else if (val->is_allowed> other->is_allowed){ + return 1; + } + + if (val->face_id < other->face_id) { + return -1; + } else if (val->face_id > other->face_id) { + return 1; + } + + if (val->sent_packets < other->sent_packets){ + return -1; + } else if (val->sent_packets > other->sent_packets){ + return 1; + } + + if (val->last_try_to_switch_round < + other->last_try_to_switch_round) { + return -1; + } else if (val->last_try_to_switch_round > + other->last_try_to_switch_round) { + return 1; + } + + if (val->try_to_switch_counter < + other->try_to_switch_counter) { + return -1; + } else if (val->try_to_switch_counter > + other->try_to_switch_counter) { + return 1; + } + + if (val->recevied_probes < other->recevied_probes) { + return -1; + } else if (val->recevied_probes > other->recevied_probes) { + return 1; + } + + if (val->rounds_without_probes < other->rounds_without_probes) { + return -1; + } else if (val->rounds_without_probes > other->rounds_without_probes) { + return 1; + } + + if (val->sent_probes < other->sent_probes) { + return -1; + } else if (val->sent_probes > other->sent_probes) { + return 1; + } + + if (val->lost_probes < other->lost_probes) { + return -1; + } else if (val->lost_probes > other->lost_probes) { + return 1; + } + + if (val->non_lossy_rounds < other->non_lossy_rounds) { + return -1; + } else if (val->non_lossy_rounds > other->non_lossy_rounds) { + return 1; + } + + if (val->avg_rtt < other->avg_rtt) { + return -1; + } else if (val->avg_rtt > other->avg_rtt) { + return 1; + } + + if (val->avg_rtt_in_use < other->avg_rtt_in_use) { + return -1; + } else if (val->avg_rtt_in_use > other->avg_rtt_in_use) { + return 1; + } + + if (val->avg_queue < other->avg_queue) { + return -1; + } else if (val->avg_queue > other->avg_queue) { + return 1; + } + + if (val->avg_loss_rate < other->avg_loss_rate) { + return -1; + } else if (val->avg_loss_rate > other->avg_loss_rate) { + return 1; + } + } + + return 0; +} + +StrategyNexthopStateLL *strategyNexthopStateLL_Copy( + const StrategyNexthopStateLL *original) { + StrategyNexthopStateLL *result = strategyNexthopStateLL_Create(original->face_id); + result->in_use = original->in_use; + result->is_allowed = original->is_allowed; + result->sent_packets = original->sent_packets; + result->last_try_to_switch_round = original->last_try_to_switch_round; + result->try_to_switch_counter = original->try_to_switch_counter; + result->recevied_probes = original->recevied_probes; + result->rounds_without_probes = original->rounds_without_probes; + result->sent_probes = original->sent_probes; + result->lost_probes = original->lost_probes; + result->non_lossy_rounds = original->non_lossy_rounds; + result->avg_rtt = original->avg_rtt; + result->avg_rtt_in_use = original->avg_rtt_in_use; + result->avg_queue = original->avg_queue; + result->avg_loss_rate = original->avg_loss_rate; + return result; +} + +void strategyNexthopStateLL_Display(const StrategyNexthopStateLL *instance, + int indentation) { + parcDisplayIndented_PrintLine(indentation, "StrategyNexthopStateLL@%p {", + instance); + parcDisplayIndented_PrintLine(indentation + 1, "%d", instance->face_id); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_rtt); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_rtt_in_use); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_queue); + parcDisplayIndented_PrintLine(indentation + 1, "%f", instance->avg_loss_rate); + parcDisplayIndented_PrintLine(indentation, "}"); +} + + +bool strategyNexthopStateLL_Equals(const StrategyNexthopStateLL *x, + const StrategyNexthopStateLL *y) { + bool result = false; + + if (x == y) { + result = true; + } else if (x == NULL || y == NULL) { + result = false; + } else { + strategyNexthopStateLL_OptionalAssertValid(x); + strategyNexthopStateLL_OptionalAssertValid(y); + + if (strategyNexthopStateLL_Compare(x, y) == 0) { + result = true; + } + } + + return result; +} + +PARCHashCode strategyNexthopStateLL_HashCode(const StrategyNexthopStateLL *x) { + PARCHashCode result = 0; + char str[128]; + sprintf(str, "ID:%d: RTT:%f: RTTUSE:%f: Q:%f L:%f", x->face_id, x->avg_rtt, + x->avg_rtt_in_use, x->avg_queue, x->avg_loss_rate); + result = parcHashCode_Hash((uint8_t *)&str, strlen(str)); + return result; +} + +bool strategyNexthopStateLL_IsValid(const StrategyNexthopStateLL *x) { + bool result = false; + + if (x != NULL) { + result = true; + } + + return result; +} + +char *strategyNexthopStateLL_ToString(const StrategyNexthopStateLL *x) { + // this is not implemented + parcTrapNotImplemented("strategyNexthopStateLL_ToString is not implemented"); + return NULL; +} + +double strategyNexthopStateLL_GetRTTProbe(StrategyNexthopStateLL *x) { + strategyNexthopStateLL_OptionalAssertValid(x); + + if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) + return DBL_MAX; + + if(x->avg_rtt == -1.0){ + if(x->avg_rtt_in_use == -1.0){ + return 0.0; + }else{ + //this happens if the face recevied probes only in in_use mode + //we set the avf_rtt with rtt_in_use + x->avg_rtt = x->avg_rtt_in_use; + } + } + + return x->avg_rtt; +} + +double strategyNexthopStateLL_GetRTTInUse(StrategyNexthopStateLL *x) { + strategyNexthopStateLL_OptionalAssertValid(x); + + if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) + return DBL_MAX; + + if(x->avg_rtt_in_use == -1.0) + return strategyNexthopStateLL_GetRTTProbe(x); + + return x->avg_rtt_in_use; +} + +double strategyNexthopStateLL_GetRTTLive(StrategyNexthopStateLL *x) { + strategyNexthopStateLL_OptionalAssertValid(x); + + if(x->in_use){ + return strategyNexthopStateLL_GetRTTInUse(x); + }else{ + return strategyNexthopStateLL_GetRTTProbe(x); + } +} + +double strategyNexthopStateLL_GetQueuing(const StrategyNexthopStateLL *x) { + strategyNexthopStateLL_OptionalAssertValid(x); + + if(x->rounds_without_probes > MAX_ROUNS_WITHOUT_PROBES) + return 0.0; + + return x->avg_queue; +} + +void strategyNexthopStateLL_AddRttSample(StrategyNexthopStateLL *x, + unsigned int rtt){ + strategyNexthopStateLL_OptionalAssertValid(x); + + x->recevied_probes++; + //form uint to double + double drtt = rtt; + + if(x->in_use){ + if(x->avg_rtt_in_use == -1.0){ + x->avg_rtt_in_use = drtt; + }else{ + x->avg_rtt_in_use = (x->avg_rtt_in_use * 0.9) + (drtt * 0.1); + } + }else{ + if(x->avg_rtt == -1.0){ + x->avg_rtt = drtt; + }else{ + x->avg_rtt = (x->avg_rtt * 0.9) + (drtt * 0.1); + } + } + + if(x->avg_rtt_in_use == -1.0 || x->avg_rtt == -1.0){ + x->avg_queue = 0.0001; + }else{ + double queue = x->avg_rtt_in_use - x->avg_rtt; + if(queue < 0){ + queue = 0.0001; + } + x->avg_queue = (x->avg_queue * 0.95) + (0.05 * queue); + } +} + +void strategyNexthopStateLL_SetUnusedFace(StrategyNexthopStateLL *x){ + strategyNexthopStateLL_OptionalAssertValid(x); + x->in_use = false; +} + +unsigned strategyNexthopStateLL_GetFaceId(StrategyNexthopStateLL *x) { + strategyNexthopStateLL_OptionalAssertValid(x); + return x->face_id; +} + +void strategyNexthopStateLL_IncreaseTryToSwitch(StrategyNexthopStateLL *x, + unsigned round){ + if(x->try_to_switch_counter == 0 || + round == (x->last_try_to_switch_round + 1)){ + x->last_try_to_switch_round = round; + x->try_to_switch_counter++; + }else{ + x->try_to_switch_counter = 0; + } +} + +unsigned strategyNexthopStateLL_GetTryToSwitch(const StrategyNexthopStateLL *x){ + return x->try_to_switch_counter; +} + +void strategyNexthopStateLL_ResetTryToSwitch(StrategyNexthopStateLL *x){ + x->try_to_switch_counter = 0; +} + +void strategyNexthopStateLL_SendPacket(StrategyNexthopStateLL *x){ + x->in_use = true; + x->sent_packets++; +} + +void strategyNexthopStateLL_SentProbe(StrategyNexthopStateLL *x){ + x->sent_probes++; +} + +void strategyNexthopStateLL_LostProbe(StrategyNexthopStateLL *x){ + x->lost_probes++; +} + +bool strategyNexthopStateLL_IsLossy(const StrategyNexthopStateLL *x){ + if(x->non_lossy_rounds < 10 || + x->avg_loss_rate > MAX_LOSS_RATE){ + return true; + } + return false; +} + +void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, bool allowed){ + x->is_allowed = allowed; +} + +bool strategyNexthopStateLL_IsAllowed(const StrategyNexthopStateLL *x){ + return x->is_allowed; +} + +void strategyNexthopStateLL_StartNewRound(StrategyNexthopStateLL *x){ + strategyNexthopStateLL_OptionalAssertValid(x); + if(x->sent_packets == 0) //the face was not used in the last round + x->in_use = false; + + x->sent_packets = 0; + + if(x->recevied_probes == 0){ + x->rounds_without_probes++; + }else{ + x->rounds_without_probes = 0; + } + + x->recevied_probes = 0; + + //compute losses in this round + if(x->sent_probes != 0){ + double loss_rate = (double) x->lost_probes / (double) x->sent_probes; + x->avg_loss_rate = x->avg_loss_rate * 0.7 + loss_rate * 0.3; + if(x->avg_loss_rate > MAX_LOSS_RATE){ + x->non_lossy_rounds = 0; + }else{ + x->non_lossy_rounds++; + } + } + + x->lost_probes = 0; + x->sent_probes = 0; +} diff --git a/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h new file mode 100644 index 000000000..34dbb8262 --- /dev/null +++ b/hicn-light/src/hicn/strategies/nexthopStateLowLatency.h @@ -0,0 +1,116 @@ +/* + * 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 nexthopstateLowLatency_h +#define nexthopstateLowLatency_h + +#include <parc/algol/parc_HashCode.h> +#include <parc/algol/parc_Object.h> + +struct strategy_nexthop_state_ll; +typedef struct strategy_nexthop_state_ll StrategyNexthopStateLL; +extern parcObjectDescriptor_Declaration(StrategyNexthopStateLL); + +/** + */ +StrategyNexthopStateLL *strategyNexthopStateLL_Acquire( + const StrategyNexthopStateLL *instance); + +#ifdef PARCLibrary_DISABLE_VALIDATION +#define strategyNexthopStateLL_OptionalAssertValid(_instance_) +#else +#define strategyNexthopStateLL_OptionalAssertValid(_instance_) \ + strategyNexthopStateLL_AssertValid(_instance_) +#endif + +/** + */ +void strategyNexthopStateLL_AssertValid(const StrategyNexthopStateLL *instance); + +/** + */ +StrategyNexthopStateLL *strategyNexthopStateLL_Create(unsigned face_id); + +void strategyNexthopStateLL_Reset(StrategyNexthopStateLL *x); +/** + */ +int strategyNexthopStateLL_Compare(const StrategyNexthopStateLL *instance, + const StrategyNexthopStateLL *other); + +/** + */ +StrategyNexthopStateLL *strategyNexthopStateLL_Copy( + const StrategyNexthopStateLL *original); + +/** + */ +void strategyNexthopStateLL_Display(const StrategyNexthopStateLL *instance, + int indentation); + +/** + */ +bool strategyNexthopStateLL_Equals(const StrategyNexthopStateLL *x, + const StrategyNexthopStateLL *y); + +/** + */ +PARCHashCode strategyNexthopStateLL_HashCode( + const StrategyNexthopStateLL *instance); + +/** + */ +bool strategyNexthopStateLL_IsValid(const StrategyNexthopStateLL *instance); + +/** + */ +void strategyNexthopStateLL_Release(StrategyNexthopStateLL **instancePtr); + +/** + */ +char *strategyNexthopStateLL_ToString(const StrategyNexthopStateLL *instance); + +/** + */ +double strategyNexthopStateLL_GetRTTProbe(StrategyNexthopStateLL *x); +double strategyNexthopStateLL_GetRTTInUse(StrategyNexthopStateLL *x); +double strategyNexthopStateLL_GetRTTLive(StrategyNexthopStateLL *x); +double strategyNexthopStateLL_GetQueuing(const StrategyNexthopStateLL *x); +void strategyNexthopStateLL_AddRttSample(StrategyNexthopStateLL *x, + unsigned int rtt); + + +void strategyNexthopStateLL_IncreaseTryToSwitch(StrategyNexthopStateLL *x, + unsigned round); +unsigned strategyNexthopStateLL_GetTryToSwitch(const StrategyNexthopStateLL *x); +void strategyNexthopStateLL_ResetTryToSwitch(StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_SetUnusedFace(StrategyNexthopStateLL *x); + +unsigned strategyNexthopStateLL_GetFaceId(StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_SendPacket(StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_SentProbe(StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_LostProbe(StrategyNexthopStateLL *x); + +bool strategyNexthopStateLL_IsLossy(const StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_SetIsAllowed(StrategyNexthopStateLL *x, bool allowed); + +bool strategyNexthopStateLL_IsAllowed(const StrategyNexthopStateLL *x); + +void strategyNexthopStateLL_StartNewRound(StrategyNexthopStateLL *x); +#endif diff --git a/hicn-light/src/hicn/strategies/nexthopStateWithPD.c b/hicn-light/src/hicn/strategies/nexthopStateWithPD.c deleted file mode 100644 index 1a5d34b78..000000000 --- a/hicn-light/src/hicn/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 <hicn/hicn-light/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 <hicn/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/hicn/strategies/nexthopStateWithPD.h b/hicn-light/src/hicn/strategies/nexthopStateWithPD.h deleted file mode 100644 index 4d8bd6d15..000000000 --- a/hicn-light/src/hicn/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/hicn/strategies/rnd.c b/hicn-light/src/hicn/strategies/rnd.c index 637fd90f9..064f3965b 100644 --- a/hicn-light/src/hicn/strategies/rnd.c +++ b/hicn-light/src/hicn/strategies/rnd.c @@ -28,9 +28,12 @@ static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); + const Message *objectMessage, + Ticks pitEntryCreation, + Ticks objReception); static void _strategyRnd_OnTimeout(StrategyImpl *strategy, const NumberSet *egressId); + static NumberSet *_strategyRnd_LookupNexthop(StrategyImpl *strategy, #ifdef WITH_POLICY NumberSet * nexthops, @@ -62,21 +65,21 @@ static StrategyImpl _template = { .getStrategy = &_strategyRnd_GetStrategy, }; +#ifndef WITH_POLICY struct strategy_rnd; typedef struct strategy_rnd StrategyRnd; struct strategy_rnd { -#ifndef WITH_POLICY NumberSet *nexthops; -#endif /* ! WITH_POLICY */ }; +#endif /* ! WITH_POLICY */ StrategyImpl *strategyRnd_Create() { +#ifndef WITH_POLICY StrategyRnd *strategy = parcMemory_AllocateAndClear(sizeof(StrategyRnd)); parcAssertNotNull(strategy, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyRnd)); -#ifndef WITH_POLICY strategy->nexthops = numberSet_Create(); #endif /* ! WITH_POLICY */ srand((unsigned int)time(NULL)); @@ -85,7 +88,9 @@ StrategyImpl *strategyRnd_Create() { parcAssertNotNull(impl, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(StrategyImpl)); memcpy(impl, &_template, sizeof(StrategyImpl)); +#ifndef WITH_POLICY impl->context = strategy; +#endif /* ! WITH_POLICY */ return impl; } @@ -111,7 +116,8 @@ static int _select_Nexthop(StrategyRnd *strategy) { static void _strategyRnd_ReceiveObject(StrategyImpl *strategy, const NumberSet *egressId, const Message *objectMessage, - Ticks rtt) {} + Ticks pitEntryCreation, + Ticks objReception) {} static void _strategyRnd_OnTimeout(StrategyImpl *strategy, const NumberSet *egressId) {} @@ -193,13 +199,13 @@ static void _strategyRnd_ImplDestroy(StrategyImpl **strategyPtr) { "Parameter must dereference to non-null pointer"); StrategyImpl *impl = *strategyPtr; - StrategyRnd *strategy = (StrategyRnd *)impl->context; #ifndef WITH_POLICY + StrategyRnd *strategy = (StrategyRnd *)impl->context; numberSet_Release(&(strategy->nexthops)); + parcMemory_Deallocate((void **)&strategy); #endif /* ! WITH_POLICY */ - parcMemory_Deallocate((void **)&strategy); parcMemory_Deallocate((void **)&impl); *strategyPtr = NULL; } diff --git a/hicn-light/src/hicn/strategies/rndSegment.c b/hicn-light/src/hicn/strategies/rndSegment.c deleted file mode 100644 index 93e39ee74..000000000 --- a/hicn-light/src/hicn/strategies/rndSegment.c +++ /dev/null @@ -1,225 +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 <hicn/hicn-light/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 <hicn/core/nameBitvector.h> -#include <hicn/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, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - const Message *interestMessage); -#ifndef WITH_POLICY -static NumberSet *_strategyRndSegment_ReturnNexthops(StrategyImpl *strategy); -static unsigned _strategyRndSegment_CountNexthops(StrategyImpl *strategy); -#endif /* ! WITH_POLICY */ -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, -#ifndef WITH_POLICY - .returnNexthops = &_strategyRndSegment_ReturnNexthops, - .countNexthops = &_strategyRndSegment_CountNexthops, -#endif /* ! WITH_POLICY */ - .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, -#ifdef WITH_POLICY - NumberSet * nexthops, -#endif /* WITH_POLICY */ - 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; -} - -#ifndef WITH_POLICY -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); -} -#endif /* ! WITH_POLICY */ - -static void _strategyRndSegment_AddNexthop(StrategyImpl *strategy, - unsigned connectionId) { -#ifndef WITH_POLICY - StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; - if (!numberSet_Contains(srnd->nexthops, connectionId)) { - numberSet_Add(srnd->nexthops, connectionId); - } -#endif /* ! WITH_POLICY */ -} - -static void _strategyRndSegment_RemoveNexthop(StrategyImpl *strategy, - unsigned connectionId) { -#ifndef WITH_POLICY - StrategyRndSegment *srnd = (StrategyRndSegment *)strategy->context; - - if (numberSet_Contains(srnd->nexthops, connectionId)) { - numberSet_Remove(srnd->nexthops, connectionId); - } -#endif /* ! WITH_POLICY */ -} - -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/hicn/strategies/strategyImpl.h b/hicn-light/src/hicn/strategies/strategyImpl.h index d4001194a..140da5bf8 100644 --- a/hicn-light/src/hicn/strategies/strategyImpl.h +++ b/hicn-light/src/hicn/strategies/strategyImpl.h @@ -52,7 +52,8 @@ typedef struct strategy_impl StrategyImpl; struct strategy_impl { void *context; void (*receiveObject)(StrategyImpl *strategy, const NumberSet *egressId, - const Message *objectMessage, Ticks rtt); + const Message *objectMessage, Ticks pitEntryCreation, + Ticks objReception); void (*onTimeout)(StrategyImpl *strategy, const NumberSet *egressId); NumberSet *(*lookupNexthop)(StrategyImpl *strategy, #ifdef WITH_POLICY diff --git a/hicn-light/src/hicn/utils/commands.h b/hicn-light/src/hicn/utils/commands.h index 1e227ad23..1cce8edd3 100644 --- a/hicn-light/src/hicn/utils/commands.h +++ b/hicn-light/src/hicn/utils/commands.h @@ -243,8 +243,7 @@ typedef struct { typedef enum { SET_STRATEGY_LOADBALANCER, SET_STRATEGY_RANDOM, - SET_STRATEGY_RANDOM_PER_DASH_SEGMENT, - SET_STRATEGY_LOADBALANCER_WITH_DELAY, + SET_STRATEGY_LOW_LATENCY, LAST_STRATEGY_VALUE } strategy_type; |