Weighted Round Robin

Recommended Posts

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 on other sites

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 on other sites

How about something like this:

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

Share on other sites

Is this Dynamic Weighted Round Robin ?

Share on other sites

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 on other sites

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 on other sites

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 on other sites

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 on other sites

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 on other sites

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

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