aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ClientStack/LindenUDP
diff options
context:
space:
mode:
authorMic Bowman2011-04-11 09:06:28 -0700
committerMic Bowman2011-04-13 15:37:25 -0700
commit5b89c66c9704f2bd219a35f8a70ac60e751d7f49 (patch)
tree6b1f271ad395d43108070b52f619f12a386ce80a /OpenSim/Region/ClientStack/LindenUDP
parentUse common coalesced serialization code for both tests and the InventoryAcces... (diff)
downloadopensim-SC_OLD-5b89c66c9704f2bd219a35f8a70ac60e751d7f49.zip
opensim-SC_OLD-5b89c66c9704f2bd219a35f8a70ac60e751d7f49.tar.gz
opensim-SC_OLD-5b89c66c9704f2bd219a35f8a70ac60e751d7f49.tar.bz2
opensim-SC_OLD-5b89c66c9704f2bd219a35f8a70ac60e751d7f49.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')
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs6
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs96
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs2
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs300
4 files changed, 259 insertions, 145 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 76d7f79..5980669 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
28using System; 28using System;
29using System.Collections;
30using System.Collections.Generic;
31using System.Reflection;
32using log4net;
29 33
30namespace OpenSim.Region.ClientStack.LindenUDP 34namespace 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}