www.CLiki.nethttp://jung.sourceforge.net/ALGORITHMIC ASPECTS OFTELECOMMUNICATION 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 showingthe 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 supplyingrandom 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 thenetwork topologyFor those links along theshortest path from source todestination, assign the b valuesUsing every node in the graph generate theshortest path using Floyd-Warshall Shortest PathAlgorithmGenerate the valuesfor the unit cost ausing M and kGenerate the randomvalues for the linkdemand b using MEnter the value
View Full Document
Unlocking...