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 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Stefano Avallone <stavallo@unina.it>
7 */
8
9#ifndef WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
10#define WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
11
13#include "wifi-mac-queue.h"
14#include "wifi-mac.h"
15
16#include <algorithm>
17#include <functional>
18#include <iterator>
19#include <list>
20#include <map>
21#include <numeric>
22#include <sstream>
23#include <unordered_map>
24#include <vector>
25
28
29namespace ns3
30{
31
32class WifiMpdu;
33class WifiMacQueue;
34
35/**
36 * @ingroup wifi
37 *
38 * WifiMacQueueSchedulerImpl is a template class enabling the definition of
39 * different types of priority values for the container queues. The function to
40 * compare priority values can be customized as well.
41 */
42template <class Priority, class Compare = std::less<Priority>>
44{
45 public:
46 /// allow test classes access
47 friend class ::WifiMacQueueDropOldestTest;
48 friend class ::WifiMacQueueFlushTest;
49
50 /**
51 * @brief Get the type ID.
52 * @return the object TypeId
53 */
54 static TypeId GetTypeId();
55
56 /**
57 * Constructor
58 */
60
61 /** @copydoc ns3::WifiMacQueueScheduler::SetWifiMac */
62 void SetWifiMac(Ptr<WifiMac> mac) final;
63 /** @copydoc ns3::WifiMacQueueScheduler::GetNext(AcIndex,std::optional<uint8_t>,bool) */
64 std::optional<WifiContainerQueueId> GetNext(AcIndex ac,
65 std::optional<uint8_t> linkId,
66 bool skipBlockedQueues = true) final;
67 /**
68 * @copydoc ns3::WifiMacQueueScheduler::GetNext(AcIndex,std::optional<uint8_t>,
69 * const WifiContainerQueueId&,bool)
70 */
72 std::optional<uint8_t> linkId,
73 const WifiContainerQueueId& prevQueueId,
74 bool skipBlockedQueues = true) final;
75 /** @copydoc ns3::WifiMacQueueScheduler::GetLinkIds */
76 std::list<uint8_t> GetLinkIds(AcIndex ac,
77 Ptr<const WifiMpdu> mpdu,
78 const std::list<WifiQueueBlockedReason>& ignoredReasons) final;
79 /** @copydoc ns3::WifiMacQueueScheduler::BlockQueues */
81 AcIndex ac,
82 const std::list<WifiContainerQueueType>& types,
83 const Mac48Address& rxAddress,
84 const Mac48Address& txAddress,
85 const std::set<uint8_t>& tids,
86 const std::set<uint8_t>& linkIds) final;
87 /** @copydoc ns3::WifiMacQueueScheduler::UnblockQueues */
89 AcIndex ac,
90 const std::list<WifiContainerQueueType>& types,
91 const Mac48Address& rxAddress,
92 const Mac48Address& txAddress,
93 const std::set<uint8_t>& tids,
94 const std::set<uint8_t>& linkIds) final;
95 /** @copydoc ns3::WifiMacQueueScheduler::BlockAllQueues */
96 void BlockAllQueues(WifiQueueBlockedReason reason, const std::set<uint8_t>& linkIds) final;
97 /** @copydoc ns3::WifiMacQueueScheduler::UnblockAllQueues */
98 void UnblockAllQueues(WifiQueueBlockedReason reason, const std::set<uint8_t>& linkIds) final;
99 /** @copydoc ns3::WifiMacQueueScheduler::GetAllQueuesBlockedOnLink */
100 bool GetAllQueuesBlockedOnLink(uint8_t linkId, WifiQueueBlockedReason reason) final;
101 /** @copydoc ns3::WifiMacQueueScheduler::GetQueueLinkMask */
103 const WifiContainerQueueId& queueId,
104 uint8_t linkId) final;
105 /** @copydoc ns3::WifiMacQueueScheduler::HasToDropBeforeEnqueue */
107 /** @copydoc ns3::WifiMacQueueScheduler::NotifyEnqueue */
108 void NotifyEnqueue(AcIndex ac, Ptr<WifiMpdu> mpdu) final;
109 /** @copydoc ns3::WifiMacQueueScheduler::NotifyDequeue */
110 void NotifyDequeue(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) final;
111 /** @copydoc ns3::WifiMacQueueScheduler::NotifyRemove */
112 void NotifyRemove(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) final;
113
114 protected:
115 /** @copydoc ns3::Object::DoDispose */
116 void DoDispose() override;
117
118 /**
119 * Set the priority for the given container queue belonging to the given Access Category.
120 *
121 * @param ac the Access Category of the container queue
122 * @param queueId the ID of the given container queue
123 * @param priority the priority value
124 */
125 void SetPriority(AcIndex ac, const WifiContainerQueueId& queueId, const Priority& priority);
126
127 struct QueueInfo;
128
129 /**
130 * Map identifiers (QueueIds) to information associated with container queues.
131 *
132 * Empty queues shall be kept in this data structure because queue information
133 * (such as the set of link IDs) may be configured just once.
134 */
136
137 /// typedef for a QueueInfoMap element
139
140 /**
141 * List of container queues sorted in decreasing order of priority.
142 *
143 * Empty queues shall not be kept in this data structure.
144 *
145 * @note We cannot store iterators to QueueInfoMap because if rehashing occurs due
146 * to an insertion, all iterators are invalidated. References are not invalidated
147 * instead. Therefore, we store reference wrappers (which can be reassigned).
148 */
149 using SortedQueues = std::multimap<Priority, std::reference_wrapper<QueueInfoPair>, Compare>;
150
151 /**
152 * Information associated with a container queue.
153 */
155 {
156 std::optional<typename SortedQueues::iterator>
157 priorityIt; /**< iterator pointing to the entry
158 for this queue in the sorted list */
159 std::map<uint8_t, Mask> linkIds; /**< Maps ID of each link on which packets contained
160 in this queue can be sent to a bitset indicating
161 whether the link is blocked (at least one bit is
162 non-zero) and for which reason */
163 };
164
165 /**
166 * Information specific to a wifi MAC queue
167 */
169 {
170 SortedQueues sortedQueues; //!< sorted list of container queues
171 QueueInfoMap queueInfoMap; //!< information associated with container queues
172 Ptr<WifiMacQueue> wifiMacQueue; //!< pointer to the WifiMacQueue object
173 };
174
175 /**
176 * Get a const reference to the sorted list of container queues for the given
177 * Access Category.
178 *
179 * @param ac the given Access Category
180 * @return a const reference to the sorted list of container queues for the given Access
181 * Category
182 */
184
185 /**
186 * Get the wifi MAC queue associated with the given Access Category.
187 *
188 * @param ac the given Access Category
189 * @return the wifi MAC queue associated with the given Access Category
190 */
192
193 private:
194 /**
195 * If no information for the container queue used to store the given MPDU of the given
196 * Access Category is present in the queue info map, add the information for such a
197 * container queue and initialize the list of the IDs of the links over which packets
198 * contained in that container queue can be sent.
199 *
200 * @param ac the given Access Category
201 * @param mpdu the given MPDU
202 * @return an iterator to the information associated with the container queue used to
203 * store the given MPDU of the given Access Category
204 */
205 typename QueueInfoMap::iterator InitQueueInfo(AcIndex ac, Ptr<const WifiMpdu> mpdu);
206
207 /**
208 * Get the next queue to serve. The search starts from the given one. The returned queue is
209 * guaranteed to contain at least an MPDU whose lifetime has not expired. Queues containing
210 * MPDUs that cannot be sent over the given link, if any, or on any link, otherwise, are ignored
211 * if and only if <i>skipBlockedQueues</i> is true.
212 *
213 * @param ac the Access Category that we want to serve
214 * @param linkId the ID of the link on which MPDUs contained in the returned queue must be
215 * allowed to be sent
216 * @param sortedQueuesIt iterator pointing to the queue we start the search from
217 * @param skipBlockedQueues whether queues containing MPDUs that cannot be sent over the given
218 * link, if any, or on any link, otherwise, must be ignored
219 * @return the ID of the selected container queue (if any)
220 */
221 std::optional<WifiContainerQueueId> DoGetNext(AcIndex ac,
222 std::optional<uint8_t> linkId,
223 typename SortedQueues::iterator sortedQueuesIt,
224 bool skipBlockedQueues);
225
226 /**
227 * Check whether an MPDU has to be dropped before enqueuing the given MPDU.
228 *
229 * @param ac the Access Category of the MPDU being enqueued
230 * @param mpdu the MPDU to enqueue
231 * @return a pointer to the MPDU to drop, if any, or a null pointer, otherwise
232 */
234 /**
235 * Notify the scheduler that the given MPDU has been enqueued by the given Access
236 * Category. The container queue in which the MPDU has been enqueued must be
237 * assigned a priority value.
238 *
239 * @param ac the Access Category of the enqueued MPDU
240 * @param mpdu the enqueued MPDU
241 */
242 virtual void DoNotifyEnqueue(AcIndex ac, Ptr<WifiMpdu> mpdu) = 0;
243 /**
244 * Notify the scheduler that the given list of MPDUs have been dequeued by the
245 * given Access Category. The container queues which became empty after dequeuing
246 * the MPDUs are removed from the sorted list of queues.
247 *
248 * @param ac the Access Category of the dequeued MPDUs
249 * @param mpdus the list of dequeued MPDUs
250 */
251 virtual void DoNotifyDequeue(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) = 0;
252 /**
253 * Notify the scheduler that the given list of MPDUs have been removed by the
254 * given Access Category. The container queues which became empty after removing
255 * the MPDUs are removed from the sorted list of queues.
256 *
257 * @param ac the Access Category of the removed MPDUs
258 * @param mpdus the list of removed MPDUs
259 */
260 virtual void DoNotifyRemove(AcIndex ac, const std::list<Ptr<WifiMpdu>>& mpdus) = 0;
261
262 /**
263 * Block or unblock the given set of links for the container queues of the given types and
264 * Access Category that hold frames having the given Receiver Address (RA),
265 * Transmitter Address (TA) and TID (if needed) for the given reason.
266 *
267 * @param block true to block the queues, false to unblock
268 * @param reason the reason for blocking the queues
269 * @param ac the given Access Category
270 * @param types the types of the queues to block
271 * @param rxAddress the Receiver Address (RA) of the frames
272 * @param txAddress the Transmitter Address (TA) of the frames
273 * @param tids the TIDs optionally identifying the queues to block
274 * @param linkIds set of links to block (empty to block all setup links)
275 */
276 void DoBlockQueues(bool block,
278 AcIndex ac,
279 const std::list<WifiContainerQueueType>& types,
280 const Mac48Address& rxAddress,
281 const Mac48Address& txAddress,
282 const std::set<uint8_t>& tids,
283 const std::set<uint8_t>& linkIds);
284
285 /**
286 * Block or unblock the given set of links for all the container queues for the given reason.
287 *
288 * @param block true to block the queues, false to unblock
289 * @param reason the reason for blocking the queues
290 * @param linkIds set of links to block (empty to block all setup links)
291 */
292 void DoBlockAllQueues(bool block,
294 const std::set<uint8_t>& linkIds);
295
296 /**
297 * When it is requested to block all the queues, an entry is added to this map to store the
298 * reason and the IDs of the links to block. This information is used to block queues that
299 * will be created afterwards.
300 */
301 std::map<WifiQueueBlockedReason, std::set<uint8_t>> m_blockAllInfo;
302
303 std::vector<PerAcInfo> m_perAcInfo{AC_UNDEF}; //!< vector of per-AC information
304 NS_LOG_TEMPLATE_DECLARE; //!< the log component
305};
306
307/**
308 * Implementation of the templates declared above.
309 */
310
311template <class Priority, class Compare>
316
317template <class Priority, class Compare>
318TypeId
320{
321 static TypeId tid = TypeId("ns3::WifiMacQueueSchedulerImpl")
323 .SetGroupName("Wifi");
324 return tid;
325}
326
327template <class Priority, class Compare>
328void
334
335template <class Priority, class Compare>
336void
338{
339 for (auto ac : {AC_BE, AC_BK, AC_VI, AC_VO, AC_BE_NQOS, AC_BEACON})
340 {
341 if (auto queue = mac->GetTxopQueue(ac); queue != nullptr)
342 {
343 m_perAcInfo.at(ac).wifiMacQueue = queue;
344 queue->SetScheduler(this);
345 }
346 }
348}
349
350template <class Priority, class Compare>
353{
354 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
355 return m_perAcInfo.at(ac).wifiMacQueue;
356}
357
358template <class Priority, class Compare>
361{
362 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
363 return m_perAcInfo.at(ac).sortedQueues;
364}
365
366template <class Priority, class Compare>
367typename WifiMacQueueSchedulerImpl<Priority, Compare>::QueueInfoMap::iterator
369{
370 NS_LOG_FUNCTION(this << ac << *mpdu);
371
372 auto queueId = WifiMacQueueContainer::GetQueueId(mpdu);
373 // insert queueId in the queue info map if not present yet
374 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId, QueueInfo()});
375
376 // Initialize/update the set of link IDs depending on the container queue type
377 if (GetMac() && GetMac()->GetNLinks() > 1 &&
378 mpdu->GetHeader().GetAddr2() == GetMac()->GetAddress())
379 {
380 // this is an MLD and the TA field of the frame contains the MLD address,
381 // which means that the frame can be sent on multiple links
382 const auto rxAddr = mpdu->GetHeader().GetAddr1();
383
384 // this assert checks that the RA field also contain an MLD address, unless
385 // it contains the broadcast address
386 NS_ASSERT_MSG(rxAddr.IsGroup() || GetMac()->GetMldAddress(rxAddr) == rxAddr,
387 "Address 1 (" << rxAddr << ") is not an MLD address");
388
389 // this assert checks that association (ML setup) has been established
390 // between sender and receiver (unless the receiver is the broadcast address)
391 NS_ASSERT_MSG(GetMac()->CanForwardPacketsTo(rxAddr),
392 "Cannot forward frame to " << rxAddr
393 << "; check that the receiver is associated");
394 // we have to include all the links in case of broadcast frame (we are an AP)
395 // and the links that have been setup with the receiver in case of unicast frame
396 for (const auto linkId : GetMac()->GetLinkIds())
397 {
398 if (rxAddr.IsGroup() ||
399 GetMac()->GetWifiRemoteStationManager(linkId)->GetAffiliatedStaAddress(rxAddr))
400 {
401 // the mask is not modified if linkId is already in the map
402 auto [it, inserted] = queueInfoIt->second.linkIds.try_emplace(linkId);
403
404 if (inserted)
405 {
406 // linkId was not in the map, set the mask if all queues are blocked
407 for (const auto& [reason, linkIds] : m_blockAllInfo)
408 {
409 if (linkIds.contains(linkId))
410 {
411 it->second.set(static_cast<std::size_t>(reason), true);
412 }
413 }
414 }
415 }
416 else
417 {
418 // this link is no (longer) setup
419 queueInfoIt->second.linkIds.erase(linkId);
420 }
421 }
422 }
423 else
424 {
425 // the TA field of the frame contains a link address, which means that the
426 // frame can only be sent on the corresponding link
427 auto linkId = GetMac() ? GetMac()->GetLinkIdByAddress(mpdu->GetHeader().GetAddr2())
428 : SINGLE_LINK_OP_ID; // make unit test happy
429 NS_ASSERT(linkId.has_value());
430 auto& linkIdsMap = queueInfoIt->second.linkIds;
431 NS_ASSERT_MSG(linkIdsMap.size() <= 1,
432 "At most one link can be associated with this container queue");
433 // set the link map to contain one entry corresponding to the computed link ID;
434 // unless the link map already contained such an entry (in which case the mask
435 // is preserved)
436 if (linkIdsMap.empty() || linkIdsMap.cbegin()->first != *linkId)
437 {
438 Mask mask;
439 for (const auto& [reason, linkIds] : m_blockAllInfo)
440 {
441 if (linkIds.contains(*linkId))
442 {
443 mask.set(static_cast<std::size_t>(reason), true);
444 }
445 }
446
447 linkIdsMap = {{*linkId, mask}};
448 }
449 }
450
451 return queueInfoIt;
452}
453
454template <class Priority, class Compare>
455void
457 const WifiContainerQueueId& queueId,
458 const Priority& priority)
459{
460 NS_LOG_FUNCTION(this << +ac);
461 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
462
463 NS_ABORT_MSG_IF(GetWifiMacQueue(ac)->GetNBytes(queueId) == 0,
464 "Cannot set the priority of an empty queue");
465
466 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
467 NS_ASSERT_MSG(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end(),
468 "No queue info for the given container queue");
469 typename SortedQueues::iterator sortedQueuesIt;
470
471 if (queueInfoIt->second.priorityIt.has_value())
472 {
473 // an element for queueId is present in the set of sorted queues. If the priority
474 // has not changed, do nothing. Otherwise, unlink the node containing such element,
475 // change the priority and insert it back
476 if (queueInfoIt->second.priorityIt.value()->first == priority)
477 {
478 return;
479 }
480
481 auto handle = m_perAcInfo[ac].sortedQueues.extract(queueInfoIt->second.priorityIt.value());
482 handle.key() = priority;
483 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert(std::move(handle));
484 }
485 else
486 {
487 // an element for queueId is not present in the set of sorted queues
488 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert({priority, std::ref(*queueInfoIt)});
489 }
490 // update the stored iterator
491 queueInfoIt->second.priorityIt = sortedQueuesIt;
492}
493
494template <class Priority, class Compare>
495std::list<uint8_t>
497 AcIndex ac,
499 const std::list<WifiQueueBlockedReason>& ignoredReasons)
500{
501 auto queueInfoIt = InitQueueInfo(ac, mpdu);
502 std::list<uint8_t> linkIds;
503
504 // include only links that are not blocked in the returned list
505 for (auto [linkId, mask] : queueInfoIt->second.linkIds)
506 {
507 // reset the bits of the mask corresponding to the reasons to ignore
508 for (const auto reason : ignoredReasons)
509 {
510 mask.reset(static_cast<std::size_t>(reason));
511 }
512
513 if (mask.none())
514 {
515 linkIds.emplace_back(linkId);
516 }
517 }
518
519 return linkIds;
520}
521
522template <class Priority, class Compare>
523void
525 bool block,
527 AcIndex ac,
528 const std::list<WifiContainerQueueType>& types,
529 const Mac48Address& rxAddress,
530 const Mac48Address& txAddress,
531 const std::set<uint8_t>& tids,
532 const std::set<uint8_t>& linkIds)
533{
534 std::stringstream ss;
535 if (g_log.IsEnabled(ns3::LOG_FUNCTION))
536 {
537 std::copy(linkIds.cbegin(), linkIds.cend(), std::ostream_iterator<uint16_t>(ss, " "));
538 }
539 NS_LOG_FUNCTION(this << block << reason << ac << rxAddress << txAddress << ss.str());
540 std::list<WifiMacHeader> headers;
541
542 for (const auto queueType : types)
543 {
544 switch (queueType)
545 {
546 case WIFI_CTL_QUEUE:
547 headers.emplace_back(WIFI_MAC_CTL_BACKREQ);
548 break;
549 case WIFI_MGT_QUEUE:
550 headers.emplace_back(WIFI_MAC_MGT_ACTION);
551 break;
553 NS_ASSERT_MSG(!tids.empty(),
554 "TID must be specified for queues containing QoS data frames");
555 for (const auto tid : tids)
556 {
557 headers.emplace_back(WIFI_MAC_QOSDATA);
558 headers.back().SetQosTid(tid);
559 }
560 break;
561 case WIFI_DATA_QUEUE:
562 headers.emplace_back(WIFI_MAC_DATA);
563 break;
564 }
565 }
566 for (auto& hdr : headers)
567 {
568 hdr.SetAddr1(rxAddress);
569 hdr.SetAddr2(txAddress);
570
571 auto queueInfoIt = InitQueueInfo(ac, Create<WifiMpdu>(Create<Packet>(), hdr));
572 for (auto& [linkId, mask] : queueInfoIt->second.linkIds)
573 {
574 if (linkIds.empty() || linkIds.contains(linkId))
575 {
576 mask.set(static_cast<std::size_t>(reason), block);
577 }
578 }
579 }
580}
581
582template <class Priority, class Compare>
583void
586 AcIndex ac,
587 const std::list<WifiContainerQueueType>& types,
588 const Mac48Address& rxAddress,
589 const Mac48Address& txAddress,
590 const std::set<uint8_t>& tids,
591 const std::set<uint8_t>& linkIds)
592{
593 DoBlockQueues(true, reason, ac, types, rxAddress, txAddress, tids, linkIds);
594}
595
596template <class Priority, class Compare>
597void
600 AcIndex ac,
601 const std::list<WifiContainerQueueType>& types,
602 const Mac48Address& rxAddress,
603 const Mac48Address& txAddress,
604 const std::set<uint8_t>& tids,
605 const std::set<uint8_t>& linkIds)
606{
607 DoBlockQueues(false, reason, ac, types, rxAddress, txAddress, tids, linkIds);
608}
609
610template <class Priority, class Compare>
611void
614 const std::set<uint8_t>& linkIds)
615{
616 for (auto& perAcInfo : m_perAcInfo)
617 {
618 for (auto& [queueId, queueInfo] : perAcInfo.queueInfoMap)
619 {
620 for (auto& [linkId, mask] : queueInfo.linkIds)
621 {
622 if (linkIds.empty() || linkIds.contains(linkId))
623 {
624 mask.set(static_cast<std::size_t>(reason), block);
625 }
626 }
627 }
628 }
629}
630
631template <class Priority, class Compare>
632void
634 const std::set<uint8_t>& linkIds)
635{
636 DoBlockAllQueues(true, reason, linkIds);
637
638 if (linkIds.empty())
639 {
640 m_blockAllInfo[reason] = GetMac()->GetLinkIds(); // all links blocked
641 }
642 else
643 {
644 m_blockAllInfo[reason].merge(std::set<uint8_t>{linkIds});
645 }
646}
647
648template <class Priority, class Compare>
649void
651 const std::set<uint8_t>& linkIds)
652{
653 DoBlockAllQueues(false, reason, linkIds);
654
655 auto infoIt = m_blockAllInfo.find(reason);
656
657 if (infoIt == m_blockAllInfo.end())
658 {
659 return; // all queues were not blocked for the given reason
660 }
661 std::erase_if(infoIt->second,
662 [&](uint8_t id) { return linkIds.empty() || linkIds.contains(id); });
663
664 if (infoIt->second.empty())
665 {
666 // no more links blocked for the given reason
667 m_blockAllInfo.erase(infoIt);
668 }
669}
670
671template <class Priority, class Compare>
672bool
674 uint8_t linkId,
676{
677 for (const auto& [r, linkIds] : m_blockAllInfo)
678 {
679 if ((reason == WifiQueueBlockedReason::REASONS_COUNT || reason == r) &&
680 linkIds.contains(linkId))
681 {
682 return true;
683 }
684 }
685 return false;
686}
687
688template <class Priority, class Compare>
689std::optional<WifiMacQueueScheduler::Mask>
691 const WifiContainerQueueId& queueId,
692 uint8_t linkId)
693{
694 NS_LOG_FUNCTION(this << +ac << +linkId);
695
696 const auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
697
698 if (queueInfoIt == m_perAcInfo[ac].queueInfoMap.cend())
699 {
700 // the given container queue does not exist
701 return std::nullopt;
702 }
703
704 const auto& linkIds = queueInfoIt->second.linkIds;
705 if (const auto linkIt = linkIds.find(linkId); linkIt != linkIds.cend())
706 {
707 return linkIt->second;
708 }
709
710 return std::nullopt;
711}
712
713template <class Priority, class Compare>
714std::optional<WifiContainerQueueId>
716 std::optional<uint8_t> linkId,
717 bool skipBlockedQueues)
718{
719 NS_LOG_FUNCTION(this << +ac << linkId.has_value() << skipBlockedQueues);
720 return DoGetNext(ac, linkId, m_perAcInfo[ac].sortedQueues.begin(), skipBlockedQueues);
721}
722
723template <class Priority, class Compare>
724std::optional<WifiContainerQueueId>
726 std::optional<uint8_t> linkId,
727 const WifiContainerQueueId& prevQueueId,
728 bool skipBlockedQueues)
729{
730 NS_LOG_FUNCTION(this << +ac << linkId.has_value() << skipBlockedQueues);
731
732 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(prevQueueId);
733 NS_ABORT_IF(queueInfoIt == m_perAcInfo[ac].queueInfoMap.end() ||
734 !queueInfoIt->second.priorityIt.has_value());
735
736 auto sortedQueuesIt = queueInfoIt->second.priorityIt.value();
737 NS_ABORT_IF(sortedQueuesIt == m_perAcInfo[ac].sortedQueues.end());
738
739 return DoGetNext(ac, linkId, ++sortedQueuesIt, skipBlockedQueues);
740}
741
742template <class Priority, class Compare>
743std::optional<WifiContainerQueueId>
745 AcIndex ac,
746 std::optional<uint8_t> linkId,
747 typename SortedQueues::iterator sortedQueuesIt,
748 bool skipBlockedQueues)
749{
750 NS_LOG_FUNCTION(this << +ac << linkId.has_value() << skipBlockedQueues);
751 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
752
753 while (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
754 {
755 const auto& queueInfoPair = sortedQueuesIt->second.get();
756 const auto& linkIds = queueInfoPair.second.linkIds;
757 typename std::decay_t<decltype(linkIds)>::const_iterator linkIt;
758
759 if (!skipBlockedQueues ||
760 std::any_of(linkIds.cbegin(), linkIds.cend(), [&linkId](const auto& linkIdMask) {
761 return (!linkId.has_value() || linkId == linkIdMask.first) &&
762 linkIdMask.second.none();
763 }))
764 {
765 // Remove packets with expired lifetime from this queue.
766 // In case the queue becomes empty, the queue is removed from the sorted
767 // list and sortedQueuesIt is invalidated; thus, store an iterator to the
768 // previous queue in the sorted list (if any) to resume the search afterwards.
769 std::optional<typename SortedQueues::iterator> prevQueueIt;
770 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.begin())
771 {
772 prevQueueIt = std::prev(sortedQueuesIt);
773 }
774
775 const auto queueId = queueInfoPair.first;
776 GetWifiMacQueue(ac)->ExtractExpiredMpdus(queueId);
777
778 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
779 {
780 auto nextQueueIt = (prevQueueIt.has_value() ? std::next(prevQueueIt.value())
781 : m_perAcInfo[ac].sortedQueues.begin());
782 // the container queue may be empty but it may not have been removed yet from the
783 // sorted list. This may happen because the scheduler is notified after that packets
784 // are dequeued and there may be a callback connected to the Dequeue trace source
785 // that calls this function. In such a case, nextQueueIt actually points to the same
786 // queue as sortedQueuesIt. The iterator is advanced to avoid an infinite loop.
787 if (nextQueueIt != m_perAcInfo[ac].sortedQueues.end() &&
788 nextQueueIt->second.get().first == queueId)
789 {
790 sortedQueuesIt = std::next(nextQueueIt);
791 }
792 else
793 {
794 sortedQueuesIt = nextQueueIt;
795 }
796 continue;
797 }
798 return queueInfoPair.first;
799 }
800
801 sortedQueuesIt++;
802 }
803 return {};
804}
805
806template <class Priority, class Compare>
809{
810 NS_LOG_FUNCTION(this << +ac << *mpdu);
811 return HasToDropBeforeEnqueuePriv(ac, mpdu);
812}
813
814template <class Priority, class Compare>
815void
817{
818 NS_LOG_FUNCTION(this << +ac << *mpdu);
819 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
820
821 // add information for the queue storing the MPDU to the queue info map, if not present yet
822 auto queueInfoIt = InitQueueInfo(ac, mpdu);
823
824 DoNotifyEnqueue(ac, mpdu);
825
826 if (!queueInfoIt->second.priorityIt.has_value())
827 {
829 "No info for the queue the MPDU was stored into (forgot to call SetPriority()?)");
830 }
831}
832
833template <class Priority, class Compare>
834void
836 const std::list<Ptr<WifiMpdu>>& mpdus)
837{
838 NS_LOG_FUNCTION(this << +ac);
839 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
840
841 DoNotifyDequeue(ac, mpdus);
842
843 std::list<WifiContainerQueueId> queueIds;
844
845 for (const auto& mpdu : mpdus)
846 {
847 queueIds.push_back(WifiMacQueueContainer::GetQueueId(mpdu));
848 }
849
850 for (const auto& queueId : queueIds)
851 {
852 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
853 {
854 // The queue has now become empty and needs to be removed from the sorted
855 // list kept by the scheduler
856 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
857 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
858 if (queueInfoIt->second.priorityIt.has_value())
859 {
860 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
861 queueInfoIt->second.priorityIt.reset();
862 }
863 }
864 }
865}
866
867template <class Priority, class Compare>
868void
870 const std::list<Ptr<WifiMpdu>>& mpdus)
871{
872 NS_LOG_FUNCTION(this << +ac);
873 NS_ASSERT(static_cast<uint8_t>(ac) < AC_UNDEF);
874
875 DoNotifyRemove(ac, mpdus);
876
877 std::list<WifiContainerQueueId> queueIds;
878
879 for (const auto& mpdu : mpdus)
880 {
881 queueIds.push_back(WifiMacQueueContainer::GetQueueId(mpdu));
882 }
883
884 for (const auto& queueId : queueIds)
885 {
886 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
887 {
888 // The queue has now become empty and needs to be removed from the sorted
889 // list kept by the scheduler
890 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
891 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
892 if (queueInfoIt->second.priorityIt.has_value())
893 {
894 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
895 queueInfoIt->second.priorityIt.reset();
896 }
897 }
898 }
899}
900
901} // namespace ns3
902
903#endif /* WIFI_MAC_QUEUE_SCHEDULER_IMPL_H */
Test DROP_OLDEST setting.
Test that a wifi MAC queue is correctly flushed even if (at least) a container queue is blocked.
an EUI-48 address
Smart pointer class similar to boost::intrusive_ptr.
a unique identifier for an interface.
Definition type-id.h:49
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
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.
std::bitset< static_cast< std::size_t >(WifiQueueBlockedReason::REASONS_COUNT)> Mask
Bitset identifying the reasons to block individual links for a container queue.
void DoDispose() override
Destructor implementation.
WifiMacQueueSchedulerImpl is a template class enabling the definition of different types of priority ...
void DoBlockQueues(bool block, WifiQueueBlockedReason reason, AcIndex ac, const std::list< WifiContainerQueueType > &types, const Mac48Address &rxAddress, const Mac48Address &txAddress, const std::set< uint8_t > &tids, const std::set< uint8_t > &linkIds)
Block or unblock the given set of links for the container queues of the given types and Access Catego...
void UnblockQueues(WifiQueueBlockedReason reason, AcIndex ac, const std::list< WifiContainerQueueType > &types, const Mac48Address &rxAddress, const Mac48Address &txAddress, const std::set< uint8_t > &tids, const std::set< uint8_t > &linkIds) final
Unblock the given set of links for the container queues of the given types and Access Category that h...
std::optional< WifiContainerQueueId > DoGetNext(AcIndex ac, std::optional< uint8_t > linkId, typename SortedQueues::iterator sortedQueuesIt, bool skipBlockedQueues)
Get the next queue to serve.
std::pair< const WifiContainerQueueId, QueueInfo > QueueInfoPair
typedef for a QueueInfoMap element
std::optional< Mask > GetQueueLinkMask(AcIndex ac, const WifiContainerQueueId &queueId, uint8_t linkId) final
Get the mask associated with the given container queue indicating whether the given link is blocked a...
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.
void UnblockAllQueues(WifiQueueBlockedReason reason, const std::set< uint8_t > &linkIds) final
Unblock the given set of links for all the container queues for the given reason.
std::unordered_map< WifiContainerQueueId, QueueInfo > QueueInfoMap
Map identifiers (QueueIds) to information associated with container queues.
std::optional< WifiContainerQueueId > GetNext(AcIndex ac, std::optional< uint8_t > linkId, bool skipBlockedQueues=true) final
Get the next queue to serve, which is guaranteed to contain at least an MPDU whose lifetime has not e...
void NotifyEnqueue(AcIndex ac, Ptr< WifiMpdu > mpdu) final
Notify the scheduler that the given MPDU has been enqueued by the given Access Category.
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.
void BlockQueues(WifiQueueBlockedReason reason, AcIndex ac, const std::list< WifiContainerQueueType > &types, const Mac48Address &rxAddress, const Mac48Address &txAddress, const std::set< uint8_t > &tids, const std::set< uint8_t > &linkIds) final
Block the given set of links for the container queues of the given types and Access Category that hol...
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.
static TypeId GetTypeId()
Get the type ID.
void DoBlockAllQueues(bool block, WifiQueueBlockedReason reason, const std::set< uint8_t > &linkIds)
Block or unblock the given set of links for all the container queues for the given reason.
std::vector< PerAcInfo > m_perAcInfo
vector of per-AC information
bool GetAllQueuesBlockedOnLink(uint8_t linkId, WifiQueueBlockedReason reason) final
Return whether all the container queues are blocked for the given link for the given reason,...
std::map< WifiQueueBlockedReason, std::set< uint8_t > > m_blockAllInfo
When it is requested to block all the queues, an entry is added to this map to store the reason and t...
std::list< uint8_t > GetLinkIds(AcIndex ac, Ptr< const WifiMpdu > mpdu, const std::list< WifiQueueBlockedReason > &ignoredReasons) final
Get the list of the IDs of the links the given MPDU (belonging to the given Access Category) can be s...
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.
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.
QueueInfoMap::iterator InitQueueInfo(AcIndex ac, Ptr< const WifiMpdu > mpdu)
If no information for the container queue used to store the given MPDU of the given Access Category i...
std::multimap< Priority, std::reference_wrapper< QueueInfoPair >, Compare > SortedQueues
List of container queues sorted in decreasing order of priority.
void BlockAllQueues(WifiQueueBlockedReason reason, const std::set< uint8_t > &linkIds) final
Block the given set of links for all the container queues for the given reason.
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.
WifiMpdu stores a (const) packet along with a MAC header.
Definition wifi-mpdu.h:51
#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_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition log.h:225
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Ptr< T > Create(Ts &&... args)
Create class instances by constructors with varying numbers of arguments and return them by Ptr.
Definition ptr.h:439
WifiQueueBlockedReason
Enumeration of the reasons to block container queues.
AcIndex
This enumeration defines the Access Categories as an enumeration with values corresponding to the AC ...
Definition qos-utils.h:62
@ AC_BE_NQOS
Non-QoS.
Definition qos-utils.h:72
@ AC_BE
Best Effort.
Definition qos-utils.h:64
@ AC_VO
Voice.
Definition qos-utils.h:70
@ AC_VI
Video.
Definition qos-utils.h:68
@ AC_BK
Background.
Definition qos-utils.h:66
@ AC_UNDEF
Total number of ACs.
Definition qos-utils.h:76
@ AC_BEACON
Beacon queue.
Definition qos-utils.h:74
Every class exported by the ns3 library is enclosed in the ns3 namespace.
static constexpr uint8_t SINGLE_LINK_OP_ID
Link ID for single link operations (helps tracking places where correct link ID is to be used to supp...
Definition wifi-utils.h:280
@ WIFI_MAC_CTL_BACKREQ
@ WIFI_MAC_MGT_ACTION
@ WIFI_MAC_DATA
@ WIFI_MAC_QOSDATA
WifiContainerQueueType
enumeration of container queue types
std::tuple< WifiContainerQueueType, WifiRcvAddr, Mac48Address, std::optional< uint8_t > > WifiContainerQueueId
Tuple (queue type, receiver address type, Address, TID) identifying a container queue.
@ LOG_FUNCTION
Function tracing for non-trivial function calls.
Definition log.h:95
STL namespace.
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::map< uint8_t, Mask > linkIds
Maps ID of each link on which packets contained in this queue can be sent to a bitset indicating whet...
std::optional< typename SortedQueues::iterator > priorityIt
iterator pointing to the entry for this queue in the sorted list