Network Design - Chapter 4: Graph Theory and Topology Design - University of Pittsburgh

Nội dung text: Network Design - Chapter 4: Graph Theory and Topology Design - University of Pittsburgh

1. Graph Theory and Topology Design David Tipper Associate Professor Department of Information Science and Telecommunications University of Pittsburgh tipper@tele.pitt.edu Slides 4 Top Down Network Design Approach • Top down network design project approach should follow three phases: – Conceptual Model • Objectives, Requirements, Constraints – Logical Model • Technology, network graph, node location, link size, etc. (where algorithms are used to minimize cost) – Physical Model • Specific hardware/software implementations • (e.g., wiring diagram, repeater locations, etc.) • Focus on Algorithms for Logical Model Design – Graph Theory – Optimization Telcom 2110 Spring 2006 2 1
2. Graphs •Telecommunication and computer networks are naturally represented by graphs •A graph G = (V, E) is a mathematical structure consisting of two sets V and E. •Elements of V are called vertices (or nodes) –For example, switches, routers, cross conects •Elements of E are called edges –Communication links are edges (wired or wireless) Vertex –Each edge has two endpoints( v 1 ,v2)∈V A D F Edge V ={A,B,C,D,E,F,G} E B E = {(A,B),(A,C), (A,D), (B,C), . , (F,G)} C G Telcom 2110 Spring 2006 3 Terminology • Loop – an edge where both endpoints are the same vertex. Also called a self-loop. • Parallel edges – a collection of two or more edges having identical end. Also called a multi-edge. • A graph is simple if it has no loops or parallel edges. • Focus on simple graphs. – When considering reliability, we will introduce parallel edges if the network has parallel links. • The degree of a node: the number of edges in the graph that have the node as an endpoint – Number of outgoing links of a node Telcom 2110 Spring 2006 4 2
3. Terminology Cont. Example: simple Graph (i.e., no loops or parallel edges) Degree of Vertex A = 3, Degree of Vertex E = 2 A D Size of graph characterized by F Number of edges |E| and number Of vertices |V| E Example |V| = 7, |E| = 10 B C G •Adjacent vertices: Two nodes are adjacent if there is an edge that has them as endpoints Example: A and B are adjacent, A and E are not Telcom 2110 Spring 2006 6 Paths and Cycles • Path from vertex A to vertex Z: an alternating sequence of vertices and edges, representing a continuous traversal from vertex A to vertex Z. Can be represented by sequence of edges or nodes in path • Trail: a path with no repeated edges. •Cycle: a path starting and ending on the same node • Connected graph: a graph in which every pair of distinct vertices has a path between them. Telcom 2110 Spring 2006 8 3
4. Terminology Cont. Example: Path from A to G is given by (A,D),(D,E),(E,G) Cycle at A is given by (A,C), (C,B), (B,A) Example is a connected Graph A D F E B C G Telcom 2110 Spring 2006 9 Trees • Tree: a connected, simple graph without cycles. • Any tree with n nodes has n-1 edges. A D F E B C G Telcom 2110 Spring 2006 10 4
5. Trees Terminoloy Typical Cellular Network • Root: One vertex of a tree EIR may be designated as a root AUC (has no parent only childern) HLR IBM VLR • Each vertex (besides root) MSC has a single parent vertex SD B ay Net works Ce ntillion 1400 ETHERLI NK RS 232C INS ACT ALM P* 8x50 RST OOO130 A O N 6 PC C ARD SD which is the vertex closest to Bay Networks Centillion 1400 ALM PW R ALM FAN0 FAN1 PW R0 PWR1 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST O OO130 A O N 6 PC CARD ALM PW R ALM FAN 0 FAN1 PWR0 PW R1 BSC BSC the root SD Bay Networks Centillion 1400 ETHERLINK RS 232C INS ACT ALM P* 8x50 RST O OO130 A O N 6 PC CARD ALM PW R ALM FAN 0 FAN1 PWR0 PW R1 BSC • Each vertex has zero or more child vertices which are BS3 BS3 BS2 BS4 the adjacent vertices farthest BS2 BS4 BS1 from the root BS1 BS7 BS5 BS7 BS5 • Leaf: a vertex without a child BS6 BS6 Telcom 2110 Spring 2006 11 Star • A tree is a star if only 1 node has degree >1 B C P Y Q X Z A D Telcom 2110 Spring 2006 12 5
6. Chains •A chain is a tree with no nodes of degree >2 B C P Q Y X A Z D • Trees are often the cheapest network design – However have poor reliability Telcom 2110 Spring 2006 13 Subgraphs and Trees • Given a set of nodes to connect – how to construct a tree? First understand subgraphs • Subgraph of graph G obtained by selecting number of edges and vertices from G – For each edge, the two vertices incident on that edge must be selected • Give graph G(E,V), graph G’(E’,V’) is a subgraph of G iff V’ ⊆ V and E’ ⊆ E and ∃ e’ ∈ E’, if e’ incident on v’ and w’ then v’, w’ ∈ V’ Telcom 2110 Spring 2006 14 6
7. Spanning Tree • Subgraph T of graph G is a spanning tree if – T is a tree – T includes all vertices of G • In other words remove edges from G such that: – Remove all cycles – Maintain connectivity • Not usually unique Telcom 2110 Spring 2006 15 Spanning Tree Examples Telcom 2110 Spring 2006 16 7
8. Weighted Graph • A graph G is weighted if there is a value associated with each edge (e.g. link speed, cost, etc.) – Weight of the edge ei = w(ei) • We often denote this graph (G, w). If G’ is any subgraph of G, then its weight is the sum of the ∑e∈G' w(e) weight of it’s edges w(G’) = • Let G be a connected weighted graph. • A spanning subgraph includes all the nodes of G. • A tree T is a spanning tree of G if T is a spanning subgraph of G. Telcom 2110 Spring 2006 17 Finding the MST • The Minimal Spanning Tree (MST) A spanning tree of G whose total edge-weight is a minimum. • Two algorithms Kruskal and Prim •Prim – starts by selecting a node, – adding the “least expensive edge” – iterates until tree is built • Kruskal achieves the MST by starting with a graph and cutting out edges • MSTs are used in for network designs when have just few nodes and cost is dominant factor Telcom 2110 Spring 2006 18 8
9. Prim’s Algorithm • Input : a weighted connected graph G=(V,E). • Output : a minimum spanning tree T. U = set of all nodes in MST V = set of all nodes that are NOT yet in MST, but they’re adjacent to nodes in U. Telcom 2110 Spring 2006 19 Prim’s Algorithm (cont’d) • 1. Place any node in U, and update V . • 2. Find the edge with smallest weight that connects a node in V to a node in U • 3. Add that edge to the tree, and update U & V. • 4. Repeat 2 & 3 until all nodes are included, i.e., | U | = | N |. Telcom 2110 Spring 2006 20 9
10. Algorithm Example Apply Prim algorithm to the graph below 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 21 Prim’s Algorithm Example Arbitrarily pick node D to start with – min cost link to a node in V is (D,A) Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 22 10
11. Prim’s Algorithm Example Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 D,A,B C,E,F,G 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 23 Prim’s Algorithm Example Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 D,A,B C,E,F,G 3 D,A,B,C E,F,G <= arbitrarily pick (D,C) link rather than (B,C) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 24 11
12. Prim’s Algorithm Example Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 D,A,B C,E,F,G 3 D,A,B,C E,F,G 4 D,A,B,C,G E,F 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 25 Prim’s Algorithm Example Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 D,A,B C,E,F,G 3 D,A,B,C E,F,G 4 D,A,B,C,G E,F 5 D,A,B,C,G,E F 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 26 12
13. Prim’s Algorithm Example Iteration U V 0 D A,B,C,E,F,G 1 D,A B,C,E,F,G 2 D,A,B C,E,F,G 3 D,A,B,C E,F,G 4 D,A,B,C,G E,F 5 D,A,B,C,G,E F 6 D,A,B,C,G,E,F <= arbitrarily pick (G,F) link rather than (D,F) link MST is complete weight is 11 2 3 A D F 1 4 2 3 E 3 B 1 2 C G Telcom 2110 Spring 2006 2 27 Kruskal’s Algorithm • 1. Check that the graph G is connected. If it is not connected stop • 2. Sort the edges of the graph G in ascending order of weight. • 3. Mark each node as a separate component. • 4. Examine each of the sorted edges: if the edge connects two separate components, add it ; otherwise, discard and go to step1 Telcom 2110 Spring 2006 28 13
14. Algorithm Example Apply Kruskal’s algorithm to the graph below Pick one of the edges with minimum weight Arbitrarily pick (A,B) rather than (E,G) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 29 Algorithm Example Iteration 2 pick (E,G) as it has minimum weight 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 30 14
15. Algorithm Example Iteration 3 Arbitrarily pick (B,C) out of possible choices (B,C), (A,D), (C,D),(C,G) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 31 Algorithm Example Iteration 4 Arbitrarily pick (C,D) out of possible choices (A,D), (C,D),(C,G) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 32 15
16. Algorithm Example Iteration 5 pick (C,G) as (A,D) is not a valid choice (A and D are in same component) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 33 Algorithm Example Iteration 6 pick (G,F) from possible choices (D,F), (G,F) MST is complete weight is 11 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 34 16
17. MST’s Drawbacks • An MST for 10 nodes N6 N2 N7 N10 N9 N1 N5 N4 N8 N3 The network is beginning to have a leggy look, which means that the traffic is taking a circuitous route between its source and destination. To qualify the legginess in the network, we make the following definition. Telcom 2110 Spring 2006 35 Number of Hops • Number of Hops The number of hops between node n1 and n2 is the number of edges in the path chosen by the routing algorithm for the traffic flowing from n1 to n2. Denoted by hops (n1,n2) • Mean number of hops in a network is: Traffic(n1,n2)×hops(n1,n2) ∑n1,n2 hops = Traffic(n1,n2) ∑n1,n2 Telcom 2110 Spring 2006 36 17
18. MSTs Do Not Scale • MSTs do not scale with increasing network size – As number of nodes grows, mean number of hops a message must traverse grows – Use shortest path trees (SPTs) not MSTs hops Table of mean number Number of nodes of hops for 5 randomly generated networks 5 1.8 connected by MSTs 10 3.1778 20 4.4158 50 8.5159 100 13.9479 Telcom 2110 Spring 2006 37 Shortest-Path Trees (SPT) • Shortest Path Given a weighted graph (G,W) and nodes n1 and n2, the shortest path from n1 to n2 is a path P such that the sum of link weights along the path ∑ w ( e ) is a minimum. e∈P • Shortest Path Tree – Given a weighted graph (G,W) and a node n1, a shortest – path tree rooted at n1 is a tree T such that, for any other node n2 ∈ G, the path from n1 to n2 in the tree T is a shortest path between the nodes. • SPT vs. MST – SPT cost more, has lower utilization and lower delay, smaller average hop count Telcom 2110 Spring 2006 40 18
19. Finding a Shortest Path Tree • Given a connected graph G and a node selected to be a root • Dijkstra’s algorithm can be used to find a shortest path tree • The algorithm is similar to Prim’s in that one iteratively builds a tree∞ – Let V = set of vertices – S = source vertex – U = set of vertices incorporated so far – W(e) is the link cost of edge e , specifically w(i,j) is the cost from vertex i to vertex j , w(i,j) = if the two vertices are not directly connected – d_min is the minimum cost path from vertex s to vertex n that is currently known Telcom 2110 Spring 2006 41 Finding a Shortest Path Tree • Dijkstra’s Algorithm • 1. Initialization: Mark every node as unscanned and U = {s}, d_min(n) = w(s,n) for n ≠ s ∞ • 2. Loop until you have scanned all the nodes. A. Find the node x not in tree T with the minimum cost path from s, add x to T B. Update the minimum cost paths d_min(n) = min{ d_min(n), d_min(x) + w(x,n) } Telcom 2110 Spring 2006 42 19
20. Algorithm Example Apply Dijkstra’s algorithm to find a SPT rooted at D Iteration T d_min(A) Path d_min(B) Path d_min(C) Path d_min(E) Path d_min(F) Path d_min(G) Path 1 {D} 2 (D,A) ∞ - 2 (D,C) 4 (D,E) 3 (D,F) ∞ - 2 {D,C} 2 (D,A) 4 (B,C),(C,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 2 3 A D F 1 4 2 3 E 3 B 1 2 C G 2 Telcom 2110 Spring 2006 43 Algorithm Example Iteration T d_min(A) Path d_min(B) Path d_min(C) Path d_min(E) Path d_min(F) Path d_min(G) Path 1 {D} 2 (D,A) ∞ - 2 (D,C) 4 (D,E) 3 (D,F) ∞ - 2 {D,C} 2 (D,A) 4 (B,C),(C,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 3 {D,C,A} 2 (D,A) 3 (B,A),(A,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 4 {D,C,A,F} 2 (D,A) 3 (B,A),(A,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 5 {D,C,A,F,B} 2 (D,A) 3 (B,A),(A,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 6 {D,C,A,F,B,E} 2 (D,A) 3 (B,A),(A,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) 7{D,C,A,F,B,E,G} 2 (D,A) 3 (B,A),(A,D) 2 (D,C) 4 (D,E) 3 (D,F) 4 (G,C),(C,D) MST SPT is a Star topology Telcom 2110 Spring 2006 44 20
21. Prim – Dijkstra Trees • MSTs have high delay – but are cheap • SPTs have lower delay and utilization but more expensive • Prim-Dijkstra algorithm – interpolates between MST and SPT (comprise) • Algorithms : 1) Prim’s: min neighbors dist(node, neighbor) 2) Dijkstra’s: min neighbors (dist(root, neighbor) + dist(neighbor, node)) 3) Prim-Dijkstra’s: 0 ≤ α ≤1 min neighbors (α × dist(root, neighbor) + dist(neighbor, node)) Telcom 2110 Spring 2006 45 Prim – Dijkstra Trees (cont’d) • If α = 0 , we build a MST. • If α = 1 , we build a SPT. If we have such a • The α delay, and cost for various Prim-Dijkstra trees in large set of designs a 100 node network – distance is cost. shown in the table, how to select the best? α Design hops Link delay Cost 0(MST) N0 13.9479 0.3066 $325,516 0.1 N1 10.5717 0.1451 $280,162 0.2 N2 7.8640 0.1067 $247,217 0.3 N3 6.7762 0.0913 $243,551 0.4 N4 5.6679 0.0746 $248,650 0.5 N5 4.6303 0.0598 $253,579 0.6 N6 3.7063 0.0467 $273,742 0.7 N7 3.0186 0.0380 $295,012 0.8 N8 2.2879 0.0277 $378,792 0.9 N9 1.9800 0.0233 $453,861 Telcom 2110 Spring 2006 46 21
22. Dominance • If we have a large set of designs, the problem is to decide which merit consideration and which should be discarded. • To help us do this we impose a partial ordering on the designs. • Suppose design D1 has cost C1 and performance P1. Suppose design D2 has cost C2 and performance P2. We will say D1 dominates D2, or D1 D2, if C1 P2. Telcom 2110 Spring 2006 47 Dominance Among Designs Design Dominates Link delay Cost N0 ∅ 0.3066 $325,516 N1 N0 0.1451 $280,162 N2 N0,N1 0.1067 $247,217 N3 N0,N1,N2 0.0913 $243,551 N4 N0,N1 0.0746 $248,650 N5 N0,N1 0.0598 $253,579 N6 N0,N1 0.0467 $273,742 N7 N0 0.0380 $295,012 N8 ∅ 0.0277 $378,792 N9 ∅ 0.0233 $453,861 Telcom 2110 Spring 2006 48 22
23. Dominance of Designs • Given a pair of nondominating designs S1 and S2, 1 must be cheaper and 1 must have lower delay. • After rejecting the dominated designs, we still have 7 designs left to choose from. One way to clarify their differences further is to discuss the marginal cost of delay: (C1 - C2)/ (D2 –D1) •Example Design Link Delay Cost Marginal Cost N3 .0913 $243,551 - N4 .0746 $248,650 305,329 N5 . 0598 $253,579 333,041 N6 .0467 $273,742 1,539,160 Telcom 2110 Spring 2006 49 Rings (Tours) • A tree maybe too unreliable to be a good network design. • Tours (Rings) are far more reliable yet only have 1 additional link. • In graph theory, a tour refers to a possible solution of the traveling salesman problem (TSP). Given a set of vertices V = {V1,V2, VN} a tour is a set of N edges E such that each vertex has degree 2 and the graph is connected Telcom 2110 Spring 2006 50 23
24. Reliability • Consider a 5-node tree: p is the probability a link fails b d a e c P(no_link_failures) = ( 1 − p ) 4 P(failure) = 1− (1− p)4 = 1− 4 p + 6 p 2 − 4 p 3 + p 4 ≈ 4 p Telcom 2110 Spring 2006 51 Reliability • For the 5-node ring network : b d a e c If q = 1-p, then 5 4 2 3 3 2 4 5 Pring( failure) =1−q −5pq = 10 p q +10 p q + 5p q + p ≈ 10 p 2 q 3 Telcom 2110 Spring 2006 52 24
25. Reliability (cont’d) • Comparing reliabilities – one can see advantage of ring • p 4p (tree) 10 p 2 q 3 (ring) 0.1 0.4 0.0729 0.01 0.04 0.00097 0.001 0.004 10 − 5 0.0001 0.0004 −7 −4 10 10 • How can one find a good ring topology? Telcom 2110 Spring 2006 53 Traveling Salesman Problem (TSP) • Number of tours is in a set of n vertices is (n −1)!/ 2 • Finding a tour is equivalent to the Traveling Salesman Problem (v ,v , ,v ) • Given a set of vertices t1 t2 tn and a distance function d : V × V → ℜ + , the traveling salesman problem is to find the tour T such that n d ( v , v ) ∑ t i t i +1 is a minimum. i = 1 • TSP is a tough problem (NP Hard) • Solve using use heuristic algorithms. Telcom 2110 Spring 2006 54 25
26. Nearest-neighbor Algorithm 1. Start at a node we call root and set current_node = root. 2. Loop until we have all the nodes in the tour. – Find the node closest (i.e., min cost or distance ) to the current_node that is not in the tour. We call this best_node. – Create an edge between current_node and best_node. – Reset the current_node to the best_node. 3. Finally create an edge between the last node and the root to complete the tour. Telcom 2110 Spring 2006 55 Nearest Neighbor Example • Example: Start at node A Table 6.1 Example Network Link Costs Node B C D E F G Node A 5 6 9 10 11 15 B 9 6 6 8 17 C 7 9 8 12 D 10 5 11 E 14 9 F 8 Telcom 2110 Spring 2006 56 26
27. Nearest Neighbor Example 1 A B G C D F E Telcom 2110 Spring 2006 57 Nearest Neighbor Example 1 A B G C 2 D F E Telcom 2110 Spring 2006 58 27
28. Nearest Neighbor Example 1 A B G C 2 D F 3 E Telcom 2110 Spring 2006 59 Nearest Neighbor Example 1 A B G C 2 4 D F 3 E Telcom 2110 Spring 2006 60 28
29. Nearest Neighbor Example 1 A B G C 5 2 4 D F 3 E Telcom 2110 Spring 2006 61 Nearest Neighbor Example 1 A B G C 5 2 4 D F 3 6 E Telcom 2110 Spring 2006 62 29
30. Nearest Neighbor Example 1 A B 7 G C 5 2 4 D F 3 6 E Telcom 2110 Spring 2006 63 Nearest-neighbor Algorithm Observation: * Good (?): We are trying to produce a short tour, we will always move to the best possible next location. * Bad (?): When we look at the figure produced, we can see the lines may cross frequently. * Can we improve it? How can we measure the goodness (creditability) of an algorithm? Telcom 2110 Spring 2006 64 30
31. Improved nearest-neighbor algorithm Differs from the simpler algorithm in two ways: • First, the closest node doesn’t mean the closest node to the last added node; it means the closest node to any node in the partial tour we have built. • Second, when we add best_node to the tour, we don’t add it at the end of the tour, rather, we do a test to find the best place to add it, such that dist(Ni ,best _ node) + dist(best _ node, N j ) − dist(Ni , N j ) is the smallest possible value among all nodes and that are Ni N j adjacent in the partially built tour. Telcom 2110 Spring 2006 65 Nearest Neighbor • Example: Start at node A Table 6.1 Example Network Link Costs Node B C D E F G Node A 5 6 9 10 11 15 B 9 8 8 8 17 C 7 9 7 12 D 10 5 11 E 14 9 F 8 Telcom 2110 Spring 2006 66 31
32. (Rings) Do Not Scale n + 1 Given uniform traffic any TSP tour of n nodes has hops = 4 n 2 if n is odd and 4 ( n − 1 ) if n is even. • Comparison of average number of hops for MST and TSP: hops hops Number of nodes MST TSP 5 1.8 1.5 10 3.1778 2.777 20 4.4158 5.263 50 8.5159 12.755 100 13.9479 25.252 Telcom 2110 Spring 2006 67 Improving Ring Topologies • Can reduce hop count by adopting a multi-ring topology. • Topology is a set of interconnected rings • Example, a TSP tour on 20 nodes. The average number of hops is 5.263. We want to reduce the average hop count but keep the 2-connectivity. N20 N13 N6 N2 N7 N15 N9 N14 N10 N1 N5 N9 N12 N16 N18 N17 N4 N8 N11 N3 Telcom 2110 Spring 2006 68 32
33. Divide and Conquer • Use a Divide and Conquer approach • Divide nodes into disjoint subset , construct ring for each subset, then join rings •Example – Divide the 20 nodes into 2 “compact” clusters of 10 nodes each. Call these clusters C1 and C2. (We might divide the 20 nodes by ranges of their coordinates, for example, to create the 2 clusters.) – Use the nearest-neighbor algorithm to design 2 TSP tours on each cluster. – Select v1 ∈C1 and v2 ∈C2 to be the 2 nodes such that the distance is the minimum. – Now select v3 ∈C1-v1 and v4 ∈C2-v2 to be the 2 nodes such that the distance is the minimum. – Add the edges (v1,v2), (v3,v4) to the design. Telcom 2110 Spring 2006 69 Divide and Conquer • In the figure, we have a TSP tour on 20 nodes. The average number of hops is 5.263. We want to reduce the average hop count but keep the 2-connectivity. N20 N13 N6 N2 N7 N15 N9 N14 N10 N1 N5 N9 N12 N16 N18 N17 N4 N8 N11 N3 Telcom 2110 Spring 2006 70 33
34. Divide and Conquer • Grouping into 2 groups of 10 nodes. Then running the nearest neighbor algorithm gives two rings as below. Note that the average hop count is reduced N20 N13 N6 N2 N7 N15 N9 N14 N10 N1 N5 N9 N12 N16 N18 N17 N4 N8 N11 N3 Telcom 2110 Spring 2006 71 Divide and Conquer • Grouping into 2 groups of 10 nodes. Then running the nearest neighbor algorithm gives two rings as below. Joining the two rings at their closet points results in N20 N13 N6 N2 N7 N15 N9 N14 N10 N1 N5 N9 N12 N16 N18 N17 N4 N8 N11 N3 Telcom 2110 Spring 2006 72 34
35. Level 3 N. American Network Telcom 2110 Spring 2006 73 Summary • If the traffic is small when compared to link size, then the optimal networks are MSTs and TSP tours, depending on the reliability desired. • Both MSTs and TSP tours do not scale. • The growth in the average # of hops is at the heart of the problem. It’s better to build a Prim- Dijkstra tree or a multi-ring “ring of rings” to control the length of the routes. Telcom 2110 Spring 2006 74 35