Skip to content
Snippets Groups Projects
pathComp_sp.c 11.6 KiB
Newer Older
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
/*
 * Copyright 2022-2023 ETSI TeraFlowSDN - TFS OSG (https://tfs.etsi.org/)
 *
 * 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.
 */
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed

#include <stdio.h>
#include <stdlib.h> 
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>
#include <unistd.h>
#include <netdb.h>
#include <glib.h>
#include <sys/time.h>
#include <ctype.h>
#include <strings.h>
#include <time.h>
#include <math.h>
#include <fcntl.h>

#include "pathComp_log.h"
#include "pathComp_tools.h"
#include "pathComp_sp.h"

// Global Variables
struct map_nodes_t* mapNodes;
struct graph_t* graph;
struct contextSet_t* contextSet;

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_sp.c
 * 	@brief Excecution Dijkstra algorithm
 *
 *  @param srcMapIndex
 *  @param dstMapIndex
 *	@param g
 *	@param s
 *
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
 *	@author Ricardo Mart�nez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void dijkstra(gint srcMapIndex, gint dstMapIndex, struct graph_t* g, struct service_t* s) {
	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);

	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_sp.c
 * 	@brief handling the Dijkstra algorithm
 *
 *  @param pred
 *  @param g
 *	@param s
 *
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
 *	@author Ricardo Mart�nez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
gint computation(struct pred_t* pred, struct graph_t* g, struct service_t* s) {
	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 shortest path
	dijkstra(srcMapIndex, dstMapIndex, g, s);

	// 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_sp.c
 * 	@brief CSPF algorithm execution
 *
 *  @param s
 *  @param path
 *  @param g
 *
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
 *	@author Ricardo Mart�nez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void computation_shortest_path(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]);

	// SP computation
	gint done = computation(predecessors, g, s);
	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);

	gboolean feasibleRoute = check_computed_path_feasability(s, p);
	if (feasibleRoute == TRUE) {
		DEBUG_PC("SP Feasible");
		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("SP FAILED!!!");
	comp_route_connection_issue_handler(path, s);

	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_sp.c
 * 	@brief Iterates over the list of network connectivity service requests
 * to compute their own paths fulfilling the constraints
 *
 *  @param outputList
 *
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
 *	@author Ricardo Mart�nez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
void sp_execution_services(struct compRouteOutputList_t* oPathList)
{
	g_assert(oPathList);
	g_assert(contextSet);
	g_assert(serviceList);

	DEBUG_PC("----- Starting the SP Computation ------");

	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 = &(oPathList->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);
			 oPathList->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);
			 oPathList->numCompRouteConnList++;
			 continue;
		 }

		 computation_shortest_path(service, pathService, g);
		 oPathList->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_sp.c
 * 	@brief handles the path computation for the constrained shortest path
 *
 *  @param compRouteOutput
 *
Lluis Gifre Renom's avatar
Lluis Gifre Renom committed
 *	@author Ricardo Mart�nez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
gint pathComp_sp_alg(struct compRouteOutputList_t* routeConnList)
{
	g_assert(routeConnList);

	gint numSuccesPathComp = 0, numPathCompIntents = 0;

	DEBUG_PC("================================================================");
	DEBUG_PC("===========================   SP   =========================");
	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
	sp_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_path_comp(routeConnList, delta, numSuccesPathComp, numPathCompIntents);
	print_path_connection_list(routeConnList);
#endif

	g_free(contextSet);
	return http_code;
}