fisheye.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.
/*
 * Fisheye Routing Protocol
 *       file: fisheye.pc
 *         by: Gary Guangyu Pei ([e-mail])
 * objectives: simulate networking routing protocol
 *  reference: Scalable Routing Strategies for Ad-hoc 
 *             Wireless Networks
 *             JSAC special issue on Ad-hoc Aug '99 by UCLA
 *
 */


/*
 * $Id: fisheye.pc,v 1.10 2001/02/15 03:17:26 mineo Exp $
 */


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

/*
 * FUNCTION   RoutingFisheyeInit
 * PURPOSE    Initialize Fisheye variables, being called once for each node 
 *            at the beginning.
 * PARAMETERS  
 *            node - information associated with the node.
 *
 * RETURN     None.                          
 */
void RoutingFisheyeInit(GlomoNode *node,const GlomoNodeInput *nodeInput)
{
  char buf[GLOMO_MAX_STRING_LENGTH];  
  BOOL retVal;
  FILE *fp;
  short Scope;
  char NeighborTOIntervalStr[GLOMO_MAX_STRING_LENGTH],
       IntraUpdateIntervalStr[GLOMO_MAX_STRING_LENGTH],
       InterUpdateIntervalStr[GLOMO_MAX_STRING_LENGTH];
  clocktype randomTime;
  GlomoRoutingFisheye *fisheye;
  Message *newMsg;
  
  fisheye = (GlomoRoutingFisheye *) 
            pc_malloc(sizeof(GlomoRoutingFisheye));
  if (fisheye == NULL) {
    fprintf(stderr, "Fisheye: Cannot alloc memory for Fisheye Routing!\n");
    assert(FALSE);
  }
  
  node->appData.routingVar = (void *)fisheye;

  /* open config file of the fisheye*/
  retVal = GLOMO_ReadString(node->nodeAddr, nodeInput, "FISHEYE-FILE", buf);
  assert(retVal == TRUE);    
  fp = fopen(buf, "r");
  assert(fp != NULL);  

  /* read the fisheye parameters and init the parameter*/
  fscanf(fp,"%hd %s %s %s\n",&Scope,
         NeighborTOIntervalStr,IntraUpdateIntervalStr,
         InterUpdateIntervalStr);
  fisheye->parameter.Scope               
    = Scope ;
  fisheye->parameter.NeighborTOInterval  
    = GLOMO_ConvertToClock(NeighborTOIntervalStr);
  fisheye->parameter.IntraUpdateInterval 
    = GLOMO_ConvertToClock(IntraUpdateIntervalStr);
  fisheye->parameter.InterUpdateInterval 
    = GLOMO_ConvertToClock(InterUpdateIntervalStr);
  fclose(fp);

  /* Initialize the TT */
  RoutingFisheyeInitTT(node,fisheye);

  /* Initialize heard neighbor */
  fisheye->heardNeighborInfo = NULL;

  RoutingFisheyeInitStats(node,fisheye);
 
  /* start TT exchange */
  randomTime = (clocktype) (pc_nrand(node->seed)%FisheyeRandomTimer);
  newMsg = GLOMO_MsgAlloc(node,
                          GLOMO_APP_LAYER,
                          ROUTING_PROTOCOL_FISHEYE,
                          MSG_APP_FisheyeNeighborTimeout);
  GLOMO_MsgSend(node,newMsg,randomTime + 
                fisheye->parameter.NeighborTOInterval);
                
  randomTime = (clocktype) (pc_nrand(node->seed)%FisheyeRandomTimer);
  newMsg = GLOMO_MsgAlloc(node,
                          GLOMO_APP_LAYER,
                          ROUTING_PROTOCOL_FISHEYE,
                          MSG_APP_FisheyeIntraUpdate);
  GLOMO_MsgSend(node,newMsg,randomTime);

  randomTime = (clocktype) (pc_nrand(node->seed)%FisheyeRandomTimer);
  newMsg = GLOMO_MsgAlloc(node,
                          GLOMO_APP_LAYER,
                          ROUTING_PROTOCOL_FISHEYE,
                          MSG_APP_FisheyeInterUpdate);
  GLOMO_MsgSend(node,newMsg,randomTime);

}
/*
 * FUNCTION   RoutingFisheyeFinalize
 * PURPOSE    Print out statistics, being called at the end.
 * PARAMETERS 
 *            node - information associated with the node.
 *
 * RETURN     None. 
 */
void RoutingFisheyeFinalize(GlomoNode *node)
{ 
  if (node->appData.routingStats == TRUE) 
    RoutingFisheyePrintRoutingStats(node);

}
/*
 * FUNCTION   RoutingFisheyeLayer
 * PURPOSE    Simulate Fisheye protocol, being called whenever a message is
 *            for Fisheye routing layer.
 * PARAMETERS 
 *            node - information associated with the node.
 *            message - message header indentifying type of message.
 *
 * RETURN     None.
 */
void RoutingFisheyeLayer(GlomoNode *node, Message *msg)
{ 
  GlomoRoutingFisheye *fisheye;
  char clockStr[GLOMO_MAX_STRING_LENGTH],*payload;
  ctoa(simclock(), clockStr);

  fisheye = (GlomoRoutingFisheye *) node->appData.routingVar;
  assert (fisheye != NULL);

  switch(msg->eventType) {
  case  MSG_APP_FromTransport: 
    {
      RoutingFisheyeHeader *header;
      fisheye->stats.pktNumFromUdp ++ ;

      header = (RoutingFisheyeHeader *) msg->packet;
      GLOMO_MsgRemoveHeader(node,msg,sizeof(RoutingFisheyeHeader));
      payload = msg->packet;

      RoutingFisheyeHandleControlPacket(node,fisheye,header,payload);
      GLOMO_MsgFree(node,msg);

      break;
    }
  case MSG_APP_FisheyeNeighborTimeout:
    {
      RoutingFisheyeHandleNeighborTOMsg(node,fisheye);
      GLOMO_MsgFree(node,msg);
      
      break;
    }
  case MSG_APP_FisheyeIntraUpdate:
    {
      fisheye->stats.intraScopeUpdate ++ ;
      RoutingFisheyeHandleIntraUpdateMsg(node,fisheye);
      GLOMO_MsgFree(node,msg);
 
      break;
    }
  case MSG_APP_FisheyeInterUpdate:
    {
      fisheye->stats.interScopeUpdate ++ ; 
      RoutingFisheyeHandleInterUpdateMsg(node,fisheye);
      GLOMO_MsgFree(node,msg);

      break;
    }
  default:
    assert(FALSE);
  }
}

/* Initialize the Topology table (indexed by nodeAddr)
 * Input parameter: node
 * Assumption NONE
 * RETURN NONE
 */
void RoutingFisheyeInitTT(GlomoNode *node,GlomoRoutingFisheye *fisheye)
{
   int i;

   NetworkEmptyForwardingTable(node);

   /* zero out the routing table*/
   memset((void*)&(fisheye->topologyTable),0,
          sizeof(FisheyeTT));
   /* locate one extra for the Dijkstra's SP */
   fisheye->topologyTable.row =
     (FisheyeTTRow *) pc_malloc((node->numNodes+1) * sizeof(FisheyeTTRow));

   /* Initialize the TT */
   for (i=0;i < (node->numNodes+1); i++){
     fisheye->topologyTable.row[i].lastModifyTime
       = simclock();
     fisheye->topologyTable.row[i].sequenceNumber
       = -1;
     fisheye->topologyTable.row[i].neighborNumber
       = 0;
     fisheye->topologyTable.row[i].neighborInfo
       = NULL;
     if ( i != node->nodeAddr) {
       fisheye->topologyTable.row[i].nextHop 
         = -1;
       fisheye->topologyTable.row[i].prevHop 
         = -1;
       fisheye->topologyTable.row[i].distance 
         = FisheyeInfinity;
     }
     else {
       fisheye->topologyTable.row[i].nextHop 
         = node->nodeAddr;
       fisheye->topologyTable.row[i].prevHop 
         = node->nodeAddr;
       fisheye->topologyTable.row[i].distance 
         = 0;
     }
     if ( i < node->numNodes) {
       if (fisheye->topologyTable.row[i].nextHop > 0 )
         NetworkUpdateForwardingTable(node, i, DEFAULT_INTERFACE,
                                      fisheye->topologyTable.row[i].nextHop);
       else
         NetworkUpdateForwardingTable(
           node, i, DEFAULT_INTERFACE, NETWORK_UNREACHABLE);
     }  
   }
}

