clockwerk-opensim – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | vero | 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 | public Int64 MaxDripRate |
||
339 | { |
||
340 | get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); } |
||
341 | protected set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); } |
||
342 | } |
||
343 | |||
344 | public bool Enabled { get; private set; } |
||
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 | Enabled = enabled; |
||
366 | |||
367 | if (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 (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 (Enabled) |
||
391 | AdjustedDripRate = AdjustedDripRate + count; |
||
392 | } |
||
393 | } |
||
394 | } |