Check out the new USENIX Web site. next up previous
Next: Implementation Up: Bundling: a hybrid approach Previous: Conceptual framework

Bundling algorithm

Once the input profiles have been used to create the graph, the bundling algorithm uses the graph to put the files into bundles. The algorithm works as follows:

  1. Initially, each file is put in a separate bundle.
  2. Edges whose weight is less than the minimum edge weight are discarded.
  3.   The edges are sorted according to the edge comparator.
  4. The edges are processed one at a time, in the order determined in step 3. For each edge, if the files connected by the edge are not already in the same bundle, and if the number of files in the resulting bundle would not exceed the maximum bundle size, and if the resulting bundle would not exceed the maximum bundle spread, then the bundles containing the files are combined into a single bundle.
  5. After all the edges have been processed, the files within each resulting bundle are sorted according to the bundle sort comparator.

Once the contents of the bundles have been determined, they are combined and compressed cumulatively. We evaluated both zlib (at the highest compression level) and Pack as compressed formats for the bundles.



David Hovemeyer
Tue Feb 27 18:43:09 EST 2001