ALGORITHMIC ASPECTS OFTELECOMMUNICATION NETWORKSTE 6385Project 3 Computation of Network Reliability for GeneralNetwork ConfigurationsBy,Gurudutt NarasimhaNet Id: gxn120830SYNOPSIS:The goal of this project is to study experimentally how the network reliability depends on the individual link reliabilities for the given specific situation below:A complete graph on n = 5 nodes.So, number of edges, m=10. All links have identical value of Reliability which is given by variable p.OBJECTIVE:Using the given number of nodes=5 and edges=10 Create and implement an algorithm to compute the network reliability using the method of exhaustive enumeration To run the algorithm for different values of p (reliability of each link) and determine the Network Reliability of the network. To construct a graph to show how the Network Reliability of the network depends on the value of p. To construct a graph to show how the Network Reliability depends on the number of links whose state is flipped compared to original configuration.GIVEN:Number of nodes in the network = 5, number of edges m=10INPUT: Number of nodes N is given as input. Input for p variable is given in the range [0,1] in steps of 0.02 Input for k is in the range [1,32] in steps of 1OUTPUT:The program will result in Network Relaibility output. Run the program on various values of p(0 to 1) in steps of 0.02 with N fixed (N=5) and m=10. Find the Network Reliability for every case. It is required to show the relationship between Network Reliability and p, reliability of each link with the help of a graph. It is required to show the relationship between number of states whose states are flipped and p, reliability of each link with the help of a graph.OVERVIEW:The important goal of this project is to implement the exhaustive enumeration algorithm tocompute the general network configuration reliability. We need to explain how the algorithmworks and provide pseudo code for the description of the algorithm, with sufficient comments tomake them readable and understandable.We have to write a computer program that implements this method. We have to run the programfor the range of p values [0,1] in steps of 0.02.The input for the algorithms is described as follows. Represent the input graph by an nxn matrix in which each row and each column corresponds to a node. Node 1 will be the source, and node n will be the destination. Each entry of the matrix provides the reliability of an edge in the graph (each edge represents a component of the system) That is, the matrix entry pij is a number with 0· pij · 1. If it is 0, it means there is no edge between nodes i and j. If it is positive, it means there is an edge between nodes i; j and its reliability is pij, that is, it operates with probability pij, independently of the others. It is assumed that the graph is undirected, that is, pij = pji. Let us restrict ourselves to graphs in which there are no multiple (parallel) edges between the same nodes, and there are no self-loops. The reliability of the entire configuration is defined as the probability of having at least one operational path between the source (node 1) and the destination (node n).ALGORITHMIC DESCRIPTION AND IMPLEMENTATION: The method of network reliability for a basic network configuration that is to be implemented in this project is Exhaustive EnumerationExhaustive enumeration When using the exhaustive enumeration, we generate all possible states of a system and assign “up” and “down” system conditions to each state. This usually yields a long expression. Though the obtained expression might be simplified, this method is only practical for small systems, due to the exponential growth of the number of states. Exhaustive enumeration method is the simplest of the combinatorial optimization techniques. The principle of this method is to evaluateall combinations of the discrete variables. For N components there are 2n possible states, makingexhaustive enumeration a non-scalable solution.PSEUDO CODE :- Choose an appropriate N : Number of nodes in the network by choosing a random number within a given range say 5-10.- Choose a random value of k for k edge-connectivity in the connected network graph.- Construct a reliability matrix which determines the reliability of each edge in the graph by generating a random number between 0 and 1.- Apply the three methods exhaustive enumeration, minimal path and minimal cut one by one on the graph generated.- Exhaustive enumeration method: Depending on the number of nodes in the network we can generate the possible states in the system. For example, if there are 5 nodes in the system then the possible system states will be : [11111, 11110, 11101, 11100, 11011, 11010, 11001, 11000, 10111, 10110, 10101, 10100, 10011, 10010, 10001, 10000, 01111, 01110, 01101, 01100, 01011, 01010, 01001, 01000, 00111, 00110, 00101, 00100, 00011, 00010, 00001, 00000] where 0 indicates that node is in fail state and 1 indicates that the node is active. - For each of the system state find out whether the system state is UP or DOWN. This can be determined in the following way: if considering the system state 11010, nodes 0,1 and 3 are active and nodes 2,4 are in failed state then is there a path between source node 0 and destination node 4. If there exists a path then the system state is UP else it is DOWN.- Consider only the UP states now, take all the nodes which are in active state and sum up the reliabilities of the edges connecting them, then take all the nodes which are in failed state and sum up (1.0 - reliabilities of the edges connecting them). This will yield the totalreliability of the network by exhaustive enumeration method. JGRAPHT: JGraphT is a free Java graph library that provides mathematical graph-theory objects and algorithms. JGraphT supports various types of graphs including: - Directed and undirected graphs. - Graphs with weighted / un-weighted / labeled or any user-defined edges. - Various edge multiplicity options, including: simple-graphs, multi-graphs, pseudo-graphs.- Un-modifiable graphs - allow modules to provide "read-only" access to internal graphs.- Listenable graphs - allow external listeners to track modification events.- All compositions of above graphs.JGRAPH AND JGRAPHT: JGraphT and JGraph are two different libraries which are intended for different purposes. JGraphT: is focused on data structures and algorithms. JGraph: is focused on rendering and
View Full Document
Unlocking...