diff options
Diffstat (limited to 'OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs')
-rw-r--r-- | OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs | 292 |
1 files changed, 181 insertions, 111 deletions
diff --git a/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs b/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs index 4c33db5..4616203 100644 --- a/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs +++ b/OpenSim/Region/ClientStack/Linden/UDP/TokenBucket.cs | |||
@@ -1,4 +1,4 @@ | |||
1 | /* | 1 | /* |
2 | * Copyright (c) Contributors, http://opensimulator.org/ | 2 | * Copyright (c) Contributors, http://opensimulator.org/ |
3 | * See CONTRIBUTORS.TXT for a full list of copyright holders. | 3 | * See CONTRIBUTORS.TXT for a full list of copyright holders. |
4 | * | 4 | * |
@@ -42,9 +42,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
42 | public class TokenBucket | 42 | public class TokenBucket |
43 | { | 43 | { |
44 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); | 44 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); |
45 | private static Int32 m_counter = 0; | 45 | |
46 | 46 | public string Identifier { get; private set; } | |
47 | // private Int32 m_identifier; | 47 | |
48 | public int DebugLevel { get; set; } | ||
48 | 49 | ||
49 | /// <summary> | 50 | /// <summary> |
50 | /// Number of ticks (ms) per quantum, drip rate and max burst | 51 | /// Number of ticks (ms) per quantum, drip rate and max burst |
@@ -60,7 +61,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
60 | 61 | ||
61 | /// <summary> | 62 | /// <summary> |
62 | /// </summary> | 63 | /// </summary> |
63 | protected const Int32 m_minimumDripRate = 1400; | 64 | protected const Int32 m_minimumDripRate = LLUDPServer.MTU; |
64 | 65 | ||
65 | /// <summary>Time of the last drip, in system ticks</summary> | 66 | /// <summary>Time of the last drip, in system ticks</summary> |
66 | protected Int32 m_lastDrip; | 67 | protected Int32 m_lastDrip; |
@@ -75,20 +76,13 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
75 | /// Map of children buckets and their requested maximum burst rate | 76 | /// Map of children buckets and their requested maximum burst rate |
76 | /// </summary> | 77 | /// </summary> |
77 | protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>(); | 78 | protected Dictionary<TokenBucket,Int64> m_children = new Dictionary<TokenBucket,Int64>(); |
78 | |||
79 | #region Properties | ||
80 | 79 | ||
81 | /// <summary> | 80 | /// <summary> |
82 | /// The parent bucket of this bucket, or null if this bucket has no | 81 | /// The parent bucket of this bucket, or null if this bucket has no |
83 | /// parent. The parent bucket will limit the aggregate bandwidth of all | 82 | /// parent. The parent bucket will limit the aggregate bandwidth of all |
84 | /// of its children buckets | 83 | /// of its children buckets |
85 | /// </summary> | 84 | /// </summary> |
86 | protected TokenBucket m_parent; | 85 | public TokenBucket Parent { get; protected set; } |
87 | public TokenBucket Parent | ||
88 | { | ||
89 | get { return m_parent; } | ||
90 | set { m_parent = value; } | ||
91 | } | ||
92 | 86 | ||
93 | /// <summary> | 87 | /// <summary> |
94 | /// Maximum burst rate in bytes per second. This is the maximum number | 88 | /// Maximum burst rate in bytes per second. This is the maximum number |
@@ -114,77 +108,106 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
114 | } | 108 | } |
115 | 109 | ||
116 | /// <summary> | 110 | /// <summary> |
117 | /// The speed limit of this bucket in bytes per second. This is the | 111 | /// The requested drip rate for this particular bucket. |
118 | /// number of tokens that are added to the bucket per quantum | ||
119 | /// </summary> | 112 | /// </summary> |
120 | /// <remarks>Tokens are added to the bucket any time | 113 | /// <remarks> |
114 | /// 0 then TotalDripRequest is used instead. | ||
115 | /// Can never be above MaxDripRate. | ||
116 | /// Tokens are added to the bucket at any time | ||
121 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of | 117 | /// <seealso cref="RemoveTokens"/> is called, at the granularity of |
122 | /// the system tick interval (typically around 15-22ms)</remarks> | 118 | /// the system tick interval (typically around 15-22ms) |
123 | protected Int64 m_dripRate; | 119 | /// FIXME: It is extremely confusing to be able to set a RequestedDripRate of 0 and then receive a positive |
120 | /// number on get if TotalDripRequest is set. This also stops us being able to retrieve the fact that | ||
121 | /// RequestedDripRate is set to 0. Really, this should always return m_dripRate and then we can get | ||
122 | /// (m_dripRate == 0 ? TotalDripRequest : m_dripRate) on some other properties. | ||
123 | /// </remarks> | ||
124 | public virtual Int64 RequestedDripRate | 124 | public virtual Int64 RequestedDripRate |
125 | { | 125 | { |
126 | get { return (m_dripRate == 0 ? m_totalDripRequest : m_dripRate); } | 126 | get { return (m_dripRate == 0 ? TotalDripRequest : m_dripRate); } |
127 | set { | 127 | set |
128 | m_dripRate = (value < 0 ? 0 : value); | 128 | { |
129 | if (value <= 0) | ||
130 | m_dripRate = 0; | ||
131 | else if (MaxDripRate > 0 && value > MaxDripRate) | ||
132 | m_dripRate = MaxDripRate; | ||
133 | else | ||
134 | m_dripRate = value; | ||
135 | |||
129 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); | 136 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); |
130 | m_totalDripRequest = m_dripRate; | 137 | |
131 | if (m_parent != null) | 138 | if (Parent != null) |
132 | m_parent.RegisterRequest(this,m_dripRate); | 139 | Parent.RegisterRequest(this, m_dripRate); |
133 | } | 140 | } |
134 | } | 141 | } |
135 | 142 | ||
143 | /// <summary> | ||
144 | /// Gets the drip rate. | ||
145 | /// </summary> | ||
146 | /// <value> | ||
147 | /// DripRate can never be above max drip rate or below min drip rate. | ||
148 | /// If we are a child bucket then the drip rate return is modifed by the total load on the capacity of the | ||
149 | /// parent bucket. | ||
150 | /// </value> | ||
136 | public virtual Int64 DripRate | 151 | public virtual Int64 DripRate |
137 | { | 152 | { |
138 | get { | 153 | get |
139 | if (m_parent == null) | 154 | { |
140 | return Math.Min(RequestedDripRate,TotalDripRequest); | 155 | double rate; |
141 | 156 | ||
142 | double rate = (double)RequestedDripRate * m_parent.DripRateModifier(); | 157 | // FIXME: This doesn't properly work if we have a parent and children and a requested drip rate set |
158 | // on ourselves which is not equal to the child drip rates. | ||
159 | if (Parent == null) | ||
160 | { | ||
161 | if (TotalDripRequest > 0) | ||
162 | rate = Math.Min(RequestedDripRate, TotalDripRequest); | ||
163 | else | ||
164 | rate = RequestedDripRate; | ||
165 | } | ||
166 | else | ||
167 | { | ||
168 | rate = (double)RequestedDripRate * Parent.DripRateModifier(); | ||
169 | } | ||
170 | |||
143 | if (rate < m_minimumDripRate) | 171 | if (rate < m_minimumDripRate) |
144 | rate = m_minimumDripRate; | 172 | rate = m_minimumDripRate; |
173 | else if (MaxDripRate > 0 && rate > MaxDripRate) | ||
174 | rate = MaxDripRate; | ||
145 | 175 | ||
146 | return (Int64)rate; | 176 | return (Int64)rate; |
147 | } | 177 | } |
148 | } | 178 | } |
179 | protected Int64 m_dripRate; | ||
180 | |||
181 | // <summary> | ||
182 | // The maximum rate for flow control. Drip rate can never be greater than this. | ||
183 | // </summary> | ||
184 | public Int64 MaxDripRate { get; set; } | ||
149 | 185 | ||
150 | /// <summary> | 186 | /// <summary> |
151 | /// The current total of the requested maximum burst rates of | 187 | /// The current total of the requested maximum burst rates of children buckets. |
152 | /// this bucket's children buckets. | ||
153 | /// </summary> | 188 | /// </summary> |
154 | protected Int64 m_totalDripRequest; | 189 | public Int64 TotalDripRequest { get; protected set; } |
155 | public Int64 TotalDripRequest | ||
156 | { | ||
157 | get { return m_totalDripRequest; } | ||
158 | set { m_totalDripRequest = value; } | ||
159 | } | ||
160 | |||
161 | #endregion Properties | ||
162 | |||
163 | #region Constructor | ||
164 | 190 | ||
165 | /// <summary> | 191 | /// <summary> |
166 | /// Default constructor | 192 | /// Default constructor |
167 | /// </summary> | 193 | /// </summary> |
194 | /// <param name="identifier">Identifier for this token bucket</param> | ||
168 | /// <param name="parent">Parent bucket if this is a child bucket, or | 195 | /// <param name="parent">Parent bucket if this is a child bucket, or |
169 | /// null if this is a root bucket</param> | 196 | /// null if this is a root bucket</param> |
170 | /// <param name="maxBurst">Maximum size of the bucket in bytes, or | 197 | /// <param name="requestedDripRate"> |
171 | /// zero if this bucket has no maximum capacity</param> | 198 | /// Requested rate that the bucket fills, in bytes per |
172 | /// <param name="dripRate">Rate that the bucket fills, in bytes per | 199 | /// second. If zero, the bucket always remains full. |
173 | /// second. If zero, the bucket always remains full</param> | 200 | /// </param> |
174 | public TokenBucket(TokenBucket parent, Int64 dripRate) | 201 | public TokenBucket(string identifier, TokenBucket parent, Int64 requestedDripRate, Int64 maxDripRate) |
175 | { | 202 | { |
176 | // m_identifier = m_counter++; | 203 | Identifier = identifier; |
177 | m_counter++; | ||
178 | 204 | ||
179 | Parent = parent; | 205 | Parent = parent; |
180 | RequestedDripRate = dripRate; | 206 | RequestedDripRate = requestedDripRate; |
181 | // TotalDripRequest = dripRate; // this will be overwritten when a child node registers | 207 | MaxDripRate = maxDripRate; |
182 | // MaxBurst = (Int64)((double)dripRate * m_quantumsPerBurst); | ||
183 | m_lastDrip = Util.EnvironmentTickCount(); | 208 | m_lastDrip = Util.EnvironmentTickCount(); |
184 | } | 209 | } |
185 | 210 | ||
186 | #endregion Constructor | ||
187 | |||
188 | /// <summary> | 211 | /// <summary> |
189 | /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning | 212 | /// Compute a modifier for the MaxBurst rate. This is 1.0, meaning |
190 | /// no modification if the requested bandwidth is less than the | 213 | /// no modification if the requested bandwidth is less than the |
@@ -195,7 +218,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
195 | protected double DripRateModifier() | 218 | protected double DripRateModifier() |
196 | { | 219 | { |
197 | Int64 driprate = DripRate; | 220 | Int64 driprate = DripRate; |
198 | return driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest; | 221 | double modifier = driprate >= TotalDripRequest ? 1.0 : (double)driprate / (double)TotalDripRequest; |
222 | |||
223 | // if (DebugLevel > 0) | ||
224 | // m_log.DebugFormat( | ||
225 | // "[TOKEN BUCKET]: Returning drip modifier {0}/{1} = {2} from {3}", | ||
226 | // driprate, TotalDripRequest, modifier, Identifier); | ||
227 | |||
228 | return modifier; | ||
199 | } | 229 | } |
200 | 230 | ||
201 | /// <summary> | 231 | /// <summary> |
@@ -217,16 +247,24 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
217 | lock (m_children) | 247 | lock (m_children) |
218 | { | 248 | { |
219 | m_children[child] = request; | 249 | m_children[child] = request; |
220 | // m_totalDripRequest = m_children.Values.Sum(); | ||
221 | 250 | ||
222 | m_totalDripRequest = 0; | 251 | TotalDripRequest = 0; |
223 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | 252 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) |
224 | m_totalDripRequest += cref.Value; | 253 | TotalDripRequest += cref.Value; |
225 | } | 254 | } |
226 | 255 | ||
227 | // Pass the new values up to the parent | 256 | // Pass the new values up to the parent |
228 | if (m_parent != null) | 257 | if (Parent != null) |
229 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | 258 | { |
259 | Int64 effectiveDripRate; | ||
260 | |||
261 | if (RequestedDripRate > 0) | ||
262 | effectiveDripRate = Math.Min(RequestedDripRate, TotalDripRequest); | ||
263 | else | ||
264 | effectiveDripRate = TotalDripRequest; | ||
265 | |||
266 | Parent.RegisterRequest(this, effectiveDripRate); | ||
267 | } | ||
230 | } | 268 | } |
231 | 269 | ||
232 | /// <summary> | 270 | /// <summary> |
@@ -238,17 +276,15 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
238 | lock (m_children) | 276 | lock (m_children) |
239 | { | 277 | { |
240 | m_children.Remove(child); | 278 | m_children.Remove(child); |
241 | // m_totalDripRequest = m_children.Values.Sum(); | ||
242 | 279 | ||
243 | m_totalDripRequest = 0; | 280 | TotalDripRequest = 0; |
244 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) | 281 | foreach (KeyValuePair<TokenBucket, Int64> cref in m_children) |
245 | m_totalDripRequest += cref.Value; | 282 | TotalDripRequest += cref.Value; |
246 | } | 283 | } |
247 | |||
248 | 284 | ||
249 | // Pass the new values up to the parent | 285 | // Pass the new values up to the parent |
250 | if (m_parent != null) | 286 | if (Parent != null) |
251 | m_parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); | 287 | Parent.RegisterRequest(this,Math.Min(RequestedDripRate, TotalDripRequest)); |
252 | } | 288 | } |
253 | 289 | ||
254 | /// <summary> | 290 | /// <summary> |
@@ -301,7 +337,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
301 | // with no drip rate... | 337 | // with no drip rate... |
302 | if (DripRate == 0) | 338 | if (DripRate == 0) |
303 | { | 339 | { |
304 | m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0"); | 340 | m_log.WarnFormat("[TOKENBUCKET] something odd is happening and drip rate is 0 for {0}", Identifier); |
305 | return; | 341 | return; |
306 | } | 342 | } |
307 | 343 | ||
@@ -321,74 +357,108 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
321 | 357 | ||
322 | public class AdaptiveTokenBucket : TokenBucket | 358 | public class AdaptiveTokenBucket : TokenBucket |
323 | { | 359 | { |
324 | // private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); | 360 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); |
361 | |||
362 | public bool AdaptiveEnabled { get; set; } | ||
325 | 363 | ||
326 | /// <summary> | 364 | /// <summary> |
327 | /// The minimum rate for flow control. Minimum drip rate is one | 365 | /// Target drip rate for this bucket. |
328 | /// packet per second. Open the throttle to 15 packets per second | ||
329 | /// or about 160kbps. | ||
330 | /// </summary> | 366 | /// </summary> |
331 | protected const Int64 m_minimumFlow = m_minimumDripRate * 15; | 367 | /// <remarks>Usually set by the client. If adaptive is enabled then throttles will increase until we reach this.</remarks> |
332 | 368 | public Int64 TargetDripRate | |
333 | // <summary> | 369 | { |
334 | // The maximum rate for flow control. Drip rate can never be | 370 | get { return m_targetDripRate; } |
335 | // greater than this. | 371 | set |
336 | // </summary> | 372 | { |
337 | protected Int64 m_maxDripRate = 0; | 373 | m_targetDripRate = Math.Max(value, m_minimumFlow); |
338 | protected Int64 MaxDripRate | 374 | } |
339 | { | ||
340 | get { return (m_maxDripRate == 0 ? m_totalDripRequest : m_maxDripRate); } | ||
341 | set { m_maxDripRate = (value == 0 ? 0 : Math.Max(value,m_minimumFlow)); } | ||
342 | } | 375 | } |
343 | 376 | protected Int64 m_targetDripRate; | |
344 | private bool m_enabled = false; | 377 | |
345 | |||
346 | // <summary> | 378 | // <summary> |
347 | // | 379 | // Adjust drip rate in response to network conditions. |
348 | // </summary> | 380 | // </summary> |
349 | public virtual Int64 AdjustedDripRate | 381 | public virtual Int64 AdjustedDripRate |
350 | { | 382 | { |
351 | get { return m_dripRate; } | 383 | get { return m_dripRate; } |
352 | set { | 384 | set |
353 | m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value,m_minimumFlow,MaxDripRate); | 385 | { |
386 | m_dripRate = OpenSim.Framework.Util.Clamp<Int64>(value, m_minimumFlow, TargetDripRate); | ||
354 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); | 387 | m_burstRate = (Int64)((double)m_dripRate * m_quantumsPerBurst); |
355 | if (m_parent != null) | 388 | |
356 | m_parent.RegisterRequest(this,m_dripRate); | 389 | if (Parent != null) |
390 | Parent.RegisterRequest(this, m_dripRate); | ||
357 | } | 391 | } |
358 | } | 392 | } |
393 | |||
394 | /// <summary> | ||
395 | /// The minimum rate for adaptive flow control. | ||
396 | /// </summary> | ||
397 | protected Int64 m_minimumFlow = 32000; | ||
359 | 398 | ||
360 | // <summary> | 399 | /// <summary> |
361 | // | 400 | /// Constructor for the AdaptiveTokenBucket class |
362 | // </summary> | 401 | /// <param name="identifier">Unique identifier for the client</param> |
363 | public AdaptiveTokenBucket(TokenBucket parent, Int64 maxDripRate, bool enabled) : base(parent,maxDripRate) | 402 | /// <param name="parent">Parent bucket in the hierarchy</param> |
403 | /// <param name="requestedDripRate"></param> | ||
404 | /// <param name="maxDripRate">The ceiling rate for adaptation</param> | ||
405 | /// <param name="minDripRate">The floor rate for adaptation</param> | ||
406 | /// </summary> | ||
407 | public AdaptiveTokenBucket(string identifier, TokenBucket parent, Int64 requestedDripRate, Int64 maxDripRate, Int64 minDripRate, bool enabled) | ||
408 | : base(identifier, parent, requestedDripRate, maxDripRate) | ||
364 | { | 409 | { |
365 | m_enabled = enabled; | 410 | AdaptiveEnabled = enabled; |
366 | 411 | ||
367 | if (m_enabled) | 412 | if (AdaptiveEnabled) |
368 | { | 413 | { |
369 | // m_log.DebugFormat("[TOKENBUCKET] Adaptive throttle enabled"); | 414 | // m_log.DebugFormat("[TOKENBUCKET]: Adaptive throttle enabled"); |
370 | MaxDripRate = maxDripRate; | 415 | m_minimumFlow = minDripRate; |
416 | TargetDripRate = m_minimumFlow; | ||
371 | AdjustedDripRate = m_minimumFlow; | 417 | AdjustedDripRate = m_minimumFlow; |
372 | } | 418 | } |
373 | } | 419 | } |
374 | 420 | ||
375 | // <summary> | 421 | /// <summary> |
376 | // | 422 | /// Reliable packets sent to the client for which we never received an ack adjust the drip rate down. |
377 | // </summary> | 423 | /// <param name="packets">Number of packets that expired without successful delivery</param> |
378 | public void ExpirePackets(Int32 count) | 424 | /// </summary> |
425 | public void ExpirePackets(Int32 packets) | ||
379 | { | 426 | { |
380 | // m_log.WarnFormat("[ADAPTIVEBUCKET] drop {0} by {1} expired packets",AdjustedDripRate,count); | 427 | if (AdaptiveEnabled) |
381 | if (m_enabled) | 428 | { |
382 | AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,count)); | 429 | if (DebugLevel > 0) |
430 | m_log.WarnFormat( | ||
431 | "[ADAPTIVEBUCKET] drop {0} by {1} expired packets for {2}", | ||
432 | AdjustedDripRate, packets, Identifier); | ||
433 | |||
434 | // AdjustedDripRate = (Int64) (AdjustedDripRate / Math.Pow(2,packets)); | ||
435 | |||
436 | // Compute the fallback solely on the rate allocated beyond the minimum, this | ||
437 | // should smooth out the fallback to the minimum rate | ||
438 | AdjustedDripRate = m_minimumFlow + (Int64) ((AdjustedDripRate - m_minimumFlow) / Math.Pow(2, packets)); | ||
439 | } | ||
383 | } | 440 | } |
384 | 441 | ||
385 | // <summary> | 442 | /// <summary> |
386 | // | 443 | /// Reliable packets acked by the client adjust the drip rate up. |
387 | // </summary> | 444 | /// <param name="packets">Number of packets successfully acknowledged</param> |
388 | public void AcknowledgePackets(Int32 count) | 445 | /// </summary> |
446 | public void AcknowledgePackets(Int32 packets) | ||
447 | { | ||
448 | if (AdaptiveEnabled) | ||
449 | AdjustedDripRate = AdjustedDripRate + packets * LLUDPServer.MTU; | ||
450 | } | ||
451 | |||
452 | /// <summary> | ||
453 | /// Adjust the minimum flow level for the adaptive throttle, this will drop adjusted | ||
454 | /// throttles back to the minimum levels | ||
455 | /// <param>minDripRate--the new minimum flow</param> | ||
456 | /// </summary> | ||
457 | public void ResetMinimumAdaptiveFlow(Int64 minDripRate) | ||
389 | { | 458 | { |
390 | if (m_enabled) | 459 | m_minimumFlow = minDripRate; |
391 | AdjustedDripRate = AdjustedDripRate + count; | 460 | TargetDripRate = m_minimumFlow; |
461 | AdjustedDripRate = m_minimumFlow; | ||
392 | } | 462 | } |
393 | } | 463 | } |
394 | } | 464 | } \ No newline at end of file |