table_crusher.py

import collections

Route = collections.namedtuple('Route', 'key mask sources targets')
RoutingEntry = collections.namedtuple('RoutingEntry',
                                      'key mask targets defaultable')
KeyMask = collections.namedtuple('KeyMask', 'key mask')


def crush_table(routes, masks):
    """Reduce the size of a routing table.

    Attempts the reduce the size of a routing table by applying a series of
    masks.  If a mask cannot be used to completely reduce an entry then it is
    discarded and the next mask tried.  The order of the table is not
    guaranteed.

    The routes are a list of tuples of ALL the routes that pass through a
    router.  The masks are intended to be specifications of which bits should
    be removed from keys and masks, e.g., 0xf to try to drop the least
    significant 8 bits.
    """
    # Invert the mask
    mask = [~m for m in masks]

    # Make all the entries into RoutingEntries
    routes = map(Route._make, routes)

    for mask in masks:
        if len(routes) > 1024:
            # Make mappings from the "masked" key and masks to sources and
            # targets.
            combinable_sources = collections.defaultdict(list)
            combinable_targets = collections.defaultdict(list)

            for r in routes:
                # Mask the key and mask for the entries
                k = r.key & mask
                m = r.mask & mask

                # Store the new source and target
                combinable_sources[KeyMask(k, m)].append(r.source)
                combinable_targets[KeyMask(k, m)].append(r.target)

            # Order the potential merges by size
            merge_preference = sorted(combinable_sources.keys(),
                                      key=lambda k: len(combinable_sources[k]))

            # Try each merge in turn, merges are only possible if the sets of
            # source (links) and target (links) are disjoint.  Stop merging if
            # there are less than 1024 entries.
            for mkv in merge_preference:
                # Get the set of sources and the set of targets which are
                # links, if they are disjoint THEN the entries may be merged.
                sources = set(combinable_sources[mkv])
                targets = set(combinable_targets[mkv])

                if sources.disjoint(targets):
                    # Routes can be merged:
                    # Remove from the list of routes all the entries that are
                    # being merged.
                    remove = [r for f in routes if (r.key == mkv.key and
                                                    r.mask == mkv.mask)]
                    for r in remove:
                        routes.remove(r)

                    # Check that we really have removed all the routes that
                    # we've merged.
                    for r in routes:
                        assert(r.key & mask != mkv.key and r.mask != mvk.mask)

                    # Create and add the new merged entry
                    merged_entry = Route(mkv.key, mkv.mask, sources, targets)
                    routes.append(merged_entry)

                    # If we're done, then don't bother with any more merges
                    if len(routes) <= 1024:
                        break

    # Convert all the merged routes into routing entries
    entries = list()
    for route in routes:
        # TODO: If there are more than one source or target in the route then
        #       create a NON-defaultable routing entry.  If there is precisely
        #       ONE source and ONE target then see if they are on opposite
        #       links.  Iff they are then add the route as defaultable,
        #       otherwise add as a NON-defaultable route.
        if len(route.sources) > 1 or len(route.targets) > 1:
            entries.append(RoutingEntry(route.key, route.mask,
                                        route.sources, route.targets, False))
        else:
            # See if the route is defaultable
            raise NotImplementedError

    return entries