1. 12 Feb, 2016 1 commit
  2. 04 Apr, 2014 1 commit
  3. 24 Sep, 2012 1 commit
    • Eric Eide's avatar
      Replace license symbols with {{{ }}}-enclosed license blocks. · 6df609a9
      Eric Eide authored
      This commit is intended to makes the license status of Emulab and
      ProtoGENI source files more clear.  It replaces license symbols like
      "EMULAB-COPYRIGHT" and "GENIPUBLIC-COPYRIGHT" with {{{ }}}-delimited
      blocks that contain actual license statements.
      
      This change was driven by the fact that today, most people acquire and
      track Emulab and ProtoGENI sources via git.
      
      Before the Emulab source code was kept in git, the Flux Research Group
      at the University of Utah would roll distributions by making tar
      files.  As part of that process, the Flux Group would replace the
      license symbols in the source files with actual license statements.
      
      When the Flux Group moved to git, people outside of the group started
      to see the source files with the "unexpanded" symbols.  This meant
      that people acquired source files without actual license statements in
      them.  All the relevant files had Utah *copyright* statements in them,
      but without the expanded *license* statements, the licensing status of
      the source files was unclear.
      
      This commit is intended to clear up that confusion.
      
      Most Utah-copyrighted files in the Emulab source tree are distributed
      under the terms of the Affero GNU General Public License, version 3
      (AGPLv3).
      
      Most Utah-copyrighted files related to ProtoGENI are distributed under
      the terms of the GENI Public License, which is a BSD-like open-source
      license.
      
      Some Utah-copyrighted files in the Emulab source tree are distributed
      under the terms of the GNU Lesser General Public License, version 2.1
      (LGPL).
      6df609a9
  4. 19 Jul, 2011 2 commits
    • Robert Ricci's avatar
      Handle new property_list.hpp location in boost · 1c333acd
      Robert Ricci authored
      Have I mentioned that I hate it when library developers move their
      headers around? Change the location of the property_list.hpp header
      to a macro and add a new -DNEWER_BOOT define that swtiches this to
      the newer location.
      
      Not automatically detected yet; should be checked in configure.
      (cherry picked from commit 2403b264)
      1c333acd
    • Robert Ricci's avatar
      Handle new property_list.hpp location in boost · 2403b264
      Robert Ricci authored
      Have I mentioned that I hate it when library developers move their
      headers around? Change the location of the property_list.hpp header
      to a macro and add a new -DNEWER_BOOT define that swtiches this to
      the newer location.
      
      Not automatically detected yet; should be checked in configure.
      2403b264
  5. 10 Nov, 2010 1 commit
  6. 13 Oct, 2010 1 commit
    • Robert Ricci's avatar
      Fifth attempt at fixing fixed interfaces in assign · a773d833
      Robert Ricci authored
      Think I got it this time (yeah, I've said that four times before).
      It requires some extra bookkeeping; we were recording source and
      dest interface names in tb_plink, but not source and dest node
      names. With this new information, find_best_link() now has sole
      responsibility for figuring out if the vlink and plink go in the
      same direction, and the callers of find_best_link() are now
      responsible for knowing which direction they are traversing the
      vlink in (and thus whether they should tell find_best_link() to
      check the source or dest of the vlink.)
      a773d833
  7. 08 Oct, 2009 1 commit
  8. 17 Jul, 2009 1 commit
  9. 15 Jun, 2009 1 commit
  10. 20 May, 2009 1 commit
  11. 17 Dec, 2007 1 commit
    • Robert Ricci's avatar
      Fix for fixed interfaces: move the code that filters interfaces whose · 43333bb7
      Robert Ricci authored
      name's don't match from resolve_link() to find_best_link() - the latter
      returns only one link of each type, so it's too late to find the right
      interface by the time we get back out to resolve_link(). Also fixed
      a built-in assmption about the 'direction' that physical links go in.
      The old code (explicity) assumed that links to from node to switch - now
      we flip around our comparison if the directions of the links do not
      match.
      
      This was a bugger, even though it didn't involve much code, since the
      'flipping' involves a 'parity' issue - it's really easy to mess up the
      parity in several places and get it to work under *some* circumstances.
      
      As a side effect, added some more information to the plink strucutre.
      This turned out to not be necessary for the solution I finally came
      up with - it was part of an earlier, abandoned one. But, it's probably
      good information to have around in the future.
      43333bb7
  12. 01 Mar, 2007 1 commit
  13. 30 Mar, 2006 1 commit
    • Robert Ricci's avatar
      prune_unusable_pclasses() now goes through the ptypes of the classes · f8b6a77c
      Robert Ricci authored
      it removes, and decrements the available slot count for every node
      in a pclass that is being removed.
      
      After running prune_unusable_pclasses(), we now do another type check,
      minus the pruned pclasses.
      
      This should enable us to detect more free node problems up front -
      let's say there are 8 vnodes that all want 2 interfaces, but only
      a couple pnodes that have 2: most have 1. The second type check will
      now catch this, since all of the 1-interface pnodes have been pruned.
      f8b6a77c
  14. 25 Jan, 2006 1 commit
    • Robert Ricci's avatar
      Merge in changes from the assign-devel branch. This includes: · ed3cbc13
      Robert Ricci authored
      Ripping out crope and replacing (almost) all cropes, char*s and
      strings with fstring
      
      Beginnings of XML parser support (not built by default yet).
      
      Significant re-org of code.
      
      Should now compile with the latest gcc.
      
      Putting link information in stored solutions.
      
      Support for fixing interfaces.
      ed3cbc13
  15. 29 Aug, 2005 1 commit
  16. 19 Jan, 2005 1 commit
    • Robert Ricci's avatar
      Add support for the set-type-limit command in the ptop file. · 8eaec842
      Robert Ricci authored
      It looks like this:
      set-type-limit <type> <count>
      
      This can be placed anywhere in the ptop file.  It limits the number of
      physical nodes of a given type that an experimenter is allowed to use.
      
      For example, we may limit a user to 10 PCs, or 5 pc850s. In the latter
      case, if the experimenter had simply asked for 10 generic PCs, then we
      will try to find them some mapping of nodes that uses types of PCs
      other than pc850s.
      
      Added a precheck to tell the user up-front if they asked for more
      nodes than they are allowed to use of a given type.
      8eaec842
  17. 11 Aug, 2004 1 commit
  18. 03 Jun, 2004 1 commit
    • Robert Ricci's avatar
      'port' assign to compile under gcc 3 (specifically tested with 3.3.1). · f05e1008
      Robert Ricci authored
      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.
      f05e1008
  19. 26 Apr, 2004 1 commit
    • Robert Ricci's avatar
      Some big changes to assign, and some related changes to assign_wrapper · 238dce73
      Robert Ricci authored
      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.
      238dce73
  20. 12 Jan, 2004 1 commit
    • Robert Ricci's avatar
      Several changes, mostly targeted at jail and simulation-type · 3a345f8e
      Robert Ricci authored
      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().
      3a345f8e
  21. 15 Sep, 2003 1 commit
    • Robert Ricci's avatar
      Some fixes aimed at vnodes: · 7848e357
      Robert Ricci authored
      Don't allow intraswitch links to vnodes on switches - they'll get
      scored as direct links. Since LANs are now directly on switches, there
      were situations where we could have scored the same link as either
      direct or intraswitch, which results in two different scores. This can
      cause those 'contact calfeld' warnings, and might have caused some
      strange scoring fluxuations as assign ran.
      
      When picking a link to a switch, for emulated links, pick the least
      loaded link, not the one with the fewest users. This helps in situations
      where the link bandwidths are heterogenous.
      7848e357
  22. 11 Sep, 2003 2 commits
  23. 08 Sep, 2003 1 commit
  24. 04 Sep, 2003 1 commit
  25. 01 Jul, 2003 1 commit
    • Robert Ricci's avatar
      Give assign the ability to make dynamic pclasses. Here's how it works: · fbcd6752
      Robert Ricci authored
      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.
      fbcd6752
  26. 26 Jun, 2003 2 commits
    • Robert Ricci's avatar
      Change around some data structures to make certain functions faster - · 55566879
      Robert Ricci authored
      turns out that getting iterators to the STL hash_* data structures is
      really slow, so for some that won't be very big, use the non-hash
      version.
      
      Buys something like a 30% speedup for large topologies.
      55566879
    • Robert Ricci's avatar
      Major changes to the way assign handles LAN nodes. · 83cfa8ec
      Robert Ricci authored
      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...
      83cfa8ec
  27. 20 Jun, 2003 1 commit
  28. 28 May, 2003 1 commit
    • Robert Ricci's avatar
      Added the TRIVIAL_LINK_BW option, which allows, in the ptop file, · 5c67bf1f
      Robert Ricci authored
      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.
      5c67bf1f
  29. 16 Apr, 2003 1 commit
    • Robert Ricci's avatar
      Fix PER_VNODE_TT to work with vclasses and emulated links. Now, we can turn it · 690ec56d
      Robert Ricci authored
      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
      690ec56d
  30. 10 Mar, 2003 1 commit
  31. 05 Mar, 2003 1 commit
  32. 10 Feb, 2003 1 commit
  33. 04 Feb, 2003 1 commit
  34. 03 Jul, 2002 1 commit
  35. 29 May, 2002 1 commit
  36. 02 Jan, 2002 1 commit
    • Christopher Alfeld's avatar
      This check-in consists of 7 modifications to assign. · 1eb1e1d9
      Christopher Alfeld authored
      1. Equivalence Classes
      
      Defined an equivalence relation on the physical nodes and applied it
      to the physical topology to get the resulting quotient topology (abuse
      of terminology).  So instead of searching among all possible physical
      nodes to make a map, assign only searches among all possible
      equivalence classes of nodes.  This tremendously reduces the search
      space.  At the time of this writing it reduces the physical topology
      from 252 nodes to 13 nodes.  The equivalence classes are generated
      automatically from the ptop file.
      
      2. Scoring based on equivalence classes.
      
      Each equivalence class used comes with a significant cost.  This
      strongly encourages assign to use equivalence machines when possible.
      The result is that an experiment that does not otherwise specify will
      almost definitely get machines of the same type.  If this needs to be
      reduced in the future it is the SCORE_PCLASS constant.
      
      3. Heuristics
      
      Added a bunch of heuristics for choosing which equivalence class to
      use.  This was less successful than I hoped.  A good solution is now
      found in record time but it still continues searching.  When OPTIMAL
      is turned on these heuristics help a lot.  When off they make little
      difference.  I may turn this into a compile time option in the future
      since the heuristics do take non-trivial CPU cycles.
      
      4. Fixed the very-very-big-and-evil disconnected-switches bug.
      
      Assign wasn't cleaning up after itself in certain cases.  Disconnected
      graphs are now merely a minor, easily ignored, bump rather than the
      towering cliffs they use to be.
      
      5. Fixed the not-yet-noticed not-enough-nodes bug.
      
      Found a bug that probably has never come up before because we have
      checks that avoid those circumstances.
      
      6. Modified constants.
      
      I was tired of waiting so long for results so, I lowered CYCLES and
      reduced the constant for naccepts (Mac, you probably want to add that
      inconspicuous number to your configurable constants; look for
      "naccepts =").  The results is roughly a speedup of 2.  It works great
      currently but we may want to change these numbers up again if we get
      problems with features and desires.
      
      7. General clean up.
      
      Associated with the other changes was a lot of restructuring and some
      cleanup.  Specifically to the assign loop and scoring code.
      1eb1e1d9
  37. 20 Jul, 2001 1 commit
    • Christopher Alfeld's avatar
      This is a nearly complete rewrite of the assign interswitch code. Assign · 8078740b
      Christopher Alfeld authored
      now precomputers the shortest path between all pairs of switches and uses
      this to computer paths through the switch fabric.  In the process of
      writing this I also removed the limitations of two switch hops.  Packets
      can now travel through any number of switches to reach their destination.
      Of course, the longer the path the more it costs so assign will prefer
      shorter paths.
      
      Also did various other tweaks in the process.  We now use strings almost
      everywhere instead of char*'s and the makefile is cleaner.
      8078740b