/* Initialize the Stats variable
 * RETURN: NONE
 */
void RoutingFisheyeInitStats(GlomoNode *node,GlomoRoutingFisheye *fisheye)
{
  /* Total number of TT updates In the scope */
  fisheye->stats.intraScopeUpdate = 0;

  /* Total number of TT updates out the scope*/
  fisheye->stats.interScopeUpdate = 0;
  
  /* Total Control OH in bytes */
  fisheye->stats.controlOH = 0;
  
}


/* Name      : RoutingFisheyeCreateHeader
 * Purpose   : Funtion to Create the network data unit
 * Parameters: sourceAddr, source sending the packet
 *             destinationAddr, destination of the packet to be sent
 *             pktLength, length of the packet
 * Return    : FisheyeRoutingPktDataUnit
 * Assumption: None
 */
RoutingFisheyeHeader
RoutingFisheyeCreateHeader(NODE_ADDR sourceAddr,
                           NODE_ADDR destinationAddr,
                           int payloadSize)
{
  RoutingFisheyeHeader header;

  header.sourceAddr          =  sourceAddr;
  header.destinationAddr     =  destinationAddr;
  header.payloadSize         =  MIN(payloadSize,MAX_TT_SIZE);

  return header;
}

/* Name     :   RoutingFisheyeSendScopeTT
 * Purpose  :   Function to send update TT packets from lower to upper
 *              distance
 * Parameter:   node
 * Return   :   none
 */
