dsr.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.
/*
 * Name: dsr.pc
 *
 * Written By S.J. Lee
 *
 */
 
/*
 NOTE: - Followed the specification of DSR Internet Draft (03)
       - Must set promiscuous mode to YES in "config.in" in order to run DSR
       - Assumes the MAC protocol sends a signal to the routing protocol
         when it detects link breaks. MAC protocols such as IEEE 802.11
         and MACAW has this functionality. In IEEE 802.11, when no CTS
         is received after RTS, and no ACK is received after retransmissions
         of unicasted packet, it sends the signal to the routing protocol
       - If users want to use MAC protocols other than IEEE 802.11, they
         must implement schemes to detect link breaks. A way to do this is,
         for example, using passive acknowledgments, as specified in DSR
         documents
       - Destination sends Route Replies to ALL Route Requests it receives, as
         was done in CMU's NS2 implementation
       - Most, but not all, optimization features of DSR are implemented.
         Implemented optimizations are:
          + Promiscuous learning of source routes
          + Discovering shorter routes
          + Rate limiting the route discovery process
          + All nodes process all of the Route Error messages the receive 
            (when the node is the destination of the packet, is the forwarder,
             or overhears the packet promiscuously) 
          + Nonpropagating Route Requests
          + Replying from cache
          + Gratuitous Route Replies
          + Salvaging (for data and Route Errors)
          + Tapping

         Optimizations not implemented are:
          + Preventing Route Reply Storms
          + Path state and flow state mechanisms
          + Piggybacking on Route Discoveries
          + Gratuitous Route Errors
*/


#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 "dsr.h"
#include "ip.h"
#include "nwip.h"
#include "nwcommon.h"
#include "application.h"
#include "transport.h"
#include "java_gui.h"


/*
 * RoutingDsrInit
 *
 * Initialization function for DSR protocol 
 */
void RoutingDsrInit(
    GlomoNode *node,
    GlomoRoutingDsr **dsrPtr,
    const GlomoNodeInput *nodeInput)
{
    GlomoRoutingDsr *dsr = 
        (GlomoRoutingDsr *)checked_pc_malloc (sizeof(GlomoRoutingDsr));

    (*dsrPtr) = dsr;

    if (dsr == NULL)
    {
        fprintf(stderr, "DSR: Cannot alloc memory for DSR struct!\n");
        assert (FALSE);
    }

    RoutingDsrInitStats(node);
    RoutingDsrInitRequestSeen(&dsr->requestSeenTable);
    RoutingDsrInitRouteCache(&dsr->routeCacheTable);
    RoutingDsrInitSeq(node);
    RoutingDsrInitRequestTable(&dsr->requestTable);
    RoutingDsrInitBuffer(&dsr->buffer);

    NetworkIpSetPacketDropNotificationFunction(
        node, &RoutingDsrPacketDropNotificationHandler);

    NetworkIpSetRouterFunction(node, &RoutingDsrRouterFunction);

    /* Need to do this to run promiscuous mode */
    NetworkIpSetPromiscuousMessagePeekFunction(node, &RoutingDsrPeekFunction);

} /* RoutingDsrInit */

/* 
 * RoutingDsrFinalize
 *
 * Called at the end of simulation to collect the results 
 */
void RoutingDsrFinalize(GlomoNode *node)
{
    GlomoNetworkIp *ipLayer = (GlomoNetworkIp *)node->networkData.networkVar;
    GlomoRoutingDsr *dsr = (GlomoRoutingDsr *)ipLayer->routingProtocol;
    FILE *statOut;
    float avgHopCnt;
    char buf[GLOMO_MAX_STRING_LENGTH];

    sprintf(buf, "Number of Requests Txed = %d", dsr->stats.numRequestSent);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of Replies Txed = %d", dsr->stats.numReplySent);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of Errors Txed = %d", dsr->stats.numErrorSent);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of CTRL Packets Txed = %d",
                 dsr->stats.numRequestSent + dsr->stats.numReplySent + 
                 dsr->stats.numErrorSent);
    GLOMO_PrintStat(node, "RoutingDsr", buf);

    sprintf(buf, "Number of Routes Selected = %d", dsr->stats.numRoutes);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of Hop Counts = %d", dsr->stats.numHops);
    GLOMO_PrintStat(node, "RoutingDsr", buf);

    sprintf(buf, "Number of Data Txed = %d", dsr->stats.numDataTxed);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of Data Originated = %d", dsr->stats.numDataSent);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    sprintf(buf, "Number of Data Received = %d", dsr->stats.numDataReceived);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    
    sprintf(buf, "Number of Link Breaks = %d", dsr->stats.numLinkBreaks);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    
    sprintf(buf, "Number of Salvaged Packets = %d", 
        dsr->stats.numSalvagedPackets);
    GLOMO_PrintStat(node, "RoutingDsr", buf);
    
    sprintf(buf, "Number of Dropped Packets = %d", 
        dsr->stats.numDroppedPackets);
    GLOMO_PrintStat(node, "RoutingDsr", buf);

} /* Network Dsr Finalize */

