7

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#?

Nevin Mathai
  • 2,316
  • 13
  • 39
  • 54

3 Answers3

24

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

kemiller2002
  • 113,795
  • 27
  • 197
  • 251
  • I would challenge a person who said he wanted to implement round robin to figure out if they really mean round robin. – Tim Apr 21 '10 at 16:23
  • 2
    It's used in server load distribution all the time. – kemiller2002 Apr 21 '10 at 16:26
  • 4
    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. – bvoyelr Sep 16 '15 at 12:52
  • this should be wrapped in a class – JJS Jun 03 '16 at 03:05
  • Wouldn't a linkedlist be better than a queue? no need to re-queue items, just restart from head :) – VisualBean Sep 25 '17 at 13:01
7

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];
    }
}
Joseph Simpson
  • 4,054
  • 1
  • 24
  • 28
  • 1
    pass IEnumerable to constructor and record mod before Incrementing _position, and this is money. – JJS Jun 03 '16 at 03:09
  • 1
    `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](https://learn.microsoft.com/en-us/dotnet/api/system.threading.interlocked.increment?view=netframework-4.7.1) 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); } ... ` – SalvatoreGarrubba Jan 20 '20 at 16:32
  • Alternative implementation that resets the position when the end of the list is reached: https://gist.github.com/randyburden/251f0514f893013d711da1b4e395aaa5 – Randy Burden Nov 12 '21 at 03:46
2

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;
    }
}
Ed Power
  • 8,310
  • 3
  • 36
  • 42