Project RequirementsAlgorithms to determine Network ReliabilityANALYSIS OF VALUE OF P VS NETWORK RELIABILITY:Algorithmic Aspects of Telecommunication Networks – Fall 2013PROJECT - 3Computing the Reliabilityof a General NetworkConfigurationGURUDUTT NARASIMHAAlgorithmic Aspects of Telecommunication Networks – Fall 2013Project RequirementsThe aim of the project is to implement the exhaustive enumeration method for calculating the reliability of a general network configuration.The task is to develop algorithms to implement the above mentioned methods and use it to calculate the reliability of a general network configuration. The input to be given in order to test and compare the methods will be in the form of a n X n matrix in which each row and each column correspond to a node. the Node 0 will be the source and the Node n will be th e destination. Each entry in the matrix provides the reliability of an edge in the graph (each edge represents a component in a system). For example, the matrix entry in the ith row and jth columnis zero, it implies that there is no edge between i and j. If the value is positive, then it means that there is an edge between i and j and its reliability is the positive value specified. The graph is undirected which implies the values are symmetric on either side of the diagonal. That is, the reliability value stored in the matrix in the ith row and jth column should be same as the value stored in the jth row and ith column. The reliability of the entire configuration is defined as the probability of having at least one operational path from the source or Node 0 to the destination orNode n. At least 6 examples must be taken to compare the three methods to be implemented. The experiments are run on all the three methods in order to compare the running time, the reliability values obtained and to check the reliability calculation change in the three methods if we change the reliability of a single component and no change is done on the other components.Algorithms to determine Network ReliabilityExhaustive EnumerationAs the name suggests, in the exhaustive enumeration method all possible paths are traversed and then it is determined which of these paths are in the 'UP' state i.e. the flow is possible between the source node and the destination node. Then, the probability of all the 'UP' paths are calculatedand summed up to get the reliability of the entire network.Algorithmic Aspects of Telecommunication Networks – Fall 2013Algorithm for Exhaustive Enumeration()- Enter the number of nodes- Enter the component probability values as a n X n matrix where n is the number of nodes taking care that the same value is input for ith row jth column and jth row and ith column.- Using the component probability matrix, extract the number of edges and the individual probabilities and store it.- Using the number of edges, determine the 2^edges combinations of selecting and deselecting the edges to be considered.- Determine among the above combinations, which have a valid path from the source to destination nodes using BFS and checking at every step if the edge has a probability above zero and is set to be selected in the combination of edges.- Calculate the resulting probabilities of those combinations which have a valid path from source to destination and sum it to get the reliability of the entire network.Pseudo code for Exhaustive Enumeration- Enter the number of nodes.- Create a matrix of size Nodes x Nodes and enter the values of the probabilities taking care that the ith row and jth column has the same probability as the jth row and ith column since the graph is undirected.- Parse through the matrix created in the previous step and starting node, ending node and probability values for all edges having probability non zero. Only the values on one side o the diagonal are considered since the values are proportional about the diagonal. We getthe number of edges in the graph at the end of the parsing.- Call the function ‘doRec’ to recursively generate 2^edges combinations of 0s and 1s.- Each time the routine completes iteration, the function ‘bfs’ is called by passing the valuewith 0s and 1s.- In the bs routine, each time we start from the starting node (0), the routine ‘getUnvisitedChildNode’ is called to find a path till the destination node (Node - 1).- In the getUnvisitedChildNode routine, if a path from the source node (0) to the destination node (nodes - 1) is found then the routine ‘calcReliabProb’ is called to calculate the reliability for the path. The value is then added to the variable totalRelib which gives the total reliability value of all the paths.Algorithmic Aspects of Telecommunication Networks – Fall 2013Sample ResultEnter the number of Nodes in the network: 50.02Reliability using Exhaustive enumeration for p[0.02] is: 1.0240000000000003E-170.04Reliability using Exhaustive enumeration for p[0.04] is: 1.0485760000000003E-140.06Reliability using Exhaustive enumeration for p[0.06] is: 6.046617599999999E-130.08Reliability using Exhaustive enumeration for p[0.08] is: 1.0737418240000003E-110.1Reliability using Exhaustive enumeration for p[0.1] is: 1.0000000000000006E-100.12000000000000001Reliability using Exhaustive enumeration for p[0.12000000000000001] is: 6.191736422400006E-100.14Reliability using Exhaustive enumeration for p[0.14] is: 2.8925465497600027E-90.16Reliability using Exhaustive enumeration for p[0.16] is: 1.0995116277760003E-80.18Reliability using Exhaustive enumeration for p[0.18] is: 3.570467226623999E-80.19999999999999998Reliability using Exhaustive enumeration for p[0.19999999999999998] is: 1.0239999999999994E-70.21999999999999997Reliability using Exhaustive enumeration for p[0.21999999999999997] is: 2.6559922791423966E-70.23999999999999996Reliability using Exhaustive enumeration for p[0.23999999999999996] is: 6.340338096537591E-70.25999999999999995Reliability using Exhaustive enumeration for p[0.25999999999999995] is: 1.4116709565337572E-60.27999999999999997Reliability using Exhaustive enumeration for p[0.27999999999999997] is: 2.9619676669542364E-60.3Reliability using Exhaustive enumeration for p[0.3] is: 5.904899999999999E-60.32Reliability using Exhaustive enumeration for p[0.32] is: 1.1258999068426243E-50.34Reliability using Exhaustive enumeration for p[0.34] is: 2.0643777540597776E-50.36000000000000004Reliability using Exhaustive enumeration for p[0.36000000000000004] is:
View Full Document
Unlocking...