RELIABILITY CONFIGURATION ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKS TE 6385.001 v. PURNA CHANDRA VINAY KUMAR PXV1716302 Table of Contents RELIABILITY CONFIGURATION OF THE NETWORK ........................................................................ 3 PROBLEM STATEMENT ........................................................................................................................... 3 Tasks: ......................................................................................................................................................... 3 APPROACH ................................................................................................................................................. 4 ALGORITHM............................................................................................................................................... 4 Task 1: ....................................................................................................................................................... 4 Task 2: ....................................................................................................................................................... 7 FLOW CHART ................................................................................................................................................. 8 PLOTS .......................................................................................................................................................... 9 Reliability vs p: .......................................................................................................................................... 9 Reliability vs K: .......................................................................................................................................... 9 REFERENCES ................................................................................................................................................ 11 APPENDIX ................................................................................................................................................. 11 READ ME: .................................................................................................................................................... 133 RELIABILITY CONFIGURATION OF THE NETWORK The reliability of the network depends on the topology of the network and the probability of the failure of the hosts and the links. The system is said to be ‘up’ if all the nodes of the network is connected i.e. at least one of the links connecting all other nodes should be ‘up’. The reliability(R) of the network is calculated by multiplying the ‘up’ and ‘down’ probabilities of the links for the ‘up’ condition of the system state, and adding up all the possible combinations. Since, the reliability defines the probability that the system is ‘up’ it is always less than one (R<=1). The complete undirected graph network topology is constructed for the given number of nodes ‘N’ eliminating the self-loops and parallel edges. The system condition is checked using the standard DFS or BFS algorithms and if connected the ‘up’ and ‘down’ probabilities are multiplied to calculate the reliability for the configuration of the network. Since for every link the possible states of the links are ‘2’, ‘up’ or ‘down’, the number of possible system states is ‘2N’. All the possible ‘2N’ states are checked for connectivity of the network and reliability is calculated if the system is ‘up’. Summing the reliabilities of all the possible connected states of the network gives the reliability of the system. PROBLEM STATEMENT The aim of the project is to compute the network reliability for the complete undirected graph of ‘N’ nodes eliminating parallel edges and self-loops, using the method of exhaustive enumeration. The project aims at fulfilling the following tasks. Tasks: ➢ To design an algorithm to construct the complete undirected graph for ‘N’ nodes and to check all the possible connected graphs from ‘2N’ possible states and compute the network reliability for all the connected states. ➢ To write a computer program that implements the above algorithm. ➢ The program takes the number of nodes ‘N’, the reliability of the link ‘p’ as inputs. ➢ It computes the reliability of the system for different values of ‘p’ plots the dependency of the network reliability on ‘p’. ➢ For the next experiment the reliability value of the link ‘p’ is fixed to a value. Among all the ‘2N’ possible combinations of component sates, ‘k’ states are picked randomly and the system state is altered i.e. if the system is ‘up’ it is changed to ‘down’ and if it is ‘down’ changed to ‘up’ and the reliability of the network is then computed.4 ➢ The connectivity of the system is checked using the Depth First Search(DFS) non recursive algorithm and if the nodes are connected the system is said to be in ‘up’ state. ➢ The total reliability of the network vs ‘k’ is plotted for different values of ‘k’. The experiment is repeated several times for the value of ‘k’ and then averaged to reduce the effect of randomness. APPROACH The approach in calculating the network reliability is described in the following steps: ➢ The program takes the number of nodes which is ‘N’ and constructs the network topology as described above. ➢ The program then calculates the number of links for the given number of nodes and creates a list of link states consisting of 0’s and 1’s. ➢ For the first task, i.e. to find the dependency of the network reliability of the link reliability, the DFS algorithm is applied on the link state list and connectivity of the graph is verified. ➢ The reliability of the state if it is connected is calculated by multiplying all the link reliability probabilities, i.e. ‘p’ for all the operational links and ‘1-p’ for all the down links. ➢ The total reliability of the network is then calculated by adding all the connected network reliabilities and the graph is plotted. ➢ For the second task the link reliability is fixed to a value and ‘k’ random numbers generated between the range
View Full Document
Unlocking...