bellmanford.pc

无线网络仿真工具Glomosim2.03

    int broadcastRTSize;
    clocktype delay = 0;

    RTIndex = 0;

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

    /* Broadcast the triggered updates. */
    while (RTIndex < node->numNodes)
    {
        memset((void*)broadcastRouteTablePtr, 0,
              (ROUTING_BELLMANFORD_NUM_OF_BROADCAST_RT_ENTRY * 
               ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE));

        currentBroadcastRTIndex = 0;
        broadcastRTSize = 0;

        /* 
         * Break routing table into smaller chunks and only the
         * the routes that have changed.
         */
        while (((broadcastRTSize + 
                ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE) <= 
                ROUTING_BELLMANFORD_MAX_BROADCAST_RT_SIZE) && 
                (RTIndex < node->numNodes))
        {
            if (routeTablePtr->row[RTIndex].routeChanged == TRUE)
            {
                broadcastRouteTablePtr[currentBroadcastRTIndex].destAddr
                    = RTIndex;

                broadcastRouteTablePtr[currentBroadcastRTIndex].nextHop 
                    = routeTablePtr->row[RTIndex].nextHop;

                broadcastRouteTablePtr[currentBroadcastRTIndex].dist
                    = routeTablePtr->row[RTIndex].dist;

                broadcastRTSize 
                    += ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE;

                routeTablePtr->row[RTIndex].routeChanged 
                    = FALSE;

                currentBroadcastRTIndex++;
            }

            RTIndex++;
        }

        if (broadcastRTSize > 0)
        {
            /* Build routing table packet. */
            header = RoutingBellmanfordBuildHeader(node->nodeAddr,
                                                  ANY_DEST, 
                                                  broadcastRTSize);

            /* Send to neighbors. */
            AppUdpSendNewHeaderDataWithPriority(node,
                                               APP_ROUTING_BELLMANFORD,
                                               ANY_DEST,
                                               (char *)&header,
                                               sizeof(RoutingBellmanfordHeader),
                                               (char *)broadcastRouteTablePtr,
                                               broadcastRTSize,
                                               CONTROL,
                                               delay);
        }
    }

    routeTablePtr->triggeredUpdate = FALSE;

    pc_free(broadcastRouteTablePtr);
}


/*
 * NAME:        RoutingBellmanfordBroadcastRoutingTable.
 *
 * PURPOSE:     Broadcasts the routing table of the node to all its neighbors.
 *
 * PARAMETERS:  node, node that is broadcasting the routing table.
 *              routeTablePtr, routing table for all nodes.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

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

    int RTIndex;

    int currentBroadcastRTIndex;
    int broadcastRTSize;
    clocktype randomTime;
    clocktype delay = 0;
    clocktype tmpNum;
    char clockStr[GLOMO_MAX_STRING_LENGTH];
    Message *newMsg;
    GlomoRoutingBellmanford *bellmanford;

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

    RTIndex = 0;

    ctoa(simclock(), clockStr);

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

    /* Broadcast routing table to neighbors. */
    while (RTIndex < node->numNodes)
    {
        memset((void *)broadcastRouteTablePtr, 0,
              (ROUTING_BELLMANFORD_NUM_OF_BROADCAST_RT_ENTRY * 
               ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE));

        currentBroadcastRTIndex = 0;
        broadcastRTSize = 0;

        /* Break routing table into smaller chunks. */
        while (((broadcastRTSize + 
                ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE) <= 
                ROUTING_BELLMANFORD_MAX_BROADCAST_RT_SIZE) && 
                (RTIndex < node->numNodes))
        {   
            broadcastRouteTablePtr[currentBroadcastRTIndex].destAddr
                = RTIndex;

            broadcastRouteTablePtr[currentBroadcastRTIndex].nextHop 
                = routeTablePtr->row[RTIndex].nextHop;

            broadcastRouteTablePtr[currentBroadcastRTIndex].dist
                = routeTablePtr->row[RTIndex].dist;

            broadcastRTSize
                += ROUTING_BELLMANFORD_BROADCAST_RT_ENTRY_SIZE;

            RTIndex++;

            currentBroadcastRTIndex++;
        }

        if (broadcastRTSize > 0)
        {
            /* Build routing table packet. */
            header = RoutingBellmanfordBuildHeader(node->nodeAddr,
                                                   ANY_DEST, 
                                                   broadcastRTSize);


            /* Send each chunk separately. */
            AppUdpSendNewHeaderDataWithPriority(node,
                                               APP_ROUTING_BELLMANFORD,
                                               ANY_DEST,
                                               (char *)&header,
                                               sizeof(RoutingBellmanfordHeader),
                                               (char *)broadcastRouteTablePtr,
                                               broadcastRTSize,
                                               CONTROL,
                                               delay);
        }
    }

    /* 
     * Broadcast after an interval.  Use random time to avoid
     * synchronization.
     */
    randomTime = (clocktype) (pc_nrand(node->seed) % 
                              ROUTING_BELLMANFORD_RANDOM_TIMER);

    tmpNum = (clocktype) (ROUTING_BELLMANFORD_BC_TIMER);

    routeTablePtr->nextRTBroadcast = simclock() + tmpNum + randomTime;

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

    GLOMO_MsgSend(node, newMsg, ROUTING_BELLMANFORD_BC_TIMER + randomTime);

    bellmanford->stats.numRTBroadcast++;

    pc_free(broadcastRouteTablePtr);
}


