Jump to content
Sign in to follow this  
Jango

Weighted Round Robin

Recommended Posts

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 by Jango

Share this post


Link to post
Share on other sites
zorphnog

How about something like this:

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

Share this post


Link to post
Share on other sites
Jango

How about something like this:

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

Share this post


Link to post
Share on other sites
Jango

Is this Dynamic Weighted Round Robin ?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 by Jango

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 ?)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.