ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKSTE 6385Project 1 Implementation of a Basic Network Design ModelBy,Gurudutt NarasimhaNet Id: gxn120830SYNOPSIS:The theme of this project is to implement the basic network design model that is capable of doing the following.OBJECTIVE:Using the given number of nodes and edges obtained by the randomly chosen values in the graphØTo create the network topology graphØTo determine the total optimal cost of the network and also to find the capacity of each link.ØTo implement the Floyd-Warshall Shortest path algorithm in order to find the shortest path from every node to another in the network and hence the total minimum cost of the network.ØTo find Density of each network (for various different inputs).ØTo construct a graph to show how the total cost of the network depends on the value of parameter k.ØAlso to construct a graph between Density of the network and value of k and how it changes with the parameter value k, for different values of k.GIVEN: aij is Unit cost values for the potential links bij is Traffic demand values between pairs of nodeINPUT:ØNumber of nodes N is given as input.ØRandom values of aij and bij is provided as the input.ØFind the total Cost of the network in each experiment before the application of the shortest path algorithm.ØSet the range of M as [0,1,2,3,4].Øget the value of kØFind the number of actual nodes in the each iteration depending on the value of k.OUTPUT:The program will result in generating the network topology according to the capacities assigned to the links.ØRun the program on various examples with N fixed (N=40).ØFind the shortest path of the random graph generated for every case.ØDesign the network topology with graphs.ØFind the total cost of the network by multiplying the shortest path of unit cost aij with traffic demand of the network bij.Finally it is required to show the relationship between total cost and parameter k and display these results with the help of a graph.Also calculation of the density of the network for each k is required which is done using the formula given below:Density (D) = 2*m/N*(N-1)Density is defined as the ratio of the actual number of edges versus maximum possible number of edges. Now after finding the total cost it is required to show that the total cost is dependent on the parameter M. Here m is the actual number of required edges in the network. A graph showing the dependencies of the density of the network on the value of k is also given for each case.PSEUDO CODE :ØAccept the value of the total number of nodes(n) from the user.ØAccept the value of k ØInitialize values of all the arrays to be used in the code.ØInitialize aij[i][j] which is the cost value matrix of the network.ØAlso initialize the traffic value matrix bij[i][j].In the main method the cost value array aij and traffic value array bij gets populated by supplying random values to them depending on the value of k. These aij and bij are adjacency matrix. According to the property of the adjacency matrix the diagonal of the matrix remains zero. According to the project we have to feed both the cost value matrix and the traffic value matrix with random numbers. The random () function is used to create random values and then populate both the arrays aij & bij.Initial cost structure of the algorithm is shown in the method DisplayCost ().Now after getting the cost value adjacency matrix, Floyd-Warshall's algorithm to find the shortest path matrix is applied to aij. The implementation of the Floyd-Warshall algorithm is shown in the method shortestPathFloydWarshallalgo(). The Algorithm typically provides the lengths of the paths between all pairs of vertices. Then the shortest path matrix is multiplied by the traffic value matrix bij to get the total cost of the network. It is possible to create a method to reconstruct the actual path between any two endpoint vertices. Hence the total cost flow of the network is calculated using the sum of all the actual link costs.Implmentation of Floyd-Warshall Algorithm:Floyd-Warshall Algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph. A single execution of the algorithm will find the lengths of the shortest paths between all pairs of vertices.Consider a graph G with vertices V, each numbered 1 through N. Furtherconsider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1,2,...,k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices 1 to k + 1.There are two candidates for each of these paths: either the true shortest path only uses vertices in the set {1, ..., k} or there exists some path that goes from i to k + 1, then from k + 1 to j that is better. We know that the best path from I to j that only uses vertices 1 through k is defined by shortestPath(i, j, k), and it is clear that if there were a better path from i to k + 1 to j, then the length of this path would be the concatenation of the shortest path from i to k + 1 (using vertices in {1, ..., k}) and the shortest path from k + 1 to j (also using vertices in {1, ..., k}).If w (i,j) is the weight of the edge between vertices i and j, we can defineshortestPath(i, j, k) in terms of the following recursive formula: the base case is shortestPath(i,j,0) = w(i,j) and the recursive procedure isshortestPath(i,j,k)=min(shortestPath(i,j,k1),shortestPath(i,k,k1)+shortestPath(k,j,k-1)Pseudocode of Floyd-Warshall Algorithm : Assume a function edge Cost(i,j) which returns the cost of the edge from i to j. Also assume that n is the number of vertices and edgeCost(i,i) =0int path[][];A 2-dimensional matrix. At each step in the algorithm, path[i][j] is theshortest path from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to edgeCost(i,j).Procedure FloydWarshall ()for k := 1 to nfor i := 1 to nfor j := 1 to npath[i][j] = min ( path[i][j], path[i][k]+path[k][j] );Flow ChartStartGenerate the network topologyFor those links along the shortest path from source to destination, assign the b valuesUsing every node in the graph generate the shortest path using Floyd-Warshall Shortest Path AlgorithmGenerate the values for the unit cost a using M and kGenerate the random values for the link demand b using MEnter the value for kEnter the value for MEnter the number of nodesGenerate a graph with the
View Full Document