/*
 * NAME:        RoutingBellmanfordHandleRoutingTableTO.
 *
 * PURPOSE:     Takes care of routing table timeouts.
 *
 * PARAMETERS:  node, node that is handle the routing table
 *                       timeouts.
 *              routeTablePtr, routing table for all nodes.
 *
 * RETURN: None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordHandleRoutingTableTO(GlomoNode *node,
                                RoutingBellmanfordRoutingTable *routeTablePtr)
{
    int i;
    BOOL changed = FALSE;
    int randomTime;
    clocktype delay;
    Message *newMsg;

    /* Check each routing table entry to see if there is a timeout. */
    for (i = 0; i < node->numNodes; i++) 
    {
        /* Check if old routing information to detect links going down. */
        if (((simclock() - routeTablePtr->row[i].lastModified) >= 
            ROUTING_BELLMANFORD_TIMEOUT) && (i != node->nodeAddr))
        {
            /* 
             * If INFINITY to begin with, no timeout since route
             * is unreachable already.  If not INFINITY, then
             * route is now unreachable.
             */
            if (routeTablePtr->row[i].dist != ROUTING_BELLMANFORD_INFINITY)
            {
                routeTablePtr->row[i].dist = ROUTING_BELLMANFORD_INFINITY;
                routeTablePtr->row[i].lastModified = simclock();
                routeTablePtr->row[i].routeChanged = TRUE;
                changed = TRUE;
            }
        }
    }

    /* Trigger routing table updates if routing information changed. */
    if (changed == TRUE)
    {
        RoutingBellmanfordHandleRouteChange(node, routeTablePtr);
    }

    /* Check timeout again after an interval */
    randomTime = (pc_nrand(node->seed) % ROUTING_BELLMANFORD_RANDOM_TIMER);

    delay = (clocktype) (randomTime + ROUTING_BELLMANFORD_TIMEOUT);

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

    GLOMO_MsgSend(node, newMsg, delay);
}


/*
 * NAME:        RoutingBellmanfordUpdateRoutingTable.
 *
 * PURPOSE:     Updates the routing table of the node using the neighor's 
 *              routing table broadcast.
 *
 * PARAMETERS:  node, node that is going to update its routing table.
 *              neighborId, neighboring node that broadcasted the
 *                          routing table update.
 *              numOfRTEntries, number of routing table entries in
 *                              neighboring node's broadcasted
 *                              routing table update.
 *              routeTablePtr, routing table for all nodes.
 *              neighRTPtr, routing table entries from neighbor node.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordUpdateRoutingTable(GlomoNode *node, 
                    NODE_ADDR neighborAddr,
                    int numOfRTEntries, 
                    RoutingBellmanfordRoutingTable *routeTablePtr, 
                    RoutingBellmanfordBroadcastRoutingTableRow *neighRTPtr)
{
    int i;

    int destAddr;
    BOOL changed = FALSE;

    #ifdef DEBUG
        printf("\nBefore routing table update\n");
        RoutingBellmanfordPrintRoutingTable(node, routeTablePtr);
    #endif

    /* Update the routing table. */
    for (i = 0; i < numOfRTEntries; i++) 
    {
        destAddr = neighRTPtr[i].destAddr;

        if (neighRTPtr[i].nextHop == node->nodeAddr)
        {
            /* Split horizon with poisoned reverse. */
            neighRTPtr[i].dist = ROUTING_BELLMANFORD_INFINITY;
        }
        else
        {
            /* 
             * Update hop count since hop count was not incremented
             * at the neighbor.
             */
            if (neighRTPtr[i].dist < ROUTING_BELLMANFORD_INFINITY)
                neighRTPtr[i].dist++;
        }

        /* 
         * Update table if found better metric or if the neighbor
         * is the next hop.
         */ 
        if ((neighRTPtr[i].dist < routeTablePtr->row[destAddr].dist) || 
            (neighborAddr == routeTablePtr->row[destAddr].nextHop))
        {
            routeTablePtr->row[destAddr].lastModified = simclock();

            if (neighRTPtr[i].dist != routeTablePtr->row[destAddr].dist)
            {
                routeTablePtr->row[destAddr].routeChanged = TRUE;

                changed = TRUE;
            }

            routeTablePtr->row[destAddr].dist = neighRTPtr[i].dist;
            routeTablePtr->row[destAddr].nextHop = neighborAddr;

            NetworkUpdateForwardingTable(node, destAddr, 
                                         DEFAULT_INTERFACE, neighborAddr);
        }
    }

    #ifdef DEBUG
        printf("After routing table update\n");
        RoutingBellmanfordPrintRoutingTable(node, routeTablePtr);
    #endif

    /* Trigger routing table updates if routing information changed. */
    if (changed == TRUE)
    {
        RoutingBellmanfordHandleRouteChange(node, routeTablePtr);
    }
}


