bellmanford.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: bellmanford.pc,v 1.16 2001/02/15 03:17:26 mineo Exp $
 *
 * PURPOSE:         Simulate the Bellman-Ford routing protocol.
 *
 * NOTE:            This implementation has no notion of a "request" or
 *                  "response" as described in RIP.
 */

#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 "bellmanford.h"


#define noDEBUG

/*
 * NAME:        RoutingBellmanfordLayer.
 *
 * PURPOSE:     Handles all messages sent to bellmanford.
 *
 * PARAMETERS:  node, node receiving message.
 *              msg, message for node to interpret.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordLayer(GlomoNode *node,
                             Message *msg)
{
    GlomoRoutingBellmanford *bellmanford;
    char clockStr[GLOMO_MAX_STRING_LENGTH];
    ctoa(simclock(), clockStr);

    bellmanford = (GlomoRoutingBellmanford *)node->appData.routingVar;

    switch(msg->eventType) 
    {
        /* Received packet from network layer. */
        case MSG_APP_FromTransport:
        {
            RoutingBellmanfordHeader *header;
            char *payload;

            bellmanford->stats.numFromUdp++;
            
            header = (RoutingBellmanfordHeader *) msg->packet;

            GLOMO_MsgRemoveHeader(node, msg,
                                  sizeof(RoutingBellmanfordHeader));

            payload = msg->packet;

            RoutingBellmanfordHandleRTPacket(node, header, payload);

            GLOMO_MsgFree(node, msg);

            break;
        }

        /* Received alarm to broadcast routing table. */
        case MSG_APP_RTBroadcastAlarm:
        {
            /* Broadcast routing table to neighbors. */
            RoutingBellmanfordBroadcastRoutingTable(node,
                                                    &bellmanford->routeTable);

            GLOMO_MsgFree(node, msg);

            break;
        }

        /* 
         * Received alarm to check if any broadcast routing table 
         * entry timeouts. 
         */
        case MSG_APP_CheckTimeoutAlarm:
        {
            /* Handle routing table entry timeouts. */
            RoutingBellmanfordHandleRoutingTableTO(node, 
                                                   &bellmanford->routeTable);

            GLOMO_MsgFree(node, msg);

            break;
        }

        /* Received alarm to check for triggered updates. */
        case MSG_APP_TriggerUpdateAlarm:
        {
            bellmanford->stats.numTriggerUpdate++;

            /* Broadcast the trigger updates to neighbors. */
            RoutingBellmanfordBroadcastTriggerUpdate(node, 
                                                    &bellmanford->routeTable);

            GLOMO_MsgFree(node, msg);

            break;
        }   
        default:
            fprintf(stderr, "RoutingBellmanford: Unknown MSG_APP type %d!\n", 
                    msg->eventType);
            assert(FALSE);
    }
}



/*
 * NAME:        RoutingBellmanfordInit.
 *
 * PURPOSE:     Handling all initializations needed by bellmanford.
 *
 * PARAMETERS:  node, node doing the initialization.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordInit(GlomoNode *node)
{
    clocktype randomTime;
    Message *newMsg;

    GlomoRoutingBellmanford *bellmanford;

    bellmanford = (GlomoRoutingBellmanford *)
                  pc_malloc(sizeof(GlomoRoutingBellmanford));

    #ifdef DEBUG
        printf("Initializing Bellmanford...\n");
    #endif

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

    node->appData.routingVar = (void *)bellmanford;

    RoutingBellmanfordInitRoutingStats(node);

    /* Initialize routing table for every node. */
    RoutingBellmanfordInitRoutingTable(node,
                        &bellmanford->routeTable);

    /* Start broadcast and timeout timers. */
    /* Used to avoid synchronization of routing table broadcasts. */
    randomTime = (clocktype) (pc_nrand(node->seed) % 
                              ROUTING_BELLMANFORD_RANDOM_TIMER); 

    bellmanford->routeTable.nextRTBroadcast = simclock() + randomTime;
                                            
    newMsg = GLOMO_MsgAlloc(node,
                            GLOMO_APP_LAYER,
                            APP_ROUTING_BELLMANFORD,
                            MSG_APP_RTBroadcastAlarm);

    GLOMO_MsgSend(node, newMsg, randomTime);

    newMsg = GLOMO_MsgAlloc(node,
                            GLOMO_APP_LAYER,
                            APP_ROUTING_BELLMANFORD,
                            MSG_APP_CheckTimeoutAlarm);

    GLOMO_MsgSend(node, newMsg, randomTime + ROUTING_BELLMANFORD_TIMEOUT);
}


