GitLab

borken the code that helps assign figure out which desire was not
matched.

Also remove some old dead code while I'm in here.

errors in the ptop file immediately fatal - we were somehow getting
into a state where the istream for the file was returning !eof, but
reading data from it got only empty strings.

branch.

zero bandwidth weren't getting printed out.

disambiguate from boost's random() function. But, for some reason,
with 3.x, random() doesn't live in the std:: namespace. Macro-ize it.

a physical link with enough bandwidth for the virtual link. This fixes
some problems with physical nodes that have multiple links of
different speeds.

graphviz support seems to be broken in at least some versions of
boost with some versions of gcc .

This mostly required messing with the STL #includes.

Still builds under gcc 2.95, and won't be built with 3.3 by default
until I've spent more time testing it.

One reason for doing this is that gcc 3.3 seems to generate faster
code from templated functions. Tests so far show that the
gcc3-compiled binary shaves 15-30% off of assign's runtime.

The other reason for doing this is forward-looking. When we end up
getting boss running on FreeBSD 5 or a recent Linux distro, the
compiler is likely to be from the gcc 3 branch.

under-counted.

work on regular, (as opposed to trivial) links too.

the temperature gets below zero, or becomes NaN (which can happen if
the solution stabilizes during melting.)

in some (okay, many) cases. Not sure why, though.

epsilon termination (and ALLOW_NEGATIVE_EPSILON), it used to be the case that
we wrapped the termination condition in a fabs(), and compared that to epsilon.
The termination condition is basically a measure of how 'stable' of a score
we're at. What this meant was that we used to keep going until we reached a
space where the solution was going neither up nor down too much. All this is
relative to the difference between initial socre and the best score - so, if
those are close (ie. it's an easy problem), we could end up thrashing a whole
lot. With the new behavior, if we ever hit a spot in which solutions start
getting worse, we'll stop.

Also, fix the GNUPLOT_OUTPUT code, which I used to debut this.

and ptopgen.

Add link typing to assign. Each virtual link is given a single type.
Each physical link is given one or more types. A virtual link will
only be mapped to a physical link which can satisfy its type. In both
the top and ptop files, the link types are now mandatory, and they
fall at the end of the mandatory link arguments.

This differers from the 'regular' type system in two ways. First, a
plink is not constrained to filling only one type at a time. If we are
using emulated links, a plink could satisfy, say, an 'ethernet' link
and an 'fxp' link at the same time. This seems to more naturally match
the way we'll use link types.  Second, there are no counts assoicated
with link types, as there are for node types. ie. a link is not an
'ethernet:1' link, it's an 'ethernet' link. Presumably, when
multiplexing virtual links onto a physical one, it's bandwidth that's
the factor that limits the multiplexing.

The link type is now taken into account when constructing pclasses,
and in the mapping precheck.

As a side-effect of these changes, the silly 'count' argument on the
end of link lines in the ptop file, which was used for the fake LAN
nodes, is no longer supported.

The implementation could be a bit more efficient, but that would mean
tossing more of the stuff we do with boost's graph library. I think
this should happen, but today is not the day.

Modify assign_wrapper and ptopgen to spit out top and ptop files in
the new format.

Changed the constant LINK_UKNOWN to LINK_UNMAPPED - the new name more
accurately reflects the way this constant is used.

Add a new '-n' flag that tells assign not to do annealing, just exit
after the type precheck.

Clarify the usage message for the -c flag.

Removed some dead code for dealing with LAN nodes.

internal errors.

(which changes how we treat violations) is not working as well as we'd
hope on some topologies.

that point, I switched the meaning of the last parameter to fd_score,
but forgot to change one place it gets called.

The result was that if there were desires that caused violations,
they would not be removed properly by remove_node() .

that gave us the error.

to accept new solutions, so that we don't give violtions any special
treatment.

This can greatly reduce 'thrasing' at low scores, allowing assign to
converge on a solution much faster. For example, in the 1000-node
topology used for the virtualization paper, assign's runtime dropped
from nearly two hours to just over half an hour, with no degredation
in scores found.

You can get the old accept behavior by enabling the
SPECIAL_VIOLATION_TREATMENT #define, which is on right now (hence, we
are not using this change yet.)

