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/log.h"
31 #include "ns3/queue-size.h"
32 #include "ns3/queue-item.h"
33 #include <string>
34 #include <sstream>
35 #include <list>
36 
37 namespace ns3 {
38 
51 class QueueBase : public Object
52 {
53 public:
58  static TypeId GetTypeId (void);
59 
60  QueueBase ();
61  virtual ~QueueBase ();
62 
82  static void AppendItemTypeIfNotPresent (std::string& typeId, const std::string& itemType);
83 
87  bool IsEmpty (void) const;
88 
92  uint32_t GetNPackets (void) const;
93 
97  uint32_t GetNBytes (void) const;
98 
103  QueueSize GetCurrentSize (void) const;
104 
110  uint32_t GetTotalReceivedBytes (void) const;
111 
117  uint32_t GetTotalReceivedPackets (void) const;
118 
124  uint32_t GetTotalDroppedBytes (void) const;
125 
131  uint32_t GetTotalDroppedBytesBeforeEnqueue (void) const;
132 
138  uint32_t GetTotalDroppedBytesAfterDequeue (void) const;
139 
145  uint32_t GetTotalDroppedPackets (void) const;
146 
152  uint32_t GetTotalDroppedPacketsBeforeEnqueue (void) const;
153 
159  uint32_t GetTotalDroppedPacketsAfterDequeue (void) const;
160 
165  void ResetStatistics (void);
166 
174  void SetMaxSize (QueueSize size);
175 
179  QueueSize GetMaxSize (void) const;
180 
188  bool WouldOverflow (uint32_t nPackets, uint32_t nBytes) const;
189 
190 #if 0
191  // average calculation requires keeping around
192  // a buffer with the date of arrival of past received packets
193  // which are within the average window
194  // so, it is quite costly to do it all the time.
195  // Hence, it is disabled by default and must be explicitly
196  // enabled with this method which specifies the size
197  // of the average window in time units.
198  void EnableRunningAverage (Time averageWindow);
199  void DisableRunningAverage (void);
200  // average
201  double GetQueueSizeAverage (void);
202  double GetReceivedBytesPerSecondAverage (void);
203  double GetReceivedPacketsPerSecondAverage (void);
204  double GetDroppedBytesPerSecondAverage (void);
205  double GetDroppedPacketsPerSecondAverage (void);
206  // variance
207  double GetQueueSizeVariance (void);
208  double GetReceivedBytesPerSecondVariance (void);
209  double GetReceivedPacketsPerSecondVariance (void);
210  double GetDroppedBytesPerSecondVariance (void);
211  double GetDroppedPacketsPerSecondVariance (void);
212 #endif
213 
214 private:
225 
227 
229  template <typename Item>
230  friend class Queue;
231 };
232 
233 
260 template <typename Item>
261 class Queue : public QueueBase
262 {
263 public:
268  static TypeId GetTypeId (void);
269 
270  Queue ();
271  virtual ~Queue ();
272 
278  virtual bool Enqueue (Ptr<Item> item) = 0;
279 
285  virtual Ptr<Item> Dequeue (void) = 0;
286 
292  virtual Ptr<Item> Remove (void) = 0;
293 
299  virtual Ptr<const Item> Peek (void) const = 0;
300 
306  void Flush (void);
307 
309  typedef Item ItemType;
310 
311 protected:
312 
314  typedef typename std::list<Ptr<Item> >::const_iterator ConstIterator;
316  typedef typename std::list<Ptr<Item> >::iterator Iterator;
317 
332  ConstIterator begin (void) const;
333 
348  Iterator begin (void);
349 
364  ConstIterator end (void) const;
365 
380  Iterator end (void);
381 
389 
397  bool DoEnqueue (ConstIterator pos, Ptr<Item> item, Iterator& ret);
398 
405 
412 
419 
429 
439 
440  void DoDispose (void) override;
441 
442 private:
443  std::list<Ptr<Item> > m_packets;
445 
456 };
457 
458 
463 template <typename Item>
464 TypeId
466 {
467  std::string name = GetTypeParamName<Queue<Item> > ();
468  static TypeId tid = TypeId ("ns3::Queue<" + name + ">")
469  .SetParent<QueueBase> ()
470  .SetGroupName ("Network")
471  .AddTraceSource ("Enqueue", "Enqueue a packet in the queue.",
473  "ns3::" + name + "::TracedCallback")
474  .AddTraceSource ("Dequeue", "Dequeue a packet from the queue.",
476  "ns3::" + name + "::TracedCallback")
477  .AddTraceSource ("Drop", "Drop a packet (for whatever reason).",
479  "ns3::" + name + "::TracedCallback")
480  .AddTraceSource ("DropBeforeEnqueue", "Drop a packet before enqueue.",
482  "ns3::" + name + "::TracedCallback")
483  .AddTraceSource ("DropAfterDequeue", "Drop a packet after dequeue.",
485  "ns3::" + name + "::TracedCallback")
486  ;
487  return tid;
488 }
489 
490 template <typename Item>
492  : NS_LOG_TEMPLATE_DEFINE ("Queue")
493 {
494 }
495 
496 template <typename Item>
498 {
499 }
500 
501 template <typename Item>
502 bool
504 {
505  Iterator ret;
506  return DoEnqueue (pos, item, ret);
507 }
508 
509 template <typename Item>
510 bool
512 {
513  NS_LOG_FUNCTION (this << item);
514 
515  if (GetCurrentSize () + item > GetMaxSize ())
516  {
517  NS_LOG_LOGIC ("Queue full -- dropping pkt");
518  DropBeforeEnqueue (item);
519  return false;
520  }
521 
522  ret = m_packets.insert (pos, item);
523 
524  uint32_t size = item->GetSize ();
525  m_nBytes += size;
526  m_nTotalReceivedBytes += size;
527 
528  m_nPackets++;
529  m_nTotalReceivedPackets++;
530 
531  NS_LOG_LOGIC ("m_traceEnqueue (p)");
532  m_traceEnqueue (item);
533 
534  return true;
535 }
536 
537 template <typename Item>
538 Ptr<Item>
540 {
541  NS_LOG_FUNCTION (this);
542 
543  if (m_nPackets.Get () == 0)
544  {
545  NS_LOG_LOGIC ("Queue empty");
546  return 0;
547  }
548 
549  Ptr<Item> item = *pos;
550  m_packets.erase (pos);
551 
552  if (item != 0)
553  {
554  NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
555  NS_ASSERT (m_nPackets.Get () > 0);
556 
557  m_nBytes -= item->GetSize ();
558  m_nPackets--;
559 
560  NS_LOG_LOGIC ("m_traceDequeue (p)");
561  m_traceDequeue (item);
562  }
563  return item;
564 }
565 
566 template <typename Item>
567 Ptr<Item>
569 {
570  NS_LOG_FUNCTION (this);
571 
572  if (m_nPackets.Get () == 0)
573  {
574  NS_LOG_LOGIC ("Queue empty");
575  return 0;
576  }
577 
578  Ptr<Item> item = *pos;
579  m_packets.erase (pos);
580 
581  if (item != 0)
582  {
583  NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
584  NS_ASSERT (m_nPackets.Get () > 0);
585 
586  m_nBytes -= item->GetSize ();
587  m_nPackets--;
588 
589  // packets are first dequeued and then dropped
590  NS_LOG_LOGIC ("m_traceDequeue (p)");
591  m_traceDequeue (item);
592 
593  DropAfterDequeue (item);
594  }
595  return item;
596 }
597 
598 template <typename Item>
599 void
601 {
602  NS_LOG_FUNCTION (this);
603  while (!IsEmpty ())
604  {
605  Remove ();
606  }
607 }
608 
609 template <typename Item>
610 void
612 {
613  NS_LOG_FUNCTION (this);
614  m_packets.clear ();
616 }
617 
618 template <typename Item>
621 {
622  NS_LOG_FUNCTION (this);
623 
624  if (m_nPackets.Get () == 0)
625  {
626  NS_LOG_LOGIC ("Queue empty");
627  return 0;
628  }
629 
630  return *pos;
631 }
632 
633 template <typename Item>
635 {
636  return m_packets.cbegin ();
637 }
638 
639 template <typename Item>
641 {
642  return m_packets.begin ();
643 }
644 
645 template <typename Item>
647 {
648  return m_packets.cend ();
649 }
650 
651 template <typename Item>
653 {
654  return m_packets.end ();
655 }
656 
657 template <typename Item>
658 void
660 {
661  NS_LOG_FUNCTION (this << item);
662 
663  m_nTotalDroppedPackets++;
664  m_nTotalDroppedPacketsBeforeEnqueue++;
665  m_nTotalDroppedBytes += item->GetSize ();
666  m_nTotalDroppedBytesBeforeEnqueue += item->GetSize ();
667 
668  NS_LOG_LOGIC ("m_traceDropBeforeEnqueue (p)");
669  m_traceDrop (item);
670  m_traceDropBeforeEnqueue (item);
671 }
672 
673 template <typename Item>
674 void
676 {
677  NS_LOG_FUNCTION (this << item);
678 
679  m_nTotalDroppedPackets++;
680  m_nTotalDroppedPacketsAfterDequeue++;
681  m_nTotalDroppedBytes += item->GetSize ();
682  m_nTotalDroppedBytesAfterDequeue += item->GetSize ();
683 
684  NS_LOG_LOGIC ("m_traceDropAfterDequeue (p)");
685  m_traceDrop (item);
686  m_traceDropAfterDequeue (item);
687 }
688 
689 // The following explicit template instantiation declarations prevent all the
690 // translation units including this header file to implicitly instantiate the
691 // Queue<Packet> class and the Queue<QueueDiscItem> class. The unique instances
692 // of these classes are explicitly created through the macros
693 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,Packet) and
694 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,QueueDiscItem), which are included in queue.cc
695 extern template class Queue<Packet>;
696 extern template class Queue<QueueDiscItem>;
697 
698 } // namespace ns3
699 
700 #endif /* QUEUE_H */
A base class which provides memory management and object aggregation.
Definition: object.h:88
virtual void DoDispose(void)
Destructor implementation.
Definition: object.cc:346
Introspection did not find any typical Config paths.
Abstract base class for packet Queues.
Definition: queue.h:52
uint32_t GetTotalDroppedPacketsBeforeEnqueue(void) const
Definition: queue.cc:170
uint32_t GetTotalDroppedBytes(void) const
Definition: queue.cc:138
uint32_t m_nTotalDroppedBytesBeforeEnqueue
Total dropped bytes before enqueue.
Definition: queue.h:220
uint32_t GetTotalDroppedPackets(void) const
Definition: queue.cc:162
void ResetStatistics(void)
Resets the counts for dropped packets, dropped bytes, received packets, and received bytes.
Definition: queue.cc:186
TracedValue< uint32_t > m_nPackets
Number of packets in the queue.
Definition: queue.h:217
bool IsEmpty(void) const
Definition: queue.cc:82
uint32_t m_nTotalDroppedPacketsAfterDequeue
Total dropped packets after dequeue.
Definition: queue.h:224
uint32_t m_nTotalReceivedPackets
Total received packets.
Definition: queue.h:218
bool WouldOverflow(uint32_t nPackets, uint32_t nBytes) const
Check if the queue would overflow with additional bytes or packets Note: the check is performed accor...
Definition: queue.cc:224
uint32_t GetNPackets(void) const
Definition: queue.cc:90
uint32_t GetTotalDroppedBytesAfterDequeue(void) const
Definition: queue.cc:154
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 '>'.
Definition: queue.cc:73
virtual ~QueueBase()
Definition: queue.cc:67
uint32_t m_nTotalDroppedBytes
Total dropped bytes.
Definition: queue.h:219
uint32_t m_nTotalDroppedPacketsBeforeEnqueue
Total dropped packets before enqueue.
Definition: queue.h:223
uint32_t GetTotalDroppedBytesBeforeEnqueue(void) const
Definition: queue.cc:146
QueueSize m_maxSize
max queue size
Definition: queue.h:226
uint32_t m_nTotalDroppedPackets
Total dropped packets.
Definition: queue.h:222
uint32_t GetTotalReceivedPackets(void) const
Definition: queue.cc:130
void SetMaxSize(QueueSize size)
Set the maximum size of this queue.
Definition: queue.cc:200
uint32_t GetTotalReceivedBytes(void) const
Definition: queue.cc:122
TracedValue< uint32_t > m_nBytes
Number of bytes in the queue.
Definition: queue.h:215
QueueSize GetCurrentSize(void) const
Definition: queue.cc:106
uint32_t m_nTotalDroppedBytesAfterDequeue
Total dropped bytes after dequeue.
Definition: queue.h:221
uint32_t m_nTotalReceivedBytes
Total received bytes.
Definition: queue.h:216
uint32_t GetTotalDroppedPacketsAfterDequeue(void) const
Definition: queue.cc:178
static TypeId GetTypeId(void)
Get the type ID.
Definition: queue.cc:34
uint32_t GetNBytes(void) const
Definition: queue.cc:98
QueueSize GetMaxSize(void) const
Definition: queue.cc:217
Template class for packet Queues.
Definition: queue.h:262
void DropAfterDequeue(Ptr< Item > item)
Drop a packet after dequeue.
Definition: queue.h:675
void Flush(void)
Flush the queue by calling Remove() on each item enqueued.
Definition: queue.h:600
Item ItemType
Define ItemType as the type of the stored elements.
Definition: queue.h:309
void DropBeforeEnqueue(Ptr< Item > item)
Drop a packet before enqueue.
Definition: queue.h:659
std::list< Ptr< Item > >::iterator Iterator
Iterator.
Definition: queue.h:316
virtual Ptr< Item > Remove(void)=0
Remove an item from the Queue (each subclass defines the position), counting it and tracing it as bot...
TracedCallback< Ptr< const Item > > m_traceEnqueue
Traced callback: fired when a packet is enqueued.
Definition: queue.h:447
std::list< Ptr< Item > > m_packets
the items in the queue
Definition: queue.h:443
Ptr< Item > DoDequeue(ConstIterator pos)
Pull the item to dequeue from the queue.
Definition: queue.h:539
Iterator end(void)
Get an iterator which indicates past-the-last item in the queue.
Definition: queue.h:652
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.
TracedCallback< Ptr< const Item > > m_traceDropAfterDequeue
Traced callback: fired when a packet is dropped after dequeue.
Definition: queue.h:455
TracedCallback< Ptr< const Item > > m_traceDropBeforeEnqueue
Traced callback: fired when a packet is dropped before enqueue.
Definition: queue.h:453
NS_LOG_TEMPLATE_DECLARE
the log component
Definition: queue.h:444
virtual Ptr< Item > Dequeue(void)=0
Remove an item from the Queue (each subclass defines the position), counting it and tracing it as deq...
Queue()
Definition: queue.h:491
Iterator begin(void)
Get an iterator which refers to the first item in the queue.
Definition: queue.h:640
void DoDispose(void) override
Destructor implementation.
Definition: queue.h:611
bool DoEnqueue(ConstIterator pos, Ptr< Item > item)
Push an item in the queue.
Definition: queue.h:503
TracedCallback< Ptr< const Item > > m_traceDequeue
Traced callback: fired when a packet is dequeued.
Definition: queue.h:449
bool DoEnqueue(ConstIterator pos, Ptr< Item > item, Iterator &ret)
Push an item in the queue.
Definition: queue.h:511
virtual bool Enqueue(Ptr< Item > item)=0
Place an item into the Queue (each subclass defines the position)
TracedCallback< Ptr< const Item > > m_traceDrop
Traced callback: fired when a packet is dropped.
Definition: queue.h:451
Ptr< Item > DoRemove(ConstIterator pos)
Pull the item to drop from the queue.
Definition: queue.h:568
Ptr< const Item > DoPeek(ConstIterator pos) const
Peek the front item in the queue.
Definition: queue.h:620
std::list< Ptr< Item > >::const_iterator ConstIterator
Const iterator.
Definition: queue.h:314
ConstIterator begin(void) const
Get a const iterator which refers to the first item in the queue.
Definition: queue.h:634
ConstIterator end(void) const
Get a const iterator which indicates past-the-last item in the queue.
Definition: queue.h:646
static TypeId GetTypeId(void)
Get the type ID.
Definition: queue.h:465
virtual ~Queue()
Definition: queue.h:497
Class for representing queue sizes.
Definition: queue-size.h:95
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
Forward calls to a chain of Callback.
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
#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
#define NS_LOG_TEMPLATE_DEFINE(name)
Initialize a reference to a Log component.
Definition: log.h:239
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Every class exported by the ns3 library is enclosed in the ns3 namespace.