Leigh Stoller committed Jul 03, 2002 1 2 3 4 5 6 ``````# # EMULAB-COPYRIGHT # Copyright (c) 2000-2002 University of Utah and the Flux Group. # All rights reserved. # `````` Christopher Alfeld committed Jan 18, 2002 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 ``````Interesting things about Assign This document is not meant to be a cohesive whole. Rather a brain dump of text, thoughts, and information. Solutions in assign are measured by two criteria. The first is a measure of basic quality, very similar to the cost functions you would find in traditional SA. The second is a measure of validity. It is an integer recording the number of violations, or broken constraints. By allowing invalid states the SA algorithm can traverse non-solution space to find other solutions. Having two separate measures allows find tuning of the SA algorithm. In particular it allows us to control the tendency to wander into non-solution space. A secondary advantage is that by tracking the source of each violation it is easy to understand the cases where assign fails to find a valid solution. The basic problem is to map one graph to another. It is not, however, simply a matter of connecting up vnodes and pnodes and vlinks and plinks. Multiple vnodes may map to a single pnodes, as is the case with delay nodes. Links are even more complicated. Certain plinks, such as interswitch trunks, may have multiple vlinks mapped to them. On the other hand, each vlink will probably traverse multiple plinks. It is quite often that a vlink will map to multiple plinks, some of which have other vlinks mapped to them. These many-to-one and one-to-many relationships complicate scoring and understanding. Further complications arise from the many criteria that solutions are judged by. How well vnodes and pnodes match, the feasibility of emulating vlinks, the "cheapness" of all resources used, are some of the basic criteria. In addition a solution is based on how well it satisfies specific requests, such as that a node already have the correct disk image installed. The "cheapness" of nods is not straight forward, a node with specialized hardware should be more expensive than its non specialized counterparts, yet that expense should only be considered if the hardware would not be used. Assign also optimizes for node homogeneity, both at a general physical level, and according to logical classification of vnodes by the user. All of these criteria have various priorities and interact with each other during the algorithm. Given the complexity of the scoring and the vast number of times the score will be recalculated during a run it is infeasible to calculate the score from scratch at each modification. Instead, the change in the score needs to be rapidly calculated. The two basic operations in assign are mapping a vnode to a pnode and unmapping a vnode from its pnode. At each operation the change in score (both quality and violations) is calculated and applied. The change in score is non-trivial and highly depends on the state of the other nodes and links. Mapping a vnode requires an evaluation of how well it maps to the chosen pnode; the choice and evaluation of any links the vnode might have that connect to mapped vnodes (vlinks are only evaluated when both ends are mapped), possibly involving the allocation of one or more switches; the new physical homogeneity of pnode usage; and the consistency of any vclass the vnode might be in. All of these need to be evaluated, even under conditions in which the current state is invalid. For example, mapping a node may require over utilizing a link. The score still needs to be updated, and needs be updated to reflect the over-utilization (an increase in the number of violations). The mapping of a vnode and the later unmapping of a vnode will not necessarily result in opposite effects on the score (in fact, it is very rare that they do so). For between map and unmap a number of other changes have been applied, each of which depended on the fact the vnode was mapped. Unmapping the vnode needs to reflect those dependencies and modify the score and state appropriately. As an example, a vnode may be mapped, and later on one of its neighbors mapped. Mapping that neighbor in will cause the link between them to be evaluated. When the original node is unmapped the effect of that evaluation must be undone. Assign has a detailed resource availability and use model. Each pnode has a number of resources along with their values. The value reflects the cost of the resource in the case that the resource is allocated but unused. For example, a pnode may have specialized hardware. If that pnode is allocated as part of a solution but the vnode will not use that hardware, then the cost is included in the score. Vnodes have resource requests along with the cost of having that request unfulfilled. Besides a quality modification, an unfulfilled request can, at the users discretion, result in an increase in violations. This basic mechanism of features and desires allows a wide range of control over the nature of any solution. Assign has a notion of physical equivalence classes. Pnodes are grouped together in cases where the choice of either pnode will have no effect on the score. The simulated annealing then chooses among pclasses instead of pnodes, dramatically reducing the scaling properties. The idea and tracking a pnodes is still very important, as even within a pclass, pnodes may differ in the vnodes mapped to them, specifically as multiple vnodes can map to a single pnode. Thus not only must assign look at pclasses but also within, at what partially full pnodes are available. By using simulated annealing on pclasses and heuristics to choose among the members of a pclass, assign finds middle ground between nodes and equivalence classes. Assign must be able to handle partial solutions specified as input. This is important in cases where users require a specific machine for reasons outside the knowledge of assign. It also provides opportunities to strongly influence a solution. For example in a distributed testbed, a local node could be fixed causing solutions to tend to utilize nearby nodes. Without, the pnodes could very well be on the far end of a continent or beyond. Often the user will be aware of relations among their vnodes that assign does not otherwise have the knowledge to be aware of. For example, a user may put great important on the homogeneity of internal nodes vs. leaf nodes, but care little as to whether leaf and internal are similar. Vtypes allows the user to specify these relationships to assign. The challenge to assign is to deal with these vnodes that are not restricted to a single type but are requested to match in type to other vnodes. The user is allowed to specify the importance of the consistency, anywhere from negligible to invalidating any solution with inconsistency within a vtype. Even in the latter case, however, assign allows for inconsistent solutions, keeping track of the violations. Before beginning simulated annealing assign performs a number of checks and computations to improve performance and avoid pathological cases that are obvious to heuristics but not SA. ``````