Constrained Minimum Weight Spanning TreesExamples of additional constraintsExamples of additional constraintsExamples of additional constraintsExamples of additional constraintsExamples of additional constraintsThree Heuristic AlgorithmsThree Heuristic AlgorithmsThree Heuristic AlgorithmsThree Heuristic AlgorithmsCapacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Capacitated Minimum Spanning Tree Problem (CMST)Sharma’s AlgorithmSharma’s AlgorithmSharma’s AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmCMST AlgorithmSlide 39The Esau-Williams AlgorithmThe Esau-Williams AlgorithmThe Esau-Williams AlgorithmThe Esau-Williams AlgorithmThe Esau-Williams AlgorithmConstrained Minimum Weight Spanning Trees•In designing a realistic tree network topology, usually there are other constraints to be taken into account. They often make the problem substantially more difficult.•In the constrained MWST design we are looking for an MWST that satisfies one or more addional constraints. Below we list some examples, along with their 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 central node (root). If the root exercises some centralized control or distributes time sensitive data, then low delay to the other nodes may be important, which is supported by a low height tree.Examples of additional constraints•Every node can have at most a given number of neighbors in the tree.–Motivation: the processing capacity of nodes may limit the number of links that can be handled at the nodes.Examples of additional constraints•Every node (except the leaves) can have at least a given number of children in the tree.–Motivation: with more outgoing links at a node there are possibly more options for routing and load balancing. Moreover, more branching will tend to make the tree shallower, resulting in lower expected delays.Examples of additional constraints•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 communicate with low delay (regardless of the choice of a root).Examples of additional constraints•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 in the tree, then the subtree (cluster) rooted at A can have altogether at most υ nodes (including A itself).–Motivation: each outgoing link from the root carries data to the group of nodes in the subtree. The larger is such a cluster, the larger is the expected data rate. The speed of the link and of the corresponding output port of the root node may limit this.Three Heuristic Algorithms•Modified Kruskal Algorithm–Idea: 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 it directly to the root. After such a cluster is connected to the root, and there are still leftover nodes, then repeat the procedure with the leftover nodes (exluding those that already belong to a cluster).Three Heuristic Algorithms•Three Heuristic Algorithms•Question: What is the rationale behind this idea?–Answer: The algorithm prefers to grow those clusters that are farther from the root. (They have larger di value, so the recomputed weights will be smaller). This results in a more balanced cluster structure. Why? In the modified Kruskal algorithm, when the clusters close to the root saturate and there are still leftover nodes, then possibly these can only be connected to the root via very long links, which tends to result in an unbalanced cluster structure.–Note: The formula (1) is only one example of the possible ways of adjusting the costs. Many other heuristic choices are possible to govern the algorithm to find a better network topology.Three Heuristic Algorithms•Sharma El-Bardai Algorithm–Idea: Sweep the plane with a ray rotating around the root, as a center. As the ray rotates, after sweeping through υ nodes, put them in a cluster. Connect the nearest node of the cluster to the root and within the cluster build an unconstrained MWST. Then start a new cluster by sweeping the ray thought the next υ nodes, and so forth.–Advantage: Those nodes will tend to cluster that are roughly in the same direction 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 spread."Capacitated Minimum Spanning Tree Problem (CMST)•CMST problem: –Given a central node N0 and –a set of other nodes (N1, …, Nn), –a set of weights(w1,…,wn) for each node, –the capacity of a link, W, and –a cost matrix Cost(i,j), –find a set of trees T1, …, Tk such that each Ni belongs to exactly one Tj and each Tj contains N0.Capacitated Minimum Spanning Tree Problem (CMST)•consider a connected graph G = (V,E)•with node set V = {0,1,,,n}•and Edge set E•Each node i in V has a unit node weight bi=1, with b0=0 . •The node weights may be interpreted as flow requirements •a non-negative Edge weight cij represents the cost of using Edge (i,j) in E . •Node is a special node called center node and will be the root of the tree.Capacitated Minimum Spanning Tree Problem (CMST)•We define a rooted sub-tree (or component) ri of a tree spanning V as its maximal sub-graph that is connected to the center by edge (0,i) (which may be referred to as central edge). •The flow requirement of a sub-tree is the sum of the node weights of the included nodes. To satisfy the capacity constraint the flow requirement of each sub-tree must not exceed a given capacity K.•The capacitated minimum spanning tree (CMST) problem is: finding a minimum cost tree spanning node
View Full Document
Unlocking...