Algorithmic Analysis of Telecommunication Networks CS6385 Spring 2014 Project1 An Application to Network Design (Using Floyd Warshall Algorithm) Submission by: Poojitha Priyanka Parcha ([email protected])Index: S.No. Topics Page No. 1. Introduction………………………………………………………………………………………………………………3 1.1 Project objective…………………………………………………………………………………………………….3 1.2 Programming aspects and algorithm………………………………………………………………………3 2. Project description…………………………………………………………………………………………………….4 3. Path reconstruction with Floyd Warshall…………………………………………………………………….5 4. Implementation & Analysis ……………………………………………………………………………………6 5. Results and inference ………………………………………………………………………………………………..8 6. Density Vs Random k value Graph ………………………………………………………………………………9 7. Total Cost Vs Random k value Graph …………………………………………………………………………..9 8. Topologies………………..…………………………………………………………………………………………… 10 9. Verbal justification……………………………………………………………………………………………………13 10. Appendix………………………………………………………………………………………………………………..14 11. References………………………………………………………………………………………………………………19I. Introduction 1.1 Objective The objective of the Project is to build the basic network topology presented in lecture note “An Application to Network Design”, that could connect the nodes using shortest path algorithm so that total cost is minimum. Given the information regarding number of nodes(N), Traffic Demand(bij) and Unit cost value for potential link(aij), a network topology is to be built with capacities assigned to the links, and compute total cost and also justify designed model. The project output will also show statistical information regarding cost and density of the network depending on k (no. of outgoing links from the node). 1.2 Programming aspects and algorithm The Program aims to provide the shortest path dynamically for a weighted graph from any selected vertex. Thus Floyd Warshall Algorithm has been chosen. Floyd Warshall is the shortest path algorithm that could run even in the presence of negative edge weights from each vertex. The Floyd-Warshall uses a dynamic-programming methodology to solve the All-Pairs-Shortest-Path problem. The algorithm runs in O(|V|^3) time and negatively weighed edges may be present, however this has limitation for negatively weighted cycles. The main recursive definition of the algorithm is given by: d ij (k) : The weight of the shortest path from vertex i to vertex j for which all intermediate vertices are in the set {1,2…k} The weight of an edge between vertex i and vertex j in graph G = (V; E), where 0 if i = j wij = the weight of a directed edge (i , j) if i ≠ j and (i, j) ∈ E 1 if i ≠ j and (i, j) ∉ E For a shortest path from i to j such that any intermediate vertices on the path are chosen from the set {1, 2,… k}, there are two possibilities:1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is. 2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j]. A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. This algorithm returns only the least cost with which the source can be routed towards the destination. The least cost is found in a recursive fashion. In this solution the path in the final graph is reconstructed with little modification to the algorithm. Applications for Floyd Warshall: - Detecting the Presence of a Negative Cycle - Transitive Closure of a Directed Graph 2. Project Description - Initially the Number of Nodes to be considered is N=35 for each case. - Generate the bij values as independent random integers from the range [0, 1, 2, 3]. - For generating the aij values, we shall pick K random unique indices j1, j2, j3, …, jk, and as well as from i . Now set aij1=aij2=…=aijk=1 and assign the value of aij = 300 to each of these K pairs. The rest of the aij parameters are chosen as random numbers. - Now we generate some new random parameters (aij, bij) independently with different values of k ranging from 3, 4, 5,…,15. - After the total experiment, plot a graph for the variation of total cost with k. - The variation of the density of the obtained network with K also should be shown graphically. Density is defined as the number of directed edges that are assigned non-zero capacity, divided by the total possible number of directed edges, which is N*(N-1). - Density is calculated using D = (m)/(N*(N-1)) where, m = no. of directed edges in the shortest path graph N = no. of nodes in the given input graph N(N-1) : Maximum possible no. of edges in the input graph - Obtain network topologies graphically randomly selecting k values in range {3,4,…15} for low, medium and high K values3. Path reconstruction using Floyd warshall: The Floyd–Warshall algorithm typically provides the lengths of the paths between all pairs of vertices. With simple modifications, it is possible to create a method to reconstruct the actual path between any two endpoint vertices. While one may be inclined to store
View Full Document
Unlocking...