Tomh: /* Status */

2015-02-24T23:28:12Z

Status

← Older revision		Revision as of 23:28, 24 February 2015
Line 168:		Line 168:
	* other changes to support the above refactoring: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/b6891bd5dedd		* other changes to support the above refactoring: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/b6891bd5dedd

			In addition:
	* No ECN support yet		* No ECN support yet
	* No support of other devices except PointToPointNetDevice		* No support of other devices except PointToPointNetDevice
	* Tracing support of the priority queues needs to be added		* Tracing support of the priority queues needs to be added

Tomh: /* Status */

2015-02-24T23:27:50Z

Status

← Older revision		Revision as of 23:27, 24 February 2015
Line 165:		Line 165:

	See http://code.nsnam.org/tomh/ns-3-dev-aqm		See http://code.nsnam.org/tomh/ns-3-dev-aqm
	** Pfifo fast queue: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/4e1543dc9d68		* Pfifo fast queue: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/4e1543dc9d68
	** other changes to support the above refactoring: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/b6891bd5dedd		* other changes to support the above refactoring: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/b6891bd5dedd

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

Tomh: /* PriorityQueue class */

2015-02-24T23:27:14Z

PriorityQueue class

← Older revision		Revision as of 23:27, 24 February 2015
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}''.

Tomh: priority queue proposal

2015-02-24T23:22:57Z

priority queue proposal

New page

{{TOC}}

This page describes a design proposal for [[ns-3.23]].

== Problem statement ==

* ns-3 needs to support Internet-aware queues such as [http://www.bufferbloat.net/projects/codel/wiki/Technical_description_of_FQ_CoDel 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, [https://www.nsnam.org/bugzilla/show_bug.cgi?id=1006 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:
# 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.

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
** Pfifo fast queue: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/4e1543dc9d68
** other changes to support the above refactoring: http://code.nsnam.org/tomh/ns-3-dev-aqm/rev/b6891bd5dedd

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

Priority-queue-proposal - Revision history

Tomh: /* Status */

Tomh: /* Status */

Tomh: /* PriorityQueue class */

Tomh: priority queue proposal