Adds the first pass at an adaptive throttle to slow start new

clients. If the sent packets are ack'ed successfully the throttle
will open quickly up to the maximum specified by the client and/or
the sims client throttle.

This still needs a lot of adjustment to get the rates correct.

4 files changed, 95 insertions, 18 deletions

diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 87b86eb..1108863 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -3585,6 +3585,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// </summary>
         private void ResendPrimUpdates(List<EntityUpdate> updates)
         {
+            // m_log.WarnFormat("[CLIENT] resending prim update {0}",updates[0].UpdateTime);
+            
             foreach (EntityUpdate update in updates)
                 ResendPrimUpdate(update);
         }
@@ -4027,6 +4029,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
         private void ResendPropertyUpdates(List<ObjectPropertyUpdate> updates)
         {
+            // m_log.WarnFormat("[CLIENT] resending object property {0}",updates[0].UpdateTime);
+
             foreach (ObjectPropertyUpdate update in updates)
                 ResendPropertyUpdate(update);
         }
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
index 7be8a0a..20bfec8 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
@@ -135,7 +135,12 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         private int m_nextOnQueueEmpty = 1;
 
         /// <summary>Throttle bucket for this agent's connection</summary>
-        private readonly TokenBucket m_throttleClient;
+        private readonly AdaptiveTokenBucket m_throttleClient;
+        public AdaptiveTokenBucket FlowThrottle
+        {
+            get { return m_throttleClient; }
+        }
+
         /// <summary>Throttle bucket for this agent's connection</summary>
         private readonly TokenBucket m_throttleCategory;
         /// <summary>Throttle buckets for each packet category</summary>
@@ -176,7 +181,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                 m_maxRTO = maxRTO;
 
             // Create a token bucket throttle for this client that has the scene token bucket as a parent
-            m_throttleClient = new TokenBucket(parentThrottle, rates.TotalLimit);
+            m_throttleClient = new AdaptiveTokenBucket(parentThrottle, rates.TotalLimit);
             // Create a token bucket throttle for the total categary with the client bucket as a throttle
             m_throttleCategory = new TokenBucket(m_throttleClient, rates.TotalLimit);
             // Create an array of token buckets for this clients different throttle categories
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
index 07b0a1d..4ee6d3a 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs
@@ -48,31 +48,31 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// Number of ticks (ms) per quantum, drip rate and max burst
         /// are defined over this interval.
         /// </summary>
-        private const Int32 m_ticksPerQuantum = 1000;
+        protected const Int32 m_ticksPerQuantum = 1000;
 
         /// <summary>
         /// This is the number of quantums worth of packets that can
         /// be accommodated during a burst
         /// </summary>
-        private const Double m_quantumsPerBurst = 1.5;
+        protected const Double m_quantumsPerBurst = 1.5;
                 
         /// <summary>
         /// </summary>
-        private const Int32 m_minimumDripRate = 1400;
+        protected const Int32 m_minimumDripRate = 1400;
         
         /// <summary>Time of the last drip, in system ticks</summary>
-        private Int32 m_lastDrip;
+        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>
-        private Int64 m_tokenCount;
+        protected Int64 m_tokenCount;
 
         /// <summary>
         /// Map of children buckets and their requested maximum burst rate
         /// </summary>
-        private Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>();
+        protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>();
         
 #region Properties
 
@@ -81,7 +81,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// parent. The parent bucket will limit the aggregate bandwidth of all
         /// of its children buckets
         /// </summary>
-        private TokenBucket m_parent;
+        protected TokenBucket m_parent;
         public TokenBucket Parent
         {
             get { return m_parent; }
@@ -93,7 +93,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// of tokens that can accumulate in the bucket at any one time. This 
         /// also sets the total request for leaf nodes
         /// </summary>
-        private Int64 m_burstRate;
+        protected Int64 m_burstRate;
         public Int64 RequestedBurstRate
         {
             get { return m_burstRate; }
@@ -118,8 +118,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// <remarks>Tokens are added to the bucket any time 
         /// <seealso cref="RemoveTokens"/> is called, at the granularity of
         /// the system tick interval (typically around 15-22ms)</remarks>
-        private Int64 m_dripRate;
-        public Int64 RequestedDripRate
+        protected Int64 m_dripRate;
+        public virtual Int64 RequestedDripRate
         {
             get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); }
             set {
@@ -131,7 +131,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             }
         }
 
