Creating a Priority Queue based on runtime delay

205 views
Skip to first unread message

Ahmed Nasrallah

unread,
Oct 30, 2019, 11:03:13 PM10/30/19
to OMNeT++ Users
Dear all,

I have a slight issue in creating a priority queue using cPacketQueue containers. I have used the comparative function (shown below within my Switch module) as indicated in previous posts and the manual, but the packets during simulations are not being sorted correctly according to the the runtime delay.

------------------------------
int sw::MyCompareFunc (cObject *a, cObject *b) {
    if ((simTime() - (check_and_cast<customeMessage*>(a))->getTimestamp()) < (simTime() - (check_and_cast<customeMessage*>(b))->getTimestamp()))
        return -1;
    else if ((simTime() - (check_and_cast<customeMessage*>(a))->getTimestamp()) == (simTime() - (check_and_cast<customeMessage*>(b))->getTimestamp()))
        return 0;
    else
        return 1;
}
------------------------------

In my Queue class which I inherit the cPacketQueue, I have this constructor shown below,

------------------------------
myQueue::myQueue(const char *name,  CompareFunc cmp) {
    this->state = 0;
    this->capacity = 0;
    this->PacketPurged = 0;
    this->setName(name);
}
------------------------------

Then in my Switch module, I create a new queue during initilization time using this,
------------------------------
...
new myQueue ("myName", MyCompareFunc)
...
------------------------------

Every time a packet proceeds to ingress policing at the switch, I insert it into the priority queue and automatically the comparator function should be called to sort the queue, correct?

Many Thanks,
Ahmed

Ahmed Nasrallah

unread,
Nov 12, 2019, 5:38:01 AM11/12/19
to OMNeT++ Users
Hello,

Does anyone know of a priority queue example in omnet? I am trying to use a priority queue from the cPacketQueue class but have not done so successfully. I've attempted to do this manually, i.e., using loops and insertBefore/After functions, but this slowed down the simulation extremely. Any help is much appreciated.

Many Thanks,
Ahmed

Rudolf Hornig

unread,
Nov 13, 2019, 5:55:11 AM11/13/19
to OMNeT++ Users
Out of curiosity, have you checked the diffserv module and examples in INET? There is a lot of basic modules in inet.common.queue that can be used to create various compound queues. 


It is very easy to build a priority queue using a classifier, several separate queues and a priorityScheduler.

NOTE: In the upcoming INET 4.2 version the queueing modules have been extensively rewritten and enhanced. If you intend to work with queuing related models, I would give a try to the INET master branch. 4.2 is now feature complete and we are in the bugfuxing phase before releaase.

Ahmed Nasrallah

unread,
Nov 13, 2019, 9:51:30 AM11/13/19
to omn...@googlegroups.com
I was actually trying to avoid using INET (since I don't have much experience with it) and wanted to develop my project using only the cSimpleModule class in Omnet++. However, I'll take a look into the link given on how to rewrite my simple switch module into a compound module and import the classifier to create a priority queue, though I am not sure why and how a classifier or several queues are needed to create a priority queue?  Also, note that I only have a single traffic class for this queue with a single priority given.

As a side note, isn't a heap (more specifically a min-heap) supposed to implement a priority queue based on minimum timestamp (or maximum runtime delay)? Therefore, can't I implement a min-heap to sort the cPacketQueue queue on the timestamp? I tried using the comparator function given in the cPacketQueue class but was not sure how it worked in detail since the comparator function was apparently never called during the queue insert operation. I greatly appreciate any other ideas you have.

Thank you very much,
Ahmed


--
You received this message because you are subscribed to the Google Groups "OMNeT++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to omnetpp+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/omnetpp/db309c2c-174f-4baf-af28-7f30caaf225f%40googlegroups.com.


--
Ahmed Nasrallah
ASU Tempe, Student
PhD Computer Engineering
School of Electrical, Computer, and Energy Engineering (ECEE)

Rudolf Hornig

unread,
Nov 15, 2019, 7:38:42 AM11/15/19
to OMNeT++ Users


On Wednesday, November 13, 2019 at 3:51:30 PM UTC+1, Ahmed Nasrallah wrote:
I was actually trying to avoid using INET (since I don't have much experience with it) and wanted to develop my project using only the cSimpleModule class in Omnet++. However, I'll take a look into the link given on how to rewrite my simple switch module into a compound module and import the classifier to create a priority queue, though I am not sure why and how a classifier or several queues are needed to create a priority queue?  Also, note that I only have a single traffic class for this queue with a single priority given.

Of course if you don't need INET, you should not complicate your model and should go with the simplest approach.
 

As a side note, isn't a heap (more specifically a min-heap) supposed to implement a priority queue based on minimum timestamp (or maximum runtime delay)? Therefore, can't I implement a min-heap to sort the cPacketQueue queue on the timestamp? I tried using the comparator function given in the cPacketQueue class but was not sure how it worked in detail since the comparator function was apparently never called during the queue insert operation. I greatly appreciate any other ideas you have.

If the comparator function is provided, but never called, that's suspicious. Looking into your code snippet:

myQueue::myQueue(const char *name,  CompareFunc cmp) {
    this->state = 0;
    this->capacity = 0;
    this->PacketPurged = 0;
    this->setName(name);
}

you are forgetting to call the base constructor hence you do not actually set it in the base class resulting in a simple FIFO operation.

myQueue::myQueue(const char *name,  CompareFunc cmp) : cPacketQueue(name, cmp) {
    this->state = 0;
    this->capacity = 0;
    this->PacketPurged = 0;
}

Rudolf
 
To unsubscribe from this group and stop receiving emails from it, send an email to omnetpp+unsubscribe@googlegroups.com.

Ahmed Nasrallah

unread,
Nov 15, 2019, 7:48:53 AM11/15/19
to omn...@googlegroups.com
Hi Rudolf,

Thank you so much. That solved my problem. Now it is sorted correctly with improved performance during simulation. 

Thank you very much,
Ahmed
To unsubscribe from this group and stop receiving emails from it, send an email to omnetpp+u...@googlegroups.com.


--
Ahmed Nasrallah
ASU Tempe, Student
PhD Computer Engineering
School of Electrical, Computer, and Energy Engineering (ECEE)

--
You received this message because you are subscribed to the Google Groups "OMNeT++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to omnetpp+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/omnetpp/474275a1-318a-4c35-bbee-b6d58fafa2d6%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages