aodv.pc

glomosim中的AODV实现,可参考RFC文档

/*
 * 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: aodv.pc
 *
 * Implemented by SJ Lee ([e-mail]) 
 */

/*
 NOTE: - Followed the specification of AODV Internet Draft
         (draft-ietf-manet-aodv-03.txt)
       - This implements only unicast functionality of AODV.
       - 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 HELLO packets, as specified in AODV documents.
       - No Precursors (Implemented other mechanism so that the protocol can
         still function the same as when precursors are used)
       - Unsolicited RREPs are broadcasted and forwarded only if the node
         is part of the broken route and not the source of that route
       - If more than one route uses the broken link, send RREP multiple times
         (this should be fixed based on new specification by C. Perkins, 
         E. Royer, and S. Das)
       - Rev route of RREQ overwrites the one in the route table
       - May need slight modifications when draft-ietf-manet-aodv-04.txt
         comes out
*/

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

#define max(a,b)        a > b ? a : b





/*
 * RoutingAodvReplaceInsertRouteTable
 *
 * Insert/Update an entry into the route table
 */

static void
RoutingAodvReplaceInsertRouteTable(
    NODE_ADDR destAddr,
    int destSeq,
    int hopCount,
    NODE_ADDR nextHop,
    clocktype lifetime,
    BOOL activated,
    BOOL source,
    AODV_RT* routeTable)
{
    AODV_RT_Node* theNode = NULL;
    AODV_RT_Node* current;
    AODV_RT_Node* previous;
    
    // Find Insertion point. 
    
    previous = NULL;
    current = routeTable->head;
    while ((current != NULL) && (current->destAddr < destAddr)) {
        previous = current;
        current = current->next;
    }//while//
    
    
    if ((current == NULL) || (current->destAddr != destAddr)) {
        ++(routeTable->size);
       
        theNode = (AODV_RT_Node *)checked_pc_malloc(sizeof(AODV_RT_Node));
        theNode->lifetime = lifetime;
        theNode->activated = activated;
        theNode->source = source;
        theNode->destAddr = destAddr;
       
        if (previous == NULL) {
           theNode->next = routeTable->head;
           routeTable->head = theNode;
        } else {
           theNode->next = previous->next;
           previous->next = theNode;
        }//if//
       
       
    } else {
        assert(current->destAddr == destAddr);
        
        current->lifetime = max(lifetime, current->lifetime);
        if (!current->activated) {
            current->activated = activated;
        }//if//
        
        if (!current->source) {
            current->source = source;
        }//if//
        
        theNode = current;
    }//if//
    
    theNode->destSeq = destSeq;
    theNode->hopCount = hopCount;
    theNode->lastHopCount = hopCount;
    theNode->nextHop = nextHop;
    
}//RoutingAodvReplaceInsertRouteTable//   



static 
void RoutingAodvInsertNbrTable(NODE_ADDR destAddr, AODV_NT* nbrTable)
{
    AODV_NT_Node* current;
    AODV_NT_Node* previous;
    
    AODV_NT_Node* newNode = 
       (AODV_NT_Node *)checked_pc_malloc(sizeof(AODV_NT_Node));
    
    newNode->destAddr = destAddr;
    newNode->next = NULL;
    
    ++(nbrTable->size);
    
    // Find Insertion point.  Insert after all address matches.
    
    previous = NULL;
    current = nbrTable->head;
    while ((current != NULL) && (current->destAddr <= destAddr)) {
        previous = current;
        current = current->next;
    }//while//
    
    
    if (previous == NULL) {
        newNode->next = nbrTable->head;
        nbrTable->head = newNode;
    } else {
        newNode->next = previous->next;
        previous->next = newNode;
    }//if//
} /* RoutingAodvInsertNbrTable */


/*
 * RoutingAodvInsertSeenTable
 *
 * Insert an entry into the seen table
 */

static void
RoutingAodvInsertSeenTable(
    GlomoNode *node,
    NODE_ADDR srcAddr,
    int bcastId,
    AODV_RST *seenTable)
{
    if (seenTable->size == 0)
    {
        seenTable->rear = (AODV_RST_Node *) pc_malloc(sizeof(AODV_RST_Node));
        assert(seenTable->rear != NULL);
        seenTable->front = seenTable->rear;
    }
    else
    {
        seenTable->rear->next = (AODV_RST_Node *)
                                pc_malloc(sizeof(AODV_RST_Node));
        assert(seenTable->rear->next != NULL);
        seenTable->rear = seenTable->rear->next;
    }

    seenTable->rear->srcAddr = srcAddr;
    seenTable->rear->bcastId = bcastId;
    seenTable->rear->next = NULL;

    ++(seenTable->size);

    RoutingAodvSetTimer(
        node, MSG_NETWORK_FlushTables, ANY_DEST, (clocktype)BCAST_ID_SAVE);

} /* RoutingAodvInsertSeenTable */

/*
 * RoutingAodvInsertBuffer
 *
 * Insert a packet into the buffer if no route is available
 */
