wrp.pc

无线网络仿真工具Glomosim2.03

/*
 * GloMoSim is COPYRIGHTED software.  Release 2.02 of GloMoSim is available 
 * at no cost to educational users only.
 *
 * Commercial use of this software requires a separate license.  No cost,
 * evaluation licenses are available for such purposes; please contact
 * [e-mail]
 *
 * By obtaining copies of this and any other files that comprise GloMoSim2.02,
 * you, the Licensee, agree to abide by the following conditions and
 * understandings with respect to the copyrighted software:
 *
 * 1.Permission to use, copy, and modify this software and its documentation
 *   for education and non-commercial research purposes only is hereby granted
 *   to Licensee, provided that the copyright notice, the original author's
 *   names and unit identification, and this permission notice appear on all
 *   such copies, and that no charge be made for such copies. Any entity
 *   desiring permission to use this software for any commercial or
 *   non-educational research purposes should contact: 
 *
 *   Professor Rajive Bagrodia 
 *   University of California, Los Angeles 
 *   Department of Computer Science 
 *   Box 951596 
 *   3532 Boelter Hall 
 *   Los Angeles, CA 90095-1596 
 *   [e-mail]
 *
 * 2.NO REPRESENTATIONS ARE MADE ABOUT THE SUITABILITY OF THE SOFTWARE FOR ANY
 *   PURPOSE. IT IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
 *
 * 3.Neither the software developers, the Parallel Computing Lab, UCLA, or any
 *   affiliate of the UC system shall be liable for any damages suffered by
 *   Licensee from the use of this software.
 */

// Use the latest version of Parsec if this line causes a compiler error.
/*
 * $Id: wrp.pc,v 1.15 1999/10/14 07:32:30 jmartin Exp $
 *
 * PURPOSE:         Simulate the WRP routing protocol.
 *
 * NOTES:           This implementation is based upon the pseudocode in:
 *                       S. Murthy and J.J. Garcia-Luna-Aceves, 
 *                       "An Efficient Routing Protocol for Wireless
 *                       Networks", ACM Mobile Networks and Applications 
 *                       Journal, Special issue on Routing in Mobile
 *                       Communication Networks, 1996.
 *
 *                  This pseudocode has been included below, with remarks
 *                  that indicate where and why deviations were made.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>

#include "api.h"
#include "structmsg.h"
#include "fileio.h"
#include "message.h"
#include "network.h"
#include "nwcommon.h"
#include "app_util.h"
#include "wrp.h"

/***/
#define WRP_HELO_TIME   1*SECOND 
#define WRP_RETX_TIME   1*SECOND
#define WRP_XMIT_TIME   1*SECOND
#define WRP_MAX_HELLO   6
#define WRP_MAX_RETX    4

/*
#define DEBUGOUTPUT
/*
#define DEBUG
*/

#define SHOWTABLES

static void WrpInitStats(GlomoNode *node);

static int packPayload(GlomoNode *node);
static void unpackPayload(GlomoNode *node);
static int NewNeighbor(GlomoNode *node, int k);
static int MinEntry(GlomoNode *node, NODE_ADDR dest);
static void setTimer(GlomoNode *node, int type, int k, clocktype delay);

static void Init1(GlomoNode *node);
static void Init2(GlomoNode *node,NODE_ADDR j, NODE_ADDR x);
static void Messge(GlomoNode *node, NODE_ADDR k, int cost);
static void DT(GlomoNode *node, const WrpTuple D, int k);
static void Update(GlomoNode *node, const WrpTuple V[], int Vct, int k);
static void ACK(GlomoNode *node, const WrpTuple V[], int Vct, int k);
static void RT_Update(GlomoNode *node, int j);
static void Connectivity(GlomoNode *node, int k);
static void addTuple(GlomoNode *node, WrpTuple W, int *response);
static void broadcastUpdateMsg(GlomoNode *node, NODE_ADDR dest,
                               clocktype delay);
static void Clean_RList(GlomoNode *node, int seqno);
static void Delete_RList(GlomoNode *node, int seqno,int k);
static void Create_RList(GlomoNode *node, int valid);
static void printDTable(GlomoNode *node);
static void printRTable(GlomoNode *node);
static void printLTable(GlomoNode *node);

