Network ReliabilityAlgorithmic Aspects of Telecommunication NetworksNETWORK RELIABILITYCOMPUTATIONIssue 1.0 ----- By Sudheesh Srikantam 2021175360Network ReliabilityOBJECTIVE The aim of the project is to study experimentally how the network reliabilitydepends on the individual link reliabilities, in the specific situation describedbelow: Network topology: A complete undirected graph on n=5 nodes. This means,every node is connected with every other one. As a result, this graph has m=10edges, representing the links of the network. - Components that may fail: Thelinks of the network may fail, the nodes are always up. The reliability of eachlink is p, the same for every link. The parameter p will take different values inthe experiments. - Reliability configuration: The system is consideredoperational, if the network topology is connected. We need to create an algorithm to compute the reliability of a given networktopology using the Exhaustive Enumeration method. For every link we need todetermine the possible state and the up or down state condition for the entirenetwork which is then converted to the reliability of the system. The reliabilityis based on the probability of each link associated with the topology of thenetwork. Then out of N states K states are chosen, whose values are changedfor each link and the reliability of the network is computed again.INTRODUCTION:-Basically network reliability is defined as the availability of end to endfunctionary for customers and the ability to experience failures or systematicattacks, without impacting customers or operations. The evolution ofcommunication technologies results in continuously increasing capacities andhigher concentration of traffic on relatively fewer elements. The failures ofthese high capacity elements affect the quality of service provided by thenetwork, and therefore several protection techniques have been developed andimplemented in order to ensure resilience to network outages caused by thefailure of the components.INPUT: - Consider a complete graph n = 5 nodes with every node is connectedwith every other one (parallel edges and self-loops are excluded in thisgraph). As a result, this graph has m = 10 edges (links). - The links of the network may fail but the nodes are always up. Thereliability of each link is p, the same for every link. - The system is considered operational, if the network topology isconnected.Network ReliabilityMETHOD OF EXHAUSTIVE ENUMERATION: Exhaustive Enumeration method is used for the computation of the reliability ofthe network which represents a brute force approach to the problem. It isapplied to a network which neither has series or parallel configuration. In thismethod we list all possible states of a path from the source node ‘1’ to thedestination node ‘n’. Therefore if there are ‘m’ edges in the path there would 2power m states of the system. Every link is then assigned ‘up’ and ‘down’system condition. For any subsystem if we have n elements , to compute the reliability of thenetwork the number of states associated with the network are required to becomputed. We can list all the possible states of the system and assign “up” and“down” system condition to each state. Then the reliability can be obtained bysumming the probability of the “up” states. For our experiment we are requiredto compute 2 to the power of 10 =1024 possible states of the network. Thismethod is practical for small systems due to the exponential growth of thenumber of states. For N components, there are 2 to the power of N possiblestates which makes Exhaustive Enumeration a non-scalable solutionEXHAUSTIVE ENUMERATION ALGORITHM Consider the number of nodes in the Network be equal to “n”, which is equal to5 for our experiment. Consider the number of edges in the Network be equal to “m”. As it is mentioned that all the nodes are completely connected and there are noparallel edges and self-loops so we have 10 edges for 5 nodes. Consider the probability of each link be “p” which is either 0 or 1. It’s value issame for all links. For p=0, link is “up” and for p=1, link is “down”. Step1:- Declare and initialize variables. Input the number of nodes which is n=5and take an array[], i=0 which implies that no components are down. Thisimplies the system is up. Step2:- Obtain the probability of each link (p) from the user. Its value isbetween 0 and 1. Step3:-Based on the requirement that there are no parallel edges and self-loops, the exact number of distinct edges is found to be 10. Step4:- Using the number of edges, determine the 2 to the power edgecombinations of selecting and deselecting the edges to be considered. Step5:- Determine those sets of the links states that have the up condition forthe network.Network ReliabilityStep6:- Repeat these steps N times for N components and store the reliabilityvalues. Step7:- Calculate the resulting probabilities of those combinations which havean “up” condition for the network and sum it to get the reliability of the entirenetwork a) Idea implementation how algorithm worksStep 1 : BeginStep 2: Generate the connectivity matrix where each entry P[i][j] not equal to zero represents an edgeStep 3: Assign 1 as the source node.Step 4: For each destination node find all possible paths from source to destination.Step 5: For every vertex which is adjacent to the destination node find all the possible paths to those adjacent nodes.Step 6: Find all paths recursively by changing the destination node.Step 7: For all states assign “up” and “down” to the links connectedStep 8: Perform exhaustive enumeration, compute the reliability and pick K combinations. Then flip the states and compute reliability again.Step 9 : StopNetwork ReliabilityFlowchart :The below is the flow chart provided for the mentioned idea Start Generate the connectivity matrix where each entry Pij not equal to zero represents an edge Assign '1' as the source node For each destination node find all possible paths from source to destinationFor every vertex which is adjacent to destination node find all the possible paths to those adjacent nodes Find all paths recursively by changing the destination nodeFor all states assign
View Full Document
Unlocking...