static 
void RoutingAodvInsertBuffer(
    Message* msg,
    NODE_ADDR destAddr,
    AODV_BUFFER* buffer)
{
    AODV_BUFFER_Node* current;
    AODV_BUFFER_Node* previous;
    
    AODV_BUFFER_Node* newNode = 
       (AODV_BUFFER_Node *)checked_pc_malloc(sizeof(AODV_BUFFER_Node));

    newNode->destAddr = destAddr;
    newNode->msg = msg;
    newNode->timestamp = simclock();
    newNode->next = NULL;
    
    ++(buffer->size);
    
    // Find Insertion point.  Insert after all address matches.
    
    previous = NULL;
    current = buffer->head;
    while ((current != NULL) && (current->destAddr <= destAddr)) {
        previous = current;
        current = current->next;
    }//while//
    
    
    if (previous == NULL) {
        newNode->next = buffer->head;
        buffer->head = newNode;
    } else {
        newNode->next = previous->next;
        previous->next = newNode;
    }//if//
} /* RoutingAodvInsertBuffer */



/*
 * RoutingAodvInsertSent
 *
 * Insert an entry into the sent table if RREQ is sent
 */
static void
RoutingAodvInsertSent(
    NODE_ADDR destAddr,
    int ttl,
    AODV_SENT *sent)
{
    AODV_SENT_Node* current;
    AODV_SENT_Node* previous;
    
    AODV_SENT_Node* newNode = 
       (AODV_SENT_Node *)checked_pc_malloc(sizeof(AODV_SENT_Node));

    newNode->destAddr = destAddr;
    newNode->ttl = ttl;
    newNode->times = 0;
    newNode->next = NULL;
    
    (sent->size)++;
    
    // Find Insertion point.  Insert after all address matches.
    
    previous = NULL;
    current = sent->head;
    while ((current != NULL) && (current->destAddr <= destAddr)) {
        previous = current;
        current = current->next;
    }//while//
    
    
    if (previous == NULL) {
        newNode->next = sent->head;
        sent->head = newNode;
    } else {
        newNode->next = previous->next;
        previous->next = newNode;
    }//if//
} /* RoutingAodvInsertSent */


/*
 * RoutingAodvDeleteRouteTable
 *
 * Remove an entry from the route table
 */
void RoutingAodvDeleteRouteTable(NODE_ADDR destAddr, AODV_RT *routeTable)
{
    AODV_RT_Node *toFree;
    AODV_RT_Node *current;

    if (routeTable->size == 0 || routeTable->head == NULL)
    {
        return;
    }
    else if (routeTable->head->destAddr == destAddr)
    {
        if (routeTable->head->lifetime <= simclock())
        {
            toFree = routeTable->head;
            routeTable->head = toFree->next;
            pc_free(toFree);
            --(routeTable->size);
        }
    }
    else
    {
        for (current = routeTable->head; 
             current->next != NULL && current->next->destAddr < destAddr;
             current = current->next)
        {
        }

        if (current->next != NULL && current->next->destAddr == destAddr &&
            current->next->lifetime <= simclock())
        {
            toFree = current->next;
            current->next = toFree->next;
            pc_free(toFree);
            --(routeTable->size);
        }
    }

} /* RoutingAodvDeleteRouteTable */

/*
 * RoutingAodvDeleteNbrTable
 *
 * Remove an entry from the neighbor table
 */
void RoutingAodvDeleteNbrTable(NODE_ADDR destAddr, AODV_NT *nbrTable)
{
    AODV_NT_Node *toFree;
    AODV_NT_Node *current;

    if (nbrTable->size == 0)
    {
        return;
    } 
    else if (nbrTable->head->destAddr == destAddr)
    {
        toFree = nbrTable->head;
        nbrTable->head = toFree->next;
        pc_free(toFree);
        --(nbrTable->size);
    }
    else
    {
        for (current = nbrTable->head;
             ((current->next != NULL) && (current->next->destAddr < destAddr));
             current = current->next)
        {
        }

        if (current->next != NULL && current->next->destAddr == destAddr)
        {
            toFree = current->next;
            current->next = toFree->next;
            pc_free(toFree);
            --(nbrTable->size);
        }
    }

} /* RoutingAodvDeleteNbrTable */

/*
 * RoutingAodvDeleteSeenTable
 *
 * Remove an entry from the seen table
 */
void RoutingAodvDeleteSeenTable(AODV_RST *seenTable)
{
    AODV_RST_Node *toFree;

    toFree = seenTable->front;
    seenTable->front = toFree->next;
    pc_free(toFree);
    --(seenTable->size);

    if (seenTable->size == 0)
    {
        seenTable->rear = NULL;
    }

} /* RoutingAodvDeleteSeenTable */

/*
 * RoutingAodvDeleteBuffer
 *
 * Remove a packet from the buffer; Return TRUE if deleted
 */
BOOL RoutingAodvDeleteBuffer(NODE_ADDR destAddr, AODV_BUFFER *buffer)
{
    AODV_BUFFER_Node *toFree;
    AODV_BUFFER_Node *current;
    BOOL deleted;

    if (buffer->size == 0)
    {
        deleted = FALSE;
    }
    else if (buffer->head->destAddr == destAddr)
    {
        toFree = buffer->head;
        buffer->head = toFree->next;
        pc_free(toFree);
        --(buffer->size);
        deleted = TRUE;
    }
    else
    {
        for (current = buffer->head;
             current->next != NULL && current->next->destAddr < destAddr;
             current = current->next)
        {
        }

        if (current->next != NULL && current->next->destAddr == destAddr)
        {
            toFree = current->next;
            current->next = toFree->next;
            pc_free(toFree);
            --(buffer->size);
            deleted = TRUE;
        }
        else
        {
            deleted = FALSE;