How to write a round robin scheduling module in NCTUNS?

 

[Goal]

   In this tutorial, two queues are used to demonstrate the round robin scheduling. One queue is for normal data packets and the other is for video data packets (The TOS field is not equal to 0 in the simulation.)

 

[Background]

1.      Refer to http://en.wikipedia.org/wiki/Round-robin_scheduling#Data_packet_scheduling to know what Round Robin scheduling is.

2.      Refer to  How to insert a new module (simple FIFO, sFIFO) into NCTUNS? to know how to add one module into NCTUNS.

3.      Refer to How to evaluate MPEG video transmission? to know how to do video simulation in NCTUNS.

4.      The Round Robin Scheduling is ported from NS by Example.

5.      Read the developer manual.

 

[Preparation]

1.      Create a folder called sFIFO_RR under /root/NCTUns-6.0/src/nctuns/module/ps.

2.      Put the following files into this folder.

(sfifo_rr.h)

#ifndef __NCTUNS_sfifo_rr_h__

#define __NCTUNS_sfifo_rr_h__

 

#include <object.h>

#include <packet.h>

#include <timer.h>

 

/* Define Interface Queue for every Interface */

struct ifqueue {

        ePacket_          *ifq_head; /* head of ifq */

        ePacket_          *ifq_tail; /* tail of ifq */

        int                    ifq_len;   /* current queue length */

        int                    ifq_maxlen;/* max queue length */

        int                    ifq_drops; /* drops count */

};

 

 

/* Define Macros for IFq */

#define IF_QFULL(ifq)           ((ifq)->ifq_len >= (ifq)->ifq_maxlen)

#define IF_DROP(ifq)            ((ifq)->ifq_drops++)

#define IF_ENQUEUE(ifq, m) { \

        if ((ifq)->ifq_tail == 0) \

                (ifq)->ifq_head = m; \

        else \

                (ifq)->ifq_tail->next_ep = m; \

        (ifq)->ifq_tail = m; \

        (ifq)->ifq_len++; \

}

#define IF_PREPEND(ifq, m) { \

        (m)->next_ep = (ifq)->ifq_head; \

        if ((ifq)->ifq_tail == 0) \

                (ifq)->ifq_tail = (m); \

        (ifq)->ifq_head = (m); \

        (ifq)->ifq_len++; \

}

#define IF_DEQUEUE(ifq, m) { \

        (m) = (ifq)->ifq_head; \

        if (m) { \

                if (((ifq)->ifq_head = (m)->next_ep) == 0) \

                        (ifq)->ifq_tail = 0; \

                (m)->next_ep = 0; \

                (ifq)->ifq_len--; \

        } \

}

 

 

class sfifo_rr : public NslObject {

 

 private:

 

        // two queues. One is for normal data packets while the other is for video packets.

struct ifqueue          if_snd; /* output interface queue */

    struct ifqueue      if_snd_video;

 

    //decide to dequeue which queues. 1: if_snd  2:if_snd_video

    int    deq_turn_;

 

 protected:

       int                   intrq(MBinder *);

 

 public:

 

        sfifo_rr(u_int32_t type, u_int32_t id, struct plist* pl, const char *name);

        ~sfifo_rr();

 

        int                    init();

        int                    recv(ePacket_ *);

        int                    send(ePacket_ *);

};

 

 

#endif /* __NCTUNS_sfifo_rr_h__ */

 

 

 

(sfifo_rr.cc)

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <fcntl.h>

#include <unistd.h>

#include <sys/stat.h>

#include <nctuns_api.h>

#include <ps/sFIFO_RR/sfifo_rr.h>

#include <exportStr.h>

#include <mbinder.h>

 

#include <netinet/in.h>

#include <netinet/udp.h>

#include <packet.h>

#include <maptable.h>

 

MODULE_GENERATOR(sfifo_rr);

 

sfifo_rr::sfifo_rr(u_int32_t type, u_int32_t id, struct plist* pl, const char *name)

                : NslObject(type, id, pl, name)

{

        /* disable flow control */

        s_flowctl = DISABLED;

        r_flowctl = DISABLED;

 

        /* initialize interface queue */

        if_snd.ifq_head = if_snd.ifq_tail = 0;

        if_snd.ifq_len = 0;

        if_snd.ifq_drops = 0;

 

        /* bind variable */

        vBind("max_qlen", &if_snd.ifq_maxlen);

    vBind("max_vqlen", &if_snd_video.ifq_maxlen);

 

        if_snd.ifq_len = 0;

        if_snd.ifq_maxlen = 25; /* by default */

        if_snd_video.ifq_len = 0;

        if_snd_video.ifq_maxlen = 25;

        deq_turn_=1;

}

 

