A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
wifi-mac-queue-scheduler-impl.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2022 Universita' degli Studi di Napoli Federico II
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation;
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 *
17 * Author: Stefano Avallone <stavallo@unina.it>
18 */
19
20#ifndef WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
21#define WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
22
24#include "wifi-mac-queue.h"
25#include "wifi-mac.h"
26
27#include <functional>
28#include <list>
29#include <map>
30#include <numeric>
31#include <unordered_map>
32#include <vector>
33
35
36namespace ns3
37{
38
39class WifiMpdu;
40class WifiMacQueue;
41
49template <class Priority, class Compare = std::less<Priority>>
51{
52 public:
54 friend class ::WifiMacQueueDropOldestTest;
55
60 static TypeId GetTypeId();
61
66
68 void SetWifiMac(Ptr<WifiMac> mac) final;
70 std::optional<WifiContainerQueueId> GetNext(AcIndex ac, uint8_t linkId) final;
72 std::optional<WifiContainerQueueId> GetNext(AcIndex ac,
73 uint8_t linkId,
74 const WifiContainerQueueId& prevQueueId) final;
76 std::list<uint8_t> GetLinkIds(AcIndex ac, const WifiContainerQueueId& queueId) final;
79 const WifiContainerQueueId& queueId,
80 const std::list<uint8_t>& linkIds) final;
84 void NotifyEnqueue(AcIndex ac, Ptr<WifiMpdu> mpdu) final;
86 void NotifyDequeue(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) final;
88 void NotifyRemove(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) final;
89
90 protected:
92 void DoDispose() override;
93
101 void SetPriority(AcIndex ac, const WifiContainerQueueId& queueId, const Priority& priority);
102
103 struct QueueInfo;
104
111 using QueueInfoMap = std::unordered_map<WifiContainerQueueId, QueueInfo>;
112
114 using QueueInfoPair = std::pair<const WifiContainerQueueId, QueueInfo>;
115
125 using SortedQueues = std::multimap<Priority, std::reference_wrapper<QueueInfoPair>, Compare>;
126
131 {
132 std::optional<typename SortedQueues::iterator>
135 std::list<uint8_t> linkIds;
138 };
139
144 {
148 };
149
159
167
168 private:
179 typename QueueInfoMap::iterator InitQueueInfo(AcIndex ac, const WifiContainerQueueId& queueId);
180
191 std::optional<WifiContainerQueueId> DoGetNext(AcIndex ac,
192 uint8_t linkId,
193 typename SortedQueues::iterator sortedQueuesIt);
194
211 virtual void DoNotifyEnqueue(AcIndex ac, Ptr<WifiMpdu> mpdu) = 0;
220 virtual void DoNotifyDequeue(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) = 0;
229 virtual void DoNotifyRemove(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) = 0;
230
231 std::vector<PerAcInfo> m_perAcInfo{AC_UNDEF};
233};
234
239template <class Priority, class Compare>
241 : NS_LOG_TEMPLATE_DEFINE("WifiMacQueueScheduler")
242{
243}
244
245template <class Priority, class Compare>
246TypeId
248{
249 static TypeId tid = TypeId("ns3::WifiMacQueueSchedulerImpl")
251 .SetGroupName("Wifi");
252 return tid;
253}
254
255template <class Priority, class Compare>
256void
258{
259 m_perAcInfo.clear();
261}
262
263template <class Priority, class Compare>
264void
266{
267 for (auto ac : {AC_BE, AC_BK, AC_VI, AC_VO, AC_BE_NQOS, AC_BEACON})
268 {
269 if (auto queue = mac->GetTxopQueue(ac); queue != nullptr)
270 {
271 m_perAcInfo.at(ac).wifiMacQueue = queue;
272 queue->SetScheduler(this);
273 }
274 }
276}
277
278template <class Priority, class Compare>
281{
282 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
283 return m_perAcInfo.at(ac).wifiMacQueue;
284}
285
286template <class Priority, class Compare>
289{
290 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
291 return m_perAcInfo.at(ac).sortedQueues;
292}
293
294template <class Priority, class Compare>
297 const WifiContainerQueueId& queueId)
298{
299 NS_LOG_FUNCTION(this);
300
301 // insert queueId in the queue info map if not present yet
302 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId, QueueInfo()});
303
304 if (ret)
305 {
306 // The given queueid has just been inserted in the queue info map.
307 // Initialize the set of link IDs depending on the container queue type
308 auto queueType = std::get<WifiContainerQueueType>(queueId);
309 auto address = std::get<Mac48Address>(queueId);
310
311 if (queueType == WIFI_MGT_QUEUE ||
312 (queueType == WIFI_CTL_QUEUE && GetMac() && address != GetMac()->GetAddress()) ||
313 queueType == WIFI_QOSDATA_BROADCAST_QUEUE)
314 {
315 // these queue types are associated with just one link
316 NS_ASSERT(GetMac());
317 auto linkId = GetMac()->GetLinkIdByAddress(address);
318 NS_ASSERT(linkId.has_value());
319 queueInfoIt->second.linkIds = {*linkId};
320 }
321 }
322 return queueInfoIt;
323}
324
325template <class Priority, class Compare>
326void
328 const WifiContainerQueueId& queueId,
329 const Priority& priority)
330{
331 NS_LOG_FUNCTION(this << +ac);
332 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
333
334 NS_ABORT_MSG_IF(GetWifiMacQueue(ac)->GetNBytes(queueId) == 0,
335 "Cannot set the priority of an empty queue");
336
337 // insert queueId in the queue info map if not present yet
338 auto queueInfoIt = InitQueueInfo(ac, queueId);
339 typename SortedQueues::iterator sortedQueuesIt;
340
341 if (queueInfoIt->second.priorityIt.has_value())
342 {
343 // an element for queueId is present in the set of sorted queues. If the priority
344 // has not changed, do nothing. Otherwise, unlink the node containing such element,
345 // change the priority and insert it back
346 if (queueInfoIt->second.priorityIt.value()->first == priority)
347 {
348 return;
349 }
350
351 auto handle = m_perAcInfo[ac].sortedQueues.extract(queueInfoIt->second.priorityIt.value());
352 handle.key() = priority;
353 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert(std::move(handle));
354 }
355 else
356 {
357 // an element for queueId is not present in the set of sorted queues
358 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert({priority, std::ref(*queueInfoIt)});
359 }
360 // update the stored iterator
361 queueInfoIt->second.priorityIt = sortedQueuesIt;
362}
363
364template <class Priority, class Compare>
365std::list<uint8_t>
367 const WifiContainerQueueId& queueId)
368{
369 auto queueInfoIt = InitQueueInfo(ac, queueId);
370
371 if (queueInfoIt->second.linkIds.empty())
372 {
373 // return the IDs of all available links
374 NS_ASSERT(GetMac() != nullptr);
375 std::list<uint8_t> linkIds(GetMac()->GetNLinks());
376 std::iota(linkIds.begin(), linkIds.end(), 0);
377 return linkIds;
378 }
379 return queueInfoIt->second.linkIds;
380}
381
382template <class Priority, class Compare>
383void
385 const WifiContainerQueueId& queueId,
386 const std::list<uint8_t>& linkIds)
387{
388 NS_LOG_FUNCTION(this << +ac);
389 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId, QueueInfo()});
390 queueInfoIt->second.linkIds = linkIds;
391}
392
393template <class Priority, class Compare>
394std::optional<WifiContainerQueueId>
396{
397 NS_LOG_FUNCTION(this << +ac << +linkId);
398 return DoGetNext(ac, linkId, m_perAcInfo[ac].sortedQueues.begin());
399}
400
401template <class Priority, class Compare>
402std::optional<WifiContainerQueueId>
404 uint8_t linkId,
405 const WifiContainerQueueId& prevQueueId)
406{
407 NS_LOG_FUNCTION(this << +ac << +linkId);
408
409 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(prevQueueId);
410 NS_ABORT_IF(queueInfoIt == m_perAcInfo[ac].queueInfoMap.end() ||
411 !queueInfoIt->second.priorityIt.has_value());
412
413 auto sortedQueuesIt = queueInfoIt->second.priorityIt.value();
414 NS_ABORT_IF(sortedQueuesIt == m_perAcInfo[ac].sortedQueues.end());
415
416 return DoGetNext(ac, linkId, ++sortedQueuesIt);
417}
418
419template <class Priority, class Compare>
420std::optional<WifiContainerQueueId>
422 AcIndex ac,
423 uint8_t linkId,
424 typename SortedQueues::iterator sortedQueuesIt)
425{
426 NS_LOG_FUNCTION(this << +ac << +linkId);
427 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
428
429 while (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
430 {
431 const auto& queueInfoPair = sortedQueuesIt->second.get();
432 const auto& linkIds = queueInfoPair.second.linkIds;
433
434 if (linkIds.empty() || std::find(linkIds.begin(), linkIds.end(), linkId) != linkIds.end())
435 {
436 // Packets in this queue can be sent over the link we got channel access on.
437 // Now remove packets with expired lifetime from this queue.
438 // In case the queue becomes empty, the queue is removed from the sorted
439 // list and sortedQueuesIt is invalidated; thus, store an iterator to the
440 // previous queue in the sorted list (if any) to resume the search afterwards.
441 std::optional<typename SortedQueues::iterator> prevQueueIt;
442 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.begin())
443 {
444 prevQueueIt = std::prev(sortedQueuesIt);
445 }
446
447 GetWifiMacQueue(ac)->ExtractExpiredMpdus(queueInfoPair.first);
448
449 if (GetWifiMacQueue(ac)->GetNBytes(queueInfoPair.first) == 0)
450 {
451 sortedQueuesIt = (prevQueueIt.has_value() ? std::next(prevQueueIt.value())
452 : m_perAcInfo[ac].sortedQueues.begin());
453 continue;
454 }
455 break;
456 }
457
458 sortedQueuesIt++;
459 }
460
461 std::optional<WifiContainerQueueId> queueId;
462
463 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
464 {
465 queueId = sortedQueuesIt->second.get().first;
466 }
467 return queueId;
468}
469
470template <class Priority, class Compare>
473{
474 NS_LOG_FUNCTION(this << +ac << *mpdu);
475 return HasToDropBeforeEnqueuePriv(ac, mpdu);
476}
477
478template <class Priority, class Compare>
479void
481{
482 NS_LOG_FUNCTION(this << +ac << *mpdu);
483 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
484
485 DoNotifyEnqueue(ac, mpdu);
486
487 if (auto queueInfoIt =
488 m_perAcInfo[ac].queueInfoMap.find(WifiMacQueueContainer::GetQueueId(mpdu));
489 queueInfoIt == m_perAcInfo[ac].queueInfoMap.end() ||
490 !queueInfoIt->second.priorityIt.has_value())
491 {
493 "No info for the queue the MPDU was stored into (forgot to call SetPriority()?)");
494 }
495}
496
497template <class Priority, class Compare>
498void
500 const std::list<Ptr<WifiMpdu>>& mpdus)
501{
502 NS_LOG_FUNCTION(this << +ac);
503 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
504
505 DoNotifyDequeue(ac, mpdus);
506
507 std::list<WifiContainerQueueId> queueIds;
508
509 for (const auto& mpdu : mpdus)
510 {
511 queueIds.push_back(WifiMacQueueContainer::GetQueueId(mpdu));
512 }
513
514 for (const auto& queueId : queueIds)
515 {
516 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
517 {
518 // The queue has now become empty and needs to be removed from the sorted
519 // list kept by the scheduler
520 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
521 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
522 if (queueInfoIt->second.priorityIt.has_value())
523 {
524 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
525 queueInfoIt->second.priorityIt.reset();
526 }
527 }
528 }
529}
530
531template <class Priority, class Compare>
532void
534 const std::list<Ptr<WifiMpdu>>& mpdus)
535{
536 NS_LOG_FUNCTION(this << +ac);
537 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
538
539 DoNotifyRemove(ac, mpdus);
540
541 std::list<WifiContainerQueueId> queueIds;
542
543 for (const auto& mpdu : mpdus)
544 {
545 queueIds.push_back(WifiMacQueueContainer::GetQueueId(mpdu));
546 }
547
548 for (const auto& queueId : queueIds)
549 {
550 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
551 {
552 // The queue has now become empty and needs to be removed from the sorted
553 // list kept by the scheduler
554 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
555 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
556 if (queueInfoIt->second.priorityIt.has_value())
557 {
558 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
559 queueInfoIt->second.priorityIt.reset();
560 }
561 }
562 }
563}
564
565} // namespace ns3
566
567#endif /* WIFI_MAC_QUEUE_SCHEDULER_IMPL_H */
Test DROP_OLDEST setting.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:78
a unique identifier for an interface.
Definition: type-id.h:60
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:935
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.
WifiMacQueueScheduler is an abstract base class defining the public interface for a wifi MAC queue sc...
virtual void SetWifiMac(Ptr< WifiMac > mac)
Set the wifi MAC.
void DoDispose() override
Destructor implementation.
WifiMacQueueSchedulerImpl is a template class enabling the definition of different types of priority ...
std::pair< const WifiContainerQueueId, QueueInfo > QueueInfoPair
typedef for a QueueInfoMap element
void SetWifiMac(Ptr< WifiMac > mac) final
Set the wifi MAC.
void DoDispose() override
Destructor implementation.
void NotifyDequeue(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus) final
Notify the scheduler that the given list of MPDUs have been dequeued by the given Access Category.
std::unordered_map< WifiContainerQueueId, QueueInfo > QueueInfoMap
Map identifiers (QueueIds) to information associated with container queues.
std::optional< WifiContainerQueueId > GetNext(AcIndex ac, uint8_t linkId, const WifiContainerQueueId &prevQueueId) final
Get the next queue to serve after the given one.
void NotifyEnqueue(AcIndex ac, Ptr< WifiMpdu > mpdu) final
Notify the scheduler that the given MPDU has been enqueued by the given Access Category.
QueueInfoMap::iterator InitQueueInfo(AcIndex ac, const WifiContainerQueueId &queueId)
Add the information associated with the given container queue (if not already present) to the map cor...
virtual void DoNotifyDequeue(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus)=0
Notify the scheduler that the given list of MPDUs have been dequeued by the given Access Category.
virtual void DoNotifyEnqueue(AcIndex ac, Ptr< WifiMpdu > mpdu)=0
Notify the scheduler that the given MPDU has been enqueued by the given Access Category.
Ptr< WifiMacQueue > GetWifiMacQueue(AcIndex ac) const
Get the wifi MAC queue associated with the given Access Category.
void SetLinkIds(AcIndex ac, const WifiContainerQueueId &queueId, const std::list< uint8_t > &linkIds) final
Set the list of the IDs of the links the given container queue (belonging to the given Access Categor...
static TypeId GetTypeId()
Get the type ID.
std::optional< WifiContainerQueueId > DoGetNext(AcIndex ac, uint8_t linkId, typename SortedQueues::iterator sortedQueuesIt)
Get the next queue to serve.
std::vector< PerAcInfo > m_perAcInfo
vector of per-AC information
const SortedQueues & GetSortedQueues(AcIndex ac) const
Get a const reference to the sorted list of container queues for the given Access Category.
Ptr< WifiMpdu > HasToDropBeforeEnqueue(AcIndex ac, Ptr< WifiMpdu > mpdu) final
Check whether an MPDU has to be dropped before enqueuing the given MPDU.
std::list< uint8_t > GetLinkIds(AcIndex ac, const WifiContainerQueueId &queueId) final
Get the list of the IDs of the links the given container queue (belonging to the given Access Categor...
void NotifyRemove(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus) final
Notify the scheduler that the given list of MPDUs have been removed by the given Access Category.
virtual Ptr< WifiMpdu > HasToDropBeforeEnqueuePriv(AcIndex ac, Ptr< WifiMpdu > mpdu)=0
Check whether an MPDU has to be dropped before enqueuing the given MPDU.
std::optional< WifiContainerQueueId > GetNext(AcIndex ac, uint8_t linkId) final
Get the next queue to serve, which is guaranteed to contain at least an MPDU whose lifetime has not e...
std::multimap< Priority, std::reference_wrapper< QueueInfoPair >, Compare > SortedQueues
List of container queues sorted in decreasing order of priority.
virtual void DoNotifyRemove(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus)=0
Notify the scheduler that the given list of MPDUs have been removed by the given Access Category.
void SetPriority(AcIndex ac, const WifiContainerQueueId &queueId, const Priority &priority)
Set the priority for the given container queue belonging to the given Access Category.
#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_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_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition: log.h:236
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
AcIndex
This enumeration defines the Access Categories as an enumeration with values corresponding to the AC ...
Definition: qos-utils.h:72
@ AC_BE_NQOS
Non-QoS.
Definition: qos-utils.h:82
@ AC_BE
Best Effort.
Definition: qos-utils.h:74
@ AC_VO
Voice.
Definition: qos-utils.h:80
@ AC_VI
Video.
Definition: qos-utils.h:78
@ AC_BK
Background.
Definition: qos-utils.h:76
@ AC_UNDEF
Total number of ACs.
Definition: qos-utils.h:86
@ AC_BEACON
Beacon queue.
Definition: qos-utils.h:84
Every class exported by the ns3 library is enclosed in the ns3 namespace.
@ WIFI_QOSDATA_BROADCAST_QUEUE
std::tuple< WifiContainerQueueType, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, Address, TID) identifying a container queue.
Information specific to a wifi MAC queue.
SortedQueues sortedQueues
sorted list of container queues
Ptr< WifiMacQueue > wifiMacQueue
pointer to the WifiMacQueue object
QueueInfoMap queueInfoMap
information associated with container queues
Information associated with a container queue.
std::list< uint8_t > linkIds
IDs of the links over which packets contained in this queue can be sent over.
std::optional< typename SortedQueues::iterator > priorityIt
iterator pointing to the entry for this queue in the sorted list