4003-541-70/4005-741-70 Data Communications and Networks II Module 3. Network Connectivity Analysis -- Lecture Notes Prof. Alan Kaminsky -- Spring Quarter 2006 Rochester Institute of Technology -- Department of Computer Science Questions Given a certain network topology (graph): How many links do you have to blow up to make the network fail? How many nodes do you have to blow up to make the network fail? Given the probability of individual link (node) failure, what is the probability of network failure?   Network non-failure = connected graph There is at least one path from every vertex to every other vertex   Network failure = disconnected graph There is no path from some vertex to some other vertex Maximum Flow Given: A directed graph (digraph) Each edge labeled with a capacity A source vertex A sink vertex   Find: A pattern of flow from source to sink, such that Each edge's flow is less than or equal to the edge's capacity, and The total flow is as large as possible -- Maximum Flow   (For an undirected graph, replace each undirected edge with two directed edges in opposite directions)   Maximum Flow Algorithm: Start with each edge's flow = 0 and each edge's capacity as given. Find a path P from source to sink such that: There are no cycles in P, and There is unused capacity (flow < capacity) along each edge in P. Let F be the smallest unused capacity among all the edges in P. For each edge in P, add F to the edge's flow. Repeat Steps 2-4 until there are no more possible paths. For each pair of mutually adjacent vertices (X, Y), compute the net flow between X and Y = (flow from X to Y) - (flow from Y to X).   Sum of flows coming out of source = Sum of flows going into sink = Maximum flow from source to sink   Example:   Maximum flow from A to F = 12:   Example:   Maximum flow from D to F = 8: (In this example there are other flow patterns that yield the same maximum flow) Minimum Cut A cut between vertices A and B = A set of edges that, if removed, disconnect A from B   Capacity of a cut = Sum of the capacities of the edges in the cut   A minimum cut between vertices A and B = A cut between A and B with the smallest capacity   Max-Flow Min-Cut Theorem Maximum flow between A and B = Capacity of minimum cut between A and B Edge Connectivity Edge connectivity from source A to sink B = Number of edge disjoint paths from A to B = Minimum number of links you have to blow up to disconnect A and B   Two paths are edge disjoint if they share no edges in common   Edge Connectivity Algorithm (source, sink): Set each edge's capacity to 1. Find the maximum flow from source to sink. The answer gives the edge connectivity from source to sink.   Why this works: The above algorithm finds the capacity of the minimum cut between source A and sink B, by the Max-Flow Min-Cut Theorem Since each edge's capacity is 1, the capacity of the minimum cut equals the number of edges in the minimum cut To disconnect A from B, it is sufficient to remove the edges in this minimum cut Therefore, the capacity of this minimum cut is the fewest number of links you have to remove to disconnect A from B; that is, the edge connectivity from A to B   Edge connectivity of the entire network (graph) = Minimum edge connectivity between any source and any sink = Number of links you have to blow up to make the network fail   Edge Connectivity Algorithm (entire graph): Pick an arbitrary vertex A. Compute the edge connectivity from A to every other vertex. Take the minimum edge connectivity computed in Step 2. The answer gives the edge connectivity of the entire graph.   (Note that you don't have to compute the edge connectivity between every pair of vertices.)   Why this works: Say the above algorithm gives the answer K Then there are at least K edge-disjoint paths from A to every other vertex Suppose we remove K-1 or fewer edges; then there is still at least one path from A to every other vertex, and the graph is still connected (via A) Suppose we remove the K edges in the minimum cut between A and some other vertex; this disconnects A from that vertex, and the whole graph is therefore disconnected Therefore, by removing K edges (but no fewer) we can disconnect the graph; that is, the graph's edge connectivity is K Vertex Connectivity Vertex connectivity from source A to sink B = Number of vertex disjoint paths from A to B = Minimum number of nodes you have to blow up to disconnect A and B   Two paths are vertex disjoint if they share no vertices in common   Vertex Connectivity Algorithm (source, sink): For each node X: Split X into two nodes, X1 and X2. Attach all of X's incoming edges to X1. Attach all of X's outgoing edges to X2. Add an edge from X1 to X2. Set each edge's capacity to 1. Find the maximum flow from source to sink. The answer gives the vertex connectivity from source to sink.   Why this works: Same as the Edge Connectivity Algorithm, except . . . Each vertex X can only be on one path, because the "internal edge" from X1 to X2 can only be on one path Therefore, this algorithm finds the number of vertex disjoint paths   Vertex connectivity of the entire network (graph) = Minimum vertex connectivity between any source and any sink = Number of nodes you have to blow up to make the network fail   Vertex Connectivity Algorithm (entire graph): For each pair of vertices (A, B), compute the vertex connectivity from A to B. Take the minimum vertex connectivity computed in Step 1. The answer gives the vertex connectivity of the entire graph.   (The reasoning behind the entire-graph Edge Connectivity Algorithm doesn't work for the entire-graph Vertex Connectivity Algorithm.)   The entire-graph Vertex Connectivity Algorithm requires O(V2) max-flow calculations, where V = number of vertices   If we change the question, we can get the answer with O(V) max-flow calculations   Old question: What is the graph's vertex connectivity? New question: Is the graph's vertex connectivity >= K? Kleitman's Algorithm Even's Algorithm Probabilistic Analysis of Connectivity Given a network topology, such as →   Suppose that: The probability of individual link failure is p Link failures are independent   What is the probability of network failure? That is, a disconnected network   Analysis For every possible subset of the links: Determine probability that all links in subset fail Determine whether removing links in subset disconnects network Add up probabilities for subsets where answer is "yes" Subset of 0 links, probability = (1 - p)8, disconnects = 0   Subsets of 1 link, probability = p (1 - p)7, disconnects = 0 The edge connectivity of this graph is 2 Therefore, removing fewer than 2 edges cannot disconnect the graph   Subsets of 2 links, probability = p2 (1 - p)6, disconnects = 2 AB,AC -- yes AB,BD -- no AB,BE -- no AB,CD -- no AB,CE -- no AB,DF -- no AB,EF -- no AC,BD -- no AC,BE -- no AC,CD -- no AC,CE -- no AC,DF -- no AC,EF -- no BD,BE -- no BD,CD -- no BD,CE -- no BD,DF -- no BD,EF -- no BE,CD -- no BE,CE -- no BE,DF -- no BE,EF -- no CD,CE -- no CD,DF -- no CD,EF -- no CE,DF -- no CE,EF -- no DF,EF -- yes Subsets of 3 links, probability = p3 (1 - p)5, disconnects = 20 AB,AC,BD -- yes AB,AC,BE -- yes AB,AC,CD -- yes AB,AC,CE -- yes AB,AC,DF -- yes AB,AC,EF -- yes AB,BD,BE -- yes AB,BD,CD -- no AB,BD,CE -- no AB,BD,DF -- no AB,BD,EF -- no AB,BE,CD -- no AB,BE,CE -- no AB,BE,DF -- no AB,BE,EF -- no AB,CD,CE -- yes AB,CD,DF -- no AB,CD,EF -- no AB,CE,DF -- no AB,CE,EF -- no AB,DF,EF -- yes AC,BD,BE -- yes AC,BD,CD -- no AC,BD,CE -- no AC,BD,DF -- no AC,BD,EF -- no AC,BE,CD -- no AC,BE,CE -- no AC,BE,DF -- no AC,BE,EF -- no AC,CD,CE -- yes AC,CD,DF -- no AC,CD,EF -- no AC,CE,DF -- no AC,CE,EF -- no AC,DF,EF -- yes BD,BE,CD -- no BD,BE,CE -- no BD,BE,DF -- no BD,BE,EF -- no BD,CD,CE -- no BD,CD,DF -- yes BD,CD,EF -- yes BD,CE,DF -- no BD,CE,EF -- no BD,DF,EF -- yes BE,CD,CE -- no BE,CD,DF -- no BE,CD,EF -- no BE,CE,DF -- yes BE,CE,EF -- yes BE,DF,EF -- yes CD,CE,DF -- no CD,CE,EF -- no CD,DF,EF -- yes CE,DF,EF -- yes Subsets of 4 links, probability = p4 (1 - p)4, disconnects = 8! / 4! / (8-4)! = 70 With 6 vertices, a spanning tree for this graph must have 5 edges Removing 4 edges leaves only 4 edges, not enough for a spanning tree Therefore, removing 4 (or more) edges disconnects the graph   Subsets of 5 links, probability = p5 (1 - p)3, disconnects = 8! / 5! / (8-5)! = 56   Subsets of 6 links, probability = p6 (1 - p)2, disconnects = 8! / 6! / (8-6)! = 28   Subsets of 7 links, probability = p7 (1 - p), disconnects = 8! / 7! / (8-7)! = 8   Subsets of 8 links, probability = p8, disconnects = 1   Probability of network failure = 2 p2 (1 - p)6 + 20 p3 (1 - p)5 + 70 p4 (1 - p)4 + 56 p5 (1 - p)3 + 28 p6 (1 - p)2 + 8 p7 (1 - p) + p8 = 2 p2 + 8 p3 - 64 p5 + 110 p6 - 72 p7 + 17 p8 Monte Carlo Analysis of Connectivity ConnectedNetwork01 Class edu.rit.datacomm2.traffic.ConnectedNetwork01 -- Source code Class ConnectedNetwork01 is a Monte Carlo program that determines the probability that a network has failed, given the probability that each link in the network has failed. The network's topology is a complete graph on N nodes. There are N(N−1)/2 links in the network. The probability that a link has failed is p. The network has failed if the network is not connected. The program generates a plot of the probability that the network has failed as a function of p from p = 0.0 to p = 1.0. For each value of p, the program does a given number of trials. For each trial, the program generates an N-node network, adding each potential link with probability 1-p, and determines if the network is disconnected. The number of disconnected networks divided by the number of trials gives the network failure probability. Usage: java edu.rit.datacomm2.traffic.ConnectedNetwork01 seed trials N seed = Random seed trials = Number of trials for each value of p N = Number of network nodes java edu.rit.datacomm2.traffic.ConnectedNetwork01 142857 2000 4 java edu.rit.datacomm2.traffic.ConnectedNetwork01 142857 2000 8 java edu.rit.datacomm2.traffic.ConnectedNetwork01 142857 2000 12 ConnectedNetwork02 Class edu.rit.datacomm2.traffic.ConnectedNetwork02 -- Source code Class ConnectedNetwork02 is a Monte Carlo program that determines the probability that a network has failed, given the probability that each link in the network has failed. The network's topology consists of 12 nodes and 16 links. The probability that a link has failed is p. The network has failed if the network is not connected. The program generates a plot of the probability that the network has failed as a function of p from p = 0.0 to p = 1.0. For each value of p, the program does a given number of trials. For each trial, the program generates an N-node network, adding each potential link with probability 1-p, and determines if the network is disconnected. The number of disconnected networks divided by the number of trials gives the network failure probability. Usage: java edu.rit.datacomm2.traffic.ConnectedNetwork02 seed trials seed = Random seed trials = Number of trials for each value of p java edu.rit.datacomm2.traffic.ConnectedNetwork02 142857 2000 ConnectedNetwork03 Class edu.rit.datacomm2.traffic.ConnectedNetwork03 -- Source code Class ConnectedNetwork03 is a Monte Carlo program that determines the probability that a network has failed, given the probability that each link in the network has failed. The network's topology consists of 6 nodes and 8 links. The probability that a link has failed is p. The network has failed if the network is not connected. The program generates a plot of the probability that the network has failed as a function of p from p = 0.0 to p = 1.0. For each value of p, the program does a given number of trials. For each trial, the program generates an N-node network, adding each potential link with probability 1-p, and determines if the network is disconnected. The number of disconnected networks divided by the number of trials gives the network failure probability. The program also plots the analytic formula for the network failure probability. Usage: java edu.rit.datacomm2.traffic.ConnectedNetwork03 seed trials seed = Random seed trials = Number of trials for each value of p java edu.rit.datacomm2.traffic.ConnectedNetwork03 142857 2000 Data Communications and Networks II 4003-541-70/4005-741-70 Spring Quarter 2006 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 13-Apr-2006. Please send comments to ark­@­cs.rit.edu.