/*
 * NAME:        RoutingBellmanfordHandleRouteChange.
 *
 * PURPOSE:     Trigger routing tabe updates to neighbors when route
 *              is changed.
 *
 * PARAMETERS:  node, node that is handling the route change.
 *              routeTablePtr, routing table for all nodes.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordHandleRouteChange(GlomoNode *node,
                                RoutingBellmanfordRoutingTable *routeTablePtr)
{
    clocktype randomTime;
    clocktype timeDiff;
    Message *newMsg;

    timeDiff = routeTablePtr->nextRTBroadcast - simclock();

    /* 
     * Don't broadcast route change to neighbor if routing table
     * is going to be broadcasted soon anyway.
     */
    if (timeDiff >= ROUTING_BELLMANFORD_TRIGGER_UPDATE_TIMER)
    {
        if (routeTablePtr->triggeredUpdate == FALSE)
        {
            randomTime = (clocktype) (pc_nrand(node->seed) % 
                                      ROUTING_BELLMANFORD_TRIGGER_UPDATE_TIMER);

            /* Trigger update at random time to avoid synchronization. */
            newMsg = GLOMO_MsgAlloc(node,
                                    GLOMO_APP_LAYER,
                                    APP_ROUTING_BELLMANFORD,
                                    MSG_APP_TriggerUpdateAlarm);

            GLOMO_MsgSend(node, newMsg, randomTime);

            routeTablePtr->triggeredUpdate = TRUE;
        }
    }
}


/*
 * NAME:        RoutingBellmanfordInitRoutingStats.
 *
 * PURPOSE:     Initialize all network layer statistics.
 *
 * PARAMETERS:  node, node keeping track of the statistics.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordInitRoutingStats(GlomoNode *node)
{
    GlomoRoutingBellmanford *bellmanford;

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

    /* Total number of routing table broadcasts. */
    bellmanford->stats.numRTBroadcast = 0;   

    /* Total number of triggered routing table updates. */
    bellmanford->stats.numTriggerUpdate = 0;

    /* Total number of routing table updates. */
    bellmanford->stats.numRTUpdate = 0;      

    /* Total number of packets received from UDP. */
    bellmanford->stats.numFromUdp = 0;
} 


/*
 * NAME:        RoutingBellmanfordPrintRoutingStats.
 *
 * PURPOSE:     Print networks layer statistics.
 *
 * PARAMETERS:  node, statistics of the node.
 *
 * RETURN:      None.
 *
 * ASSUMPTION:  None.
 */

void RoutingBellmanfordPrintRoutingStats(GlomoNode *node)
{
    float averageHopCount;
    char buf[GLOMO_MAX_STRING_LENGTH];
    GlomoRoutingBellmanford *bellmanford;

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

    sprintf(buf, "Number of routing table broadcasts = %d", 
            bellmanford->stats.numRTBroadcast);
    GLOMO_PrintStat(node, "RoutingBellmanford", buf);

    sprintf(buf, "Number of routing table trigger updates = %d", 
            bellmanford->stats.numTriggerUpdate);
    GLOMO_PrintStat(node, "RoutingBellmanford", buf);

    sprintf(buf, "Number of routing table updates = %d", 
            bellmanford->stats.numRTUpdate);
    GLOMO_PrintStat(node, "RoutingBellmanford", buf);

    sprintf(buf, "Number of routing packets received from UDP = %d",
            bellmanford->stats.numFromUdp); 
    GLOMO_PrintStat(node, "RoutingBellmanford", buf);
}