diff options
author | Justin Clark-Casey (justincc) | 2011-04-21 23:02:32 +0100 |
---|---|---|
committer | Justin Clark-Casey (justincc) | 2011-04-21 23:02:32 +0100 |
commit | 149d4e48d851e83037998d9034a1015975d8d35f (patch) | |
tree | 50f9511dc1a317047d9262e380b64cddbe09ffab /OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs | |
parent | Merge branch 'master' into 0.7.1-dev (diff) | |
parent | Merge branch 'master' of ssh://opensimulator.org/var/git/opensim (diff) | |
download | opensim-SC_OLD-149d4e48d851e83037998d9034a1015975d8d35f.zip opensim-SC_OLD-149d4e48d851e83037998d9034a1015975d8d35f.tar.gz opensim-SC_OLD-149d4e48d851e83037998d9034a1015975d8d35f.tar.bz2 opensim-SC_OLD-149d4e48d851e83037998d9034a1015975d8d35f.tar.xz |
Merge branch 'master' into 0.7.1-dev
Diffstat (limited to 'OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs')
-rw-r--r-- | OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs | 297 |
1 files changed, 194 insertions, 103 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs index 0a8331f..07b0a1d 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/TokenBucket.cs | |||
@@ -26,6 +26,10 @@ | |||
26 | */ | 26 | */ |
27 | 27 | ||
28 | using System; | 28 | using System; |
29 | using System.Collections; | ||
30 | using System.Collections.Generic; | ||
31 | using System.Reflection; | ||
32 | using log4net; | ||
29 | 33 | ||
30 | namespace OpenSim.Region.ClientStack.LindenUDP | 34 | namespace OpenSim.Region.ClientStack.LindenUDP |
31 | { | 35 | { |
@@ -35,89 +39,126 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
35 | /// </summary> | 39 | /// </summary> |
36 | public class TokenBucket | 40 | public class TokenBucket |
37 | { | 41 | { |
38 | /// <summary>Parent bucket to this bucket, or null if this is a root | 42 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); |
39 | /// bucket</summary> | 43 | private static Int32 m_counter = 0; |
40 | TokenBucket parent; | 44 | |
41 | /// <summary>Size of the bucket in bytes. If zero, the bucket has | 45 | private Int32 m_identifier; |
42 | /// infinite capacity</summary> | 46 | |
43 | int maxBurst; | 47 | /// <summary> |
44 | /// <summary>Rate that the bucket fills, in bytes per millisecond. If | 48 | /// Number of ticks (ms) per quantum, drip rate and max burst |
45 | /// zero, the bucket always remains full</summary> | 49 | /// are defined over this interval. |
46 | int tokensPerMS; | 50 | /// </summary> |
47 | /// <summary>Number of tokens currently in the bucket</summary> | 51 | private const Int32 m_ticksPerQuantum = 1000; |
48 | int content; | 52 | |
53 | /// <summary> | ||
54 | /// This is the number of quantums worth of packets that can | ||
55 | /// be accommodated during a burst | ||
56 | /// </summary> | ||
57 | private const Double m_quantumsPerBurst = 1.5; | ||
58 | |||
59 | /// <summary> | ||
60 | /// </summary> | ||
61 | private const Int32 m_minimumDripRate = 1400; | ||
62 | |||
49 | /// <summary>Time of the last drip, in system ticks</summary> | 63 | /// <summary>Time of the last drip, in system ticks</summary> |
50 | int lastDrip; | 64 | private Int32 m_lastDrip; |
51 | 65 | ||
52 | #region Properties | 66 | /// <summary> |
67 | /// The number of bytes that can be sent at this moment. This is the | ||
68 | /// current number of tokens in the bucket | ||
69 | /// </summary> | ||
70 | private Int64 m_tokenCount; | ||
71 | |||
72 | /// <summary> | ||
73 | /// Map of children buckets and their requested maximum burst rate | ||
74 | /// </summary> | ||
75 | private Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>(); | ||
76 | |||
77 | #region Properties | ||
53 | 78 | ||
54 | /// <summary> | 79 | /// <summary> |
55 | /// The parent bucket of this bucket, or null if this bucket has no | 80 | /// The parent bucket of this bucket, or null if this bucket has no |
56 | /// parent. The parent bucket will limit the aggregate bandwidth of all | 81 | /// parent. The parent bucket will limit the aggregate bandwidth of all |
57 | /// of its children buckets | 82 | /// of its children buckets |
58 | /// </summary> | 83 | /// </summary> |
84 | private TokenBucket m_parent; | ||
59 | public TokenBucket Parent | 85 | public TokenBucket Parent |
60 | { | 86 | { |
61 | get { return parent; } | 87 | get { return m_parent; } |
88 | set { m_parent = value; } | ||
62 | } | 89 | } |
63 | 90 | ||
64 | /// <summary> | 91 | /// <summary> |
65 | /// Maximum burst rate in bytes per second. This is the maximum number | 92 | /// Maximum burst rate in bytes per second. This is the maximum number |
66 | /// of tokens that can accumulate in the bucket at any one time | 93 | /// of tokens that can accumulate in the bucket at any one time. This |
94 | /// also sets the total request for leaf nodes | ||
67 | /// </summary> | 95 | /// </summary> |
68 | public int MaxBurst | 96 | private Int64 m_burstRate; |
97 | public Int64 RequestedBurstRate | ||
69 | { | 98 | { |
70 | get { return maxBurst; } | 99 | get { return m_burstRate; } |
71 | set { maxBurst = (value >= 0 ? value : 0); } | 100 | set { m_burstRate = (value < 0 ? 0 : value); } |
72 | } | 101 | } |
73 | 102 | ||
103 | public Int64 BurstRate | ||
104 | { | ||
105 | get { | ||
106 | double rate = RequestedBurstRate * BurstRateModifier(); | ||
107 | if (rate < m_minimumDripRate * m_quantumsPerBurst) | ||
108 | rate = m_minimumDripRate * m_quantumsPerBurst; | ||
109 | |||
110 | return (Int64) rate; | ||
111 | } | ||
112 | } | ||
113 | |||
74 | /// <summary> | 114 | /// <summary> |
75 | /// The speed limit of this bucket in bytes per second. This is the | 115 | /// The speed limit of this bucket in bytes per second. This is the |
76 | /// number of tokens that are added to the bucket per second | 116 | /// number of tokens that are added to the bucket per quantum |
77 | /// </summary> | 117 | /// </summary> |
78 | /// <remarks>Tokens are added to the bucket any time | 118 | /// <remarks>Tokens are added to the bucket any time |
79 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of | 119 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of |
80 | /// the system tick interval (typically around 15-22ms)</remarks> | 120 | /// the system tick interval (typically around 15-22ms)</remarks> |
81 | public int DripRate | 121 | private Int64 m_dripRate; |
122 | public Int64 RequestedDripRate | ||
82 | { | 123 | { |
83 | get { return tokensPerMS * 1000; } | 124 | get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); } |
84 | set | 125 | set { |
85 | { | 126 | m_dripRate = (value < 0 ? 0 : value); |
86 | if (value == 0) | 127 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); |
87 | tokensPerMS = 0; | 128 | m_totalDripRequest = m_dripRate; |
88 | else | 129 | if (m_parent != null) |
89 | { | 130 | m_parent.RegisterRequest(this,m_dripRate); |
90 | int bpms = (int)((float)value / 1000.0f); | ||
91 | |||
92 | if (bpms <= 0) | ||
93 | tokensPerMS = 1; // 1 byte/ms is the minimum granularity | ||
94 | else | ||
95 | tokensPerMS = bpms; | ||
96 | } | ||
97 | } | 131 | } |
98 | } | 132 | } |
99 | 133 | ||
100 | /// <summary> | 134 | public Int64 DripRate |
101 | /// The speed limit of this bucket in bytes per millisecond | ||
102 | /// </summary> | ||
103 | public int DripPerMS | ||
104 | { | 135 | { |
105 | get { return tokensPerMS; } | 136 | get { |
137 | if (m_parent == null) | ||
138 | return Math.Min(RequestedDripRate,TotalDripRequest); | ||
139 | |||
140 | double rate = (double)RequestedDripRate * m_parent.DripRateModifier(); | ||
141 | if (rate < m_minimumDripRate) | ||
142 | rate = m_minimumDripRate; | ||
143 | |||
144 | return (Int64)rate; | ||
145 | } | ||
106 | } | 146 | } |
107 | 147 | ||
108 | /// <summary> | 148 | /// <summary> |
109 | /// The number of bytes that can be sent at this moment. This is the | 149 | /// The current total of the requested maximum burst rates of |
110 | /// current number of tokens in the bucket | 150 | /// this bucket's children buckets. |
111 | /// <remarks>If this bucket has a parent bucket that does not have | ||
112 | /// enough tokens for a request, <seealso cref="RemoveTokens"/> will | ||
113 | /// return false regardless of the content of this bucket</remarks> | ||
114 | /// </summary> | 151 | /// </summary> |
115 | public int Content | 152 | private Int64 m_totalDripRequest; |
116 | { | 153 | public Int64 TotalDripRequest |
117 | get { return content; } | 154 | { |
118 | } | 155 | get { return m_totalDripRequest; } |
156 | set { m_totalDripRequest = value; } | ||
157 | } | ||
158 | |||
159 | #endregion Properties | ||
119 | 160 | ||
120 | #endregion Properties | 161 | #region Constructor |
121 | 162 | ||
122 | /// <summary> | 163 | /// <summary> |
123 | /// Default constructor | 164 | /// Default constructor |
@@ -128,56 +169,114 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
128 | /// zero if this bucket has no maximum capacity</param> | 169 | /// zero if this bucket has no maximum capacity</param> |
129 | /// <param name="dripRate">Rate that the bucket fills, in bytes per | 170 | /// <param name="dripRate">Rate that the bucket fills, in bytes per |
130 | /// second. If zero, the bucket always remains full</param> | 171 | /// second. If zero, the bucket always remains full</param> |
131 | public TokenBucket(TokenBucket parent, int maxBurst, int dripRate) | 172 | public TokenBucket(TokenBucket parent, Int64 dripRate) |
132 | { | 173 | { |
133 | this.parent = parent; | 174 | m_identifier = m_counter++; |
134 | MaxBurst = maxBurst; | 175 | |
135 | DripRate = dripRate; | 176 | Parent = parent; |
136 | lastDrip = Environment.TickCount & Int32.MaxValue; | 177 | RequestedDripRate = dripRate; |
178 | // TotalDripRequest = dripRate; // this will be overwritten when a child node registers | ||
179 | // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst); | ||
180 | m_lastDrip = Environment.TickCount & Int32.MaxValue; | ||
137 | } | 181 | } |
138 | 182 | ||
183 | #endregion Constructor | ||
184 | |||
139 | /// <summary> | 185 | /// <summary> |
140 | /// Remove a given number of tokens from the bucket | 186 | /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning |
187 | /// no modification if the requested bandwidth is less than the | ||
188 | /// max burst bandwidth all the way to the root of the throttle | ||
189 | /// hierarchy. However, if any of the parents is over-booked, then | ||
190 | /// the modifier will be less than 1. | ||
141 | /// </summary> | 191 | /// </summary> |
142 | /// <param name="amount">Number of tokens to remove from the bucket</param> | 192 | private double DripRateModifier() |
143 | /// <returns>True if the requested number of tokens were removed from | ||
144 | /// the bucket, otherwise false</returns> | ||
145 | public bool RemoveTokens(int amount) | ||
146 | { | 193 | { |
147 | bool dummy; | 194 | Int64 driprate = DripRate; |
148 | return RemoveTokens(amount, out dummy); | 195 | return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest; |
149 | } | 196 | } |
150 | 197 | ||
151 | /// <summary> | 198 | /// <summary> |
199 | /// </summary> | ||
200 | private double BurstRateModifier() | ||
201 | { | ||
202 | // for now... burst rate is always m_quantumsPerBurst (constant) | ||
203 | // larger than drip rate so the ratio of burst requests is the | ||
204 | // same as the drip ratio | ||
205 | return DripRateModifier(); | ||
206 | } | ||
207 | |||
208 | /// <summary> | ||
209 | /// Register drip rate requested by a child of this throttle. Pass the | ||
210 | /// changes up the hierarchy. | ||
211 | /// </summary> | ||
212 | public void RegisterRequest(TokenBucket child, Int64 request) | ||
213 | { | ||
214 | m_children[child] = request; | ||
215 | // m_totalDripRequest = m_children.Values.Sum(); | ||
216 | |||
217 | m_totalDripRequest = 0; | ||
218 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | ||
219 | m_totalDripRequest += cref.Value; | ||
220 | |||
221 | // Pass the new values up to the parent | ||
222 | if (m_parent != null) | ||
223 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | ||
224 | } | ||
225 | |||
226 | /// <summary> | ||
227 | /// Remove the rate requested by a child of this throttle. Pass the | ||
228 | /// changes up the hierarchy. | ||
229 | /// </summary> | ||
230 | public void UnregisterRequest(TokenBucket child) | ||
231 | { | ||
232 | m_children.Remove(child); | ||
233 | // m_totalDripRequest = m_children.Values.Sum(); | ||
234 | |||
235 | m_totalDripRequest = 0; | ||
236 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | ||
237 | m_totalDripRequest += cref.Value; | ||
238 | |||
239 | // Pass the new values up to the parent | ||
240 | if (m_parent != null) | ||
241 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | ||
242 | } | ||
243 | |||
244 | /// <summary> | ||
152 | /// Remove a given number of tokens from the bucket | 245 | /// Remove a given number of tokens from the bucket |
153 | /// </summary> | 246 | /// </summary> |
154 | /// <param name="amount">Number of tokens to remove from the bucket</param> | 247 | /// <param name="amount">Number of tokens to remove from the bucket</param> |
155 | /// <param name="dripSucceeded">True if tokens were added to the bucket | ||
156 | /// during this call, otherwise false</param> | ||
157 | /// <returns>True if the requested number of tokens were removed from | 248 | /// <returns>True if the requested number of tokens were removed from |
158 | /// the bucket, otherwise false</returns> | 249 | /// the bucket, otherwise false</returns> |
159 | public bool RemoveTokens(int amount, out bool dripSucceeded) | 250 | public bool RemoveTokens(Int64 amount) |
160 | { | 251 | { |
161 | if (maxBurst == 0) | 252 | // Deposit tokens for this interval |
253 | Drip(); | ||
254 | |||
255 | // If we have enough tokens then remove them and return | ||
256 | if (m_tokenCount - amount >= 0) | ||
162 | { | 257 | { |
163 | dripSucceeded = true; | 258 | // we don't have to remove from the parent, the drip rate is already |
259 | // reflective of the drip rate limits in the parent | ||
260 | m_tokenCount -= amount; | ||
164 | return true; | 261 | return true; |
165 | } | 262 | } |
166 | 263 | ||
167 | dripSucceeded = Drip(); | 264 | return false; |
265 | } | ||
168 | 266 | ||
169 | if (content - amount >= 0) | 267 | /// <summary> |
170 | { | 268 | /// Deposit tokens into the bucket from a child bucket that did |
171 | if (parent != null && !parent.RemoveTokens(amount)) | 269 | /// not use all of its available tokens |
172 | return false; | 270 | /// </summary> |
271 | private void Deposit(Int64 count) | ||
272 | { | ||
273 | m_tokenCount += count; | ||
173 | 274 | ||
174 | content -= amount; | 275 | // Deposit the overflow in the parent bucket, this is how we share |
175 | return true; | 276 | // unused bandwidth |
176 | } | 277 | Int64 burstrate = BurstRate; |
177 | else | 278 | if (m_tokenCount > burstrate) |
178 | { | 279 | m_tokenCount = burstrate; |
179 | return false; | ||
180 | } | ||
181 | } | 280 | } |
182 | 281 | ||
183 | /// <summary> | 282 | /// <summary> |
@@ -186,37 +285,29 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
186 | /// call to Drip | 285 | /// call to Drip |
187 | /// </summary> | 286 | /// </summary> |
188 | /// <returns>True if tokens were added to the bucket, otherwise false</returns> | 287 | /// <returns>True if tokens were added to the bucket, otherwise false</returns> |
189 | public bool Drip() | 288 | private void Drip() |
190 | { | 289 | { |
191 | if (tokensPerMS == 0) | 290 | // This should never happen... means we are a leaf node and were created |
291 | // with no drip rate... | ||
292 | if (DripRate == 0) | ||
192 | { | 293 | { |
193 | content = maxBurst; | 294 | m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0"); |
194 | return true; | 295 | return; |
195 | } | 296 | } |
196 | else | 297 | |
197 | { | 298 | // Determine the interval over which we are adding tokens, never add |
198 | int now = Environment.TickCount & Int32.MaxValue; | 299 | // more than a single quantum of tokens |
199 | int deltaMS = now - lastDrip; | 300 | Int32 now = Environment.TickCount & Int32.MaxValue; |
301 | Int32 deltaMS = Math.Min(now - m_lastDrip, m_ticksPerQuantum); | ||
200 | 302 | ||
201 | if (deltaMS <= 0) | 303 | m_lastDrip = now; |
202 | { | ||
203 | if (deltaMS < 0) | ||
204 | lastDrip = now; | ||
205 | return false; | ||
206 | } | ||
207 | 304 | ||
208 | int dripAmount = deltaMS * tokensPerMS; | 305 | // This can be 0 in the very unusual case that the timer wrapped |
306 | // It can be 0 if we try add tokens at a sub-tick rate | ||
307 | if (deltaMS <= 0) | ||
308 | return; | ||
209 | 309 | ||
210 | content = Math.Min(content + dripAmount, maxBurst); | 310 | Deposit(deltaMS * DripRate / m_ticksPerQuantum); |
211 | lastDrip = now; | ||
212 | |||
213 | if (dripAmount < 0 || content < 0) | ||
214 | // sim has been idle for too long, integer has overflown | ||
215 | // previous calculation is meaningless, let's put it at correct max | ||
216 | content = maxBurst; | ||
217 | |||
218 | return true; | ||
219 | } | ||
220 | } | 311 | } |
221 | } | 312 | } |
222 | } | 313 | } |