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 "ns3/queue-fwd.h"
34#include <string>
35#include <sstream>
36#include <type_traits>
37
38namespace ns3 {
39
52class QueueBase : public Object
53{
54public:
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
119
125 uint32_t GetTotalDroppedBytes (void) const;
126
133
140
146 uint32_t GetTotalDroppedPackets (void) const;
147
154
161
166 void ResetStatistics (void);
167
175 void SetMaxSize (QueueSize size);
176
180 QueueSize GetMaxSize (void) const;
181
189 bool WouldOverflow (uint32_t nPackets, uint32_t nBytes) const;
190
191#if 0
192 // average calculation requires keeping around
193 // a buffer with the date of arrival of past received packets
194 // which are within the average window
195 // so, it is quite costly to do it all the time.
196 // Hence, it is disabled by default and must be explicitly
197 // enabled with this method which specifies the size
198 // of the average window in time units.
199 void EnableRunningAverage (Time averageWindow);
200 void DisableRunningAverage (void);
201 // average
202 double GetQueueSizeAverage (void);
203 double GetReceivedBytesPerSecondAverage (void);
204 double GetReceivedPacketsPerSecondAverage (void);
205 double GetDroppedBytesPerSecondAverage (void);
206 double GetDroppedPacketsPerSecondAverage (void);
207 // variance
208 double GetQueueSizeVariance (void);
209 double GetReceivedBytesPerSecondVariance (void);
210 double GetReceivedPacketsPerSecondVariance (void);
211 double GetDroppedBytesPerSecondVariance (void);
212 double GetDroppedPacketsPerSecondVariance (void);
213#endif
214
215protected:
226
228};
229
230
265template <typename Item, typename Container>
266class Queue : public QueueBase
267{
268public:
273 static TypeId GetTypeId (void);
274
276 virtual ~Queue ();
277
283 virtual bool Enqueue (Ptr<Item> item) = 0;
284
290 virtual Ptr<Item> Dequeue (void) = 0;
291
297 virtual Ptr<Item> Remove (void) = 0;
298
304 virtual Ptr<const Item> Peek (void) const = 0;
305
311 void Flush (void);
312
314 typedef Item ItemType;
315
316protected:
318 typedef typename Container::const_iterator ConstIterator;
320 typedef typename Container::iterator Iterator;
321
327 const Container& GetContainer (void) const;
328
336
345
352
359
366
376
386
388 void DoDispose (void) override;
389
390private:
398 template <class, class = void>
400 {
405 static Ptr<Item> GetItem (const Container&, const ConstIterator it)
406 {
407 return *it;
408 }
409 };
410
417 template <class T>
418 struct MakeGetItem<T, std::void_t<decltype (std::declval<T> ().GetItem (std::declval<ConstIterator> ()))> >
419 {
425 static Ptr<Item> GetItem (const Container& container, const ConstIterator it)
426 {
427 return container.GetItem (it);
428 }
429 };
430
433
444};
445
446
451template <typename Item, typename Container>
452TypeId
454{
455 std::string name = GetTemplateClassName<Queue<Item, Container>> ();
456 auto startPos = name.find ('<') + 1;
457 auto endPos = name.find_first_of (",>", startPos);
458 std::string tcbName = "ns3::" + name.substr (startPos, endPos - startPos) + "::TracedCallback";
459
460 static TypeId tid = TypeId (name)
462 .SetGroupName ("Network")
463 .AddTraceSource ("Enqueue", "Enqueue a packet in the queue.",
465 tcbName)
466 .AddTraceSource ("Dequeue", "Dequeue a packet from the queue.",
468 tcbName)
469 .AddTraceSource ("Drop", "Drop a packet (for whatever reason).",
471 tcbName)
472 .AddTraceSource ("DropBeforeEnqueue", "Drop a packet before enqueue.",
474 tcbName)
475 .AddTraceSource ("DropAfterDequeue", "Drop a packet after dequeue.",
477 tcbName)
478 ;
479 return tid;
480}
481
482template <typename Item, typename Container>
484 : NS_LOG_TEMPLATE_DEFINE ("Queue")
485{
486}
487
488template <typename Item, typename Container>
490{
491}
492
493template <typename Item, typename Container>
494const Container&
496{
497 return m_packets;
498}
499
500template <typename Item, typename Container>
501bool
503{
504 Iterator ret;
505 return DoEnqueue (pos, item, ret);
506}
507
508template <typename Item, typename Container>
509bool
511{
512 NS_LOG_FUNCTION (this << item);
513
514 if (GetCurrentSize () + item > GetMaxSize ())
515 {
516 NS_LOG_LOGIC ("Queue full -- dropping pkt");
517 DropBeforeEnqueue (item);
518 return false;
519 }
520
521 ret = m_packets.insert (pos, item);
522
523 uint32_t size = item->GetSize ();
524 m_nBytes += size;
525 m_nTotalReceivedBytes += size;
526
527 m_nPackets++;
528 m_nTotalReceivedPackets++;
529
530 NS_LOG_LOGIC ("m_traceEnqueue (p)");
531 m_traceEnqueue (item);
532
533 return true;
534}
535
536template <typename Item, typename Container>
539{
540 NS_LOG_FUNCTION (this);
541
542 if (m_nPackets.Get () == 0)
543 {
544 NS_LOG_LOGIC ("Queue empty");
545 return 0;
546 }
547
548 Ptr<Item> item = MakeGetItem<Container>::GetItem (m_packets, pos);
549
550 if (item != 0)
551 {
552 m_packets.erase (pos);
553 NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
554 NS_ASSERT (m_nPackets.Get () > 0);
555
556 m_nBytes -= item->GetSize ();
557 m_nPackets--;
558
559 NS_LOG_LOGIC ("m_traceDequeue (p)");
560 m_traceDequeue (item);
561 }
562 return item;
563}
564
565template <typename Item, typename Container>
568{
569 NS_LOG_FUNCTION (this);
570
571 if (m_nPackets.Get () == 0)
572 {
573 NS_LOG_LOGIC ("Queue empty");
574 return 0;
575 }
576
577 Ptr<Item> item = MakeGetItem<Container>::GetItem (m_packets, pos);
578
579 if (item != 0)
580 {
581 m_packets.erase (pos);
582 NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
583 NS_ASSERT (m_nPackets.Get () > 0);
584
585 m_nBytes -= item->GetSize ();
586 m_nPackets--;
587
588 // packets are first dequeued and then dropped
589 NS_LOG_LOGIC ("m_traceDequeue (p)");
590 m_traceDequeue (item);
591
592 DropAfterDequeue (item);
593 }
594 return item;
595}
596
597template <typename Item, typename Container>
598void
600{
601 NS_LOG_FUNCTION (this);
602 while (!IsEmpty ())
603 {
604 Remove ();
605 }
606}
607
608template <typename Item, typename Container>
609void
611{
612 NS_LOG_FUNCTION (this);
613 m_packets.clear ();
615}
616
617template <typename Item, typename Container>
620{
621 NS_LOG_FUNCTION (this);
622
623 if (m_nPackets.Get () == 0)
624 {
625 NS_LOG_LOGIC ("Queue empty");
626 return 0;
627 }
628
629 return MakeGetItem<Container>::GetItem (m_packets, pos);
630}
631
632template <typename Item, typename Container>
633void
635{
636 NS_LOG_FUNCTION (this << item);
637
638 m_nTotalDroppedPackets++;
639 m_nTotalDroppedPacketsBeforeEnqueue++;
640 m_nTotalDroppedBytes += item->GetSize ();
641 m_nTotalDroppedBytesBeforeEnqueue += item->GetSize ();
642
643 NS_LOG_LOGIC ("m_traceDropBeforeEnqueue (p)");
644 m_traceDrop (item);
645 m_traceDropBeforeEnqueue (item);
646}
647
648template <typename Item, typename Container>
649void
651{
652 NS_LOG_FUNCTION (this << item);
653
654 m_nTotalDroppedPackets++;
655 m_nTotalDroppedPacketsAfterDequeue++;
656 m_nTotalDroppedBytes += item->GetSize ();
657 m_nTotalDroppedBytesAfterDequeue += item->GetSize ();
658
659 NS_LOG_LOGIC ("m_traceDropAfterDequeue (p)");
660 m_traceDrop (item);
661 m_traceDropAfterDequeue (item);
662}
663
664// The following explicit template instantiation declarations prevent all the
665// translation units including this header file to implicitly instantiate the
666// Queue<Packet> class and the Queue<QueueDiscItem> class. The unique instances
667// of these classes are explicitly created through the macros
668// NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,Packet) and
669// NS_OBJECT_TEMPLATE_CLASS_DEFINE (Queue,QueueDiscItem), which are included in queue.cc
670extern template class Queue<Packet>;
671extern template class Queue<QueueDiscItem>;
672
673} // namespace ns3
674
675#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
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
Introspection did not find any typical Config paths.
Abstract base class for packet Queues.
Definition: queue.h:53
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:221
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:218
bool IsEmpty(void) const
Definition: queue.cc:82
uint32_t m_nTotalDroppedPacketsAfterDequeue
Total dropped packets after dequeue.
Definition: queue.h:225
uint32_t m_nTotalReceivedPackets
Total received packets.
Definition: queue.h:219
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:220
uint32_t m_nTotalDroppedPacketsBeforeEnqueue
Total dropped packets before enqueue.
Definition: queue.h:224
uint32_t GetTotalDroppedBytesBeforeEnqueue(void) const
Definition: queue.cc:146
QueueSize m_maxSize
max queue size
Definition: queue.h:227
uint32_t m_nTotalDroppedPackets
Total dropped packets.
Definition: queue.h:223
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:216
QueueSize GetCurrentSize(void) const
Definition: queue.cc:106
uint32_t m_nTotalDroppedBytesAfterDequeue
Total dropped bytes after dequeue.
Definition: queue.h:222
uint32_t m_nTotalReceivedBytes
Total received bytes.
Definition: queue.h:217
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:267
Ptr< Item > DoRemove(ConstIterator pos)
Pull the item to drop from the queue.
Definition: queue.h:567
static TypeId GetTypeId(void)
Get the type ID.
Definition: queue.h:453
bool DoEnqueue(ConstIterator pos, Ptr< Item > item, Iterator &ret)
Push an item in the queue.
Definition: queue.h:510
virtual Ptr< Item > Dequeue(void)=0
Remove an item from the Queue (each subclass defines the position), counting it and tracing it as deq...
TracedCallback< Ptr< const Item > > m_traceDrop
Traced callback: fired when a packet is dropped.
Definition: queue.h:439
Ptr< Item > DoDequeue(ConstIterator pos)
Pull the item to dequeue from the queue.
Definition: queue.h:538
Container m_packets
the items in the queue
Definition: queue.h:431
TracedCallback< Ptr< const Item > > m_traceDropAfterDequeue
Traced callback: fired when a packet is dropped after dequeue.
Definition: queue.h:443
bool DoEnqueue(ConstIterator pos, Ptr< Item > item)
Push an item in the queue.
Definition: queue.h:502
Ptr< const Item > DoPeek(ConstIterator pos) const
Peek the front item in the queue.
Definition: queue.h:619
Queue()
Definition: queue.h:483
void DropAfterDequeue(Ptr< Item > item)
Drop a packet after dequeue.
Definition: queue.h:650
TracedCallback< Ptr< const Item > > m_traceEnqueue
Traced callback: fired when a packet is enqueued.
Definition: queue.h:435
virtual bool Enqueue(Ptr< Item > item)=0
Place an item into the Queue (each subclass defines the position)
TracedCallback< Ptr< const Item > > m_traceDequeue
Traced callback: fired when a packet is dequeued.
Definition: queue.h:437
const Container & GetContainer(void) const
Get a const reference to the container of queue items.
Definition: queue.h:495
void DropBeforeEnqueue(Ptr< Item > item)
Drop a packet before enqueue.
Definition: queue.h:634
void Flush(void)
Flush the queue by calling Remove() on each item enqueued.
Definition: queue.h:599
void DoDispose(void) override
Destructor implementation.
Definition: queue.h:610
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.
Container::iterator Iterator
Iterator.
Definition: queue.h:320
virtual ~Queue()
Definition: queue.h:489
TracedCallback< Ptr< const Item > > m_traceDropBeforeEnqueue
Traced callback: fired when a packet is dropped before enqueue.
Definition: queue.h:441
Container::const_iterator ConstIterator
Const iterator.
Definition: queue.h:318
virtual Ptr< Item > Remove(void)=0
Remove an item from the Queue (each subclass defines the position), counting it and tracing it as bot...
Item ItemType
Define ItemType as the type of the stored elements.
Definition: queue.h:314
NS_LOG_TEMPLATE_DECLARE
the log component
Definition: queue.h:432
Class for representing queue sizes.
Definition: queue-size.h:95
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:104
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.
STL namespace.
static Ptr< Item > GetItem(const Container &container, const ConstIterator it)
Definition: queue.h:425
Struct providing a static method returning the object stored within the queue that is included in the...
Definition: queue.h:400
static Ptr< Item > GetItem(const Container &, const ConstIterator it)
Definition: queue.h:405