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 
386 
393 
400 
409  void DropBeforeEnqueue (Ptr<Item> item);
410 
419  void DropAfterDequeue (Ptr<Item> item);
420 
421 private:
422  std::list<Ptr<Item> > m_packets;
424 
435 };
436 
437 
442 template <typename Item>
443 TypeId
445 {
446  std::string name = GetTypeParamName<Queue<Item> > ();
447  static TypeId tid = TypeId (("ns3::Queue<" + name + ">").c_str ())
448  .SetParent<QueueBase> ()
449  .SetGroupName ("Network")
450  .AddTraceSource ("Enqueue", "Enqueue a packet in the queue.",
452  "ns3::" + name + "::TracedCallback")
453  .AddTraceSource ("Dequeue", "Dequeue a packet from the queue.",
455  "ns3::" + name + "::TracedCallback")
456  .AddTraceSource ("Drop", "Drop a packet (for whatever reason).",
458  "ns3::" + name + "::TracedCallback")
459  .AddTraceSource ("DropBeforeEnqueue", "Drop a packet before enqueue.",
461  "ns3::" + name + "::TracedCallback")
462  .AddTraceSource ("DropAfterDequeue", "Drop a packet after dequeue.",
464  "ns3::" + name + "::TracedCallback")
465  ;
466  return tid;
467 }
468 
469 template <typename Item>
471  : NS_LOG_TEMPLATE_DEFINE ("Queue")
472 {
473 }
474 
475 template <typename Item>
477 {
478 }
479 
480 template <typename Item>
481 bool
483 {
484  NS_LOG_FUNCTION (this << item);
485 
486  if (GetCurrentSize () + item > GetMaxSize ())
487  {
488  NS_LOG_LOGIC ("Queue full -- dropping pkt");
489  DropBeforeEnqueue (item);
490  return false;
491  }
492 
493  m_packets.insert (pos, item);
494 
495  uint32_t size = item->GetSize ();
496  m_nBytes += size;
497  m_nTotalReceivedBytes += size;
498 
499  m_nPackets++;
500  m_nTotalReceivedPackets++;
501 
502  NS_LOG_LOGIC ("m_traceEnqueue (p)");
503  m_traceEnqueue (item);
504 
505  return true;
506 }
507 
508 template <typename Item>
509 Ptr<Item>
511 {
512  NS_LOG_FUNCTION (this);
513 
514  if (m_nPackets.Get () == 0)
515  {
516  NS_LOG_LOGIC ("Queue empty");
517  return 0;
518  }
519 
520  Ptr<Item> item = *pos;
521  m_packets.erase (pos);
522 
523  if (item != 0)
524  {
525  NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
526  NS_ASSERT (m_nPackets.Get () > 0);
527 
528  m_nBytes -= item->GetSize ();
529  m_nPackets--;
530 
531  NS_LOG_LOGIC ("m_traceDequeue (p)");
532  m_traceDequeue (item);
533  }
534  return item;
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  // packets are first dequeued and then dropped
561  NS_LOG_LOGIC ("m_traceDequeue (p)");
562  m_traceDequeue (item);
563 
564  DropAfterDequeue (item);
565  }
566  return item;
567 }
568 
569 template <typename Item>
570 void
572 {
573  NS_LOG_FUNCTION (this);
574  while (!IsEmpty ())
575  {
576  Remove ();
577  }
578 }
579 
580 template <typename Item>
583 {
584  NS_LOG_FUNCTION (this);
585 
586  if (m_nPackets.Get () == 0)
587  {
588  NS_LOG_LOGIC ("Queue empty");
589  return 0;
590  }
591 
592  return *pos;
593 }
594 
595 template <typename Item>
597 {
598  return m_packets.cbegin ();
599 }
600 
601 template <typename Item>
603 {
604  return m_packets.begin ();
605 }
606 
607 template <typename Item>
609 {
610  return m_packets.cend ();
611 }
612 
613 template <typename Item>
615 {
616  return m_packets.end ();
617 }
618 
619 template <typename Item>
620 void
622 {
623  NS_LOG_FUNCTION (this << item);
624 
625  m_nTotalDroppedPackets++;
626  m_nTotalDroppedPacketsBeforeEnqueue++;
627  m_nTotalDroppedBytes += item->GetSize ();
628  m_nTotalDroppedBytesBeforeEnqueue += item->GetSize ();
629 
630  NS_LOG_LOGIC ("m_traceDropBeforeEnqueue (p)");
631  m_traceDrop (item);
632  m_traceDropBeforeEnqueue (item);
633 }
634 
635 template <typename Item>
636 void
638 {
639  NS_LOG_FUNCTION (this << item);
640 
641  m_nTotalDroppedPackets++;
642  m_nTotalDroppedPacketsAfterDequeue++;
643  m_nTotalDroppedBytes += item->GetSize ();
644  m_nTotalDroppedBytesAfterDequeue += item->GetSize ();
645 
646  NS_LOG_LOGIC ("m_traceDropAfterDequeue (p)");
647  m_traceDrop (item);
648  m_traceDropAfterDequeue (item);
649 }
650 
651 // The following explicit template instantiation declarations prevent all the
652 // translation units including this header file to implicitly instantiate the
653 // Queue<Packet> class and the Queue<QueueDiscItem> class. The unique instances
654 // of these classes are explicitly created through the macros
655 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,Packet) and
656 // NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,QueueDiscItem), which are included in queue.cc
657 extern template class Queue<Packet>;
658 extern template class Queue<QueueDiscItem>;
659 
660 } // namespace ns3
661 
662 #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:102
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:428
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:423
Forward calls to a chain of Callback.
void Flush(void)
Flush the queue.
Definition: queue.h:571
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:539
TracedCallback< Ptr< const Item > > m_traceDrop
Traced callback: fired when a packet is dropped.
Definition: queue.h:430
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:444
TracedCallback< Ptr< const Item > > m_traceDropAfterDequeue
Traced callback: fired when a packet is dropped after dequeue.
Definition: queue.h:434
ConstIterator begin(void) const
Get a const iterator which refers to the first item in the queue.
Definition: queue.h:596
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:426
void DropAfterDequeue(Ptr< Item > item)
Drop a packet after dequeue.
Definition: queue.h:637
ConstIterator end(void) const
Get a const iterator which indicates past-the-last item in the queue.
Definition: queue.h:608
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:470
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:432
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
Ptr< const Item > DoPeek(ConstIterator pos) const
Peek the front item in the queue.
Definition: queue.h:582
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:621
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:510
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:922
bool DoEnqueue(ConstIterator pos, Ptr< Item > item)
Push an item in the queue.
Definition: queue.h:482
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:422
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:476
TracedValue< uint32_t > m_nBytes
Number of bytes in the queue.
Definition: queue.h:207