sfifo_rr::~sfifo_rr() {

}

 

 

int sfifo_rr::init() {

 

  int       (NslObject::*upcall)(MBinder *);

 

  /* set upcall */

  upcall = (int (NslObject::*)(MBinder *))&sfifo_rr::intrq;

  sendtarget_->set_upcall(this, upcall);

  return(1);

}

 

int sfifo_rr::send(ePacket_ *pkt) {  

        Packet *p;

        struct ip *iph;    

 

        p = (Packet *)pkt->DataInfo_;

        iph = (struct ip *)p->pkt_sget();

 

        assert(pkt&&pkt->DataInfo_);

        /*

         * If Module-Binder Queue(MBQ) is full, we should

         * insert the outgoing packet into the interface

         * queue. If MBQ is not full, we can call the

         * put() or NslObject::send() method to pass the

         * outgoing packet to next module.

         */

        if( sendtarget_->qfull() ) {

               if(iph!=NULL && iph->ip_tos!=0) {

                    if(IF_QFULL(&if_snd_video)){

                      IF_DROP(&if_snd_video);

                      freePacket(pkt);

                      return(1);

                    }

                    IF_ENQUEUE(&if_snd_video, pkt);

                    return(1);

 

               }

               else {

              

                 /* MBQ is full, insert to ifq */

                 if (IF_QFULL(&if_snd)) {

                        /* ifq full, drop it! */

                        IF_DROP(&if_snd);

                        freePacket(pkt);

                        return(1);

                 }

                 /* otherwise, ifq not full, insert it */

                 IF_ENQUEUE(&if_snd, pkt);

                 return(1);

               }

        }   

        else {

                /*

                 * MBQ is not full, pass outgoing packet

                 * to next module.

                 */

                return(NslObject::send(pkt));

        }

}

 

 

int sfifo_rr::recv(ePacket_ *pkt) {

 

        /* Just by pass incoming packet */

        assert(pkt&&pkt->DataInfo_);

        return(NslObject::recv(pkt));

}

 

 

int sfifo_rr::intrq(MBinder *port) {

 

        ePacket_  *pkt;

 

        /*

         * Push the packet in the interface queue

         * to the MBQ. Whenever the pakcet in the

         * MBQ is sent, the scheduler will call this

         * member function to give sfifo module a

         * chance to send the next packet in the

         * interface queue.

         */

 

        if(deq_turn_ == 1) {

          IF_DEQUEUE(&if_snd, pkt);

          if(pkt == NULL) {

            IF_DEQUEUE(&if_snd_video, pkt);

            deq_turn_ = 1;

          }

          else

            deq_turn_ = 2;

        }

        else {

          IF_DEQUEUE(&if_snd_video, pkt);

          if(pkt == NULL) {

            IF_DEQUEUE(&if_snd, pkt);

            deq_turn_=2;

          }

          else

            deq_turn_=1;

        }

 

        if (pkt != NULL) {

                /*

                 * If still exist packet in the interface

                 * queue, we try to push it to the MBQ,

                 */

                assert(sendtarget_->enqueue(pkt) == 0);

        }

        return(1);

}

 

 

3.      Configure the related files and recompile.

 

[Simulation]

1.      Create a topology. (Video flow: Node 1à Node 4; TCP flow: Node 2à Node 6)

 

 

2.      Click “E” to edit property.

 

 

 

 

3.      Click “R” but don’t click Simulation/Run. We have to do some settings. (Here we only modify the FIFO to sFIFO_RR in the port id 3 of Node 3. If the reader is interested in the evaluation of video transmission. Please also modify the FIFO to sFIFO_video in Node 1 and Node 4.)

 

 

4.      Copy st to test.sim and click Simulation/Run to start simulation.

 

5.      View packet trace file to see whether RR works or not. (TCP flow starts at 10 seconds.) In the link from node 3 to node 5, if one tcp data packet is sent out, then node 3 will send out one video packet in the following.

 


Dr. 
Chih-Heng Ke

Department of Computer Science and Information Engineering, National Quemoy University, Taiwan

Email: smallko@gmail.com