Spanning Tree Based Network TopologyDesignA spanning tree is the smallest connected network topology that includes allnodes.Unconstrained Miniumum Weight Spanning Tree (MWST)This is well known from any introductory course in discrete mathematics, letus just recall the basic facts.Two fundamental algorithms: Kruskal and Prim.Kruskal’s algorithmIdea: greedy algorithm. Always add the next cheapest link that does notform a circle (loop) with the already selected links.Worst-case complexity: O(n2) for a graph with n nodes.Prim’s algorithmIdea: grow a spanning tree by adding in each step the cheapest link betweenthe existing tree and the rest of the graph (this automatically guaranteesloop avoidance).Worst-case complexity: O(n2) for a graph with n nodes.What is the difference between the two algorithms? In Prim’s algorithm wegrow one tree until it becomes a spanning tree. In Kruskal’s algorithm wegrow a forest (i.e., possibly several trees) until they finally merge into a singlespanning tree.Constrained Minimum Weight Spanning TreesIn designing a realistic tree network topology, usually there are other con-straints to be taken into account. They often make the problem substantiallymore difficult.In the constrained MWST design we are looking for an MWST that satisfiesone or more addional constraints. Below we list some examples, along withtheir networking motivation.Examples of additional constraints:• The height of the tree can be at most a given value.Motivation: to make all nodes reachable on short paths from a centralnode (root). If the root exercises some centralized control or distributestime sensitive data, then low delay to the other nodes may be impor-tant, which is supported by a low height tree.• Every node can have at most a given number of neighbors in the tree.Motivation: the processing capacity of nodes may limit the number oflinks that can be handled at the nodes.• Every node (except the leaves) can have at least a given number ofchildren in the tree.Motivation: with more outgoing links at a node there are possibly moreoptions for routing and load balancing. Moreover, more branching willtend to make the tree shallower, resulting in lower expected delays.• The diameter of the tree should be low (diameter = the longest hop-distance that occurs in the tree between any two nodes).Motivation: if the diameter is low, then any two nodes can communi-cate with low delay (regardless of the choice of a root).• Any subtree rooted at a neighbor of the main root can have at most νnodes. That is, if a node A is directly connected to the main root inthe tree, then the subtree (cluster) rooted at A can have altogether atmost ν nodes (including A itself).Motivation: each outgoing link from the root carries data to the groupof nodes in the subtree. The larger is such a cluster, the larger is theexpected data rate. The speed of the link and of the correspondingoutput port of the root node may limit this.Let us outline three heuristic algorithms for the last example.Modified Kruskal AlgorithmIdea: Run the original Kruskal algorithm on the nodes other than the root,but whenever a cluster arises pick its node nearest to the root and connect itdirectly to the root. After such a cluster is connected to the root, and thereare still leftover nodes, then repeat the procedure with the leftover nodes(exluding those that already belong to a cluster).Esau-Williams AlgorithmIdea: Works like the modified Kruskal algorithm, but after adding a newlink, the weights are recomputed asc0ij= cij− αdi+ dj2(1)where diis the distance to the main root of the closest node in the cluster towhich i belongs, and α > 0 is a parameter that we can choose.Question: What is the rationale behind this idea?Answer: The algorithm prefers to grow those clusters that are farther fromthe root. (They have larger divalue, so the recomputed weights will besmaller). This results in a more balanced cluster structure. Why? In themodified Kruskal algorithm, when the clusters close to the ro ot saturate andthere are still leftover nodes, then possibly these can only be connected tothe root via very long links, which tends to result in an unbalanced clusterstructure.Note: The formula (1) is only one example of the possible ways of adjustingthe costs. Many other heuristic choices are possible to govern the algorithmto find a better network topology.Sharma El-Bardai AlgorithmIdea: Sweep the plane with a ray rotating around the root, as a center. As theray rotates, after sweeping through ν nodes, put them in a cluster. Connectthe nearest node of the cluster to the root and within the cluster build anunconstrained MWST. Then start a new cluster by sweeping the ray thoughtthe next ν nodes, and so forth.Advantage: Those nodes will tend to cluster that are roughly in the samedirection from the root, so the geographical location (in the sense of direction)is better taken into account.Disadvantage: The algorithm may be fooled by configurations in which the“angular spread” is small with respect to the ”distance
View Full Document
Unlocking...