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.IsGroup());
321 return PeekByQueueId(queueId, item);
322}
323
326{
327 NS_LOG_FUNCTION(this << item);
328 NS_ASSERT(!item || (item->IsQueued() && WifiMacQueueContainer::GetQueueId(item) == queueId));
329
330 // Remove MPDUs with expired lifetime if we are looking for the first MPDU in the queue
331 if (!item)
332 {
333 ExtractExpiredMpdus(queueId);
334 }
335
336 auto it = (item ? std::next(GetIt(item)) : GetContainer().GetQueue(queueId).cbegin());
337
338 if (it == GetContainer().GetQueue(queueId).cend())
339 {
340 NS_LOG_DEBUG("The queue is empty");
341 return nullptr;
342 }
343
344 return it->mpdu;
345}
346
349{
350 NS_LOG_FUNCTION(this << +linkId << item);
351 NS_ASSERT(!item || item->IsQueued());
352
353 if (item)
354 {
355 // check if there are other MPDUs in the same container queue as item
356 auto mpdu = PeekByQueueId(WifiMacQueueContainer::GetQueueId(item), item);
357
358 if (mpdu)
359 {
360 return mpdu;
361 }
362 }
363
364 std::optional<WifiContainerQueueId> queueId;
365
366 if (item)
367 {
368 queueId = m_scheduler->GetNext(m_ac, linkId, WifiMacQueueContainer::GetQueueId(item));
369 }
370 else
371 {
372 queueId = m_scheduler->GetNext(m_ac, linkId);
373 }
374
375 if (!queueId.has_value())
376 {
377 NS_LOG_DEBUG("The queue is empty");
378 return nullptr;
379 }
380
381 return GetContainer().GetQueue(queueId.value()).cbegin()->mpdu;
382}
383
386{
387 return Remove(Peek());
388}
389
392{
393 NS_LOG_FUNCTION(this << mpdu);
394 NS_ASSERT(mpdu && mpdu->IsQueued());
395 auto it = GetIt(mpdu);
396 NS_ASSERT(it->ac == m_ac);
397 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
398
399 return DoRemove(it);
400}
401
402void
404{
405 NS_LOG_FUNCTION(this);
406
407 // there may be some expired MPDUs in the container queue storing MPDUs with expired lifetime,
408 // which will not be flushed by the Flush() method of the base class.
411}
412
413void
415{
416 NS_LOG_FUNCTION(this << *currentItem << *newItem);
417 NS_ASSERT(currentItem->IsQueued());
418 auto currentIt = GetIt(currentItem);
419 NS_ASSERT(currentIt->ac == m_ac);
420 NS_ASSERT(currentIt->mpdu == currentItem->GetOriginal());
421 NS_ASSERT(!newItem->IsQueued());
422
423 Time expiryTime = currentIt->expiryTime;
424 auto pos = std::next(currentIt);
425 DoDequeue({currentIt});
426 bool ret = Insert(pos, newItem);
427 GetIt(newItem)->expiryTime = expiryTime;
428 // The size of a WifiMacQueue is measured as number of packets. We dequeued
429 // one packet, so there is certainly room for inserting one packet
430 NS_ABORT_IF(!ret);
431}
432
435{
436 return GetContainer().GetQueue(queueId).size();
437}
438
441{
442 return GetContainer().GetNBytes(queueId);
443}
444
445bool
447{
448 NS_LOG_FUNCTION(this << *item);
449
450 auto currSize = GetMaxSize();
451 // control frames should not consume room in the MAC queue, so increase queue size
452 // if we are trying to enqueue a control frame
453 if (item->GetHeader().IsCtl())
454 {
455 SetMaxSize(currSize + item);
456 }
457 auto mpdu = m_scheduler->HasToDropBeforeEnqueue(m_ac, item);
458
459 if (mpdu == item)
460 {
461 // the given item must be dropped
462 SetMaxSize(currSize);
463 return false;
464 }
465
466 auto queueId = WifiMacQueueContainer::GetQueueId(item);
467 if (pos != GetContainer().GetQueue(queueId).cend() && mpdu && pos->mpdu == mpdu->GetOriginal())
468 {
469 // the element pointed to by pos must be dropped; update insert position
470 pos = std::next(pos);
471 }
472 if (mpdu)
473 {
474 DoRemove(GetIt(mpdu));
475 }
476
477 Iterator ret;
479 {
480 // set item's information about its position in the queue
481 item->SetQueueIt(ret, {});
482 ret->ac = m_ac;
483 ret->expiryTime = item->GetHeader().IsCtl() ? Time::Max() : Simulator::Now() + m_maxDelay;
484 WmqIteratorTag tag;
485 ret->deleter = [tag](auto mpdu) { mpdu->SetQueueIt(std::nullopt, tag); };
486
487 m_scheduler->NotifyEnqueue(m_ac, item);
488 return true;
489 }
490 SetMaxSize(currSize);
491 return false;
492}
493
494void
495WifiMacQueue::DoDequeue(const std::list<ConstIterator>& iterators)
496{
497 NS_LOG_FUNCTION(this);
498
499 std::list<Ptr<WifiMpdu>> items;
500
501 // First, dequeue all the items
502 for (auto& it : iterators)
503 {
505 {
506 items.push_back(item);
507 if (item->GetHeader().IsCtl())
508 {
509 SetMaxSize(GetMaxSize() - item);
510 }
511 }
512 }
513
514 // Then, notify the scheduler
515 if (!items.empty())
516 {
517 m_scheduler->NotifyDequeue(m_ac, items);
518 }
519}
520
522WifiMacQueue::DoRemove(ConstIterator pos)
523{
524 NS_LOG_FUNCTION(this);
525
527
528 if (item)
529 {
530 if (item->GetHeader().IsCtl())
531 {
532 SetMaxSize(GetMaxSize() - item);
533 }
534 m_scheduler->NotifyRemove(m_ac, {item});
535 }
536
537 return item;
538}
539
540} // namespace ns3
an EUI-48 address
bool IsGroup() 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
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:594
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition nstime.h:286
a unique identifier for an interface.
Definition type-id.h:48
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
#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:1320
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.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition queue-size.h:210
std:: tuple< WifiContainerQueueType, WifiReceiverAddressType, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, receiver address type, Address, TID) identifying a container queue.
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition nstime.h:1396
Ptr< const AttributeChecker > MakeQueueSizeChecker()
Definition queue-size.cc:18
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416