aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs
blob: 0f71222d6115fe1063f3d4957d4e40a52fada23f (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
/*
 * 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);

        private static Int32 m_counter = 0;
        
//        private Int32 m_identifier;      
  
        protected const float m_timeScale = 1e-3f;

        /// <summary>
        /// This is the number of m_minimumDripRate bytes 
        /// allowed in a burst
        /// roughtly, with this settings, the maximum time system will take
        /// to recheck a bucket in ms
        /// 
        /// </summary>
        protected const float m_quantumsPerBurst = 5;
                
        /// <summary>
        /// </summary>
        protected const float m_minimumDripRate = 1500;
        
        /// <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 float m_tokenCount;

        /// <summary>
        /// Map of children buckets and their requested maximum burst rate
        /// </summary>

        protected Dictionary<TokenBucket, float> m_children = new Dictionary<TokenBucket, float>();
        
#region Properties

        /// <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>
        protected TokenBucket m_parent;
        public TokenBucket Parent
        {
            get { return m_parent; }
            set { m_parent = value; }
        }
        /// <summary>
        /// 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 float m_burst;
//not in use
        public float MaxDripRate { get; set; }

        public float RequestedBurst
        {
            get { return m_burst; }
            set {
                float rate = (value < 0 ? 0 : value);
                if (rate < 1.5f * m_minimumDripRate)
                    rate = 1.5f * m_minimumDripRate;
                else if (rate > m_minimumDripRate * m_quantumsPerBurst)
                    rate = m_minimumDripRate * m_quantumsPerBurst;

                m_burst = rate;
                }
        }

        public float Burst
        {
            get {
                float rate = RequestedBurst * BurstModifier();
                if (rate < m_minimumDripRate)
                    rate = m_minimumDripRate;
                return (float)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)</remarks>
        protected float m_dripRate;

        public virtual float RequestedDripRate
        {
            get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); }
            set {
                m_dripRate = (value < 0 ? 0 : value);
                m_totalDripRequest = m_dripRate;

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

       public virtual float DripRate
        {
            get {
                float rate = Math.Min(RequestedDripRate,TotalDripRequest);
                if (m_parent == null)
                    return rate;

                rate *= m_parent.DripRateModifier();
                if (rate < m_minimumDripRate)
                    rate = m_minimumDripRate;

                return (float)rate;
            }
        }

        /// <summary>
        /// The current total of the requested maximum burst rates of children buckets.
        /// </summary>
        protected float m_totalDripRequest;
        public float TotalDripRequest 
            {
                get { return m_totalDripRequest; }
                set { m_totalDripRequest = value; }
            }
        
#endregion Properties

#region Constructor


        /// <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="maxBurst">Maximum size of the bucket in bytes, or
        /// zero if this bucket has no maximum capacity</param>
        /// <param name="dripRate">Rate that the bucket fills, in bytes per
        /// second. If zero, the bucket always remains full</param>
        public TokenBucket(TokenBucket parent, float dripRate, float MaxBurst) 
        {
            m_counter++;

            Parent = parent;
            RequestedDripRate = dripRate;
            RequestedBurst = MaxBurst;
            // TotalDripRequest = dripRate; // this will be overwritten when a child node registers
            // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst);
            m_lastDrip = Util.EnvironmentTickCount() + 100000;
        }

#endregion Constructor

        /// <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 float DripRateModifier()
        {
            float driprate = DripRate;
            return driprate >= TotalDripRequest ? 1.0f : driprate / TotalDripRequest;
        }

        /// <summary>
        /// </summary>
        protected float BurstModifier()
        {
            // 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, float request)
        {
            lock (m_children)
            {
                m_children[child] = request;

                m_totalDripRequest = 0;
                foreach (KeyValuePair<TokenBucket, float> cref in m_children)
                    m_totalDripRequest += cref.Value;
            }
            
            // Pass the new values up to the parent
            if (m_parent != null)
                m_parent.RegisterRequest(this, Math.Min(RequestedDripRate, TotalDripRequest));
        }

        /// <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);

                m_totalDripRequest = 0;
                foreach (KeyValuePair<TokenBucket, float> cref in m_children)
                    m_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(int 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;
        }

        public bool CheckTokens(int amount)
        {
            return  (m_tokenCount - amount >= 0);
        }

        public int GetCatBytesCanSend(int timeMS)
        {
//            return (int)(m_tokenCount + timeMS * m_dripRate * 1e-3);
            return (int)(timeMS * DripRate * 1e-3);
        }

        /// <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}", m_counter);
                return;
            }
            
            Int32 now = Util.EnvironmentTickCount();
            Int32 deltaMS = now - m_lastDrip;
            m_lastDrip = now;

            if (deltaMS <= 0)
                return;

            m_tokenCount += deltaMS * DripRate * m_timeScale;

            float burst = Burst;
            if (m_tokenCount > burst)
                m_tokenCount = burst;
        }
    }

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

        public bool AdaptiveEnabled { get; set; }

        /// <summary>
        /// The minimum rate for flow control. Minimum drip rate is one
        /// packet per second. 
        /// </summary>

        protected const float m_minimumFlow = 50000;

        // <summary>
        // The maximum rate for flow control. Drip rate can never be
        // greater than this.
        // </summary>

        protected float m_maxDripRate = 0;
        public float MaxDripRate
        {
            get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); }
            set
            {
                m_maxDripRate = (value == 0 ? m_totalDripRequest : Math.Max(value, m_minimumFlow));
            }
        }

        private bool m_enabled = false;

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

                if (m_parent != null)
                    m_parent.RegisterRequest(this, m_dripRate);
            }
        }
                
   
        // <summary>
        // 
        // </summary>
        public AdaptiveTokenBucket(TokenBucket parent, float maxDripRate, float maxBurst, bool enabled)
            : base(parent, maxDripRate, maxBurst)
        {
            m_enabled = enabled;

            MaxDripRate = maxDripRate;

            if (enabled)
                AdjustedDripRate = m_maxDripRate * .5f;
            else
                AdjustedDripRate = m_maxDripRate;
        }
                
        /// <summary>
        /// Reliable packets sent to the client for which we never received an ack adjust the drip rate down.
        /// <param name="packets">Number of packets that expired without successful delivery</param>
        /// </summary>
        public void ExpirePackets(Int32 count)
        {
            // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
            if (m_enabled)
                AdjustedDripRate = (Int64)(AdjustedDripRate / Math.Pow(2, count));
        }

        // <summary>
        // 
        // </summary>
        public void AcknowledgePackets(Int32 count)
        {
            if (m_enabled)
                AdjustedDripRate = AdjustedDripRate + count;
        }
    }
}