1
0

TokenBucket.cs 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  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. namespace OpenSim.Region.ClientStack.LindenUDP
  29. {
  30. /// <summary>
  31. /// A hierarchical token bucket for bandwidth throttling. See
  32. /// http://en.wikipedia.org/wiki/Token_bucket for more information
  33. /// </summary>
  34. public class TokenBucket
  35. {
  36. /// <summary>Parent bucket to this bucket, or null if this is a root
  37. /// bucket</summary>
  38. TokenBucket parent;
  39. /// <summary>Size of the bucket in bytes. If zero, the bucket has
  40. /// infinite capacity</summary>
  41. int maxBurst;
  42. /// <summary>Rate that the bucket fills, in bytes per millisecond. If
  43. /// zero, the bucket always remains full</summary>
  44. int tokensPerMS;
  45. /// <summary>Number of tokens currently in the bucket</summary>
  46. int content;
  47. /// <summary>Time of the last drip, in system ticks</summary>
  48. int lastDrip;
  49. #region Properties
  50. /// <summary>
  51. /// The parent bucket of this bucket, or null if this bucket has no
  52. /// parent. The parent bucket will limit the aggregate bandwidth of all
  53. /// of its children buckets
  54. /// </summary>
  55. public TokenBucket Parent
  56. {
  57. get { return parent; }
  58. }
  59. /// <summary>
  60. /// Maximum burst rate in bytes per second. This is the maximum number
  61. /// of tokens that can accumulate in the bucket at any one time
  62. /// </summary>
  63. public int MaxBurst
  64. {
  65. get { return maxBurst; }
  66. set { maxBurst = (value >= 0 ? value : 0); }
  67. }
  68. /// <summary>
  69. /// The speed limit of this bucket in bytes per second. This is the
  70. /// number of tokens that are added to the bucket per second
  71. /// </summary>
  72. /// <remarks>Tokens are added to the bucket any time
  73. /// <seealso cref="RemoveTokens"/> is called, at the granularity of
  74. /// the system tick interval (typically around 15-22ms)</remarks>
  75. public int DripRate
  76. {
  77. get { return tokensPerMS * 1000; }
  78. set
  79. {
  80. if (value == 0)
  81. tokensPerMS = 0;
  82. else
  83. {
  84. int bpms = (int)((float)value / 1000.0f);
  85. if (bpms <= 0)
  86. tokensPerMS = 1; // 1 byte/ms is the minimum granularity
  87. else
  88. tokensPerMS = bpms;
  89. }
  90. }
  91. }
  92. /// <summary>
  93. /// The speed limit of this bucket in bytes per millisecond
  94. /// </summary>
  95. public int DripPerMS
  96. {
  97. get { return tokensPerMS; }
  98. }
  99. /// <summary>
  100. /// The number of bytes that can be sent at this moment. This is the
  101. /// current number of tokens in the bucket
  102. /// <remarks>If this bucket has a parent bucket that does not have
  103. /// enough tokens for a request, <seealso cref="RemoveTokens"/> will
  104. /// return false regardless of the content of this bucket</remarks>
  105. /// </summary>
  106. public int Content
  107. {
  108. get { return content; }
  109. }
  110. #endregion Properties
  111. /// <summary>
  112. /// Default constructor
  113. /// </summary>
  114. /// <param name="parent">Parent bucket if this is a child bucket, or
  115. /// null if this is a root bucket</param>
  116. /// <param name="maxBurst">Maximum size of the bucket in bytes, or
  117. /// zero if this bucket has no maximum capacity</param>
  118. /// <param name="dripRate">Rate that the bucket fills, in bytes per
  119. /// second. If zero, the bucket always remains full</param>
  120. public TokenBucket(TokenBucket parent, int maxBurst, int dripRate)
  121. {
  122. this.parent = parent;
  123. MaxBurst = maxBurst;
  124. DripRate = dripRate;
  125. lastDrip = Environment.TickCount & Int32.MaxValue;
  126. }
  127. /// <summary>
  128. /// Remove a given number of tokens from the bucket
  129. /// </summary>
  130. /// <param name="amount">Number of tokens to remove from the bucket</param>
  131. /// <returns>True if the requested number of tokens were removed from
  132. /// the bucket, otherwise false</returns>
  133. public bool RemoveTokens(int amount)
  134. {
  135. bool dummy;
  136. return RemoveTokens(amount, out dummy);
  137. }
  138. /// <summary>
  139. /// Remove a given number of tokens from the bucket
  140. /// </summary>
  141. /// <param name="amount">Number of tokens to remove from the bucket</param>
  142. /// <param name="dripSucceeded">True if tokens were added to the bucket
  143. /// during this call, otherwise false</param>
  144. /// <returns>True if the requested number of tokens were removed from
  145. /// the bucket, otherwise false</returns>
  146. public bool RemoveTokens(int amount, out bool dripSucceeded)
  147. {
  148. if (maxBurst == 0)
  149. {
  150. dripSucceeded = true;
  151. return true;
  152. }
  153. dripSucceeded = Drip();
  154. if (content - amount >= 0)
  155. {
  156. if (parent != null && !parent.RemoveTokens(amount))
  157. return false;
  158. content -= amount;
  159. return true;
  160. }
  161. else
  162. {
  163. return false;
  164. }
  165. }
  166. /// <summary>
  167. /// Add tokens to the bucket over time. The number of tokens added each
  168. /// call depends on the length of time that has passed since the last
  169. /// call to Drip
  170. /// </summary>
  171. /// <returns>True if tokens were added to the bucket, otherwise false</returns>
  172. public bool Drip()
  173. {
  174. if (tokensPerMS == 0)
  175. {
  176. content = maxBurst;
  177. return true;
  178. }
  179. else
  180. {
  181. int now = Environment.TickCount & Int32.MaxValue;
  182. int deltaMS = now - lastDrip;
  183. if (deltaMS <= 0)
  184. {
  185. if (deltaMS < 0)
  186. lastDrip = now;
  187. return false;
  188. }
  189. int dripAmount = deltaMS * tokensPerMS;
  190. content = Math.Min(content + dripAmount, maxBurst);
  191. lastDrip = now;
  192. return true;
  193. }
  194. }
  195. }
  196. }