Weighted Round Robin

[Jango]

Hello,

I have made this simple round robin in AutoIt:

$ServerArray[0] = 3
$ServerArray[1] = "Server1"
$ServerArray[2] = "Server2"
$ServerArray[3] = "Server3"

$Server = RoundRobin($ServerArray)


Func RoundRobin(ByRef $sArray)
    $Last = $sArray[0]
    If $Last > 1 Then
        For $i = $Last To 2 Step -1
            _ArraySwap($sArray[$i], $sArray[$i-1])
        Next
    EndIf
    Return $sArray[1]
EndFunc

And it works fine but i'm looking to implement the Weighted Round Robin (click here) . Can someone help me on this ? give me at least some clue to do that

Edited May 28, 2008 by Jango

[zorphnog]

How about something like this:

expandcollapse popup

Global $aServers[3][3], $nConnections = 0, $nCount = 0, $nCurQueuePos = -1

$aServers[0][0] = "Server1"     ;Server name
$aServers[0][1] = 4             ;Max Weight
$aServers[0][2] = 4             ;Current weight
$aServers[1][0] = "Server2"
$aServers[1][1] = 12
$aServers[1][2] = 12
$aServers[2][0] = "Server3"
$aServers[2][1] = 1
$aServers[2][2] = 1

While $nCount < 100
    $sServer = RoundRobin($aServers)
    ConsoleWrite(StringFormat("  Connection[%03d] given to %s\n", $nCount, $sServer))
    $nCount += 1
WEnd

Func FindMaxWeight($aWeights)
    Local $nMin, $nNumServers, $i
    $nNumServers = UBound($aWeights)-1
    If $nNumServers >= 0 Then
        $nMax = $aWeights[0][1]
        For $i=1 To $nNumServers
            If $aWeights[$i][1] > $nMax Then $nMax = $aWeights[$i][1]
        Next
        Return $nMax
    EndIf
    Return 0
EndFunc

Func ResetCurrentWeights(ByRef $aWeights)
    Local $nNumServers, $i
    $nNumServers = UBound($aWeights)-1
    For $i=0 To $nNumServers
        $aWeights[$i][2] = $aWeights[$i][1]
    Next
EndFunc

Func RoundRobin(ByRef $aServerQueue)
    Local $nMaxWeight, $nMaxQueue
    $nMaxQueue = UBound($aServerQueue)-1
    $nMaxWeight = FindMaxWeight($aServerQueue)
    $nConnections += 1
    Do
        $nCurQueuePos += 1
        If $nCurQueuePos > $nMaxQueue Then $nCurQueuePos = 0
    Until $aServerQueue[$nCurQueuePos][2] > 0
    $aServerQueue[$nCurQueuePos][2] -= 1
    If Mod($nConnections, $nMaxWeight) = 0 Then ResetCurrentWeights($aServerQueue)
    Return $aServerQueue[$nCurQueuePos][0]
EndFunc

[Jango]

How about something like this:

Damn you are fast, moreover this code is very clean and readable. I'm heavily testing it.

[Jango]

Is this Dynamic Weighted Round Robin ?

[zorphnog]

No its static. Basically, i tried to match what the example in the article you provided does:

It's pretty clear what happens next: for every 12 requests sent to server two, 4 will be sent to server one, and just 1 will be sent to server 3. The result is a more even, if less equal, load distribution.

So basically the algorithm is dependent on the highest weighted member. In our example, 12. Each member of our server pool has a name, maximum weight (this number does not change), and current weight. The current weight simply keeps track of how many connections that server has received in our 12 connection cycle. The algorithm uses the standard round-robin technique (whoever is next in line gets a chance to have the new connection), but if a member has already received its allotted connections for the 12 connection cycle (its current weight is zero) then the next member in line tries to receive the connection. The resulting pattern is:

Server1

Server2

Server3 <= Current weight is now 0

Server1

Server2

Server1

Server2

Server1 <= Current weight is now 0

Server2

Server2

Server2

Server2 <= End of 12 connection cycle; Reset current weights

[Jango]

I tested with the following weights

