aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs
blob: 4ca83ff207cfba13d366fc8d4790bbebff2d0423 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
/*
 * Copyright (c) Contributors, http://opensimulator.org/
 * See CONTRIBUTORS.TXT for a full list of copyright holders.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the OpenSimulator Project nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using OpenSim.Framework;

using log4net;

namespace OpenSim.Region.ClientStack.LindenUDP
{
    /// <summary>
    /// A hierarchical token bucket for bandwidth throttling. See
    /// http://en.wikipedia.org/wiki/Token_bucket for more information
    /// </summary>
    public class TokenBucket
    {
        private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);

        public string Identifier { get; private set; }

        public int DebugLevel { get; set; }
        
        /// <summary>
        /// Number of ticks (ms) per quantum, drip rate and max burst
        /// are defined over this interval.
        /// </summary>
        protected const Int32 m_ticksPerQuantum = 1000;

        /// <summary>
        /// This is the number of quantums worth of packets that can
        /// be accommodated during a burst
        /// </summary>
        protected const Double m_quantumsPerBurst = 1.5;
                
        /// <summary>
        /// </summary>
        protected const Int32 m_minimumDripRate = 1400;
        
        /// <summary>Time of the last drip, in system ticks</summary>
        protected Int32 m_lastDrip;

        /// <summary>
        /// The number of bytes that can be sent at this moment. This is the
        /// current number of tokens in the bucket
        /// </summary>
        protected Int64 m_tokenCount;

        /// <summary>
        /// Map of children buckets and their requested maximum burst rate
        /// </summary>
        protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>();

        /// <summary>
        /// The parent bucket of this bucket, or null if this bucket has no
        /// parent. The parent bucket will limit the aggregate bandwidth of all
        /// of its children buckets
        /// </summary>
        public TokenBucket Parent { get; protected set; }

        /// <summary>
        /// Maximum burst rate in bytes per second. This is the maximum number
        /// of tokens that can accumulate in the bucket at any one time. This 
        /// also sets the total request for leaf nodes
        /// </summary>
        protected Int64 m_burstRate;
        public Int64 RequestedBurstRate
        {
            get { return m_burstRate; }
            set { m_burstRate = (value < 0 ? 0 : value); }
        }

        public Int64 BurstRate
        {
            get {
                double rate = RequestedBurstRate * BurstRateModifier();
                if (rate < m_minimumDripRate * m_quantumsPerBurst)
                    rate = m_minimumDripRate * m_quantumsPerBurst;
                
                return (Int64) rate;
            }
        }
               
        /// <summary>
        /// The requested drip rate for this particular bucket.
        /// </summary>
        /// <remarks>
        /// 0 then TotalDripRequest is used instead.
        /// Can never be above MaxDripRate.
        /// Tokens are added to the bucket at any time 
        /// <seealso cref="RemoveTokens"/> is called, at the granularity of
        /// the system tick interval (typically around 15-22ms)
        /// FIXME: It is extremely confusing to be able to set a RequestedDripRate of 0 and then receive a positive
        /// number on get if TotalDripRequest is set.  This also stops us being able to retrieve the fact that
        /// RequestedDripRate is set to 0.  Really, this should always return m_dripRate and then we can get
        /// (m_dripRate == 0 ? TotalDripRequest : m_dripRate) on some other properties.
        /// </remarks>
        public virtual Int64 RequestedDripRate
        {
            get { return (m_dripRate == 0 ? TotalDripRequest : m_dripRate); }
            set 
            {
                if (value <= 0)
                    m_dripRate = 0;
                else if (MaxDripRate > 0 && value > MaxDripRate)
                    m_dripRate = MaxDripRate;
                else
                    m_dripRate = value;

                m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);

                if (Parent != null)
                    Parent.RegisterRequest(this, m_dripRate);
            }
        }

        /// <summary>
        /// Gets the drip rate.
        /// </summary>
        /// <value>
        /// DripRate can never be above max drip rate or below min drip rate.
        /// If we are a child bucket then the drip rate return is modifed by the total load on the capacity of the
        /// parent bucket.
        /// </value>
        public virtual Int64 DripRate
        {
            get 
            {
                double rate;

                // FIXME: This doesn't properly work if we have a parent and children and a requested drip rate set
                // on ourselves which is not equal to the child drip rates.
                if (Parent == null)
                {
                    if (TotalDripRequest > 0)
                        rate = Math.Min(RequestedDripRate, TotalDripRequest);
                    else
                        rate = RequestedDripRate;
                }   
                else
                {
                    rate = (double)RequestedDripRate * Parent.DripRateModifier();
                }

                if (rate < m_minimumDripRate)
                    rate = m_minimumDripRate;
                else if (MaxDripRate > 0 && rate > MaxDripRate)
                    rate = MaxDripRate;

                return (Int64)rate;
            }
        }
        protected Int64 m_dripRate;

        // <summary>
        // The maximum rate for flow control. Drip rate can never be greater than this.
        // </summary>
        public Int64 MaxDripRate { get; set; }

        /// <summary>
        /// The current total of the requested maximum burst rates of children buckets.
        /// </summary>
        public Int64 TotalDripRequest { get; protected set; }

        /// <summary>
        /// Default constructor
        /// </summary>
        /// <param name="identifier">Identifier for this token bucket</param>
        /// <param name="parent">Parent bucket if this is a child bucket, or
        /// null if this is a root bucket</param>
        /// <param name="requestedDripRate">
        /// Requested rate that the bucket fills, in bytes per
        /// second. If zero, the bucket always remains full.
        /// </param>
        public TokenBucket(string identifier, TokenBucket parent, Int64 requestedDripRate, Int64 maxDripRate) 
        {
            Identifier = identifier;

            Parent = parent;
            RequestedDripRate = requestedDripRate;
            MaxDripRate = maxDripRate;
            m_lastDrip = Util.EnvironmentTickCount();
        }

        /// <summary>
        /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning
        /// no modification if the requested bandwidth is less than the
        /// max burst bandwidth all the way to the root of the throttle
        /// hierarchy. However, if any of the parents is over-booked, then
        /// the modifier will be less than 1.
        /// </summary>
        protected double DripRateModifier()
        {
            Int64 driprate = DripRate;
            double modifier = driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;

//            if (DebugLevel > 0)
//                m_log.DebugFormat(
//                    "[TOKEN BUCKET]: Returning drip modifier {0}/{1} = {2} from {3}", 
//                    driprate, TotalDripRequest, modifier, Identifier);

            return modifier;
        }

        /// <summary>
        /// </summary>
        protected double BurstRateModifier()
        {
            // for now... burst rate is always m_quantumsPerBurst (constant)
            // larger than drip rate so the ratio of burst requests is the
            // same as the drip ratio
            return DripRateModifier();
        }

        /// <summary>
        /// Register drip rate requested by a child of this throttle. Pass the
        /// changes up the hierarchy.
        /// </summary>
        public void RegisterRequest(TokenBucket child, Int64 request)
        {
            lock (m_children)
            {
                m_children[child] = request;

                TotalDripRequest = 0;
                foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
                    TotalDripRequest += cref.Value;
            }
            
            // Pass the new values up to the parent
            if (Parent != null)
            {
                Int64 effectiveDripRate;

                if (RequestedDripRate > 0)
                    effectiveDripRate = Math.Min(RequestedDripRate, TotalDripRequest);
                else
                    effectiveDripRate = TotalDripRequest;

                Parent.RegisterRequest(this, effectiveDripRate);
            }
        }

        /// <summary>
        /// Remove the rate requested by a child of this throttle. Pass the
        /// changes up the hierarchy.
        /// </summary>
        public void UnregisterRequest(TokenBucket child)
        {
            lock (m_children)
            {
                m_children.Remove(child);

                TotalDripRequest = 0;
                foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
                    TotalDripRequest += cref.Value;
            }

            // Pass the new values up to the parent
            if (Parent != null)
                Parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
        }
        
        /// <summary>
        /// Remove a given number of tokens from the bucket
        /// </summary>
        /// <param name="amount">Number of tokens to remove from the bucket</param>
        /// <returns>True if the requested number of tokens were removed from
        /// the bucket, otherwise false</returns>
        public bool RemoveTokens(Int64 amount)
        {
            // Deposit tokens for this interval
            Drip();

            // If we have enough tokens then remove them and return
            if (m_tokenCount - amount >= 0)
            {
                // we don't have to remove from the parent, the drip rate is already
                // reflective of the drip rate limits in the parent
                m_tokenCount -= amount;
                return true;
            }

            return false;
        }

        /// <summary>
        /// Deposit tokens into the bucket from a child bucket that did
        /// not use all of its available tokens
        /// </summary>
        protected void Deposit(Int64 count)
        {
            m_tokenCount += count;

            // Deposit the overflow in the parent bucket, this is how we share
            // unused bandwidth
            Int64 burstrate = BurstRate;
            if (m_tokenCount > burstrate)
                m_tokenCount = burstrate;
        }

        /// <summary>
        /// Add tokens to the bucket over time. The number of tokens added each
        /// call depends on the length of time that has passed since the last 
        /// call to Drip
        /// </summary>
        /// <returns>True if tokens were added to the bucket, otherwise false</returns>
        protected void Drip()
        {
            // This should never happen... means we are a leaf node and were created
            // with no drip rate...
            if (DripRate == 0)
            {
                m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0 for {0}", Identifier);
                return;
            }
            
            // Determine the interval over which we are adding tokens, never add
            // more than a single quantum of tokens
            Int32 deltaMS = Math.Min(Util.EnvironmentTickCountSubtract(m_lastDrip), m_ticksPerQuantum);
            m_lastDrip = Util.EnvironmentTickCount();

            // This can be 0 in the very unusual case that the timer wrapped
            // It can be 0 if we try add tokens at a sub-tick rate
            if (deltaMS <= 0)
                return;

            Deposit(deltaMS * DripRate / m_ticksPerQuantum);
        }
    }

    public class AdaptiveTokenBucket : TokenBucket
    {
        private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);               

        public bool AdaptiveEnabled { get; set; }

        /// <summary>
        /// Target drip rate for this bucket.
        /// </summary>
        /// <remarks>Usually set by the client.  If adaptive is enabled then throttles will increase until we reach this.</remarks>
        public Int64 TargetDripRate 
        { 
            get { return m_targetDripRate; }
            set 
            {
                m_targetDripRate = Math.Max(value, m_minimumFlow);
            }
        }
        protected Int64 m_targetDripRate;

        // <summary>
        // Adjust drip rate in response to network conditions. 
        // </summary>
        public virtual Int64 AdjustedDripRate
        {
            get { return m_dripRate; }
            set 
            {
                m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value, m_minimumFlow, TargetDripRate);
                m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);

                if (Parent != null)
                    Parent.RegisterRequest(this, m_dripRate);
            }
        }
                
        /// <summary>
        /// The minimum rate for flow control. Minimum drip rate is one
        /// packet per second. Open the throttle to 15 packets per second
        /// or about 160kbps.
        /// </summary>
        protected const Int64 m_minimumFlow = m_minimumDripRate * 15;

        public AdaptiveTokenBucket(string identifier, TokenBucket parent, Int64 requestedDripRate, Int64 maxDripRate, bool enabled) 
            : base(identifier, parent, requestedDripRate, maxDripRate)
        {
            AdaptiveEnabled = enabled;

            if (AdaptiveEnabled)
            {
//                m_log.DebugFormat("[TOKENBUCKET]: Adaptive throttle enabled");
                TargetDripRate = m_minimumFlow;
                AdjustedDripRate = m_minimumFlow;
            }
        }
                
        // <summary>
        // Reliable packets sent to the client for which we never received an ack adjust the drip rate down.
        // </summary>
        public void ExpirePackets(Int32 count)
        {
            if (AdaptiveEnabled)
            {
                if (DebugLevel > 0)
                    m_log.WarnFormat(
                        "[ADAPTIVEBUCKET] drop {0} by {1} expired packets for {2}", 
                        AdjustedDripRate, count, Identifier);

                AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count));
            }
        }

        // <summary>
        // Reliable packets acked by the client adjust the drip rate up.
        // </summary>
        public void AcknowledgePackets(Int32 count)
        {
            if (AdaptiveEnabled)
                AdjustedDripRate = AdjustedDripRate + count;
        }
    }
}