OVS algorithm for weighted group selection is not correct

[araghava]

The code in group_best_live_bucket does the following: it assigns each bucket a score based on the hash of the flow and the bucket ID (should be uniformly distributed), and then simply chooses the highest score.

This doesn't properly take into account the relative weights of buckets. For example, imagine you had buckets of weights [5, 100, 100] and a random variable uniformly distributed from 0-1. The likelihood that the bucket with weight 5 even has an opportunity of winning is the likelihood that both 100s do not win, which is 0.05 * 0.05 = 0.0025 (the chance of both 100s scoring less than a 5).

However, we expect the likelihood of actually choosing the bucket with weight 5 to be 0.024 (5 / (100 + 100 + 5) = ~0.024), which is almost 10x higher.

[blp]

OK.

What's the fix?

[araghava]

Fix would be to replace the function w/ this, which IIUC applies the relative weighting properly. I can take a look at submitting a PR when I have some time.

static struct ofputil_bucket *
group_best_live_bucket(const struct xlate_ctx *ctx,
                                         const struct group_dpif *group,
                                         uint32_t basis)
{
    uint32_t total_weight = 0;
    const struct list *buckets;
    group_dpif_get_buckets(group, &buckets);
    struct ofputil_bucket *bucket;
    LIST_FOR_EACH (bucket, list_node, buckets) {
        if (!bucket_is_alive(ctx, bucket, 0)) {
            continue;
        }
        total_weight += bucket->weight;
    }

    /* Generate integer uniformly distributed within [0, total_weight - 1] using the flowkey hash. */
    uint32_t rand = total_weight * ldexp(basis, -32);

    /* Iterate through each bucket, keeping track of the accumulated weight so
     * far. If the accumulated weight exceeds the number generated, pick that
     * bucket. This gives each bucket its fair share relative to its weight. */
    uint32_t accum = 0;
    struct ofputil_bucket *bucket;
    LIST_FOR_EACH (bucket, list_node, buckets) {
        if (!bucket_is_alive(ctx, bucket, 0)) {
            continue;
        }

        accum += bucket->weight;
        if (accum > rand) {
            return bucket;
        }
    }

    return NULL;
}