/*
 * NAME:        RoutingBellmanfordFinalize.
 *
 * PURPOSE:     Handling all finalization needed by bellmanford.
 *
 * PARAMETERS:  node, node doing the finalization.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordFinalize(GlomoNode *node)
{
    if (node->appData.routingStats == TRUE)
    {
        RoutingBellmanfordPrintRoutingStats(node);
    }
}



/*
 * NAME:        RoutingBellmanfordHandleRTPacket.
 *
 * PURPOSE:     Decide what to do when a routing table packet arrives.
 *
 * PARAMETERS:  node, node handling the data packet.
 *              header, header of routing table packet.
 *              payload, routing table packet.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordHandleRTPacket(GlomoNode *node, 
                                      RoutingBellmanfordHeader *header,
                                      char *payload)
{
    int numOfRTEntries;
    RoutingBellmanfordBroadcastRoutingTableRow *broadcastRouteTablePtr;
    GlomoRoutingBellmanford *bellmanford;

    bellmanford = (GlomoRoutingBellmanford *)node->appData.routingVar;

    broadcastRouteTablePtr = (RoutingBellmanfordBroadcastRoutingTableRow *) 
                    pc_malloc(ROUTING_BELLMANFORD_NUM_OF_BROADCAST_RT_ENTRY * 
                    sizeof(RoutingBellmanfordBroadcastRoutingTableRow));
    
    if (broadcastRouteTablePtr == NULL)
    {
        fprintf(stderr, "Bellmanford: No more memory\n");
        assert(FALSE);
    }
       
    memset((void *)broadcastRouteTablePtr,
          0,
          (ROUTING_BELLMANFORD_NUM_OF_BROADCAST_RT_ENTRY * 
          ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE));

    memcpy((void *)(broadcastRouteTablePtr), 
           (void *)payload, 
           header->payloadSize);

    /* 
     * Find out the number of routing table entries
     * that packet contains.
     */
    numOfRTEntries = header->payloadSize / 
                     ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE;

    /* 
     * Update the nodes's routing table from neighbor's
     * routing table broadcast.
     */
    RoutingBellmanfordUpdateRoutingTable(node,
                                         header->sourceAddr,
                                         numOfRTEntries,
                                         &bellmanford->routeTable, 
                                         broadcastRouteTablePtr);

    bellmanford->stats.numRTUpdate++;

    pc_free(broadcastRouteTablePtr);
}



/*
 * NAME:        RoutingBellmanfordInitRoutingTable.
 *
 * PURPOSE:     Initialize the routing table of a node.
 *
 * PARAMETERS:  node, node which routing table is initialized.
 *              routeTablePtr, routing table of this node.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordInitRoutingTable(GlomoNode *node, 
                                RoutingBellmanfordRoutingTable *routeTablePtr)
{
    int i;
    GlomoRoutingBellmanford *bellmanford;

    bellmanford = (GlomoRoutingBellmanford *)node->appData.routingVar;

    /* Empty IP forwarding table. */
    NetworkEmptyForwardingTable(node);

    /* Zero out routing table. */
    memset((void*)routeTablePtr, 0, sizeof(RoutingBellmanfordRoutingTable));

    routeTablePtr->row = (RoutingBellmanfordRoutingTableRow *) 
                         pc_malloc(node->numNodes * 
                         sizeof(RoutingBellmanfordRoutingTableRow));

    routeTablePtr->nextRTBroadcast = 0;
    routeTablePtr->triggeredUpdate = FALSE;

    /* Fill default values in routing table. */
    for (i = 0; i < node->numNodes; i++)
    {
        routeTablePtr->row[i].lastModified = simclock();
        routeTablePtr->row[i].routeChanged = FALSE;

        if (i != node->nodeAddr)
        {
            routeTablePtr->row[i].dist = ROUTING_BELLMANFORD_INFINITY;
            routeTablePtr->row[i].nextHop = NETWORK_UNREACHABLE;
        }
        else
        {
            routeTablePtr->row[i].dist = 0;
            routeTablePtr->row[i].nextHop = node->nodeAddr;
        }
    }
}


