Difference between revisions of "Priority-queue-proposal"

From Nsnam
Jump to: navigation, search
(priority queue proposal)
 
(PriorityQueue class)
Line 41: Line 41:
 
# ECN support doesn't require removing the headers
 
# ECN support doesn't require removing the headers
 
# It is easier to peek the transport header if the Ip header hasn't been added yet.  Flow classification such as in fq_codel requires access to the 5-tuple.
 
# It is easier to peek the transport header if the Ip header hasn't been added yet.  Flow classification such as in fq_codel requires access to the 5-tuple.
 +
But the drawback to this is that the neighbor discovery cache needs also to be modified to enqueue packets that don't yet have IP headers; m_pending can no longer be a std::list<Ptr<Packet> >;
  
 
Current implementation is in ''src/internet/model/priority-queue.{cc,h}''.
 
Current implementation is in ''src/internet/model/priority-queue.{cc,h}''.

Revision as of 23:27, 24 February 2015

Main Page - Current Development - Developer FAQ - Tools - Related Projects - Project Ideas - Summer Projects

Installation - Troubleshooting - User FAQ - HOWTOs - Samples - Models - Education - Contributed Code - Papers

This page describes a design proposal for ns-3.23.

Problem statement

  • ns-3 needs to support Internet-aware queues such as fq_codel
  • Current ns3::Queue class has an Ethernet header already added, and doesn't provide easy visibility to IP or transport headers
  • An additional complexity is that wireless devices implement their own queues; for instance, WiFi does not even use class ns3::Queue
  • ECN support is needed, so not only do we need to peek at the IP header or use Packet metadata, we need to sometimes modify it.

Proposed solution

For these problems, it seems advantageous to define a new 'priority queue' layer that sits above the devices and below the IP forwarding layer, such as is done in Linux. Natale Patriciello proposed this on the list: http://mailman.isi.edu/pipermail/ns-developers/2014-November/012398.html

  • this will allow easier access to the IP and transport header, perhaps even deferring the addition of the IP header until just before sending it to the device
  • this will allow uniform application of these queues across all device types
  • this may also help to solve the UDP backpressure problem, bug 1006

The main consequence is that it requires flow control between the priority queue layer and the device layer. All ns-3 devices need to be extended to support backpressure to the priority queue layer.

Details

Each Ipv4Interface object is extended to include an ns3::PriorityQueue object. This is a different base class than ns3::Queue. I chose to put it in the interface object instead of ns3::Ipv4L3Protocol, which is an implementation detail. If we place it above Ipv4Interface, we need to have a data structure in the Ipv4L3Protocol that still maintains a per-interface queue within that class.

PriorityQueue class

This differs from ns3::Queue because it needs to support enqueuing of a struct, not just a Ptr<Packet>. At this point of the stack, we have a destination hardware address, and the fully formed IP packet; we combine these in a struct:

 struct QueueElement
 {
   Ptr<Packet> p;
   Address dest;
 };

and we enqueue these queue elements:

 bool Enqueue (struct QueueElement q);
 struct QueueElement Dequeue (void);

This approach could even be extended further to allow the Ipv4Header or Ipv6Header to be included in the struct, deferring its addition from Ipv4L3Protocol to this class. This is probably beneficial for two reasons:

  1. ECN support doesn't require removing the headers
  2. It is easier to peek the transport header if the Ip header hasn't been added yet. Flow classification such as in fq_codel requires access to the 5-tuple.

But the drawback to this is that the neighbor discovery cache needs also to be modified to enqueue packets that don't yet have IP headers; m_pending can no longer be a std::list<Ptr<Packet> >;

Current implementation is in src/internet/model/priority-queue.{cc,h}.

Ipv4Interface changes

The main change to this class is the priority queue inclusion, the registering of this object with the NetDevice callback, and the logic to enqueue/dequeue packets. Where the object once called down to NetDevice::Send(), we add a DeviceQueueTransmit() method that looks like this:

 void
 Ipv4Interface::DeviceQueueTransmit (Ptr<Packet> packet, const Address& dest)
 {
   NS_LOG_FUNCTION (this << packet << dest);
   NS_ASSERT_MSG (m_prioQueue, "This method being called before DoSetup; shouldn't happen");
   struct PriorityQueue::QueueElement q;
   q.p = packet;
   q.dest = dest;
   m_prioQueue->Enqueue (q);
   if (m_device->IsReady ())
     {
       // We enqueue and dequeue immediately rather than bypass the queue in 
       // case the queue needs to know about such packets for future scheduling
       q = m_prioQueue->Dequeue ();
       m_device->Send (q.p, q.dest, Ipv4L3Protocol::PROT_NUMBER);
     }
 }

