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 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Authors: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19 * Mirko Banchi <mk.banchi@gmail.com>
20 * Stefano Avallone <stavallo@unina.it>
21 */
22
23#include "wifi-mac-queue.h"
24
27
28#include "ns3/simulator.h"
29
30#include <functional>
31
32namespace ns3
33{
34
35NS_LOG_COMPONENT_DEFINE("WifiMacQueue");
36
37NS_OBJECT_ENSURE_REGISTERED(WifiMacQueue);
38NS_OBJECT_TEMPLATE_CLASS_TWO_DEFINE(Queue, WifiMpdu, WifiMacQueueContainer);
39
40TypeId
42{
43 static TypeId tid =
44 TypeId("ns3::WifiMacQueue")
46 .SetGroupName("Wifi")
47 .AddConstructor<WifiMacQueue>()
48 .AddAttribute("MaxSize",
49 "The max queue size",
51 MakeQueueSizeAccessor(&QueueBase::SetMaxSize, &QueueBase::GetMaxSize),
52 MakeQueueSizeChecker())
53 .AddAttribute("MaxDelay",
54 "If a packet stays longer than this delay in the queue, it is dropped.",
58 .AddTraceSource("Expired",
59 "MPDU dropped because its lifetime expired.",
61 "ns3::WifiMpdu::TracedCallback");
62 return tid;
63}
64
66 : m_ac(ac),
67 NS_LOG_TEMPLATE_DEFINE("WifiMacQueue")
68{
69}
70
72{
74}
75
76void
78{
79 NS_LOG_FUNCTION(this);
80 m_scheduler = nullptr;
82}
83
86{
87 return m_ac;
88}
89
92{
93 NS_ASSERT(mpdu->IsQueued());
94 return mpdu->GetQueueIt(WmqIteratorTag());
95}
96
99{
100 return GetIt(mpdu)->mpdu;
101}
102
103void
105{
106 NS_LOG_FUNCTION(this);
107
108 std::list<Ptr<WifiMpdu>> mpdus;
109 auto [first, last] = GetContainer().ExtractExpiredMpdus(queueId);
110
111 for (auto it = first; it != last; it++)
112 {
113 mpdus.push_back(it->mpdu);
114 }
115 for (const auto& mpdu : mpdus)
116 {
117 // fire the Expired trace
119 }
120 // notify the scheduler
121 if (!mpdus.empty())
122 {
123 m_scheduler->NotifyRemove(m_ac, mpdus);
124 }
125}
126
127void
129{
130 NS_LOG_FUNCTION(this);
131
132 std::list<Ptr<WifiMpdu>> mpdus;
133 auto [first, last] = GetContainer().ExtractAllExpiredMpdus();
134
135 for (auto it = first; it != last; it++)
136 {
137 mpdus.push_back(it->mpdu);
138 }
139 for (const auto& mpdu : mpdus)
140 {
141 // fire the Expired trace
143 }
144 // notify the scheduler
145 if (!mpdus.empty())
146 {
147 m_scheduler->NotifyRemove(m_ac, mpdus);
148 }
149}
150
151void
153{
154 NS_LOG_FUNCTION(this);
155
157
158 auto [first, last] = GetContainer().GetAllExpiredMpdus();
159
160 for (auto it = first; it != last;)
161 {
162 // the scheduler has been notified and the Expired trace has been fired
163 // when the MPDU was extracted from its queue. The only thing left to do
164 // is to update the Queue base class statistics by calling Queue::DoRemove
165 auto curr = it++;
167 }
168}
169
170bool
172{
173 NS_ASSERT(item && item->IsQueued());
174 auto it = GetIt(item);
175 if (now > it->expiryTime)
176 {
177 NS_LOG_DEBUG("Removing packet that stayed in the queue for too long (queuing time="
178 << now - it->expiryTime + m_maxDelay << ")");
180 return true;
181 }
182 return false;
183}
184
185void
187{
188 NS_LOG_FUNCTION(this << scheduler);
189 m_scheduler = scheduler;
190}
191
192void
194{
195 NS_LOG_FUNCTION(this << delay);
196 m_maxDelay = delay;
197}
198
199Time
201{
202 return m_maxDelay;
203}
204
205bool
207{
208 NS_LOG_FUNCTION(this << *item);
209
210 auto queueId = WifiMacQueueContainer::GetQueueId(item);
211 return Insert(GetContainer().GetQueue(queueId).cend(), item);
212}
213
214bool
215WifiMacQueue::Insert(ConstIterator pos, Ptr<WifiMpdu> item)
216{
217 NS_LOG_FUNCTION(this << *item);
219 "WifiMacQueues must be in packet mode");
220
221 // insert the item if the queue is not full
222 if (QueueBase::GetNPackets() < GetMaxSize().GetValue())
223 {
224 return DoEnqueue(pos, item);
225 }
226
227 // the queue is full; try to make some room by removing stale packets
228 auto queueId = WifiMacQueueContainer::GetQueueId(item);
229
230 if (pos != GetContainer().GetQueue(queueId).cend())
231 {
233 "pos must point to an element in the same container queue as item");
234 if (pos->expiryTime <= Simulator::Now())
235 {
236 // the element pointed to by pos is stale and will be removed along with all of
237 // its predecessors; the new item will be enqueued at the front of the queue
238 pos = GetContainer().GetQueue(queueId).cbegin();
239 }
240 }
241
243
244 return DoEnqueue(pos, item);
245}
246
249{
250 // An MPDU is dequeued when either is acknowledged or is dropped, hence a Dequeue
251 // method without an argument makes no sense.
252 NS_ABORT_MSG("Not implemented by WifiMacQueue");
253 return nullptr;
254}
255
256void
258{
259 NS_LOG_FUNCTION(this);
260
261 std::list<ConstIterator> iterators;
262
263 for (const auto& mpdu : mpdus)
264 {
265 if (mpdu->IsQueued())
266 {
267 auto it = GetIt(mpdu);
268 NS_ASSERT(it->ac == m_ac);
269 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
270 iterators.emplace_back(it);
271 }
272 }
273
274 DoDequeue(iterators);
275}
276
279{
280 // Need to specify the link ID
281 NS_ABORT_MSG("Not implemented by WifiMacQueue");
282 return nullptr;
283}
284
286WifiMacQueue::Peek(uint8_t linkId) const
287{
288 NS_LOG_FUNCTION(this);
289
290 auto queueId = m_scheduler->GetNext(m_ac, linkId);
291
292 if (!queueId.has_value())
293 {
294 NS_LOG_DEBUG("The queue is empty");
295 return nullptr;
296 }
297
298 return GetContainer().GetQueue(queueId.value()).cbegin()->mpdu;
299}
300
303{
304 NS_LOG_FUNCTION(this << +tid << dest << item);
305 NS_ABORT_IF(dest.IsGroup());
307 return PeekByQueueId(queueId, item);
308}
309
312{
313 NS_LOG_FUNCTION(this << item);
314 NS_ASSERT(!item || (item->IsQueued() && WifiMacQueueContainer::GetQueueId(item) == queueId));
315
316 // Remove MPDUs with expired lifetime if we are looking for the first MPDU in the queue
317 if (!item)
318 {
319 ExtractExpiredMpdus(queueId);
320 }
321
322 ConstIterator it = (item ? std::next(GetIt(item)) : GetContainer().GetQueue(queueId).cbegin());
323
324 if (it == GetContainer().GetQueue(queueId).cend())
325 {
326 NS_LOG_DEBUG("The queue is empty");
327 return nullptr;
328 }
329
330 return it->mpdu;
331}
332
335 const Ptr<QosBlockedDestinations> blockedPackets,
336 Ptr<const WifiMpdu> item) const
337{
338 NS_LOG_FUNCTION(this << +linkId << item);
339 NS_ASSERT(!item || item->IsQueued());
340
341 if (item)
342 {
343 NS_ASSERT(!item->GetHeader().IsQosData() || !blockedPackets ||
344 !blockedPackets->IsBlocked(item->GetHeader().GetAddr1(),
345 item->GetHeader().GetQosTid()));
346 // check if there are other MPDUs in the same container queue as item
347 auto mpdu = PeekByQueueId(WifiMacQueueContainer::GetQueueId(item), item);
348
349 if (mpdu)
350 {
351 return mpdu;
352 }
353 }
354
355 std::optional<WifiContainerQueueId> queueId;
356
357 if (item)
358 {
359 queueId = m_scheduler->GetNext(m_ac, linkId, WifiMacQueueContainer::GetQueueId(item));
360 }
361 else
362 {
363 queueId = m_scheduler->GetNext(m_ac, linkId);
364 }
365
366 NS_ASSERT(!queueId || std::get<0>(*queueId) != WIFI_QOSDATA_UNICAST_QUEUE ||
367 std::get<2>(*queueId));
368
369 while (queueId.has_value() && blockedPackets &&
370 std::get<0>(queueId.value()) == WIFI_QOSDATA_UNICAST_QUEUE &&
371 blockedPackets->IsBlocked(std::get<1>(queueId.value()), *std::get<2>(queueId.value())))
372 {
373 queueId = m_scheduler->GetNext(m_ac, linkId, queueId.value());
374
375 NS_ASSERT(!queueId || std::get<0>(*queueId) != WIFI_QOSDATA_UNICAST_QUEUE ||
376 std::get<2>(*queueId));
377 }
378
379 if (!queueId.has_value())
380 {
381 NS_LOG_DEBUG("The queue is empty");
382 return nullptr;
383 }
384
385 return GetContainer().GetQueue(queueId.value()).cbegin()->mpdu;
386}
387
390{
391 return Remove(Peek(0));
392}
393
396{
397 NS_LOG_FUNCTION(this << mpdu);
398 NS_ASSERT(mpdu && mpdu->IsQueued());
399 auto it = GetIt(mpdu);
400 NS_ASSERT(it->ac == m_ac);
401 NS_ASSERT(it->mpdu == mpdu->GetOriginal());
402
403 return DoRemove(it);
404}
405
406void
408{
409 NS_LOG_FUNCTION(this << *currentItem << *newItem);
410 NS_ASSERT(currentItem->IsQueued());
411 auto currentIt = GetIt(currentItem);
412 NS_ASSERT(currentIt->ac == m_ac);
413 NS_ASSERT(currentIt->mpdu == currentItem->GetOriginal());
414 NS_ASSERT(!newItem->IsQueued());
415
416 Time expiryTime = currentIt->expiryTime;
417 auto pos = std::next(currentIt);
418 DoDequeue({currentIt});
419 bool ret = Insert(pos, newItem);
420 GetIt(newItem)->expiryTime = expiryTime;
421 // The size of a WifiMacQueue is measured as number of packets. We dequeued
422 // one packet, so there is certainly room for inserting one packet
423 NS_ABORT_IF(!ret);
424}
425
428{
429 return GetContainer().GetQueue(queueId).size();
430}
431
434{
435 return GetContainer().GetNBytes(queueId);
436}
437
438bool
440{
441 NS_LOG_FUNCTION(this << *item);
442
443 auto currSize = GetMaxSize();
444 // control frames should not consume room in the MAC queue, so increase queue size
445 // if we are trying to enqueue a control frame
446 if (item->GetHeader().IsCtl())
447 {
448 SetMaxSize(currSize + item);
449 }
450 auto mpdu = m_scheduler->HasToDropBeforeEnqueue(m_ac, item);
451
452 if (mpdu == item)
453 {
454 // the given item must be dropped
455 SetMaxSize(currSize);
456 return false;
457 }
458
459 auto queueId = WifiMacQueueContainer::GetQueueId(item);
460 if (pos != GetContainer().GetQueue(queueId).cend() && mpdu && pos->mpdu == mpdu->GetOriginal())
461 {
462 // the element pointed to by pos must be dropped; update insert position
463 pos = std::next(pos);
464 }
465 if (mpdu)
466 {
467 DoRemove(GetIt(mpdu));
468 }
469
470 Iterator ret;
472 {
473 // set item's information about its position in the queue
474 item->SetQueueIt(ret, {});
475 ret->ac = m_ac;
476 ret->expiryTime = item->GetHeader().IsCtl() ? Time::Max() : Simulator::Now() + m_maxDelay;
477 WmqIteratorTag tag;
478 ret->deleter = [tag](auto mpdu) { mpdu->SetQueueIt(std::nullopt, tag); };
479
480 m_scheduler->NotifyEnqueue(m_ac, item);
481 return true;
482 }
483 SetMaxSize(currSize);
484 return false;
485}
486
487void
488WifiMacQueue::DoDequeue(const std::list<ConstIterator>& iterators)
489{
490 NS_LOG_FUNCTION(this);
491
492 std::list<Ptr<WifiMpdu>> items;
493
494 // First, dequeue all the items
495 for (auto& it : iterators)
496 {
498 {
499 items.push_back(item);
500 if (item->GetHeader().IsCtl())
501 {
502 SetMaxSize(GetMaxSize() - item);
503 }
504 }
505 }
506
507 // Then, notify the scheduler
508 if (!items.empty())
509 {
510 m_scheduler->NotifyDequeue(m_ac, items);
511 }
512}
513
515WifiMacQueue::DoRemove(ConstIterator pos)
516{
517 NS_LOG_FUNCTION(this);
518
520
521 if (item)
522 {
523 if (item->GetHeader().IsCtl())
524 {
525 SetMaxSize(GetMaxSize() - item);
526 }
527 m_scheduler->NotifyRemove(m_ac, {item});
528 }
529
530 return item;
531}
532
533} // namespace ns3
an EUI-48 address
Definition: mac48-address.h:46
bool IsGroup() const
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:78
QueueSize GetMaxSize() const
Definition: queue.cc:217
uint32_t GetNBytes() const
Definition: queue.cc:98
uint32_t GetNPackets() const
Definition: queue.cc:90
void SetMaxSize(QueueSize size)
Set the maximum size of this queue.
Definition: queue.cc:200
Template class for packet Queues.
Definition: queue.h:267
Ptr< Item > DoRemove(ConstIterator pos)
Pull the item to drop from the queue.
Definition: queue.h:575
void DoDispose() override
Destructor implementation.
Definition: queue.h:618
const ns3::WifiMacQueueContainer & GetContainer() const
Get a const reference to the container of queue items.
Definition: queue.h:503
Container::iterator Iterator
Iterator.
Definition: queue.h:320
Container::const_iterator ConstIterator
Const iterator.
Definition: queue.h:318
Class for representing queue sizes.
Definition: queue-size.h:96
AttributeValue implementation for QueueSize.
static Time Now()
Return the current simulation virtual time.
Definition: simulator.cc:199
static EventId ScheduleNow(FUNC f, Ts &&... args)
Schedule an event to expire Now.
Definition: simulator.h:606
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:105
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition: nstime.h:296
AttributeValue implementation for Time.
Definition: nstime.h:1423
a unique identifier for an interface.
Definition: type-id.h:60
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:935
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 > 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.
void DequeueIfQueued(const std::list< Ptr< const WifiMpdu > > &mpdus)
Dequeue the given MPDUs if they are stored in this queue.
Ptr< WifiMpdu > PeekFirstAvailable(uint8_t linkId, const Ptr< QosBlockedDestinations > blockedPackets=nullptr, Ptr< const WifiMpdu > item=nullptr) const
Return first available packet for transmission on the given link.
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 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:47
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:66
#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:86
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition: nstime.h:1444
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition: nstime.h:1424
#define NS_ABORT_MSG(msg)
Unconditional abnormal program termination with a message.
Definition: abort.h:49
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition: abort.h:108
#define NS_ABORT_IF(cond)
Abnormal program termination if a condition is true.
Definition: abort.h:76
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition: log.h:236
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#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...
Definition: object-base.h:116
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
@ PACKETS
Use number of packets for queue size.
Definition: queue-size.h:45
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1348
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:72
Definition: first.py:1
Every class exported by the ns3 library is enclosed in the ns3 namespace.
@ WIFI_QOSDATA_UNICAST_QUEUE
std::tuple< WifiContainerQueueType, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, Address, TID) identifying a container queue.