Issue 279950043: adaptive RED implementation (Closed)
|
Created:
8 years, 5 months ago by Mohit P. Tahiliani Modified:
8 years, 1 month ago CC:
ns-3-reviews_googlegroups.com Visibility:
Public. |
DescriptionThis patch provides an implementation of Adaptive RED (ARED) in ns-3.24.
ARED algorithm is described in Sally Floyd's paper here: http://www.icir.org/floyd/papers/adaptiveRed.pdf
This implementation is a port of ns-2's adaptive RED code.
Main features of Adaptive RED Paper are:
1. Automatic Setting of QW (already implemented in ns-3; tests were not available, so have been added in this patch)
2. Automatic Setting of minTh and maxTh (implemented in this patch)
3. Adapting "maximum drop probability" (implemented in this patch)
A separate test suite has been provided (src/network/test/adaptive-red-queue-suite.cc) that contains test cases for all the features of ARED.
Two examples for ARED have been included in the patch.
Any suggestions/reviews would be much appreciated.
Thanks,
Mohit P. Tahiliani
Patch Set 1 : Adaptive RED implementation #
Total comments: 38
Patch Set 2 : Modified Adaptive RED code #
Total comments: 16
Patch Set 3 : Modified Adaptive RED code with updated Docs #Patch Set 4 : adaptive RED implementation #Patch Set 5 : adaptive RED patch for ns-3.24 with modified tests #
Total comments: 2
Patch Set 6 : Modified ARED patch with more tests #
MessagesTotal messages: 22
Some comments on the code inlined. General view on the ns-3-dev mailing list. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.cc File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:139: MakeDoubleAccessor (&RedQueue::m_targetDelay), This is a Time attribute, not a double indicating seconds https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:150: MakeDoubleChecker <double> ()) Since this is a drop probability, the range is from 0 to 1 https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:155: MakeDoubleChecker <double> ()) Also, this is a probability https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:165: MakeDoubleChecker <double> ()) Alpha and Beta have min or max values? If yes, specify them on the checker https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:471: } Is this part shared by Red and Adaptive Red? If yes ok, if not we should check the attribute https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:492: m_curMaxP = m_curMaxP * m_beta; Indentation https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:522: if (m_isAdaptive == 1 && now > m_lastSet + m_interval) Check against boolean values not integer
Sign in to reply to this message.
Two main issues I found before we can merge this: 1) the documentation file src/network/doc/queue.rst must be updated; it still says that Adaptive RED is not supported. 2) the tests may have an error that is not testing adaptive RED but just RED. I suggest some changes to the tests. https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... File src/network/examples/adaptive-red-tests.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation tests are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) If we test for good data, and "exit(1)" if the good data is not found at the end of the program, we can add this example to the "examples_to_run.py" file and test for regressions. https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... File src/network/examples/red_vs_ared.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:2: /* This file misses a copyright statement. https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:59: NS_ABORT_MSG ("Invalid queue type: Use --queueType=RED or --queueType=RED"); should be queueType=ARED https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:151: NS_LOG_UNCOND ("----------------------------\nQueue Type:" we do not use NS_LOG_UNCOND in examples; it does not display in optimized builds. If you want to always print out, use std::cout. https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... File src/network/test/red-queue-test-suite.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... src/network/test/red-queue-test-suite.cc:414: NS_TEST_EXPECT_MSG_LT (drop.test15, drop.test14, "Test 15 should have less drops than test 14"); I do not understand why the attribute "Adaptive" is not set to true if these are adaptive RED tests? Is this a mistake (setting "Mode" instead of "Adaptive")? If this is a mistake, this means that these tests were not testing adaptive RED, just RED. Maybe the tests need to be rethought if so (if they pass regardless of whether Adaptive is true or false, they are not good tests). Rather than simply checking whether the aggregate number of drops are less than one test or another, could you test explicitly for exact values, that you have validated by hand? For example, what is the exact value expected for unforcedrop, forcedDrop, and qLimDrop in all cases, and can you test for "EQ" instead of "LT"? https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.cc File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:139: MakeDoubleAccessor (&RedQueue::m_targetDelay), On 2015/12/02 09:05:07, n.p wrote: > This is a Time attribute, not a double indicating seconds I agree to avoid using double values to represent time quantities where possible. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:150: MakeDoubleChecker <double> ()) On 2015/12/02 09:05:07, n.p wrote: > Since this is a drop probability, the range is from 0 to 1 To clarify, I think Natale is saying to use MakeDoubleChecker<double> (0,1)) https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:451: // set m_minTh to half of targetqueue, if this is greater could be restated "set m_minTh to half of targetqueue, if the targetqueue is greater than 10 packets". Could also be expressed as max (minTh, targetqueue/2.0). https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:459: m_maxTh = 3 * m_minTh; please add a comment for where the value '3' comes from https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:467: // So W = 0.1 * m_linkBandwidth.GetBitRate () / 8000 just like linkBandwidth is an attribute, shouldn't also the assumed packet size and RTT be attributes? https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:470: m_bottom = bottom1; add braces around if statement (also in the above if statements)
Sign in to reply to this message.
Dear Nat and Tom Sir, Thank you very much for your time and suggestions. I have tried incorporating most of the suggestions and corrected the code accordingly. In a couple of places, I have raised a query. Please take a look when possible. Your suggestions are highly appreciated. Thank you once again. Regards, Mohit P. Tahiliani https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... File src/network/examples/red_vs_ared.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:2: /* On 2015/12/02 19:54:45, Tom Henderson wrote: > This file misses a copyright statement. Done. https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:59: NS_ABORT_MSG ("Invalid queue type: Use --queueType=RED or --queueType=RED"); On 2015/12/02 19:54:45, Tom Henderson wrote: > should be queueType=ARED Done. https://codereview.appspot.com/279950043/diff/1/src/network/examples/red_vs_a... src/network/examples/red_vs_ared.cc:151: NS_LOG_UNCOND ("----------------------------\nQueue Type:" Replaced NS_LOG_UNCOND by std::cout. This example is derived from droptail_vs_red.cc (not a part of this patch). It uses NS_LOG_UNCOND. Should I change that too? On 2015/12/02 19:54:45, Tom Henderson wrote: > we do not use NS_LOG_UNCOND in examples; it does not display in optimized > builds. If you want to always print out, use std::cout. https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... File src/network/test/red-queue-test-suite.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... src/network/test/red-queue-test-suite.cc:414: NS_TEST_EXPECT_MSG_LT (drop.test15, drop.test14, "Test 15 should have less drops than test 14"); Dear Sir, There are three main parts of Adaptive RED *paper*: 1. *Automatic* setting of QW 2. *Automatic* setting of minTh and maxTh 3. *Adaptive* setting of "maximum drop probability" The tests provided in this patch are for 1 and 2. They do not require "adaptive" to be set to true (Ref.: Our previous communication on *automatic* vs *adaptive* for ns-2). In that case, are these tests acceptable? Tests for 3 are pending. Regarding explicitly testing for values: Sure Sir, I would try to do that. On 2015/12/02 19:54:45, Tom Henderson wrote: > I do not understand why the attribute "Adaptive" is not set to true if these are > adaptive RED tests? Is this a mistake (setting "Mode" instead of "Adaptive")? > > If this is a mistake, this means that these tests were not testing adaptive RED, > just RED. Maybe the tests need to be rethought if so (if they pass regardless > of whether Adaptive is true or false, they are not good tests). > > Rather than simply checking whether the aggregate number of drops are less than > one test or another, could you test explicitly for exact values, that you have > validated by hand? For example, what is the exact value expected for > unforcedrop, forcedDrop, and qLimDrop in all cases, and can you test for "EQ" > instead of "LT"? https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.cc File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:139: MakeDoubleAccessor (&RedQueue::m_targetDelay), Done. Accordingly changed the related code in other files (red-queue.h and adaptive-red-tests.cc) On 2015/12/02 19:54:45, Tom Henderson wrote: > On 2015/12/02 09:05:07, n.p wrote: > > This is a Time attribute, not a double indicating seconds > > I agree to avoid using double values to represent time quantities where > possible. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:150: MakeDoubleChecker <double> ()) Thank you. Done. On 2015/12/02 19:54:45, Tom Henderson wrote: > On 2015/12/02 09:05:07, n.p wrote: > > Since this is a drop probability, the range is from 0 to 1 > > To clarify, I think Natale is saying to use MakeDoubleChecker<double> (0,1)) https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:155: MakeDoubleChecker <double> ()) On 2015/12/02 09:05:07, n.p wrote: > Also, this is a probability Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:165: MakeDoubleChecker <double> ()) On 2015/12/02 09:05:07, n.p wrote: > Alpha and Beta have min or max values? If yes, specify them on the checker Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:451: // set m_minTh to half of targetqueue, if this is greater On 2015/12/02 19:54:45, Tom Henderson wrote: > could be restated "set m_minTh to half of targetqueue, if the targetqueue is > greater than 10 packets". Could also be expressed as max (minTh, > targetqueue/2.0). Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:459: m_maxTh = 3 * m_minTh; On 2015/12/02 19:54:45, Tom Henderson wrote: > please add a comment for where the value '3' comes from Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:467: // So W = 0.1 * m_linkBandwidth.GetBitRate () / 8000 I ported this code from ns-2, so retained the values instead of making them as attributes. We have an attribute "meanPktSize" already, so I will change the code accordingly. I will create an attribute for RTT if that's a better approach (Note: Adaptive RED paper assumes an RTT of 100ms) Please suggest. On 2015/12/02 19:54:45, Tom Henderson wrote: > just like linkBandwidth is an attribute, shouldn't also the assumed packet size > and RTT be attributes? https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:470: m_bottom = bottom1; On 2015/12/02 19:54:45, Tom Henderson wrote: > add braces around if statement (also in the above if statements) Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:471: } Yes, it is shared. On 2015/12/02 09:05:07, n.p wrote: > Is this part shared by Red and Adaptive Red? If yes ok, if not we should check > the attribute https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:492: m_curMaxP = m_curMaxP * m_beta; On 2015/12/02 09:05:07, n.p wrote: > Indentation Done. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:522: if (m_isAdaptive == 1 && now > m_lastSet + m_interval) On 2015/12/02 09:05:07, n.p wrote: > Check against boolean values not integer Done.
Sign in to reply to this message.
Hi, as a general comment, I'd suggest to work on the documentation too. Delaying 'til the code is settled will only mean that we'll have one more round of review :) https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:160: MakeDoubleChecker <double> (0, 0.01)) Alpha value is a bit less constrained than this. From the formulas, one can "only" say that its hard limit is zero to (1-max_p), simply because the result of the max_p update formula is a probability. In order to avoid a one-step oscillation, one can update the bound to zero - (0.5-max_p), such that the update make it max_p jump to its maximum value in one step. Since doing a check with a variable parameter is not possible, my suggestion is to use MakeDoubleChecker <double> (0, 0.5) and to use a setter function. Inside the setter function, do the proper checks: a "hard" check with max_p and a warning for not using the range of values suggested by the paper. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:165: MakeDoubleChecker <double> (0.83)) For beta I can do the same comments as for alpha. Its "true" boundaries are (0,1), with 0 and 1 excluded. The paper *suggests* to use a beta greater than 0.83 (and with good arguments), but we shouldn't prevent to have a smaller value. Perhaps one could want to show the dumb students what happens when the suggestions are not followed. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:491: RedQueue::UpdateMaxP (double newAve, Time now) This should be a periodic function and *not* a function bound to the execution of Enqueue / Estimator. The difference is that in the former case the values are updated at fixed the intervals, thus the formulas are the ones of an EWMA (more or less). In the latter case (the one implemented) the values are updated aperiodically, i.e., they can be changed once in a while or very often, one doesn't know. There is a way to counterbalance this effect (i.e., time-dependent EWMA), but I don't think it can be used here, as the formulas aren't exactly EWMA. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:493: double m_part = 0.4 * (m_maxTh - m_minTh); In the paper there is a quantity called "target", and it's said that this value should be between m_minTh + 0.4 * (m_maxTh - m_minTh) and m_minTh + 0.6 * (m_maxTh - m_minTh) Please let the user set the multiplicative part (i.e., add an attribute). Also, I'd suggest to be more in-line with the paper's algorithm, it avoids mistakes... https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:501: else if (newAve > m_maxTh - m_part && m_top > m_curMaxP) .. like here. It should be else if (newAve > m_minTh + m_part && m_top > m_curMaxP) https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:507: alpha = 0.25 * m_curMaxP; In the paper you are referencing to, there's no change in alpha value whatsoever. It is a constant... https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:529: Time now = Simulator::Now(); As said before. No, not here. It should be "bootstrapped" when the queue is initialized. I'd suggest to have an EventId tracking the running event and to cancel it when the queue is destroyed (it's more than a suggestion).
Sign in to reply to this message.
Minor comments; I am now testing ARed in already existing test-scenarios, and will report problems (if found) https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.cc File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:110: MakeBooleanChecker ()) Just think on that... isn't possible to split Adaptive red in another class, using inheritance? Pro: users can differentiate AQM by just change the TypeId name (allowing, for example, to write things as: ./tcp-test --queue=ns3::RedQueue or --queue=ns3::ARedQueue) This is a more general question than related to the actual code; comments welcome. https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:467: // So W = 0.1 * m_linkBandwidth.GetBitRate () / 8000 On 2015/12/04 03:12:56, Mohit P. Tahiliani wrote: > I will create an attribute for RTT if that's a better approach (Note: Adaptive > RED paper assumes an RTT of 100ms) Please suggest. Yes, I think having RTT as attribute, as Tom suggested, is a must-have, because this way we can utilize ARed in other context, where RTT can be different. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:393: Just a minor note: please avoid inserting these whitespaces
Sign in to reply to this message.
Dear Tommaso, Sure, I will update the document now itself and ensure that it is a part of the next corrected patch. Thank you very much for the reviews. I have tried to address all of them. Kindly let me know if they are correct, when possible. Your views are much appreciated. Dear Nat, Thank you again for your time and suggestions :) Regards, Mohit P. Tahiliani https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.cc File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/utils/red-queue.c... src/network/utils/red-queue.cc:467: // So W = 0.1 * m_linkBandwidth.GetBitRate () / 8000 On 2015/12/09 08:55:54, n.p wrote: > On 2015/12/04 03:12:56, Mohit P. Tahiliani wrote: > > I will create an attribute for RTT if that's a better approach (Note: Adaptive > > RED paper assumes an RTT of 100ms) Please suggest. > > Yes, I think having RTT as attribute, as Tom suggested, is a must-have, because > this way we can utilize ARed in other context, where RTT can be different. Done. I will add an attribute for RTT and set its default value to 100ms. For packet size, I will use the existing attribute. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... File src/network/utils/red-queue.cc (right): https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:160: MakeDoubleChecker <double> (0, 0.01)) On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > Alpha value is a bit less constrained than this. > From the formulas, one can "only" say that its hard limit is zero to (1-max_p), > simply because the result of the max_p update formula is a probability. > In order to avoid a one-step oscillation, one can update the bound to zero - > (0.5-max_p), such that the update make it max_p jump to its maximum value in one > step. > > Since doing a check with a variable parameter is not possible, my suggestion is > to use MakeDoubleChecker <double> (0, 0.5) and to use a setter function. Inside > the setter function, do the proper checks: a "hard" check with max_p and a > warning for not using the range of values suggested by the paper. Algorithm in the paper (Ref.: Fig. 10 on page 6) suggests that "alpha" be set to min(0.01, max_p/4). So in any case, the value of "alpha" would not be greater than 0.01. Moreover, since upper limit on max_p itself is 0.5 and "alpha" being an increment parameter to max_p, would it be correct to use (0, 0.5) for alpha? (as you mentioned in your suggestion for beta, to explain to students we can certainly use those checks). Looking into above two points, should we retain the current check (i.e., 0 to 0.01)? Or should we consider changing it? https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:165: MakeDoubleChecker <double> (0.83)) On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > For beta I can do the same comments as for alpha. Its "true" boundaries are > (0,1), with 0 and 1 excluded. > The paper *suggests* to use a beta greater than 0.83 (and with good arguments), > but we shouldn't prevent to have a smaller value. Perhaps one could want to show > the dumb students what happens when the suggestions are not followed. So should we consider using (0, 1) for beta? If so, then Done. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:393: On 2015/12/09 08:55:54, n.p wrote: > Just a minor note: please avoid inserting these whitespaces Done. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:491: RedQueue::UpdateMaxP (double newAve, Time now) On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > This should be a periodic function and *not* a function bound to the execution > of Enqueue / Estimator. > The difference is that in the former case the values are updated at fixed the > intervals, thus the formulas are the ones of an EWMA (more or less). In the > latter case (the one implemented) the values are updated aperiodically, i.e., > they can be changed once in a while or very often, one doesn't know. > There is a way to counterbalance this effect (i.e., time-dependent EWMA), but I > don't think it can be used here, as the formulas aren't exactly EWMA. I believe this function is not intended to be periodic *always* because RED does not update *newAve* periodically. RED updates *newAve* on arrival of each packet. So if packet arrival rate is high, frequency of updating *newAve* is high. In such cases, this function is called periodically (rather than getting called as frequently as *newAve* is updated). If there are no incoming packets, *newAve* is not updated. In such cases, since *newave* doesn't change - there is no need to call this function. Also, this code is an exact port of Adaptive RED author's (Sally Flyod's) ns-2 code. In summary, I feel we should keep this function bound to the execution of Enqueue / Estimator. Please suggest. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:493: double m_part = 0.4 * (m_maxTh - m_minTh); On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > In the paper there is a quantity called "target", and it's said that this value > should be between m_minTh + 0.4 * (m_maxTh - m_minTh) and m_minTh + 0.6 * > (m_maxTh - m_minTh) > Please let the user set the multiplicative part (i.e., add an attribute). > Also, I'd suggest to be more in-line with the paper's algorithm, it avoids > mistakes... I think "target" in the paper is a "range"; not a "value". And it's lower bound is m_minTh + 0.4 * (m_maxTh - m_minTh) and upper bound is m_minTh + 0.6 * (m_maxTh - m_minTh). Author intends to keep *newAve* within this range. Example: if m_minTh = 5 and m_maxTh = 15 (i.e., 3 times of min), then target range is [9, 11]. Yes, the multiplicative part can be made open to the user for trying different values. This code is also an exact port of Sally Floyd's ns-2 code :) https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:501: else if (newAve > m_maxTh - m_part && m_top > m_curMaxP) On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > .. like here. It should be > else if (newAve > m_minTh + m_part && m_top > m_curMaxP) The condition (newAve > m_minTh + m_part) wouldn't be correct because here we need to check whether "newAve" has gone above the "target range" [i.e., beyond 0.6 * (m_maxTh - m_minTh)] If "target" was a "value" - then the suggested condition would have been correct. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:507: alpha = 0.25 * m_curMaxP; On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > In the paper you are referencing to, there's no change in alpha value > whatsoever. It is a constant... I believe it is not constant because it is set to min(0.01, max_p/4). So when max_p changes (and max_p/4 becomes lesser than 0.01), alpha would also change. https://codereview.appspot.com/279950043/diff/20001/src/network/utils/red-que... src/network/utils/red-queue.cc:529: Time now = Simulator::Now(); On 2015/12/06 14:09:04, Tommaso Pecorella wrote: > As said before. No, not here. It should be "bootstrapped" when the queue is > initialized. > I'd suggest to have an EventId tracking the running event and to cancel it when > the queue is destroyed (it's more than a suggestion). Looking into the points mentioned earlier, would be better to retain it here?
Sign in to reply to this message.
On 2015/12/09 10:11:30, Mohit P. Tahiliani wrote: > Dear Tommaso, > > Sure, I will update the document now itself and ensure that it is a part of the > next corrected patch. > Hi, is the third version of the patch available? Thank you Nat
Sign in to reply to this message.
On 2015/12/18 15:47:04, n.p wrote: > On 2015/12/09 10:11:30, Mohit P. Tahiliani wrote: > > Dear Tommaso, > > > > Sure, I will update the document now itself and ensure that it is a part of > the > > next corrected patch. > > > > Hi, > > is the third version of the patch available? > > Thank you > > Nat Hi Nat, I have completed the following so far: 1. Updated the document 2. Removed unnecessary white spaces 3. Added RTT as a new attribute I haven't posted the new patch here as I am waiting for confirmation/suggestions on: 1. Tom Sir's point about test cases 2. Tommaso Sir's suggestions If you prefer to take a look at those 3 changes made so far, I will upload the patch here and then wait for further suggestions. Please let me know. Thank you very much for your time, Nat! Regards, Mohit P. Tahiliani
Sign in to reply to this message.
On 2015/12/19 17:24:39, Mohit P. Tahiliani wrote: > 1. Updated the document > 2. Removed unnecessary white spaces > 3. Added RTT as a new attribute > > I haven't posted the new patch here as I am waiting for confirmation/suggestions > on: > > 1. Tom Sir's point about test cases > 2. Tommaso Sir's suggestions > > If you prefer to take a look at those 3 changes made so far, I will upload the > patch here and then wait for further suggestions. Please let me know. Yes, small steps at time. Thank you! Nat
Sign in to reply to this message.
On 2015/12/20 13:50:20, n.p wrote: > On 2015/12/19 17:24:39, Mohit P. Tahiliani wrote: > > 1. Updated the document > > 2. Removed unnecessary white spaces > > 3. Added RTT as a new attribute > > > > I haven't posted the new patch here as I am waiting for > confirmation/suggestions > > on: > > > > 1. Tom Sir's point about test cases > > 2. Tommaso Sir's suggestions > > > > If you prefer to take a look at those 3 changes made so far, I will upload the > > patch here and then wait for further suggestions. Please let me know. > > > Yes, small steps at time. > > Thank you! > > Nat Hi Nat, I have uploaded Patch 3 with: changes in doc, addition of new attribute for RTT and removal of unnecessary whitespaces. Please take a look when possible. Thank you very much for your valuable suggestions. Regards, Mohit P. Tahiliani
Sign in to reply to this message.
Hi Mohit,
sorry for the late round of review. This is the last thing from my side tho,
so...
I'm still unconvinced by the checks in alpha and beta. I'd actually **remove**
the checks in the Attribute part or set them to very permissive values (e.g.,
0..1).
However, I'd also change the attribute in this way:
.AddAttribute ("Alpha",
"Increment parameter for maximum drop probability in Adaptive
RED",
DoubleValue (0.01),
- MakeDoubleAccessor (&RedQueue::m_alpha),
- MakeDoubleChecker <double> (0, 0.01))
+ MakeDoubleAccessor (&RedQueue::SetAredAlpha,
&RedQueue::GetAredAlpha),
- MakeDoubleChecker <double> (0, 1))
Where SetAredAlpha and GetAredAlpha are the setter and getter for alpha. Inside
the setter you can have your checks, including warnings for out-of-logical-range
values - feel free to find better names for the functions.
The same approach can be used for beta.
In this way one can also override and blatantly violate Sally Floyd's
suggestions, and see what's happening.
Cheers,
T.
Sign in to reply to this message.
On 2015/12/26 11:19:45, Tommaso Pecorella wrote:
> Hi Mohit,
>
> sorry for the late round of review. This is the last thing from my side tho,
> so...
>
> I'm still unconvinced by the checks in alpha and beta. I'd actually **remove**
> the checks in the Attribute part or set them to very permissive values (e.g.,
> 0..1).
>
> However, I'd also change the attribute in this way:
> .AddAttribute ("Alpha",
> "Increment parameter for maximum drop probability in Adaptive
> RED",
> DoubleValue (0.01),
> - MakeDoubleAccessor (&RedQueue::m_alpha),
> - MakeDoubleChecker <double> (0, 0.01))
> + MakeDoubleAccessor (&RedQueue::SetAredAlpha,
> &RedQueue::GetAredAlpha),
> - MakeDoubleChecker <double> (0, 1))
>
> Where SetAredAlpha and GetAredAlpha are the setter and getter for alpha.
Inside
> the setter you can have your checks, including warnings for
out-of-logical-range
> values - feel free to find better names for the functions.
> The same approach can be used for beta.
>
> In this way one can also override and blatantly violate Sally Floyd's
> suggestions, and see what's happening.
>
> Cheers,
>
> T.
Hi Tommaso,
Thank you for taking out time and reviewing the patch again.
I would work on your suggestions and keep the code ready for both; alpha and
beta.
Thank you again for your time and suggestions.
Regards,
Mohit P. Tahiliani
Sign in to reply to this message.
On 2015/12/30 03:19:45, Mohit P. Tahiliani wrote:
> On 2015/12/26 11:19:45, Tommaso Pecorella wrote:
> > Hi Mohit,
> >
> > sorry for the late round of review. This is the last thing from my side tho,
> > so...
> >
> > I'm still unconvinced by the checks in alpha and beta. I'd actually
**remove**
> > the checks in the Attribute part or set them to very permissive values
(e.g.,
> > 0..1).
> >
> > However, I'd also change the attribute in this way:
> > .AddAttribute ("Alpha",
> > "Increment parameter for maximum drop probability in Adaptive
> > RED",
> > DoubleValue (0.01),
> > - MakeDoubleAccessor (&RedQueue::m_alpha),
> > - MakeDoubleChecker <double> (0, 0.01))
> > + MakeDoubleAccessor (&RedQueue::SetAredAlpha,
> > &RedQueue::GetAredAlpha),
> > - MakeDoubleChecker <double> (0, 1))
> >
> > Where SetAredAlpha and GetAredAlpha are the setter and getter for alpha.
> Inside
> > the setter you can have your checks, including warnings for
> out-of-logical-range
> > values - feel free to find better names for the functions.
> > The same approach can be used for beta.
> >
> > In this way one can also override and blatantly violate Sally Floyd's
> > suggestions, and see what's happening.
> >
> > Cheers,
> >
> > T.
>
> Hi Tommaso,
>
> Thank you for taking out time and reviewing the patch again.
>
> I would work on your suggestions and keep the code ready for both; alpha and
> beta.
>
> Thank you again for your time and suggestions.
>
> Regards,
> Mohit P. Tahiliani
Hi Mohit,
for me the code looks ok, and I'm using it in my tests without a problem (until
now).
Nat
Sign in to reply to this message.
Dear Nat, Apologies for the late response. Thank you very much for informing. I have uploaded Patch 4 and it has two changes: 1. Added adaptive-red-tests.cc to examples-to-run.py and verified whether the test passes (Ref. Tom Sir's suggestion in Patch 1). 2. Added setters and getters for alpha and beta values (Ref. Tommaso Sir's suggestion in Patch 3) Regards, Mohit P. Tahiliani https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... File src/network/examples/adaptive-red-tests.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation tests are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) On 2015/12/02 19:54:45, Tom Henderson wrote: > If we test for good data, and "exit(1)" if the good data is not found at the end > of the program, we can add this example to the "examples_to_run.py" file and > test for regressions. Done.
Sign in to reply to this message.
On 2016/01/21 16:01:19, Mohit P. Tahiliani wrote: > Dear Nat, > > Apologies for the late response. > > Thank you very much for informing. > > I have uploaded Patch 4 and it has two changes: > > 1. Added adaptive-red-tests.cc to examples-to-run.py and verified whether the > test passes (Ref. Tom Sir's suggestion in Patch 1). > > 2. Added setters and getters for alpha and beta values (Ref. Tommaso Sir's > suggestion in Patch 3) > > Regards, > Mohit P. Tahiliani > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > File src/network/examples/adaptive-red-tests.cc (right): > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation tests > are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) > On 2015/12/02 19:54:45, Tom Henderson wrote: > > If we test for good data, and "exit(1)" if the good data is not found at the > end > > of the program, we can add this example to the "examples_to_run.py" file and > > test for regressions. > > Done. Hi, I don't see the example/test verification, but I guess that it's just a problem of patch upload. T.
Sign in to reply to this message.
On 2016/01/21 16:07:07, Tommaso Pecorella wrote: > On 2016/01/21 16:01:19, Mohit P. Tahiliani wrote: > > Dear Nat, > > > > Apologies for the late response. > > > > Thank you very much for informing. > > > > I have uploaded Patch 4 and it has two changes: > > > > 1. Added adaptive-red-tests.cc to examples-to-run.py and verified whether the > > test passes (Ref. Tom Sir's suggestion in Patch 1). > > > > 2. Added setters and getters for alpha and beta values (Ref. Tommaso Sir's > > suggestion in Patch 3) > > > > Regards, > > Mohit P. Tahiliani > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > File src/network/examples/adaptive-red-tests.cc (right): > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation tests > > are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) > > On 2015/12/02 19:54:45, Tom Henderson wrote: > > > If we test for good data, and "exit(1)" if the good data is not found at the > > end > > > of the program, we can add this example to the "examples_to_run.py" file and > > > test for regressions. > > > > Done. > > Hi, > > I don't see the example/test verification, but I guess that it's just a problem > of patch upload. > > T. Indeed, I missed out one thing (exit(1) in example programs when good data is not found) in Patch 4. So I've deleted Patch 4 and uploaded a new one. Thank you very much for your time and suggestions. Regards, Mohit P. Tahiliani
Sign in to reply to this message.
On 2016/01/22 18:12:21, Mohit P. Tahiliani wrote: > On 2016/01/21 16:07:07, Tommaso Pecorella wrote: > > On 2016/01/21 16:01:19, Mohit P. Tahiliani wrote: > > > Dear Nat, > > > > > > Apologies for the late response. > > > > > > Thank you very much for informing. > > > > > > I have uploaded Patch 4 and it has two changes: > > > > > > 1. Added adaptive-red-tests.cc to examples-to-run.py and verified whether > the > > > test passes (Ref. Tom Sir's suggestion in Patch 1). > > > > > > 2. Added setters and getters for alpha and beta values (Ref. Tommaso Sir's > > > suggestion in Patch 3) > > > > > > Regards, > > > Mohit P. Tahiliani > > > > > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > > File src/network/examples/adaptive-red-tests.cc (right): > > > > > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > > src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation > tests > > > are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) > > > On 2015/12/02 19:54:45, Tom Henderson wrote: > > > > If we test for good data, and "exit(1)" if the good data is not found at > the > > > end > > > > of the program, we can add this example to the "examples_to_run.py" file > and > > > > test for regressions. > > > > > > Done. > > > > Hi, > > > > I don't see the example/test verification, but I guess that it's just a > problem > > of patch upload. > > > > T. > > Indeed, I missed out one thing (exit(1) in example programs when good data is > not found) in Patch 4. > > So I've deleted Patch 4 and uploaded a new one. > > Thank you very much for your time and suggestions. > > Regards, > Mohit P. Tahiliani I was thinking to something different... like placing this code (or similar) to the end of red_vs_ared: ---------------------------------- if (queueType == "ARED") { if (totalRxBytesCounter > 2733328) { std::cout << "ARED Goodput is too high, should be about 10181.1 Bps" << std::endl; exit (-1); } else if (totalRxBytesCounter < 2713328) { std::cout << "ARED Goodput is too low, should be about 10181.1 Bps" << std::endl; exit (-1); } } else if (queueType == "RED") { if (totalRxBytesCounter > 2715920) { std::cout << "RED Goodput is too high, should be about 10136.3 Bps" << std::endl; exit (-1); } else if (totalRxBytesCounter < 2695920) { std::cout << "RED Goodput is too low, should be about 10136.3 Bps" << std::endl; exit (-1); } } ---------------------------------- and (of course) ad it to the list of the examples to run. Twice - one for red and one for ared. Feel free to elaborate the solution also for the other tests. As a side note, checking the exact value is not a good idea, otherwise randomness could make the tests fail.
Sign in to reply to this message.
On 2016/01/24 23:58:18, Tommaso Pecorella wrote: > On 2016/01/22 18:12:21, Mohit P. Tahiliani wrote: > > On 2016/01/21 16:07:07, Tommaso Pecorella wrote: > > > On 2016/01/21 16:01:19, Mohit P. Tahiliani wrote: > > > > Dear Nat, > > > > > > > > Apologies for the late response. > > > > > > > > Thank you very much for informing. > > > > > > > > I have uploaded Patch 4 and it has two changes: > > > > > > > > 1. Added adaptive-red-tests.cc to examples-to-run.py and verified whether > > the > > > > test passes (Ref. Tom Sir's suggestion in Patch 1). > > > > > > > > 2. Added setters and getters for alpha and beta values (Ref. Tommaso Sir's > > > > suggestion in Patch 3) > > > > > > > > Regards, > > > > Mohit P. Tahiliani > > > > > > > > > > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > > > File src/network/examples/adaptive-red-tests.cc (right): > > > > > > > > > > > > > > https://codereview.appspot.com/279950043/diff/1/src/network/examples/adaptive... > > > > src/network/examples/adaptive-red-tests.cc:19: * NOTE: These validation > > tests > > > > are same as provided in ns-2 (ns/tcl/test/test-suite-adaptive-red.tcl) > > > > On 2015/12/02 19:54:45, Tom Henderson wrote: > > > > > If we test for good data, and "exit(1)" if the good data is not found at > > the > > > > end > > > > > of the program, we can add this example to the "examples_to_run.py" file > > and > > > > > test for regressions. > > > > > > > > Done. > > > > > > Hi, > > > > > > I don't see the example/test verification, but I guess that it's just a > > problem > > > of patch upload. > > > > > > T. > > > > Indeed, I missed out one thing (exit(1) in example programs when good data is > > not found) in Patch 4. > > > > So I've deleted Patch 4 and uploaded a new one. > > > > Thank you very much for your time and suggestions. > > > > Regards, > > Mohit P. Tahiliani > > I was thinking to something different... like placing this code (or similar) to > the end of red_vs_ared: > > ---------------------------------- > if (queueType == "ARED") > { > if (totalRxBytesCounter > 2733328) > { > std::cout << "ARED Goodput is too high, should be about 10181.1 Bps" > << std::endl; > exit (-1); > } > else if (totalRxBytesCounter < 2713328) > { > std::cout << "ARED Goodput is too low, should be about 10181.1 Bps" << > std::endl; > exit (-1); > } > } > else if (queueType == "RED") > { > if (totalRxBytesCounter > 2715920) > { > std::cout << "RED Goodput is too high, should be about 10136.3 Bps" << > std::endl; > exit (-1); > } > else if (totalRxBytesCounter < 2695920) > { > std::cout << "RED Goodput is too low, should be about 10136.3 Bps" << > std::endl; > exit (-1); > } > } > ---------------------------------- > > and (of course) ad it to the list of the examples to run. Twice - one for red > and one for ared. > Feel free to elaborate the solution also for the other tests. > As a side note, checking the exact value is not a good idea, otherwise > randomness could make the tests fail. Thank you very much for the example :) I have incorporated the suggestions accordingly in both the example files: red_vs_ared.cc and adaptive-red-tests.cc Also modified examples-to-run.py to test these two examples with different input values. I wanted to verify the following: - checking is not done with exact values as recommended. - values used for checking are obtained by running the same example with same input for different values of RngRun (1 to 10). E.g.: red_vs_ared.cc was executed with RED ten times, once for each RngRun value. The lowest and highest goodput values among these ten observations are used for checking. Is this a correct way to find out "the appropriate values to be used for checking"?
Sign in to reply to this message.
Hi, Following updates have been made in Patch 5: 1. Modified adaptive-red-tests.cc to check for good data 2. Modified red_vs_ared.cc to check for good data 3. Modified examples-to-run.py to run above both examples with different inputs 4. Modified tests in red-queue-test-suite.cc to check for EQ instead of LT / GT Any suggestions / corrections would be much appreciated. Regards, Mohit P. Tahiliani
Sign in to reply to this message.
One last thing from my side. Other than that, I can't spot anything more. I have not extensively used this implementation, but I'm confident you did. Shortly put, +1. https://codereview.appspot.com/279950043/diff/140001/src/network/examples/ada... File src/network/examples/adaptive-red-tests.cc (right): https://codereview.appspot.com/279950043/diff/140001/src/network/examples/ada... src/network/examples/adaptive-red-tests.cc:650: std::cout << "*** RED stats from Node 2 queue ***" << std::endl; Should't it be "ARED" ?
Sign in to reply to this message.
Dear Tommaso, Thank you very much for your time and feedback! I've corrected the typo and changed it to ARED. Also, I'm updating the doc to provide little more detail and will upload the same too. Thank you again, for consistently providing your valuable feedback. Regards, Mohit P. Tahiliani https://codereview.appspot.com/279950043/diff/140001/src/network/examples/ada... File src/network/examples/adaptive-red-tests.cc (right): https://codereview.appspot.com/279950043/diff/140001/src/network/examples/ada... src/network/examples/adaptive-red-tests.cc:650: std::cout << "*** RED stats from Node 2 queue ***" << std::endl; On 2016/02/08 16:36:23, Tommaso Pecorella wrote: > Should't it be "ARED" ? Yes, it should be ARED :) I think I've missed such things in many other places. Thank you!
Sign in to reply to this message.
Hi, I have uploaded patch 6, with the following major modifications: 1. There was a bug that I found while testing the patch (with BYTES mode of ARED). It has been resolved. 2. Another bug was with automatic settings of minTh and maxTh. It has been resolved too. 3. A separate test suite (adaptive-red-queue-suite.cc) is implemented for ARED, and decoupled from that of RED. 4. ARED's test suite contains two test cases: (i) for automatic parameters of ARED and (ii) for adaptive parameter of ARED. Earlier patches did not contain tests for (ii) 5. Added little more detail to doc. 6. Some typos have been corrected. Thank you very much for your time and suggestions. Any further suggestions / corrections would be much appreciated. Regards, Mohit P. Tahiliani https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... File src/network/test/red-queue-test-suite.cc (right): https://codereview.appspot.com/279950043/diff/1/src/network/test/red-queue-te... src/network/test/red-queue-test-suite.cc:414: NS_TEST_EXPECT_MSG_LT (drop.test15, drop.test14, "Test 15 should have less drops than test 14"); On 2015/12/02 19:54:45, Tom Henderson wrote: > I do not understand why the attribute "Adaptive" is not set to true if these are > adaptive RED tests? Is this a mistake (setting "Mode" instead of "Adaptive")? > > If this is a mistake, this means that these tests were not testing adaptive RED, > just RED. Maybe the tests need to be rethought if so (if they pass regardless > of whether Adaptive is true or false, they are not good tests). > > Rather than simply checking whether the aggregate number of drops are less than > one test or another, could you test explicitly for exact values, that you have > validated by hand? For example, what is the exact value expected for > unforcedrop, forcedDrop, and qLimDrop in all cases, and can you test for "EQ" > instead of "LT"? Dear Sir, I've added a separate test case with "Adaptive" set to true in the new test suite implemented in patch 6. Further, all tests now use EQ instead of LT or GT.
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
