diff options
author | Mic Bowman | 2011-04-11 09:06:28 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-11 09:06:28 -0700 |
commit | 6e9cdb9ce32807ddd1a39e72c436b8fd788768d2 (patch) | |
tree | 1f03340fcd068e108854cd72219d6ee533f4b05d /OpenSim/Region/ClientStack/LindenUDP | |
parent | Merge branch 'queuetest' of ssh://opensimulator.org/var/git/opensim into queu... (diff) | |
download | opensim-SC_OLD-6e9cdb9ce32807ddd1a39e72c436b8fd788768d2.zip opensim-SC_OLD-6e9cdb9ce32807ddd1a39e72c436b8fd788768d2.tar.gz opensim-SC_OLD-6e9cdb9ce32807ddd1a39e72c436b8fd788768d2.tar.bz2 opensim-SC_OLD-6e9cdb9ce32807ddd1a39e72c436b8fd788768d2.tar.xz |
New tokenbucket algorithm. This one provides fair sharing of the queues
when client and simulator throttles are set. This algorithm also uses
pre-defined burst rate of 150% of the sustained rate for each of the
throttles.
Removed the "state" queue. The state queue is not a Linden queue and
appeared to be used just to get kill packets sent.
Diffstat (limited to 'OpenSim/Region/ClientStack/LindenUDP')
4 files changed, 259 insertions, 145 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs index 8de31d7..934a2d5 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs | |||
@@ -1610,7 +1610,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
1610 | } | 1610 | } |
1611 | else | 1611 | else |
1612 | { | 1612 | { |
1613 | OutPacket(kill, ThrottleOutPacketType.State); | 1613 | // OutPacket(kill, ThrottleOutPacketType.State); |
1614 | OutPacket(kill, ThrottleOutPacketType.Task); | ||
1614 | } | 1615 | } |
1615 | } | 1616 | } |
1616 | 1617 | ||
@@ -2440,7 +2441,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
2440 | 2441 | ||
2441 | packet.Effect = effectBlocks; | 2442 | packet.Effect = effectBlocks; |
2442 | 2443 | ||
2443 | OutPacket(packet, ThrottleOutPacketType.State); | 2444 | // OutPacket(packet, ThrottleOutPacketType.State); |
2445 | OutPacket(packet, ThrottleOutPacketType.Task); | ||
2444 | } | 2446 | } |
2445 | 2447 | ||
2446 | public void SendAvatarProperties(UUID avatarID, string aboutText, string bornOn, Byte[] charterMember, | 2448 | public void SendAvatarProperties(UUID avatarID, string aboutText, string bornOn, Byte[] charterMember, |
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs index 9a8bfd3..5a69851 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs | |||
@@ -135,7 +135,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
135 | private int m_nextOnQueueEmpty = 1; | 135 | private int m_nextOnQueueEmpty = 1; |
136 | 136 | ||
137 | /// <summary>Throttle bucket for this agent's connection</summary> | 137 | /// <summary>Throttle bucket for this agent's connection</summary> |
138 | private readonly TokenBucket m_throttle; | 138 | private readonly TokenBucket m_throttleClient; |
139 | /// <summary>Throttle bucket for this agent's connection</summary> | ||
140 | private readonly TokenBucket m_throttleCategory; | ||
139 | /// <summary>Throttle buckets for each packet category</summary> | 141 | /// <summary>Throttle buckets for each packet category</summary> |
140 | private readonly TokenBucket[] m_throttleCategories; | 142 | private readonly TokenBucket[] m_throttleCategories; |
141 | /// <summary>Outgoing queues for throttled packets</summary> | 143 | /// <summary>Outgoing queues for throttled packets</summary> |
@@ -174,7 +176,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
174 | m_maxRTO = maxRTO; | 176 | m_maxRTO = maxRTO; |
175 | 177 | ||
176 | // Create a token bucket throttle for this client that has the scene token bucket as a parent | 178 | // Create a token bucket throttle for this client that has the scene token bucket as a parent |
177 | m_throttle = new TokenBucket(parentThrottle, rates.TotalLimit, rates.Total); | 179 | m_throttleClient = new TokenBucket(parentThrottle, rates.TotalLimit); |
180 | // Create a token bucket throttle for the total categary with the client bucket as a throttle | ||
181 | m_throttleCategory = new TokenBucket(m_throttleClient, rates.TotalLimit); | ||
178 | // Create an array of token buckets for this clients different throttle categories | 182 | // Create an array of token buckets for this clients different throttle categories |
179 | m_throttleCategories = new TokenBucket[THROTTLE_CATEGORY_COUNT]; | 183 | m_throttleCategories = new TokenBucket[THROTTLE_CATEGORY_COUNT]; |
180 | 184 | ||
@@ -185,7 +189,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
185 | // Initialize the packet outboxes, where packets sit while they are waiting for tokens | 189 | // Initialize the packet outboxes, where packets sit while they are waiting for tokens |
186 | m_packetOutboxes[i] = new OpenSim.Framework.LocklessQueue<OutgoingPacket>(); | 190 | m_packetOutboxes[i] = new OpenSim.Framework.LocklessQueue<OutgoingPacket>(); |
187 | // Initialize the token buckets that control the throttling for each category | 191 | // Initialize the token buckets that control the throttling for each category |
188 | m_throttleCategories[i] = new TokenBucket(m_throttle, rates.GetLimit(type), rates.GetRate(type)); | 192 | m_throttleCategories[i] = new TokenBucket(m_throttleCategory, rates.GetLimit(type)); |
189 | } | 193 | } |
190 | 194 | ||
191 | // Default the retransmission timeout to three seconds | 195 | // Default the retransmission timeout to three seconds |
@@ -206,6 +210,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
206 | m_packetOutboxes[i].Clear(); | 210 | m_packetOutboxes[i].Clear(); |
207 | m_nextPackets[i] = null; | 211 | m_nextPackets[i] = null; |
208 | } | 212 | } |
213 | |||
214 | // pull the throttle out of the scene throttle | ||
215 | m_throttleClient.Parent.UnregisterRequest(m_throttleClient); | ||
209 | OnPacketStats = null; | 216 | OnPacketStats = null; |
210 | OnQueueEmpty = null; | 217 | OnQueueEmpty = null; |
211 | } | 218 | } |
@@ -216,6 +223,26 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
216 | /// <returns>Information about the client connection</returns> | 223 | /// <returns>Information about the client connection</returns> |
217 | public ClientInfo GetClientInfo() | 224 | public ClientInfo GetClientInfo() |
218 | { | 225 | { |
226 | ///<mic> | ||
227 | TokenBucket tb; | ||
228 | |||
229 | tb = m_throttleClient.Parent; | ||
230 | m_log.WarnFormat("[TOKENS] {3}: Actual={0},Request={1},TotalRequest={2}",tb.DripRate,tb.RequestedDripRate,tb.TotalDripRequest,"ROOT"); | ||
231 | |||
232 | tb = m_throttleClient; | ||
233 | m_log.WarnFormat("[TOKENS] {3}: Actual={0},Request={1},TotalRequest={2}",tb.DripRate,tb.RequestedDripRate,tb.TotalDripRequest," CLIENT"); | ||
234 | |||
235 | tb = m_throttleCategory; | ||
236 | m_log.WarnFormat("[TOKENS] {3}: Actual={0},Request={1},TotalRequest={2}",tb.DripRate,tb.RequestedDripRate,tb.TotalDripRequest," CATEGORY"); | ||
237 | |||
238 | for (int i = 0; i < THROTTLE_CATEGORY_COUNT; i++) | ||
239 | { | ||
240 | tb = m_throttleCategories[i]; | ||
241 | m_log.WarnFormat("[TOKENS] {4} <{0}:{1}>: Actual={2},Requested={3}",AgentID,i,tb.DripRate,tb.RequestedDripRate," BUCKET"); | ||
242 | } | ||
243 | |||
244 | ///</mic> | ||
245 | |||
219 | // TODO: This data structure is wrong in so many ways. Locking and copying the entire lists | 246 | // TODO: This data structure is wrong in so many ways. Locking and copying the entire lists |
220 | // of pending and needed ACKs for every client every time some method wants information about | 247 | // of pending and needed ACKs for every client every time some method wants information about |
221 | // this connection is a recipe for poor performance | 248 | // this connection is a recipe for poor performance |
@@ -223,13 +250,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
223 | info.pendingAcks = new Dictionary<uint, uint>(); | 250 | info.pendingAcks = new Dictionary<uint, uint>(); |
224 | info.needAck = new Dictionary<uint, byte[]>(); | 251 | info.needAck = new Dictionary<uint, byte[]>(); |
225 | 252 | ||
226 | info.resendThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Resend].DripRate; | 253 | info.resendThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Resend].DripRate; |
227 | info.landThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Land].DripRate; | 254 | info.landThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Land].DripRate; |
228 | info.windThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Wind].DripRate; | 255 | info.windThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Wind].DripRate; |
229 | info.cloudThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Cloud].DripRate; | 256 | info.cloudThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Cloud].DripRate; |
230 | info.taskThrottle = m_throttleCategories[(int)ThrottleOutPacketType.State].DripRate + m_throttleCategories[(int)ThrottleOutPacketType.Task].DripRate; | 257 | // info.taskThrottle = m_throttleCategories[(int)ThrottleOutPacketType.State].DripRate + m_throttleCategories[(int)ThrottleOutPacketType.Task].DripRate; |
231 | info.assetThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Asset].DripRate; | 258 | info.taskThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Task].DripRate; |
232 | info.textureThrottle = m_throttleCategories[(int)ThrottleOutPacketType.Texture].DripRate; | 259 | info.assetThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Asset].DripRate; |
260 | info.textureThrottle = (int)m_throttleCategories[(int)ThrottleOutPacketType.Texture].DripRate; | ||
233 | info.totalThrottle = info.resendThrottle + info.landThrottle + info.windThrottle + info.cloudThrottle + | 261 | info.totalThrottle = info.resendThrottle + info.landThrottle + info.windThrottle + info.cloudThrottle + |
234 | info.taskThrottle + info.assetThrottle + info.textureThrottle; | 262 | info.taskThrottle + info.assetThrottle + info.textureThrottle; |
235 | 263 | ||
@@ -317,8 +345,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
317 | int texture = (int)(BitConverter.ToSingle(adjData, pos) * 0.125f); pos += 4; | 345 | int texture = (int)(BitConverter.ToSingle(adjData, pos) * 0.125f); pos += 4; |
318 | int asset = (int)(BitConverter.ToSingle(adjData, pos) * 0.125f); | 346 | int asset = (int)(BitConverter.ToSingle(adjData, pos) * 0.125f); |
319 | // State is a subcategory of task that we allocate a percentage to | 347 | // State is a subcategory of task that we allocate a percentage to |
320 | int state = (int)((float)task * STATE_TASK_PERCENTAGE); | 348 | int state = 0; |
321 | task -= state; | 349 | // int state = (int)((float)task * STATE_TASK_PERCENTAGE); |
350 | // task -= state; | ||
322 | 351 | ||
323 | // Make sure none of the throttles are set below our packet MTU, | 352 | // Make sure none of the throttles are set below our packet MTU, |
324 | // otherwise a throttle could become permanently clogged | 353 | // otherwise a throttle could become permanently clogged |
@@ -339,40 +368,32 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
339 | // Update the token buckets with new throttle values | 368 | // Update the token buckets with new throttle values |
340 | TokenBucket bucket; | 369 | TokenBucket bucket; |
341 | 370 | ||
342 | bucket = m_throttle; | 371 | bucket = m_throttleCategory; |
343 | bucket.MaxBurst = total; | 372 | bucket.RequestedDripRate = total; |
344 | 373 | ||
345 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Resend]; | 374 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Resend]; |
346 | bucket.DripRate = resend; | 375 | bucket.RequestedDripRate = resend; |
347 | bucket.MaxBurst = resend; | ||
348 | 376 | ||
349 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Land]; | 377 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Land]; |
350 | bucket.DripRate = land; | 378 | bucket.RequestedDripRate = land; |
351 | bucket.MaxBurst = land; | ||
352 | 379 | ||
353 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Wind]; | 380 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Wind]; |
354 | bucket.DripRate = wind; | 381 | bucket.RequestedDripRate = wind; |
355 | bucket.MaxBurst = wind; | ||
356 | 382 | ||
357 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Cloud]; | 383 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Cloud]; |
358 | bucket.DripRate = cloud; | 384 | bucket.RequestedDripRate = cloud; |
359 | bucket.MaxBurst = cloud; | ||
360 | 385 | ||
361 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Asset]; | 386 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Asset]; |
362 | bucket.DripRate = asset; | 387 | bucket.RequestedDripRate = asset; |
363 | bucket.MaxBurst = asset; | ||
364 | 388 | ||
365 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Task]; | 389 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Task]; |
366 | bucket.DripRate = task + state; | 390 | bucket.RequestedDripRate = task; |
367 | bucket.MaxBurst = task + state; | ||
368 | 391 | ||
369 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.State]; | 392 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.State]; |
370 | bucket.DripRate = state; | 393 | bucket.RequestedDripRate = state; |
371 | bucket.MaxBurst = state; | ||
372 | 394 | ||
373 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Texture]; | 395 | bucket = m_throttleCategories[(int)ThrottleOutPacketType.Texture]; |
374 | bucket.DripRate = texture; | 396 | bucket.RequestedDripRate = texture; |
375 | bucket.MaxBurst = texture; | ||
376 | 397 | ||
377 | // Reset the packed throttles cached data | 398 | // Reset the packed throttles cached data |
378 | m_packedThrottles = null; | 399 | m_packedThrottles = null; |
@@ -387,14 +408,13 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
387 | data = new byte[7 * 4]; | 408 | data = new byte[7 * 4]; |
388 | int i = 0; | 409 | int i = 0; |
389 | 410 | ||
390 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Resend].DripRate), 0, data, i, 4); i += 4; | 411 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Resend].RequestedDripRate), 0, data, i, 4); i += 4; |
391 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Land].DripRate), 0, data, i, 4); i += 4; | 412 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Land].RequestedDripRate), 0, data, i, 4); i += 4; |
392 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Wind].DripRate), 0, data, i, 4); i += 4; | 413 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Wind].RequestedDripRate), 0, data, i, 4); i += 4; |
393 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Cloud].DripRate), 0, data, i, 4); i += 4; | 414 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Cloud].RequestedDripRate), 0, data, i, 4); i += 4; |
394 | Buffer.BlockCopy(Utils.FloatToBytes((float)(m_throttleCategories[(int)ThrottleOutPacketType.Task].DripRate) + | 415 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Task].RequestedDripRate), 0, data, i, 4); i += 4; |
395 | m_throttleCategories[(int)ThrottleOutPacketType.State].DripRate), 0, data, i, 4); i += 4; | 416 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Texture].RequestedDripRate), 0, data, i, 4); i += 4; |
396 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Texture].DripRate), 0, data, i, 4); i += 4; | 417 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Asset].RequestedDripRate), 0, data, i, 4); i += 4; |
397 | Buffer.BlockCopy(Utils.FloatToBytes((float)m_throttleCategories[(int)ThrottleOutPacketType.Asset].DripRate), 0, data, i, 4); i += 4; | ||
398 | 418 | ||
399 | m_packedThrottles = data; | 419 | m_packedThrottles = data; |
400 | } | 420 | } |
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs b/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs index 583214c..d08b25f 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs | |||
@@ -228,7 +228,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
228 | } | 228 | } |
229 | #endregion BinaryStats | 229 | #endregion BinaryStats |
230 | 230 | ||
231 | m_throttle = new TokenBucket(null, sceneThrottleBps, sceneThrottleBps); | 231 | m_throttle = new TokenBucket(null, sceneThrottleBps); |
232 | ThrottleRates = new ThrottleRates(configSource); | 232 | ThrottleRates = new ThrottleRates(configSource); |
233 | } | 233 | } |
234 | 234 | ||
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs index 0a8331f..e4d59ff 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs | |||
@@ -26,6 +26,10 @@ | |||
26 | */ | 26 | */ |
27 | 27 | ||
28 | using System; | 28 | using System; |
29 | using System.Collections; | ||
30 | using System.Collections.Generic; | ||
31 | using System.Reflection; | ||
32 | using log4net; | ||
29 | 33 | ||
30 | namespace OpenSim.Region.ClientStack.LindenUDP | 34 | namespace OpenSim.Region.ClientStack.LindenUDP |
31 | { | 35 | { |
@@ -35,89 +39,126 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
35 | /// </summary> | 39 | /// </summary> |
36 | public class TokenBucket | 40 | public class TokenBucket |
37 | { | 41 | { |
38 | /// <summary>Parent bucket to this bucket, or null if this is a root | 42 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); |
39 | /// bucket</summary> | 43 | private static Int32 m_counter = 0; |
40 | TokenBucket parent; | 44 | |
41 | /// <summary>Size of the bucket in bytes. If zero, the bucket has | 45 | private Int32 m_identifier; |
42 | /// infinite capacity</summary> | 46 | |
43 | int maxBurst; | 47 | /// <summary> |
44 | /// <summary>Rate that the bucket fills, in bytes per millisecond. If | 48 | /// Number of ticks (ms) per quantum, drip rate and max burst |
45 | /// zero, the bucket always remains full</summary> | 49 | /// are defined over this interval. |
46 | int tokensPerMS; | 50 | /// </summary> |
47 | /// <summary>Number of tokens currently in the bucket</summary> | 51 | private const Int32 m_ticksPerQuantum = 1000; |
48 | int content; | 52 | |
53 | /// <summary> | ||
54 | /// This is the number of quantums worth of packets that can | ||
55 | /// be accommodated during a burst | ||
56 | /// </summary> | ||
57 | private const Double m_quantumsPerBurst = 1.5; | ||
58 | |||
59 | /// <summary> | ||
60 | /// </summary> | ||
61 | private const Int32 m_minimumDripRate = 1400; | ||
62 | |||
49 | /// <summary>Time of the last drip, in system ticks</summary> | 63 | /// <summary>Time of the last drip, in system ticks</summary> |
50 | int lastDrip; | 64 | private Int32 m_lastDrip; |
65 | |||
66 | /// <summary> | ||
67 | /// The number of bytes that can be sent at this moment. This is the | ||
68 | /// current number of tokens in the bucket | ||
69 | /// </summary> | ||
70 | private Int64 m_tokenCount; | ||
51 | 71 | ||
52 | #region Properties | 72 | /// <summary> |
73 | /// Map of children buckets and their requested maximum burst rate | ||
74 | /// </summary> | ||
75 | private Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>(); | ||
76 | |||
77 | #region Properties | ||
53 | 78 | ||
54 | /// <summary> | 79 | /// <summary> |
55 | /// The parent bucket of this bucket, or null if this bucket has no | 80 | /// The parent bucket of this bucket, or null if this bucket has no |
56 | /// parent. The parent bucket will limit the aggregate bandwidth of all | 81 | /// parent. The parent bucket will limit the aggregate bandwidth of all |
57 | /// of its children buckets | 82 | /// of its children buckets |
58 | /// </summary> | 83 | /// </summary> |
84 | private TokenBucket m_parent; | ||
59 | public TokenBucket Parent | 85 | public TokenBucket Parent |
60 | { | 86 | { |
61 | get { return parent; } | 87 | get { return m_parent; } |
88 | set { m_parent = value; } | ||
62 | } | 89 | } |
63 | 90 | ||
64 | /// <summary> | 91 | /// <summary> |
65 | /// Maximum burst rate in bytes per second. This is the maximum number | 92 | /// Maximum burst rate in bytes per second. This is the maximum number |
66 | /// of tokens that can accumulate in the bucket at any one time | 93 | /// of tokens that can accumulate in the bucket at any one time. This |
94 | /// also sets the total request for leaf nodes | ||
67 | /// </summary> | 95 | /// </summary> |
68 | public int MaxBurst | 96 | private Int64 m_burstRate; |
97 | public Int64 RequestedBurstRate | ||
69 | { | 98 | { |
70 | get { return maxBurst; } | 99 | get { return m_burstRate; } |
71 | set { maxBurst = (value >= 0 ? value : 0); } | 100 | set { m_burstRate = (value < 0 ? 0 : value); } |
72 | } | 101 | } |
73 | 102 | ||
103 | public Int64 BurstRate | ||
104 | { | ||
105 | get { | ||
106 | double rate = RequestedBurstRate * BurstRateModifier(); | ||
107 | if (rate < m_minimumDripRate * m_quantumsPerBurst) | ||
108 | rate = m_minimumDripRate * m_quantumsPerBurst; | ||
109 | |||
110 | return (Int64) rate; | ||
111 | } | ||
112 | } | ||
113 | |||
74 | /// <summary> | 114 | /// <summary> |
75 | /// The speed limit of this bucket in bytes per second. This is the | 115 | /// The speed limit of this bucket in bytes per second. This is the |
76 | /// number of tokens that are added to the bucket per second | 116 | /// number of tokens that are added to the bucket per quantum |
77 | /// </summary> | 117 | /// </summary> |
78 | /// <remarks>Tokens are added to the bucket any time | 118 | /// <remarks>Tokens are added to the bucket any time |
79 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of | 119 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of |
80 | /// the system tick interval (typically around 15-22ms)</remarks> | 120 | /// the system tick interval (typically around 15-22ms)</remarks> |
81 | public int DripRate | 121 | private Int64 m_dripRate; |
122 | public Int64 RequestedDripRate | ||
82 | { | 123 | { |
83 | get { return tokensPerMS * 1000; } | 124 | get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); } |
84 | set | 125 | set { |
85 | { | 126 | m_dripRate = (value < 0 ? 0 : value); |
86 | if (value == 0) | 127 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); |
87 | tokensPerMS = 0; | 128 | m_totalDripRequest = m_dripRate; |
88 | else | 129 | if (m_parent != null) |
89 | { | 130 | m_parent.RegisterRequest(this,m_dripRate); |
90 | int bpms = (int)((float)value / 1000.0f); | ||
91 | |||
92 | if (bpms <= 0) | ||
93 | tokensPerMS = 1; // 1 byte/ms is the minimum granularity | ||
94 | else | ||
95 | tokensPerMS = bpms; | ||
96 | } | ||
97 | } | 131 | } |
98 | } | 132 | } |
99 | 133 | ||
100 | /// <summary> | 134 | public Int64 DripRate |
101 | /// The speed limit of this bucket in bytes per millisecond | ||
102 | /// </summary> | ||
103 | public int DripPerMS | ||
104 | { | 135 | { |
105 | get { return tokensPerMS; } | 136 | get { |
137 | if (m_parent == null) | ||
138 | return Math.Min(RequestedDripRate,TotalDripRequest); | ||
139 | |||
140 | double rate = (double)RequestedDripRate * m_parent.DripRateModifier(); | ||
141 | if (rate < m_minimumDripRate) | ||
142 | rate = m_minimumDripRate; | ||
143 | |||
144 | return (Int64)rate; | ||
145 | } | ||
106 | } | 146 | } |
107 | 147 | ||
108 | /// <summary> | 148 | /// <summary> |
109 | /// The number of bytes that can be sent at this moment. This is the | 149 | /// The current total of the requested maximum burst rates of |
110 | /// current number of tokens in the bucket | 150 | /// this bucket's children buckets. |
111 | /// <remarks>If this bucket has a parent bucket that does not have | ||
112 | /// enough tokens for a request, <seealso cref="RemoveTokens"/> will | ||
113 | /// return false regardless of the content of this bucket</remarks> | ||
114 | /// </summary> | 151 | /// </summary> |
115 | public int Content | 152 | private Int64 m_totalDripRequest; |
116 | { | 153 | public Int64 TotalDripRequest |
117 | get { return content; } | 154 | { |
118 | } | 155 | get { return m_totalDripRequest; } |
156 | set { m_totalDripRequest = value; } | ||
157 | } | ||
158 | |||
159 | #endregion Properties | ||
119 | 160 | ||
120 | #endregion Properties | 161 | #region Constructor |
121 | 162 | ||
122 | /// <summary> | 163 | /// <summary> |
123 | /// Default constructor | 164 | /// Default constructor |
@@ -128,56 +169,115 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
128 | /// zero if this bucket has no maximum capacity</param> | 169 | /// zero if this bucket has no maximum capacity</param> |
129 | /// <param name="dripRate">Rate that the bucket fills, in bytes per | 170 | /// <param name="dripRate">Rate that the bucket fills, in bytes per |
130 | /// second. If zero, the bucket always remains full</param> | 171 | /// second. If zero, the bucket always remains full</param> |
131 | public TokenBucket(TokenBucket parent, int maxBurst, int dripRate) | 172 | public TokenBucket(TokenBucket parent, Int64 dripRate) |
132 | { | 173 | { |
133 | this.parent = parent; | 174 | m_identifier = m_counter++; |
134 | MaxBurst = maxBurst; | 175 | |
135 | DripRate = dripRate; | 176 | Parent = parent; |
136 | lastDrip = Environment.TickCount & Int32.MaxValue; | 177 | RequestedDripRate = dripRate; |
178 | // TotalDripRequest = dripRate; // this will be overwritten when a child node registers | ||
179 | // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst); | ||
180 | m_lastDrip = Environment.TickCount & Int32.MaxValue; | ||
137 | } | 181 | } |
138 | 182 | ||
183 | #endregion Constructor | ||
184 | |||
139 | /// <summary> | 185 | /// <summary> |
140 | /// Remove a given number of tokens from the bucket | 186 | /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning |
187 | /// no modification if the requested bandwidth is less than the | ||
188 | /// max burst bandwidth all the way to the root of the throttle | ||
189 | /// hierarchy. However, if any of the parents is over-booked, then | ||
190 | /// the modifier will be less than 1. | ||
141 | /// </summary> | 191 | /// </summary> |
142 | /// <param name="amount">Number of tokens to remove from the bucket</param> | 192 | private double DripRateModifier() |
143 | /// <returns>True if the requested number of tokens were removed from | 193 | { |
144 | /// the bucket, otherwise false</returns> | 194 | Int64 driprate = DripRate; |
145 | public bool RemoveTokens(int amount) | 195 | return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest; |
196 | } | ||
197 | |||
198 | /// <summary> | ||
199 | /// </summary> | ||
200 | private double BurstRateModifier() | ||
201 | { | ||
202 | // for now... burst rate is always m_quantumsPerBurst (constant) | ||
203 | // larger than drip rate so the ratio of burst requests is the | ||
204 | // same as the drip ratio | ||
205 | return DripRateModifier(); | ||
206 | } | ||
207 | |||
208 | /// <summary> | ||
209 | /// Register drip rate requested by a child of this throttle. Pass the | ||
210 | /// changes up the hierarchy. | ||
211 | /// </summary> | ||
212 | public void RegisterRequest(TokenBucket child, Int64 request) | ||
146 | { | 213 | { |
147 | bool dummy; | 214 | m_children[child] = request; |
148 | return RemoveTokens(amount, out dummy); | 215 | // m_totalDripRequest = m_children.Values.Sum(); |
216 | |||
217 | m_totalDripRequest = 0; | ||
218 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | ||
219 | m_totalDripRequest += cref.Value; | ||
220 | |||
221 | // Pass the new values up to the parent | ||
222 | if (m_parent != null) | ||
223 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | ||
149 | } | 224 | } |
150 | 225 | ||
151 | /// <summary> | 226 | /// <summary> |
227 | /// Remove the rate requested by a child of this throttle. Pass the | ||
228 | /// changes up the hierarchy. | ||
229 | /// </summary> | ||
230 | public void UnregisterRequest(TokenBucket child) | ||
231 | { | ||
232 | m_children.Remove(child); | ||
233 | // m_totalDripRequest = m_children.Values.Sum(); | ||
234 | |||
235 | m_totalDripRequest = 0; | ||
236 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | ||
237 | m_totalDripRequest += cref.Value; | ||
238 | |||
239 | // Pass the new values up to the parent | ||
240 | if (m_parent != null) | ||
241 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | ||
242 | } | ||
243 | |||
244 | /// <summary> | ||
152 | /// Remove a given number of tokens from the bucket | 245 | /// Remove a given number of tokens from the bucket |
153 | /// </summary> | 246 | /// </summary> |
154 | /// <param name="amount">Number of tokens to remove from the bucket</param> | 247 | /// <param name="amount">Number of tokens to remove from the bucket</param> |
155 | /// <param name="dripSucceeded">True if tokens were added to the bucket | ||
156 | /// during this call, otherwise false</param> | ||
157 | /// <returns>True if the requested number of tokens were removed from | 248 | /// <returns>True if the requested number of tokens were removed from |
158 | /// the bucket, otherwise false</returns> | 249 | /// the bucket, otherwise false</returns> |
159 | public bool RemoveTokens(int amount, out bool dripSucceeded) | 250 | public bool RemoveTokens(Int64 amount) |
160 | { | 251 | { |
161 | if (maxBurst == 0) | 252 | // Deposit tokens for this interval |
253 | Drip(); | ||
254 | |||
255 | // If we have enough tokens then remove them and return | ||
256 | if (m_tokenCount - amount >= 0) | ||
162 | { | 257 | { |
163 | dripSucceeded = true; | 258 | if (m_parent == null || m_parent.RemoveTokens(amount)) |
164 | return true; | 259 | { |
260 | m_tokenCount -= amount; | ||
261 | return true; | ||
262 | } | ||
165 | } | 263 | } |
166 | 264 | ||
167 | dripSucceeded = Drip(); | 265 | return false; |
266 | } | ||
168 | 267 | ||
169 | if (content - amount >= 0) | 268 | /// <summary> |
170 | { | 269 | /// Deposit tokens into the bucket from a child bucket that did |
171 | if (parent != null && !parent.RemoveTokens(amount)) | 270 | /// not use all of its available tokens |
172 | return false; | 271 | /// </summary> |
272 | private void Deposit(Int64 count) | ||
273 | { | ||
274 | m_tokenCount += count; | ||
173 | 275 | ||
174 | content -= amount; | 276 | // Deposit the overflow in the parent bucket, this is how we share |
175 | return true; | 277 | // unused bandwidth |
176 | } | 278 | Int64 burstrate = BurstRate; |
177 | else | 279 | if (m_tokenCount > burstrate) |
178 | { | 280 | m_tokenCount = burstrate; |
179 | return false; | ||
180 | } | ||
181 | } | 281 | } |
182 | 282 | ||
183 | /// <summary> | 283 | /// <summary> |
@@ -186,37 +286,29 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
186 | /// call to Drip | 286 | /// call to Drip |
187 | /// </summary> | 287 | /// </summary> |
188 | /// <returns>True if tokens were added to the bucket, otherwise false</returns> | 288 | /// <returns>True if tokens were added to the bucket, otherwise false</returns> |
189 | public bool Drip() | 289 | private void Drip() |
190 | { | 290 | { |
191 | if (tokensPerMS == 0) | 291 | // This should never happen... means we are a leaf node and were created |
292 | // with no drip rate... | ||
293 | if (DripRate == 0) | ||
192 | { | 294 | { |
193 | content = maxBurst; | 295 | m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0"); |
194 | return true; | 296 | return; |
195 | } | 297 | } |
196 | else | 298 | |
197 | { | 299 | // Determine the interval over which we are adding tokens, never add |
198 | int now = Environment.TickCount & Int32.MaxValue; | 300 | // more than a single quantum of tokens |
199 | int deltaMS = now - lastDrip; | 301 | Int32 now = Environment.TickCount & Int32.MaxValue; |
200 | 302 | Int32 deltaMS = Math.Min(now - m_lastDrip, m_ticksPerQuantum); | |
201 | if (deltaMS <= 0) | ||
202 | { | ||
203 | if (deltaMS < 0) | ||
204 | lastDrip = now; | ||
205 | return false; | ||
206 | } | ||
207 | 303 | ||
208 | int dripAmount = deltaMS * tokensPerMS; | 304 | m_lastDrip = now; |
209 | 305 | ||
210 | content = Math.Min(content + dripAmount, maxBurst); | 306 | // This can be 0 in the very unusual case that the timer wrapped |
211 | lastDrip = now; | 307 | // It can be 0 if we try add tokens at a sub-tick rate |
308 | if (deltaMS <= 0) | ||
309 | return; | ||
212 | 310 | ||
213 | if (dripAmount < 0 || content < 0) | 311 | Deposit(deltaMS * DripRate / m_ticksPerQuantum); |
214 | // sim has been idle for too long, integer has overflown | ||
215 | // previous calculation is meaningless, let's put it at correct max | ||
216 | content = maxBurst; | ||
217 | |||
218 | return true; | ||
219 | } | ||
220 | } | 312 | } |
221 | } | 313 | } |
222 | } | 314 | } |