11#include "ns3/codel-queue-disc.h"
12#include "ns3/double.h"
14#include "ns3/packet.h"
15#include "ns3/simulator.h"
16#include "ns3/string.h"
18#include "ns3/uinteger.h"
23#define REC_INV_SQRT_BITS_ns3 (8 * sizeof(uint16_t))
26#define REC_INV_SQRT_SHIFT_ns3 (32 - REC_INV_SQRT_BITS_ns3)
32 uint32_t invsqrt2 = ((uint64_t)invsqrt * invsqrt) >> 32;
33 uint64_t val = (3LL << 32) - ((uint64_t)count * invsqrt2);
36 val = (val * invsqrt) >> (32 - 2 + 1);
43 return (
uint32_t)(((uint64_t)val * ep_ro) >> 32);
80 m_ecnCapablePacket(ecnCapable)
113 void DoRun()
override;
120 :
TestCase(
"Basic enqueue and dequeue operations, and attribute setting")
137 "Verify that we can actually set the attribute MinBytes");
140 "Verify that we can actually set the attribute Interval");
143 "Verify that we can actually set the attribute Target");
145 if (
m_mode == QueueSizeUnit::BYTES)
149 else if (
m_mode == QueueSizeUnit::PACKETS)
156 "Verify that we can actually set the attribute MaxSize");
174 "There should be no packets in queue");
178 "There should be one packet in queue");
182 "There should be two packets in queue");
186 "There should be three packets in queue");
190 "There should be four packets in queue");
194 "There should be five packets in queue");
198 "There should be six packets in queue");
202 "There should be no packets being dropped due to full queue");
206 item = queue->Dequeue();
210 "There should be five packets in queue");
213 item = queue->Dequeue();
217 "There should be four packets in queue");
220 "Was this the second packet ?");
222 item = queue->Dequeue();
226 "There should be three packets in queue");
229 item = queue->Dequeue();
233 "There should be two packets in queue");
236 "Was this the fourth packet ?");
238 item = queue->Dequeue();
242 "There should be one packet in queue");
245 item = queue->Dequeue();
249 "There should be zero packet in queue");
252 item = queue->Dequeue();
258 "There should be no packet drops according to CoDel algorithm");
275 void DoRun()
override;
289 :
TestCase(
"Basic overflow behavior")
303 if (
m_mode == QueueSizeUnit::BYTES)
307 else if (
m_mode == QueueSizeUnit::PACKETS)
322 "Verify that we can actually set the attribute MaxSize");
325 "Verify that we can actually set the attribute MinBytes");
336 "There should be 500 packets in queue");
339 "There should be three packets being dropped due to full queue");
361 void DoRun()
override;
365 :
TestCase(
"NewtonStep arithmetic unit test")
377 for (uint16_t recInvSqrt = 0xff; recInvSqrt > 0; recInvSqrt /= 2)
379 for (
uint32_t count = 1; count < 0xff; count *= 2)
381 result = queue->NewtonStep(recInvSqrt, count);
385 "ns-3 NewtonStep() fails to match Linux equivalent");
399 void DoRun()
override;
411 :
TestCase(
"ControlLaw arithmetic unit test")
436 for (uint16_t recInvSqrt = 0xff; recInvSqrt > 0; recInvSqrt /= 2)
438 codelTimeVal = queue->Time2CoDel(timeVal);
439 uint32_t ns3Result = queue->ControlLaw(codelTimeVal, interval, recInvSqrt);
443 "Linux result for ControlLaw should equal ns-3 result");
462 void DoRun()
override;
507 if (
m_mode == QueueSizeUnit::BYTES)
511 else if (
m_mode == QueueSizeUnit::PACKETS)
519 "Verify that we can actually set the attribute MaxSize");
526 "There should be 20 packets in queue.");
530 Time waitUntilFirstDequeue = 2 * queue->GetTarget();
538 Time waitUntilSecondDequeue = waitUntilFirstDequeue + 2 * queue->GetInterval();
580 uint32_t initialQSize = queue->GetCurrentSize().GetValue();
581 uint32_t initialDropNext = queue->GetDropNext();
585 if (initialDropCount > 0 && currentTime.
GetMicroSeconds() >= initialDropNext)
587 queue->TraceConnectWithoutContext(
592 if (initialQSize != 0)
595 if (initialDropCount == 0 && currentTime > queue->GetTarget())
597 if (currentTime < queue->GetInterval())
603 "We are not in dropping state."
604 "Sojourn time has just gone above target from below."
605 "Hence, there should be no packet drops");
607 initialQSize - modeSize,
608 "There should be 1 packet dequeued.");
610 else if (currentTime >= queue->GetInterval())
615 initialQSize - 2 * modeSize,
616 "Sojourn time has been above target for at least interval."
617 "We enter the dropping state, perform initial packet drop, "
618 "and dequeue the next."
619 "So there should be 2 more packets dequeued.");
623 else if (initialDropCount > 0)
630 initialQSize - modeSize,
631 "We are in dropping state."
632 "Sojourn is still above target."
633 "However, it's not time for next drop."
634 "So there should be only 1 more packet dequeued");
639 "There should still be only 1 packet drop from the last dequeue");
647 "We are in dropping state."
648 "It's time for next drop."
649 "The number of packets dequeued equals to the number of "
650 "times m_dropNext is updated plus initial dequeue");
653 "The number of drops equals to the number of times "
654 "m_dropNext is updated plus 1 from last dequeue");
674 void DoRun()
override;
732 if (
m_mode == QueueSizeUnit::BYTES)
736 else if (
m_mode == QueueSizeUnit::PACKETS)
744 "Verify that we can actually set the attribute MaxSize");
747 "Verify that we can actually set the attribute UseEcn");
755 "There should be 20 packets in queue.");
759 Time waitUntilFirstDequeue = 2 * queue->GetTarget();
768 Time waitUntilSecondDequeue = waitUntilFirstDequeue + 2 * queue->GetInterval();
784 "Verify that we can actually set the attribute MaxSize");
787 "Verify that we can actually set the attribute UseEcn");
795 "There should be 20 packets in queue.");
840 "Verify that we can actually set the attribute MaxSize");
843 "Verify that we can actually set the attribute UseEcn");
846 "Verify that we can actually set the attribute CeThreshold");
856 "There should be 20 packets in queue.");
902 "Verify that we can actually set the attribute MaxSize");
905 "Verify that we can actually set the attribute UseEcn");
908 "Verify that we can actually set the attribute CeThreshold");
916 "There should be 20 packets in queue.");
977 uint32_t initialQSize = queue->GetCurrentSize().GetValue();
978 uint32_t initialDropNext = queue->GetDropNext();
981 uint32_t currentTargetMarkCount = 0;
982 uint32_t currentCeThreshMarkCount = 0;
984 if (initialTargetMarkCount > 0 && currentTime.
GetMicroSeconds() >= initialDropNext &&
987 queue->TraceConnectWithoutContext(
992 if (initialQSize != 0)
999 if (currentDropCount == 1)
1004 else if (testCase == 2)
1006 if (initialTargetMarkCount == 0 && currentTime > queue->GetTarget())
1008 if (currentTime < queue->GetInterval())
1012 currentTargetMarkCount =
1014 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1017 initialQSize - modeSize,
1018 "There should be 1 packet dequeued.");
1021 "There should not be any packet drops");
1023 currentTargetMarkCount,
1025 "We are not in dropping state."
1026 "Sojourn time has just gone above target from below."
1027 "Hence, there should be no target exceeded marked packets");
1029 currentCeThreshMarkCount,
1031 "Marking due to CE threshold is disabled"
1032 "Hence, there should not be any CE threshold exceeded marked packet");
1034 else if (currentTime >= queue->GetInterval())
1038 currentTargetMarkCount =
1041 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1044 queue->GetCurrentSize().GetValue(),
1045 initialQSize - modeSize,
1046 "Sojourn time has been above target for at least interval."
1047 "We enter the dropping state and perform initial packet marking"
1048 "So there should be only 1 more packet dequeued.");
1051 "There should not be any packet drops");
1054 "There should be 1 target exceeded marked packet");
1056 currentCeThreshMarkCount,
1058 "There should not be any CE threshold exceeded marked packet");
1061 else if (initialTargetMarkCount > 0)
1067 currentTargetMarkCount =
1069 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1072 initialQSize - modeSize,
1073 "We are in dropping state."
1074 "Sojourn is still above target."
1075 "However, it's not time for next target exceeded mark."
1076 "So there should be only 1 more packet dequeued");
1079 "There should not be any packet drops");
1082 "There should still be only 1 target exceeded marked "
1083 "packet from the last dequeue");
1085 currentCeThreshMarkCount,
1087 "There should not be any CE threshold exceeded marked packet");
1093 currentTargetMarkCount =
1095 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1098 initialQSize - modeSize,
1099 "We are in dropping state."
1100 "It's time for packet to be marked"
1101 "So there should be only 1 more packet dequeued");
1104 "There should not be any packet drops");
1107 "There should 2 target exceeded marked packet");
1111 "Number of packets in the queue before drop should be equal"
1112 "to number of packets in the queue before first mark as the behavior "
1113 "until packet N should be the same.");
1115 currentCeThreshMarkCount,
1117 "There should not be any CE threshold exceeded marked packet");
1121 else if (testCase == 3)
1123 if (initialTargetMarkCount == 0 && currentTime > queue->GetTarget())
1125 if (currentTime < queue->GetInterval())
1129 currentTargetMarkCount =
1131 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1134 initialQSize - modeSize,
1135 "There should be 1 packet dequeued.");
1138 "There should not be any packet drops");
1140 currentTargetMarkCount,
1142 "We are not in dropping state."
1143 "Sojourn time has just gone above target from below."
1144 "Hence, there should be no target exceeded marked packets");
1146 currentCeThreshMarkCount,
1148 "Sojourn time has gone above CE threshold."
1149 "Hence, there should be 1 CE threshold exceeded marked packet");
1151 else if (currentTime >= queue->GetInterval())
1155 currentTargetMarkCount =
1157 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1160 queue->GetCurrentSize().GetValue(),
1161 initialQSize - modeSize,
1162 "Sojourn time has been above target for at least interval."
1163 "We enter the dropping state and perform initial packet marking"
1164 "So there should be only 1 more packet dequeued.");
1167 "There should not be any packet drops");
1170 "There should be 1 target exceeded marked packet");
1173 "There should be 1 CE threshold exceeded marked packets");
1176 else if (initialTargetMarkCount > 0)
1182 currentTargetMarkCount =
1184 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1187 initialQSize - modeSize,
1188 "We are in dropping state."
1189 "Sojourn is still above target."
1190 "However, it's not time for next target exceeded mark."
1191 "So there should be only 1 more packet dequeued");
1194 "There should not be any packet drops");
1197 "There should still be only 1 target exceeded marked "
1198 "packet from the last dequeue");
1201 "There should be 2 CE threshold exceeded marked packets");
1207 currentTargetMarkCount =
1209 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1212 queue->GetCurrentSize().GetValue(),
1214 "We are in dropping state."
1215 "It's time for packet to be dropped as packets are not ecnCapable"
1216 "The number of packets dequeued equals to the number of times m_dropNext "
1217 "is updated plus initial dequeue");
1221 "The number of drops equals to the number of times m_dropNext is updated");
1223 currentTargetMarkCount,
1225 "There should still be only 1 target exceeded marked packet");
1228 "There should still be 2 CE threshold exceeded marked "
1229 "packet as packets are not ecnCapable");
1233 else if (testCase == 4)
1235 if (currentTime < queue->GetTarget())
1237 if (initialCeThreshMarkCount == 0 && currentTime <
MilliSeconds(2))
1241 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1244 initialQSize - modeSize,
1245 "There should be 1 packet dequeued.");
1248 "There should not be any packet drops");
1250 currentCeThreshMarkCount,
1252 "Sojourn time has not gone above CE threshold."
1253 "Hence, there should not be any CE threshold exceeded marked packet");
1259 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1262 initialQSize - modeSize,
1263 "There should be only 1 more packet dequeued.");
1266 "There should not be any packet drops");
1269 "Sojourn time has gone above CE threshold."
1270 "There should be 1 CE threshold exceeded marked packet");
1273 else if (initialCeThreshMarkCount > 0 && currentTime < queue->GetInterval())
1275 if (initialCeThreshMarkCount < 2)
1279 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1282 initialQSize - modeSize,
1283 "There should be only 1 more packet dequeued.");
1286 "There should not be any packet drops");
1289 "There should be 2 CE threshold exceeded marked packets");
1295 currentCeThreshMarkCount = queue->GetStats().GetNMarkedPackets(
1298 initialQSize - modeSize,
1299 "There should be only 1 more packet dequeued.");
1302 "There should not be any packet drops");
1305 "There should be 3 CE threshold exceeded marked packet");
1325 TestCase::Duration::QUICK);
1327 TestCase::Duration::QUICK);
1330 TestCase::Duration::QUICK);
1332 TestCase::Duration::QUICK);
Test 5: enqueue/dequeue with drops according to CoDel algorithm.
uint32_t m_dropNextCount
count the number of times m_dropNext is recalculated
CoDelQueueDiscBasicDrop(QueueSizeUnit mode)
Constructor.
void Dequeue(Ptr< CoDelQueueDisc > queue, uint32_t modeSize)
Dequeue function.
void Enqueue(Ptr< CoDelQueueDisc > queue, uint32_t size, uint32_t nPkt)
Enqueue function.
void DoRun() override
Implementation to actually run this TestCase.
void DropNextTracer(uint32_t oldVal, uint32_t newVal)
Drop next tracer function.
Test 1: simple enqueue/dequeue with no drops.
CoDelQueueDiscBasicEnqueueDequeue(QueueSizeUnit mode)
Constructor.
void DoRun() override
Implementation to actually run this TestCase.
Test 6: enqueue/dequeue with marks according to CoDel algorithm.
uint32_t nPacketsBeforeFirstMark
Number of packets in the queue before first mark.
void Enqueue(Ptr< CoDelQueueDisc > queue, uint32_t size, uint32_t nPkt, bool ecnCapable)
Enqueue function.
uint32_t m_dropNextCount
count the number of times m_dropNext is recalculated
void DropNextTracer(uint32_t oldVal, uint32_t newVal)
Drop next tracer function.
uint32_t nPacketsBeforeFirstDrop
Number of packets in the queue before first drop.
void Dequeue(Ptr< CoDelQueueDisc > queue, uint32_t modeSize, uint32_t testCase)
Dequeue function.
void DoRun() override
Implementation to actually run this TestCase.
CoDelQueueDiscBasicMark(QueueSizeUnit mode)
Constructor.
Test 2: enqueue with drops due to queue overflow.
CoDelQueueDiscBasicOverflow(QueueSizeUnit mode)
Constructor.
void DoRun() override
Implementation to actually run this TestCase.
void Enqueue(Ptr< CoDelQueueDisc > queue, uint32_t size, uint32_t nPkt)
Enqueue function.
Test 4: ControlLaw unit test - test against explicit port of Linux implementation.
void DoRun() override
Implementation to actually run this TestCase.
CoDelQueueDiscControlLawTest()
uint32_t _codel_control_law(uint32_t t, uint32_t interval, uint32_t recInvSqrt)
Codel control law function.
Test 3: NewtonStep unit test - test against explicit port of Linux implementation.
void DoRun() override
Implementation to actually run this TestCase.
CoDelQueueDiscNewtonStepTest()
CoDel Queue Disc Test Suite.
CoDelQueueDiscTestSuite()
Codel Queue Disc Test Item.
void AddHeader() override
Add the header to the packet.
~CodelQueueDiscTestItem() override
bool Mark() override
Marks the packet as a substitute for dropping it, such as for Explicit Congestion Notification.
bool m_ecnCapablePacket
ECN capable packet?
CodelQueueDiscTestItem & operator=(const CodelQueueDiscTestItem &)=delete
CodelQueueDiscTestItem(const CodelQueueDiscTestItem &)=delete
CodelQueueDiscTestItem()=delete
a polymophic address class
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
static constexpr const char * TARGET_EXCEEDED_MARK
Sojourn time above target.
Smart pointer class similar to boost::intrusive_ptr.
QueueDiscItem is the abstract base class for items that are stored in a queue disc.
Class for representing queue sizes.
static EventId Schedule(const Time &delay, FUNC f, Ts &&... args)
Schedule an event to expire after delay.
static void Destroy()
Execute the events scheduled with ScheduleDestroy().
static Time Now()
Return the current simulation virtual time.
static void Run()
Run the simulation.
Hold variables of type string.
void AddTestCase(TestCase *testCase, Duration duration=Duration::QUICK)
Add an individual child TestCase to this test suite.
static constexpr auto UNIT
Simulation virtual time values and global simulation resolution.
int64_t GetMicroSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Hold an unsigned integer type.
#define REC_INV_SQRT_SHIFT_ns3
static uint16_t _codel_Newton_step(uint16_t rec_inv_sqrt, uint32_t count)
static uint32_t _reciprocal_scale(uint32_t val, uint32_t ep_ro)
Ptr< T > CreateObject(Args &&... args)
Create an object by type, with varying number of constructor parameters.
Ptr< T > Create(Ts &&... args)
Create class instances by constructors with varying numbers of arguments and return them by Ptr.
QueueSizeUnit
Enumeration of the operating modes of queues.
#define NS_TEST_ASSERT_MSG_EQ(actual, limit, msg)
Test that an actual and expected (limit) value are equal and report and abort if not.
#define NS_TEST_EXPECT_MSG_EQ(actual, limit, msg)
Test that an actual and expected (limit) value are equal and report if not.
#define NS_TEST_ASSERT_MSG_NE(actual, limit, msg)
Test that an actual and expected (limit) value are not equal and report and abort if not.
Time Seconds(double value)
Construct a Time in the indicated unit.
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
CoDelQueueDiscTestSuite g_coDelQueueTestSuite
the test suite
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Callback< R, Args... > MakeCallback(R(T::*memPtr)(Args...), OBJ objPtr)
Build Callbacks for class method members which take varying numbers of arguments and potentially retu...
uint32_t pktSize
packet size used for the simulation (in bytes)