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 static std::list<Ptr<WifiMacQueueItem>> g_emptyWifiMacQueue;
76 
77 const WifiMacQueue::ConstIterator WifiMacQueue::EMPTY = g_emptyWifiMacQueue.end ();
78 
79 void
81 {
82  NS_LOG_FUNCTION (this << delay);
83  m_maxDelay = delay;
84 }
85 
86 Time
88 {
89  return m_maxDelay;
90 }
91 
92 bool
93 WifiMacQueue::TtlExceeded (ConstIterator &it)
94 {
95  NS_LOG_FUNCTION (this);
96 
97  if (Simulator::Now () > (*it)->GetTimeStamp () + m_maxDelay)
98  {
99  NS_LOG_DEBUG ("Removing packet that stayed in the queue for too long (" <<
100  Simulator::Now () - (*it)->GetTimeStamp () << ")");
101  m_traceExpired (*it);
102  auto curr = it++;
103  DoRemove (curr);
104  return true;
105  }
106  return false;
107 }
108 
109 bool
111 {
112  NS_LOG_FUNCTION (this << *item);
113 
114  return Insert (end (), item);
115 }
116 
117 bool
119 {
120  NS_LOG_FUNCTION (this << *item);
121 
122  return Insert (begin (), item);
123 }
124 
125 bool
127 {
128  NS_LOG_FUNCTION (this << *item);
129  NS_ASSERT_MSG (GetMaxSize ().GetUnit () == QueueSizeUnit::PACKETS,
130  "WifiMacQueues must be in packet mode");
131 
132  // insert the item if the queue is not full
133  if (QueueBase::GetNPackets () < GetMaxSize ().GetValue ())
134  {
135  return DoEnqueue (pos, item);
136  }
137 
138  // the queue is full; scan the list in the attempt to remove stale packets
139  ConstIterator it = begin ();
140  while (it != end ())
141  {
142  if (it == pos && TtlExceeded (it))
143  {
144  return DoEnqueue (it, item);
145  }
146  if (TtlExceeded (it))
147  {
148  return DoEnqueue (pos, item);
149  }
150  it++;
151  }
152 
153  // the queue is still full, remove the oldest item if the policy is drop oldest
154  if (m_dropPolicy == DROP_OLDEST)
155  {
156  NS_LOG_DEBUG ("Remove the oldest item in the queue");
157  DoRemove (begin ());
158  }
159 
160  return DoEnqueue (pos, item);
161 }
162 
165 {
166  NS_LOG_FUNCTION (this);
167  for (ConstIterator it = begin (); it != end (); )
168  {
169  if (!TtlExceeded (it))
170  {
171  return DoDequeue (it);
172  }
173  }
174  NS_LOG_DEBUG ("The queue is empty");
175  return 0;
176 }
177 
180 {
181  NS_LOG_FUNCTION (this << dest);
182  ConstIterator it = PeekByAddress (dest);
183 
184  if (it == end ())
185  {
186  return 0;
187  }
188  return Dequeue (it);
189 }
190 
193 {
194  NS_LOG_FUNCTION (this << +tid);
195  ConstIterator it = PeekByTid (tid);
196 
197  if (it == end ())
198  {
199  return 0;
200  }
201  return Dequeue (it);
202 }
203 
206 {
207  NS_LOG_FUNCTION (this << +tid << dest);
208  ConstIterator it = PeekByTidAndAddress (tid, dest);
209 
210  if (it == end ())
211  {
212  return 0;
213  }
214  return Dequeue (it);
215 }
216 
219 {
220  NS_LOG_FUNCTION (this);
221  ConstIterator it = PeekFirstAvailable (blockedPackets);
222 
223  if (it == end ())
224  {
225  return 0;
226  }
227  return Dequeue (it);
228 }
229 
231 WifiMacQueue::Dequeue (ConstIterator pos)
232 {
233  NS_LOG_FUNCTION (this);
234 
236  {
237  if (TtlExceeded (pos))
238  {
239  NS_LOG_DEBUG ("Packet lifetime expired");
240  return 0;
241  }
242  return DoDequeue (pos);
243  }
244 
245  // remove stale items queued before the given position
246  ConstIterator it = begin ();
247  while (it != end ())
248  {
249  if (it == pos)
250  {
251  // reset the flag signaling the presence of expired packets before returning
252  m_expiredPacketsPresent = false;
253 
254  if (TtlExceeded (it))
255  {
256  return 0;
257  }
258  return DoDequeue (it);
259  }
260  else if (!TtlExceeded (it))
261  {
262  it++;
263  }
264  }
265  NS_LOG_DEBUG ("Invalid iterator");
266  return 0;
267 }
268 
269 Ptr<const WifiMacQueueItem>
270 WifiMacQueue::Peek (void) const
271 {
272  NS_LOG_FUNCTION (this);
273  for (auto it = begin (); it != end (); it++)
274  {
275  // skip packets that stayed in the queue for too long. They will be
276  // actually removed from the queue by the next call to a non-const method
277  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
278  {
279  return DoPeek (it);
280  }
281  // signal the presence of expired packets
283  }
284  NS_LOG_DEBUG ("The queue is empty");
285  return 0;
286 }
287 
288 WifiMacQueue::ConstIterator
289 WifiMacQueue::PeekByAddress (Mac48Address dest, ConstIterator pos) const
290 {
291  NS_LOG_FUNCTION (this << dest);
292  ConstIterator it = (pos != EMPTY ? pos : begin ());
293  while (it != end ())
294  {
295  // skip packets that stayed in the queue for too long. They will be
296  // actually removed from the queue by the next call to a non-const method
297  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
298  {
299  if (((*it)->GetHeader ().IsData () || (*it)->GetHeader ().IsQosData ())
300  && (*it)->GetDestinationAddress () == dest)
301  {
302  return it;
303  }
304  }
305  else
306  {
307  // signal the presence of expired packets
309  }
310  it++;
311  }
312  NS_LOG_DEBUG ("The queue is empty");
313  return end ();
314 }
315 
316 WifiMacQueue::ConstIterator
317 WifiMacQueue::PeekByTid (uint8_t tid, ConstIterator pos) const
318 {
319  NS_LOG_FUNCTION (this << +tid);
320  ConstIterator it = (pos != EMPTY ? pos : begin ());
321  while (it != end ())
322  {
323  // skip packets that stayed in the queue for too long. They will be
324  // actually removed from the queue by the next call to a non-const method
325  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
326  {
327  if ((*it)->GetHeader ().IsQosData () && (*it)->GetHeader ().GetQosTid () == tid)
328  {
329  return it;
330  }
331  }
332  else
333  {
334  // signal the presence of expired packets
336  }
337  it++;
338  }
339  NS_LOG_DEBUG ("The queue is empty");
340  return end ();
341 }
342 
343 WifiMacQueue::ConstIterator
344 WifiMacQueue::PeekByTidAndAddress (uint8_t tid, Mac48Address dest, ConstIterator pos) const
345 {
346  NS_LOG_FUNCTION (this << +tid << dest);
347  ConstIterator it = (pos != EMPTY ? pos : begin ());
348  while (it != end ())
349  {
350  // skip packets that stayed in the queue for too long. They will be
351  // actually removed from the queue by the next call to a non-const method
352  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
353  {
354  if ((*it)->GetHeader ().IsQosData () && (*it)->GetDestinationAddress () == dest
355  && (*it)->GetHeader ().GetQosTid () == tid)
356  {
357  return it;
358  }
359  }
360  else
361  {
362  // signal the presence of expired packets
364  }
365  it++;
366  }
367  NS_LOG_DEBUG ("The queue is empty");
368  return end ();
369 }
370 
371 WifiMacQueue::ConstIterator
372 WifiMacQueue::PeekFirstAvailable (const Ptr<QosBlockedDestinations> blockedPackets, ConstIterator pos) const
373 {
374  NS_LOG_FUNCTION (this);
375  ConstIterator it = (pos != EMPTY ? pos : begin ());
376  while (it != end ())
377  {
378  // skip packets that stayed in the queue for too long. They will be
379  // actually removed from the queue by the next call to a non-const method
380  if (Simulator::Now () <= (*it)->GetTimeStamp () + m_maxDelay)
381  {
382  if (!(*it)->GetHeader ().IsQosData () || !blockedPackets
383  || !blockedPackets->IsBlocked ((*it)->GetHeader ().GetAddr1 (), (*it)->GetHeader ().GetQosTid ()))
384  {
385  return it;
386  }
387  }
388  else
389  {
390  // signal the presence of expired packets
392  }
393  it++;
394  }
395  NS_LOG_DEBUG ("The queue is empty");
396  return end ();
397 }
398 
401 {
402  NS_LOG_FUNCTION (this);
403 
404  for (ConstIterator it = begin (); it != end (); )
405  {
406  if (!TtlExceeded (it))
407  {
408  return DoRemove (it);
409  }
410  }
411  NS_LOG_DEBUG ("The queue is empty");
412  return 0;
413 }
414 
415 bool
417 {
418  NS_LOG_FUNCTION (this << packet);
419  for (ConstIterator it = begin (); it != end (); )
420  {
421  if (!TtlExceeded (it))
422  {
423  if ((*it)->GetPacket () == packet)
424  {
425  DoRemove (it);
426  return true;
427  }
428 
429  it++;
430  }
431  }
432  NS_LOG_DEBUG ("Packet " << packet << " not found in the queue");
433  return false;
434 }
435 
436 WifiMacQueue::ConstIterator
437 WifiMacQueue::Remove (ConstIterator pos, bool removeExpired)
438 {
439  NS_LOG_FUNCTION (this);
440 
441  if (!removeExpired)
442  {
443  ConstIterator curr = pos++;
444  DoRemove (curr);
445  return pos;
446  }
447 
448  // remove stale items queued before the given position
449  ConstIterator it = begin ();
450  while (it != end ())
451  {
452  if (it == pos)
453  {
454  // reset the flag signaling the presence of expired packets before returning
455  m_expiredPacketsPresent = false;
456 
457  ConstIterator curr = pos++;
458  DoRemove (curr);
459  return pos;
460  }
461  else if (!TtlExceeded (it))
462  {
463  it++;
464  }
465  }
466  NS_LOG_DEBUG ("Invalid iterator");
467  return end ();
468 }
469 
470 uint32_t
472 {
473  NS_LOG_FUNCTION (this << dest);
474 
475  uint32_t nPackets = 0;
476 
477  for (ConstIterator it = begin (); it != end (); )
478  {
479  if (!TtlExceeded (it))
480  {
481  if ((*it)->GetHeader ().IsData () && (*it)->GetDestinationAddress () == dest)
482  {
483  nPackets++;
484  }
485 
486  it++;
487  }
488  }
489  NS_LOG_DEBUG ("returns " << nPackets);
490  return nPackets;
491 }
492 
493 uint32_t
495 {
496  NS_LOG_FUNCTION (this << dest);
497  uint32_t nPackets = 0;
498  for (ConstIterator it = begin (); it != end (); )
499  {
500  if (!TtlExceeded (it))
501  {
502  if ((*it)->GetHeader ().IsQosData () && (*it)->GetDestinationAddress () == dest
503  && (*it)->GetHeader ().GetQosTid () == tid)
504  {
505  nPackets++;
506  }
507 
508  it++;
509  }
510  }
511  NS_LOG_DEBUG ("returns " << nPackets);
512  return nPackets;
513 }
514 
515 bool
517 {
518  NS_LOG_FUNCTION (this);
519  for (ConstIterator it = begin (); it != end (); )
520  {
521  if (!TtlExceeded (it))
522  {
523  NS_LOG_DEBUG ("returns false");
524  return false;
525  }
526  }
527  NS_LOG_DEBUG ("returns true");
528  return true;
529 }
530 
531 uint32_t
533 {
534  NS_LOG_FUNCTION (this);
535  // remove packets that stayed in the queue for too long
536  for (ConstIterator it = begin (); it != end (); )
537  {
538  if (!TtlExceeded (it))
539  {
540  it++;
541  }
542  }
543  return QueueBase::GetNPackets ();
544 }
545 
546 uint32_t
548 {
549  NS_LOG_FUNCTION (this);
550  // remove packets that stayed in the queue for too long
551  for (ConstIterator it = begin (); it != end (); )
552  {
553  if (!TtlExceeded (it))
554  {
555  it++;
556  }
557  }
558  return QueueBase::GetNBytes ();
559 }
560 
561 } //namespace ns3
Time m_maxDelay
Time to live for packets in the queue.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
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
#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:1286
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.
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:1342
#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...
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:203
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.
static std::list< Ptr< WifiMacQueueItem > > g_emptyWifiMacQueue
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:1343
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:195
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.
#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:88
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< const AttributeChecker > MakeEnumChecker(int v, std::string n, Ts... args)
Make an EnumChecker pre-configured with a set of allowed values by name.
Definition: enum.h:161
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...
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:449
#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:923
Ptr< WifiMacQueueItem > DequeueByTid(uint8_t tid)
Search and return, if present in the queue, the first packet having the TID equal to tid...