1
0

TokenBucket.cs 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. using System.Collections;
  29. using System.Collections.Generic;
  30. using System.Reflection;
  31. using OpenSim.Framework;
  32. using log4net;
  33. namespace OpenSim.Region.ClientStack.LindenUDP
  34. {
  35. /// <summary>
  36. /// A hierarchical token bucket for bandwidth throttling. See
  37. /// http://en.wikipedia.org/wiki/Token_bucket for more information
  38. /// </summary>
  39. public class TokenBucket
  40. {
  41. private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
  42. private static Int32 m_counter = 0;
  43. // private Int32 m_identifier;
  44. protected const float m_timeScale = 1e-3f;
  45. /// <summary>
  46. /// This is the number of m_minimumDripRate bytes
  47. /// allowed in a burst
  48. /// roughtly, with this settings, the maximum time system will take
  49. /// to recheck a bucket in ms
  50. ///
  51. /// </summary>
  52. protected const float m_quantumsPerBurst = 5;
  53. /// <summary>
  54. /// </summary>
  55. protected const float m_minimumDripRate = 1500;
  56. /// <summary>Time of the last drip</summary>
  57. protected double m_lastDrip;
  58. /// <summary>
  59. /// The number of bytes that can be sent at this moment. This is the
  60. /// current number of tokens in the bucket
  61. /// </summary>
  62. protected float m_tokenCount;
  63. /// <summary>
  64. /// Map of children buckets and their requested maximum burst rate
  65. /// </summary>
  66. protected Dictionary<TokenBucket, float> m_children = new Dictionary<TokenBucket, float>();
  67. #region Properties
  68. /// <summary>
  69. /// The parent bucket of this bucket, or null if this bucket has no
  70. /// parent. The parent bucket will limit the aggregate bandwidth of all
  71. /// of its children buckets
  72. /// </summary>
  73. protected TokenBucket m_parent;
  74. public TokenBucket Parent
  75. {
  76. get { return m_parent; }
  77. set { m_parent = value; }
  78. }
  79. /// <summary>
  80. /// This is the maximum number
  81. /// of tokens that can accumulate in the bucket at any one time. This
  82. /// also sets the total request for leaf nodes
  83. /// </summary>
  84. protected float m_burst;
  85. protected float m_maxDripRate = 0;
  86. public virtual float MaxDripRate
  87. {
  88. get { return m_maxDripRate; }
  89. set { m_maxDripRate = value; }
  90. }
  91. public float RequestedBurst
  92. {
  93. get { return m_burst; }
  94. set {
  95. float rate = (value < 0 ? 0 : value);
  96. if (rate < 1.5f * m_minimumDripRate)
  97. rate = 1.5f * m_minimumDripRate;
  98. else if (rate > m_minimumDripRate * m_quantumsPerBurst)
  99. rate = m_minimumDripRate * m_quantumsPerBurst;
  100. m_burst = rate;
  101. }
  102. }
  103. public float Burst
  104. {
  105. get {
  106. float rate = RequestedBurst * BurstModifier();
  107. if (rate < m_minimumDripRate)
  108. rate = m_minimumDripRate;
  109. return (float)rate;
  110. }
  111. }
  112. /// <summary>
  113. /// The requested drip rate for this particular bucket.
  114. /// </summary>
  115. /// <remarks>
  116. /// 0 then TotalDripRequest is used instead.
  117. /// Can never be above MaxDripRate.
  118. /// Tokens are added to the bucket at any time
  119. /// <seealso cref="RemoveTokens"/> is called, at the granularity of
  120. /// the system tick interval (typically around 15-22ms)</remarks>
  121. protected float m_dripRate;
  122. public float RequestedDripRate
  123. {
  124. get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); }
  125. set {
  126. m_dripRate = (value < 0 ? 0 : value);
  127. m_totalDripRequest = m_dripRate;
  128. if (m_parent != null)
  129. m_parent.RegisterRequest(this,m_dripRate);
  130. }
  131. }
  132. public float DripRate
  133. {
  134. get {
  135. float rate = Math.Min(RequestedDripRate,TotalDripRequest);
  136. if (m_parent == null)
  137. return rate;
  138. rate *= m_parent.DripRateModifier();
  139. if (rate < m_minimumDripRate)
  140. rate = m_minimumDripRate;
  141. return (float)rate;
  142. }
  143. }
  144. /// <summary>
  145. /// The current total of the requested maximum burst rates of children buckets.
  146. /// </summary>
  147. protected float m_totalDripRequest;
  148. public float TotalDripRequest
  149. {
  150. get { return m_totalDripRequest; }
  151. set { m_totalDripRequest = value; }
  152. }
  153. #endregion Properties
  154. #region Constructor
  155. /// <summary>
  156. /// Default constructor
  157. /// </summary>
  158. /// <param name="identifier">Identifier for this token bucket</param>
  159. /// <param name="parent">Parent bucket if this is a child bucket, or
  160. /// null if this is a root bucket</param>
  161. /// <param name="maxBurst">Maximum size of the bucket in bytes, or
  162. /// zero if this bucket has no maximum capacity</param>
  163. /// <param name="dripRate">Rate that the bucket fills, in bytes per
  164. /// second. If zero, the bucket always remains full</param>
  165. public TokenBucket(TokenBucket parent, float dripRate, float MaxBurst)
  166. {
  167. m_counter++;
  168. Parent = parent;
  169. RequestedDripRate = dripRate;
  170. RequestedBurst = MaxBurst;
  171. m_lastDrip = Util.GetTimeStampMS() + 100000.0; // skip first drip
  172. }
  173. #endregion Constructor
  174. /// <summary>
  175. /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning
  176. /// no modification if the requested bandwidth is less than the
  177. /// max burst bandwidth all the way to the root of the throttle
  178. /// hierarchy. However, if any of the parents is over-booked, then
  179. /// the modifier will be less than 1.
  180. /// </summary>
  181. protected float DripRateModifier()
  182. {
  183. float driprate = DripRate;
  184. return driprate >= TotalDripRequest ? 1.0f : (driprate / TotalDripRequest);
  185. }
  186. /// <summary>
  187. /// </summary>
  188. protected float BurstModifier()
  189. {
  190. // for now... burst rate is always m_quantumsPerBurst (constant)
  191. // larger than drip rate so the ratio of burst requests is the
  192. // same as the drip ratio
  193. return DripRateModifier();
  194. }
  195. /// <summary>
  196. /// Register drip rate requested by a child of this throttle. Pass the
  197. /// changes up the hierarchy.
  198. /// </summary>
  199. public void RegisterRequest(TokenBucket child, float request)
  200. {
  201. lock (m_children)
  202. {
  203. m_children[child] = request;
  204. m_totalDripRequest = 0;
  205. foreach (KeyValuePair<TokenBucket, float> cref in m_children)
  206. m_totalDripRequest += cref.Value;
  207. }
  208. // Pass the new values up to the parent
  209. if (m_parent != null)
  210. m_parent.RegisterRequest(this, Math.Min(RequestedDripRate, TotalDripRequest));
  211. }
  212. /// <summary>
  213. /// Remove the rate requested by a child of this throttle. Pass the
  214. /// changes up the hierarchy.
  215. /// </summary>
  216. public void UnregisterRequest(TokenBucket child)
  217. {
  218. lock (m_children)
  219. {
  220. m_children.Remove(child);
  221. m_totalDripRequest = 0;
  222. foreach (KeyValuePair<TokenBucket, float> cref in m_children)
  223. m_totalDripRequest += cref.Value;
  224. }
  225. // Pass the new values up to the parent
  226. if (Parent != null)
  227. Parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
  228. }
  229. /// <summary>
  230. /// Remove a given number of tokens from the bucket
  231. /// </summary>
  232. /// <param name="amount">Number of tokens to remove from the bucket</param>
  233. /// <returns>True if the requested number of tokens were removed from
  234. /// the bucket, otherwise false</returns>
  235. public bool RemoveTokens(int amount)
  236. {
  237. // Deposit tokens for this interval
  238. Drip();
  239. // If we have enough tokens then remove them and return
  240. if (m_tokenCount - amount >= 0)
  241. {
  242. // we don't have to remove from the parent, the drip rate is already
  243. // reflective of the drip rate limits in the parent
  244. m_tokenCount -= amount;
  245. return true;
  246. }
  247. return false;
  248. }
  249. public bool CheckTokens(int amount)
  250. {
  251. return (m_tokenCount - amount >= 0);
  252. }
  253. public int GetCatBytesCanSend(int timeMS)
  254. {
  255. // return (int)(m_tokenCount + timeMS * m_dripRate * 1e-3);
  256. return (int)(timeMS * DripRate * 1e-3);
  257. }
  258. /// <summary>
  259. /// Add tokens to the bucket over time. The number of tokens added each
  260. /// call depends on the length of time that has passed since the last
  261. /// call to Drip
  262. /// </summary>
  263. /// <returns>True if tokens were added to the bucket, otherwise false</returns>
  264. protected void Drip()
  265. {
  266. // This should never happen... means we are a leaf node and were created
  267. // with no drip rate...
  268. if (DripRate == 0)
  269. {
  270. m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0 for {0}", m_counter);
  271. return;
  272. }
  273. double now = Util.GetTimeStampMS();
  274. double deltaMS = now - m_lastDrip;
  275. m_lastDrip = now;
  276. if (deltaMS <= 0)
  277. return;
  278. m_tokenCount += (float)deltaMS * DripRate * m_timeScale;
  279. float burst = Burst;
  280. if (m_tokenCount > burst)
  281. m_tokenCount = burst;
  282. }
  283. }
  284. public class AdaptiveTokenBucket : TokenBucket
  285. {
  286. private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
  287. public bool AdaptiveEnabled { get; set; }
  288. /// <summary>
  289. /// The minimum rate for flow control. Minimum drip rate is one
  290. /// packet per second.
  291. /// </summary>
  292. protected const float m_minimumFlow = 50000;
  293. // <summary>
  294. // The maximum rate for flow control. Drip rate can never be
  295. // greater than this.
  296. // </summary>
  297. public override float MaxDripRate
  298. {
  299. get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); }
  300. set
  301. {
  302. m_maxDripRate = (value == 0 ? m_totalDripRequest : Math.Max(value, m_minimumFlow));
  303. }
  304. }
  305. private bool m_enabled = false;
  306. // <summary>
  307. // Adjust drip rate in response to network conditions.
  308. // </summary>
  309. public float AdjustedDripRate
  310. {
  311. get { return m_dripRate; }
  312. set
  313. {
  314. m_dripRate = OpenSim.Framework.Util.Clamp<float>(value, m_minimumFlow, MaxDripRate);
  315. if (m_parent != null)
  316. m_parent.RegisterRequest(this, m_dripRate);
  317. }
  318. }
  319. // <summary>
  320. //
  321. // </summary>
  322. public AdaptiveTokenBucket(TokenBucket parent, float maxDripRate, float maxBurst, bool enabled)
  323. : base(parent, maxDripRate, maxBurst)
  324. {
  325. m_enabled = enabled;
  326. m_maxDripRate = (maxDripRate == 0 ? m_totalDripRequest : Math.Max(maxDripRate, m_minimumFlow));
  327. if (enabled)
  328. m_dripRate = m_maxDripRate * .5f;
  329. else
  330. m_dripRate = m_maxDripRate;
  331. if (m_parent != null)
  332. m_parent.RegisterRequest(this, m_dripRate);
  333. }
  334. /// <summary>
  335. /// Reliable packets sent to the client for which we never received an ack adjust the drip rate down.
  336. /// <param name="packets">Number of packets that expired without successful delivery</param>
  337. /// </summary>
  338. public void ExpirePackets(Int32 count)
  339. {
  340. // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
  341. if (m_enabled)
  342. AdjustedDripRate = (Int64)(AdjustedDripRate / Math.Pow(2, count));
  343. }
  344. // <summary>
  345. //
  346. // </summary>
  347. public void AcknowledgePackets(Int32 count)
  348. {
  349. if (m_enabled)
  350. AdjustedDripRate = AdjustedDripRate + count;
  351. }
  352. }
  353. }