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>
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.
Definition ptr.h:67
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.
This queue implements the timeout procedure described in (Section 9.19.2.6 "Retransmit procedures" pa...
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.
Ptr< WifiMac > GetMac() const
Get 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.
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
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
void SetWifiMac(Ptr< WifiMac > mac) final
Set the wifi MAC.
void NotifyDequeue(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus) final
void UnblockAllQueues(WifiQueueBlockedReason reason, const std::set< uint8_t > &linkIds) final
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
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
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
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
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
void NotifyRemove(AcIndex ac, const std::list< Ptr< WifiMpdu > > &mpdus) final
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
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 FcfsPrio &priority)
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:63
@ AC_BE_NQOS
Non-QoS.
Definition qos-utils.h:73
@ AC_BE
Best Effort.
Definition qos-utils.h:65
@ AC_VO
Voice.
Definition qos-utils.h:71
@ AC_VI
Video.
Definition qos-utils.h:69
@ AC_BK
Background.
Definition qos-utils.h:67
@ AC_UNDEF
Total number of ACs.
Definition qos-utils.h:77
@ AC_BEACON
Beacon queue.
Definition qos-utils.h:75
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.
#define list
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