Packet scheduler in ns-3

[Andrea Palazzi]

Hi all,
we are two students of University of Modena and Reggio Emilia (Italy).

We are looking for a level 3 packet scheduler (even something simple, like RR, PRIO etc) to implement it in a topology we already created.

We already have asked Google ad surfed a lot of web pages, but we didn't find anything related to packet scheduling in ns3.

If someone ever handled this problem and has some code to share, or maybe can tell us where to start, this would be really helpful.

Thank you all

Andrea, Guido

[Tommaso Pecorella]

Sócc'mel... [typical expression used in the Bologna area, quite similar to Finnish's use of "Vittu"]

I'll keep using Engrish for the benefit of the other forum readers.

You will not find a L3 packet scheduler (yet) in ns-3, simply because there's no need for one.

L3 schedulers are a myth, because they are below L3. They may be above L2, but they are still below L3. Let's say that they're L3 "minus".

As an example, Linux's TC (see http://tldp.org/HOWTO/Traffic-Control-HOWTO/intro.html) handles full IP packets, and after they have been routed. However, they are scheduled before the MAC.

Anyway, beside the naming thing, why ns-3 doesn't have them. Because they aren't needed / used (yet).

In order to have a scheduler, you should also have a backpressure from the MAC, which right now we don't always have, plus a number of other elements.

Shortly put, actually ns-3 IP layers (v4 and v6) call the MAC Send function as soon as they have a packet ready. The queues and the schedulers are the ones in the MAC layer, and IP doesn't actually do anything.

This, of course, is a limitation, and if you would like to start working on it... patches are always welcome.

Cheers,

T.

[Nat P]

Il giorno mercoledì 3 settembre 2014 13:52:35 UTC+2, Tommaso Pecorella ha scritto:

In order to have a scheduler, you should also have a backpressure from the MAC, which right now we don't always have, plus a number of other elements.

Shortly put, actually ns-3 IP layers (v4 and v6) call the MAC Send function as soon as they have a packet ready. The queues and the schedulers are the ones in the MAC layer, and IP doesn't actually do anything.

What do you mean by backpressure?

Andrea, Guido, after a brief survey of IPv4 code, it seems that the only thing required is to add another layer between IP and MAC (call it, for example, QoS). IP calls QoS->Schedule(Ptr<Packet> p), which is responsible to call the MAC layer (of course, it can enqueue p, and send to the MAC layer an old scheduled packet, for example p1).

Implementations for QoS can be FIFO (the default one), or a Round Robin (one queue for tcp packets and another for UDP packets for example), or whatever you want (and your tutor need, after all :-D).

Have a nice day

[Tommaso Pecorella]

Backpressure:

the lower layer have to inform the upper one when it is ready to accept more packets.

Without backpressure the upper layer will just send everything to the lower layer as soon as it can.

If you build a shim layer between IP and L2, then you'll need the backpressure between L2 and the shim.

Cheers,

T.

[Nat P]

Il giorno mercoledì 3 settembre 2014 17:53:57 UTC+2, Tommaso Pecorella ha scritto:

Backpressure:

the lower layer have to inform the upper one when it is ready to accept more packets.

Without backpressure the upper layer will just send everything to the lower layer as soon as it can.

If you build a shim layer between IP and L2, then you'll need the backpressure between L2 and the shim.

Ok, now it makes sense.. but this move the complexity from "get a scheduler" to "get a backpressure", which seems dependent on L2 technology.

Thank you

[Nat P]

Ok, I have another doubt.

What if actually we have only a mis-definition about Queue class?
In other words.. the Queue class is a super class which can be suited for a Scheduling algorithm; after all, it has an Enqueue and a Dequeue method. Most L2 protocol (e.g. csma and p2p) already support queues.
Example (taken from p2p):

http://pastebin.com/rpdCxxut

So, for each packet, Send enqueue and call a Dequeue if the machine state is ready. After all, a droptail queue is a fifo scheduler.. with one queue.
So, I can build a RR scheduler, for one tcp and one udp flow, by (big pseudocode)

class RR : public Queue
{
   (...)
private:

   Ptr<Queue> m_tcpQueue;
   Ptr<Queue> m_udpQueue;
}

and choosing from one or the other when someone call my Dequeue method. The two private fields can be any queue (Droptail maybe is the most immediate).

Implementatively, we are working inside L2; Logically, we are between L2 and L3, without modifying any line of L3 algorithm.

Am I wrong ?

Thank you

[Tommaso Pecorella]

You're right, but I'd rather have this done in a formal way, rather than using a "trick".

Formal way: define a L2.5 similar to TC.

Trick: using the queues. It's a trick because it works if and only if the queue is used in the way you said (there's no guarantee that the queue isn't used in a different way).

However, if one is on a rush, the trick may work :)

Cheers,

T.