/*
 * NAME:        RoutingBellmanfordBuildHeader.
 *
 * PURPOSE:     Builds the routing layer header.
 *
 * PARAMETERS:  sourceAddr, source sending the packet.
 *              destAddr, destination of the packet to be sent.
 *              payloadSize, size of the payload.
 *
 * RETURN:      A routing header.
 *
 * ASSUMPTION:  None.
 */

RoutingBellmanfordHeader 
RoutingBellmanfordBuildHeader(NODE_ADDR sourceAddr,
                              NODE_ADDR destAddr,
                              int payloadSize)
{
    RoutingBellmanfordHeader header;

    header.sourceAddr = sourceAddr;
    header.destAddr = destAddr;
    header.payloadSize = payloadSize;

    return header;
}


/*
 * NAME:        RoutingBellmanfordPrintBroadcastRoutingTable.
 *
 * PURPOSE:     Print the routing table that was broadcasted.
 *              Used for debugging purposes only.
 *
 * PARAMETERS:  node, node that routing table belongs to.
 *              neighRTPtr, routing table broadcasted by neighbor.
 *              numOfRTEntries, number of routing table entreis in
 *                              neighbor routing table.
 *
 * RETRUN: None. 
 * 
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordPrintBroadcastRoutingTable(GlomoNode *node,
                    RoutingBellmanfordBroadcastRoutingTableRow *neighRTPtr,
                    int numOfRTEntries)
{
    int i;

    printf("Node %ld's broadcast routing table.\n", node->nodeAddr);

    for (i = 0; i < numOfRTEntries; i++)
    {
        printf("\tDest[%d]: NextHop:%d  Dist:%d\n", neighRTPtr[i].destAddr,
                neighRTPtr[i].nextHop, neighRTPtr[i].dist);
    }
}


/*
 * NAME:        RoutingBellmanfordPrintRoutingTable.
 *
 * PURPOSE:     Print the routing table entries of all nodes.  Used for
 *              debugging purposes only.
 *
 * PARAMETERS:  node, node that routing table belongs to.
 *              routeTablePtr, routing table to be printed.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordPrintRoutingTable(GlomoNode *node, 
                                RoutingBellmanfordRoutingTable *routeTablePtr)
{
    int i;

    char clockStr[GLOMO_MAX_STRING_LENGTH];
    ctoa(simclock(), clockStr);

    printf("Node %u's routing table at time %s.\n",
           node->nodeAddr, clockStr);

    for (i = 0; i < node->numNodes; i++)
    {
        printf("\tDest[%d]: NextHop:%d  Dist:%d\n", i, 
               routeTablePtr->row[i].nextHop, 
               routeTablePtr->row[i].dist);
    }
}


/*
 * NAME:        RoutingBellmanfordBroadcastTriggerUpdate.
 *
 * PURPOSE:     Broadcasts the routing table due to triggered updates.
 *
 * PARAMETERS:  node, node that is broadcasting the routing table.
 *              routeTablePtr, routing table for all nodes.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordBroadcastTriggerUpdate(GlomoNode *node,
                                RoutingBellmanfordRoutingTable *routeTablePtr)
{
    RoutingBellmanfordHeader header;
    RoutingBellmanfordBroadcastRoutingTableRow *broadcastRouteTablePtr;

    int RTIndex;

    int currentBroadcastRTIndex;