A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
wifi-mac-queue.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2005, 2009 INRIA
3 * Copyright (c) 2009 MIRKO BANCHI
4 *
5 * SPDX-License-Identifier: GPL-2.0-only
6 *
7 * Authors: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
8 * Mirko Banchi <mk.banchi@gmail.com>
9 * Stefano Avallone <stavallo@unina.it>
10 */
11
12#include "wifi-mac-queue.h"
13
15
16#include "ns3/simulator.h"
17
18#include <functional>
19#include <optional>
20
21namespace ns3
22{
23
24NS_LOG_COMPONENT_DEFINE("WifiMacQueue");
25
26NS_OBJECT_ENSURE_REGISTERED(WifiMacQueue);
27NS_OBJECT_TEMPLATE_CLASS_TWO_DEFINE(Queue, WifiMpdu, WifiMacQueueContainer);
28
29TypeId
31{
32 static TypeId tid =
33 TypeId("ns3::WifiMacQueue")
35 .SetGroupName("Wifi")
36 .AddConstructor<WifiMacQueue>()
37 .AddAttribute("MaxSize",
38 "The max queue size",
42 .AddAttribute("MaxDelay",
43 "If a packet stays longer than this delay in the queue, it is dropped.",
47 .AddTraceSource("Expired",
48 "MPDU dropped because its lifetime expired.",
50 "ns3::WifiMpdu::TracedCallback");
51 return tid;
52}
53
55 : m_ac(ac),
56 NS_LOG_TEMPLATE_DEFINE("WifiMacQueue")
57{
58}
59
64
65void
72
75{
76 return m_ac;
77}
78
81{
82 NS_ASSERT(mpdu->IsQueued());
83 return mpdu->GetQueueIt(WmqIteratorTag());
84}
85
88{
89 return GetIt(mpdu)->mpdu;
90}
91
94{
95 if (!mpdu->IsQueued())
96 {
97 return nullptr;
98 }
99 if (auto aliasIt = GetIt(mpdu)->inflights.find(linkId);
100 aliasIt != GetIt(mpdu)->inflights.cend())
101 {
102 return aliasIt->second;
103 }
104 return nullptr;
105}
106
107void
109{
110 NS_LOG_FUNCTION(this);
111
112 std::list<Ptr<WifiMpdu>> mpdus;
113 auto [first, last] = GetContainer().ExtractExpiredMpdus(queueId);
114
115 for (auto it = first; it != last; it++)
116 {
117 mpdus.push_back(it->mpdu);
118 }
119 for (const auto& mpdu : mpdus)
120 {
121 // fire the Expired trace
122 auto fire = [this, mpdu]() -> void { this->m_traceExpired(mpdu); };
124 }
125 // notify the scheduler
126 if (!mpdus.empty())
127 {
128 m_scheduler->NotifyRemove(m_ac, mpdus);
129 }
130}
131
132void
134{
135 NS_LOG_FUNCTION(this);
136
137 std::list<Ptr<WifiMpdu>> mpdus;
138 auto [first, last] = GetContainer().ExtractAllExpiredMpdus();
139
140 for (auto it = first; it != last; it++)
141 {
142 mpdus.push_back(it->mpdu);
143 }
144 for (const auto& mpdu : mpdus)
145 {
146 // fire the Expired trace
147 auto fire = [this, mpdu]() -> void { this->m_traceExpired(mpdu); };
149 }
150 // notify the scheduler
151 if (!mpdus.empty())
152 {
153 m_scheduler->NotifyRemove(m_ac, mpdus);
154 }
155}
156
157void
159{
160 NS_LOG_FUNCTION(this);
161
163
164 auto [first, last] = GetContainer().GetAllExpiredMpdus();
165
166 for (auto it = first; it != last;)
167 {
168 // the scheduler has been notified and the Expired trace has been fired
169 // when the MPDU was extracted from its queue. The only thing left to do
170 // is to update the Queue base class statistics by calling Queue::DoRemove
171 auto curr = it++;
173 }
174}
175
176bool
178{
179 NS_ASSERT(item && item->IsQueued());
180 auto it = GetIt(item);
181 if (now > it->expiryTime)
182 {
183 NS_LOG_DEBUG("Removing packet that stayed in the queue for too long (queuing time="
184 << now - it->expiryTime + m_maxDelay << ")");
185 // Trace the expired MPDU first and then remove it from the queue (if still in the queue).
186 // Indeed, the Expired traced source is connected to BlockAckManager::NotifyDiscardedMpdu,
187 // which checks if the expired MPDU is in-flight or is a retransmission to determine
188 // whether a BlockAckReq frame must be sent to advance the recipient window. If the
189 // expired MPDU is removed from the queue before tracing the expiration, it is no longer
190 // in-flight and NotifyDiscardedMpdu wrongfully assumes that a BlockAckReq is not needed.
191 m_traceExpired(item);
192 if (item->IsQueued())
193 {
194 DoRemove(it);
195 }
196 return true;
197 }
198 return false;
199}
200
201void
203{
204 NS_LOG_FUNCTION(this << scheduler);
205 m_scheduler = scheduler;
206}
207
208void
210{
211 NS_LOG_FUNCTION(this << delay);
212 m_maxDelay = delay;
213}
214
215Time
217{
218 return m_maxDelay;
219}
220
221bool
223{
224 NS_LOG_FUNCTION(this << *item);
225
226 auto queueId = WifiMacQueueContainer::GetQueueId(item);
227 return Insert(GetContainer().GetQueue(queueId).cend(), item);
228}
229
230bool
231WifiMacQueue::Insert(ConstIterator pos, Ptr<WifiMpdu> item)
232{
233 NS_LOG_FUNCTION(this << *item);
235 "WifiMacQueues must be in packet mode");
236
237 // insert the item if the queue is not full
238 if (QueueBase::GetNPackets() < GetMaxSize().GetValue())
239 {
240 return DoEnqueue(pos, item);
241 }
242
243 // the queue is full; try to make some room by removing stale packets
244 auto queueId = WifiMacQueueContainer::GetQueueId(item);
245
246 if (pos != GetContainer().GetQueue(queueId).cend())
247 {
249 "pos must point to an element in the same container queue as item");
250 if (pos->expiryTime <= Simulator::Now())
251 {
252 // the element pointed to by pos is stale and will be removed along with all of
253 // its predecessors; the new item will be enqueued at the front of the queue
254 pos = GetContainer().GetQueue(queueId).cbegin();
255 }
256 }
257
259
260 return DoEnqueue(pos, item);
261}
262
265{
266 // An MPDU is dequeued when either is acknowledged or is dropped, hence a Dequeue
267 // method without an argument makes no sense.
268 NS_ABORT_MSG("Not implemented by WifiMacQueue");
269 return nullptr;
270}
271
272void
274{
275 NS_LOG_FUNCTION(this);
276
277 std::list<ConstIterator> iterators;
278
279 for (const auto& mpdu : mpdus)
280 {
281 if (mpdu->IsQueued())
282 {
283 auto it = GetIt(mpdu);
284 NS_ASSERT(it->ac == m_ac);
285 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
286 iterators.emplace_back(it);
287 }
288 }
289
290 DoDequeue(iterators);
291}
292
295{
296 return Peek(std::nullopt);
297}
298
300WifiMacQueue::Peek(std::optional<uint8_t> linkId) const
301{
302 NS_LOG_FUNCTION(this);
303
304 auto queueId = m_scheduler->GetNext(m_ac, linkId);
305
306 if (!queueId.has_value())
307 {
308 NS_LOG_DEBUG("The queue is empty");
309 return nullptr;
310 }
311
312 return GetContainer().GetQueue(queueId.value()).cbegin()->mpdu;
313}
314
317{
318 NS_LOG_FUNCTION(this << +tid << dest << item);
319 NS_ABORT_IF(dest.IsBroadcast());
322 dest,
323 tid);
324 return PeekByQueueId(queueId, item);
325}
326
329{
330 NS_LOG_FUNCTION(this << item);
331 NS_ASSERT(!item || (item->IsQueued() && WifiMacQueueContainer::GetQueueId(item) == queueId));
332
333 // Remove MPDUs with expired lifetime if we are looking for the first MPDU in the queue
334 if (!item)
335 {
336 ExtractExpiredMpdus(queueId);
337 }
338
339 auto it = (item ? std::next(GetIt(item)) : GetContainer().GetQueue(queueId).cbegin());
340
341 if (it == GetContainer().GetQueue(queueId).cend())
342 {
343 NS_LOG_DEBUG("The queue is empty");
344 return nullptr;
345 }
346
347 return it->mpdu;
348}
349
352{
353 NS_LOG_FUNCTION(this << +linkId << item);
354 NS_ASSERT(!item || item->IsQueued());
355
356 if (item)
357 {
358 // check if there are other MPDUs in the same container queue as item
359 auto mpdu = PeekByQueueId(WifiMacQueueContainer::GetQueueId(item), item);
360
361 if (mpdu)
362 {
363 return mpdu;
364 }
365 }
366
367 std::optional<WifiContainerQueueId> queueId;
368
369 if (item)
370 {
371 queueId = m_scheduler->GetNext(m_ac, linkId, WifiMacQueueContainer::GetQueueId(item));
372 }
373 else
374 {
375 queueId = m_scheduler->GetNext(m_ac, linkId);
376 }
377
378 if (!queueId.has_value())
379 {
380 NS_LOG_DEBUG("The queue is empty");
381 return nullptr;
382 }
383
384 return GetContainer().GetQueue(queueId.value()).cbegin()->mpdu;
385}
386
389{
390 if (auto queueId = m_scheduler->GetNext(m_ac, std::nullopt, false))
391 {
392 return Remove(GetContainer().GetQueue(queueId.value()).cbegin()->mpdu);
393 }
394
395 NS_LOG_DEBUG("The queue is empty");
396 return nullptr;
397}
398
401{
402 NS_LOG_FUNCTION(this << mpdu);
403 NS_ASSERT(mpdu && mpdu->IsQueued());
404 auto it = GetIt(mpdu);
405 NS_ASSERT(it->ac == m_ac);
406 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
407
408 return DoRemove(it);
409}
410
411void
413{
414 NS_LOG_FUNCTION(this);
415
416 // there may be some expired MPDUs in the container queue storing MPDUs with expired lifetime,
417 // which will not be flushed by the Flush() method of the base class.
420}
421
422void
424{
425 NS_LOG_FUNCTION(this << *currentItem << *newItem);
426 NS_ASSERT(currentItem->IsQueued());
427 auto currentIt = GetIt(currentItem);
428 NS_ASSERT(currentIt->ac == m_ac);
429 NS_ASSERT(currentIt->mpdu == currentItem->GetOriginal());
430 NS_ASSERT(!newItem->IsQueued());
431
432 Time expiryTime = currentIt->expiryTime;
433 auto pos = std::next(currentIt);
434 DoDequeue({currentIt});
435 bool ret = Insert(pos, newItem);
436 GetIt(newItem)->expiryTime = expiryTime;
437 // The size of a WifiMacQueue is measured as number of packets. We dequeued
438 // one packet, so there is certainly room for inserting one packet
439 NS_ABORT_IF(!ret);
440}
441
444{
445 return GetContainer().GetQueue(queueId).size();
446}
447
450{
451 return GetContainer().GetNBytes(queueId);
452}
453
454bool
456{
457 NS_LOG_FUNCTION(this << *item);
458
459 auto currSize = GetMaxSize();
460 // control frames should not consume room in the MAC queue, so increase queue size
461 // if we are trying to enqueue a control frame
462 if (item->GetHeader().IsCtl())
463 {
464 SetMaxSize(currSize + item);
465 }
466 auto mpdu = m_scheduler->HasToDropBeforeEnqueue(m_ac, item);
467
468 if (mpdu == item)
469 {
470 // the given item must be dropped
471 SetMaxSize(currSize);
472 return false;
473 }
474
475 auto queueId = WifiMacQueueContainer::GetQueueId(item);
476 if (pos != GetContainer().GetQueue(queueId).cend() && mpdu && pos->mpdu == mpdu->GetOriginal())
477 {
478 // the element pointed to by pos must be dropped; update insert position
479 pos = std::next(pos);
480 }
481 if (mpdu)
482 {
483 DoRemove(GetIt(mpdu));
484 }
485
486 Iterator ret;
488 {
489 // set item's information about its position in the queue
490 item->SetQueueIt(ret, {});
491 ret->ac = m_ac;
492 ret->expiryTime = item->GetHeader().IsCtl() ? Time::Max() : Simulator::Now() + m_maxDelay;
493 WmqIteratorTag tag;
494 ret->deleter = [tag](auto mpdu) { mpdu->SetQueueIt(std::nullopt, tag); };
495
496 m_scheduler->NotifyEnqueue(m_ac, item);
497 return true;
498 }
499 SetMaxSize(currSize);
500 return false;
501}
502
503void
504WifiMacQueue::DoDequeue(const std::list<ConstIterator>& iterators)
505{
506 NS_LOG_FUNCTION(this);
507
508 std::list<Ptr<WifiMpdu>> items;
509
510 // First, dequeue all the items
511 for (auto& it : iterators)
512 {
514 {
515 items.push_back(item);
516 if (item->GetHeader().IsCtl())
517 {
518 SetMaxSize(GetMaxSize() - item);
519 }
520 }
521 }
522
523 // Then, notify the scheduler
524 if (!items.empty())
525 {
526 m_scheduler->NotifyDequeue(m_ac, items);
527 }
528}
529
531WifiMacQueue::DoRemove(ConstIterator pos)
532{
533 NS_LOG_FUNCTION(this);
534
536
537 if (item)
538 {
539 if (item->GetHeader().IsCtl())
540 {
541 SetMaxSize(GetMaxSize() - item);
542 }
543 m_scheduler->NotifyRemove(m_ac, {item});
544 }
545
546 return item;
547}
548
549} // namespace ns3
an EUI-48 address
bool IsGroup() const
bool IsBroadcast() const
Smart pointer class similar to boost::intrusive_ptr.
QueueSize GetMaxSize() const
Definition queue.cc:206
uint32_t GetNBytes() const
Definition queue.cc:87
uint32_t GetNPackets() const
Definition queue.cc:79
void SetMaxSize(QueueSize size)
Set the maximum size of this queue.
Definition queue.cc:189
Template class for packet Queues.
Definition queue.h:257
Ptr< Item > DoRemove(ConstIterator pos)
Pull the item to drop from the queue.
Definition queue.h:565
void Flush()
Flush the queue by calling Remove() on each item enqueued.
Definition queue.h:597
void DoDispose() override
Destructor implementation.
Definition queue.h:608
const ns3::WifiMacQueueContainer & GetContainer() const
Definition queue.h:493
ns3::WifiMacQueueContainer::iterator Iterator
Definition queue.h:310
Class for representing queue sizes.
Definition queue-size.h:85
AttributeValue implementation for QueueSize.
Definition queue-size.h:210
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
static EventId ScheduleNow(FUNC f, Ts &&... args)
Schedule an event to expire Now.
Definition simulator.h:595
Simulation virtual time values and global simulation resolution.
Definition nstime.h:96
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition nstime.h:288
AttributeValue implementation for Time.
Definition nstime.h:1456
a unique identifier for an interface.
Definition type-id.h:49
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
const ContainerQueue & GetQueue(const WifiContainerQueueId &queueId) const
Get a const reference to the container queue identified by the given QueueId.
static WifiContainerQueueId GetQueueId(Ptr< const WifiMpdu > mpdu)
Return the QueueId identifying the container queue in which the given MPDU is (or is to be) enqueued.
uint32_t GetNBytes(const WifiContainerQueueId &queueId) const
Get the total size of the MPDUs stored in the queue identified by the given QueueId.
std::pair< iterator, iterator > ExtractAllExpiredMpdus() const
Transfer non-inflight MPDUs with expired lifetime in all the container queues to the container queue ...
std::pair< iterator, iterator > GetAllExpiredMpdus() const
Get the range [first, last) of iterators pointing to all the MPDUs queued in the container queue stor...
std::pair< iterator, iterator > ExtractExpiredMpdus(const WifiContainerQueueId &queueId) const
Transfer non-inflight MPDUs with expired lifetime in the container queue identified by the given Queu...
This queue implements the timeout procedure described in (Section 9.19.2.6 "Retransmit procedures" pa...
Time m_maxDelay
Time to live for packets in the queue.
void Replace(Ptr< const WifiMpdu > currentItem, Ptr< WifiMpdu > newItem)
Replace the given current item with the given new item.
Ptr< WifiMpdu > PeekByQueueId(const WifiContainerQueueId &queueId, Ptr< const WifiMpdu > item=nullptr) const
Search and return the first packet present in the container queue identified by the given queue ID.
Ptr< WifiMpdu > Remove() override
Remove the packet in the front of the queue.
Ptr< WifiMacQueueScheduler > m_scheduler
the MAC queue scheduler
AcIndex GetAc() const
Get the Access Category of the packets stored in this queue.
bool Insert(ConstIterator pos, Ptr< WifiMpdu > item)
Enqueue the given Wifi MAC queue item before the given position.
void ExtractExpiredMpdus(const WifiContainerQueueId &queueId) const
Move MPDUs with expired lifetime from the container queue identified by the given queue ID to the con...
bool Enqueue(Ptr< WifiMpdu > item) override
Enqueue the given Wifi MAC queue item at the end of the queue.
Ptr< const WifiMpdu > Peek() const override
Peek the packet in the front of the queue.
Iterator GetIt(Ptr< const WifiMpdu > mpdu) const
bool TtlExceeded(Ptr< const WifiMpdu > item, const Time &now)
Remove the given item if it has been in the queue for too long.
void WipeAllExpiredMpdus()
Remove all MPDUs with expired lifetime from this WifiMacQueue object.
Ptr< WifiMpdu > Dequeue() override
Dequeue the packet in the front of the queue.
void SetScheduler(Ptr< WifiMacQueueScheduler > scheduler)
Set the wifi MAC queue scheduler.
void SetMaxDelay(Time delay)
Set the maximum delay before the packet is discarded.
void DoDispose() override
Destructor implementation.
~WifiMacQueue() override
Ptr< WifiMpdu > GetAlias(Ptr< const WifiMpdu > mpdu, uint8_t linkId)
Ptr< WifiMpdu > DoRemove(ConstIterator pos)
Wrapper for the DoRemove method provided by the base class that additionally resets the iterator fiel...
Ptr< WifiMpdu > GetOriginal(Ptr< WifiMpdu > mpdu)
Unlike the GetOriginal() method of WifiMpdu, this method returns a non-const pointer to the original ...
WifiMacQueue(AcIndex ac=AC_UNDEF)
Constructor.
Ptr< WifiMpdu > PeekFirstAvailable(uint8_t linkId, Ptr< const WifiMpdu > item=nullptr) const
Return first available packet for transmission on the given link.
void DequeueIfQueued(const std::list< Ptr< const WifiMpdu > > &mpdus)
Dequeue the given MPDUs if they are stored in this queue.
TracedCallback< Ptr< const WifiMpdu > > m_traceExpired
Traced callback: fired when a packet is dropped due to lifetime expiration.
bool DoEnqueue(ConstIterator pos, Ptr< WifiMpdu > item)
Wrapper for the DoEnqueue method provided by the base class that additionally sets the iterator field...
AcIndex m_ac
the access category
Ptr< WifiMpdu > PeekByTidAndAddress(uint8_t tid, Mac48Address dest, Ptr< const WifiMpdu > item=nullptr) const
Search and return, if present in the queue, the first packet having the receiver address equal to des...
void Flush()
Flush the queue.
void DoDequeue(const std::list< ConstIterator > &iterators)
Wrapper for the DoDequeue method provided by the base class that additionally resets the iterator fie...
void ExtractAllExpiredMpdus() const
Move MPDUs with expired lifetime from all the container queues to the container queue storing MPDUs w...
static TypeId GetTypeId()
Get the type ID.
Time GetMaxDelay() const
Return the maximum delay before the packet is discarded.
Tag used to allow (only) WifiMacQueue to access the queue iterator stored by a WifiMpdu.
Definition wifi-mpdu.h:37
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition assert.h:55
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition assert.h:75
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition queue-size.h:210
Ptr< const AttributeChecker > MakeQueueSizeChecker()
Definition queue-size.cc:18
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition nstime.h:1457
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1477
#define NS_ABORT_MSG(msg)
Unconditional abnormal program termination with a message.
Definition abort.h:38
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition abort.h:97
#define NS_ABORT_IF(cond)
Abnormal program termination if a condition is true.
Definition abort.h:65
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition log.h:225
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_TEMPLATE_CLASS_TWO_DEFINE(type, param1, param2)
Explicitly instantiate a template class with two template parameters and register the resulting insta...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
@ PACKETS
Use number of packets for queue size.
Definition queue-size.h:34
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1381
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
AcIndex
This enumeration defines the Access Categories as an enumeration with values corresponding to the AC ...
Definition qos-utils.h:62
Definition first.py:1
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::tuple< WifiContainerQueueType, WifiRcvAddr, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, receiver address type, Address, TID) identifying a container queue.