20#ifndef WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
21#define WIFI_MAC_QUEUE_SCHEDULER_IMPL_H
34#include <unordered_map>
52template <
class Priority,
class Compare = std::less<Priority>>
57 friend class ::WifiMacQueueDropOldestTest;
73 std::optional<WifiContainerQueueId>
GetNext(
AcIndex ac, std::optional<uint8_t> linkId)
final;
79 std::optional<uint8_t> linkId,
84 const std::list<WifiQueueBlockedReason>& ignoredReasons)
final;
88 const std::list<WifiContainerQueueType>& types,
91 const std::set<uint8_t>& tids,
92 const std::set<uint8_t>& linkIds)
final;
96 const std::list<WifiContainerQueueType>& types,
99 const std::set<uint8_t>& tids,
100 const std::set<uint8_t>& linkIds)
final;
104 uint8_t linkId)
final;
135 using QueueInfoMap = std::unordered_map<WifiContainerQueueId, QueueInfo>;
149 using SortedQueues = std::multimap<Priority, std::reference_wrapper<QueueInfoPair>, Compare>;
156 std::optional<typename SortedQueues::iterator>
219 std::optional<uint8_t> linkId,
220 typename SortedQueues::iterator sortedQueuesIt);
275 const std::list<WifiContainerQueueType>& types,
278 const std::set<uint8_t>& tids,
279 const std::set<uint8_t>& linkIds);
289template <
class Priority,
class Compare>
295template <
class Priority,
class Compare>
299 static TypeId tid =
TypeId(
"ns3::WifiMacQueueSchedulerImpl")
301 .SetGroupName(
"Wifi");
305template <
class Priority,
class Compare>
313template <
class Priority,
class Compare>
319 if (
auto queue = mac->GetTxopQueue(ac); queue !=
nullptr)
321 m_perAcInfo.at(ac).wifiMacQueue = queue;
322 queue->SetScheduler(
this);
328template <
class Priority,
class Compare>
333 return m_perAcInfo.at(ac).wifiMacQueue;
336template <
class Priority,
class Compare>
341 return m_perAcInfo.at(ac).sortedQueues;
344template <
class Priority,
class Compare>
352 auto [queueInfoIt, ret] = m_perAcInfo[ac].queueInfoMap.insert({queueId,
QueueInfo()});
355 if (GetMac() && GetMac()->GetNLinks() > 1 &&
356 mpdu->GetHeader().GetAddr2() == GetMac()->GetAddress())
360 const auto rxAddr = mpdu->GetHeader().GetAddr1();
364 NS_ASSERT_MSG(rxAddr.IsGroup() || GetMac()->GetMldAddress(rxAddr) == rxAddr,
365 "Address 1 (" << rxAddr <<
") is not an MLD address");
369 NS_ASSERT_MSG(GetMac()->CanForwardPacketsTo(rxAddr),
"Cannot forward frame to " << rxAddr);
372 for (
const auto linkId : GetMac()->GetLinkIds())
374 if (rxAddr.IsGroup() ||
375 GetMac()->GetWifiRemoteStationManager(linkId)->GetAffiliatedStaAddress(rxAddr))
378 queueInfoIt->second.linkIds.emplace(linkId,
Mask{});
383 queueInfoIt->second.linkIds.erase(linkId);
391 auto linkId = GetMac() ? GetMac()->GetLinkIdByAddress(mpdu->GetHeader().GetAddr2())
394 auto& linkIdsMap = queueInfoIt->second.linkIds;
396 "At most one link can be associated with this container queue");
400 if (linkIdsMap.empty() || linkIdsMap.cbegin()->first != *linkId)
402 linkIdsMap = {{*linkId,
Mask{}}};
409template <
class Priority,
class Compare>
413 const Priority& priority)
419 "Cannot set the priority of an empty queue");
421 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
422 NS_ASSERT_MSG(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end(),
423 "No queue info for the given container queue");
424 typename SortedQueues::iterator sortedQueuesIt;
426 if (queueInfoIt->second.priorityIt.has_value())
431 if (queueInfoIt->second.priorityIt.value()->first == priority)
436 auto handle = m_perAcInfo[ac].sortedQueues.extract(queueInfoIt->second.priorityIt.value());
437 handle.key() = priority;
438 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert(std::move(handle));
443 sortedQueuesIt = m_perAcInfo[ac].sortedQueues.insert({priority, std::ref(*queueInfoIt)});
446 queueInfoIt->second.priorityIt = sortedQueuesIt;
449template <
class Priority,
class Compare>
454 const std::list<WifiQueueBlockedReason>& ignoredReasons)
456 auto queueInfoIt = InitQueueInfo(ac, mpdu);
457 std::list<uint8_t> linkIds;
460 for (
auto [linkId, mask] : queueInfoIt->second.linkIds)
463 for (
const auto reason : ignoredReasons)
465 mask.reset(
static_cast<std::size_t
>(reason));
470 linkIds.emplace_back(linkId);
477template <
class Priority,
class Compare>
483 const std::list<WifiContainerQueueType>& types,
486 const std::set<uint8_t>& tids,
487 const std::set<uint8_t>& linkIds)
489 std::stringstream ss;
492 std::copy(linkIds.cbegin(), linkIds.cend(), std::ostream_iterator<uint16_t>(ss,
" "));
494 NS_LOG_FUNCTION(
this << block << reason << ac << rxAddress << txAddress << ss.str());
495 std::list<WifiMacHeader> headers;
497 for (
const auto queueType : types)
509 "TID must be specified for queues containing QoS data frames");
510 for (
const auto tid : tids)
513 headers.back().SetQosTid(tid);
521 for (
auto& hdr : headers)
523 hdr.SetAddr1(rxAddress);
524 hdr.SetAddr2(txAddress);
526 auto queueInfoIt = InitQueueInfo(ac, Create<WifiMpdu>(Create<Packet>(), hdr));
527 for (
auto& [linkId, mask] : queueInfoIt->second.linkIds)
529 if (linkIds.empty() || linkIds.count(linkId) > 0)
531 mask.set(
static_cast<std::size_t
>(reason), block);
537template <
class Priority,
class Compare>
542 const std::list<WifiContainerQueueType>& types,
545 const std::set<uint8_t>& tids,
546 const std::set<uint8_t>& linkIds)
548 DoBlockQueues(
true, reason, ac, types, rxAddress, txAddress, tids, linkIds);
551template <
class Priority,
class Compare>
556 const std::list<WifiContainerQueueType>& types,
559 const std::set<uint8_t>& tids,
560 const std::set<uint8_t>& linkIds)
562 DoBlockQueues(
false, reason, ac, types, rxAddress, txAddress, tids, linkIds);
565template <
class Priority,
class Compare>
566std::optional<WifiMacQueueScheduler::Mask>
573 const auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
575 if (queueInfoIt == m_perAcInfo[ac].queueInfoMap.cend())
581 const auto& linkIds = queueInfoIt->second.linkIds;
582 if (
const auto linkIt = linkIds.find(linkId); linkIt != linkIds.cend())
584 return linkIt->second;
590template <
class Priority,
class Compare>
591std::optional<WifiContainerQueueId>
595 return DoGetNext(ac, linkId, m_perAcInfo[ac].sortedQueues.begin());
598template <
class Priority,
class Compare>
599std::optional<WifiContainerQueueId>
601 std::optional<uint8_t> linkId,
606 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(prevQueueId);
607 NS_ABORT_IF(queueInfoIt == m_perAcInfo[ac].queueInfoMap.end() ||
608 !queueInfoIt->second.priorityIt.has_value());
610 auto sortedQueuesIt = queueInfoIt->second.priorityIt.value();
611 NS_ABORT_IF(sortedQueuesIt == m_perAcInfo[ac].sortedQueues.end());
613 return DoGetNext(ac, linkId, ++sortedQueuesIt);
616template <
class Priority,
class Compare>
617std::optional<WifiContainerQueueId>
620 std::optional<uint8_t> linkId,
621 typename SortedQueues::iterator sortedQueuesIt)
626 while (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
628 const auto& queueInfoPair = sortedQueuesIt->second.get();
629 const auto& linkIds = queueInfoPair.second.linkIds;
630 typename std::decay_t<
decltype(linkIds)>::const_iterator linkIt;
632 if (!linkId.has_value() ||
633 ((linkIt = linkIds.find(*linkId)) != linkIds.cend() && linkIt->second.none()))
640 std::optional<typename SortedQueues::iterator> prevQueueIt;
641 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.begin())
643 prevQueueIt = std::prev(sortedQueuesIt);
646 GetWifiMacQueue(ac)->ExtractExpiredMpdus(queueInfoPair.first);
648 if (GetWifiMacQueue(ac)->GetNBytes(queueInfoPair.first) == 0)
650 sortedQueuesIt = (prevQueueIt.has_value() ? std::next(prevQueueIt.value())
651 : m_perAcInfo[ac].sortedQueues.begin());
660 std::optional<WifiContainerQueueId> queueId;
662 if (sortedQueuesIt != m_perAcInfo[ac].sortedQueues.end())
664 queueId = sortedQueuesIt->second.get().first;
669template <
class Priority,
class Compare>
674 return HasToDropBeforeEnqueuePriv(ac, mpdu);
677template <
class Priority,
class Compare>
685 auto queueInfoIt = InitQueueInfo(ac, mpdu);
687 DoNotifyEnqueue(ac, mpdu);
689 if (!queueInfoIt->second.priorityIt.has_value())
692 "No info for the queue the MPDU was stored into (forgot to call SetPriority()?)");
696template <
class Priority,
class Compare>
704 DoNotifyDequeue(ac, mpdus);
706 std::list<WifiContainerQueueId> queueIds;
708 for (
const auto& mpdu : mpdus)
713 for (
const auto& queueId : queueIds)
715 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
719 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
720 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
721 if (queueInfoIt->second.priorityIt.has_value())
723 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
724 queueInfoIt->second.priorityIt.reset();
730template <
class Priority,
class Compare>
738 DoNotifyRemove(ac, mpdus);
740 std::list<WifiContainerQueueId> queueIds;
742 for (
const auto& mpdu : mpdus)
747 for (
const auto& queueId : queueIds)
749 if (GetWifiMacQueue(ac)->GetNBytes(queueId) == 0)
753 auto queueInfoIt = m_perAcInfo[ac].queueInfoMap.find(queueId);
754 NS_ASSERT(queueInfoIt != m_perAcInfo[ac].queueInfoMap.end());
755 if (queueInfoIt->second.priorityIt.has_value())
757 m_perAcInfo[ac].sortedQueues.erase(queueInfoIt->second.priorityIt.value());
758 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 ",...
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