CODEWITHSUNDEEP
load-balancingscheduler
Net205
Net205

Reputation: 171

How to implement weighted round robin using c#?

If I have some servers: 192.168.100.1, 192.168.100.2, 192.168.100.3, 192.168.100.4... and weights of them are: 5, 1, 2, 3

I want to implement load balancing, but how can I implement weighted round robin using C#?

Upvotes: 2

Views: 8303

Answers (2)

Jacky Wang
Jacky Wang

Reputation: 3520

Random Weighted Select algorithm

// returns the index of the chosen one, note that the index starting with 0
static int randomWeightedSelect(List<int> colls) {
    int lucky = rand.Next(1, colls.Sum());
    for (int i = 0; i < colls.Count(); ++i) {
        lucky -= colls[i];
        if (lucky <= 0)
            return i;
    }
    // should never reach here
    return -1;
}

Weighted Round Robin Algorithm https://dotnetfiddle.net/71Sft0

public class WRRScheduler
{
    // A list of node name/label -> weight
    List<Tuple<string, int>> nodes;
    int maxWeight;
    int step;

    int idx;
    int quantum;

    // for testing purpose
    public static void Main()
    {
        var colls = new List<Tuple<string, int>> {
            Tuple.Create("A", 5), Tuple.Create("B", 1),
            Tuple.Create("C", 7), Tuple.Create("D", 3)
        };
        var s = new WRRScheduler(colls);

        for (int i = 0; i < colls.Sum(e => e.Item2); ++i)
            Console.WriteLine("choose {0}", s.next());
    }

    public WRRScheduler(List<Tuple<string, int>> nodes) {
        this.nodes = nodes;

        this.maxWeight = nodes.Max(e => e.Item2);
        // use gcd as a optimization
        this.step = nodes.Select(e => e.Item2).Aggregate(gcd);

        this.idx = -1;
        this.quantum = 0;
    }

    string next() {
        while (true) {
            this.idx = (this.idx + 1) % this.nodes.Count;
            if (this.idx == 0) {
                // start a new round, decrement current quantum
                this.quantum -= this.step;
                if (this.quantum <= 0) {
                    this.quantum = this.maxWeight;
                }
            }

            // pick the node if its weight greater than current quantum
            if (this.nodes[this.idx].Item2 >= this.quantum) {
                return this.nodes[this.idx].Item1;
            }
        }
    }

    private static int gcd(int a, int b)
    {
        while (a != 0 && b != 0) {
            if (a > b)
                a %= b;
            else
                b %= a;
        }
        return a == 0 ? b : a;
    }
}

Upvotes: 1

SundayMonday
SundayMonday

Reputation: 19757

Say you have servers a, b, c, d. And you have corresponding weights 5, 1, 2, 3. You can do weighted round robin in the following way:

Random rand = new Random(seed);

void processRequest(Request r){

    // assume rand.next() returns a uniformly distributed integer >= 0
    int i = rand.next() % 11; // 11 is sum of weights

    if(i <= 4)      // process r with server a
    else if(i == 5) // process r with server b
    else if(i <= 7) // process r with server c
    else            // process r with server d
}

rand.next() % 11 returns a uniformly distributed integer in the range [0, 10] (inclusive). We process the request with server a for five of the possible values [0, 4]. We process the request with server b for only one possible value 5 and so on.

Pay special attention to the particular random method you use and the seed value.

Upvotes: 3

Related Questions