opensim – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 eva 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  
28 using System;
29 using System.Collections;
30 using System.Collections.Generic;
31 using System.Reflection;
32 using OpenSim.Framework;
33  
34 using log4net;
35  
36 namespace 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 m_counter++;
178  
179 Parent = parent;
180 RequestedDripRate = dripRate;
181 // TotalDripRequest = dripRate; // this will be overwritten when a child node registers
182 // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst);
183 m_lastDrip = Util.EnvironmentTickCount();
184 }
185  
186 #endregion Constructor
187  
188 /// <summary>
189 /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning
190 /// no modification if the requested bandwidth is less than the
191 /// max burst bandwidth all the way to the root of the throttle
192 /// hierarchy. However, if any of the parents is over-booked, then
193 /// the modifier will be less than 1.
194 /// </summary>
195 protected double DripRateModifier()
196 {
197 Int64 driprate = DripRate;
198 return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;
199 }
200  
201 /// <summary>
202 /// </summary>
203 protected double BurstRateModifier()
204 {
205 // for now... burst rate is always m_quantumsPerBurst (constant)
206 // larger than drip rate so the ratio of burst requests is the
207 // same as the drip ratio
208 return DripRateModifier();
209 }
210  
211 /// <summary>
212 /// Register drip rate requested by a child of this throttle. Pass the
213 /// changes up the hierarchy.
214 /// </summary>
215 public void RegisterRequest(TokenBucket child, Int64 request)
216 {
217 lock (m_children)
218 {
219 m_children[child] = request;
220 // m_totalDripRequest = m_children.Values.Sum();
221  
222 m_totalDripRequest = 0;
223 foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
224 m_totalDripRequest += cref.Value;
225 }
226  
227 // Pass the new values up to the parent
228 if (m_parent != null)
229 m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
230 }
231  
232 /// <summary>
233 /// Remove the rate requested by a child of this throttle. Pass the
234 /// changes up the hierarchy.
235 /// </summary>
236 public void UnregisterRequest(TokenBucket child)
237 {
238 lock (m_children)
239 {
240 m_children.Remove(child);
241 // m_totalDripRequest = m_children.Values.Sum();
242  
243 m_totalDripRequest = 0;
244 foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
245 m_totalDripRequest += cref.Value;
246 }
247  
248  
249 // Pass the new values up to the parent
250 if (m_parent != null)
251 m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
252 }
253  
254 /// <summary>
255 /// Remove a given number of tokens from the bucket
256 /// </summary>
257 /// <param name="amount">Number of tokens to remove from the bucket</param>
258 /// <returns>True if the requested number of tokens were removed from
259 /// the bucket, otherwise false</returns>
260 public bool RemoveTokens(Int64 amount)
261 {
262 // Deposit tokens for this interval
263 Drip();
264  
265 // If we have enough tokens then remove them and return
266 if (m_tokenCount - amount >= 0)
267 {
268 // we don't have to remove from the parent, the drip rate is already
269 // reflective of the drip rate limits in the parent
270 m_tokenCount -= amount;
271 return true;
272 }
273  
274 return false;
275 }
276  
277 /// <summary>
278 /// Deposit tokens into the bucket from a child bucket that did
279 /// not use all of its available tokens
280 /// </summary>
281 protected void Deposit(Int64 count)
282 {
283 m_tokenCount += count;
284  
285 // Deposit the overflow in the parent bucket, this is how we share
286 // unused bandwidth
287 Int64 burstrate = BurstRate;
288 if (m_tokenCount > burstrate)
289 m_tokenCount = burstrate;
290 }
291  
292 /// <summary>
293 /// Add tokens to the bucket over time. The number of tokens added each
294 /// call depends on the length of time that has passed since the last
295 /// call to Drip
296 /// </summary>
297 /// <returns>True if tokens were added to the bucket, otherwise false</returns>
298 protected void Drip()
299 {
300 // This should never happen... means we are a leaf node and were created
301 // with no drip rate...
302 if (DripRate == 0)
303 {
304 m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0");
305 return;
306 }
307  
308 // Determine the interval over which we are adding tokens, never add
309 // more than a single quantum of tokens
310 Int32 deltaMS = Math.Min(Util.EnvironmentTickCountSubtract(m_lastDrip), m_ticksPerQuantum);
311 m_lastDrip = Util.EnvironmentTickCount();
312  
313 // This can be 0 in the very unusual case that the timer wrapped
314 // It can be 0 if we try add tokens at a sub-tick rate
315 if (deltaMS <= 0)
316 return;
317  
318 Deposit(deltaMS * DripRate / m_ticksPerQuantum);
319 }
320 }
321  
322 public class AdaptiveTokenBucket : TokenBucket
323 {
324 // private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
325  
326 /// <summary>
327 /// The minimum rate for flow control. Minimum drip rate is one
328 /// packet per second. Open the throttle to 15 packets per second
329 /// or about 160kbps.
330 /// </summary>
331 protected const Int64 m_minimumFlow = m_minimumDripRate * 15;
332  
333 // <summary>
334 // The maximum rate for flow control. Drip rate can never be
335 // greater than this.
336 // </summary>
337 protected Int64 m_maxDripRate = 0;
338 protected Int64 MaxDripRate
339 {
340 get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); }
341 set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); }
342 }
343  
344 private bool m_enabled = false;
345  
346 // <summary>
347 //
348 // </summary>
349 public virtual Int64 AdjustedDripRate
350 {
351 get { return m_dripRate; }
352 set {
353 m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value,m_minimumFlow,MaxDripRate);
354 m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
355 if (m_parent != null)
356 m_parent.RegisterRequest(this,m_dripRate);
357 }
358 }
359  
360 // <summary>
361 //
362 // </summary>
363 public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate, bool enabled) : base(parent,maxDripRate)
364 {
365 m_enabled = enabled;
366  
367 if (m_enabled)
368 {
369 // m_log.DebugFormat("[TOKENBUCKET] Adaptive throttle enabled");
370 MaxDripRate = maxDripRate;
371 AdjustedDripRate = m_minimumFlow;
372 }
373 }
374  
375 // <summary>
376 //
377 // </summary>
378 public void ExpirePackets(Int32 count)
379 {
380 // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
381 if (m_enabled)
382 AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count));
383 }
384  
385 // <summary>
386 //
387 // </summary>
388 public void AcknowledgePackets(Int32 count)
389 {
390 if (m_enabled)
391 AdjustedDripRate = AdjustedDripRate + count;
392 }
393 }
394 }