ALGORITHMIC ASPECTS OFTELECOMMUNICATION NETWORKSTE 6385Project - 3 NETWORK RELIABITLITY USING METHOD OF EXHAUSTIVE ENUMERATIONAshwin WuluvaranaNet Id: [email protected] 2014Page 1 of 19INTRODUCTION:This project is an experimental study to test reliability of anetwork based on individual link reliability. We have to develop analgorithm to find out the overall network reliability. In this casenetwork reliability only depends on individual link reliability. Eachof the links in the network may fail but nodes are always up. Thesystem will be operational if the network topology is connected.We will develop our algorithm to find the overall network by usingExhaustive Enumeration method. In this project after implementing the algorithm, we have torun some experiment to find out how overall network reliabilitychanges based on individual link reliability. Each link has linkreliability p. In our experiment we will find out network reliabilityfor different values of p and will show graphically how the networkreliability changes if p changes.Second part of the project will run some other experiment.For p = 0.9 we will run the experiment but in this case we willrandomly flip some possible combinations of component statesand will monitor how it eventually changes the network reliability.In order to reduce the randomness, we will run the experimentseveral times and average them out for any particular case. A solid can be represented as a collection of smaller primitiveobjects that are assumed to be non-overlapping, i.e. gluedtogether, and are of uniform size and orientation, i.e. one kind ofprimitive object. This representation is called the exhaustiveenumeration. It only approximates realistic solids but all kind ofsolids can be represented. In the collection of primitive objectsforming the exhaustive enumeration, each object can bedescribed in terms of its coordinates.Page 2 of 19It is difficult to describe realistic solids directly by enumeratingits objects. A more practical approach is to create exhaustiveenumerations by a conversion from some other representationsuch as the constructive or boundary models. In exhaustiveenumeration it is straightforward to produce algorithms thatcreate new representations from existing representations.Exhaustive enumeration consumes a lot of memory but it issimple and general.SYNOPSIS:The theme of this project is to implement the Exhaustive Enumeration algorithm capable of finding network reliability in an undirected graph.OBJECTIVE :Using the given number of nodes and edges obtained by the randomly chosen values in the graph- The goal of this project is to study experimentally howthe network reliability depends on individual linkreliabilities, in the situation described as follows.- Consider a complete graph containing 5 nodes , thismeans every node is connected with every other onei.e, parallel edges and self loops are excluded in thisgraph. The resultant graph has m=10 edges,representing the links of the network.- The reliability of each link is p and the parameter p willtake different values in the experiment.- To create an algorithm to compute the networkreliability considering the above described situationusing the method of exhaustive enumeration.Page 3 of 19- Also to run the program for different values of p,increasing the parameter over the interval 0 to 1 insteps of 0.02.- Consider a complete graph n = 5 nodes with every node is connected with every other one (parallel edges and self-loops are excluded in this graph). As a result, this graph has m = 10 edges (links).- The links of the network may fail but the nodes are always up. The reliability of each link is p, the same for every link. - The system is considered operational, if the network topology is connected.DESCRIPTION:In order to apply EXHAUSTIVE ENUMERATION TECHNIQUE to aspecific class of problems, one must implement four procedures first, next, valid, and output. These procedures should take as a parameter the data P for the particular instance of the problem that is to be solved, and should do the following:1. first (P): generate a first candidate solution for P.2. next (P, c): generate the next candidate for P after the current one c.3. valid (P, c): check whether candidate c is a solution for P.4. output (P, c): use the solution c of P as appropriate to the application.The next procedure must also tell when there are no morecandidates for the instance P, after the current one c. Aconvenient way to do that is to return a "null candidate", somePage 4 of 19conventional data value Λ that is distinct from any real candidate.Likewise the first procedure should return Λ if there are nocandidates at all for the instance P. The exhaustive enumerationmethod is then expressed by the algorithmc first(P)while' c Λ do if' valid(P,c) then output(P, c) c next(P,c)end whileIn order to find the overall network reliability, we can list allpossible states of the network and assign ‘up’ and ‘down’ systemcondition to each state. Then the reliability can be obtained bysumming the probability of the ‘up’ states. In our networktopology, there are 5 nodes and 10 links. As we are consideringthe link states only, possible network states can be 210=1024. Inorder to implement the algorithm, we need a way to incorporatethese in our algorithm and we have to find out a way to generateall these states.IMPLEMENTATION:Implementation – JAVA languageGraph Implementation – ExcelThe Implementation of the Exhaustive Enumeration Algorithm for nodes=5 and value of p varying in increments of 0.02 done as follows:-Page 5 of 191. The number of nodes n, the number of edges needed andthe reliability of each edge components are accepted asinputs from the user. 2. Now for each number I between 0 and 2n.a. Generate the binary equivalent for the decimal numberand store it in the character array set[i]. 3. Now each digit in the binary number corresponds to anedge in the graph. For example 001 implies the 3rd edgeis present and the first 2 edges are not present and hencenot considered when network connectivity is checked.
View Full Document
Unlocking...