$aServers[0][0] = "A";Server name
$aServers[0][1] = 2     ;Max Weight
$aServers[0][2] = 2     ;Current weight
$aServers[1][0] = "B"
$aServers[1][1] = 4
$aServers[1][2] = 4
$aServers[2][0] = "C"
$aServers[2][1] = 8
$aServers[2][2] = 8

doing an ConsoleWrite in the RoundRobin Func and i'm not convinced by the result

Connection[000] given to A 2 1
  Connection[001] given to B 4 3
  Connection[002] given to C 8 7
  Connection[003] given to A 2 0
  Connection[004] given to B 4 2
  Connection[005] given to C 8 6
  Connection[006] given to B 4 1
  Connection[007] given to C 8 8
  Connection[008] given to A 2 1
  Connection[009] given to B 4 3
  Connection[010] given to C 8 7
  Connection[011] given to A 2 0
  Connection[012] given to B 4 2
  Connection[013] given to C 8 6
  Connection[014] given to B 4 1
  Connection[015] given to C 8 8
  Connection[016] given to A 2 1

It seems that when the Server with the lower weight reach 0, the cycle restart ? I think it should be when the server with biggest weight reach 0, the cycle should restart ?

What do you think ?

Edit here is the consolewrite:

ConsoleWrite(StringFormat("  Connection[%03d] given to %s\n", $nCount, $aServerQueue[$nCurQueuePos][0]& " " & $aServerQueue[$nCurQueuePos][1] & " " & $aServerQueue[$nCurQueuePos][2]))
    Return $aServerQueue[$nCurQueuePos][0]

Edited May 28, 2008 by Jango

[zorphnog]

The problem is with your weighting values. If you want A to have 2 connections, B to have 4 connections, and C to have 8 connections (14 total connections). Then your weights should be: A-2, B-4, C-14. Remember that the connection cycle is based on the greatest weight. Of course, you could change the algorithm so that it works the way you want it to. I was just going off of the example in the article.

[Jango]

The problem is with your weighting values. If you want A to have 2 connections, B to have 4 connections, and C to have 8 connections (14 total connections). Then your weights should be: A-2, B-4, C-14. Remember that the connection cycle is based on the greatest weight. Of course, you could change the algorithm so that it works the way you want it to. I was just going off of the example in the article.

Ok thank you for your help, it's very helpfull for me. I'm off now but i will do more test tommorow.

[zorphnog]

Here's the algorithm for the way you were talking about. This one will continue a cycle until all members have used their allotted connections.

Func RoundRobin(ByRef $aServerQueue)
    Local $nMaxWeight, $nMaxQueue, $nCycleCount = -1
    $nMaxQueue = UBound($aServerQueue)-1
    $nMaxWeight = FindMaxWeight($aServerQueue)
    $nConnections += 1
    Do
        $nCurQueuePos += 1
        $nCycleCount += 1
        If $nCurQueuePos > $nMaxQueue Then $nCurQueuePos = 0
        If $nCycleCount > $nMaxQueue Then ResetCurrentWeights($aServerQueue)
    Until $aServerQueue[$nCurQueuePos][2] > 0
    $aServerQueue[$nCurQueuePos][2] -= 1
    Return $aServerQueue[$nCurQueuePos][0]
EndFunc

[Jango]

Here's the algorithm for the way you were talking about. This one will continue a cycle until all members have used their allotted connections.

Func RoundRobin(ByRef $aServerQueue)
    Local $nMaxWeight, $nMaxQueue, $nCycleCount = -1
    $nMaxQueue = UBound($aServerQueue)-1
    $nMaxWeight = FindMaxWeight($aServerQueue)
    $nConnections += 1
    Do
        $nCurQueuePos += 1
        $nCycleCount += 1
        If $nCurQueuePos > $nMaxQueue Then $nCurQueuePos = 0
        If $nCycleCount > $nMaxQueue Then ResetCurrentWeights($aServerQueue)
    Until $aServerQueue[$nCurQueuePos][2] > 0
    $aServerQueue[$nCurQueuePos][2] -= 1
    Return $aServerQueue[$nCurQueuePos][0]
EndFunc

Thank you for bringing your skills (i think you're a professional coder is'nt it ?)