queue.h

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2007 University of Washington
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

// The queue base class has a limit on its size, in terms of number of
// packets or number of bytes depending on the operating mode.
// The base class implements tracing and basic statistics calculations.

#ifndef QUEUE_H
#define QUEUE_H

#include "ns3/packet.h"
#include "ns3/object.h"
#include "ns3/traced-callback.h"
#include "ns3/traced-value.h"
#include "ns3/unused.h"
#include "ns3/log.h"
#include <string>
#include <sstream>
#include <list>

namespace ns3 {

class QueueBase : public Object
{
public:
  static TypeId GetTypeId (void);

  QueueBase ();
  virtual ~QueueBase ();

  static void AppendItemTypeIfNotPresent (std::string& typeId, const std::string& itemType);

  bool IsEmpty (void) const;

  uint32_t GetNPackets (void) const;

  uint32_t GetNBytes (void) const;

  uint32_t GetTotalReceivedBytes (void) const;

  uint32_t GetTotalReceivedPackets (void) const;

  uint32_t GetTotalDroppedBytes (void) const;

  uint32_t GetTotalDroppedBytesBeforeEnqueue (void) const;

  uint32_t GetTotalDroppedBytesAfterDequeue (void) const;

  uint32_t GetTotalDroppedPackets (void) const;

  uint32_t GetTotalDroppedPacketsBeforeEnqueue (void) const;

  uint32_t GetTotalDroppedPacketsAfterDequeue (void) const;

  void ResetStatistics (void);

  enum QueueMode
  {
    QUEUE_MODE_PACKETS,     
    QUEUE_MODE_BYTES,       
  };

  void SetMode (QueueBase::QueueMode mode);

  QueueBase::QueueMode GetMode (void) const;

  void SetMaxPackets (uint32_t maxPackets);

  uint32_t GetMaxPackets (void) const;

  void SetMaxBytes (uint32_t maxBytes);

  uint32_t GetMaxBytes (void) const;

#if 0
  // average calculation requires keeping around
  // a buffer with the date of arrival of past received packets
  // which are within the average window
  // so, it is quite costly to do it all the time.
  // Hence, it is disabled by default and must be explicitly
  // enabled with this method which specifies the size
  // of the average window in time units.
  void EnableRunningAverage (Time averageWindow);
  void DisableRunningAverage (void);
  // average
  double GetQueueSizeAverage (void);
  double GetReceivedBytesPerSecondAverage (void);
  double GetReceivedPacketsPerSecondAverage (void);
  double GetDroppedBytesPerSecondAverage (void);
  double GetDroppedPacketsPerSecondAverage (void);
  // variance
  double GetQueueSizeVariance (void);
  double GetReceivedBytesPerSecondVariance (void);
  double GetReceivedPacketsPerSecondVariance (void);
  double GetDroppedBytesPerSecondVariance (void);
  double GetDroppedPacketsPerSecondVariance (void);
#endif

private:
  TracedValue<uint32_t> m_nBytes;               
  uint32_t m_nTotalReceivedBytes;               
  TracedValue<uint32_t> m_nPackets;             
  uint32_t m_nTotalReceivedPackets;             
  uint32_t m_nTotalDroppedBytes;                
  uint32_t m_nTotalDroppedBytesBeforeEnqueue;   
  uint32_t m_nTotalDroppedBytesAfterDequeue;    
  uint32_t m_nTotalDroppedPackets;              
  uint32_t m_nTotalDroppedPacketsBeforeEnqueue; 
  uint32_t m_nTotalDroppedPacketsAfterDequeue;  

  uint32_t m_maxPackets;              
  uint32_t m_maxBytes;                
  QueueMode m_mode;                   

  template <typename Item>
  friend class Queue;
};


template <typename Item>
class Queue : public QueueBase
{
public:
  static TypeId GetTypeId (void);

  Queue ();
  virtual ~Queue ();

  virtual bool Enqueue (Ptr<Item> item) = 0;

  virtual Ptr<Item> Dequeue (void) = 0;

  virtual Ptr<Item>  Remove (void) = 0;

  virtual Ptr<const Item> Peek (void) const = 0;

  void Flush (void);

protected:

  typedef typename std::list<Ptr<Item> >::const_iterator ConstIterator;

  ConstIterator Head (void) const;

  ConstIterator Tail (void) const;

  bool DoEnqueue (ConstIterator pos, Ptr<Item> item);

  Ptr<Item> DoDequeue (ConstIterator pos);

  Ptr<Item> DoRemove (ConstIterator pos);

  Ptr<const Item> DoPeek (ConstIterator pos) const;

  void DropBeforeEnqueue (Ptr<Item> item);

  void DropAfterDequeue (Ptr<Item> item);

private:
  std::list<Ptr<Item> > m_packets;          
  NS_LOG_TEMPLATE_DECLARE;                  

