1
0

TokenBucket.cs 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394
  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. /// <summary>
  45. /// Number of ticks (ms) per quantum, drip rate and max burst
  46. /// are defined over this interval.
  47. /// </summary>
  48. protected const Int32 m_ticksPerQuantum = 1000;
  49. /// <summary>
  50. /// This is the number of quantums worth of packets that can
  51. /// be accommodated during a burst
  52. /// </summary>
  53. protected const Double m_quantumsPerBurst = 1.5;
  54. /// <summary>
  55. /// </summary>
  56. protected const Int32 m_minimumDripRate = 1400;
  57. /// <summary>Time of the last drip, in system ticks</summary>
  58. protected Int32 m_lastDrip;
  59. /// <summary>
  60. /// The number of bytes that can be sent at this moment. This is the
  61. /// current number of tokens in the bucket
  62. /// </summary>
  63. protected Int64 m_tokenCount;
  64. /// <summary>
  65. /// Map of children buckets and their requested maximum burst rate
  66. /// </summary>
  67. protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>();
  68. #region Properties
  69. /// <summary>
  70. /// The parent bucket of this bucket, or null if this bucket has no
  71. /// parent. The parent bucket will limit the aggregate bandwidth of all
  72. /// of its children buckets
  73. /// </summary>
  74. protected TokenBucket m_parent;
  75. public TokenBucket Parent
  76. {
  77. get { return m_parent; }
  78. set { m_parent = value; }
  79. }
  80. /// <summary>
  81. /// Maximum burst rate in bytes per second. This is the maximum number
  82. /// of tokens that can accumulate in the bucket at any one time. This
  83. /// also sets the total request for leaf nodes
  84. /// </summary>
  85. protected Int64 m_burstRate;
  86. public Int64 RequestedBurstRate
  87. {
  88. get { return m_burstRate; }
  89. set { m_burstRate = (value < 0 ? 0 : value); }
  90. }
  91. public Int64 BurstRate
  92. {
  93. get {
  94. double rate = RequestedBurstRate * BurstRateModifier();
  95. if (rate < m_minimumDripRate * m_quantumsPerBurst)
  96. rate = m_minimumDripRate * m_quantumsPerBurst;
  97. return (Int64) rate;
  98. }
  99. }
  100. /// <summary>
  101. /// The speed limit of this bucket in bytes per second. This is the
  102. /// number of tokens that are added to the bucket per quantum
  103. /// </summary>
  104. /// <remarks>Tokens are added to the bucket any time
  105. /// <seealso cref="RemoveTokens"/> is called, at the granularity of
  106. /// the system tick interval (typically around 15-22ms)</remarks>
  107. protected Int64 m_dripRate;
  108. public virtual Int64 RequestedDripRate
  109. {
  110. get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); }
  111. set {
  112. m_dripRate = (value < 0 ? 0 : value);
  113. m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
  114. m_totalDripRequest = m_dripRate;
  115. if (m_parent != null)
  116. m_parent.RegisterRequest(this,m_dripRate);
  117. }
  118. }
  119. public virtual Int64 DripRate
  120. {
  121. get {
  122. if (m_parent == null)
  123. return Math.Min(RequestedDripRate,TotalDripRequest);
  124. double rate = (double)RequestedDripRate * m_parent.DripRateModifier();
  125. if (rate < m_minimumDripRate)
  126. rate = m_minimumDripRate;
  127. return (Int64)rate;
  128. }
  129. }
  130. /// <summary>
  131. /// The current total of the requested maximum burst rates of
  132. /// this bucket's children buckets.
  133. /// </summary>
  134. protected Int64 m_totalDripRequest;
  135. public Int64 TotalDripRequest
  136. {
  137. get { return m_totalDripRequest; }
  138. set { m_totalDripRequest = value; }
  139. }
  140. #endregion Properties
  141. #region Constructor
  142. /// <summary>
  143. /// Default constructor
  144. /// </summary>
  145. /// <param name="parent">Parent bucket if this is a child bucket, or
  146. /// null if this is a root bucket</param>
  147. /// <param name="maxBurst">Maximum size of the bucket in bytes, or
  148. /// zero if this bucket has no maximum capacity</param>
  149. /// <param name="dripRate">Rate that the bucket fills, in bytes per
  150. /// second. If zero, the bucket always remains full</param>
  151. public TokenBucket(TokenBucket parent, Int64 dripRate)
  152. {
  153. // m_identifier = m_counter++;
  154. m_counter++;
  155. Parent = parent;
  156. RequestedDripRate = dripRate;
  157. // TotalDripRequest = dripRate; // this will be overwritten when a child node registers
  158. // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst);
  159. m_lastDrip = Util.EnvironmentTickCount();
  160. }
  161. #endregion Constructor
  162. /// <summary>
  163. /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning
  164. /// no modification if the requested bandwidth is less than the
  165. /// max burst bandwidth all the way to the root of the throttle
  166. /// hierarchy. However, if any of the parents is over-booked, then
  167. /// the modifier will be less than 1.
  168. /// </summary>
  169. protected double DripRateModifier()
  170. {
  171. Int64 driprate = DripRate;
  172. return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest;
  173. }
  174. /// <summary>
  175. /// </summary>
  176. protected double BurstRateModifier()
  177. {
  178. // for now... burst rate is always m_quantumsPerBurst (constant)
  179. // larger than drip rate so the ratio of burst requests is the
  180. // same as the drip ratio
  181. return DripRateModifier();
  182. }
  183. /// <summary>
  184. /// Register drip rate requested by a child of this throttle. Pass the
  185. /// changes up the hierarchy.
  186. /// </summary>
  187. public void RegisterRequest(TokenBucket child, Int64 request)
  188. {
  189. lock (m_children)
  190. {
  191. m_children[child] = request;
  192. // m_totalDripRequest = m_children.Values.Sum();
  193. m_totalDripRequest = 0;
  194. foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
  195. m_totalDripRequest += cref.Value;
  196. }
  197. // Pass the new values up to the parent
  198. if (m_parent != null)
  199. m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
  200. }
  201. /// <summary>
  202. /// Remove the rate requested by a child of this throttle. Pass the
  203. /// changes up the hierarchy.
  204. /// </summary>
  205. public void UnregisterRequest(TokenBucket child)
  206. {
  207. lock (m_children)
  208. {
  209. m_children.Remove(child);
  210. // m_totalDripRequest = m_children.Values.Sum();
  211. m_totalDripRequest = 0;
  212. foreach (KeyValuePair<TokenBucket, Int64> cref in m_children)
  213. m_totalDripRequest += cref.Value;
  214. }
  215. // Pass the new values up to the parent
  216. if (m_parent != null)
  217. m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest));
  218. }
  219. /// <summary>
  220. /// Remove a given number of tokens from the bucket
  221. /// </summary>
  222. /// <param name="amount">Number of tokens to remove from the bucket</param>
  223. /// <returns>True if the requested number of tokens were removed from
  224. /// the bucket, otherwise false</returns>
  225. public bool RemoveTokens(Int64 amount)
  226. {
  227. // Deposit tokens for this interval
  228. Drip();
  229. // If we have enough tokens then remove them and return
  230. if (m_tokenCount - amount >= 0)
  231. {
  232. // we don't have to remove from the parent, the drip rate is already
  233. // reflective of the drip rate limits in the parent
  234. m_tokenCount -= amount;
  235. return true;
  236. }
  237. return false;
  238. }
  239. /// <summary>
  240. /// Deposit tokens into the bucket from a child bucket that did
  241. /// not use all of its available tokens
  242. /// </summary>
  243. protected void Deposit(Int64 count)
  244. {
  245. m_tokenCount += count;
  246. // Deposit the overflow in the parent bucket, this is how we share
  247. // unused bandwidth
  248. Int64 burstrate = BurstRate;
  249. if (m_tokenCount > burstrate)
  250. m_tokenCount = burstrate;
  251. }
  252. /// <summary>
  253. /// Add tokens to the bucket over time. The number of tokens added each
  254. /// call depends on the length of time that has passed since the last
  255. /// call to Drip
  256. /// </summary>
  257. /// <returns>True if tokens were added to the bucket, otherwise false</returns>
  258. protected void Drip()
  259. {
  260. // This should never happen... means we are a leaf node and were created
  261. // with no drip rate...
  262. if (DripRate == 0)
  263. {
  264. m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0");
  265. return;
  266. }
  267. // Determine the interval over which we are adding tokens, never add
  268. // more than a single quantum of tokens
  269. Int32 deltaMS = Math.Min(Util.EnvironmentTickCountSubtract(m_lastDrip), m_ticksPerQuantum);
  270. m_lastDrip = Util.EnvironmentTickCount();
  271. // This can be 0 in the very unusual case that the timer wrapped
  272. // It can be 0 if we try add tokens at a sub-tick rate
  273. if (deltaMS <= 0)
  274. return;
  275. Deposit(deltaMS * DripRate / m_ticksPerQuantum);
  276. }
  277. }
  278. public class AdaptiveTokenBucket : TokenBucket
  279. {
  280. // private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
  281. /// <summary>
  282. /// The minimum rate for flow control. Minimum drip rate is one
  283. /// packet per second. Open the throttle to 15 packets per second
  284. /// or about 160kbps.
  285. /// </summary>
  286. protected const Int64 m_minimumFlow = m_minimumDripRate * 15;
  287. // <summary>
  288. // The maximum rate for flow control. Drip rate can never be
  289. // greater than this.
  290. // </summary>
  291. protected Int64 m_maxDripRate = 0;
  292. protected Int64 MaxDripRate
  293. {
  294. get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); }
  295. set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); }
  296. }
  297. private bool m_enabled = false;
  298. // <summary>
  299. //
  300. // </summary>
  301. public virtual Int64 AdjustedDripRate
  302. {
  303. get { return m_dripRate; }
  304. set {
  305. m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value,m_minimumFlow,MaxDripRate);
  306. m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst);
  307. if (m_parent != null)
  308. m_parent.RegisterRequest(this,m_dripRate);
  309. }
  310. }
  311. // <summary>
  312. //
  313. // </summary>
  314. public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate, bool enabled) : base(parent,maxDripRate)
  315. {
  316. m_enabled = enabled;
  317. if (m_enabled)
  318. {
  319. // m_log.DebugFormat("[TOKENBUCKET] Adaptive throttle enabled");
  320. MaxDripRate = maxDripRate;
  321. AdjustedDripRate = m_minimumFlow;
  322. }
  323. }
  324. // <summary>
  325. //
  326. // </summary>
  327. public void ExpirePackets(Int32 count)
  328. {
  329. // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count);
  330. if (m_enabled)
  331. AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count));
  332. }
  333. // <summary>
  334. //
  335. // </summary>
  336. public void AcknowledgePackets(Int32 count)
  337. {
  338. if (m_enabled)
  339. AdjustedDripRate = AdjustedDripRate + count;
  340. }
  341. }
  342. }