In wireless multi-hop networks, how to measure the delay time from the sender to each hop?

 

[Background]

1.      The first way to measure the delay time from the source to each hop is to parse the packet trace file. However, you need to write different parsing code for different scenario. It is time-consuming.

2.      The second way is to write a module to record the sending time and receiving time. The delay time = receiving time – sending time. The following figure shows the protocol stack of an IEEE 802.11b (ad hoc mode) node. In this example, I will re-write the FIFO queue to record the packet information. When the packet is sent down to the lower layers, the send() function will be invoked. Just make sure that the current node is the sending node and then we can record the sending time in the sender trace file. When the packet is sent up for path lookup or to the destination application, the recv() function will be called. Therefore, we can record the packet information in the receiver trace file. After simulation, you can find one sender trace file and receiver trace files for each intermediate node or destination.

 

3.      The adopted application in this example is stg. This is one of default programs in NCTUns for performance evaluation. It can generate greedy TCP/UP, self-similar, uniform, constant, exponential type traffic. Also, stg can read the trace file and generate the corresponding packet at the specific time. More information can be found at the app usage. The application layer of stg packets store packet id and sending time information in it. When the stg packets go through the modified FIFO module, the packet id and some information will be recorded.

 

[Preparation]

Refer to http://csie.nqu.edu.tw/smallko/nctuns/sfifo.htm to add sFIFO_measure into NCTUns.

 

(sfifo_measure.h)

#ifndef __NCTUNS_sfifo_measure_h__

#define __NCTUNS_sfifo_measure_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_measure : public NslObject {

 

 private:

 

        struct ifqueue          if_snd; /* output interface queue */

        int    open1, open2;

        FILE  *ptr1, *ptr2;

 

 protected:

       int                   intrq(MBinder *);

 

 public:

 

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

        ~sfifo_measure();

 

        int                    init();

        int                    recv(ePacket_ *);

        int                    send(ePacket_ *);

};

 

 

#endif /* __NCTUNS_sfifo_measure_h__ */

 

(sfifo_measure.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_measure/sfifo_measure.h>

#include <exportStr.h>

#include <mbinder.h>

 

#include <netinet/in.h>

#include <netinet/udp.h>

#include <packet.h>

#include <maptable.h>

#include <string.h>

 

MODULE_GENERATOR(sfifo_measure);

 

sfifo_measure::sfifo_measure(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);

 

        if_snd.ifq_len = 0;

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

 

        open1=0;

        open2=0;

}

 

sfifo_measure::~sfifo_measure() {

   if(open1!=0)

     fclose(ptr1);

   if(open2!=0)

     fclose(ptr2);

}

 

 

int sfifo_measure::init() {

 

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

 

        /* set upcall */

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

  sendtarget_->set_upcall(this, upcall);

  return(1);

}

 

int sfifo_measure::send(ePacket_ *pkt) {

       char buf_s[100];

       double current_time, send_time;

       Packet *p;

       int i, pid;

       struct ip *iph;

       const char *sep="+";

       char *brkt, *str, tok[4][50], *temp;

   

       current_time=GetCurrentTime() * TICK / 1000000000.0;

       p = (Packet *)pkt->DataInfo_;

 

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

       temp=(char *)iph+sizeof(struct ip)+sizeof(struct udphdr);

     

       //only in the sender node, the packet information will be recorded.

       if(iph!=NULL && get_nid() == mtbl_iptonid(iph->ip_src)) {

         if(open1==0){

           sprintf(buf_s,"/tmp/mysd_%d", get_nid());

           open1=1;

           ptr1=fopen(buf_s,"w+");

         }

 

         for(i=0;i<=30;i++)

           buf_s[i]=temp[i];

 

         i = 0;

         for(str=strtok_r(buf_s, sep,&brkt); str; str=strtok_r(NULL, sep, &brkt))

         {

           strcpy(tok[i], str);

           i++;

         }

          

         pid = (int)atoi(tok[0]);

         send_time = (double)atof(tok[1]);

         if(pid!=-1){

           sprintf(buf_s, "%d\t%f\n", pid, send_time);

           fwrite(buf_s, strlen(buf_s), 1, ptr1);

         }

       }    

 

 

        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() ) {

                /* 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_measure::recv(ePacket_ *pkt) {

       char buf_r[100];

       double current_time, send_time;

       Packet *p;

       int i, pid;

       struct ip *iph;

       const char *sep="+";

       char *brkt, *str, tok[4][50], *temp;

   

       current_time=GetCurrentTime() * TICK / 1000000000.0;

       p = (Packet *)pkt->DataInfo_;

 

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

       temp=(char *)iph+sizeof(struct ip)+sizeof(struct udphdr);

 

       if(iph!=NULL) {

         if(open2==0){

           sprintf(buf_r,"/tmp/myrd_%d", get_nid());

           open2=1;

           ptr2=fopen(buf_r,"w+");

         }

 

         for(i=0;i<=30;i++)

          buf_r[i]=temp[i];

 

         i = 0;

         for(str=strtok_r(buf_r, sep,&brkt); str; str=strtok_r(NULL, sep, &brkt))

         {

           strcpy(tok[i], str);

           i++;

         }

          

         pid = (int)atoi(tok[0]);

         send_time = (double)atof(tok[1]);

         if(pid!=-1){

           sprintf(buf_r, "%d\t%f\t%f\t%f\t%d\n", pid, send_time, current_time, current_time-send_time, p->pkt_getlen());

           fwrite(buf_r, strlen(buf_r), 1, ptr2);

         }

       }

 

 

        /* Just by pass incoming packet */

        assert(pkt&&pkt->DataInfo_);

        return(NslObject::recv(pkt));

}

 

 

int sfifo_measure::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_DEQUEUE(&if_snd, pkt);

 

        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);

}

 

[Simulation]

1.      Create a topology. (Node 1 is the sender, node 2 is the intermediate node, and the node 3 is the receiver.)

 

2.      Click “E” to edit property. (Assume the project name is test.)

 

3.      Click “R” but don’t click Simulation/Run now. We need to modify the test.tcl. Because we don’t add sFIFO_measure into GUI.

 

 

 

 

 

4.      After editing, click the Simulation/Run to start simulation.

 

5.      After simulation, you can find /tmp/mysd_1, /tmp/myrd_2, and /tmp/myrd_3.

(part of mysd_1) The first column is packet id and the second is the sending time.

 

(part of myrd_2) The first column is packet id, the second is sending time, the third the receiving time, the 4th is the delay time, the 5th is the packet size.

 

(part of myrd_3) The first column is packet id, the second is sending time, the third the receiving time, the 4th is the delay time, the 5th is the packet size.

 

6.      Plot the delay graph.

(use awk to direct get the first column and the fourth column data.)

 

(use gnuplot to draw the figure).

 

p.s. You can also find the loss rate for each hop transmission. Just compare the trace files and you will know how many packets are lost. You also can calculate the throughput for each hop. Try it.

 

Dr. Chih-Heng Ke (http://csie.nqu.edu.tw/smallko), smallko@gmail.com

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