pathComp_tools.c

 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void destroy_context(struct context_t* c) {
	g_assert(c);
	g_free(c);
	return;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Excecution Dijkstra algorithm
 *
 *  @param srcMapIndex
 *  @param dstMapIndex
 *	@param g
 *	@param s
 *  @param mapNodes
 *  @param SN
 *  @param RP
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void dijkstra(gint srcMapIndex, gint dstMapIndex, struct graph_t* g, struct service_t* s, 
	struct map_nodes_t* mapNodes, struct nodes_t* SN, struct compRouteOutputItem_t* RP,
	guint arg) {
	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;
	mapNodes->map[srcMapIndex].power = 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;
	nodeItem->power = 0.0;
	duplicate_node_id(&mapNodes->map[srcMapIndex].verticeId, &nodeItem->node);

	// Select the optimization process
	if (arg & ENERGY_EFFICIENT_ARGUMENT)
		Q = g_list_insert_sorted(Q, nodeItem, sort_by_energy);
	// more "if" according to different optimization criteria ...
	else
		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, arg);
			(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(g_steal_pointer(&S), g_free);
			g_list_free_full(g_steal_pointer(&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, arg);
			(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(g_steal_pointer(&S), g_free);
	g_list_free_full(g_steal_pointer(&Q), g_free);
	return;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief KSP computation using Dijkstra algorithm
 *
 *  @param pred
 *  @param g
 *	@param s
  *	@param SN
 *	@param RP
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@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, 
	struct map_nodes_t* mapNodes, guint arg) {
	g_assert(pred); g_assert(g); g_assert(s);

	DEBUG_PC("Source: %s -- Destination: %s", s->service_endpoints_id[0].device_uuid, s->service_endpoints_id[1].device_uuid);

	// 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;
	}

	//DEBUG_PC("srcMapIndex: %d (node: %s)", srcMapIndex, mapNodes->map[srcMapIndex].verticeId.nodeId);
	//DEBUG_PC("dstMapIndex: %d (node: %s)", dstMapIndex, mapNodes->map[dstMapIndex].verticeId.nodeId);

	// Compute the shortest path route
	dijkstra(srcMapIndex, dstMapIndex, g, s, mapNodes, SN, RP, arg);

	// 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_tools.c
 * 	@brief set the path parameters (e.g., latency, cost, power, ...) to an under-constructed
 * path from the computed map vertex
 *
 *  @param p
 *  @param mapV
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void set_path_attributes(struct compRouteOutputItem_t* p, struct map_t* mapV) {
	g_assert(p); g_assert(mapV);
	memcpy(&p->cost, &mapV->distance, sizeof(gdouble));
	memcpy(&p->availCap, &mapV->avaiBandwidth, sizeof(mapV->avaiBandwidth));
	memcpy(&p->delay, &mapV->latency, sizeof(mapV->latency));
	memcpy(&p->power, &mapV->power, sizeof(gdouble));
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief K-CSPF algorithm execution (YEN algorithm)
 *
 *  @param s
 *  @param path
 *  @param g
 *  @param optimization_flag
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void alg_comp(struct service_t* s, struct compRouteOutput_t* path, struct graph_t* g, guint arg) {
	g_assert(s); g_assert(path); g_assert(g);

	// create map of devices/nodes to handle the path computation using the context
	struct map_nodes_t* 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, mapNodes, arg);
	if (done == -1) {
		DEBUG_PC("NO PATH for %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);
	gint indexDest = get_map_index_by_nodeId(eEp->device_uuid, mapNodes);
	struct map_t* dst_map = &mapNodes->map[indexDest];
	// Get the delay and cost
	set_path_attributes(p, dst_map);		

	// Add the computed path, it may be a not feasible path, but at the end it is
	// checked all the feasible paths, and select the first one
	print_path(p);
	
	// 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 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;

	DEBUG_PC("COMPUTE UP TO K Feasible Paths A[%d]", MAX_KSP_VALUE);	
	// Create A and B sets of paths to handle the YEN algorithm
	struct path_set_t *A = create_path_set(), *B = create_path_set();
	// Add 1st 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(), *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("\n");
			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();
			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, mapNodes, arg) == -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];
			set_path_attributes(newKpath, dst_map);
			DEBUG_PC("New PATH (@ kth: %d) ADDED to B[%d] - {Path Cost: %f, e2e latency: %f, bw: %f, Power: %f ", k, B->numPaths, newKpath->cost, 
													newKpath->delay, newKpath->availCap, newKpath->power);
			// 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 B paths according to different optimization parameters
		sort_path_set(B, arg);
		// Add the lowest path into A[k]		
		DEBUG_PC("-------------------------------------------------------------");
		DEBUG_PC("Append SP for B[0] to A[%d] --- Cost: %f, Latency: %f, Power: %f", A->numPaths, B->paths[0].cost, 
																				B->paths[0].delay, B->paths[0].power);
		duplicate_path(&B->paths[0], &A->paths[A->numPaths]);
		A->numPaths++;
		DEBUG_PC("A Set size: %d", A->numPaths);
		DEBUG_PC("-------------------------------------------------------------");

		// Remove/Pop 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 = &(s->service_endpoints_id[m]);
		copy_service_endpoint_id(oEp, iEp);
	}

	// Print all the paths i A
	for (gint h = 0; h < A->numPaths; h++) {
		DEBUG_PC("================== A[%d] =======================", h);
		print_path(&A->paths[h]);
	}
	DEBUG_PC("Number of paths: %d", path->numPaths);
	// For all the computed paths in A, pick the one being feasible wrt the service constraints
	for (gint ksp = 0; 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[%d] available: %f, pathCost: %f; latency: %f, Power: %f", ksp, A->paths[ksp].availCap, A->paths[ksp].cost, A->paths[ksp].delay, A->paths[ksp].power);
			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;
}