void RoutingFisheyeSendScopeTT(GlomoNode *node, 
                               GlomoRoutingFisheye *fisheye,
                               short lower,short upper)
{
  RoutingFisheyeHeader header;
  int i,TTindex,max,maxEntrySize,broadcastTTsize;
  FisheyeTTRow *row;
  char payload[MAX_TT_SIZE];
  FisheyeNeighborInfo *tmp;
  clocktype delay = 0;
  
  TTindex = 0;
  max = -1;
  row = fisheye->topologyTable.row;
  
  /* Find out the max number of a node in the scope entries */
  for (i = 0; i< node->numNodes;i++) {
    if(row[i].distance >= lower && row[i].distance < upper) {
      if (row[i].neighborNumber > max) 
        max = row[i].neighborNumber;
    }
  }
  
  maxEntrySize = sizeof(TTindex)               +
                 sizeof(row[0].sequenceNumber) + 
                 sizeof(row[0].neighborNumber) +
                 sizeof(NODE_ADDR)*max;
  
  /* packet the entries to nwDU, multiple nwDUs are sent
     in the case of size exceeds one packet */
  while ( TTindex < node->numNodes) {
    
    broadcastTTsize = 0;
    while ( ((broadcastTTsize + maxEntrySize) <= MAX_TT_SIZE) &&
            (TTindex < node->numNodes) ){
      if(row[TTindex].distance >= lower && row[TTindex].distance < upper){
        /* Entry index */
        memcpy(&(payload[broadcastTTsize]),&TTindex,sizeof(TTindex));
        broadcastTTsize += sizeof(TTindex);
        /* Sequence number */
        memcpy(&(payload[broadcastTTsize]),&(row[TTindex].sequenceNumber),
               sizeof(row[TTindex].sequenceNumber));
        broadcastTTsize += sizeof(row[TTindex].sequenceNumber);
        /* number of neighbors */
        memcpy(&(payload[broadcastTTsize]),&(row[TTindex].neighborNumber),
               sizeof(row[TTindex].neighborNumber));
        broadcastTTsize += sizeof(row[TTindex].neighborNumber);
        /* the neighbor IDs */
        tmp = row[TTindex].neighborInfo;
        while ( tmp != NULL) {
          memcpy(&(payload[broadcastTTsize]),&(tmp->nodeAddr),
                 sizeof(tmp->nodeAddr));
          broadcastTTsize += sizeof(tmp->nodeAddr);
          tmp = tmp->next;
        }
      }
      
      TTindex ++;
    }
    
    if (broadcastTTsize > 0 ) {
      /* create header and send TT to UDP */
      
      header = RoutingFisheyeCreateHeader(node->nodeAddr,
                                          ANY_DEST,
                                          broadcastTTsize);

      /* Send to neighbors*/
      AppUdpSendNewHeaderDataWithPriority(node,
                                                     ROUTING_PROTOCOL_FISHEYE,
                                                     ANY_DEST,
                                                     (char *)&header,
                                                     sizeof(RoutingFisheyeHeader),
                                                     payload,
                                                     broadcastTTsize,
                                                     CONTROL,
                                                     delay);

      fisheye->stats.controlOH += broadcastTTsize;
    }
  }


  
  
}

/* Name      :  RoutingFisheyeUpdateNeighbor
 * Purpose   :  Update Neighbor Information based on the 
 *              control packet received
 * Papramers :  node and packet
 * Return    :  None
 */
void RoutingFisheyeUpdateNeighborInfo(GlomoNode *node,
                                      GlomoRoutingFisheye *fisheye,
                                      RoutingFisheyeHeader *header)
{
  int index;
  FisheyeHeardNeighborInfo *tmp;

  index = node->nodeAddr;

  if(fisheye->heardNeighborInfo
     == NULL) {
    /* I don't have any neighbour yet */
    assert(fisheye->topologyTable.row[index].neighborNumber == 0 );
    tmp = (FisheyeHeardNeighborInfo *) 
      pc_malloc(sizeof(FisheyeHeardNeighborInfo));
    assert(tmp != NULL);
    tmp->nodeAddr = header->sourceAddr;
    tmp->lastHeardTime = simclock();
    tmp->next = fisheye->heardNeighborInfo;
    fisheye->heardNeighborInfo = tmp;
    fisheye->topologyTable.row[index].neighborNumber ++;
    RoutingFisheyeCopyHeardToTable(node,fisheye);
    RoutingFisheyeFindSP(node);
  }
  else {
    /* Update neighbor info if header->sourceAddr in the list
       otherwise insert it */
    int Find = 0;
    FisheyeHeardNeighborInfo *prev;

    tmp =fisheye->heardNeighborInfo ;
    while ( !Find && tmp != NULL) {
      if (tmp->nodeAddr == header->sourceAddr) {
        Find = 1;
        tmp->lastHeardTime = simclock();
      }
      prev = tmp;
      tmp = tmp->next;
    }
    if (!Find) {
      tmp = (FisheyeHeardNeighborInfo *) 
        pc_malloc(sizeof(FisheyeHeardNeighborInfo));
      assert(tmp != NULL);
      tmp->nodeAddr = header->sourceAddr;
      tmp->lastHeardTime = simclock();
      tmp->next = prev->next;
      prev->next = tmp ;
      fisheye->topologyTable.row[index].neighborNumber ++;
      RoutingFisheyeCopyHeardToTable(node,fisheye);
      RoutingFisheyeFindSP(node);
    }
  }