topology-manager-policy-comparison.py

import itertools
import prettytable

from prettytable import PrettyTable

affinities = [
  (0,1),
  (1,0),
  (1,1),
]

preferred = [
  True,
  False
]


class TopologyHint(object):
    def __init__(self, affinity, preferred):
        self.affinity = affinity
        self.preferred = preferred

    def __str__(self):
        return "({}, {})".format(self.affinity, self.preferred)


class TopologyHintMerger(object):
    @classmethod
    def merge(cls, *hints):
        affinity = cls._merge_affinity(*hints)
        preferred = cls._merge_preferred(*hints)
        return TopologyHint(affinity, preferred)


class BitwiseAndMerger(TopologyHintMerger):
    @staticmethod
    def _merge_affinity(*hints):
        affinities = [h.affinity for h in hints]
        merged = [1]*len(affinities[0])
        for affinity in affinities:
            merged = [m & a for m,a in zip(merged, affinity)]
        return tuple(merged)

    @staticmethod
    def _merge_preferred(*hints):
        return all([h.preferred for h in hints])


class StrictEqualsMerger(TopologyHintMerger):
    @staticmethod
    def _merge_affinity(*hints):
        affinities = [h.affinity for h in hints]
        merged = [0]*len(affinities[0])
        if all(a == affinities[0] for a in affinities):
            merged = affinities[0]
        return tuple(merged)

    @staticmethod
    def _merge_preferred(*hints):
        return all([h.preferred for h in hints])


class TopologyManagerPolicy(object):
    @staticmethod
    def run(hint_providers, hint_merger):
        best_hint = TopologyHint([0]*len(hint_providers[0][0].affinity), False)

        for permutation in itertools.product(*hint_providers):
            merged = hint_merger.merge(*permutation)

            if not best_hint.preferred  and preferred:
                best_hint = merged
                continue

            if sum(best_hint.affinity) == 0:
                best_hint = merged
                continue

            if sum(merged.affinity) == 0:
                continue

            if sum(merged.affinity) <= sum(best_hint.affinity):
                best_hint = merged
                continue

            if merged.affinity <= best_hint.affinity:
                best_hint = merged
                continue

        return best_hint


class PolicyResult(object):
    def __init__(self, hint, admit):
        self.hint = hint
        self.admit = admit


class BestEffortPolicy(TopologyManagerPolicy):
    @staticmethod
    def run(hint_providers):
        hint = super(BestEffortPolicy, BestEffortPolicy).run(hint_providers, BitwiseAndMerger)
        return PolicyResult(hint, True)


class CurrentStrictPolicy(TopologyManagerPolicy):
    @staticmethod
    def run(hint_providers):
        hint = super(CurrentStrictPolicy, CurrentStrictPolicy).run(hint_providers, BitwiseAndMerger)
        admit = sum(hint.affinity) > 0 and hint.preferred
        return PolicyResult(hint, admit)


class ProposedStrictPolicy(TopologyManagerPolicy):
    @staticmethod
    def run(hint_providers):
        hint = super(ProposedStrictPolicy, ProposedStrictPolicy).run(hint_providers, StrictEqualsMerger)
        admit = sum(hint.affinity) > 0 and hint.preferred
        return PolicyResult(hint, admit)


def generate_all_possible_hint_combinations(affinities, preferred):
    combos = []

    def iterate(affinities, preferred, hints_per_combo, current_preferred):
        combos = []

        if len(current_preferred) == hints_per_combo:
            for c in itertools.combinations(affinities, hints_per_combo):
                hints = []
                for a, p in zip(c, current_preferred):
                    hints.append(TopologyHint(a, p))
                combos += [hints]
            return combos

        for p in preferred:
            combos += iterate(affinities, preferred, hints_per_combo, current_preferred + [p])

        return combos

    for i in range(len(affinities)):
        combos += iterate(affinities, preferred, i+1, [])

    return combos


def calculate_results(policies):
    hint_combos = generate_all_possible_hint_combinations(affinities, preferred)
    hints = list(itertools.product(hint_combos, repeat=2))
    all_results = []

    for hint_providers in hints:
        results = []
        for policy in policies:
            result  = policy.run(hint_providers)
            results.append(result)

        all_results.append((hint_providers, results))

    return all_results


def print_results(labels, results):
    labels = ["Providers", "Hints"] + labels
    table = PrettyTable(labels, hrules=prettytable.ALL)
    table.align = "l"

    for i in range(len(results)):
        provider_cell = ""
        hints_cell = ""
        for j, hint_providers in enumerate(results[i][0]):
            provider_cell += "Provider {}{}".format(j, "\n"*len(hint_providers))
            provider_cell += "\n"

            for hint in hint_providers:
                hints_cell += str(hint) + "\n"
            hints_cell += "\n"

        result_cells = []
        for result in results[i][1]:
            result_cell = ""
            result_cell += "Merged Hint:\n{}\n\n".format(result.hint)
            result_cell += "Admit Pod: {}\n".format(result.admit)
            result_cells.append(result_cell)

        table.add_row([provider_cell[:-2], hints_cell[:-2]] + result_cells)

    print(table)


def main():
    labels = ["Best Effort", "Current Strict", "Proposed Strict"]
    policies = [BestEffortPolicy, CurrentStrictPolicy, ProposedStrictPolicy]

    results = calculate_results(policies)
    results = sorted(results, key=lambda r: r[1][0].hint.affinity)
    results = sorted(results, key=lambda r: r[1][0].hint.preferred, reverse=True)

    print_results(labels, results)


if __name__ == "__main__" :
    main()