9#ifndef WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
10#define WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
23#include <unordered_map>
42template <
class Priority,
class Compare = std::less<Priority>>
47 friend class ::WifiMacQueueDropOldestTest;
48 friend class ::WifiMacQueueFlushTest;
65 std::optional<uint8_t> linkId,
66 bool skipBlockedQueues =
true) final;
72 std::optional<uint8_t> linkId,
74 bool skipBlockedQueues = true) final;
85 const
std::set<uint8_t>& tids,
86 const
std::set<uint8_t>& linkIds) final;
93 const
std::set<uint8_t>& tids,
94 const
std::set<uint8_t>& linkIds) final;
104 uint8_t linkId) final;
156 std::optional<typename SortedQueues::iterator>
222 std::optional<uint8_t> linkId,
223 typename SortedQueues::iterator sortedQueuesIt,
224 bool skipBlockedQueues);
279 const std::list<WifiContainerQueueType>& types,
282 const std::set<uint8_t>& tids,
283 const std::set<uint8_t>& linkIds);
294 const std::set<uint8_t>& linkIds);
311template <
class Priority,
class Compare>
317template <
class Priority,
class Compare>
321 static TypeId tid =
TypeId(
"ns3::WifiMacQueueSchedulerImpl")
323 .SetGroupName(
"Wifi");
327template <
class Priority,
class Compare>
335template <
class Priority,
class Compare>
341 if (
auto queue = mac->GetTxopQueue(ac); queue !=
nullptr)
343 m_perAcInfo.at(ac).wifiMacQueue = queue;
344 queue->SetScheduler(
this);
350template <
class Priority,
class Compare>
355 return m_perAcInfo.at(ac).wifiMacQueue;
358template <
class Priority,
class Compare>
363 return m_perAcInfo.at(ac).sortedQueues;
366template <
class Priority,
class Compare>
367typename WifiMacQueueSchedulerImpl<Priority, Compare>::QueueInfoMap::iterator
374 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId,
QueueInfo()});
377 if (GetMac() && GetMac()->GetNLinks() > 1 &&
378 mpdu->GetHeader().GetAddr2() == GetMac()->GetAddress())
382 const auto rxAddr = mpdu->GetHeader().GetAddr1();
386 NS_ASSERT_MSG(rxAddr.IsGroup() || GetMac()->GetMldAddress(rxAddr) == rxAddr,
387 "Address 1 (" << rxAddr <<
") is not an MLD address");
392 "Cannot forward frame to " << rxAddr
393 <<
"; check that the receiver is associated");
396 for (
const auto linkId : GetMac()->GetLinkIds())
398 if (rxAddr.IsGroup() ||
399 GetMac()->GetWifiRemoteStationManager(linkId)->GetAffiliatedStaAddress(rxAddr))
402 auto [it, inserted] = queueInfoIt->second.linkIds.try_emplace(linkId);
407 for (
const auto& [reason, linkIds] : m_blockAllInfo)
409 if (linkIds.contains(linkId))
411 it->second.set(
static_cast<std::size_t
>(reason),
true);
419 queueInfoIt->second.linkIds.erase(linkId);
427 auto linkId = GetMac() ? GetMac()->GetLinkIdByAddress(mpdu->GetHeader().GetAddr2())
430 auto& linkIdsMap = queueInfoIt->second.linkIds;
432 "At most one link can be associated with this container queue");
436 if (linkIdsMap.empty() || linkIdsMap.cbegin()->first != *linkId)
439 for (
const auto& [reason, linkIds] : m_blockAllInfo)
441 if (linkIds.contains(*linkId))
443 mask.set(
static_cast<std::size_t
>(reason),
true);
447 linkIdsMap = {{*linkId, mask}};
454template <
class Priority,
class Compare>
458 const Priority& priority)
464 "Cannot set the priority of an empty queue");
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;
471 if (queueInfoIt->second.priorityIt.has_value())
476 if (queueInfoIt->second.priorityIt.value()->first == priority)
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));
488 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert({priority, std::ref(*queueInfoIt)});
491 queueInfoIt->second.priorityIt = sortedQueuesIt;
494template <
class Priority,
class Compare>
499 const std::list<WifiQueueBlockedReason>& ignoredReasons)
501 auto queueInfoIt = InitQueueInfo(ac, mpdu);
502 std::list<uint8_t> linkIds;
505 for (
auto [linkId, mask] : queueInfoIt->second.linkIds)
508 for (
const auto reason : ignoredReasons)
510 mask.reset(
static_cast<std::size_t
>(reason));
515 linkIds.emplace_back(linkId);
522template <
class Priority,
class Compare>
528 const std::list<WifiContainerQueueType>& types,
531 const std::set<uint8_t>& tids,
532 const std::set<uint8_t>& linkIds)
534 std::stringstream ss;
537 std::copy(linkIds.cbegin(), linkIds.cend(), std::ostream_iterator<uint16_t>(ss,
" "));
539 NS_LOG_FUNCTION(
this << block << reason << ac << rxAddress << txAddress << ss.str());
540 std::list<WifiMacHeader> headers;
542 for (
const auto queueType : types)
554 "TID must be specified for queues containing QoS data frames");
555 for (
const auto tid : tids)
558 headers.back().SetQosTid(tid);
566 for (
auto& hdr : headers)
568 hdr.SetAddr1(rxAddress);
569 hdr.SetAddr2(txAddress);
572 for (
auto& [linkId, mask] : queueInfoIt->second.linkIds)
574 if (linkIds.empty() || linkIds.contains(linkId))
576 mask.set(
static_cast<std::size_t
>(reason), block);
582template <
class Priority,
class Compare>
587 const std::list<WifiContainerQueueType>& types,
590 const std::set<uint8_t>& tids,
591 const std::set<uint8_t>& linkIds)
593 DoBlockQueues(
true, reason, ac, types, rxAddress, txAddress, tids, linkIds);
596template <
class Priority,
class Compare>
601 const std::list<WifiContainerQueueType>& types,
604 const std::set<uint8_t>& tids,
605 const std::set<uint8_t>& linkIds)
607 DoBlockQueues(
false, reason, ac, types, rxAddress, txAddress, tids, linkIds);
610template <
class Priority,
class Compare>
614 const std::set<uint8_t>& linkIds)
616 for (
auto& perAcInfo : m_perAcInfo)
618 for (
auto& [queueId, queueInfo] : perAcInfo.queueInfoMap)
620 for (
auto& [linkId, mask] : queueInfo.linkIds)
622 if (linkIds.empty() || linkIds.contains(linkId))
624 mask.set(
static_cast<std::size_t
>(reason), block);
631template <
class Priority,
class Compare>
634 const std::set<uint8_t>& linkIds)
636 DoBlockAllQueues(
true, reason, linkIds);
640 m_blockAllInfo[reason] = GetMac()->GetLinkIds();
644 m_blockAllInfo[reason].merge(std::set<uint8_t>{linkIds});
648template <
class Priority,
class Compare>
651 const std::set<uint8_t>& linkIds)
653 DoBlockAllQueues(
false, reason, linkIds);
655 auto infoIt = m_blockAllInfo.find(reason);
657 if (infoIt == m_blockAllInfo.end())
661 std::erase_if(infoIt->second,
662 [&](uint8_t
id) { return linkIds.empty() || linkIds.contains(id); });
664 if (infoIt->second.empty())
667 m_blockAllInfo.erase(infoIt);
671template <
class Priority,
class Compare>
677 for (
const auto& [r, linkIds] : m_blockAllInfo)
680 linkIds.contains(linkId))
688template <
class Priority,
class Compare>
689std::optional<WifiMacQueueScheduler::Mask>
696 const auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
698 if (queueInfoIt == m_perAcInfo[ac].queueInfoMap.cend())
704 const auto& linkIds = queueInfoIt->second.linkIds;
705 if (
const auto linkIt = linkIds.find(linkId); linkIt != linkIds.cend())
707 return linkIt->second;
713template <
class Priority,
class Compare>
714std::optional<WifiContainerQueueId>
716 std::optional<uint8_t> linkId,
717 bool skipBlockedQueues)
719 NS_LOG_FUNCTION(
this << +ac << linkId.has_value() << skipBlockedQueues);
720 return DoGetNext(ac, linkId, m_perAcInfo[ac].sortedQueues.begin(), skipBlockedQueues);
723template <
class Priority,
class Compare>
724std::optional<WifiContainerQueueId>
726 std::optional<uint8_t> linkId,
728 bool skipBlockedQueues)
730 NS_LOG_FUNCTION(
this << +ac << linkId.has_value() << skipBlockedQueues);
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());
736 auto sortedQueuesIt = queueInfoIt->second.priorityIt.value();
737 NS_ABORT_IF(sortedQueuesIt == m_perAcInfo[ac].sortedQueues.end());
739 return DoGetNext(ac, linkId, ++sortedQueuesIt, skipBlockedQueues);
742template <
class Priority,
class Compare>
743std::optional<WifiContainerQueueId>
746 std::optional<uint8_t> linkId,
747 typename SortedQueues::iterator sortedQueuesIt,
748 bool skipBlockedQueues)
750 NS_LOG_FUNCTION(
this << +ac << linkId.has_value() << skipBlockedQueues);
753 while (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
755 const auto& queueInfoPair = sortedQueuesIt->second.get();
756 const auto& linkIds = queueInfoPair.second.linkIds;
757 typename std::decay_t<
decltype(linkIds)>::const_iterator linkIt;
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();
769 std::optional<typename SortedQueues::iterator> prevQueueIt;
770 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.begin())
772 prevQueueIt = std::prev(sortedQueuesIt);
775 const auto queueId = queueInfoPair.first;
776 GetWifiMacQueue(ac)->ExtractExpiredMpdus(queueId);
778 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
780 auto nextQueueIt = (prevQueueIt.has_value() ? std::next(prevQueueIt.value())
781 : m_perAcInfo[ac].sortedQueues.begin());
787 if (nextQueueIt != m_perAcInfo[ac].sortedQueues.end() &&
788 nextQueueIt->second.get().first == queueId)
790 sortedQueuesIt = std::next(nextQueueIt);
794 sortedQueuesIt = nextQueueIt;
798 return queueInfoPair.first;
806template <
class Priority,
class Compare>
811 return HasToDropBeforeEnqueuePriv(ac, mpdu);
814template <
class Priority,
class Compare>
822 auto queueInfoIt = InitQueueInfo(ac, mpdu);
824 DoNotifyEnqueue(ac, mpdu);
826 if (!queueInfoIt->second.priorityIt.has_value())
829 "No info for the queue the MPDU was stored into (forgot to call SetPriority()?)");
833template <
class Priority,
class Compare>
841 DoNotifyDequeue(ac, mpdus);
843 std::list<WifiContainerQueueId> queueIds;
845 for (
const auto& mpdu : mpdus)
850 for (
const auto& queueId : queueIds)
852 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
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())
860 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
861 queueInfoIt->second.priorityIt.reset();
867template <
class Priority,
class Compare>
875 DoNotifyRemove(ac, mpdus);
877 std::list<WifiContainerQueueId> queueIds;
879 for (
const auto& mpdu : mpdus)
884 for (
const auto& queueId : queueIds)
886 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
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())
894 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
895 queueInfoIt->second.priorityIt.reset();
Test DROP_OLDEST setting.
Test that a wifi MAC queue is correctly flushed even if (at least) a container queue is blocked.
Smart pointer class similar to boost::intrusive_ptr.
a unique identifier for an interface.
TypeId SetParent(TypeId tid)
Set the parent TypeId.
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
NS_LOG_TEMPLATE_DECLARE
the log component
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.
WifiMacQueueSchedulerImpl()
Constructor.
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.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
#define NS_ABORT_MSG(msg)
Unconditional abnormal program termination with a message.
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
#define NS_ABORT_IF(cond)
Abnormal program termination if a condition is true.
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
#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.
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 ...
@ AC_UNDEF
Total number of ACs.
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...
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.
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