Here are the pertinent comments from the code:

#ifdef SPECIAL_VIOLATION_TREATMENT
         /*
          * In this ifdef, we always accept new solutions that have fewer
          * violations than the old solution, and when we're trying to
          * determine whether or not to accept a new solution with a higher
          * score, we don't take violations into the account.
          *
          * The problem with this shows up at low temperatures. What can often
          * happen is that we accept a solution with worse violations but a
          * better (or similar) score. Then, if we were to try, say the first
          * solution (or a score-equivalent one) again, we'd accept it again.
          *
          * What this leads to is 'thrashing', where we have a whole lot of
          * variation of scores over time, but are not making any real
          * progress. This prevents the cooling schedule from converging for
          * much, much longer than it should really take.
          */
#else // no SPECIAL_VIOLATION_TREATMENT
         /*
          * In this branch of the ifdef, we give violations no special
          * treatment when it comes to accepting new solution - we just add
          * them into the score. This makes assign behave in a more 'classic'
          * simulated annealing manner.
          *
          * One consequence, though, is that we have to be more careful with
          * scores. We do not want to be able to get into a situation where
          * adding a violation results in a _lower_ score than a solution with
          * fewer violations.
          */

in find_best_link(), don't try plinks that already have a non-emulated
link on them, when we're doing an emulated link.

local features/desires - turns out, we are using them in a manner
similar to types, so can save ourselves from looking at a lot of
bad solutions by being careful about going too far over on local
features.

Do some scoring, not just violations, for stateful features and
desires - this does a better job of nudging assign towards good
solutions.

The type each pnode is being used as.

The remaining capacity for all 'local' features.

more than one vnode; not much point if a one-to-one mapping is all we
can do.

precheck - even though their weight is > 1, they do not necessariliy
cause violations if undesired.

combined with non-multiplexed nodes.

Also clear up the sense of the 'is_fixed' parameter to add_node() -
it was being handled correctly, but was confusing because it was non-
intuitive.

topologies.

First, added a new 'summary' of the solution, when the '-u' option is
given. It's a view of things from the physical side - prints out how
many vnodes were mapped to each pnode, as well as how much bandwidth
(trivial and non-trivial) was used on each node. For 'normal' nodes,
we also print out all links used and how much bandwidth was used on
each of them. For switches, we print only inter-switch links. This is
amazingly helpful in getting an intuitive feel for how well assign is
doing.

Added a SIGINFO handler for the impatient (like me) to see things such
as the current temperature, and current and best scores, while assign
is running.

Fixed a bug in which emulated links could get over-subscribed, as well
as a few other misc. bugfixes.

Changed the way assign goes through the list of a node's pclasses in
random order - there were problems with the old way in which you could
end up with a situation in which some pnodes were chosen with a much
higher probability than others. Now, rather than treating the list as
a ring and starting at a random place, we make a randomly-ordered list
of the pclasseses, and go through it from start to finish.

Did some work on dynamic pclasses so that we adjust the estimate of
the neighborhood size to account for disabled pclasses (ie. pnodes
that have nothing mapped to them yet.)

Changed the way that find_link_to_switch() decides on the best link to
use - the old method was doing very poorly at bin-packing emulated
links into plinks. I now use a simple first-fit algorithm. This made a
pretty big difference. I may try some other fast bin-packing
approximation algorithm, but my main fear is that all of the good ones
(such as the 'sort from largest to smallest, then do first-fit'
algorithm) may require re-mapping other links. This might be slow,
and/or it might make it difficult, if not impossible, to keep
add_node() and remove_node() symmetric.

Combinded direct_link() and find_link_to_switch() into
find_best_link(), since they really do the same thing.

Standardized on std::random() to get random numbers - previosuly, some
calls were using std::rand().

The big one: I added a find_pnode_connected() function that finds a
random pnode that one of the vnode's neighbors in the virtual graph is
assigned to. Then, with a random probability (given with the -c option
on the command line), we try that function to find a pnode first (if
it fails, we still call find_pnode() ). Of course, this is only really
applicable when you have a reasonable degree of vnode-to-pnode
multiplexing. In the test case I'm using, this managed to get 3x as
much bandwidth into trivial links as just using find_pnode().

again.

One of the fixes changes the way in which we iterate through pclasses
in find_pnode(). We used to treat the vector like a ring buffer, and
start (randomly) someplace in the middle. This turns out to give some
bad statistical properties when doing dynamic pclasses, since long
chains of disabled pclasses will cause some pclasses to be selected
more often. My old hack of just hopping around randomly in the
disabled-pclass case was bad, because it's hard to tell when you've
actually tried all the pclasses - so, we were getting false negatives
where it was looking like there was no place available where we could
map a vnode, which turned out to have worse effects than I had
thought.

So, now, we make a list of all the indices and randomize the order,
then just iterate through that list.

We also now count the number of pclasses that are enabled at every
temperature step, and adjust the neighborhood size to remove them.
This makes dynamic pclasses quite a bit faster - it cuts the time
by 30% - 50% for my test case.

Cleaned up find_pnode() by removing some #ifdef's that we don't use,
and probably will never want to again - this makes the function almost
readable!

In the top file, you can provide a 'node-hint', which is similar to a
'fix-node' in that it specifies a starting mapping for the virtual
node. Unlike a fixed node, however, assign is allowed to move hinted
nodes around all it wants.

Add a '-t' option to assign that allows you to give a starting
temperature, instead of going through the usual melting process.

Together, these may be helpful with the pre-pass we're planning on
incorporating into assign. During that pass, assign will be working
on a coarsened version of the virtual graph, so there may be some
places where decisions are made poorly due to the reduced information.
After one run has been done with the coarsened version, we can run
assign again with the full version of the graph, but with 'node-hints'
that start virtual nodes where the first run decided. This will allow
assign to fine-tune the results of the first mapping.

Of course, we don't want this second run to take too long, so we'll
want to start it with a low initial temperature (so that it basically
just does hill-climbing), and probably use a fractional '-H' argument
to prevent it from spending too long on large topologies.

'slot'. In the top file, you can how give' the virtual node's type as
type:count - sim:5, for example. If you give no count, it defaults to
one.

The idea here is to allow a pre-pass to assign to 'coarsen' the
virtual graph. This pre-pass could, for example, combine several
virtual or simulated nodes into one so that assign has a simpler
virtual graph to work with.

effect a single node, but are different from 'class' fds in that they
are stateful - ie. the socre you get depends on all other vnodes
currently mapped to the pnodes. These are identified by prefixing
them with a '?'. ('*' for global, mnemoic 'matches all'; '?' for
local, mnemonic 'matches one')

The currently implemented local fd is the additive one, or '?+'. We
add the desire weight for all vnodes on the pnode together, and if
this number is greater than the pnode's weight for the feature, a
violation is flagged.

The idea here is that we can give a pnode a feature like: ?+memory:256
and vnodes desires like ?+memory:16 or ?+memory:64 to pack vnodes
onto pnodes in a manner that appropriately reflects their resource
usage.

features to be lumped togther in one pclass. We were checking to make
sure that the second node passed to pclass_equiv() had all the
features of the first, but not that the first has all the features of
the second.

the compiler on cash happy.

connect a vnode to itself):

Move up the point at which we consider a vnode to be assigned - we
want to do this before we look for link resolutions, or the 'other
end' of a loopback link appears to be unassigned, which is not true.

Add a mecahism to watch out for scoring lookpback links twice. The
edge iterator for an undirected graph sees each vlink twice (there
are two 'out' edges from the vnode). So, we have to avoid scoring it
the second time.

Note that we still only allow loopback links if they are 'trivial_ok'.