From d8ee0cbe1cf93ca521f52ce39aa2a15cb5784e48 Mon Sep 17 00:00:00 2001 From: Diva Canto Date: Sat, 30 Apr 2011 09:24:15 -0700 Subject: First stab at cleaning up Caps. Compiles. Untested. --- .../Region/ClientStack/Linden/UDP/TokenBucket.cs | 393 +++++++++++++++++++++ 1 file changed, 393 insertions(+) create mode 100644 OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs (limited to 'OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs') diff --git a/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs b/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs new file mode 100644 index 0000000..29fd1a4 --- /dev/null +++ b/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs @@ -0,0 +1,393 @@ +/* + * 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 +{ + /// + /// A hierarchical token bucket for bandwidth throttling. See + /// http://en.wikipedia.org/wiki/Token_bucket for more information + /// + public class TokenBucket + { + private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); + private static Int32 m_counter = 0; + + private Int32 m_identifier; + + /// + /// Number of ticks (ms) per quantum, drip rate and max burst + /// are defined over this interval. + /// + protected const Int32 m_ticksPerQuantum = 1000; + + /// + /// This is the number of quantums worth of packets that can + /// be accommodated during a burst + /// + protected const Double m_quantumsPerBurst = 1.5; + + /// + /// + protected const Int32 m_minimumDripRate = 1400; + + /// Time of the last drip, in system ticks + protected Int32 m_lastDrip; + + /// + /// The number of bytes that can be sent at this moment. This is the + /// current number of tokens in the bucket + /// + protected Int64 m_tokenCount; + + /// + /// Map of children buckets and their requested maximum burst rate + /// + protected Dictionary m_children = new Dictionary(); + +#region Properties + + /// + /// 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 + /// + protected TokenBucket m_parent; + public TokenBucket Parent + { + get { return m_parent; } + set { m_parent = value; } + } + + /// + /// 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 + /// + 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; + } + } + + /// + /// The speed limit of this bucket in bytes per second. This is the + /// number of tokens that are added to the bucket per quantum + /// + /// Tokens are added to the bucket any time + /// is called, at the granularity of + /// the system tick interval (typically around 15-22ms) + protected Int64 m_dripRate; + public virtual Int64 RequestedDripRate + { + get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); } + set { + m_dripRate = (value < 0 ? 0 : value); + m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); + m_totalDripRequest = m_dripRate; + if (m_parent != null) + m_parent.RegisterRequest(this,m_dripRate); + } + } + + public virtual Int64 DripRate + { + get { + if (m_parent == null) + return Math.Min(RequestedDripRate,TotalDripRequest); + + double rate = (double)RequestedDripRate * m_parent.DripRateModifier(); + if (rate < m_minimumDripRate) + rate = m_minimumDripRate; + + return (Int64)rate; + } + } + + /// + /// The current total of the requested maximum burst rates of + /// this bucket's children buckets. + /// + protected Int64 m_totalDripRequest; + public Int64 TotalDripRequest + { + get { return m_totalDripRequest; } + set { m_totalDripRequest = value; } + } + +#endregion Properties + +#region Constructor + + /// + /// Default constructor + /// + /// Parent bucket if this is a child bucket, or + /// null if this is a root bucket + /// Maximum size of the bucket in bytes, or + /// zero if this bucket has no maximum capacity + /// Rate that the bucket fills, in bytes per + /// second. If zero, the bucket always remains full + public TokenBucket(TokenBucket parent, Int64 dripRate) + { + m_identifier = m_counter++; + + Parent = parent; + RequestedDripRate = dripRate; + // TotalDripRequest = dripRate; // this will be overwritten when a child node registers + // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst); + m_lastDrip = Util.EnvironmentTickCount(); + } + +#endregion Constructor + + /// + /// 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. + /// + protected double DripRateModifier() + { + Int64 driprate = DripRate; + return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest; + } + + /// + /// + 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(); + } + + /// + /// Register drip rate requested by a child of this throttle. Pass the + /// changes up the hierarchy. + /// + public void RegisterRequest(TokenBucket child, Int64 request) + { + lock (m_children) + { + m_children[child] = request; + // m_totalDripRequest = m_children.Values.Sum(); + + m_totalDripRequest = 0; + foreach (KeyValuePair 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)); + } + + /// + /// Remove the rate requested by a child of this throttle. Pass the + /// changes up the hierarchy. + /// + public void UnregisterRequest(TokenBucket child) + { + lock (m_children) + { + m_children.Remove(child); + // m_totalDripRequest = m_children.Values.Sum(); + + m_totalDripRequest = 0; + foreach (KeyValuePair 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)); + } + + /// + /// Remove a given number of tokens from the bucket + /// + /// Number of tokens to remove from the bucket + /// True if the requested number of tokens were removed from + /// the bucket, otherwise false + 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; + } + + /// + /// Deposit tokens into the bucket from a child bucket that did + /// not use all of its available tokens + /// + 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; + } + + /// + /// 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 + /// + /// True if tokens were added to the bucket, otherwise false + 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"); + 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); + + /// + /// 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. + /// + protected const Int64 m_minimumFlow = m_minimumDripRate * 15; + + // + // The maximum rate for flow control. Drip rate can never be + // greater than this. + // + protected Int64 m_maxDripRate = 0; + protected Int64 MaxDripRate + { + get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); } + set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); } + } + + private bool m_enabled = false; + + // + // + // + public virtual Int64 AdjustedDripRate + { + get { return m_dripRate; } + set { + m_dripRate = OpenSim.Framework.Util.Clamp(value,m_minimumFlow,MaxDripRate); + m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); + if (m_parent != null) + m_parent.RegisterRequest(this,m_dripRate); + } + } + + // + // + // + public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate, bool enabled) : base(parent,maxDripRate) + { + m_enabled = enabled; + + if (m_enabled) + { + // m_log.DebugFormat("[TOKENBUCKET] Adaptive throttle enabled"); + MaxDripRate = maxDripRate; + AdjustedDripRate = m_minimumFlow; + } + } + + // + // + // + 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)); + } + + // + // + // + public void AcknowledgePackets(Int32 count) + { + if (m_enabled) + AdjustedDripRate = AdjustedDripRate + count; + } + } +} -- cgit v1.1