void RoutingWrpInit(GlomoNode *node, const GlomoNodeInput *nodeInput)
{
    clocktype delay;
    int count, count2;
    GlomoRoutingWrp *wrp;
    WrpMrlTuple *head,*temp;
    long retVal;
    char buf[GLOMO_MAX_STRING_LENGTH];

#ifdef DEBUG
    printf("#%u: RoutingWrpInit\n",node->nodeAddr);
#endif
    wrp = (GlomoRoutingWrp *) pc_malloc(sizeof(GlomoRoutingWrp));
    assert(wrp);
    node->appData.routingVar = (void *) wrp;

    if (node->appData.routingStats == TRUE)
    {
        WrpInitStats(node);
    }

    wrp->DTable = pc_malloc(sizeof(DistTable)*node->numNodes);
    wrp->RTable = pc_malloc(sizeof(RouteTable)*node->numNodes);
    wrp->LTable = pc_malloc(sizeof(LCTable)*node->numNodes);

    wrp->N = pc_malloc(sizeof(int)*node->numNodes);
    wrp->Ni = pc_malloc(sizeof(int)*node->numNodes);

    wrp->LISTmax = MIN( (node->numNodes*2),
        ((MAX_NW_BROADCAST_RT_SIZE-sizeof(int)*node->numNodes
          -sizeof(WrpPacketHeader))/sizeof(WrpTuple)) );
    wrp->LISTmax = wrp->LISTmax - 1;
#ifdef DEBUG
    printf("LISTmax = %d\n",wrp->LISTmax);
#endif
    wrp->LIST = pc_malloc(sizeof(WrpTuple)*wrp->LISTmax);
    wrp->LISTct = 0;    
    wrp->V = pc_malloc(sizeof(WrpTuple)*wrp->LISTmax);
    wrp->Vct = 0;
    wrp->responseList = pc_malloc(sizeof(int)*node->numNodes);
    wrp->wpkt = pc_malloc(sizeof(WrpPacket));

    wrp->MRL = pc_malloc(sizeof(WrpMrlEntry)*WRP_MAX_SEQ_NUM);

    if ((!wrp->DTable) || (!wrp->RTable) || (!wrp->LTable) || 
        (!wrp->N) || (!wrp->Ni) || (!wrp->LIST) || (!wrp->V) ||
        (!wrp->responseList) || (!wrp->wpkt) || (!wrp->MRL)) {
        printf("Error allocating memory for node #%u\n",node->nodeAddr);
        assert(FALSE);
    }
    memset(wrp->DTable, 0, sizeof(DistTable)*node->numNodes);
    for (count=0; count < node->numNodes; count++) {
        wrp->DTable[count].dat = pc_malloc(sizeof(DistEntry)*node->numNodes);
        if (!wrp->DTable[count].dat) {
            printf("Not enough memory for node #%u\n",node->nodeAddr);
            assert(FALSE);
        }
        memset(wrp->DTable[count].dat, 0, sizeof(DistEntry)*node->numNodes);
    }
/*
    for (count=0; count < WRP_MAX_SEQ_NUM; count++) {
        wrp->MRL[count].bitmap = pc_malloc(sizeof(NODE_ADDR)*node->numNodes);
        wrp->MRL[count].dat = pc_malloc(sizeof(WrpTuple)*wrp->LISTmax);
        if ((!wrp->MRL[count].bitmap) || (!wrp->MRL[count].dat)) {
            printf("Not enough memory for node #%u\n",node->nodeAddr);
            assert(FALSE);
        }
        memset(wrp->MRL[count].bitmap, 0, sizeof(NODE_ADDR)*node->numNodes);
        memset(wrp->MRL[count].dat, 0, sizeof(WrpTuple)*node->numNodes);
    }
*/
    memset(wrp->RTable, 0, sizeof(RouteTable)*node->numNodes);
    memset(wrp->LTable, 0, sizeof(LCTable)*node->numNodes);

    memset(wrp->N, 0, sizeof(int)*node->numNodes);
    memset(wrp->Ni, 0, sizeof(int)*node->numNodes);

    memset(wrp->LIST, 0, sizeof(WrpTuple)*node->numNodes);
    memset(wrp->responseList, 0, sizeof(int)*node->numNodes);
    memset(wrp->wpkt, 0, sizeof(WrpPacket));

    for (count=0; count < WRP_MAX_SEQ_NUM; count++)
    {
        wrp->MRL[count].MRLsize = 0;
    }

/* 6/26/99 */
    for (count=0; count < node->numNodes; count++)
    {
        wrp->RTable[count].dist = WRP_INFINITY;
        wrp->RTable[count].pred = -1;
        wrp->RTable[count].succ = -1;
    }
    for (count = 0; count < node->numNodes; count++)
    {
        wrp->DTable[count].dest = count;
        for (count2 = 0; count2 < node->numNodes; count2++)
        {
            wrp->DTable[count].dat[count2].via = count2;
            wrp->DTable[count].dat[count2].dist = WRP_INFINITY;
            wrp->DTable[count].dat[count2].pred = -1;
            wrp->DTable[count].dat[count2].valid = 0;
        }
    }
/***********/
    Init1(node);
/***/

}