-        public Int64 DripRate
+        public virtual Int64 DripRate
         {
             get {
                 if (m_parent == null)
@@ -149,7 +149,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// The current total of the requested maximum burst rates of 
         /// this bucket's children buckets.
         /// </summary>
-        private Int64 m_totalDripRequest;
+        protected Int64 m_totalDripRequest;
         public Int64 TotalDripRequest 
             {
                 get { return m_totalDripRequest; }
@@ -189,7 +189,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// hierarchy. However, if any of the parents is over-booked, then
         /// the modifier will be less than 1.
         /// </summary>
-        private double DripRateModifier()
+        protected double DripRateModifier()
         {
             Int64 driprate = DripRate;
             return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;
@@ -197,7 +197,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
         /// <summary>
         /// </summary>
-        private double BurstRateModifier()
+        protected double BurstRateModifier()
         {
             // for now... burst rate is always m_quantumsPerBurst (constant)
             // larger than drip rate so the ratio of burst requests is the
@@ -268,7 +268,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// Deposit tokens into the bucket from a child bucket that did
         /// not use all of its available tokens
         /// </summary>
-        private void Deposit(Int64 count)
+        protected void Deposit(Int64 count)
         {
             m_tokenCount += count;
 
@@ -285,7 +285,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// call to Drip
         /// </summary>
         /// <returns>True if tokens were added to the bucket, otherwise false</returns>
-        private void Drip()
+        protected void Drip()
         {
             // This should never happen... means we are a leaf node and were created
             // with no drip rate...
@@ -310,4 +310,64 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             Deposit(deltaMS * DripRate / m_ticksPerQuantum);
         }
     }
+
+    public class AdaptiveTokenBucket : TokenBucket
+    {
+        private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
+
+        // <summary>
+        // The minimum rate for flow control. 
+        // </summary>
+        protected const Int64 m_minimumFlow = m_minimumDripRate * 10;
+
+        // <summary>
+        // The maximum rate for flow control. Drip rate can never be
+        // greater than this.
+        // </summary>
+        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)); }
+        }
+        
+        // <summary>
+        // 
+        // </summary>
+        public virtual Int64 AdjustedDripRate
+        {
+            get { return m_dripRate; }
+            set {
+                m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value,m_minimumFlow,MaxDripRate);
+                m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
+                if (m_parent != null)
+                    m_parent.RegisterRequest(this,m_dripRate);
+            }
+        }
+
+        // <summary>
+        // 
+        // </summary>
+        public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate) : base(parent,m_minimumFlow)
+        {
+            MaxDripRate = maxDripRate;
+        }
+                
+        // <summary>
+        // 
+        // </summary>
+        public void ExpirePackets(Int32 count)
+        {
+            // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
+            AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count));
+        }
+
+        // <summary>
+        // 
+        // </summary>
+        public void AcknowledgePackets(Int32 count)
+        {
+            AdjustedDripRate = AdjustedDripRate + count;
+        }
+    }
 }
diff --git a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
index d195110..b170964 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
@@ -130,6 +130,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                         // is actually sent out again
                         packet.TickCount = 0;
 
+                        // As with other network applications, assume that an expired packet is
+                        // an indication of some network problem, slow transmission
+                        packet.Client.FlowThrottle.ExpirePackets(1);
+                        
                         expiredPackets.Add(packet);
                     }
                 }
@@ -157,6 +161,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                     {
                         m_packets.Remove(pendingRemove.SequenceNumber);
 
+                        // As with other network applications, assume that an acknowledged packet is an
+                        // indication that the network can handle a little more load, speed up the transmission
+                        ackedPacket.Client.FlowThrottle.AcknowledgePackets(ackedPacket.Buffer.DataLength);
+
                         // Update stats
                         Interlocked.Add(ref ackedPacket.Client.UnackedBytes, -ackedPacket.Buffer.DataLength);