Programming Language: JavaOperating System: Linux Ubuntu 11.04Graph plotting: MATLABThe pseudocode for the path reconstruction algorithm is shown below:After calculating the shortest distance and the paths traverse, the total cost and density of the resulting network were also computed as follows:Olawale Abidemi OKUSANYAAlgorithmic Aspects of Telecommunications NetworksCS 6385Project 1AbstractThe theme of this project is to implement the basic network design model that is presented in the lecture note entitled "An Application to Network Design", and experiment with it.Tools usedProgramming Language: JavaOperating System: Linux Ubuntu 11.04Graph plotting: MATLABDescriptionThis project implements the basic network design model that was presented in the lecture note titled “An Application to Network Design” and then experiment with the network model. The goal we are trying to achieve here is to determine which links of the network will be built in order to minimise the cost of building the network, given the unit cost aij per link, the traffic demand between any two nodes of the network bij.Java programming language was used to implement the project on a Linux based operating system. The program requests for the values of the number of nodes N and the value of M from the user. From these inputs the program generates two graphs a[][] and b[][] for the cost and the traffic demands respectively by randomly assigning values to using the inbuilt random value generation class of java (ie java.Math.Random()). The graph is then stored as an N*N 2-D array of integers a[][] and b[][] for the cost and traffic demands respectively.Algorithm and Logic The Java programming language was used to implement this project. First the program ask the user to input the value of N then the value of M. From this values the program randomly assigns edges to the graph using the in-built random number generator of Javaclass Math.Random. The program also randomly generates unit cost and traffic demand graphs a[][] and b[][] respectively as described above. The program consist of four methods, the main method that generates that graphs and the method floydWarshal (to calculate the shortest path between all pairs of nodes), method floydWarshallWithPathReconstruction to generate the path traversed from one node to another and method getPath() for calculating the path.From the cost graph matrix generated above a[][], the links the are not used are assigned an infinity cost by setting the cost to a very high value so that these paths will never be considered valid. In this project, the value 99999999 was assigned as “infinity”. the graph was then passed to the method floydWarshall to calculate the shortest path between every pair of nodes and then the method floydWarshallWithPathReconstruction to generate the path traversal from one node to the other.The value generated by the random number generator are governed by a value 'M'; where M changes for each experiment that was performed. This experiment was performed several time for different values of M i.e., M=5,10,20,30,40,50; for a total of 6 experiments in all. The pseudo code used for the implementation ofthe floydWarshall and the floydWarshallWithPathReconstruction algorithms are as shown below: 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j 2 (infinity if there is none). 3 Also assume that n is the number of vertices and edgeCost(i,i) = 0 4 */ 5 6 int path[][]; 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 8 from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to 9 edgeCost(i,j).10 */1112 procedure FloydWarshall ()13 for k := 1 to n14 for i := 1 to n15 for j := 1 to n16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );(http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)The pseudocode for the path reconstruction algorithm is shown below: 1 procedure FloydWarshallWithPathReconstruction () 2 for k := 1 to n 3 for i := 1 to n 4 for j := 1 to n 5 if path[i][k] + path[k][j] < path[i][j] then 6 path[i][j] := path[i][k]+path[k][j]; 7 next[i][j] := k; 8 9 procedure GetPath (i,j)10 if path[i][j] equals infinity then11 return "no path";12 int intermediate := next[i][j];13 if intermediate equals 'null' then14 return " "; /* there is an edge from i to j, with no vertices between */15 else16 return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);(http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)After calculating the shortest distance and the paths traverse, the total cost and density of the resulting network were also computed as follows:The total cost was computed by adding the cost of all the edges while the density was computed for as density D = m/(N*(N-1)/2)where,N = 25 andm = the actual number of edges in the graphfor each value of M=5,10,20,30,40,50 for each experimentEdges that are not used to carry traffic are not built, hence the resulting network topology in not a full mesh network. From here the resulting network graph was exported into MATLAB for visual presentation.ParametersThe parameters used for these experiments are:1. The number of nodes (N)2. The value of MBoth of these were requested from the user as inputs.Results and OutputsThe graph of Density versus cost and Density versus M were ploted and shown below.0 10 20 30 40 50 6000.10.20.30.40.50.60.70.80.91Graph of Density Versus MDENSITYDENSITYM0 10 20 30 40 50 600100002000030000400005000060000Graph of Cost Versus 'M'DENSITYValue of 'M'Cost in abitary unitsTabulated below is the result of the experiment.Also shown below are graphical representations of the resulting network topologies, also shown are the cost and the densities for each experiment with M= 5 10, 20, 30, 40, and 50. The network topologies were generated by exporting the graph results to Matlab.When M=5Results of the ExperimentM 5 10 20 30 40 50Density 0.7933 0.7067 0.84 0.8033 0.8633 0.8767238 212 252 241 259 263Cost 2412 2594 14127 1596 42263 48062Number of Edges (m)When M=10when M=20When M=30When M=40when M=50AppendixThe
View Full Document
Unlocking...