  TracedCallback<Ptr<const Item> > m_traceEnqueue;
  TracedCallback<Ptr<const Item> > m_traceDequeue;
  TracedCallback<Ptr<const Item> > m_traceDrop;
  TracedCallback<Ptr<const Item> > m_traceDropBeforeEnqueue;
  TracedCallback<Ptr<const Item> > m_traceDropAfterDequeue;
};


template <typename Item>
TypeId
Queue<Item>::GetTypeId (void)
{
  std::string name = GetTypeParamName<Queue<Item> > ();
  static TypeId tid = TypeId (("ns3::Queue<" + name + ">").c_str ())
    .SetParent<QueueBase> ()
    .SetGroupName ("Network")
    .AddTraceSource ("Enqueue", "Enqueue a packet in the queue.",
                     MakeTraceSourceAccessor (&Queue<Item>::m_traceEnqueue),
                     "ns3::" + name + "::TracedCallback")
    .AddTraceSource ("Dequeue", "Dequeue a packet from the queue.",
                     MakeTraceSourceAccessor (&Queue<Item>::m_traceDequeue),
                     "ns3::" + name + "::TracedCallback")
    .AddTraceSource ("Drop", "Drop a packet (for whatever reason).",
                     MakeTraceSourceAccessor (&Queue<Item>::m_traceDrop),
                     "ns3::" + name + "::TracedCallback")
    .AddTraceSource ("DropBeforeEnqueue", "Drop a packet before enqueue.",
                     MakeTraceSourceAccessor (&Queue<Item>::m_traceDropBeforeEnqueue),
                     "ns3::" + name + "::TracedCallback")
    .AddTraceSource ("DropAfterDequeue", "Drop a packet after dequeue.",
                     MakeTraceSourceAccessor (&Queue<Item>::m_traceDropAfterDequeue),
                     "ns3::" + name + "::TracedCallback")
  ;
  return tid;
}

template <typename Item>
Queue<Item>::Queue ()
  : NS_LOG_TEMPLATE_DEFINE ("Queue")
{
}

template <typename Item>
Queue<Item>::~Queue ()
{
}

template <typename Item>
bool
Queue<Item>::DoEnqueue (ConstIterator pos, Ptr<Item> item)
{
  NS_LOG_FUNCTION (this << item);

  if (m_mode == QUEUE_MODE_PACKETS && (m_nPackets.Get () >= m_maxPackets))
    {
      NS_LOG_LOGIC ("Queue full (at max packets) -- dropping pkt");
      DropBeforeEnqueue (item);
      return false;
    }

  if (m_mode == QUEUE_MODE_BYTES && (m_nBytes.Get () + item->GetSize () > m_maxBytes))
    {
      NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- dropping pkt");
      DropBeforeEnqueue (item);
      return false;
    }

  m_packets.insert (pos, item);

  uint32_t size = item->GetSize ();
  m_nBytes += size;
  m_nTotalReceivedBytes += size;

  m_nPackets++;
  m_nTotalReceivedPackets++;

  NS_LOG_LOGIC ("m_traceEnqueue (p)");
  m_traceEnqueue (item);

  return true;
}

template <typename Item>
Ptr<Item>
Queue<Item>::DoDequeue (ConstIterator pos)
{
  NS_LOG_FUNCTION (this);

  if (m_nPackets.Get () == 0)
    {
      NS_LOG_LOGIC ("Queue empty");
      return 0;
    }

  Ptr<Item> item = *pos;
  m_packets.erase (pos);

  if (item != 0)
    {
      NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
      NS_ASSERT (m_nPackets.Get () > 0);

      m_nBytes -= item->GetSize ();
      m_nPackets--;

      NS_LOG_LOGIC ("m_traceDequeue (p)");
      m_traceDequeue (item);
    }
  return item;
}

template <typename Item>
Ptr<Item>
Queue<Item>::DoRemove (ConstIterator pos)
{
  NS_LOG_FUNCTION (this);

  if (m_nPackets.Get () == 0)
    {
      NS_LOG_LOGIC ("Queue empty");
      return 0;
    }

  Ptr<Item> item = *pos;
  m_packets.erase (pos);

  if (item != 0)
    {
      NS_ASSERT (m_nBytes.Get () >= item->GetSize ());
      NS_ASSERT (m_nPackets.Get () > 0);

      m_nBytes -= item->GetSize ();
      m_nPackets--;

      // packets are first dequeued and then dropped
      NS_LOG_LOGIC ("m_traceDequeue (p)");
      m_traceDequeue (item);

      DropAfterDequeue (item);
    }
  return item;
}

template <typename Item>
void
Queue<Item>::Flush (void)
{
  NS_LOG_FUNCTION (this);
  while (!IsEmpty ())
    {
      Remove ();
    }
}

template <typename Item>
Ptr<const Item>
Queue<Item>::DoPeek (ConstIterator pos) const
{
  NS_LOG_FUNCTION (this);

  if (m_nPackets.Get () == 0)
    {
      NS_LOG_LOGIC ("Queue empty");
      return 0;
    }

  return *pos;
}

template <typename Item>
typename Queue<Item>::ConstIterator Queue<Item>::Head (void) const
{
  return m_packets.cbegin ();
}

template <typename Item>
typename Queue<Item>::ConstIterator Queue<Item>::Tail (void) const
{
  return m_packets.cend ();
}

template <typename Item>
void
Queue<Item>::DropBeforeEnqueue (Ptr<Item> item)
{
  NS_LOG_FUNCTION (this << item);

  m_nTotalDroppedPackets++;
  m_nTotalDroppedPacketsBeforeEnqueue++;
  m_nTotalDroppedBytes += item->GetSize ();
  m_nTotalDroppedBytesBeforeEnqueue += item->GetSize ();

  NS_LOG_LOGIC ("m_traceDropBeforeEnqueue (p)");
  m_traceDrop (item);
  m_traceDropBeforeEnqueue (item);
}

template <typename Item>
void
Queue<Item>::DropAfterDequeue (Ptr<Item> item)
{
  NS_LOG_FUNCTION (this << item);

  m_nTotalDroppedPackets++;
  m_nTotalDroppedPacketsAfterDequeue++;
  m_nTotalDroppedBytes += item->GetSize ();
  m_nTotalDroppedBytesAfterDequeue += item->GetSize ();

  NS_LOG_LOGIC ("m_traceDropAfterDequeue (p)");
  m_traceDrop (item);
  m_traceDropAfterDequeue (item);
}

} // namespace ns3

#endif /* QUEUE_H */