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 return Remove(Peek());
391}
392
395{
396 NS_LOG_FUNCTION(this << mpdu);
397 NS_ASSERT(mpdu && mpdu->IsQueued());
398 auto it = GetIt(mpdu);
399 NS_ASSERT(it->ac == m_ac);
400 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
401
402 return DoRemove(it);
403}
404
405void
407{
408 NS_LOG_FUNCTION(this);
409
410 // there may be some expired MPDUs in the container queue storing MPDUs with expired lifetime,
411 // which will not be flushed by the Flush() method of the base class.
414}
415
416void
418{
419 NS_LOG_FUNCTION(this << *currentItem << *newItem);
420 NS_ASSERT(currentItem->IsQueued());
421 auto currentIt = GetIt(currentItem);
422 NS_ASSERT(currentIt->ac == m_ac);
423 NS_ASSERT(currentIt->mpdu == currentItem->GetOriginal());
424 NS_ASSERT(!newItem->IsQueued());
425
426 Time expiryTime = currentIt->expiryTime;
427 auto pos = std::next(currentIt);
428 DoDequeue({currentIt});
429 bool ret = Insert(pos, newItem);
430 GetIt(newItem)->expiryTime = expiryTime;
431 // The size of a WifiMacQueue is measured as number of packets. We dequeued
432 // one packet, so there is certainly room for inserting one packet
433 NS_ABORT_IF(!ret);
434}
435
438{
439 return GetContainer().GetQueue(queueId).size();
440}
441
444{
445 return GetContainer().GetNBytes(queueId);
446}
447
448bool
450{
451 NS_LOG_FUNCTION(this << *item);
452
453 auto currSize = GetMaxSize();
454 // control frames should not consume room in the MAC queue, so increase queue size
455 // if we are trying to enqueue a control frame
456 if (item->GetHeader().IsCtl())
457 {
458 SetMaxSize(currSize + item);
459 }
460 auto mpdu = m_scheduler->HasToDropBeforeEnqueue(m_ac, item);
461
462 if (mpdu == item)
463 {
464 // the given item must be dropped
465 SetMaxSize(currSize);
466 return false;
467 }
468
469 auto queueId = WifiMacQueueContainer::GetQueueId(item);
470 if (pos != GetContainer().GetQueue(queueId).cend() && mpdu && pos->mpdu == mpdu->GetOriginal())
471 {
472 // the element pointed to by pos must be dropped; update insert position
473 pos = std::next(pos);
474 }
475 if (mpdu)
476 {
477 DoRemove(GetIt(mpdu));
478 }
479
480 Iterator ret;
482 {
483 // set item's information about its position in the queue
484 item->SetQueueIt(ret, {});
485 ret->ac = m_ac;
486 ret->expiryTime = item->GetHeader().IsCtl() ? Time::Max() : Simulator::Now() + m_maxDelay;
487 WmqIteratorTag tag;
488 ret->deleter = [tag](auto mpdu) { mpdu->SetQueueIt(std::nullopt, tag); };
489
490 m_scheduler->NotifyEnqueue(m_ac, item);
491 return true;
492 }
493 SetMaxSize(currSize);
494 return false;
495}
496
497void
498WifiMacQueue::DoDequeue(const std::list<ConstIterator>& iterators)
499{
500 NS_LOG_FUNCTION(this);
501
502 std::list<Ptr<WifiMpdu>> items;
503
504 // First, dequeue all the items
505 for (auto& it : iterators)
506 {
508 {
509 items.push_back(item);
510 if (item->GetHeader().IsCtl())
511 {
512 SetMaxSize(GetMaxSize() - item);
513 }
514 }
515 }
516
517 // Then, notify the scheduler
518 if (!items.empty())
519 {
520 m_scheduler->NotifyDequeue(m_ac, items);
521 }
522}
523
525WifiMacQueue::DoRemove(ConstIterator pos)
526{
527 NS_LOG_FUNCTION(this);
528
530
531 if (item)
532 {
533 if (item->GetHeader().IsCtl())
534 {
535 SetMaxSize(GetMaxSize() - item);
536 }
537 m_scheduler->NotifyRemove(m_ac, {item});
538 }
539
540 return item;
541}
542
543} // 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: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
AttributeValue implementation for Time.
Definition nstime.h:1431
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
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:1432
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1452
#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:1356
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, WifiReceiverAddressType, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, receiver address type, Address, TID) identifying a container queue.