9#ifndef WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
10#define WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
23#include <unordered_map>
41template <
class Priority,
class Compare = std::less<Priority>>
46 friend class ::WifiMacQueueDropOldestTest;
62 std::optional<WifiContainerQueueId>
GetNext(
AcIndex ac, std::optional<uint8_t> linkId)
final;
68 std::optional<uint8_t> linkId,
73 const std::list<WifiQueueBlockedReason>& ignoredReasons)
final;
77 const std::list<WifiContainerQueueType>& types,
80 const std::set<uint8_t>& tids,
81 const std::set<uint8_t>& linkIds)
final;
85 const std::list<WifiContainerQueueType>& types,
88 const std::set<uint8_t>& tids,
89 const std::set<uint8_t>& linkIds)
final;
93 uint8_t linkId)
final;
124 using QueueInfoMap = std::unordered_map<WifiContainerQueueId, QueueInfo>;
138 using SortedQueues = std::multimap<Priority, std::reference_wrapper<QueueInfoPair>, Compare>;
145 std::optional<typename SortedQueues::iterator>
208 std::optional<uint8_t> linkId,
209 typename SortedQueues::iterator sortedQueuesIt);
264 const std::list<WifiContainerQueueType>& types,
267 const std::set<uint8_t>& tids,
268 const std::set<uint8_t>& linkIds);
278template <
class Priority,
class Compare>
284template <
class Priority,
class Compare>
288 static TypeId tid =
TypeId(
"ns3::WifiMacQueueSchedulerImpl")
290 .SetGroupName(
"Wifi");
294template <
class Priority,
class Compare>
302template <
class Priority,
class Compare>
308 if (
auto queue = mac->GetTxopQueue(ac); queue !=
nullptr)
310 m_perAcInfo.at(ac).wifiMacQueue = queue;
311 queue->SetScheduler(
this);
317template <
class Priority,
class Compare>
322 return m_perAcInfo.at(ac).wifiMacQueue;
325template <
class Priority,
class Compare>
330 return m_perAcInfo.at(ac).sortedQueues;
333template <
class Priority,
class Compare>
334typename WifiMacQueueSchedulerImpl<Priority, Compare>::QueueInfoMap::iterator
341 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId,
QueueInfo()});
344 if (GetMac() && GetMac()->GetNLinks() > 1 &&
345 mpdu->GetHeader().GetAddr2() == GetMac()->GetAddress())
349 const auto rxAddr = mpdu->GetHeader().GetAddr1();
353 NS_ASSERT_MSG(rxAddr.IsGroup() || GetMac()->GetMldAddress(rxAddr) == rxAddr,
354 "Address 1 (" << rxAddr <<
") is not an MLD address");
359 "Cannot forward frame to " << rxAddr
360 <<
"; check that the receiver is associated");
363 for (
const auto linkId : GetMac()->GetLinkIds())
365 if (rxAddr.IsGroup() ||
366 GetMac()->GetWifiRemoteStationManager(linkId)->GetAffiliatedStaAddress(rxAddr))
369 queueInfoIt->second.linkIds.emplace(linkId,
Mask{});
374 queueInfoIt->second.linkIds.erase(linkId);
382 auto linkId = GetMac() ? GetMac()->GetLinkIdByAddress(mpdu->GetHeader().GetAddr2())
385 auto& linkIdsMap = queueInfoIt->second.linkIds;
387 "At most one link can be associated with this container queue");
391 if (linkIdsMap.empty() || linkIdsMap.cbegin()->first != *linkId)
393 linkIdsMap = {{*linkId,
Mask{}}};
400template <
class Priority,
class Compare>
404 const Priority& priority)
410 "Cannot set the priority of an empty queue");
412 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
413 NS_ASSERT_MSG(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end(),
414 "No queue info for the given container queue");
415 typename SortedQueues::iterator sortedQueuesIt;
417 if (queueInfoIt->second.priorityIt.has_value())
422 if (queueInfoIt->second.priorityIt.value()->first == priority)
427 auto handle = m_perAcInfo[ac].sortedQueues.extract(queueInfoIt->second.priorityIt.value());
428 handle.key() = priority;
429 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert(std::move(handle));
434 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert({priority, std::ref(*queueInfoIt)});
437 queueInfoIt->second.priorityIt = sortedQueuesIt;
440template <
class Priority,
class Compare>
445 const std::list<WifiQueueBlockedReason>& ignoredReasons)
447 auto queueInfoIt = InitQueueInfo(ac, mpdu);
448 std::list<uint8_t> linkIds;
451 for (
auto [linkId, mask] : queueInfoIt->second.linkIds)
454 for (
const auto reason : ignoredReasons)
456 mask.reset(
static_cast<std::size_t
>(reason));
461 linkIds.emplace_back(linkId);
468template <
class Priority,
class Compare>
474 const std::list<WifiContainerQueueType>& types,
477 const std::set<uint8_t>& tids,
478 const std::set<uint8_t>& linkIds)
480 std::stringstream ss;
483 std::copy(linkIds.cbegin(), linkIds.cend(), std::ostream_iterator<uint16_t>(ss,
" "));
485 NS_LOG_FUNCTION(
this << block << reason << ac << rxAddress << txAddress << ss.str());
486 std::list<WifiMacHeader> headers;
488 for (
const auto queueType : types)
500 "TID must be specified for queues containing QoS data frames");
501 for (
const auto tid : tids)
504 headers.back().SetQosTid(tid);
512 for (
auto& hdr : headers)
514 hdr.SetAddr1(rxAddress);
515 hdr.SetAddr2(txAddress);
518 for (
auto& [linkId, mask] : queueInfoIt->second.linkIds)
520 if (linkIds.empty() || linkIds.count(linkId) > 0)
522 mask.set(
static_cast<std::size_t
>(reason), block);
528template <
class Priority,
class Compare>
533 const std::list<WifiContainerQueueType>& types,
536 const std::set<uint8_t>& tids,
537 const std::set<uint8_t>& linkIds)
539 DoBlockQueues(
true, reason, ac, types, rxAddress, txAddress, tids, linkIds);
542template <
class Priority,
class Compare>
547 const std::list<WifiContainerQueueType>& types,
550 const std::set<uint8_t>& tids,
551 const std::set<uint8_t>& linkIds)
553 DoBlockQueues(
false, reason, ac, types, rxAddress, txAddress, tids, linkIds);
556template <
class Priority,
class Compare>
557std::optional<WifiMacQueueScheduler::Mask>
564 const auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
566 if (queueInfoIt == m_perAcInfo[ac].queueInfoMap.cend())
572 const auto& linkIds = queueInfoIt->second.linkIds;
573 if (
const auto linkIt = linkIds.find(linkId); linkIt != linkIds.cend())
575 return linkIt->second;
581template <
class Priority,
class Compare>
582std::optional<WifiContainerQueueId>
586 return DoGetNext(ac, linkId, m_perAcInfo[ac].sortedQueues.begin());
589template <
class Priority,
class Compare>
590std::optional<WifiContainerQueueId>
592 std::optional<uint8_t> linkId,
597 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(prevQueueId);
598 NS_ABORT_IF(queueInfoIt == m_perAcInfo[ac].queueInfoMap.end() ||
599 !queueInfoIt->second.priorityIt.has_value());
601 auto sortedQueuesIt = queueInfoIt->second.priorityIt.value();
602 NS_ABORT_IF(sortedQueuesIt == m_perAcInfo[ac].sortedQueues.end());
604 return DoGetNext(ac, linkId, ++sortedQueuesIt);
607template <
class Priority,
class Compare>
608std::optional<WifiContainerQueueId>
611 std::optional<uint8_t> linkId,
612 typename SortedQueues::iterator sortedQueuesIt)
617 while (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
619 const auto& queueInfoPair = sortedQueuesIt->second.get();
620 const auto& linkIds = queueInfoPair.second.linkIds;
621 typename std::decay_t<
decltype(linkIds)>::const_iterator linkIt;
623 if (!linkId.has_value() ||
624 ((linkIt = linkIds.find(*linkId)) != linkIds.cend() && linkIt->second.none()))
631 std::optional<typename SortedQueues::iterator> prevQueueIt;
632 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.begin())
634 prevQueueIt = std::prev(sortedQueuesIt);
637 GetWifiMacQueue(ac)->ExtractExpiredMpdus(queueInfoPair.first);
639 if (GetWifiMacQueue(ac)->GetNBytes(queueInfoPair.first) == 0)
641 sortedQueuesIt = (prevQueueIt.has_value() ? std::next(prevQueueIt.value())
642 : m_perAcInfo[ac].sortedQueues.begin());
651 std::optional<WifiContainerQueueId> queueId;
653 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
655 queueId = sortedQueuesIt->second.get().first;
660template <
class Priority,
class Compare>
665 return HasToDropBeforeEnqueuePriv(ac, mpdu);
668template <
class Priority,
class Compare>
676 auto queueInfoIt = InitQueueInfo(ac, mpdu);
678 DoNotifyEnqueue(ac, mpdu);
680 if (!queueInfoIt->second.priorityIt.has_value())
683 "No info for the queue the MPDU was stored into (forgot to call SetPriority()?)");
687template <
class Priority,
class Compare>
695 DoNotifyDequeue(ac, mpdus);
697 std::list<WifiContainerQueueId> queueIds;
699 for (
const auto& mpdu : mpdus)
704 for (
const auto& queueId : queueIds)
706 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
710 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
711 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
712 if (queueInfoIt->second.priorityIt.has_value())
714 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
715 queueInfoIt->second.priorityIt.reset();
721template <
class Priority,
class Compare>
729 DoNotifyRemove(ac, mpdus);
731 std::list<WifiContainerQueueId> queueIds;
733 for (
const auto& mpdu : mpdus)
738 for (
const auto& queueId : queueIds)
740 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
744 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
745 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
746 if (queueInfoIt->second.priorityIt.has_value())
748 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
749 queueInfoIt->second.priorityIt.reset();
Test DROP_OLDEST setting.
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::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.
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.
std::vector< PerAcInfo > m_perAcInfo
vector of per-AC information
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.
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::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.
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.
#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.
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...
@ 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