aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs')
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs393
1 files changed, 0 insertions, 393 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
deleted file mode 100644
index 29fd1a4..0000000
--- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
+++ /dev/null
@@ -1,393 +0,0 @@
1/*
2 * Copyright (c) Contributors, http://opensimulator.org/
3 * See CONTRIBUTORS.TXT for a full list of copyright holders.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the OpenSimulator Project nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28using System;
29using System.Collections;
30using System.Collections.Generic;
31using System.Reflection;
32using OpenSim.Framework;
33
34using log4net;
35
36namespace OpenSim.Region.ClientStack.LindenUDP
37{
38 /// <summary>
39 /// A hierarchical token bucket for bandwidth throttling. See
40 /// http://en.wikipedia.org/wiki/Token_bucket for more information
41 /// </summary>
42 public class TokenBucket
43 {
44 private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
45 private static Int32 m_counter = 0;
46
47 private Int32 m_identifier;
48
49 /// <summary>
50 /// Number of ticks (ms) per quantum, drip rate and max burst
51 /// are defined over this interval.
52 /// </summary>
53 protected const Int32 m_ticksPerQuantum = 1000;
54
55 /// <summary>
56 /// This is the number of quantums worth of packets that can
57 /// be accommodated during a burst
58 /// </summary>
59 protected const Double m_quantumsPerBurst = 1.5;
60
61 /// <summary>
62 /// </summary>
63 protected const Int32 m_minimumDripRate = 1400;
64
65 /// <summary>Time of the last drip, in system ticks</summary>
66 protected Int32 m_lastDrip;
67
68 /// <summary>
69 /// The number of bytes that can be sent at this moment. This is the
70 /// current number of tokens in the bucket
71 /// </summary>
72 protected Int64 m_tokenCount;
73
74 /// <summary>
75 /// Map of children buckets and their requested maximum burst rate
76 /// </summary>
77 protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>();
78
79#region Properties
80
81 /// <summary>
82 /// The parent bucket of this bucket, or null if this bucket has no
83 /// parent. The parent bucket will limit the aggregate bandwidth of all
84 /// of its children buckets
85 /// </summary>
86 protected TokenBucket m_parent;
87 public TokenBucket Parent
88 {
89 get { return m_parent; }
90 set { m_parent = value; }
91 }
92
93 /// <summary>
94 /// Maximum burst rate in bytes per second. This is the maximum number
95 /// of tokens that can accumulate in the bucket at any one time. This
96 /// also sets the total request for leaf nodes
97 /// </summary>
98 protected Int64 m_burstRate;
99 public Int64 RequestedBurstRate
100 {
101 get { return m_burstRate; }
102 set { m_burstRate = (value < 0 ? 0 : value); }
103 }
104
105 public Int64 BurstRate
106 {
107 get {
108 double rate = RequestedBurstRate * BurstRateModifier();
109 if (rate < m_minimumDripRate * m_quantumsPerBurst)
110 rate = m_minimumDripRate * m_quantumsPerBurst;
111
112 return (Int64) rate;
113 }
114 }
115
116 /// <summary>
117 /// The speed limit of this bucket in bytes per second. This is the
118 /// number of tokens that are added to the bucket per quantum
119 /// </summary>
120 /// <remarks>Tokens are added to the bucket any time
121 /// <seealso cref="RemoveTokens"/> is called, at the granularity of
122 /// the system tick interval (typically around 15-22ms)</remarks>
123 protected Int64 m_dripRate;
124 public virtual Int64 RequestedDripRate
125 {
126 get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); }
127 set {
128 m_dripRate = (value < 0 ? 0 : value);
129 m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
130 m_totalDripRequest = m_dripRate;
131 if (m_parent != null)
132 m_parent.RegisterRequest(this,m_dripRate);
133 }
134 }
135
136 public virtual Int64 DripRate
137 {
138 get {
139 if (m_parent == null)
140 return Math.Min(RequestedDripRate,TotalDripRequest);
141
142 double rate = (double)RequestedDripRate * m_parent.DripRateModifier();
143 if (rate < m_minimumDripRate)
144 rate = m_minimumDripRate;
145
146 return (Int64)rate;
147 }
148 }
149
150 /// <summary>
151 /// The current total of the requested maximum burst rates of
152 /// this bucket's children buckets.
153 /// </summary>
154 protected Int64 m_totalDripRequest;
155 public Int64 TotalDripRequest
156 {
157 get { return m_totalDripRequest; }
158 set { m_totalDripRequest = value; }
159 }
160
161#endregion Properties
162
163#region Constructor
164
165 /// <summary>
166 /// Default constructor
167 /// </summary>
168 /// <param name="parent">Parent bucket if this is a child bucket, or
169 /// null if this is a root bucket</param>
170 /// <param name="maxBurst">Maximum size of the bucket in bytes, or
171 /// zero if this bucket has no maximum capacity</param>
172 /// <param name="dripRate">Rate that the bucket fills, in bytes per
173 /// second. If zero, the bucket always remains full</param>
174 public TokenBucket(TokenBucket parent, Int64 dripRate)
175 {
176 m_identifier = m_counter++;
177
178 Parent = parent;
179 RequestedDripRate = dripRate;
180 // TotalDripRequest = dripRate; // this will be overwritten when a child node registers
181 // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst);
182 m_lastDrip = Util.EnvironmentTickCount();
183 }
184
185#endregion Constructor
186
187 /// <summary>
188 /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning
189 /// no modification if the requested bandwidth is less than the
190 /// max burst bandwidth all the way to the root of the throttle
191 /// hierarchy. However, if any of the parents is over-booked, then
192 /// the modifier will be less than 1.
193 /// </summary>
194 protected double DripRateModifier()
195 {
196 Int64 driprate = DripRate;
197 return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;
198 }
199
200 /// <summary>
201 /// </summary>
202 protected double BurstRateModifier()
203 {
204 // for now... burst rate is always m_quantumsPerBurst (constant)
205 // larger than drip rate so the ratio of burst requests is the
206 // same as the drip ratio
207 return DripRateModifier();
208 }
209
210 /// <summary>
211 /// Register drip rate requested by a child of this throttle. Pass the
212 /// changes up the hierarchy.
213 /// </summary>
214 public void RegisterRequest(TokenBucket child, Int64 request)
215 {
216 lock (m_children)
217 {
218 m_children[child] = request;
219 // m_totalDripRequest = m_children.Values.Sum();
220
221 m_totalDripRequest = 0;
222 foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
223 m_totalDripRequest += cref.Value;
224 }
225
226 // Pass the new values up to the parent
227 if (m_parent != null)
228 m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
229 }
230
231 /// <summary>
232 /// Remove the rate requested by a child of this throttle. Pass the
233 /// changes up the hierarchy.
234 /// </summary>
235 public void UnregisterRequest(TokenBucket child)
236 {
237 lock (m_children)
238 {
239 m_children.Remove(child);
240 // m_totalDripRequest = m_children.Values.Sum();
241
242 m_totalDripRequest = 0;
243 foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
244 m_totalDripRequest += cref.Value;
245 }
246
247
248 // Pass the new values up to the parent
249 if (m_parent != null)
250 m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
251 }
252
253 /// <summary>
254 /// Remove a given number of tokens from the bucket
255 /// </summary>
256 /// <param name="amount">Number of tokens to remove from the bucket</param>
257 /// <returns>True if the requested number of tokens were removed from
258 /// the bucket, otherwise false</returns>
259 public bool RemoveTokens(Int64 amount)
260 {
261 // Deposit tokens for this interval
262 Drip();
263
264 // If we have enough tokens then remove them and return
265 if (m_tokenCount - amount >= 0)
266 {
267 // we don't have to remove from the parent, the drip rate is already
268 // reflective of the drip rate limits in the parent
269 m_tokenCount -= amount;
270 return true;
271 }
272
273 return false;
274 }
275
276 /// <summary>
277 /// Deposit tokens into the bucket from a child bucket that did
278 /// not use all of its available tokens
279 /// </summary>
280 protected void Deposit(Int64 count)
281 {
282 m_tokenCount += count;
283
284 // Deposit the overflow in the parent bucket, this is how we share
285 // unused bandwidth
286 Int64 burstrate = BurstRate;
287 if (m_tokenCount > burstrate)
288 m_tokenCount = burstrate;
289 }
290
291 /// <summary>
292 /// Add tokens to the bucket over time. The number of tokens added each
293 /// call depends on the length of time that has passed since the last
294 /// call to Drip
295 /// </summary>
296 /// <returns>True if tokens were added to the bucket, otherwise false</returns>
297 protected void Drip()
298 {
299 // This should never happen... means we are a leaf node and were created
300 // with no drip rate...
301 if (DripRate == 0)
302 {
303 m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0");
304 return;
305 }
306
307 // Determine the interval over which we are adding tokens, never add
308 // more than a single quantum of tokens
309 Int32 deltaMS = Math.Min(Util.EnvironmentTickCountSubtract(m_lastDrip), m_ticksPerQuantum);
310 m_lastDrip = Util.EnvironmentTickCount();
311
312 // This can be 0 in the very unusual case that the timer wrapped
313 // It can be 0 if we try add tokens at a sub-tick rate
314 if (deltaMS <= 0)
315 return;
316
317 Deposit(deltaMS * DripRate / m_ticksPerQuantum);
318 }
319 }
320
321 public class AdaptiveTokenBucket : TokenBucket
322 {
323 private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
324
325 /// <summary>
326 /// The minimum rate for flow control. Minimum drip rate is one
327 /// packet per second. Open the throttle to 15 packets per second
328 /// or about 160kbps.
329 /// </summary>
330 protected const Int64 m_minimumFlow = m_minimumDripRate * 15;
331
332 // <summary>
333 // The maximum rate for flow control. Drip rate can never be
334 // greater than this.
335 // </summary>
336 protected Int64 m_maxDripRate = 0;
337 protected Int64 MaxDripRate
338 {
339 get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); }
340 set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); }
341 }
342
343 private bool m_enabled = false;
344
345 // <summary>
346 //
347 // </summary>
348 public virtual Int64 AdjustedDripRate
349 {
350 get { return m_dripRate; }
351 set {
352 m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value,m_minimumFlow,MaxDripRate);
353 m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
354 if (m_parent != null)
355 m_parent.RegisterRequest(this,m_dripRate);
356 }
357 }
358
359 // <summary>
360 //
361 // </summary>
362 public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate, bool enabled) : base(parent,maxDripRate)
363 {
364 m_enabled = enabled;
365
366 if (m_enabled)
367 {
368 // m_log.DebugFormat("[TOKENBUCKET] Adaptive throttle enabled");
369 MaxDripRate = maxDripRate;
370 AdjustedDripRate = m_minimumFlow;
371 }
372 }
373
374 // <summary>
375 //
376 // </summary>
377 public void ExpirePackets(Int32 count)
378 {
379 // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
380 if (m_enabled)
381 AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count));
382 }
383
384 // <summary>
385 //
386 // </summary>
387 public void AcknowledgePackets(Int32 count)
388 {
389 if (m_enabled)
390 AdjustedDripRate = AdjustedDripRate + count;
391 }
392 }
393}
generated by cgit v1.1 at 2024-11-19 09:58:42 +0000