LEFT | RIGHT |
| 1 // /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 /* |
| 3 * Copyright © 2011 Marcos Talau |
| 4 * |
| 5 * This program is free software; you can redistribute it and/or modify |
| 6 * it under the terms of the GNU General Public License version 2 as |
| 7 * published by the Free Software Foundation; |
| 8 * |
| 9 * This program is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 12 * GNU General Public License for more details. |
| 13 * |
| 14 * You should have received a copy of the GNU General Public License |
| 15 * along with this program; if not, write to the Free Software |
| 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 17 * |
| 18 * Author: Marcos Talau (talau@users.sourceforge.net) |
| 19 * |
| 20 * Thanks to: Duy Nguyen<duy@soe.ucsc.edu> by RED efforts in NS3 |
| 21 * |
| 22 * |
| 23 * This file incorporates work covered by the following copyright and·· |
| 24 * permission notice:·· |
| 25 * |
| 26 * Copyright (c) 1990-1997 Regents of the University of California. |
| 27 * All rights reserved. |
| 28 * |
| 29 * Redistribution and use in source and binary forms, with or without |
| 30 * modification, are permitted provided that the following conditions |
| 31 * are met: |
| 32 * 1. Redistributions of source code must retain the above copyright |
| 33 * notice, this list of conditions and the following disclaimer. |
| 34 * 2. Redistributions in binary form must reproduce the above copyright |
| 35 * notice, this list of conditions and the following disclaimer in the |
| 36 * documentation and/or other materials provided with the distribution. |
| 37 * 3. Neither the name of the University nor of the Laboratory may be used |
| 38 * to endorse or promote products derived from this software without |
| 39 * specific prior written permission. |
| 40 * |
| 41 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
| 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
| 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 51 * SUCH DAMAGE. |
| 52 */ |
| 53 |
| 54 /* |
| 55 * PORT NOTE: This code was ported from ns-2 (queue/red.cc). Almost all· |
| 56 * comments have also been ported from NS-2 |
| 57 */ |
| 58 |
| 59 #include "ns3/log.h" |
| 60 #include "ns3/enum.h" |
| 61 #include "ns3/uinteger.h" |
| 62 #include "ns3/double.h" |
| 63 #include "ns3/simulator.h" |
| 64 #include "ns3/abort.h" |
| 65 #include "red-queue-disc.h" |
| 66 #include "ns3/drop-tail-queue.h" |
| 67 |
| 68 namespace ns3 { |
| 69 |
| 70 NS_LOG_COMPONENT_DEFINE ("RedQueueDisc"); |
| 71 |
| 72 NS_OBJECT_ENSURE_REGISTERED (RedQueueDisc); |
| 73 |
| 74 TypeId RedQueueDisc::GetTypeId (void) |
| 75 { |
| 76 static TypeId tid = TypeId ("ns3::RedQueueDisc") |
| 77 .SetParent<QueueDisc> () |
| 78 .SetGroupName("TrafficControl") |
| 79 .AddConstructor<RedQueueDisc> () |
| 80 .AddAttribute ("Mode", |
| 81 "Determines unit for QueueLimit", |
| 82 EnumValue (Queue::QUEUE_MODE_PACKETS), |
| 83 MakeEnumAccessor (&RedQueueDisc::SetMode), |
| 84 MakeEnumChecker (Queue::QUEUE_MODE_BYTES, "QUEUE_MODE_BYTES", |
| 85 Queue::QUEUE_MODE_PACKETS, "QUEUE_MODE_PACKE
TS")) |
| 86 .AddAttribute ("MeanPktSize", |
| 87 "Average of packet size", |
| 88 UintegerValue (500), |
| 89 MakeUintegerAccessor (&RedQueueDisc::m_meanPktSize), |
| 90 MakeUintegerChecker<uint32_t> ()) |
| 91 .AddAttribute ("IdlePktSize", |
| 92 "Average packet size used during idle times. Used when m_caut
ions = 3", |
| 93 UintegerValue (0), |
| 94 MakeUintegerAccessor (&RedQueueDisc::m_idlePktSize), |
| 95 MakeUintegerChecker<uint32_t> ()) |
| 96 .AddAttribute ("Wait", |
| 97 "True for waiting between dropped packets", |
| 98 BooleanValue (true), |
| 99 MakeBooleanAccessor (&RedQueueDisc::m_isWait), |
| 100 MakeBooleanChecker ()) |
| 101 .AddAttribute ("Gentle", |
| 102 "True to increases dropping probability slowly when average q
ueue exceeds maxthresh", |
| 103 BooleanValue (true), |
| 104 MakeBooleanAccessor (&RedQueueDisc::m_isGentle), |
| 105 MakeBooleanChecker ()) |
| 106 .AddAttribute ("ARED", |
| 107 "True to enable ARED", |
| 108 BooleanValue (false), |
| 109 MakeBooleanAccessor (&RedQueueDisc::m_isARED), |
| 110 MakeBooleanChecker ()) |
| 111 .AddAttribute ("AdaptMaxP", |
| 112 "True to adapt m_curMaxP", |
| 113 BooleanValue (false), |
| 114 MakeBooleanAccessor (&RedQueueDisc::m_isAdaptMaxP), |
| 115 MakeBooleanChecker ()) |
| 116 .AddAttribute ("MinTh", |
| 117 "Minimum average length threshold in packets/bytes", |
| 118 DoubleValue (5), |
| 119 MakeDoubleAccessor (&RedQueueDisc::m_minTh), |
| 120 MakeDoubleChecker<double> ()) |
| 121 .AddAttribute ("MaxTh", |
| 122 "Maximum average length threshold in packets/bytes", |
| 123 DoubleValue (15), |
| 124 MakeDoubleAccessor (&RedQueueDisc::m_maxTh), |
| 125 MakeDoubleChecker<double> ()) |
| 126 .AddAttribute ("QueueLimit", |
| 127 "Queue limit in bytes/packets", |
| 128 UintegerValue (25), |
| 129 MakeUintegerAccessor (&RedQueueDisc::SetQueueLimit), |
| 130 MakeUintegerChecker<uint32_t> ()) |
| 131 .AddAttribute ("QW", |
| 132 "Queue weight related to the exponential weighted moving aver
age (EWMA)", |
| 133 DoubleValue (0.002), |
| 134 MakeDoubleAccessor (&RedQueueDisc::m_qW), |
| 135 MakeDoubleChecker <double> ()) |
| 136 .AddAttribute ("LInterm", |
| 137 "The maximum probability of dropping a packet", |
| 138 DoubleValue (50), |
| 139 MakeDoubleAccessor (&RedQueueDisc::m_lInterm), |
| 140 MakeDoubleChecker <double> ()) |
| 141 .AddAttribute ("TargetDelay", |
| 142 "Target average queuing delay in ARED", |
| 143 TimeValue (Seconds (0.005)), |
| 144 MakeTimeAccessor (&RedQueueDisc::m_targetDelay), |
| 145 MakeTimeChecker ()) |
| 146 .AddAttribute ("Interval", |
| 147 "Time interval to update m_curMaxP", |
| 148 TimeValue (Seconds (0.5)), |
| 149 MakeTimeAccessor (&RedQueueDisc::m_interval), |
| 150 MakeTimeChecker ()) |
| 151 .AddAttribute ("Top", |
| 152 "Upper bound for m_curMaxP in ARED", |
| 153 DoubleValue (0.5), |
| 154 MakeDoubleAccessor (&RedQueueDisc::m_top), |
| 155 MakeDoubleChecker <double> (0, 1)) |
| 156 .AddAttribute ("Bottom", |
| 157 "Lower bound for m_curMaxP in ARED", |
| 158 DoubleValue (0.0), |
| 159 MakeDoubleAccessor (&RedQueueDisc::m_bottom), |
| 160 MakeDoubleChecker <double> (0, 1)) |
| 161 .AddAttribute ("Alpha", |
| 162 "Increment parameter for m_curMaxP in ARED", |
| 163 DoubleValue (0.01), |
| 164 MakeDoubleAccessor (&RedQueueDisc::SetAredAlpha), |
| 165 MakeDoubleChecker <double> (0, 1)) |
| 166 .AddAttribute ("Beta", |
| 167 "Decrement parameter for m_curMaxP in ARED", |
| 168 DoubleValue (0.9), |
| 169 MakeDoubleAccessor (&RedQueueDisc::SetAredBeta), |
| 170 MakeDoubleChecker <double> (0, 1)) |
| 171 .AddAttribute ("LastSet", |
| 172 "Store the last time m_curMaxP was updated", |
| 173 TimeValue (Seconds (0.0)), |
| 174 MakeTimeAccessor (&RedQueueDisc::m_lastSet), |
| 175 MakeTimeChecker ()) |
| 176 .AddAttribute ("Rtt", |
| 177 "Round Trip Time to be considered while automatically setting
m_bottom", |
| 178 TimeValue (Seconds (0.1)), |
| 179 MakeTimeAccessor (&RedQueueDisc::m_rtt), |
| 180 MakeTimeChecker ()) |
| 181 .AddAttribute ("Ns1Compat", |
| 182 "NS-1 compatibility", |
| 183 BooleanValue (false), |
| 184 MakeBooleanAccessor (&RedQueueDisc::m_isNs1Compat), |
| 185 MakeBooleanChecker ()) |
| 186 .AddAttribute ("LinkBandwidth",· |
| 187 "The RED link bandwidth", |
| 188 DataRateValue (DataRate ("1.5Mbps")), |
| 189 MakeDataRateAccessor (&RedQueueDisc::m_linkBandwidth), |
| 190 MakeDataRateChecker ()) |
| 191 .AddAttribute ("LinkDelay",· |
| 192 "The RED link delay", |
| 193 TimeValue (MilliSeconds (20)), |
| 194 MakeTimeAccessor (&RedQueueDisc::m_linkDelay), |
| 195 MakeTimeChecker ()) |
| 196 .AddAttribute ("UseEcn", |
| 197 "Checks if queue-disc is ECN Capable", |
| 198 BooleanValue (false), |
| 199 MakeBooleanAccessor (&RedQueueDisc::m_useEcn), |
| 200 MakeBooleanChecker ()) |
| 201 ; |
| 202 |
| 203 return tid; |
| 204 } |
| 205 |
| 206 RedQueueDisc::RedQueueDisc () : |
| 207 QueueDisc () |
| 208 { |
| 209 NS_LOG_FUNCTION (this); |
| 210 m_uv = CreateObject<UniformRandomVariable> (); |
| 211 } |
| 212 |
| 213 RedQueueDisc::~RedQueueDisc () |
| 214 { |
| 215 NS_LOG_FUNCTION (this); |
| 216 } |
| 217 |
| 218 void |
| 219 RedQueueDisc::DoDispose (void) |
| 220 { |
| 221 NS_LOG_FUNCTION (this); |
| 222 m_uv = 0; |
| 223 QueueDisc::DoDispose (); |
| 224 } |
| 225 |
| 226 void |
| 227 RedQueueDisc::SetMode (Queue::QueueMode mode) |
| 228 { |
| 229 NS_LOG_FUNCTION (this << mode); |
| 230 m_mode = mode; |
| 231 } |
| 232 |
| 233 Queue::QueueMode |
| 234 RedQueueDisc::GetMode (void) |
| 235 { |
| 236 NS_LOG_FUNCTION (this); |
| 237 return m_mode; |
| 238 } |
| 239 |
| 240 void |
| 241 RedQueueDisc::SetAredAlpha (double alpha) |
| 242 { |
| 243 NS_LOG_FUNCTION (this << alpha); |
| 244 m_alpha = alpha; |
| 245 |
| 246 if (m_alpha > 0.01) |
| 247 { |
| 248 NS_LOG_WARN ("Alpha value is above the recommended bound!"); |
| 249 } |
| 250 } |
| 251 |
| 252 double |
| 253 RedQueueDisc::GetAredAlpha (void) |
| 254 { |
| 255 NS_LOG_FUNCTION (this); |
| 256 return m_alpha; |
| 257 } |
| 258 |
| 259 void |
| 260 RedQueueDisc::SetAredBeta (double beta) |
| 261 { |
| 262 NS_LOG_FUNCTION (this << beta); |
| 263 m_beta = beta; |
| 264 |
| 265 if (m_beta < 0.83) |
| 266 { |
| 267 NS_LOG_WARN ("Beta value is below the recommended bound!"); |
| 268 } |
| 269 } |
| 270 |
| 271 double |
| 272 RedQueueDisc::GetAredBeta (void) |
| 273 { |
| 274 NS_LOG_FUNCTION (this); |
| 275 return m_beta; |
| 276 } |
| 277 |
| 278 void |
| 279 RedQueueDisc::SetQueueLimit (uint32_t lim) |
| 280 { |
| 281 NS_LOG_FUNCTION (this << lim); |
| 282 m_queueLimit = lim; |
| 283 } |
| 284 |
| 285 void |
| 286 RedQueueDisc::SetTh (double minTh, double maxTh) |
| 287 { |
| 288 NS_LOG_FUNCTION (this << minTh << maxTh); |
| 289 NS_ASSERT (minTh <= maxTh); |
| 290 m_minTh = minTh; |
| 291 m_maxTh = maxTh; |
| 292 } |
| 293 |
| 294 RedQueueDisc::Stats |
| 295 RedQueueDisc::GetStats () |
| 296 { |
| 297 NS_LOG_FUNCTION (this); |
| 298 return m_stats; |
| 299 } |
| 300 |
| 301 int64_t· |
| 302 RedQueueDisc::AssignStreams (int64_t stream) |
| 303 { |
| 304 NS_LOG_FUNCTION (this << stream); |
| 305 m_uv->SetStream (stream); |
| 306 return 1; |
| 307 } |
| 308 |
| 309 bool |
| 310 RedQueueDisc::DoEnqueue (Ptr<QueueDiscItem> item) |
| 311 { |
| 312 NS_LOG_FUNCTION (this << item); |
| 313 |
| 314 uint32_t nQueued = 0; |
| 315 |
| 316 if (GetMode () == Queue::QUEUE_MODE_BYTES) |
| 317 { |
| 318 NS_LOG_DEBUG ("Enqueue in bytes mode"); |
| 319 nQueued = GetInternalQueue (0)->GetNBytes (); |
| 320 } |
| 321 else if (GetMode () == Queue::QUEUE_MODE_PACKETS) |
| 322 { |
| 323 NS_LOG_DEBUG ("Enqueue in packets mode"); |
| 324 nQueued = GetInternalQueue (0)->GetNPackets (); |
| 325 } |
| 326 |
| 327 // simulate number of packets arrival during idle period |
| 328 uint32_t m = 0; |
| 329 |
| 330 if (m_idle == 1) |
| 331 { |
| 332 NS_LOG_DEBUG ("RED Queue Disc is idle."); |
| 333 Time now = Simulator::Now (); |
| 334 |
| 335 if (m_cautious == 3) |
| 336 { |
| 337 double ptc = m_ptc * m_meanPktSize / m_idlePktSize; |
| 338 m = uint32_t (ptc * (now - m_idleTime).GetSeconds ()); |
| 339 } |
| 340 else |
| 341 { |
| 342 m = uint32_t (m_ptc * (now - m_idleTime).GetSeconds ()); |
| 343 } |
| 344 |
| 345 m_idle = 0; |
| 346 } |
| 347 |
| 348 m_qAvg = Estimator (nQueued, m + 1, m_qAvg, m_qW); |
| 349 |
| 350 NS_LOG_DEBUG ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes () << "\t
Qavg " << m_qAvg); |
| 351 NS_LOG_DEBUG ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets () <<
"\tQavg " << m_qAvg); |
| 352 |
| 353 m_count++; |
1 m_countBytes += item->GetPacketSize (); | 354 m_countBytes += item->GetPacketSize (); |
2 | 355 |
3 uint32_t dropType = DTYPE_NONE; | 356 uint32_t dropType = DTYPE_NONE; |
4 if (m_qAvg >= m_minTh && nQueued > 1) | 357 if (m_qAvg >= m_minTh && nQueued > 1) |
5 { | 358 { |
6 if ((!m_isGentle && m_qAvg >= m_maxTh) || | 359 if ((!m_isGentle && m_qAvg >= m_maxTh) || |
7 (m_isGentle && m_qAvg >= 2 * m_maxTh)) | 360 (m_isGentle && m_qAvg >= 2 * m_maxTh)) |
8 { | 361 { |
9 NS_LOG_DEBUG ("adding DROP FORCED MARK"); | 362 NS_LOG_DEBUG ("adding DROP FORCED MARK"); |
10 dropType = DTYPE_FORCED; | 363 dropType = DTYPE_FORCED; |
11 } | 364 } |
12 else if (m_old == 0) | 365 else if (m_old == 0) |
| 366 { |
| 367 /*· |
| 368 * The average queue size has just crossed the |
| 369 * threshold from below to above "minthresh", or |
| 370 * from above "minthresh" with an empty queue to |
| 371 * above "minthresh" with a nonempty queue. |
| 372 */ |
| 373 m_count = 1; |
| 374 m_countBytes = item->GetPacketSize (); |
| 375 m_old = 1; |
| 376 } |
| 377 else if (DropEarly (item, nQueued)) |
| 378 { |
| 379 NS_LOG_LOGIC ("DropEarly returns 1"); |
| 380 dropType = DTYPE_UNFORCED; |
| 381 } |
| 382 } |
| 383 else· |
| 384 { |
| 385 // No packets are being dropped |
| 386 m_vProb = 0.0; |
| 387 m_old = 0; |
| 388 } |
| 389 |
| 390 if ((GetMode () == Queue::QUEUE_MODE_PACKETS && nQueued >= m_queueLimit) || |
| 391 (GetMode () == Queue::QUEUE_MODE_BYTES && nQueued + item->GetPacketSize()
> m_queueLimit)) |
| 392 { |
| 393 NS_LOG_DEBUG ("\t Dropping due to Queue Full " << nQueued); |
| 394 dropType = DTYPE_FORCED; |
| 395 m_stats.qLimDrop++; |
| 396 } |
| 397 |
| 398 if (dropType == DTYPE_UNFORCED) |
| 399 { |
| 400 if (m_useEcn && item->Mark ()) |
| 401 { |
| 402 NS_LOG_DEBUG ("\t Marking due to Prob Mark " << m_qAvg); |
| 403 m_stats.unforcedMark++; |
| 404 } |
| 405 else |
| 406 { |
| 407 NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qAvg); |
| 408 m_stats.unforcedDrop++; |
| 409 Drop (item); |
| 410 return false; |
| 411 } |
| 412 } |
| 413 else if (dropType == DTYPE_FORCED) |
| 414 { |
| 415 NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qAvg); |
| 416 m_stats.forcedDrop++; |
| 417 Drop (item); |
| 418 if (m_isNs1Compat) |
| 419 { |
| 420 m_count = 0; |
| 421 m_countBytes = 0; |
| 422 } |
| 423 return false; |
| 424 } |
| 425 |
| 426 bool retval = GetInternalQueue (0)->Enqueue (item); |
| 427 |
| 428 if (!retval) |
| 429 { |
| 430 m_stats.qLimDrop++; |
| 431 } |
| 432 |
| 433 // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue |
| 434 // because QueueDisc::AddInternalQueue sets the drop callback |
| 435 |
| 436 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ()); |
| 437 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ()); |
| 438 |
| 439 return retval;· |
| 440 } |
| 441 |
| 442 /* |
| 443 * Note: if the link bandwidth changes in the course of the |
| 444 * simulation, the bandwidth-dependent RED parameters do not change. |
| 445 * This should be fixed, but it would require some extra parameters, |
| 446 * and didn't seem worth the trouble... |
| 447 */ |
| 448 void |
| 449 RedQueueDisc::InitializeParams (void) |
| 450 { |
| 451 NS_LOG_FUNCTION (this); |
| 452 NS_LOG_INFO ("Initializing RED params."); |
| 453 |
| 454 m_cautious = 0; |
| 455 m_ptc = m_linkBandwidth.GetBitRate () / (8.0 * m_meanPktSize); |
| 456 |
| 457 if (m_isARED) |
| 458 { |
| 459 // Set m_minTh, m_maxTh and m_qW to zero for automatic setting |
| 460 m_minTh = 0; |
| 461 m_maxTh = 0; |
| 462 m_qW = 0; |
| 463 |
| 464 // Turn on m_isAdaptMaxP to adapt m_curMaxP |
| 465 m_isAdaptMaxP = true; |
| 466 } |
| 467 |
| 468 if (m_minTh == 0 && m_maxTh == 0) |
| 469 { |
| 470 m_minTh = 5.0; |
| 471 |
| 472 // set m_minTh to max(m_minTh, targetqueue/2.0) [Ref: http://www.icir.org/
floyd/papers/adaptiveRed.pdf] |
| 473 double targetqueue = m_targetDelay.GetSeconds() * m_ptc; |
| 474 |
| 475 if (m_minTh < targetqueue / 2.0 ) |
| 476 { |
| 477 m_minTh = targetqueue / 2.0; |
| 478 } |
| 479 if (GetMode () == Queue::QUEUE_MODE_BYTES) |
| 480 { |
| 481 m_minTh = m_minTh * m_meanPktSize; |
| 482 } |
| 483 |
| 484 // set m_maxTh to three times m_minTh [Ref: http://www.icir.org/floyd/pape
rs/adaptiveRed.pdf] |
| 485 m_maxTh = 3 * m_minTh; |
| 486 } |
| 487 |
| 488 NS_ASSERT (m_minTh <= m_maxTh); |
| 489 m_stats.forcedDrop = 0; |
| 490 m_stats.unforcedDrop = 0; |
| 491 m_stats.qLimDrop = 0; |
| 492 m_stats.unforcedMark = 0; |
| 493 |
| 494 m_qAvg = 0.0; |
| 495 m_count = 0; |
| 496 m_countBytes = 0; |
| 497 m_old = 0; |
| 498 m_idle = 1; |
| 499 |
| 500 double th_diff = (m_maxTh - m_minTh); |
| 501 if (th_diff == 0) |
| 502 { |
| 503 th_diff = 1.0;· |
| 504 } |
| 505 m_vA = 1.0 / th_diff; |
| 506 m_curMaxP = 1.0 / m_lInterm; |
| 507 m_vB = -m_minTh / th_diff; |
| 508 |
| 509 if (m_isGentle) |
| 510 { |
| 511 m_vC = (1.0 - m_curMaxP) / m_maxTh; |
| 512 m_vD = 2.0 * m_curMaxP - 1.0; |
| 513 } |
| 514 m_idleTime = NanoSeconds (0); |
| 515 |
| 516 /* |
| 517 * If m_qW=0, set it to a reasonable value of 1-exp(-1/C) |
| 518 * This corresponds to choosing m_qW to be of that value for |
| 519 * which the packet time constant -1/ln(1-m)qW) per default RTT· |
| 520 * of 100ms is an order of magnitude more than the link capacity, C. |
| 521 * |
| 522 * If m_qW=-1, then the queue weight is set to be a function of |
| 523 * the bandwidth and the link propagation delay. In particular,· |
| 524 * the default RTT is assumed to be three times the link delay and· |
| 525 * transmission delay, if this gives a default RTT greater than 100 ms.· |
| 526 * |
| 527 * If m_qW=-2, set it to a reasonable value of 1-exp(-10/C). |
| 528 */ |
| 529 if (m_qW == 0.0) |
| 530 { |
| 531 m_qW = 1.0 - std::exp (-1.0 / m_ptc); |
| 532 } |
| 533 else if (m_qW == -1.0) |
| 534 { |
| 535 double rtt = 3.0 * (m_linkDelay.GetSeconds () + 1.0 / m_ptc); |
| 536 |
| 537 if (rtt < 0.1) |
| 538 { |
| 539 rtt = 0.1; |
| 540 } |
| 541 m_qW = 1.0 - std::exp (-1.0 / (10 * rtt * m_ptc)); |
| 542 } |
| 543 else if (m_qW == -2.0) |
| 544 { |
| 545 m_qW = 1.0 - std::exp (-10.0 / m_ptc); |
| 546 } |
| 547 |
| 548 if (m_bottom == 0) |
| 549 { |
| 550 m_bottom = 0.01; |
| 551 // Set bottom to at most 1/W, where W is the delay-bandwidth |
| 552 // product in packets for a connection. |
| 553 // So W = m_linkBandwidth.GetBitRate () / (8.0 * m_meanPktSize * m_rtt.Get
Seconds()) |
| 554 double bottom1 = (8.0 * m_meanPktSize * m_rtt.GetSeconds()) / m_linkBandwi
dth.GetBitRate(); |
| 555 if (bottom1 < m_bottom) |
| 556 { |
| 557 m_bottom = bottom1; |
| 558 } |
| 559 } |
| 560 |
| 561 NS_LOG_DEBUG ("\tm_delay " << m_linkDelay.GetSeconds () << "; m_isWait "· |
| 562 << m_isWait << "; m_qW " << m_qW << "; m_ptc " << m
_ptc |
| 563 << "; m_minTh " << m_minTh << "; m_maxTh " << m_max
Th |
| 564 << "; m_isGentle " << m_isGentle << "; th_diff " <<
th_diff |
| 565 << "; lInterm " << m_lInterm << "; va " << m_vA <<
"; cur_max_p " |
| 566 << m_curMaxP << "; v_b " << m_vB << "; m_vC " |
| 567 << m_vC << "; m_vD " << m_vD); |
| 568 } |
| 569 |
| 570 // Update m_curMaxP to keep the average queue length within the target range. |
| 571 void |
| 572 RedQueueDisc::UpdateMaxP (double newAve, Time now) |
| 573 { |
| 574 double m_part = 0.4 * (m_maxTh - m_minTh); |
| 575 // AIMD rule to keep target Q~1/2(m_minTh + m_maxTh) |
| 576 if (newAve < m_minTh + m_part && m_curMaxP > m_bottom) |
| 577 { |
| 578 // we should increase the average queue size, so decrease m_curMaxP |
| 579 m_curMaxP = m_curMaxP * m_beta; |
| 580 m_lastSet = now; |
| 581 } |
| 582 else if (newAve > m_maxTh - m_part && m_top > m_curMaxP) |
| 583 { |
| 584 // we should decrease the average queue size, so increase m_curMaxP |
| 585 double alpha = m_alpha; |
| 586 if (alpha > 0.25 * m_curMaxP) |
| 587 { |
| 588 alpha = 0.25 * m_curMaxP; |
| 589 } |
| 590 m_curMaxP = m_curMaxP + alpha; |
| 591 m_lastSet = now; |
| 592 } |
| 593 } |
| 594 |
| 595 // Compute the average queue size |
| 596 double |
| 597 RedQueueDisc::Estimator (uint32_t nQueued, uint32_t m, double qAvg, double qW) |
| 598 { |
| 599 NS_LOG_FUNCTION (this << nQueued << m << qAvg << qW); |
| 600 |
| 601 double newAve = qAvg * pow(1.0-qW, m); |
| 602 newAve += qW * nQueued; |
| 603 |
| 604 Time now = Simulator::Now(); |
| 605 if (m_isAdaptMaxP && now > m_lastSet + m_interval) |
| 606 { |
| 607 UpdateMaxP(newAve, now); |
| 608 } |
| 609 |
| 610 return newAve; |
| 611 } |
| 612 |
| 613 // Check if packet p needs to be dropped due to probability mark |
| 614 uint32_t |
| 615 RedQueueDisc::DropEarly (Ptr<QueueDiscItem> item, uint32_t qSize) |
| 616 { |
| 617 NS_LOG_FUNCTION (this << item << qSize); |
| 618 m_vProb1 = CalculatePNew (m_qAvg, m_maxTh, m_isGentle, m_vA, m_vB, m_vC, m_vD,
m_curMaxP); |
| 619 m_vProb = ModifyP (m_vProb1, m_count, m_countBytes, m_meanPktSize, m_isWait, i
tem->GetPacketSize ()); |
| 620 |
| 621 // Drop probability is computed, pick random number and act |
| 622 if (m_cautious == 1) |
| 623 { |
| 624 /* |
| 625 * Don't drop/mark if the instantaneous queue is much below the average. |
| 626 * For experimental purposes only. |
| 627 * pkts: the number of packets arriving in 50 ms |
| 628 */ |
| 629 double pkts = m_ptc * 0.05; |
| 630 double fraction = std::pow ((1 - m_qW), pkts); |
| 631 |
| 632 if ((double) qSize < fraction * m_qAvg) |
| 633 { |
| 634 // Queue could have been empty for 0.05 seconds |
| 635 return 0; |
| 636 } |
| 637 } |
| 638 |
| 639 double u = m_uv->GetValue (); |
| 640 |
| 641 if (m_cautious == 2) |
| 642 { |
| 643 /* |
| 644 * Decrease the drop probability if the instantaneous |
| 645 * queue is much below the average. |
| 646 * For experimental purposes only. |
| 647 * pkts: the number of packets arriving in 50 ms |
| 648 */ |
| 649 double pkts = m_ptc * 0.05; |
| 650 double fraction = std::pow ((1 - m_qW), pkts); |
| 651 double ratio = qSize / (fraction * m_qAvg); |
| 652 |
| 653 if (ratio < 1.0) |
| 654 { |
| 655 u *= 1.0 / ratio; |
| 656 } |
| 657 } |
| 658 |
| 659 if (u <= m_vProb) |
| 660 { |
| 661 NS_LOG_LOGIC ("u <= m_vProb; u " << u << "; m_vProb " << m_vProb); |
| 662 |
| 663 // DROP or MARK |
| 664 m_count = 0; |
| 665 m_countBytes = 0; |
| 666 /// \todo Implement set bit to mark |
| 667 |
| 668 return 1; // drop |
| 669 } |
| 670 |
| 671 return 0; // no drop/mark |
| 672 } |
| 673 |
| 674 // Returns a probability using these function parameters for the DropEarly funti
on |
| 675 double |
| 676 RedQueueDisc::CalculatePNew (double qAvg, double maxTh, bool isGentle, double vA
, |
| 677 double vB, double vC, double vD, double maxP) |
| 678 { |
| 679 NS_LOG_FUNCTION (this << qAvg << maxTh << isGentle << vA << vB << vC << vD <<
maxP); |
| 680 double p; |
| 681 |
| 682 if (isGentle && qAvg >= maxTh) |
| 683 { |
| 684 // p ranges from maxP to 1 as the average queue |
| 685 // Size ranges from maxTh to twice maxTh |
| 686 p = vC * qAvg + vD; |
| 687 } |
| 688 else if (!isGentle && qAvg >= maxTh) |
| 689 { |
| 690 /*· |
| 691 * OLD: p continues to range linearly above max_p as |
| 692 * the average queue size ranges above th_max. |
| 693 * NEW: p is set to 1.0 |
| 694 */ |
| 695 p = 1.0; |
| 696 } |
| 697 else |
| 698 { |
| 699 /* |
| 700 * p ranges from 0 to max_p as the average queue size ranges from |
| 701 * th_min to th_max |
| 702 */ |
| 703 p = vA * qAvg + vB; |
| 704 p *= maxP; |
| 705 } |
| 706 |
| 707 if (p > 1.0) |
| 708 { |
| 709 p = 1.0; |
| 710 } |
| 711 |
| 712 return p; |
| 713 } |
| 714 |
| 715 // Returns a probability using these function parameters for the DropEarly funti
on |
| 716 double· |
| 717 RedQueueDisc::ModifyP (double p, uint32_t count, uint32_t countBytes, |
| 718 uint32_t meanPktSize, bool isWait, uint32_t size) |
| 719 { |
| 720 NS_LOG_FUNCTION (this << p << count << countBytes << meanPktSize << isWait <<
size); |
| 721 double count1 = (double) count; |
| 722 |
| 723 if (GetMode () == Queue::QUEUE_MODE_BYTES) |
| 724 { |
| 725 count1 = (double) (countBytes / meanPktSize); |
| 726 } |
| 727 |
| 728 if (isWait) |
| 729 { |
| 730 if (count1 * p < 1.0) |
| 731 { |
| 732 p = 0.0; |
| 733 } |
| 734 else if (count1 * p < 2.0) |
| 735 { |
| 736 p /= (2.0 - count1 * p); |
| 737 } |
| 738 else |
| 739 { |
| 740 p = 1.0; |
| 741 } |
| 742 } |
| 743 else |
| 744 { |
| 745 if (count1 * p < 1.0) |
| 746 { |
| 747 p /= (1.0 - count1 * p); |
| 748 } |
| 749 else |
| 750 { |
| 751 p = 1.0; |
| 752 } |
| 753 } |
| 754 |
| 755 if ((GetMode () == Queue::QUEUE_MODE_BYTES) && (p < 1.0)) |
| 756 { |
| 757 p = (p * size) / meanPktSize; |
| 758 } |
| 759 |
| 760 if (p > 1.0) |
| 761 { |
| 762 p = 1.0; |
| 763 } |
| 764 |
| 765 return p; |
| 766 } |
| 767 |
| 768 uint32_t |
| 769 RedQueueDisc::GetQueueSize (void) |
| 770 { |
| 771 NS_LOG_FUNCTION (this); |
| 772 if (GetMode () == Queue::QUEUE_MODE_BYTES) |
| 773 { |
| 774 return GetInternalQueue (0)->GetNBytes (); |
| 775 } |
| 776 else if (GetMode () == Queue::QUEUE_MODE_PACKETS) |
| 777 { |
| 778 return GetInternalQueue (0)->GetNPackets (); |
| 779 } |
| 780 else |
| 781 { |
| 782 NS_ABORT_MSG ("Unknown RED mode."); |
| 783 } |
| 784 } |
| 785 |
| 786 Ptr<QueueDiscItem> |
| 787 RedQueueDisc::DoDequeue (void) |
| 788 { |
| 789 NS_LOG_FUNCTION (this); |
| 790 |
| 791 if (GetInternalQueue (0)->IsEmpty ()) |
| 792 { |
| 793 NS_LOG_LOGIC ("Queue empty"); |
| 794 m_idle = 1; |
| 795 m_idleTime = Simulator::Now (); |
| 796 |
| 797 return 0; |
| 798 } |
| 799 else |
| 800 { |
| 801 m_idle = 0; |
| 802 Ptr<QueueDiscItem> item = StaticCast<QueueDiscItem> (GetInternalQueue (0)-
>Dequeue ()); |
| 803 |
| 804 NS_LOG_LOGIC ("Popped " << item); |
| 805 |
| 806 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ()); |
| 807 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ()); |
| 808 |
| 809 return item; |
| 810 } |
| 811 } |
| 812 |
| 813 Ptr<const QueueDiscItem> |
| 814 RedQueueDisc::DoPeek (void) const |
| 815 { |
| 816 NS_LOG_FUNCTION (this); |
| 817 if (GetInternalQueue (0)->IsEmpty ()) |
| 818 { |
| 819 NS_LOG_LOGIC ("Queue empty"); |
| 820 return 0; |
| 821 } |
| 822 |
| 823 Ptr<const QueueDiscItem> item = StaticCast<const QueueDiscItem> (GetInternalQu
eue (0)->Peek ()); |
| 824 |
| 825 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ()); |
| 826 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ()); |
| 827 |
| 828 return item; |
| 829 } |
| 830 |
| 831 bool |
| 832 RedQueueDisc::CheckConfig (void) |
| 833 { |
| 834 NS_LOG_FUNCTION (this); |
| 835 if (GetNQueueDiscClasses () > 0) |
| 836 { |
| 837 NS_LOG_ERROR ("RedQueueDisc cannot have classes"); |
| 838 return false; |
| 839 } |
| 840 |
| 841 if (GetNPacketFilters () > 0) |
| 842 { |
| 843 NS_LOG_ERROR ("RedQueueDisc cannot have packet filters"); |
| 844 return false; |
| 845 } |
| 846 |
| 847 if (GetNInternalQueues () == 0) |
| 848 { |
| 849 // create a DropTail queue |
| 850 Ptr<Queue> queue = CreateObjectWithAttributes<DropTailQueue> ("Mode", Enum
Value (m_mode)); |
| 851 if (m_mode == Queue::QUEUE_MODE_PACKETS) |
| 852 { |
| 853 queue->SetMaxPackets (m_queueLimit); |
| 854 } |
| 855 else |
| 856 { |
| 857 queue->SetMaxBytes (m_queueLimit); |
| 858 } |
| 859 AddInternalQueue (queue); |
| 860 } |
| 861 |
| 862 if (GetNInternalQueues () != 1) |
| 863 { |
| 864 NS_LOG_ERROR ("RedQueueDisc needs 1 internal queue"); |
| 865 return false; |
| 866 } |
| 867 |
| 868 if (GetInternalQueue (0)->GetMode () != m_mode) |
| 869 { |
| 870 NS_LOG_ERROR ("The mode of the provided queue does not match the mode set
on the RedQueueDisc"); |
| 871 return false; |
| 872 } |
| 873 |
| 874 if ((m_mode == Queue::QUEUE_MODE_PACKETS && GetInternalQueue (0)->GetMaxPacke
ts () < m_queueLimit) || |
| 875 (m_mode == Queue::QUEUE_MODE_BYTES && GetInternalQueue (0)->GetMaxBytes (
) < m_queueLimit)) |
| 876 { |
| 877 NS_LOG_ERROR ("The size of the internal queue is less than the queue disc
limit"); |
| 878 return false; |
| 879 } |
| 880 |
| 881 return true; |
| 882 } |
| 883 |
| 884 } // namespace ns3 |
LEFT | RIGHT |