//////////////////////////////////////////////////////////////////////////////////////// /** * # Copyright 2022 Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA) www.cttc.es * * 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. * Author: CTTC/CERCA PONS RU Ricardo Martínez (ricardo.martinez@cttc.es) */ //////////////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "pathComp_log.h" #include "pathComp_tools.h" #include "pathComp_ksp.h" // Global Variables struct map_nodes_t *mapNodes = NULL; struct graph_t *graph = NULL; struct contextSet_t* contextSet = NULL; //struct linkList_t* linkList; //struct deviceList_t* deviceList; //struct serviceList_t* serviceList; gint numPathCompIntents = 0; // number of events triggering the path computation gint numSuccesPathComp = 0; // number of events resulting in succesfully path computations fulfilling the constraints struct timeval total_path_comp_time; gdouble totalReqBw = 0.0; gdouble totalServedBw = 0.0; /////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief update statistics of the KSP path computation * * @param routeConnList * @param d * * @author Ricardo Martínez * @date 2021 */ ///////////////////////////////////////////////////////////////////////////////////////// void update_stats_ksp_path_comp(struct compRouteOutputList_t* routeConnList, struct timeval d) { g_assert(routeConnList); g_assert(serviceList); total_path_comp_time.tv_sec = total_path_comp_time.tv_sec + d.tv_sec; total_path_comp_time.tv_usec = total_path_comp_time.tv_usec + d.tv_usec; total_path_comp_time = tv_adjust(total_path_comp_time); gdouble path_comp_time_msec = (((total_path_comp_time.tv_sec) * 1000) + ((total_path_comp_time.tv_usec) / 1000)); gdouble av_alg_comp_time = ((path_comp_time_msec / numSuccesPathComp)); DEBUG_PC("\t --- STATS KSP PATH COMP ----"); DEBUG_PC("Succesfully Comp: %d | Path Comp Requests: %d", numSuccesPathComp, numPathCompIntents); DEBUG_PC("AV. PATH COMP ALG. TIME: %f ms", av_alg_comp_time); for (gint i = 0; i < serviceList->numServiceList; i++) { struct service_t* s = &(serviceList->services[i]); char* eptr; for (gint j = 0; j < s->num_service_constraints; j++) { struct constraint_t* constraints = &(s->constraints[j]); if (strncmp((const char*)(constraints->constraint_type), "bandwidth", 9) == 0) { totalReqBw += (gdouble)(strtod((char*)constraints->constraint_value, &eptr)); } } } for (gint k = 0; k < routeConnList->numCompRouteConnList; k++) { struct compRouteOutput_t* rO = &(routeConnList->compRouteConnection[k]); if (rO->noPathIssue == NO_PATH_CONS_ISSUE) { continue; } // Get the requested service bw bound to that computed path struct path_t* p = &(rO->paths[0]); struct service_t* s = get_service_for_computed_path(rO->serviceId.service_uuid); if (s == NULL) { DEBUG_PC("Weird the service associated to a path is not found"); exit(-1); } for (gint l = 0; l < s->num_service_constraints; l++) { struct constraint_t* constraints = &(s->constraints[l]); char* eptr; if (strncmp((const char*)(constraints->constraint_type), "bandwidth", 9) == 0) { totalServedBw += (gdouble)(strtod((char*)constraints->constraint_value, &eptr)); } } } gdouble avServedRatio = totalServedBw / totalReqBw; DEBUG_PC("AV. Served Ratio: %f", avServedRatio); gdouble avBlockedBwRatio = (gdouble)(1.0 - avServedRatio); DEBUG_PC("AV. BBE: %f", avBlockedBwRatio); return; } /////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief Dijkstra algorithm * * @param srcMapIndex * @param dstMapIndex * @param g * @param s * @param SN * @param RP * * @author Ricardo Martínez * @date 2022 */ ///////////////////////////////////////////////////////////////////////////////////////// void sp_comp(gint srcMapIndex, gint dstMapIndex, struct graph_t* g, struct service_t* s, struct nodes_t* SN, struct compRouteOutputItem_t* RP) { g_assert(s); g_assert(g); // Set params into mapNodes related to the source nodes of the request mapNodes->map[srcMapIndex].distance = 0.0; mapNodes->map[srcMapIndex].latency = 0.0; mapNodes->map[srcMapIndex].avaiBandwidth = 0.0; // Initialize the set Q and S GList* S = NULL, * Q = NULL; gint indexVertice = -1; // Add the source into the Q struct nodeItem_t* nodeItem = g_malloc0(sizeof(struct nodeItem_t)); if (nodeItem == NULL) { DEBUG_PC("memory allocation failed\n"); exit(-1); } // initialize some nodeItem attributes nodeItem->distance = 0.0; nodeItem->latency = 0.0; duplicate_node_id(&mapNodes->map[srcMapIndex].verticeId, &nodeItem->node); Q = g_list_insert_sorted(Q, nodeItem, sort_by_distance); // Check whether there is spurNode (SN) and rootPath (RP) if (SN != NULL && RP != NULL) { struct routeElement_t* re; for (gint j = 0; j < RP->numRouteElements; j++) { // Get the source and target Nodes of the routeElement within the rootPath re = &RP->routeElement[j]; DEBUG_PC ("root Link: aNodeId: %s (%s) --> zNodeiId: %s (%s)", re->aNodeId.nodeId, re->aEndPointId, re->zNodeId.nodeId, re->zEndPointId); // if ingress of the root link (aNodeId) is the spurNode, then stops if (compare_node_id(&re->aNodeId, SN) == 0) { DEBUG_PC ("root Link: aNodeId: %s and spurNode: %s -- stop exploring the rootPath (RP)", re->aNodeId.nodeId, SN->nodeId); break; } // Extract from Q GList* listnode = g_list_first(Q); struct nodeItem_t* node = (struct nodeItem_t*)(listnode->data); Q = g_list_remove(Q, node); //DEBUG_RL_RA ("Exploring node %s", node->node.nodeId); indexVertice = graph_vertice_lookup(node->node.nodeId, g); g_assert(indexVertice >= 0); // Get the indexTargetedVertice gint indexTVertice = -1; indexTVertice = graph_targeted_vertice_lookup(indexVertice, re->zNodeId.nodeId, g); gint done = check_link(node, indexVertice, indexTVertice, g, s, &S, &Q, mapNodes); (void)done; // Add to the S list S = g_list_append(S, node); } // Check that the first node in Q set is SpurNode, otherwise something went wrong ... if (compare_node_id(&re->aNodeId, SN) != 0) { //DEBUG_PC ("root Link: aNodeId: %s is NOT the spurNode: %s -- something wrong", re->aNodeId.nodeId, SN->nodeId); g_list_free_full(S, g_free); g_list_free_full(Q, g_free); return; } } while (g_list_length(Q) > 0) { //Extract from Q set GList* listnode = g_list_first(Q); struct nodeItem_t* node = (struct nodeItem_t*)(listnode->data); Q = g_list_remove(Q, node); DEBUG_PC ("Q length: %d", g_list_length (Q)); DEBUG_PC ("DeviceId: %s", node->node.nodeId); // visit all the links from u within the graph indexVertice = graph_vertice_lookup(node->node.nodeId, g); g_assert(indexVertice >= 0); // Check the targeted vertices from u for (gint i = 0; i < g->vertices[indexVertice].numTargetedVertices; i++) { gint done = check_link(node, indexVertice, i, g, s, &S, &Q, mapNodes); (void)done; } // Add node into the S Set S = g_list_append(S, node); //DEBUG_PC ("S length: %d", g_list_length (S)); } g_list_free_full(S, g_free); g_list_free_full(Q, g_free); return; } /////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief KSP computation using Dijkstra algorithm * * @param pred * @param g * @param s * @param SN * @param RP * * @author Ricardo Martínez * @date 2022 */ ///////////////////////////////////////////////////////////////////////////////////////// gint ksp_comp(struct pred_t* pred, struct graph_t* g, struct service_t* s, struct nodes_t *SN, struct compRouteOutputItem_t *RP) { g_assert(pred); g_assert(g); g_assert(s); // Check the both ingress src and dst endpoints are in the graph gint srcMapIndex = get_map_index_by_nodeId(s->service_endpoints_id[0].device_uuid, mapNodes); if (srcMapIndex == -1) { DEBUG_PC("ingress DeviceId: %s NOT in the graph", s->service_endpoints_id[0].device_uuid); return -1; } gint dstMapIndex = get_map_index_by_nodeId(s->service_endpoints_id[1].device_uuid, mapNodes); if (dstMapIndex == -1) { DEBUG_PC("egress DeviceId: %s NOT in the graph", s->service_endpoints_id[1].device_uuid); return -1; } // Compute the shortes path route sp_comp(srcMapIndex, dstMapIndex, g, s, SN, RP); // Check that a feasible solution in term of latency and bandwidth is found gint map_dstIndex = get_map_index_by_nodeId(s->service_endpoints_id[1].device_uuid, mapNodes); struct map_t* dest_map = &mapNodes->map[map_dstIndex]; if (!(dest_map->distance < INFINITY_COST)) { DEBUG_PC("destination: %s NOT reachable", s->service_endpoints_id[1].device_uuid); return -1; } DEBUG_PC("AvailBw @ %s is %f", dest_map->verticeId.nodeId, dest_map->avaiBandwidth); // Check that the computed available bandwidth is larger than 0.0 if (dest_map->avaiBandwidth <= (gfloat)0.0) { DEBUG_PC("dst: %s NOT REACHABLE", s->service_endpoints_id[1].device_uuid); return -1; } DEBUG_PC("dst: %s REACHABLE", s->service_endpoints_id[1].device_uuid); // Handle predecessors build_predecessors(pred, s, mapNodes); return 1; } //////////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief K-CSPF algorithm execution (YEN algorithm) * * @param s * @param path * @param g * * @author Ricardo Martínez * @date 2022 */ ///////////////////////////////////////////////////////////////////////////////////////// void alg_comp(struct service_t* s, struct compRouteOutput_t* path, struct graph_t *g) { g_assert(s); g_assert(path); g_assert(g); // create map of devices/nodes to handle the path computation using the context mapNodes = create_map_node(); build_map_node(mapNodes, g); // predecessors to store the computed path struct pred_t* predecessors = create_predecessors(); struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[0]); struct service_endpoints_id_t* eEp = &(s->service_endpoints_id[1]); // Compute the 1st KSP path gint done = ksp_comp (predecessors, g, s, NULL, NULL); if (done == -1) { DEBUG_PC("NO PATH FOUND %s[%s] ---> %s[%s]", iEp->device_uuid, iEp->endpoint_uuid, eEp->device_uuid, eEp->endpoint_uuid); comp_route_connection_issue_handler(path, s); g_free(mapNodes); g_free(predecessors); return; } // Construct the path from the computed predecessors struct compRouteOutputItem_t* p = create_path_item(); //print_predecessors(predecessors); build_path(p, predecessors, s); //DEBUG_PC ("Path is constructed"); gint indexDest = get_map_index_by_nodeId(eEp->device_uuid, mapNodes); struct map_t* dst_map = &mapNodes->map[indexDest]; // Get the delay and cost memcpy(&p->cost, &dst_map->distance, sizeof(gdouble)); memcpy(&p->availCap, &dst_map->avaiBandwidth, sizeof(dst_map->avaiBandwidth)); memcpy(&p->delay, &dst_map->latency, sizeof(mapNodes->map[indexDest].latency)); DEBUG_PC ("Computed Path Avail Bw: %f, Path Cost: %f, latency: %f", p->availCap, p->cost, p->delay); print_path(p); // If 1st SP satisfies the requirements from the req, STOP gboolean feasibleRoute = check_computed_path_feasability(s, p); if (feasibleRoute == TRUE) { DEBUG_PC("1st K-CSPF FEASIBLE, STOP!"); print_path (p); path->numPaths++; // Copy the serviceId DEBUG_PC("contextId: %s", s->serviceId.contextId); copy_service_id(&path->serviceId, &s->serviceId); // copy the service endpoints, in general, there will be 2 (point-to-point network connectivity services) for (gint i = 0; i < s->num_service_endpoints_id; i++) { struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[i]); struct service_endpoints_id_t* oEp = &(path->service_endpoints_id[i]); copy_service_endpoint_id(oEp, iEp); } path->num_service_endpoints_id = s->num_service_endpoints_id; // Copy the computed path struct path_t* targetedPath = &(path->paths[path->numPaths - 1]); duplicate_path_t(p, targetedPath); print_path_t (targetedPath); g_free(predecessors); g_free(p); g_free(mapNodes); return; } DEBUG_PC("1st CSPF COMPUTATION IS NOT FEASIBLE --> TRIGGER K COMPUTATIONS"); // Create A and B sets of paths to handle the YEN algorithm struct path_set_t* A = create_path_set(); struct path_set_t* B = create_path_set(); // Add the previously computed path into A->paths[0] duplicate_path(p, &A->paths[0]); A->numPaths++; g_free(predecessors); g_free(p); for (gint k = 1; k < MAX_KSP_VALUE; k++) { DEBUG_PC("------------ kth (%d) ---------------------", k); struct compRouteOutputItem_t* p = create_path_item(); duplicate_path(&A->paths[k - 1], p); // The spurNode ranges from near-end node of the first link to the near-end of the last link forming the kth path gint i = 0; struct compRouteOutputItem_t* rootPath = create_path_item(); for (i = 0; i < p->numRouteElements; i++) { struct nodes_t* spurNode = create_node(); struct nodes_t* nextSpurNode = create_node(); struct routeElement_t* re = &(p->routeElement[i]); // Create predecessors to store the computed path struct pred_t* predecessors = create_predecessors(); // Clear previous mapNodes, i.e. create it again g_free(mapNodes); mapNodes = create_map_node(); build_map_node(mapNodes, g); struct nodes_t* n = &re->aNodeId; duplicate_node_id(n, spurNode); n = &re->zNodeId; duplicate_node_id(n, nextSpurNode); DEBUG_PC("spurNode: %s --> nextSpurNode: %s", spurNode->nodeId, nextSpurNode->nodeId); // rootPath contains a set of links of A[k-1] from the source Node till the SpurNode -> NextSpurNode // Example: A[k-1] = {L1, L2, L3, L4}, i.e. " Node_a -- L1 --> Node_b -- L2 --> Node_c -- L3 --> Node_d -- L4 --> Node_e " // E.g., for the ith iteration if the spurNode = Node_c and NextSpurNode = Node_d; then rootPath = {L1, L2, L3} add_routeElement_path_back(re, rootPath); DEBUG_PC("rootPath:"); print_path(rootPath); // For all existing and computed paths p in A check if from the source to the NextSpurNode // the set of links matches with those contained in the rootPath // If YES, remove from the auxiliary graph the next link in p from NextSpurNode // Otherwise do nothing struct graph_t* gAux = create_graph(); // Baseline graph //build_graph (gAux); duplicate_graph(g, gAux); // Modified graph modify_targeted_graph(gAux, A, rootPath, spurNode); // Trigger the computation of the path from src to dst constrained to traverse all the links from src // to spurNode contained into rootPath over the resulting graph if (ksp_comp(predecessors, gAux, s, spurNode, rootPath) == -1) { DEBUG_PC("FAILED SP from %s via spurNode: %s to %s", iEp->device_uuid, spurNode->nodeId, eEp->device_uuid); g_free(nextSpurNode); g_free(spurNode); g_free(gAux); g_free(predecessors); continue; } DEBUG_PC("SUCCESFUL SP from %s via spurNode: %s to %s", iEp->device_uuid, spurNode->nodeId, eEp->device_uuid); // Create the node list from the predecessors struct compRouteOutputItem_t* newKpath = create_path_item(); build_path(newKpath, predecessors, s); DEBUG_PC("new K (for k: %d) Path is built", k); gint indexDest = get_map_index_by_nodeId(eEp->device_uuid, mapNodes); struct map_t* dst_map = &mapNodes->map[indexDest]; memcpy(&newKpath->cost, &dst_map->distance, sizeof(gdouble)); memcpy(&newKpath->availCap, &dst_map->avaiBandwidth, sizeof(dst_map->avaiBandwidth)); memcpy(&newKpath->delay, &dst_map->latency, sizeof(mapNodes->map[indexDest].latency)); DEBUG_PC("New PATH (@ kth: %d) ADDED to B[%d] - {Path Cost: %f, e2e latency: %f, bw: %f ", k, B->numPaths, newKpath->cost, newKpath->delay, newKpath->availCap); // Add the computed kth SP to the heap B duplicate_path(newKpath, &B->paths[B->numPaths]); B->numPaths++; DEBUG_PC("Number of B paths: %d", B->numPaths); g_free(newKpath); g_free(nextSpurNode); g_free(spurNode); g_free(gAux); g_free(predecessors); } // If B is empty then stops if (B->numPaths == 0) { DEBUG_PC("B does not have any path ... the stops kth computation"); break; } // Sort the potential paths contained in B by cost and latency and available bandwidth sort_path_set(B); // Add the lowest path into A[k] DEBUG_PC("-------------------------------------------------------------"); DEBUG_PC("To Add SP from B[0] to A[%d] --- Path Cost: %f, e2e Latency: %f", A->numPaths, B->paths[0].cost, B->paths[0].delay); duplicate_path(&B->paths[0], &A->paths[A->numPaths]); A->numPaths++; DEBUG_PC("A Set size: %d", A->numPaths); DEBUG_PC("-------------------------------------------------------------"); // Remove/pòp front element from the path set B (i.e. remove B[0]) pop_front_path_set(B); DEBUG_PC("B Set Size: %d", B->numPaths); } // Copy the serviceId copy_service_id(&path->serviceId, &s->serviceId); // copy the service endpoints, in general, there will be 2 (point-to-point network connectivity services) for (gint m = 0; m < s->num_service_endpoints_id; m++) { struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[m]); struct service_endpoints_id_t* oEp = &(path->service_endpoints_id[m]); copy_service_endpoint_id(oEp, iEp); } for (gint ksp = 1; ksp < A->numPaths; ksp++){ if (ksp >= MAX_KSP_VALUE) { DEBUG_PC("Number Requested paths (%d) REACHED - STOP", ksp); break; } gdouble feasibleRoute = check_computed_path_feasability(s, &A->paths[ksp]); if (feasibleRoute == TRUE) { DEBUG_PC("A[k-th%d] available: %f, pathCost: %f; latency: %f", ksp, A->paths[ksp].availCap, A->paths[ksp].cost, A->paths[ksp].delay); struct compRouteOutputItem_t* pathaux = &A->paths[ksp]; path->numPaths++; struct path_t* targetedPath = &path->paths[path->numPaths - 1]; duplicate_path_t(pathaux, targetedPath); print_path_t(targetedPath); remove_path_set(A); remove_path_set(B); return; } } remove_path_set(A); remove_path_set(B); // No paths found --> Issue DEBUG_PC("K-SP failed!!!"); comp_route_connection_issue_handler(path, s); return; } //////////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief Iterates over the list of network connectivity service requests * to compute their own paths fulfilling the constraints * * @param outputList * * @author Ricardo Martínez * @date 2022 */ ///////////////////////////////////////////////////////////////////////////////////////// void ksp_alg_execution_services(struct compRouteOutputList_t* outputList) { g_assert(outputList); g_assert(contextSet); g_assert(serviceList); DEBUG_PC("----- Starting the KSP Computation ------"); // Iterate over the list of requested network connectivity services for (gint i = 0; i < serviceList->numServiceList; i++) { struct service_t* service = &(serviceList->services[i]); DEBUG_PC("Starting the Computation for ServiceId: %s [ContextId: %s]", service->serviceId.service_uuid, service->serviceId.contextId); struct compRouteOutput_t* pathService = &(outputList->compRouteConnection[i]); // check endpoints of the service are different (PE devices/nodes are different) if (same_src_dst_pe_nodeid(service) == 0) { DEBUG_PC("PEs are the same... no path computation"); comp_route_connection_issue_handler(pathService, service); outputList->numCompRouteConnList++; continue; } // get the graph associated to the contextId in the contextSet, if no then error struct graph_t* g = get_graph_by_contextId(contextSet, service->serviceId.contextId); if (g == NULL) { DEBUG_PC("The targeted contextId is NOT in the ContextSet ... then NO graph"); comp_route_connection_issue_handler(pathService, service); outputList->numCompRouteConnList++; continue; } alg_comp(service, pathService, g); outputList->numCompRouteConnList++; // for each network connectivity service, a single computed path (out of the KCSP) is retuned // If path is found, then the selected resources must be pre-assigned into the context information if (pathService->noPathIssue == NO_PATH_CONS_ISSUE) { continue; } struct path_t* path = &(pathService->paths[pathService->numPaths - 1]); allocate_graph_resources(path, service, g); allocate_graph_reverse_resources(path, service, g); print_graph(g); } return; } //////////////////////////////////////////////////////////////////////////////////////// /** * @file pathComp_ksp.c * @brief handles the path computation triggering k-cspf algorithm * * @param compRouteOutput * * @author Ricardo Martínez * @date 2022 */ ///////////////////////////////////////////////////////////////////////////////////////// gint pathComp_ksp_alg(struct compRouteOutputList_t * routeConnList) { g_assert(routeConnList); DEBUG_PC ("================================================================"); DEBUG_PC ("=========================== KSP ========================="); DEBUG_PC ("================================================================"); // increase the number of Path Comp. Intents numPathCompIntents++; gint http_code = HTTP_CODE_OK; // timestamp t0 struct timeval t0; gettimeofday(&t0, NULL); // Allocate memory for the context contextSet = create_contextSet(); // Build up the contextSet (>= 1) build_contextSet(contextSet); print_contextSet(contextSet); #if 1 //Triggering the path computation for each specific network connectivity service ksp_alg_execution_services (routeConnList); // -- timestamp t1 struct timeval t1, delta; gettimeofday(&t1, NULL); delta.tv_sec = t1.tv_sec - t0.tv_sec; delta.tv_usec = t1.tv_usec - t0.tv_usec; delta = tv_adjust(delta); numSuccesPathComp++; update_stats_ksp_path_comp(routeConnList, delta); print_path_connection_list(routeConnList); #endif g_free(contextSet); return http_code; }