void RoutingWrpLayer(GlomoNode *node, Message *msg)
{
    /*
     * Retrieve the pointer to the data portion which relates
     * to the NETWORK protocol.
     */
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;
    char clockStr[GLOMO_MAX_STRING_LENGTH];

    switch (msg->eventType) {
    case MSG_APP_FromTransport: {

        WrpPacket *packet;
        char clockStr[80];
        void *bptr;
        int size;

        packet = (WrpPacket *) GLOMO_MsgReturnPacket(msg);
/* OLD
        memcpy(wrp->wpkt,packet,sizeof(WrpPacket));
*/
/* 6/30/99 */
        size = MIN(GLOMO_MsgReturnPacketSize(msg), sizeof(WrpPacket));
        memcpy(wrp->wpkt, packet, size);
/***********/


        if (node->appData.routingStats == TRUE)
        {
            wrp->stats.numFromTransport++;
        }

        if (wrp->wpkt->hdr.msgType == WRP_RT)
        {
#ifdef DEBUG
            ctoa(simclock(),clockStr);
            printf("#%u: valid=%d, from=%d, seqNum=%d at %s\n",node->nodeAddr,
                   wrp->wpkt->hdr.valid, wrp->wpkt->hdr.k, 
                   wrp->wpkt->hdr.seqNum,clockStr);
#endif
            unpackPayload(node);
            Messge(node, wrp->wpkt->hdr.k, WRP_COST);
        }
        else
            assert(FALSE);

        GLOMO_MsgFree(node, msg);
        break;
    }
    case MSG_APP_TimerExpired: {
        WrpTimer *wt;
        clocktype delay;
        char buf[GLOMO_MAX_STRING_LENGTH];

        wt = (WrpTimer *) GLOMO_MsgReturnInfo(msg);

        switch (wt->timerType) {
        case WRP_XMIT_TIMER: {
#ifdef DEBUG
            ctoa(simclock(),buf);
            printf("#%u: WRP_XMIT_TIMER Expired at %s\n",node->nodeAddr, buf);
#endif
            delay = (clocktype) WRP_XMIT_TIME;
            delay *= pc_erand(node->seed);

            setTimer(node,WRP_XMIT_TIMER,0,(clocktype) delay);

            if (wrp->LISTct > 0)
                broadcastUpdateMsg(node,ANY_DEST,0);

            break;
        }
        case WRP_HELO_TIMER: {
            if (wrp->LTable[wt->k].HelloTimer <= simclock())
            {
#ifdef DEBUG
                printf("#%u: Expired HelloTimer to %d.\n",
                       node->nodeAddr,wt->k);
#endif
                Connectivity(node,wt->k);
            }
            else
            {
#ifdef DEBUG
                printf("#%u: Reset HelloTimer for %d\n",node->nodeAddr,wt->k);
                ctoa((wrp->LTable[wt->k].HelloTimer-simclock()),buf);
                printf("#%u:   %s ticks remaining.\n",node->nodeAddr,buf);
#endif
                setTimer(node,WRP_HELO_TIMER,wt->k,
                    (clocktype)(wrp->LTable[wt->k].HelloTimer-simclock()));
            }
            break;
        }
        case WRP_RETX_TIMER: {
            int count, count2, count3;
            WrpMrlTuple *head,*temp;
            WrpTuple W;
            int *response = pc_malloc(sizeof(int)*node->numNodes);
/* wsu addition */
            WrpMrlEntry tempMRL;

            assert(response);
 
#ifdef DEBUG
            printf("#%u: RetxTimer expired.\n",node->nodeAddr);
#endif

            setTimer(node,WRP_RETX_TIMER,0,(clocktype) WRP_RETX_TIME);

            /* decrement retx counters for outstanding MRL entries */
            for (count=0; count < WRP_MAX_SEQ_NUM; count++)
            {
                if ((wrp->SEQNO != count) &&(wrp->MRL[count].MRLsize > 0))
                {
                    wrp->MRL[count].retx_counter--;
                    if (wrp->MRL[count].retx_counter==0)
                    {
#ifdef DEBUG
                        printf("#%u: Need to retx %d\n",node->nodeAddr,count);
#endif
                        wrp->MRL[count].retx_counter = WRP_MRL_RETX_CONST;
                        for (count3=0; count3<node->numNodes; count3++)
                            response[count3] = wrp->MRL[count].bitmap[count3];
                        /* wsu addition */
                        tempMRL.dat = pc_malloc(sizeof(WrpTuple)*wrp->MRL[count].MRLsize);

                        for (count2=0;count2<wrp->MRL[count].MRLsize;count2++)
                           tempMRL.dat[count2] =  wrp->MRL[count].dat[count2];

                        tempMRL.MRLsize = wrp->MRL[count].MRLsize;

                        for (count2=0;count2<tempMRL.MRLsize;count2++)
                        {
                            W = tempMRL.dat[count2];
                            addTuple(node,W,response);
                        }

                        Clean_RList(node,count);
                        pc_free(tempMRL.dat);

                    }
                    
                }
            }
            pc_free(response);
            break;
        }
        case WRP_INIT_TIMER: {
            int *ZeroList;
            WrpTuple W;
            int *response = pc_malloc(sizeof(int)*node->numNodes);

            ZeroList = pc_malloc(sizeof(int)*node->numNodes);
            if ((!ZeroList)||(!response)) {
                printf("Not enough memory.\n");
                assert(FALSE);
            }
            memset(ZeroList, 0, sizeof(int)*node->numNodes);
            if (memcmp(ZeroList,wrp->Ni,sizeof(int)*node->numNodes) == 0) {
#ifdef DEBUG
                printf("NO NEIGHBORS YET.\n");
#endif
                W.u = 0;
                W.j = node->nodeAddr;
                W.RDkj = 0;
                W.rpkj = node->nodeAddr;
                memset(response, 0, sizeof(int)*node->numNodes);
                addTuple(node,W,response);
                setTimer(node,WRP_INIT_TIMER,0,(clocktype) WRP_HELO_TIME);


            }
            pc_free(ZeroList);
            pc_free(response);
            break;
        }
        default:
            assert(FALSE);
        }
        GLOMO_MsgFree(node, msg);
        break;
    }
    default:
        printf("Unknown Message Type\n");
        break;
    }

}


void WrpPrintRoutingStats(GlomoNode *node)
{
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;
    float averageHopCount;
    char buf[GLOMO_MAX_STRING_LENGTH];

    sprintf(buf, "Number of routing packets sent = %d",
            wrp->stats.numRTsent);
    GLOMO_PrintStat(node, "RoutingWrp", buf);

    sprintf(buf, "Number of routing packets recvd = %d",
            wrp->stats.numFromTransport);
    GLOMO_PrintStat(node, "RoutingWrp", buf);

}

void RoutingWrpFinalize(GlomoNode *node)
{
#ifdef DEBUGOUTPUT
   printDTable(node);
   printRTable(node);