From 2f436875899f432a88f432ab86a6858b3a4cc373 Mon Sep 17 00:00:00 2001
From: Mic Bowman
Date: Mon, 11 Apr 2011 09:06:28 -0700
Subject: New tokenbucket algorithm. This one provides fair sharing of the
queues when client and simulator throttles are set. This algorithm also uses
pre-defined burst rate of 150% of the sustained rate for each of the
throttles.
Removed the "state" queue. The state queue is not a Linden queue and
appeared to be used just to get kill packets sent.
---
.../Region/ClientStack/LindenUDP/TokenBucket.cs | 300 ++++++++++++++-------
1 file changed, 196 insertions(+), 104 deletions(-)
(limited to 'OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs')
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
index 0a8331f..e4d59ff 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
@@ -26,6 +26,10 @@
*/
using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Reflection;
+using log4net;
namespace OpenSim.Region.ClientStack.LindenUDP
{
@@ -35,89 +39,126 @@ namespace OpenSim.Region.ClientStack.LindenUDP
///
public class TokenBucket
{
- /// Parent bucket to this bucket, or null if this is a root
- /// bucket
- TokenBucket parent;
- /// Size of the bucket in bytes. If zero, the bucket has
- /// infinite capacity
- int maxBurst;
- /// Rate that the bucket fills, in bytes per millisecond. If
- /// zero, the bucket always remains full
- int tokensPerMS;
- /// Number of tokens currently in the bucket
- int content;
+ 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.
+ ///
+ private const Int32 m_ticksPerQuantum = 1000;
+
+ ///
+ /// This is the number of quantums worth of packets that can
+ /// be accommodated during a burst
+ ///
+ private const Double m_quantumsPerBurst = 1.5;
+
+ ///
+ ///
+ private const Int32 m_minimumDripRate = 1400;
+
/// Time of the last drip, in system ticks
- int lastDrip;
+ private Int32 m_lastDrip;
+
+ ///
+ /// The number of bytes that can be sent at this moment. This is the
+ /// current number of tokens in the bucket
+ ///
+ private Int64 m_tokenCount;
- #region Properties
+ ///
+ /// Map of children buckets and their requested maximum burst rate
+ ///
+ private 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
///
+ private TokenBucket m_parent;
public TokenBucket Parent
{
- get { return 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
+ /// of tokens that can accumulate in the bucket at any one time. This
+ /// also sets the total request for leaf nodes
///
- public int MaxBurst
+ private Int64 m_burstRate;
+ public Int64 RequestedBurstRate
{
- get { return maxBurst; }
- set { maxBurst = (value >= 0 ? value : 0); }
+ 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 second
+ /// 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)
- public int DripRate
+ private Int64 m_dripRate;
+ public Int64 RequestedDripRate
{
- get { return tokensPerMS * 1000; }
- set
- {
- if (value == 0)
- tokensPerMS = 0;
- else
- {
- int bpms = (int)((float)value / 1000.0f);
-
- if (bpms <= 0)
- tokensPerMS = 1; // 1 byte/ms is the minimum granularity
- else
- tokensPerMS = bpms;
- }
+ 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);
}
}
- ///
- /// The speed limit of this bucket in bytes per millisecond
- ///
- public int DripPerMS
+ public Int64 DripRate
{
- get { return tokensPerMS; }
+ 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 number of bytes that can be sent at this moment. This is the
- /// current number of tokens in the bucket
- /// If this bucket has a parent bucket that does not have
- /// enough tokens for a request, will
- /// return false regardless of the content of this bucket
+ /// The current total of the requested maximum burst rates of
+ /// this bucket's children buckets.
///
- public int Content
- {
- get { return content; }
- }
+ private Int64 m_totalDripRequest;
+ public Int64 TotalDripRequest
+ {
+ get { return m_totalDripRequest; }
+ set { m_totalDripRequest = value; }
+ }
+
+#endregion Properties
- #endregion Properties
+#region Constructor
///
/// Default constructor
@@ -128,56 +169,115 @@ namespace OpenSim.Region.ClientStack.LindenUDP
/// 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, int maxBurst, int dripRate)
+ public TokenBucket(TokenBucket parent, Int64 dripRate)
{
- this.parent = parent;
- MaxBurst = maxBurst;
- DripRate = dripRate;
- lastDrip = Environment.TickCount & Int32.MaxValue;
+ 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 = Environment.TickCount & Int32.MaxValue;
}
+#endregion Constructor
+
///
- /// Remove a given number of tokens from the bucket
+ /// 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.
///
- /// 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(int amount)
+ private double DripRateModifier()
+ {
+ Int64 driprate = DripRate;
+ return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;
+ }
+
+ ///
+ ///
+ private 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)
{
- bool dummy;
- return RemoveTokens(amount, out dummy);
+ 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)
+ {
+ 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 tokens were added to the bucket
- /// during this call, otherwise false
/// True if the requested number of tokens were removed from
/// the bucket, otherwise false
- public bool RemoveTokens(int amount, out bool dripSucceeded)
+ public bool RemoveTokens(Int64 amount)
{
- if (maxBurst == 0)
+ // Deposit tokens for this interval
+ Drip();
+
+ // If we have enough tokens then remove them and return
+ if (m_tokenCount - amount >= 0)
{
- dripSucceeded = true;
- return true;
+ if (m_parent == null || m_parent.RemoveTokens(amount))
+ {
+ m_tokenCount -= amount;
+ return true;
+ }
}
- dripSucceeded = Drip();
+ return false;
+ }
- if (content - amount >= 0)
- {
- if (parent != null && !parent.RemoveTokens(amount))
- return false;
+ ///
+ /// Deposit tokens into the bucket from a child bucket that did
+ /// not use all of its available tokens
+ ///
+ private void Deposit(Int64 count)
+ {
+ m_tokenCount += count;
- content -= amount;
- return true;
- }
- else
- {
- return false;
- }
+ // Deposit the overflow in the parent bucket, this is how we share
+ // unused bandwidth
+ Int64 burstrate = BurstRate;
+ if (m_tokenCount > burstrate)
+ m_tokenCount = burstrate;
}
///
@@ -186,37 +286,29 @@ namespace OpenSim.Region.ClientStack.LindenUDP
/// call to Drip
///
/// True if tokens were added to the bucket, otherwise false
- public bool Drip()
+ private void Drip()
{
- if (tokensPerMS == 0)
+ // This should never happen... means we are a leaf node and were created
+ // with no drip rate...
+ if (DripRate == 0)
{
- content = maxBurst;
- return true;
+ m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0");
+ return;
}
- else
- {
- int now = Environment.TickCount & Int32.MaxValue;
- int deltaMS = now - lastDrip;
-
- if (deltaMS <= 0)
- {
- if (deltaMS < 0)
- lastDrip = now;
- return false;
- }
+
+ // Determine the interval over which we are adding tokens, never add
+ // more than a single quantum of tokens
+ Int32 now = Environment.TickCount & Int32.MaxValue;
+ Int32 deltaMS = Math.Min(now - m_lastDrip, m_ticksPerQuantum);
- int dripAmount = deltaMS * tokensPerMS;
+ m_lastDrip = now;
- content = Math.Min(content + dripAmount, maxBurst);
- lastDrip = now;
+ // 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;
- if (dripAmount < 0 || content < 0)
- // sim has been idle for too long, integer has overflown
- // previous calculation is meaningless, let's put it at correct max
- content = maxBurst;
-
- return true;
- }
+ Deposit(deltaMS * DripRate / m_ticksPerQuantum);
}
}
}
--
cgit v1.1
From 3e0e1057acffa2c92a6f949cef0183193033d8c2 Mon Sep 17 00:00:00 2001
From: Mic Bowman
Date: Fri, 15 Apr 2011 16:44:53 -0700
Subject: Remove the call to remove tokens from the parent. Under heavy load
this appears to cause problems with the system timer resolution. This caused
a problem with tokens going into the root throttle as bursts leading to some
starvation.
Also changed EnqueueOutgoing to always queue a packet if there
are already packets in the queue. Ensures consistent ordering
of packet sends.
---
OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs | 9 ++++-----
1 file changed, 4 insertions(+), 5 deletions(-)
(limited to 'OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs')
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
index e4d59ff..07b0a1d 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
@@ -255,11 +255,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP
// If we have enough tokens then remove them and return
if (m_tokenCount - amount >= 0)
{
- if (m_parent == null || m_parent.RemoveTokens(amount))
- {
- m_tokenCount -= amount;
- return true;
- }
+ // 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;
--
cgit v1.1