Scheduling load with a round robin algorithm?

Question

I need to write a round robin algorithm to schedule load to n endpoints?

So if I have servers A, B and C

I wanted to make sure to round-robin through them for each request I get. How do I do this in C#?

Butts

Will it be constant load or you want even distribution of load? – Suckle

I think 'round robin' indicates there is no attempt to evenly distribute the load. – Decahedron

Answer 1

Just for the record, definition of round robin:

http://en.wikipedia.org/wiki/Round-robin_scheduling

Just use a queue. Take one off of the top, use it and put it back. This ensures that the most recent one used will always be the last one to be picked up.

Queue<Server> q = new Queue<Server>();

//get the next one up
Server s = q.DeQueue();


//Use s;


//put s back for later use.
q.Enqueue(s);

Link to the queue class:

http://msdn.microsoft.com/en-us/library/7977ey2c.aspx

Stealer

I would challenge a person who said he wanted to implement round robin to figure out if they really mean round robin. – Sacristan

It's used in server load distribution all the time. – Stealer

When using this pattern, it might be worthwhile to immediately enqueue the server before using it (or putting the enqueue in a finally block). That way, any exceptions thrown during "using" the server won't possibly result in the server being removed from the rotation entirely. – Anthrax

this should be wrapped in a class – Bankable

Wouldn't a linkedlist be better than a queue? no need to re-queue items, just restart from head :) – Materialize

Answer 2

Same idea as ebpower, but focussing on what is the next item rather than what is the index of the next item.

public class RoundRobinList<T>
{
    private readonly IList<T> _list;
    private readonly int _size;
    private int _position;

    public RoundRobinList(IList<T> list)
    {
        if (!list.Any())
            throw new NullReferenceException("list");

        _list = new List<T>(list);
        _size = _list.Count;            
    }

    public T Next()
    {
        if (_size == 1)
            return _list[0];

        Interlocked.Increment(ref _position);
        var mod = _position % _size;
        return _list[mod];
    }
}

Alkyd

pass IEnumerable<T> to constructor and record mod before Incrementing _position, and this is money. – Bankable

Interlocked.Increment will reach int.MaxValue in very high load scenarios. In that case, it handles the overflow condition and returns int.MinValue as per documentation and this code will throw an System.ArgumentOutOfRangeException while accessing the array because of the negative index. A simple check can handle it: ` ... Interlocked.Increment(ref _position); if(_position == Int32.MinValue) { Interlocked.Exchange(ref _position, 0); } ... ` – Horseweed

Alternative implementation that resets the position when the end of the list is reached: gist.github.com/randyburden/251f0514f893013d711da1b4e395aaa5 – Statistician

Answer 3

If your endpoints are accessed through a List or Array, you only need to increment an index in a circular fashion:

public class RoundRobinIndex
{
    volatile int index = 0;
    int count;

    public int Next
    {
        get
        {
            if (index == count)
            {
                index = 0;
            } 
            return index++;
        }
    }

    public RoundRobinIndex(int countArg)
    {
        count = countArg;
    }
}

Deal

Using that will cause an IndexOutOfRangeException – Lambertson

@IBootstrap - It does Not cause an IndexOutOfRangeException. Have you actually tested it? – Deal

Next can also be achieved using: (index + 1) % count; – Currey