Skip to content
Snippets Groups Projects
pathComp_tools.c 119 KiB
Newer Older
	
	// Remove the edge
	//DEBUG_PC ("Start Removing %s --> %s from Graph", e->aNodeId.nodeId, e->zNodeId.nodeId);	
	struct targetNodes_t *v = &(g->vertices[verticeIndex].targetedVertices[targetedVerticeIndex]);	
	for (gint j = edgeIndex; j < v->numEdges; j++) {	
		struct edges_t *e1 = &(v->edges[j]);
		struct edges_t *e2 = &(v->edges[j+1]);		
		duplicate_edge (e1, e2);
	}
	v->numEdges --;
	DEBUG_PC ("Number of Edges between %s and %s is %d", e->aNodeId.nodeId, e->zNodeId.nodeId, v->numEdges);	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief create the pointer for keeping a set of the paths (struct compRouteOutput_t)
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
struct path_set_t * create_path_set () {
	struct path_set_t * p = g_malloc0 (sizeof (struct path_set_t));
martinezric's avatar
martinezric committed
	if (p == NULL) {
		DEBUG_PC ("Memory allocation problem");
		exit (-1);		
	}
	return p;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Remove the path set
 *
 * @param p
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2021
 */
 /////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void remove_path_set(struct path_set_t* p) {
	g_assert(p); g_free(p);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Create map of nodes to handle the path computation
 *
 * 	@param mapN
 *  @param g
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void build_map_node (struct map_nodes_t *mapN, struct graph_t *g) {
	//DEBUG_PC ("Construction of the Map of Nodes");               
martinezric's avatar
martinezric committed
    for (gint i = 0; i < g->numVertices; i++) {	
		duplicate_node_id (&g->vertices[i].verticeId, &mapN->map[i].verticeId);
        mapN->map[i].distance = INFINITY_COST;
        mapN->map[i].avaiBandwidth = 0.0;
        mapN->map[i].latency = INFINITY_COST;
martinezric's avatar
martinezric committed
		mapN->map[i].power = INFINITY_COST;
        mapN->numMapNodes++;
    }
    //DEBUG_PC ("mapNodes formed by %d Nodes", mapN->numMapNodes);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Allocate memory for path of struct compRouteOutputList_t *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
struct compRouteOutputList_t * create_route_list () {
	struct compRouteOutputList_t *p = g_malloc0 (sizeof (struct compRouteOutputList_t));
martinezric's avatar
martinezric committed
	if (p == NULL) {
		DEBUG_PC ("Memory Allocation Problem");
		exit (-1);
	}
	return p;
}

martinezric's avatar
martinezric committed
////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Copy all the attributes defining a path
 *
 * @param dst_path
 * @param src_path
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void copy_path(struct path_t* dst_path, struct path_t* src_path) {
	g_assert(dst_path);
	g_assert(src_path);

	// Path capacity
	dst_path->path_capacity.unit = src_path->path_capacity.unit;
	memcpy(&dst_path->path_capacity.value, &src_path->path_capacity.value, sizeof(gdouble));

	// Path latency
	memcpy(&dst_path->path_latency.fixed_latency, &src_path->path_latency.fixed_latency, sizeof(gdouble));

	// Path cost
	duplicate_string(dst_path->path_cost.cost_name, src_path->path_cost.cost_name);
	memcpy(&dst_path->path_cost.cost_value, &src_path->path_cost.cost_value, sizeof(gdouble));
	memcpy(&dst_path->path_cost.cost_algorithm, &src_path->path_cost.cost_algorithm, sizeof(gdouble));

	// Path links
	dst_path->numPathLinks = src_path->numPathLinks;
	for (gint i = 0; i < dst_path->numPathLinks; i++) {
		struct pathLink_t* dPathLink = &(dst_path->pathLinks[i]);
		struct pathLink_t* sPathLink = &(src_path->pathLinks[i]);

		duplicate_string(dPathLink->linkId, sPathLink->linkId);
		duplicate_string(dPathLink->aDeviceId, sPathLink->aDeviceId);
		duplicate_string(dPathLink->zDeviceId, sPathLink->zDeviceId);
		duplicate_string(dPathLink->aEndPointId, sPathLink->aEndPointId);
		duplicate_string(dPathLink->zEndPointId, sPathLink->zEndPointId);

		duplicate_string(dPathLink->topologyId.contextId, sPathLink->topologyId.contextId);
		duplicate_string(dPathLink->topologyId.topology_uuid, sPathLink->topologyId.topology_uuid);

		dPathLink->numLinkTopologies = sPathLink->numLinkTopologies;
		for (gint j = 0; j < dPathLink->numLinkTopologies; j++) {
			struct linkTopology_t* dLinkTop = &(dPathLink->linkTopologies[j]);
			struct linkTopology_t* sLinkTop = &(sPathLink->linkTopologies[j]);

			duplicate_string(dLinkTop->topologyId, sLinkTop->topologyId);
		}
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Duplicate the route output instance
 *
 * @param dst_ro
 * @param src_ro
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void duplicate_compRouteOuput(struct compRouteOutput_t* dst_ro, struct compRouteOutput_t* src_ro) {
	g_assert(dst_ro); g_assert(src_ro); 
		
	// Copy the serviceId
	copy_service_id(&dst_ro->serviceId, &src_ro->serviceId);
	dst_ro->num_service_endpoints_id = src_ro->num_service_endpoints_id;

	for (gint j = 0; j < dst_ro->num_service_endpoints_id; j++) {
		struct service_endpoints_id_t* iEp = &(src_ro->service_endpoints_id[j]);
		struct service_endpoints_id_t* oEp = &(dst_ro->service_endpoints_id[j]);
		copy_service_endpoint_id(oEp, iEp);
	}

	// Copy paths
	dst_ro->numPaths = src_ro->numPaths;
	for (gint j = 0; j < dst_ro->numPaths; j++) {
		struct path_t* dst_path = &(dst_ro->paths[j]);
		struct path_t* src_path = &(src_ro->paths[j]);
		copy_path(dst_path, src_path);
	}
	// copy no path issue value
	dst_ro->noPathIssue = src_ro->noPathIssue;
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Duplicate the computation route output list
 * 
 * @param dst
 * @param src
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void duplicate_route_list(struct compRouteOutputList_t* dst, struct compRouteOutputList_t* src) {
	g_assert(src); g_assert(dst);

	dst->numCompRouteConnList = src->numCompRouteConnList;
	dst->compRouteOK = src->compRouteOK;
	memcpy(&dst->compRouteConnAvBandwidth, &src->compRouteConnAvBandwidth, sizeof(gdouble));
	memcpy(&dst->compRouteConnAvPathLength, &src->compRouteConnAvPathLength, sizeof(gdouble));
	for (gint i = 0; i < src->numCompRouteConnList; i++) {
		struct compRouteOutput_t* src_ro = &(src->compRouteConnection[i]);
		struct compRouteOutput_t* dst_ro = &(dst->compRouteConnection[i]);
		duplicate_compRouteOuput(dst_ro, src_ro);
	}	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Allocate memory for path of struct compRouteOutputItem_t *
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
struct compRouteOutputItem_t *create_path_item () {
	struct compRouteOutputItem_t *p = g_malloc0 (sizeof (struct compRouteOutputItem_t));
	if (p == NULL) 	{
		DEBUG_PC ("Memory Allocation Problem");
		exit (-1);
	}
	return p;	
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
martinezric's avatar
martinezric committed
 * 	@brief Sort the set of paths the AvailBw, Cost and Delay
martinezric's avatar
martinezric committed
 *  @params args
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void sort_path_set(struct path_set_t* setP, guint args) {
martinezric's avatar
martinezric committed
	// Sort the paths contained in setP by:
	// 1st Criteria: The path cost (maybe bound to link distance)
	// 2nd Criteria: The consumed path power 
	// 3nd Criteria: The path latency
	// 3rd Criteria: The available Bw
	float epsilon = 0.1;

	for (gint i = 0; i < setP->numPaths; i++) {
		for (gint j = 0; j < (setP->numPaths - i - 1); j++)	{
			struct compRouteOutputItem_t* path1 = &setP->paths[j];
martinezric's avatar
martinezric committed
			struct compRouteOutputItem_t* path2 = &setP->paths[j + 1];			
			struct compRouteOutputItem_t* pathTmp = create_path_item();
martinezric's avatar
martinezric committed
			//////////////////////// Criterias ////////////////////////////////////////
			// 1st Criteria (Cost)
			if (path2->cost < path1->cost) {
				duplicate_path(path1, pathTmp);
				duplicate_path(path2, path1);
				duplicate_path(pathTmp, path2);
				g_free(pathTmp);
				continue;
			}
martinezric's avatar
martinezric committed
			if (path2->cost == path1->cost) {
				// 2nd Criteria (Energy)
				if (args & ENERGY_EFFICIENT_ARGUMENT) {
					if (path2->power < path1->power) {
						duplicate_path(path1, pathTmp);
						duplicate_path(path2, path1);
						duplicate_path(pathTmp, path2);
						g_free(pathTmp);
						continue;
					}
					else {	  // path1->power < path2->power
martinezric's avatar
martinezric committed
				}
				else { // No enery efficient argument
					// 3rd Criteria (latency)
					if (path2->delay < path1->delay) {
						duplicate_path(path1, pathTmp);
						duplicate_path(path2, path1);
						duplicate_path(pathTmp, path2);
						g_free(pathTmp);
						continue;
					}
martinezric's avatar
martinezric committed
					else if (path1->delay < path2->delay) {
martinezric's avatar
martinezric committed
					else { // path1->delay == path2->delay
						// 4th Criteria (available bw)
						if (path2->availCap > path1->availCap) {
							duplicate_path(path1, pathTmp);
							duplicate_path(path2, path1);
							duplicate_path(pathTmp, path2);
							g_free(pathTmp);
							continue;
						}
						else {
							g_free(pathTmp);
							continue;
						}
					}
martinezric's avatar
martinezric committed
			}
			else {	// path1->cost < path2->cost
				g_free(pathTmp);
				continue;
			}				
		}
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Remove first element from the path sets 
 *
 *	@params setP
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void pop_front_path_set (struct path_set_t *setP) {
	for (gint j = 0; j < setP->numPaths - 1; j++) {
		struct compRouteOutputItem_t *path1 = &setP->paths[j];
		struct compRouteOutputItem_t *path2 = &setP->paths[j+1];		
		duplicate_path (path2, path1);		
	}
	setP->numPaths--;	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Add routeElement to the back of the path
 *
 * 	@param rE
 * 	@param p
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void add_routeElement_path_back (struct routeElement_t *rE, struct compRouteOutputItem_t *p) {
	//DEBUG_PC ("p->numRouteElements: %d", p->numRouteElements);
	p->numRouteElements++;
	gint index = p->numRouteElements - 1;
	
	struct nodes_t *pn = &(p->routeElement[index].aNodeId);
	struct nodes_t *rEn = &(rE->aNodeId);
	
	// duplicate aNodeId
	duplicate_node_id (rEn, pn);	
	pn = &(p->routeElement[index].zNodeId);
	rEn = &(rE->zNodeId);
	duplicate_node_id (rEn, pn);
	duplicate_string(p->routeElement[index].aEndPointId, rE->aEndPointId);
	duplicate_string(p->routeElement[index].zEndPointId, rE->zEndPointId);
	duplicate_string(p->routeElement[index].linkId, rE->linkId);
	duplicate_string(p->routeElement[index].aTopologyId, rE->aTopologyId);
	duplicate_string(p->routeElement[index].zTopologyId, rE->zTopologyId);
	return;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief This function compares ap and rootPath. If all the links are equal between both ap and rootPath till the sN, then the link from sN to next node 
 * 	ap is returned
 * 
 * @params ap
 * @params p
 * @params sN
 * @params e
 * 
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gboolean matching_path_rootPath (struct compRouteOutputItem_t *ap, struct compRouteOutputItem_t *rootPath, struct nodes_t *sN, struct edges_t *e) {
	gint j = 0;
	gboolean ret = FALSE;
	while ((j < ap->numRouteElements) && (j < rootPath->numRouteElements)) {
		if ((memcmp (ap->routeElement[j].aNodeId.nodeId, rootPath->routeElement[j].aNodeId.nodeId, sizeof (ap->routeElement[j].aNodeId.nodeId)) == 0) &&
			//(memcmp (ap->routeElement[j].zNodeId.nodeId, rootPath->routeElement[j].zNodeId.nodeId, sizeof (ap->routeElement[j].zNodeId.nodeId)) != 0) &&
			(memcmp (sN->nodeId, rootPath->routeElement[j].aNodeId.nodeId, sizeof (ap->routeElement[j].aNodeId.nodeId)) == 0)) {						
			duplicate_node_id (&ap->routeElement[j].aNodeId, &e->aNodeId);
			duplicate_node_id (&ap->routeElement[j].zNodeId, &e->zNodeId);
			duplicate_string(e->aEndPointId, ap->routeElement[j].aEndPointId);
			duplicate_string(e->zEndPointId, ap->routeElement[j].zEndPointId);
			duplicate_string(e->linkId, ap->routeElement[j].linkId);
			return TRUE;			
		}		
		if ((memcmp (ap->routeElement[j].aNodeId.nodeId, rootPath->routeElement[j].aNodeId.nodeId, sizeof (ap->routeElement[j].aNodeId.nodeId)) == 0) && 
			(memcmp (ap->routeElement[j].zNodeId.nodeId, rootPath->routeElement[j].zNodeId.nodeId, sizeof (ap->routeElement[j].zNodeId.nodeId)) == 0)) {
			j++;			
			continue;			
		}
		
		if ((memcmp (ap->routeElement[j].aNodeId.nodeId, rootPath->routeElement[j].aNodeId.nodeId, sizeof (ap->routeElement[j].aNodeId.nodeId)) != 0) || 
			(memcmp (ap->routeElement[j].zNodeId.nodeId, rootPath->routeElement[j].zNodeId.nodeId, sizeof (ap->routeElement[j].zNodeId.nodeId)) != 0)) {
			//DEBUG_PC ("ap and rootPath not in the same path");
			return ret;
		}
	}	
	return ret;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief This function is used to modify the graph to be used for running the subsequent SP computations acording to the YEN algorithm principles
 * 
 * @params g
 * @params A
 * @params rootPath
 * @params spurNode
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void modify_targeted_graph (struct graph_t *g, struct path_set_t *A, struct compRouteOutputItem_t * rootPath, struct nodes_t * spurNode) {
	//DEBUG_PC ("Modify the Targeted graph according to the Yen algorithm principles");
martinezric's avatar
martinezric committed
	for (gint j = 0; j < A->numPaths; j++) {
		struct compRouteOutputItem_t *ap = &A->paths[j];
martinezric's avatar
martinezric committed
		struct edges_t *e = create_edge();
		gboolean ret =  FALSE;
		ret = matching_path_rootPath (ap, rootPath, spurNode, e);		
		if (ret == TRUE) {
martinezric's avatar
martinezric committed
			DEBUG_PC ("Removal %s[%s] --> %s[%s] from the graph", e->aNodeId.nodeId, e->aEndPointId, e->zNodeId.nodeId, e->aEndPointId);
			remove_edge_from_graph (g, e);
			//DEBUG_PC ("Print Resulting Graph");
martinezric's avatar
martinezric committed
			print_graph (g);
martinezric's avatar
martinezric committed
		if (ret == FALSE) {
			g_free (e);
			continue;
		}						
	}	
	return;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Supporting fucntion to Check if a nodeId is already in the items of a given GList
 * 
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint find_nodeId (gconstpointer data, gconstpointer userdata)
{
     /** check values */
     g_assert(data != NULL);
     g_assert(userdata != NULL);
 
     struct nodeItem_t *SNodeId = (struct nodeItem_t *)data;
     guchar * nodeId = (guchar *)userdata; 
     
     //DEBUG_PC ("SNodeId (%s) nodeId (%s)", SNodeId->node.nodeId, nodeId);   
        
     if (!memcmp(SNodeId->node.nodeId, nodeId, strlen (SNodeId->node.nodeId)))
     {
		return (0);
     }
    return -1;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Explores the link between u and v
 * 
 *  @param u
 *  @param v 
 *	@param g
 *	@param s
 *  @param S
 *  @param Q
 *	@param mapNodes
 * 
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint check_link (struct nodeItem_t *u, gint indexGraphU, gint indexGraphV, struct graph_t *g, 
martinezric's avatar
martinezric committed
				struct service_t *s, GList **S, GList **Q, struct map_nodes_t *mapNodes, 
				guint arg) { 
	g_assert(g); g_assert(s); g_assert(mapNodes);

	struct targetNodes_t *v = &(g->vertices[indexGraphU].targetedVertices[indexGraphV]);	
martinezric's avatar
martinezric committed
    DEBUG_PC("Explored Link %s => %s)", u->node.nodeId, v->tVertice.nodeId);
	//DEBUG_PC("\t %s => %s", u->node.nodeId, v->tVertice.nodeId);	
    
    // v already explored in S? then, discard it
    GList *found = g_list_find_custom (*S, v->tVertice.nodeId, find_nodeId);
    if (found != NULL) {
martinezric's avatar
martinezric committed
        DEBUG_PC ("v (%s) in S, Discard", v->tVertice.nodeId);        
        return 0;
    }

	// Get the set of constraints imposed by the service
	struct path_constraints_t* path_constraints = get_path_constraints(s);
martinezric's avatar
martinezric committed
    gdouble distance_through_u = INFINITY_COST ,latency_through_u = INFINITY_COST, power_through_u = INFINITY_COST;
	gint i = 0, foundAvailBw = 0;
    // BANDWIDTH requirement to be fulfilled on EDGE u->v        
    gdouble edgeAvailBw = 0.0, edgeTotalBw = 0.0;
    for (i = 0; i < v->numEdges; i++) {        
        struct edges_t *e = &(v->edges[i]);
		memcpy (&edgeAvailBw, &(e->availCap), sizeof (gdouble));
martinezric's avatar
martinezric committed
		memcpy(&edgeTotalBw, &(e->totalCap), sizeof(gdouble));
		DEBUG_PC("EDGE %s[%s] => %s[%s]", u->node.nodeId, e->aEndPointId, v->tVertice.nodeId, e->zEndPointId);
        //DEBUG_PC ("\t %s[%s] =>", u->node.nodeId, e->aEndPointId);
		//DEBUG_PC("\t => %s[%s]", v->tVertice.nodeId, e->zEndPointId);
		DEBUG_PC("\t AvailBw: %f, TotalBw: %f", edgeAvailBw, edgeTotalBw);
        // Check Service Bw constraint
		if ((path_constraints->bw == TRUE) && (edgeAvailBw < path_constraints->bwConstraint))
			continue;
		else {
			foundAvailBw = 1;
			break;
martinezric's avatar
martinezric committed
	// BW constraint NOT MET, then DISCARD edge
    if ((path_constraints->bw == TRUE) && (foundAvailBw == 0)) {
        DEBUG_PC ("AvailBw: %f < path_constraint: %f -- Discard Edge", edgeAvailBw, path_constraints->bwConstraint);
		g_free(path_constraints);
        return 0;    
    } 

    gint indexEdge = i; // get the index for the explored edge
    // Update distance, latency and availBw through u to reach v
    gint map_uIndex = get_map_index_by_nodeId (u->node.nodeId, mapNodes);
	struct map_t *u_map = &mapNodes->map[map_uIndex];
    distance_through_u = u_map->distance + v->edges[indexEdge].cost;
martinezric's avatar
martinezric committed
    latency_through_u = u_map->latency + v->edges[indexEdge].delay;
	// Consumed power at v through u is the sum
	// 1. Power from src to u
	// 2. Power-idle at node u
	// 3. power consumed over the edge between u and v, i.e. energy*usedBw
	power_through_u = u_map->power + g->vertices[indexGraphU].power_idle + ((edgeTotalBw - edgeAvailBw + path_constraints->bwConstraint) * (v->edges[indexEdge].energy));
    gdouble availBw_through_u = 0.0;

	// ingress endpoint (u) is the src of the request
    if (strcmp (u->node.nodeId, s->service_endpoints_id[0].device_uuid) == 0) {
        //DEBUG_PC ("AvailBw %f on %s --> %s", edgeAvailBw, u->node.nodeId, v->tVertice.nodeId);        
        memcpy (&availBw_through_u, &edgeAvailBw, sizeof (gdouble));        
    }
    else {
        // Get the minimum available bandwidth between the src-->u and the new added edge u-->v
        //DEBUG_PC ("Current AvailBw: %f from src to %s", u_map->avaiBandwidth, u->node.nodeId);
        //DEBUG_PC ("AvailBw: %f %s --> %s", edgeAvailBw, u->node.nodeId, v->tVertice.nodeId);
        if (u_map->avaiBandwidth <= edgeAvailBw) {
            memcpy (&availBw_through_u, &u_map->avaiBandwidth, sizeof (gdouble));    
		}
		else {
			memcpy (&availBw_through_u, &edgeAvailBw, sizeof (gdouble));
		} 
    }     
martinezric's avatar
martinezric committed
    // Relax the link according to the pathCost, latency, and energy
    gint map_vIndex = get_map_index_by_nodeId (v->tVertice.nodeId, mapNodes);
	struct map_t *v_map = &mapNodes->map[map_vIndex];
    // If cost dist (u, v) > dist (src, v) relax the link
    if (distance_through_u > v_map->distance) {
        //DEBUG_PC ("dist(src, u) + dist(u, v): %f > dist (src, v): %f --> Discard Link", distance_through_u, v_map->distance);  
        return 0;
    }
martinezric's avatar
martinezric committed
	// If energy consumption optimization is requested
	if (arg & ENERGY_EFFICIENT_ARGUMENT) {
		if (distance_through_u == v_map->distance) {
			if (power_through_u > v_map->power) {
				DEBUG_PC("Energy (src -> u + u -> v: %f (Watts) >Energy (src, v): %f (Watts)--> DISCARD LINK", power_through_u, v_map->power);
				return 0;
			}
			// same energy consumption, consider latency
			if ((power_through_u == v_map->power) && (latency_through_u > v_map->latency)) {
				return 0;
			}
			if ((power_through_u == v_map->power) && (latency_through_u == v_map->latency) && (availBw_through_u < v_map->avaiBandwidth)) {
				return 0;
			}
		}
	} // No optimization, rely on latency and available e2e bandwidth
	else {
		// If dist (src, u) + dist (u, v) = current dist(src, v), then use the latency as discarding criteria
		if ((distance_through_u == v_map->distance) && (latency_through_u > v_map->latency)) {
			//DEBUG_PC ("dist(src, u) + dist(u,v) = current dist(src, v), but latency (src,u) + latency (u, v) > current latency (src, v)");          
			return 0;
		}
		// If dist (src, u) + dist (u,v) == current dist(src, v) AND latency (src, u) + latency (u, v) == current latency (src, v), the available bandwidth is the criteria
		if ((distance_through_u == v_map->distance) && (latency_through_u == v_map->latency) && (availBw_through_u < v_map->avaiBandwidth)) {
			return 0;
		}
	}
    DEBUG_PC ("%s --> %s Relaxed", u->node.nodeId, v->tVertice.nodeId);
martinezric's avatar
martinezric committed
    DEBUG_PC ("\t AvailBw: %f Mb/s, Cost: %f, Latency: %f ms, Energy: %f Watts", availBw_through_u, distance_through_u, latency_through_u, power_through_u);
    
    // Update Q list -- 
    struct nodeItem_t *nodeItem = g_malloc0 (sizeof (struct nodeItem_t));
    if (nodeItem == NULL) {
		DEBUG_PC ("memory allocation failed\n");
		exit (-1);    
    }    
    nodeItem->distance = distance_through_u;
	memcpy(&nodeItem->distance, &distance_through_u, sizeof(gdouble));		     
	memcpy(&nodeItem->latency, &latency_through_u, sizeof(gdouble));
martinezric's avatar
martinezric committed
	memcpy(&nodeItem->power, &power_through_u, sizeof(gdouble));
	duplicate_node_id (&v->tVertice, &nodeItem->node);	
	// add node to the Q list
martinezric's avatar
martinezric committed
	if (arg & ENERGY_EFFICIENT_ARGUMENT) {
		*Q = g_list_insert_sorted(*Q, nodeItem, sort_by_energy);
	}
	else
		*Q = g_list_insert_sorted (*Q, nodeItem, sort_by_distance);
martinezric's avatar
martinezric committed
	// Update the mapNodes for the specific reached tv   
    v_map->distance = distance_through_u;
	memcpy(&v_map->distance, &distance_through_u, sizeof(gdouble));
    memcpy (&v_map->avaiBandwidth, &availBw_through_u, sizeof (gdouble));
    memcpy (&v_map->latency, &latency_through_u, sizeof (gdouble));
martinezric's avatar
martinezric committed
	memcpy(&v_map->power, &power_through_u, sizeof(gdouble));
    // Duplicate the predecessor edge into the mapNodes 
	struct edges_t *e1 = &(v_map->predecessor);
	struct edges_t *e2 = &(v->edges[indexEdge]);
martinezric's avatar
martinezric committed
	duplicate_edge(e1, e2);	
	DEBUG_PC ("u->v Edge: %s(%s) --> %s(%s)", e2->aNodeId.nodeId, e2->aEndPointId, e2->zNodeId.nodeId, e2->zEndPointId);
martinezric's avatar
martinezric committed
	//DEBUG_PC("v-pred aTopology: %s", e2->aTopologyId);
	DEBUG_PC("v-pred zTopology: %s", e2->zTopologyId);

    // Check whether v is dstPEId
martinezric's avatar
martinezric committed
	//DEBUG_PC ("Targeted dstId: %s", s->service_endpoints_id[1].device_uuid);
	//DEBUG_PC ("nodeId added to the map: %s", v_map->verticeId.nodeId);
	//DEBUG_PC ("Q Length: %d", g_list_length(*Q));
	g_free(path_constraints);
    return 0;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Check the feasability of a path wrt the constraints imposed by the request in terms of latency
 * 
 *  @param s
 *	@param p
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gboolean check_computed_path_feasability (struct service_t *s, struct compRouteOutputItem_t* p) {	
	float epsilon = 0.0000001;
	struct path_constraints_t* pathCons = get_path_constraints(s);
	gboolean ret = TRUE;
	if (pathCons->latency == TRUE) {
		if ((pathCons->latencyConstraint - p->delay > 0.0) || (fabs(pathCons->latencyConstraint - p->delay) < epsilon)) {
			DEBUG_PC("Computed Path (latency: %f) is feasible wrt Connection Demand: %f", p->delay, pathCons->latencyConstraint);
		}
		else {
			DEBUG_PC("Computed Path (latency: %f) is NOT feasible wrt Connection Demand: %f", p->delay, pathCons->latencyConstraint);
			g_free(pathCons);
			return FALSE;
		}
	}
martinezric's avatar
martinezric committed
	// Other constraints...		
	g_free(pathCons);
	return ret;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Sorting the GList Q items by distance 
 * 
martinezric's avatar
martinezric committed
 * @param a
 * @param b
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
gint sort_by_distance (gconstpointer a, gconstpointer b) {
	//DEBUG_PC ("sort by distance a and b");	
	g_assert(a != NULL);
	g_assert(b != NULL);
	
	//DEBUG_PC ("sort by distance a and b");	  
	struct nodeItem_t *node1 = (struct nodeItem_t *)a;
	struct nodeItem_t *node2 = (struct nodeItem_t *)b;
	g_assert (node1);
	g_assert (node2);
	 
	//DEBUG_PC ("a->distance %u; b->distance %u", node1->distance, node2->distance);
	//DEBUG_PC("a->latency: %f; b->latency: %f", node1->latency, node2->latency);
	//1st criteria, sorting by lowest distance
	if (node1->distance > node2->distance)
		return 1;
	else if (node1->distance < node2->distance)
		return 0;
martinezric's avatar
martinezric committed
	if (node1->distance == node2->distance) {
		if (node1->latency > node2->latency)
			return 1;
		else if (node1->latency <= node2->latency)
			return 0;
	}
martinezric's avatar
martinezric committed
	return 0;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Sorting the GList Q items by distance
 * 
 * @param a
 * @param b
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
gint sort_by_energy(gconstpointer a, gconstpointer b) {	
	g_assert(a != NULL);
	g_assert(b != NULL);

	//DEBUG_PC ("sort by distance a and b");	  
	struct nodeItem_t* node1 = (struct nodeItem_t*)a;
	struct nodeItem_t* node2 = (struct nodeItem_t*)b;
	g_assert(node1);
	g_assert(node2);
	
	//1st criteria: sorting by lowest distance
	if (node1->distance > node2->distance)
		return 1;
	if (node1->distance < node2->distance)
		return 0;

	// 2nd Criteria: sorting by the lowest energy
	if (node1->power > node2->power)
		return 1;
	if (node1->power < node1->power)
		return 0;

	// 3rd Criteria: by the latency 
	if (node1->latency > node2->latency)
		return 1;
	if (node1->latency <= node2->latency)
		return 0;
	return 0;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Allocate memory for graph
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
struct graph_t * create_graph () {
	struct graph_t * g = g_malloc0 (sizeof (struct graph_t));
martinezric's avatar
martinezric committed
	if (g == NULL) {
		DEBUG_PC ("Memory Allocation Problem");
		exit (-1);
	}
	return g;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Allocate memory for mapNodes
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
struct map_nodes_t * create_map_node ()	 {
	struct map_nodes_t * mN = g_malloc0 (sizeof (struct map_nodes_t));
martinezric's avatar
martinezric committed
	if (mN == NULL) {
		DEBUG_PC ("Memory allocation failed");
		exit (-1);
	}
	return mN;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Look up for the service in the servieList bound to a serviceUUID
 * 
 * @params serviceUUID
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
struct service_t* get_service_for_computed_path(gchar* serviceUUID) {
martinezric's avatar
martinezric committed
	gint i = 0;
	for(GList *listnode = g_list_first(serviceList);
		listnode;
		listnode = g_list_next(listnode), i++) {
			struct service_t* s = (struct service_t*)(listnode->data);
			if (strcmp(s->serviceId.service_uuid, serviceUUID) == 0)
				return s;
	}
	return NULL;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the service type
 * 
 * @param type
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void print_service_type(guint type) {
	switch (type) {
	case SERVICE_TYPE_UNKNOWN:
			DEBUG_PC("Service Type UNKNOWN");
			break;
		case SERVICE_TYPE_L3NM:
			DEBUG_PC("Service Type L3NM");
			break;
		case SERVICE_TYPE_L2NM:
			DEBUG_PC("Service Type L2NM");
			break;
		case SERVICE_TYPE_TAPI:
			DEBUG_PC("Service Type L2NM");
			break;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the port direction
 *
 * @param direction
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void print_link_port_direction(guint direction) {
	switch (direction) {
		case LINK_PORT_DIRECTION_BIDIRECTIONAL:
			//DEBUG_PC("Bidirectional Port Direction");
			break;
		case LINK_PORT_DIRECTION_INPUT:
			//DEBUG_PC("Input Port Direction");
			break;
		case LINK_PORT_DIRECTION_OUTPUT:
			//DEBUG_PC("Output Port Direction");
			break;
		case LINK_PORT_DIRECTION_UNKNOWN:
			//DEBUG_PC("Unknown Port Direction");
			break;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the port termination direction
 *
 * @param direction
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
martinezric's avatar
martinezric committed
void print_termination_direction(guint direction) {
	switch (direction) {
	case TERMINATION_DIRECTION_BIDIRECTIONAL:
		//DEBUG_PC("Bidirectional Termination Direction");
		break;
	case TERMINATION_DIRECTION_SINK:
		//DEBUG_PC("Input Termination Direction");
		break;
	case TERMINATION_DIRECTION_SOURCE:
		//DEBUG_PC("Output Termination Direction");
		break;
	case TERMINATION_DIRECTION_UNKNOWN:
		//DEBUG_PC("Unknown Termination Direction");
		break;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the termination state
 *
 * @param state 
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void print_termination_state(guint state)
{
	switch (state) {
	case TERMINATION_STATE_CAN_NEVER_TERMINATE:
		//DEBUG_PC("Can never Terminate");
		break;
	case TERMINATION_STATE_NOT_TERMINATED:
		DEBUG_PC("Not terminated");
		break;
	case TERMINATION_STATE_TERMINATED_SERVER_TO_CLIENT_FLOW:
		DEBUG_PC("Terminated server to client flow");
		break;
	case TERMINATION_STATE_TERMINATED_CLIENT_TO_SERVER_FLOW:
		DEBUG_PC("Terminated client to server flow");
		break;
	case TERMINATION_STATE_TERMINATED_BIDIRECTIONAL:
		//DEBUG_PC("Terminated bidirectional");
		break;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the capacity unit
 *
 * @param unit
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void print_capacity_unit(guint unit) {

	switch (unit) {
		case CAPACITY_UNIT_TB:
			DEBUG_PC("Unit in TB");
			break;
		case CAPACITY_UNIT_TBPS:
			DEBUG_PC("Unit in TB/s");
			break;
		case CAPACITY_UNIT_GB:
			DEBUG_PC("Unit in GB");
			break;
		case CAPACITY_UNIT_GBPS:
			DEBUG_PC("Unit in GB/s");
			break;
		case CAPACITY_UNIT_MB:
			DEBUG_PC("Unit in MB");
			break;
		case CAPACITY_UNIT_MBPS:
			//DEBUG_PC("Unit in MB/s");
			break;
		case CAPACITY_UNIT_KB:
			DEBUG_PC("Unit in KB");
			break;
		case CAPACITY_UNIT_KBPS:
			DEBUG_PC("Unit in KB/s");
			break;
		case CAPACITY_UNIT_GHZ: 
			DEBUG_PC("Unit in GHz");
			break;
		case CAPACITY_UNIT_MHZ:
			DEBUG_PC("Unit in MHz");
			break;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Friendly function to log the link forwarding direction
 *
 * @param linkFwDir
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */