GitLab

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.

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

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().

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.

Fix a bug with limited trivial link bandwidth. It used to be the case
that we penalized solutions that over-used the trivial bandwidth based
on the number of links that were over it. Turns out this was a
problem, if you had links of differing bandwidths, and were near the
limit. Certain orderings were possible where you would remove two
trivial links in a different order than you added them, which might
result in more (or fewer) violations being scored then when you did
them originally. The fix for this is to penalize these based on
bandwidth, which is what assign now does.

Added a '-g' flag, which does greedy link selection - assign normally
does random link selection until the very end, when it does one pass
with greedy selection. This flag makes it do this all the time. This
is useful for debugging, because it cuts out a call to random(). Turns
out, it doesn't seem to make assign much slower. I might consider
making it the default.

Better output when the selftest (-T) fails.

they mean.

many links to slip by unnoticed.

everything else goes to stdout. This will hopefully make things a bit
simpler by avoiding funny buffering issues for programs like
assign_wrapper that want to redirect assign's stdout.

violations.

sure they're within some tolerance of each other. Use this so that
cumulative float point errors don't cause us to spit out scary
looking false positive warnings.

recognizes it properly.

unretryable error, so Mike doesn't have to kill assign off 20 times!

was sooo wrong you wonder how it worked in the first place... Took
me days to find this one!

Also added a new switch, '-o', that lets assign try out solutions
that over-load a pnode. This helps a lot with topologies where the
optimal solution is a best-fit onto multiplexed pnodes.

The end result is that Mike's snake maps much better - it used to get
an essentially random mapping, but now it gets something acceptible.

a floating point number that, roughly, scales the runtime.

don't get confusing if they're redirected to different places.

After building the set of pclasses normally, we make another pass
through the vnodes. The goal to create a pclass for each individual
node. We disable the node's 'own' pclass to begin with. Then, the
_first_ time it gets a vnode mapped to it, we remove it from the
'regular' pclass it belongs to, and enable it's own pclass. Then, if
it goes empty, we put it back in its regular pclass and disable it's
own.

The point of this is to replace -p for use with multiplexed nodes.
Instead of disabling pclasses altogheter, which has serious
performance implications, we can instead be smart about which pnodes
remain equivalent (because nothing's been mapped to them), and which
are now different. The result is that on my test topoloy, the time to
get a good mapping has gone from over 3 minutes to about 6 seconds.

This feature is enabled with the -d option, and the -P option is
pretty much mandatory when using it, since it greatly exacerbates the
problem of cruft in the ptop file.

This satisfies #14 from the todo file:
14.  do dynamic pclasses

Also bumped up the minimum neighborhood size from 500 to 1000. In some
tests I was doing, this resulted in better solutions.

LAN nodes are no longer treated specially. Instead, I've introduced
the idea of 'static' types (old-style types retroactively become
'dynamic' types). While a pnode can only satisfy one dynamic type at a
time, it can always satisfy its static types (assuming it has enough
capacity left.) Static types are flagged by prepending them with a '*'
in the ptop file. So, for example, you may give switches the
'*lan:10000' type so that they can satisfy virtual LAN nodes. Of
course, other pnodes can have this type too, so that we can get
'trivial LANs'.

Actually, removing special treatment for LANs cleans up a lot of code.
However, it may have some negative impacts on solutions, since we're
not as smart about where to place LAN nodes as we used to be (they get
annealed along with everything else, and not migrated.) I haven't seen
any evidence of this yet, however.

This leaves us with a single type of special pnode, a switch.

Also added a new bit of syntax in ptop files - when '*' is given as a
the maxiumum load for a type, the node is allowed to take on an
infinite (well, actually, just a really big number of) vnodes of that
type.

ptopgen was modified to always report switches as being capable of
hosting LANs, and assign_wrapper now understands direct links to LANs,
which is what we get when the LAN is hosted directly on a switch.

Fixed a bug in scoring direct links, in which the penatly was being
added once when a direct link was mapped, but subtracted only once
when it was freed.

Added a '-T' option for doing simple self-testing. When adding a node
to the solution, assign records the score, adds the node, removes it
again, and checks to make sure that the resulting score is the same as
the original score. The usefulness of this feature in debugging
scoring problems cannot be understated...

some independant functionality off into new files, and reduce its
use of globals, which can be very confusing to follow.

I didn't get as far as I had hoped, but it's a good start.

specification of how much bandwidth can be used on the node for
trivial links. Clearly, there will be some limit to loopback
transfers, and this makes assign aware of it.

While I was in there, cleaned up and commented some of the code I was
working on.

Also fixed a bug with the type pre-check and emulated links that are
trivial_ok - we can't add these into the total for a vnode, because
they could end up being satisified with trivial links.

Add features and desires to the PER_VNODE_TT restrictions. For
desires, we can tell the user which ones can't be satisfied, but for
features, we don't even try to figure out which one(s) keep us from
mapping. From the assign_todo file, this is:
9.   add features/desires to PER_VNODE_TT restrictions

Add a new -P switch, when PER_VNODE_TT is in use. This casues it to
prune out pclasses that no vnode can map to - this can lead to _huge_
time savings, particularly since we put things like wide-area nodes
into the ptop file. I've seen a 98% reduction in time when using both
-p and -P! But, it's not the default yet, because I need to do more
testing to make sure that this isn't hurting solution quality
significantly.  todo item:
8.   prune pclasses when using PER_VNODE_TT

Standardize the exit values from assign:
On success, returns 0
On failures that are not retryable (ie. this top can never be mapped
    to this ptop), returns 2
If SA fails to find a solution (ie., we might consider retrying),
    returns 1

Fix a bug that has annoyed me for a very, very long time - if the
input files don't exist, exit instead of hanging forever!

Make the weight at which a feature/desire is considered 'hard' (ie. it
generates a violation if unsatisifed or undesired) a variable, so that
we'll be able to change it from 1.0 if we want.

Put some more messages that should appear inline in the mail to stderr
instead of stdout.

on in production!

PER_VNODE_TT handles emulated links by simply adding up the total bandwidth
consumed by a vnode, and the total bandwidth available on each pnode. Of
course, this can lead to false positives (knapsack problem), but that's okay,
because it just means we won't bail up front - we'll have to do the full
annealing pass before we decide it's unmappable.

PER_VNODE_TT now also tries to figure out why a vnode is not mappable - if
there are _no_ pclasses that match one of the restrictions, it will print out
something like:
  *** No possible mapping for nodeA
      Too many links!
  *** No possible mapping for nodeB
      Too much bandwidth on emulated links!

This completes the following two items from assign_todo.txt:

6.   fix PER_VNODE_TT and vclasses
7.   fix PER_VNODE_TT and emulated vlinks

available, and check that against the types of the vnodes in the top file. This
way, we can bail early with a comprehensible error message if, say, there are
not enough pc850s free!

This fixes the following item from the todo list:
13.  add type-count checks

using the new assign, and captures Leigh's linkdelays work.

time to debug a delayed LAN problem.

In addition to assign, assign_wrapper and ptopgen have been modified
to output the new formats used by assign.

links.

with other emulated links.  Also added a trivial link type for virtual
links between vnodes in the same pnode.

make-vclass A 0.5 pc600 pc850

in the top file.  And then have nodes of type A.  Assign will try to put
them all as either pc600 or pc850.

Still need to write all the pre-assign stuff.

pclasses.  This involved removing the heuristics, which, for the most
part, were not worth the cycles they consumed, and scaled badly.