A Discrete-Event Network Simulator
API
wifi-mac-queue.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2005, 2009 INRIA
4  * Copyright (c) 2009 MIRKO BANCHI
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 as
8  * published by the Free Software Foundation;
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  *
19  * Authors: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
20  * Mirko Banchi <mk.banchi@gmail.com>
21  * Stefano Avallone <stavallo@unina.it>
22  */
23 
24 #include "ns3/simulator.h"
25 #include "wifi-mac-queue.h"
27 
28 namespace ns3 {
29 
30 NS_LOG_COMPONENT_DEFINE ("WifiMacQueue");
31 
32 NS_OBJECT_ENSURE_REGISTERED (WifiMacQueue);
33 NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue, WifiMacQueueItem);
34 
35 TypeId
37 {
38  static TypeId tid = TypeId ("ns3::WifiMacQueue")
40  .SetGroupName ("Wifi")
41  .AddConstructor<WifiMacQueue> ()
42  .AddAttribute ("MaxSize",
43  "The max queue size",
44  QueueSizeValue (QueueSize ("500p")),
48  .AddAttribute ("MaxDelay", "If a packet stays longer than this delay in the queue, it is dropped.",
49  TimeValue (MilliSeconds (500)),
51  MakeTimeChecker ())
52  .AddAttribute ("DropPolicy", "Upon enqueue with full queue, drop oldest (DropOldest) or newest (DropNewest) packet",
56  WifiMacQueue::DROP_NEWEST, "DropNewest"))
57  .AddTraceSource ("Expired", "MPDU dropped because its lifetime expired.",
59  "ns3::WifiMacQueueItem::TracedCallback")
60  ;
61  return tid;
62 }
63 
65  : m_expiredPacketsPresent (false),
66  NS_LOG_TEMPLATE_DEFINE ("WifiMacQueue")
67 {
68 }
69 
71 {
73 }
74 
75 const WifiMacQueue::ConstIterator WifiMacQueue::EMPTY = std::list<Ptr<WifiMacQueueItem>> ().end ();
76 
77 void
79 {
80  NS_LOG_FUNCTION (this << delay);
81  m_maxDelay = delay;
82 }
83 
84 Time
86 {
87  return m_maxDelay;
88 }
89 
90 bool
91 WifiMacQueue::TtlExceeded (ConstIterator &it)
92 {
93  NS_LOG_FUNCTION (this);
94 
95  if (Simulator::Now () > (*it)->GetTimeStamp () + m_maxDelay)
96  {
97  NS_LOG_DEBUG ("Removing packet that stayed in the queue for too long (" <<
98  Simulator::Now () - (*it)->GetTimeStamp () << ")");
99  m_traceExpired (*it);
100  auto curr = it++;
101  DoRemove (curr);
102  return true;
103  }
104  return false;
105 }
106 
107 bool
109 {
110  NS_LOG_FUNCTION (this << *item);
111 
112  return Insert (end (), item);
113 }
114 
115 bool
117 {
118  NS_LOG_FUNCTION (this << *item);
119 
120  return Insert (begin (), item);
121 }
122 
123 bool
125 {
126  NS_LOG_FUNCTION (this << *item);
127  NS_ASSERT_MSG (GetMaxSize ().GetUnit () == QueueSizeUnit::PACKETS,
128  "WifiMacQueues must be in packet mode");
129 
130  // insert the item if the queue is not full
131  if (QueueBase::GetNPackets () < GetMaxSize ().GetValue ())
132  {
133  return DoEnqueue (pos, item);
134  }
135 
136  // the queue is full; scan the list in the attempt to remove stale packets
137  ConstIterator it = begin ();
138  while (it != end ())
139  {
140  if (it == pos && TtlExceeded (it))
141  {
142  return DoEnqueue (it, item);
143  }
144  if (TtlExceeded (it))
145  {
146  return DoEnqueue (pos, item);
147  }
148  it++;
149  }
150 
151  // the queue is still full, remove the oldest item if the policy is drop oldest
152  if (m_dropPolicy == DROP_OLDEST)
153  {
154  NS_LOG_DEBUG ("Remove the oldest item in the queue");
155  DoRemove (begin ());
156  }
157 
158  return DoEnqueue (pos, item);
159 }
160 
163 {
164  NS_LOG_FUNCTION (this);
165  for (ConstIterator it = begin (); it != end (); )
166  {
167  if (!TtlExceeded (it))
168  {
169  return DoDequeue (it);
170  }
171  }
172  NS_LOG_DEBUG ("The queue is empty");
173  return 0;
174 }
175 
178 {
179  NS_LOG_FUNCTION (this << dest);
180  ConstIterator it = PeekByAddress (dest);
181 
182  if (it == end ())
183  {
184  return 0;
185  }
186  return Dequeue (it);
187 }
188 
191 {
192  NS_LOG_FUNCTION (this << +tid);
193  ConstIterator it = PeekByTid (tid);
194 
195  if (it == end ())
196  {
197  return 0;
198  }
199  return Dequeue (it);
200 }
201 
204 {
205  NS_LOG_FUNCTION (this << +tid << dest);
206  ConstIterator it = PeekByTidAndAddress (tid, dest);
207 
208  if (it == end ())
209  {
210  return 0;
211  }
212  return Dequeue (it);
213 }
214 
217 {
218  NS_LOG_FUNCTION (this);
219  ConstIterator it = PeekFirstAvailable (blockedPackets);
220 
221  if (it == end ())
222  {
223  return 0;
224  }
225  return Dequeue (it);
226 }
227 
229 WifiMacQueue::Dequeue (ConstIterator pos)
230 {
231  NS_LOG_FUNCTION (this);
232 
234  {
235  if (TtlExceeded (pos))
236  {
237  NS_LOG_DEBUG ("Packet lifetime expired");
238  return 0;
239  }
240  return DoDequeue (pos);
241  }
242 
243  // remove stale items queued before the given position
244  ConstIterator it = begin ();
245  while (it != end ())
246  {
247  if (it == pos)
248  {
249  // reset the flag signaling the presence of expired packets before returning
250  m_expiredPacketsPresent = false;
251 
252  if (TtlExceeded (it))
253  {
254  return 0;
255  }
256  return DoDequeue (it);
257  }
258  else if (!TtlExceeded (it))
259  {
260  it++;
261  }
262  }
263  NS_LOG_DEBUG ("Invalid iterator");
264  return 0;
265 }
266 
267 Ptr<const WifiMacQueueItem>
268 WifiMacQueue::Peek (void) const
269 {
270  NS_LOG_FUNCTION (this);
271  for (auto it = begin (); it != end (); it++)
272  {
273  // skip packets that stayed in the queue for too long. They will be
274  // actually removed from the queue by the next call to a non-const method
275  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
276  {
277  return DoPeek (it);
278  }
279  // signal the presence of expired packets
281  }
282  NS_LOG_DEBUG ("The queue is empty");
283  return 0;
284 }
285 
286 WifiMacQueue::ConstIterator
287 WifiMacQueue::PeekByAddress (Mac48Address dest, ConstIterator pos) const
288 {
289  NS_LOG_FUNCTION (this << dest);
290  ConstIterator it = (pos != EMPTY ? pos : begin ());
291  while (it != end ())
292  {
293  // skip packets that stayed in the queue for too long. They will be
294  // actually removed from the queue by the next call to a non-const method
295  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
296  {
297  if (((*it)->GetHeader ().IsData () || (*it)->GetHeader ().IsQosData ())
298  && (*it)->GetDestinationAddress () == dest)
299  {
300  return it;
301  }
302  }
303  else
304  {
305  // signal the presence of expired packets
307  }
308  it++;
309  }
310  NS_LOG_DEBUG ("The queue is empty");
311  return end ();
312 }
313 
314 WifiMacQueue::ConstIterator
315 WifiMacQueue::PeekByTid (uint8_t tid, ConstIterator pos) const
316 {
317  NS_LOG_FUNCTION (this << +tid);
318  ConstIterator it = (pos != EMPTY ? pos : begin ());
319  while (it != end ())
320  {
321  // skip packets that stayed in the queue for too long. They will be
322  // actually removed from the queue by the next call to a non-const method
323  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
324  {
325  if ((*it)->GetHeader ().IsQosData () && (*it)->GetHeader ().GetQosTid () == tid)
326  {
327  return it;
328  }
329  }
330  else
331  {
332  // signal the presence of expired packets
334  }
335  it++;
336  }
337  NS_LOG_DEBUG ("The queue is empty");
338  return end ();
339 }
340 
341 WifiMacQueue::ConstIterator
342 WifiMacQueue::PeekByTidAndAddress (uint8_t tid, Mac48Address dest, ConstIterator pos) const
343 {
344  NS_LOG_FUNCTION (this << +tid << dest);
345  ConstIterator it = (pos != EMPTY ? pos : begin ());
346  while (it != end ())
347  {
348  // skip packets that stayed in the queue for too long. They will be
349  // actually removed from the queue by the next call to a non-const method
350  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
351  {
352  if ((*it)->GetHeader ().IsQosData () && (*it)->GetDestinationAddress () == dest
353  && (*it)->GetHeader ().GetQosTid () == tid)
354  {
355  return it;
356  }
357  }
358  else
359  {
360  // signal the presence of expired packets
362  }
363  it++;
364  }
365  NS_LOG_DEBUG ("The queue is empty");
366  return end ();
367 }
368 
369 WifiMacQueue::ConstIterator
370 WifiMacQueue::PeekFirstAvailable (const Ptr<QosBlockedDestinations> blockedPackets, ConstIterator pos) const
371 {
372  NS_LOG_FUNCTION (this);
373  ConstIterator it = (pos != EMPTY ? pos : begin ());
374  while (it != end ())
375  {
376  // skip packets that stayed in the queue for too long. They will be
377  // actually removed from the queue by the next call to a non-const method
378  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
379  {
380  if (!(*it)->GetHeader ().IsQosData () || !blockedPackets
381  || !blockedPackets->IsBlocked ((*it)->GetHeader ().GetAddr1 (), (*it)->GetHeader ().GetQosTid ()))
382  {
383  return it;
384  }
385  }
386  else
387  {
388  // signal the presence of expired packets
390  }
391  it++;
392  }
393  NS_LOG_DEBUG ("The queue is empty");
394  return end ();
395 }
396 
399 {
400  NS_LOG_FUNCTION (this);
401 
402  for (ConstIterator it = begin (); it != end (); )
403  {
404  if (!TtlExceeded (it))
405  {
406  return DoRemove (it);
407  }
408  }
409  NS_LOG_DEBUG ("The queue is empty");
410  return 0;
411 }
412 
413 bool
415 {
416  NS_LOG_FUNCTION (this << packet);
417  for (ConstIterator it = begin (); it != end (); )
418  {
419  if (!TtlExceeded (it))
420  {
421  if ((*it)->GetPacket () == packet)
422  {
423  DoRemove (it);
424  return true;
425  }
426 
427  it++;
428  }
429  }
430  NS_LOG_DEBUG ("Packet " << packet << " not found in the queue");
431  return false;
432 }
433 
434 WifiMacQueue::ConstIterator
435 WifiMacQueue::Remove (ConstIterator pos, bool removeExpired)
436 {
437  NS_LOG_FUNCTION (this);
438 
439  if (!removeExpired)
440  {
441  ConstIterator curr = pos++;
442  DoRemove (curr);
443  return pos;
444  }
445 
446  // remove stale items queued before the given position
447  ConstIterator it = begin ();
448  while (it != end ())
449  {
450  if (it == pos)
451  {
452  // reset the flag signaling the presence of expired packets before returning
453  m_expiredPacketsPresent = false;
454 
455  ConstIterator curr = pos++;
456  DoRemove (curr);
457  return pos;
458  }
459  else if (!TtlExceeded (it))
460  {
461  it++;
462  }
463  }
464  NS_LOG_DEBUG ("Invalid iterator");
465  return end ();
466 }
467 
468 uint32_t
470 {
471  NS_LOG_FUNCTION (this << dest);
472 
473  uint32_t nPackets = 0;
474 
475  for (ConstIterator it = begin (); it != end (); )
476  {
477  if (!TtlExceeded (it))
478  {
479  if ((*it)->GetHeader ().IsData () && (*it)->GetDestinationAddress () == dest)
480  {
481  nPackets++;
482  }
483 
484  it++;
485  }
486  }
487  NS_LOG_DEBUG ("returns " << nPackets);
488  return nPackets;
489 }
490 
491 uint32_t
493 {
494  NS_LOG_FUNCTION (this << dest);
495  uint32_t nPackets = 0;
496  for (ConstIterator it = begin (); it != end (); )
497  {
498  if (!TtlExceeded (it))
499  {
500  if ((*it)->GetHeader ().IsQosData () && (*it)->GetDestinationAddress () == dest
501  && (*it)->GetHeader ().GetQosTid () == tid)
502  {
503  nPackets++;
504  }
505 
506  it++;
507  }
508  }
509  NS_LOG_DEBUG ("returns " << nPackets);
510  return nPackets;
511 }
512 
513 bool
515 {
516  NS_LOG_FUNCTION (this);
517  for (ConstIterator it = begin (); it != end (); )
518  {
519  if (!TtlExceeded (it))
520  {
521  NS_LOG_DEBUG ("returns false");
522  return false;
523  }
524  }
525  NS_LOG_DEBUG ("returns true");
526  return true;
527 }
528 
529 uint32_t
531 {
532  NS_LOG_FUNCTION (this);
533  // remove packets that stayed in the queue for too long
534  for (ConstIterator it = begin (); it != end (); )
535  {
536  if (!TtlExceeded (it))
537  {
538  it++;
539  }
540  }
541  return QueueBase::GetNPackets ();
542 }
543 
544 uint32_t
546 {
547  NS_LOG_FUNCTION (this);
548  // remove packets that stayed in the queue for too long
549  for (ConstIterator it = begin (); it != end (); )
550  {
551  if (!TtlExceeded (it))
552  {
553  it++;
554  }
555  }
556  return QueueBase::GetNBytes ();
557 }
558 
559 } //namespace ns3
Time m_maxDelay
Time to live for packets in the queue.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
void SetMaxDelay(Time delay)
Set the maximum delay before the packet is discarded.
Class for representing queue sizes.
Definition: queue-size.h:94
QueueSize GetMaxSize(void) const
Definition: queue.cc:217
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
NS_ASSERT_MSG(false, "Ipv4AddressGenerator::MaskToIndex(): Impossible")
Ptr< const AttributeAccessor > MakeEnumAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: enum.h:209
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1072
uint32_t GetNBytes(void)
Introspection did not find any typical Config paths.
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
uint32_t GetNPacketsByTidAndAddress(uint8_t tid, Mac48Address dest)
Return the number of QoS packets having TID equal to tid and destination address equal to dest...
Ptr< WifiMacQueueItem > Dequeue(void)
Dequeue the packet in the front of the queue.
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:449
ConstIterator PeekByTidAndAddress(uint8_t tid, Mac48Address dest, ConstIterator pos=EMPTY) const
Search and return, if present in the queue, the first packet having the receiver address equal to des...
bool m_expiredPacketsPresent
True if expired packets are in the queue.
uint32_t GetNBytes(void) const
Definition: queue.cc:98
Hold variables of type enum.
Definition: enum.h:54
ConstIterator PeekByAddress(Mac48Address dest, ConstIterator pos=EMPTY) const
Search and return, if present in the queue, the first packet (either Data frame or QoS Data frame) ha...
AttributeValue implementation for Time.
Definition: nstime.h:1126
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition: log.h:239
Ptr< WifiMacQueueItem > DequeueByAddress(Mac48Address dest)
Search and return, if present in the queue, the first packet (either Data frame or QoS Data frame) ha...
Use number of packets for queue size.
Definition: queue-size.h:44
Ptr< const WifiMacQueueItem > Peek(void) const
Peek the packet in the front of the queue.
static TypeId GetTypeId(void)
Get the type ID.
Time GetMaxDelay(void) const
Return the maximum delay before the packet is discarded.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
static const ConstIterator EMPTY
Invalid iterator to signal an empty queue.
DropPolicy m_dropPolicy
Drop behavior of queue.
uint32_t GetNPacketsByAddress(Mac48Address dest)
Return the number of packets having destination address specified by dest.
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
Every class exported by the ns3 library is enclosed in the ns3 namespace.
TracedCallback< Ptr< const WifiMacQueueItem > > m_traceExpired
Traced callback: fired when a packet is dropped due to lifetime expiration.
an EUI-48 address
Definition: mac48-address.h:43
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: nstime.h:1127
Ptr< WifiMacQueueItem > DequeueFirstAvailable(const Ptr< QosBlockedDestinations > blockedPackets=nullptr)
Return first available packet for transmission.
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:193
bool Enqueue(Ptr< WifiMacQueueItem > item)
Enqueue the given Wifi MAC queue item at the end of the queue.
This queue implements the timeout procedure described in (Section 9.19.2.6 "Retransmit procedures" pa...
bool Insert(ConstIterator pos, Ptr< WifiMacQueueItem > item)
Enqueue the given Wifi MAC queue item before the given position.
Ptr< const AttributeChecker > MakeEnumChecker(int v1, std::string n1, int v2, std::string n2, int v3, std::string n3, int v4, std::string n4, int v5, std::string n5, int v6, std::string n6, int v7, std::string n7, int v8, std::string n8, int v9, std::string n9, int v10, std::string n10, int v11, std::string n11, int v12, std::string n12, int v13, std::string n13, int v14, std::string n14, int v15, std::string n15, int v16, std::string n16, int v17, std::string n17, int v18, std::string n18, int v19, std::string n19, int v20, std::string n20, int v21, std::string n21, int v22, std::string n22)
Make an EnumChecker pre-configured with a set of allowed values by name.
Definition: enum.cc:184
Ptr< WifiMacQueueItem > Remove(void)
Remove the packet in the front of the queue.
bool PushFront(Ptr< WifiMacQueueItem > item)
Enqueue the given Wifi MAC queue item at the front of the queue.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
bool TtlExceeded(ConstIterator &it)
Remove the item pointed to by the iterator it if it has been in the queue for too long...
Ptr< WifiMacQueueItem > DequeueByTidAndAddress(uint8_t tid, Mac48Address dest)
Search and return, if present in the queue, the first packet having the address indicated by type equ...
#define NS_OBJECT_TEMPLATE_CLASS_DEFINE(type, param)
Explicitly instantiate a template class and register the resulting instance with the TypeId system...
Definition: object-base.h:67
ConstIterator PeekFirstAvailable(const Ptr< QosBlockedDestinations > blockedPackets=nullptr, ConstIterator pos=EMPTY) const
Return first available packet for transmission.
void SetMaxSize(QueueSize size)
Set the maximum size of this queue.
Definition: queue.cc:200
uint32_t GetNPackets(void)
uint32_t GetNPackets(void) const
Definition: queue.cc:90
a unique identifier for an interface.
Definition: type-id.h:58
ConstIterator PeekByTid(uint8_t tid, ConstIterator pos=EMPTY) const
Search and return, if present in the queue, the first packet having the TID equal to tid...
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Ptr< WifiMacQueueItem > DequeueByTid(uint8_t tid)
Search and return, if present in the queue, the first packet having the TID equal to tid...