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