/*
 * RoutingDsrHandleRequest
 * 
 * Processing procedure when Route Request is received
 */
void RoutingDsrHandleRequest(GlomoNode *node, Message *msg, int ttl)
{
    GlomoNetworkIp* ipLayer = (GlomoNetworkIp *) node->networkData.networkVar;
    GlomoRoutingDsr* dsr = (GlomoRoutingDsr *) ipLayer->routingProtocol;
    DSR_RouteRequest *rreq = (DSR_RouteRequest *)GLOMO_MsgReturnPacket(msg);
    IpHeaderType *ipHdr = (IpHeaderType *)GLOMO_MsgReturnPacket(msg);

    /* If destination of the route (dest sends Reply to every requests) */
    if (rreq->targetAddr == node->nodeAddr)
    {
        RoutingDsrInitiateRREP(node, msg);
    }

    /* Not a destination; if the request is not seen before */
    else if (!RoutingDsrLookupRequestSeen(rreq->srcAddr, 
                                          rreq->seqNumber, 
                                          &dsr->requestSeenTable))
    {
        /* Insert request info into request seen table */
        RoutingDsrInsertRequestSeen(node, 
                                    rreq->srcAddr, 
                                    rreq->seqNumber, 
                                    &dsr->requestSeenTable);

        /* Check if its address is in the path of the packet */
        if (!RoutingDsrCheckRequestPath(node, 
                                        rreq->path, 
                                        rreq->hopCount - 1))
        {
            /* If it has a route to destination, send a Route Reply */
            if (RoutingDsrCheckRouteExist(rreq->targetAddr, 
                                          &dsr->routeCacheTable))
            {
                RoutingDsrInitiateRREPbyIN(node, msg);
            } /* if check route exist */

            /* Does not have any route in cache; Relay the packet if ttl > 0 */
            else if (ttl > 0 && rreq->hopCount < DSR_MAX_SR_LEN)
            {
                RoutingDsrRelayRREQ(node, msg, ttl);
            } /* else if ttl > 0 */

            else
            {
                GLOMO_MsgFree(node, msg);
            }

        } /* if check request path */

        else
        {
            GLOMO_MsgFree(node, msg);
        }
    } /* else if lookup request seen */

    else
    {
        GLOMO_MsgFree(node, msg);
    }
} /* Handle Request */

/*
 * RoutingDsrHandleReply
 *
 * Processing procedure when Route Reply is received
 */
