assign_todo.txt 4.39 KB
Newer Older
Leigh Stoller's avatar
Leigh Stoller committed
1
#
2
# Copyright (c) 2000-2004 University of Utah and the Flux Group.
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
# 
# {{{EMULAB-LICENSE
# 
# This file is part of the Emulab network testbed software.
# 
# This file is free software: you can redistribute it and/or modify it
# under the terms of the GNU Affero General Public License as published by
# the Free Software Foundation, either version 3 of the License, or (at
# your option) any later version.
# 
# This file is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public
# License for more details.
# 
# You should have received a copy of the GNU Affero General Public License
# along with this file.  If not, see <http://www.gnu.org/licenses/>.
# 
# }}}
Leigh Stoller's avatar
Leigh Stoller committed
22 23
#

24 25 26
This is the current TODO list for assign (not in order by priority):

1.   vclass improvements - from calfeld
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
  
  Two immediate improvements to vclass come to mind.  The first is,
  when choosing the type for the first assignment in a vclass use some
  sort of heuristics to find the best type.  We still want it to be
  random among all types that might give a valid solution but we
  could weight certain types over others.  For example, we weight the
  types by relative number of pnodes of that type.

  The second improvement is to occasionally induce a complete
  unmapping of every node in a given vclass at random times.  This
  should happen repletively rarely and only when either there are no
  unassigned nodes or we have a high rate of finding pnodes for our
  vnodes (both cases have special code in assign.cc).  The idea is
  that it is very hard to back out of a bad type choice with vclasses,
  so we want to every so often back out of whatever choice we made to
  allow for other choices.


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
2.   clean up assign.cc and score.cc

   Many monolithic functions, like anneal(), need to be split up, because
   they're just too big to comprehend.

   The code is in bad need of commenting.

   All the compile-time options have made a mess of things, so many that are
   obviously good things should just be on. Many that are compile-time should
   also become command-line options.

   A lot of the 'classes' are just used like structs. They really should have
   proper constructors, etc.

4.   clean up top/ptop parsers, change output format

   The parsers are currently very sensitive to syntax and ordering errors. The
   output is also difficult to parse, and is error-prone due to its lack of
   type information. At the very least, the top/ptop parsers should be
   re-written to be more robust. It may also make sense to go to a different
   format, one that uses key=value pairs. Or, even, something like XML, for
   which there are already standard graph representations and parsers.

5.   add delay node support

   Merge back in Chris's delay node support.

11.  put link mappings into stored solutions
73

74 75 76 77 78 79
   The current behavior of re-doing link assignment on a revert is becoming more
   and more questionable, since the greedy algorithm it currently uses can
   result in worse scores than the original, and possibly even violations in the
   reported solution. The solution is to keep the link mappings. But, this 
   tosses out our 'deterministic' link mapping. Need to decide which of these
   things is more important.
80

81
12.  make rejected transitions work more correctly
82

83 84 85 86 87
   Currently, rejected transitions can result in something not identical to the
   original configuration. This is because we re-do link mappings (see #11), and
   don't keep track of any nodes we might have foribly unmapped to try to open
   up a mapping for an unassignable vnode. Doesn't seem to hurt anything, so is
   low priority
88

Robert Ricci's avatar
Robert Ricci committed
89 90 91 92 93 94 95 96 97 98 99 100 101 102
15.  add a 'move an entire pnode' operation

   It can be very hard to get out of some situations in which a mapping is
   split across two switches, because doing so involes many transitions which
   may not improve the score, adn you can get into a 'tug of war' where vnodes
   get dragged back and forth without any progress being made. To combat this,
   I'm thinking of adding a new way to generate a new state: Rather than just
   move one vnode, move all vnodes on one pnode to a pnode in another pclass.
   We would do this with some random (low) probability. However, there is a
   fair amount of work to do to get this to work, since there is more
   bookkeeping necessary to be able to reject the transition.

(next free #:16)