and we add a callback target that allows the interface to try to dequeue if the device becomes unblocked:

 void
 Ipv4Interface::DeviceReady (Ptr<NetDevice> nd)
 {
   NS_LOG_FUNCTION (this << nd);
   NS_LOG_UNCOND ("Device is ready");
   struct PriorityQueue::QueueElement q;
   q = m_prioQueue->Dequeue ();
   if (!q.p)
     {
       NS_LOG_LOGIC ("No packet to send");
       return;
     }
   do
     {
       m_device->Send (q.p, q.dest, Ipv4L3Protocol::PROT_NUMBER);
       if (m_device->IsReady ())
         {
           q = m_prioQueue->Dequeue ();
         }
       else
         {
           break;
         }
     }
   while (q.p);
 }

The suggested default PriorityQueue is the new PfifoFast queue that models the Linux default.

NetDevice changes

Each ns3::NetDevice is extended to support this in the base class:

 diff -r 4e1543dc9d68 -r b6891bd5dedd src/network/model/net-device.h
 --- a/src/network/model/net-device.h	Thu Nov 06 15:18:11 2014 -0800
 +++ b/src/network/model/net-device.h	Fri Jan 16 15:57:07 2015 -0800
   @@ -335,6 +335,22 @@
     */
    virtual bool SupportsSendFrom (void) const = 0;
  
 +  
 +  /**
 +   * Callback invoked when device wants to tell the higher layer that it
 +   * may send a packet
 +   */
 +  typedef Callback < void, Ptr<NetDevice> > DeviceReadyCallback;
 +
 +  virtual void SetDeviceReadyCallback (DeviceReadyCallback cb) { m_deviceReadyCallback = cb; }
 +
 +  /**
 +   * \return true if this interface is ready for a packet from the higher layer
 +   */
 +  virtual bool IsReady (void) const = 0;
 +
 +private:
 +  DeviceReadyCallback m_deviceReadyCallback;
  };

The NetDevice objects support polling (IsReady ()) or callbacks to notify when the upper layer can send a packet. If the device enters a not ready state, the callback is invoked when the device becomes ready.

An example of how this is supported is as follows. In the PointToPointNetDevice, IsReady() is implemented as follows:

 +bool
 +PointToPointNetDevice::IsReady (void) const
 +{
 +  NS_LOG_FUNCTION (this);
 +  return !(m_queue->IsFull ());
 +}

and the callback is called when a packet is sent, as follows:

 +  bool blocked = m_queue->IsFull ();
    Ptr<Packet> p = m_queue->Dequeue ();
    if (p == 0)
      {
 -      //
 -      // No packet was on the queue, so we just exit.
 -      //
 +      NS_LOG_LOGIC ("No pending packets in device queue after tx complete");
 +      if (blocked && !m_deviceReadyCallback.IsNull())
 +        {
 +          m_deviceReadyCallback (this);
 +        }
      return;

The above is the basic idea, to be implemented across all devices. It is not clear yet how the more complicated device queueing structures (e.g. WiFi 802.11e) will manage and report their "IsReady()" status. In the current code, only PointToPointNetDevice has been implemented this way; other devices simply always return true to IsReady(), so that the priority queue never faces backpressure.

Other changes

In addition, queue type ns3::RedQueue should be moved from src/network/utils to src/internet/model/ and ported to class PriorityQueue.

We can possibly implement some UDP backpressure by allowing the UdpSocket some access to the priority queue corresponding to its interface. Doing so with callbacks may be tricky since routing may change the underlying device for the socket.

Status

See http://code.nsnam.org/tomh/ns-3-dev-aqm

  • No ECN support yet
  • No support of other devices except PointToPointNetDevice
  • Tracing support of the priority queues needs to be added