void RoutingDsrHandleReply(
    GlomoNode *node, Message *msg, NODE_ADDR destAddr)
{
    GlomoNetworkIp* ipLayer = (GlomoNetworkIp *) node->networkData.networkVar;
    GlomoRoutingDsr* dsr = (GlomoRoutingDsr *) ipLayer->routingProtocol;
    Message *newMsg;
    DSR_RouteReply *rrep = (DSR_RouteReply *)GLOMO_MsgReturnPacket(msg);
    NODE_ADDR newPath[DSR_MAX_SR_LEN];
    int segLeft;
    int i, j, k;

    segLeft = rrep->segLeft - 1;

    /* I'm the destination of the packet (source of the route) */
    if (rrep->targetAddr == node->nodeAddr && destAddr == node->nodeAddr)
    {
        /* A new (and first) route to the destination */
        if (!RoutingDsrCheckRouteExist(rrep->srcAddr, &dsr->routeCacheTable) &&
            !RoutingDsrCheckDataSeen(node, rrep->path, rrep->hopCount) &&
            rrep->srcAddr != ANY_DEST)
        {
            RoutingDsrInsertRouteCache(rrep->path[rrep->hopCount - 1],
                                       rrep->hopCount,
                                       rrep->path,
                                       &dsr->routeCacheTable);

            dsr->stats.numRoutes++;
            dsr->stats.numHops += rrep->hopCount;

            RoutingDsrDeleteRequestTable(rrep->srcAddr, &dsr->requestTable);

            // Remove packets expired waiting for route.
            
            RoutingDsrRemoveOldPacketsFromBuffer(&dsr->buffer); 
                            
            /* Send buffered data packets that waited for a route */
            while (RoutingDsrLookupBuffer(rrep->srcAddr, &dsr->buffer))
            {
                newMsg = RoutingDsrGetBufferedPacket(rrep->srcAddr, 
                                                     &dsr->buffer);

                RoutingDsrTransmitData(node, newMsg, rrep->srcAddr);

                RoutingDsrDeleteBuffer(rrep->srcAddr, &dsr->buffer);

            } /* while */

            /* Optimization: Adding routes to intermediate nodes */
            for (i = 0; i < rrep->hopCount - 1; i++)
            {
                for (j = 0; j <= i; j++)
                {
                    newPath[j] = rrep->path[j];
                }
                for (j = i + 1; j < DSR_MAX_SR_LEN; j++)
                {
                    newPath[j] = ANY_DEST;
                }

                /* Check if the route is new */
                if (!RoutingDsrCompareRoute(rrep->path[i],
                                            i + 1,
                                            newPath,
                                            &dsr->routeCacheTable) &&
                    !RoutingDsrCheckDataSeen(node, newPath, i + 1))
                {
                    RoutingDsrInsertRouteCache(rrep->path[i],
                                               i + 1, 
                                               newPath,
                                               &dsr->routeCacheTable);

                } /* if a new route */
            } /* for */
        } /* if check route exist */

        /* routes to the destination already exist */
        else
        {
            /* if the route is not the same as one in the cache */
            if (!RoutingDsrCompareRoute(rrep->path[rrep->hopCount - 1],
                                        rrep->hopCount,
                                        rrep->path,
                                        &dsr->routeCacheTable) &&
                !RoutingDsrCheckDataSeen(node, rrep->path, rrep->hopCount))
            {
                RoutingDsrInsertRouteCache(rrep->path[rrep->hopCount - 1],
                                           rrep->hopCount,
                                           rrep->path,
                                           &dsr->routeCacheTable);

            }

            /* Optimization: Adding routes to intermediate nodes */
            for (i = 0; i < rrep->hopCount - 1; i++)
            {
                for (j = 0; j <= i; j++)
                {
                    newPath[j] = rrep->path[j];
                }
                for (j = i + 1; j < DSR_MAX_SR_LEN; j++)
                {
                    newPath[j] = ANY_DEST;
                }

                /* Check if new route is the same as one in cache */
                if (!RoutingDsrCompareRoute(rrep->path[i],
                                            i + 1,
                                            newPath,
                                            &dsr->routeCacheTable) &&
                    !RoutingDsrCheckDataSeen(node, newPath, i + 1))
                {
                    /* Insert the route into cache */
                    RoutingDsrInsertRouteCache(rrep->path[i],
                                               i + 1, 
                                               newPath,
                                               &dsr->routeCacheTable);

                } /* if a new route */
            } /* for */
        } /* else */

        GLOMO_MsgFree(node, msg);

    } /* if dest */

    /* Node is the intended intermediate node; 
       cache the routes and relay the packet*/
    else if (destAddr == node->nodeAddr)
    {
        /* Insert the routes into cache */
        for (i = 0; i < rrep->hopCount; i++)
        {
            newPath[i] = rrep->path[segLeft + i];
        }
        for (i = rrep->hopCount; i < DSR_MAX_SR_LEN; i++)
        {
            newPath[i] = ANY_DEST;
        }

        /* Check if the route is new */
        if (!RoutingDsrCompareRoute(rrep->srcAddr,
                                    rrep->hopCount,
                                    newPath,
                                    &dsr->routeCacheTable) &&
            !RoutingDsrCheckDataSeen(node, newPath, rrep->hopCount))
        {
            RoutingDsrInsertRouteCache(
                rrep->srcAddr, rrep->hopCount, newPath, &dsr->routeCacheTable);

        } /* if compare route */

        /* Optimization: Adding routes to intermediate nodes */
        for (j = segLeft; 
             j < rrep->hopCount + segLeft - 1; 
             j++)
        {
            for (k = 0; k <= j - segLeft; k++)
            {
                newPath[k] = rrep->path[k + segLeft];
            }
            for (k = j + 1 - segLeft; k < DSR_MAX_SR_LEN; k++)
            {
                newPath[k] = ANY_DEST;
            }

            /* Check if the route is new */
            if (!RoutingDsrCompareRoute(rrep->path[j],
                                        j + 1 - segLeft,
                                        newPath,
                                        &dsr->routeCacheTable) &&
                !RoutingDsrCheckDataSeen(node, newPath, j + 1 - segLeft))
            {
                RoutingDsrInsertRouteCache(rrep->path[j],
                                           j + 1 - segLeft,
                                           newPath,
                                           &dsr->routeCacheTable);

            } /* if compare route */
        } /* for */

        RoutingDsrRelayRREP(node, msg); 

    } /* else if intended receiver */

    else
    {
        GLOMO_MsgFree(node, msg);
    }
} /* Handle Reply */

/*
 * RoutingDsrHandleError
 *
 * Processing procedure when Route Error is received
 */