A Discrete-Event Network Simulator
API
queue.h
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2007 University of Washington
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  */
18 
19 // The queue base class has a limit on its size, in terms of number of
20 // packets or number of bytes depending on the operating mode.
21 // The base class implements tracing and basic statistics calculations.
22 
23 #ifndef QUEUE_H
24 #define QUEUE_H
25 
26 #include "ns3/packet.h"
27 #include "ns3/object.h"
28 #include "ns3/traced-callback.h"
29 #include "ns3/traced-value.h"
30 #include "ns3/unused.h"
31 #include "ns3/log.h"
32 #include "ns3/queue-size.h"
33 #include "ns3/queue-item.h"
34 #include <string>
35 #include <sstream>
36 #include <list>
37 
38 namespace ns3 {
39 
52 class QueueBase : public Object
53 {
54 public:
59  static TypeId GetTypeId (void);
60 
61  QueueBase ();
62  virtual ~QueueBase ();
63 
83  static void AppendItemTypeIfNotPresent (std::string& typeId, const std::string& itemType);
84 
88  bool IsEmpty (void) const;
89 
93  uint32_t GetNPackets (void) const;
94 
98  uint32_t GetNBytes (void) const;
99 
104  QueueSize GetCurrentSize (void) const;
105 
111  uint32_t GetTotalReceivedBytes (void) const;
112 
118  uint32_t GetTotalReceivedPackets (void) const;
119 
125  uint32_t GetTotalDroppedBytes (void) const;
126 
132  uint32_t GetTotalDroppedBytesBeforeEnqueue (void) const;
133 
139  uint32_t GetTotalDroppedBytesAfterDequeue (void) const;
140 
146  uint32_t GetTotalDroppedPackets (void) const;
147 
153  uint32_t GetTotalDroppedPacketsBeforeEnqueue (void) const;
154 
160  uint32_t GetTotalDroppedPacketsAfterDequeue (void) const;
161 
166  void ResetStatistics (void);
167 
175  void SetMaxSize (QueueSize size);
176 
180  QueueSize GetMaxSize (void) const;
181 
182 #if 0
183  // average calculation requires keeping around
184  // a buffer with the date of arrival of past received packets
185  // which are within the average window
186  // so, it is quite costly to do it all the time.
187  // Hence, it is disabled by default and must be explicitly
188  // enabled with this method which specifies the size
189  // of the average window in time units.
190  void EnableRunningAverage (Time averageWindow);
191  void DisableRunningAverage (void);
192  // average
193  double GetQueueSizeAverage (void);
194  double GetReceivedBytesPerSecondAverage (void);
195  double GetReceivedPacketsPerSecondAverage (void);
196  double GetDroppedBytesPerSecondAverage (void);
197  double GetDroppedPacketsPerSecondAverage (void);
198  // variance
199  double GetQueueSizeVariance (void);
200  double GetReceivedBytesPerSecondVariance (void);
201  double GetReceivedPacketsPerSecondVariance (void);
202  double GetDroppedBytesPerSecondVariance (void);
203  double GetDroppedPacketsPerSecondVariance (void);
204 #endif
205 
206 private:
217 
219 
221  template <typename Item>
222  friend class Queue;
223 };
224 
225 
252 template <typename Item>
253 class Queue : public QueueBase
254 {
255 public:
260  static TypeId GetTypeId (void);
261 
262  Queue ();
263  virtual ~Queue ();
264 
270  virtual bool Enqueue (Ptr<Item> item) = 0;
271 
277  virtual Ptr<Item> Dequeue (void) = 0;
278 
284  virtual Ptr<Item> Remove (void) = 0;
285 
291  virtual Ptr<const Item> Peek (void) const = 0;
292 
296  void Flush (void);
297 
299  typedef Item ItemType;
300 
301 protected:
302 
304  typedef typename std::list<Ptr<Item> >::const_iterator ConstIterator;
306  typedef typename std::list<Ptr<Item> >::iterator Iterator;
307 
322  ConstIterator begin (void) const;
323 
338  Iterator begin (void);
339 
354  ConstIterator end (void) const;
355 
370  Iterator end (void);
371 
378  bool DoEnqueue (ConstIterator pos, Ptr<Item> item);
379 
387  bool DoEnqueue (ConstIterator pos, Ptr<Item> item, Iterator& ret);
388 
395 
402 
409 
418  void DropBeforeEnqueue (Ptr<Item> item);
419 
428  void DropAfterDequeue (Ptr<Item> item);
429 
430 private:
431  std::list<Ptr<Item> > m_packets;
433 
444 };
445 
446 
451 template <typename Item>
452 TypeId
454 {
455  std::string name = GetTypeParamName<Queue<Item> > ();
456  static TypeId tid = TypeId (("ns3::Queue<" + name + ">").c_str ())
457  .SetParent<QueueBase> ()
458  .SetGroupName ("Network")
459  .AddTraceSource ("Enqueue", "Enqueue a packet in the queue.",
461  "ns3::" + name + "::TracedCallback")
462  .AddTraceSource ("Dequeue", "Dequeue a packet from the queue.",
464  "ns3::" + name + "::TracedCallback")
465  .AddTraceSource ("Drop", "Drop a packet (for whatever reason).",
467  "ns3::" + name + "::TracedCallback")
468  .AddTraceSource ("DropBeforeEnqueue", "Drop a packet before enqueue.",
470  "ns3::" + name + "::TracedCallback")
471  .AddTraceSource ("DropAfterDequeue", "Drop a packet after dequeue.",
473  "ns3::" + name + "::TracedCallback")
474  ;
475  return tid;
476 }
477 
478 template <typename Item>
480  : NS_LOG_TEMPLATE_DEFINE ("Queue")
481 {
482 }
483 
484 template <typename Item>
486 {
487 }
488 
489 template <typename Item>
490 bool
492 {
493  Iterator ret;
494  return DoEnqueue (pos, item, ret);
495 }
496 
497 template <typename Item>
498 bool
500 {
501  NS_LOG_FUNCTION (this << item);
502 
503  if (GetCurrentSize () + item > GetMaxSize ())
504  {
505  NS_LOG_LOGIC ("Queue full -- dropping pkt");
506  DropBeforeEnqueue (item);
507  return false;
508  }
509 
510  ret = m_packets.insert (pos, item);
511 
512  uint32_t size = item->GetSize ();
513  m_nBytes += size;
514  m_nTotalReceivedBytes += size;
515 
516  m_nPackets++;
517  m_nTotalReceivedPackets++;
518 
519  NS_LOG_LOGIC ("m_traceEnqueue (p)");
520  m_traceEnqueue (item);
521 
522  return true;
523 }
524 
525 template <typename Item>
526 Ptr<Item>
528 {
529  NS_LOG_FUNCTION (this);
530 
531  if (m_nPackets.Get () == 0)
532  {
533  NS_LOG_LOGIC ("Queue empty");
534  return 0;
535  }
536 
537  Ptr<Item> item = *pos;
538  m_packets.erase (pos);
539 
540  if (item != 0)
541  {
542  NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
543  NS_ASSERT (m_nPackets.Get () > 0);
544 
545  m_nBytes -= item->GetSize ();
546  m_nPackets--;
547 
548  NS_LOG_LOGIC ("m_traceDequeue (p)");
549  m_traceDequeue (item);
550  }
551  return item;
552 }
553 
554 template <typename Item>
555 Ptr<Item>
557 {
558  NS_LOG_FUNCTION (this);
559 
560  if (m_nPackets.Get () == 0)
561  {
562  NS_LOG_LOGIC ("Queue empty");
563  return 0;
564  }
565 
566  Ptr<Item> item = *pos;
567  m_packets.erase (pos);
568 
569  if (item != 0)
570  {
571  NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
572  NS_ASSERT (m_nPackets.Get () > 0);
573 
574  m_nBytes -= item->GetSize ();
575  m_nPackets--;
576 
577  // packets are first dequeued and then dropped
578  NS_LOG_LOGIC ("m_traceDequeue (p)");
579  m_traceDequeue (item);
580 
581  DropAfterDequeue (item);
582  }
583  return item;
584 }
585 
586 template <typename Item>
587 void
589 {
590  NS_LOG_FUNCTION (this);
591  while (!IsEmpty ())
592  {
593  Remove ();
594  }
595 }
596 
597 template <typename Item>
600 {
601  NS_LOG_FUNCTION (this);
602 
603  if (m_nPackets.Get () == 0)
604  {
605  NS_LOG_LOGIC ("Queue empty");
606  return 0;
607  }
608 
609  return *pos;
610 }
611 
612 template <typename Item>
614 {
615  return m_packets.cbegin ();
616 }
617 
618 template <typename Item>
620 {
621  return m_packets.begin ();
622 }
623 
624 template <typename Item>
626 {
627  return m_packets.cend ();
628 }
629 
630 template <typename Item>
632 {
633  return m_packets.end ();
634 }
635 
636 template <typename Item>
637 void
639 {
640  NS_LOG_FUNCTION (this << item);
641 
642  m_nTotalDroppedPackets++;
643  m_nTotalDroppedPacketsBeforeEnqueue++;
644  m_nTotalDroppedBytes += item->GetSize ();
645  m_nTotalDroppedBytesBeforeEnqueue += item->GetSize ();
646 
647  NS_LOG_LOGIC ("m_traceDropBeforeEnqueue (p)");
648  m_traceDrop (item);
649  m_traceDropBeforeEnqueue (item);
650 }
651 
652 template <typename Item>
653 void
655 {
656  NS_LOG_FUNCTION (this << item);
657 
658  m_nTotalDroppedPackets++;
659  m_nTotalDroppedPacketsAfterDequeue++;
660  m_nTotalDroppedBytes += item->GetSize ();
661  m_nTotalDroppedBytesAfterDequeue += item->GetSize ();
662 
663  NS_LOG_LOGIC ("m_traceDropAfterDequeue (p)");
664  m_traceDrop (item);
665  m_traceDropAfterDequeue (item);
666 }
667 
668 // The following explicit template instantiation declarations prevent all the
669 // translation units including this header file to implicitly instantiate the
670 // Queue<Packet> class and the Queue<QueueDiscItem> class. The unique instances
671 // of these classes are explicitly created through the macros
672 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,Packet) and
673 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,QueueDiscItem), which are included in queue.cc
674 extern template class Queue<Packet>;
675 extern template class Queue<QueueDiscItem>;
676 
677 } // namespace ns3
678 
679 #endif /* QUEUE_H */
Item ItemType
Define ItemType as the type of the stored elements.
Definition: queue.h:299
uint32_t m_nTotalDroppedPacketsBeforeEnqueue
Total dropped packets before enqueue.
Definition: queue.h:215
uint32_t m_nTotalReceivedPackets
Total received packets.
Definition: queue.h:210
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
uint32_t m_nTotalDroppedPackets
Total dropped packets.
Definition: queue.h:214
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
TracedCallback< Ptr< const Item > > m_traceDequeue
Traced callback: fired when a packet is dequeued.
Definition: queue.h:437
Class for representing queue sizes.
Definition: queue-size.h:94
QueueSize GetMaxSize(void) const
Definition: queue.cc:217
uint32_t GetTotalDroppedPacketsBeforeEnqueue(void) const
Definition: queue.cc:170
uint32_t GetTotalDroppedBytes(void) const
Definition: queue.cc:138
uint32_t GetTotalReceivedPackets(void) const
Definition: queue.cc:130
NS_LOG_TEMPLATE_DECLARE
the log component
Definition: queue.h:432
Forward calls to a chain of Callback.
void Flush(void)
Flush the queue.
Definition: queue.h:588
uint32_t m_nTotalDroppedBytes
Total dropped bytes.
Definition: queue.h:211
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
uint32_t m_nTotalDroppedPacketsAfterDequeue
Total dropped packets after dequeue.
Definition: queue.h:216
uint32_t GetTotalDroppedBytesBeforeEnqueue(void) const
Definition: queue.cc:146
uint32_t m_nTotalDroppedBytesAfterDequeue
Total dropped bytes after dequeue.
Definition: queue.h:213
Ptr< Item > DoRemove(ConstIterator pos)
Pull the item to drop from the queue.
Definition: queue.h:556
TracedCallback< Ptr< const Item > > m_traceDrop
Traced callback: fired when a packet is dropped.
Definition: queue.h:439
TracedValue< uint32_t > m_nPackets
Number of packets in the queue.
Definition: queue.h:209
static void AppendItemTypeIfNotPresent(std::string &typeId, const std::string &itemType)
Append the item type to the provided type ID if the latter does not end with &#39;>&#39;. ...
Definition: queue.cc:73
QueueSize m_maxSize
max queue size
Definition: queue.h:218
virtual ~QueueBase()
Definition: queue.cc:67
uint32_t GetTotalDroppedBytesAfterDequeue(void) const
Definition: queue.cc:154
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Template class for packet Queues.
static TypeId GetTypeId(void)
Get the type ID.
Definition: queue.h:453
TracedCallback< Ptr< const Item > > m_traceDropAfterDequeue
Traced callback: fired when a packet is dropped after dequeue.
Definition: queue.h:443
ConstIterator begin(void) const
Get a const iterator which refers to the first item in the queue.
Definition: queue.h:613
uint32_t GetNBytes(void) const
Definition: queue.cc:98
uint32_t m_nTotalDroppedBytesBeforeEnqueue
Total dropped bytes before enqueue.
Definition: queue.h:212
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition: log.h:239
TracedCallback< Ptr< const Item > > m_traceEnqueue
Traced callback: fired when a packet is enqueued.
Definition: queue.h:435
void DropAfterDequeue(Ptr< Item > item)
Drop a packet after dequeue.
Definition: queue.h:654
ConstIterator end(void) const
Get a const iterator which indicates past-the-last item in the queue.
Definition: queue.h:625
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
std::list< Ptr< Item > >::iterator Iterator
Iterator.
Definition: queue.h:306
uint32_t m_nTotalReceivedBytes
Total received bytes.
Definition: queue.h:208
void ResetStatistics(void)
Resets the counts for dropped packets, dropped bytes, received packets, and received bytes...
Definition: queue.cc:186
virtual bool Enqueue(Ptr< Item > item)=0
Place an item into the Queue (each subclass defines the position)
Every class exported by the ns3 library is enclosed in the ns3 namespace.
virtual Ptr< Item > Remove(void)=0
Remove an item from the Queue (each subclass defines the position), counting it as dropped...
Queue()
Definition: queue.h:479
uint32_t GetTotalDroppedPacketsAfterDequeue(void) const
Definition: queue.cc:178
TracedCallback< Ptr< const Item > > m_traceDropBeforeEnqueue
Traced callback: fired when a packet is dropped before enqueue.
Definition: queue.h:441
Ptr< const Item > DoPeek(ConstIterator pos) const
Peek the front item in the queue.
Definition: queue.h:599
Abstract base class for packet Queues.
Definition: queue.h:52
virtual Ptr< Item > Dequeue(void)=0
Remove an item from the Queue (each subclass defines the position), counting it as dequeued...
uint32_t GetTotalDroppedPackets(void) const
Definition: queue.cc:162
Introspection did not find any typical Config paths.
void DropBeforeEnqueue(Ptr< Item > item)
Drop a packet before enqueue.
Definition: queue.h:638
virtual Ptr< const Item > Peek(void) const =0
Get a copy of an item in the queue (each subclass defines the position) without removing it...
A base class which provides memory management and object aggregation.
Definition: object.h:87
uint32_t GetTotalReceivedBytes(void) const
Definition: queue.cc:122
void SetMaxSize(QueueSize size)
Set the maximum size of this queue.
Definition: queue.cc:200
Ptr< Item > DoDequeue(ConstIterator pos)
Pull the item to dequeue from the queue.
Definition: queue.h:527
QueueSize GetCurrentSize(void) const
Definition: queue.cc:106
uint32_t GetNPackets(void) const
Definition: queue.cc:90
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:923
bool DoEnqueue(ConstIterator pos, Ptr< Item > item)
Push an item in the queue.
Definition: queue.h:491
std::list< Ptr< Item > >::const_iterator ConstIterator
Const iterator.
Definition: queue.h:304
std::list< Ptr< Item > > m_packets
the items in the queue
Definition: queue.h:431
static TypeId GetTypeId(void)
Get the type ID.
Definition: queue.cc:34
bool IsEmpty(void) const
Definition: queue.cc:82
virtual ~Queue()
Definition: queue.h:485
TracedValue< uint32_t > m_nBytes
Number of bytes in the queue.
Definition: queue.h:207