ntable.cc

CBRP协议（移动adhoc中基于分簇的路由协议）ns2下的源码

  ent = head;
  while (ent) {
    if ( ent->neighbor == dest ) 
      return ent;
    ent = ent->next;
  }
  return NULL;
}

nsaddr_t
NeighborTable::GetQuickNextNode(nsaddr_t dest) {
  
  double now = Scheduler::instance().clock();
  if ((now - adjtable[dest-1].last_updated) > 1.1*BROADCAST_INTEVAL) {
    return 0;
  }else { 
    return adjtable[dest-1].the_node;
  }

}
adjtable_ent *
NeighborTable::GetAdjEntry(nsaddr_t dest_cluster, int primary) {

  adjtable_ent *ent;
  
  if (primary) {
    ent = adjtable_1;
  }else {
    ent = adjtable_2;
  }

  while(ent) {
    if (ent->neighbor_cluster == dest_cluster) 
      return ent;
    ent = ent->next;
  }
  return NULL;
}

void
NeighborTable::processUpdate(Packet *p) {

  hdr_ip *iph = (hdr_ip *) p->access (a->off_ip_);
  hdr_cmn *cmnh = (hdr_cmn *)p->access(a->off_cmn_);

  int i;
  int size;
  int adj_size;
  int dest;
  int dest_status;
  unsigned char *d;
  unsigned char *tmp_d;

  Scheduler & s = Scheduler::instance();
 
  assert(cmnh->ptype() == PT_MESSAGE);
  d = p->accessdata ();

  ntable_ent *rte = new ntable_ent();
  rte->last_update = s.clock(); 
  rte->neighbor = iph->src_;
  rte->neighbor_status = *(d++);
  rte->link_status = LINK_FROM;
  rte->n_pkt = NULL;
  rte->next = NULL;

  size = *(d++);
  adj_size = *(d++);

  tmp_d = d;
  for (i = size; i>0; i--) {

    dest = *(d++);
    d++;
    if (dest == a->myaddr_) {
      rte->link_status = LINK_BIDIRECTIONAL;
      break;
    }
  }
  /* I will check last_update to see whether this entry is worth a real update to the neighbortable */
/*
  if ((rte->last_update -  last_update[rte->neighbor])<BROADCAST_INTEVAL) {
*/
    AddUpdateEntry(rte);
/*
    last_update[rte->neighbor] = rte->last_update;
  }else {
    last_update[rte->neighbor] = rte->last_update;
    delete rte;
    Packet::free(p);
    return;
  }
*/
    
  if (rte->link_status != LINK_BIDIRECTIONAL) {
    rte->n_pkt = NULL;
    Packet::free(p);
    return;
  }
  d = tmp_d;

  for (i = size; i>0; i--) {

    dest = *(d++);
    dest_status = *(d++);

    if (dest == a->myaddr_) {
      continue;
    }
    AddUpdateQuickAdj(dest,dest_status,iph->src_);
    if ((dest_status == CLUSTER_HEAD) && (!GetEntry(dest))) {
      AddUpdateAdj(dest,iph->src_,1);
    }
  }

  if (my_status == CLUSTER_HEAD) {
    
    for (i = adj_size;i>0;i--) {
      dest = *(d++);
      AddUpdateAdj(dest,iph->src_,0); 
  
    }
  }

  if (my_status != CLUSTER_HEAD) {
    Packet::free(p);
    rte->n_pkt = NULL;
  }else {
    rte->n_pkt = p;
  }
}

void
NeighborTable::AddUpdateQuickAdj(nsaddr_t dest, uint dest_status,nsaddr_t next_node ) 

{

  Scheduler & s = Scheduler::instance();

 adjtable[dest-1].the_node = next_node;
  adjtable[dest-1].dest_status = dest_status;
  adjtable[dest-1].last_updated = s.clock();
}

void
NeighborTable::AddUpdateAdj(nsaddr_t dest, nsaddr_t next_stop, int primary){

  adjtable_ent *tmp;
  adjtable_ent *prev = NULL;
  adjtable_ent *ent;
  nexthop_ent *phop_prev;
  nexthop_ent *phop = NULL;

  Scheduler & s = Scheduler::instance();

  if (primary) {
    tmp = adjtable_1;
  }else {
    tmp = adjtable_2;
  }

  while (tmp && (tmp->neighbor_cluster != dest)) {
    prev = tmp;
    tmp = tmp->next;
  }
 
  if (tmp) {
    phop = tmp->next_hop;
    phop_prev = NULL;

    while (phop) {
      if (phop->next_node == next_stop ) {
        break;
      }
      phop_prev = phop;
      phop = phop->next;
    }

    if (phop) {
      s.cancel(phop->timeout_event);
      s.schedule(timeout_handler, phop->timeout_event, 1.1*BROADCAST_INTEVAL);
    }else {
      phop = new nexthop_ent();
      phop->next = NULL;
      phop->next_node = next_stop;
      phop->timeout_event = new Event;
      s.schedule(timeout_handler, phop->timeout_event, 1.1*BROADCAST_INTEVAL);
      
      if (phop_prev == NULL) {
        phop->next = tmp->next_hop;
        tmp->next_hop = phop;
      }else {
        phop_prev->next = phop;
      }
    } 

  }else {
  
    ent = new adjtable_ent();    
    ent->neighbor_cluster = dest;

    phop = new nexthop_ent();
    phop->next = NULL;
    phop->next_node = next_stop;
    phop->timeout_event = new Event;
    s.schedule(timeout_handler, phop->timeout_event, 1.1*BROADCAST_INTEVAL);
    ent->next_hop = phop;

    if (primary) {
      ent->next = adjtable_1;
      adjtable_1 = ent;
      adjtable_size++;
    }else {
      ent->next = adjtable_2;
      adjtable_2 = ent;
    }
  }


}
     
void
NeighborTable::AddUpdateEntry(ntable_ent  *prte) {

  ntable_ent *tmp;
  ntable_ent *prev_tmp;
  Scheduler & s = Scheduler::instance();

  assert((prte->neighbor>0) && (prte->neighbor<= MAX_NODE_NUM));

  tmp = head;
  prev_tmp = NULL;
  while (tmp && (tmp->neighbor != prte->neighbor)) {
   
     prev_tmp = tmp;
     tmp = tmp->next;
  }

  if (tmp) {
    if (tmp->n_pkt) {
      Packet::free(tmp->n_pkt);
    }
    prte->timeout_event = tmp->timeout_event;
    s.cancel(tmp->timeout_event);
  }else {
    //size of neighbor table has increased by 1
    my_size++;
    prte->timeout_event =  new Event;
  }
  s.schedule(timeout_handler, prte->timeout_event, 2.1*BROADCAST_INTEVAL);
 
  if (tmp) {
    
    //a neighbor changed from non-clusterhead to clusterhead
    if ((tmp->neighbor_status != CLUSTER_HEAD) && 
        (prte->neighbor_status == CLUSTER_HEAD) &&
        (prte->link_status == LINK_BIDIRECTIONAL)) {
      no_of_clusterheads++;

    //a neighbor changed from clusterhead to non-clusterhead
    }else if ((tmp->neighbor_status == CLUSTER_HEAD) &&
              (prte->neighbor_status != CLUSTER_HEAD) &&
              (tmp->link_status == LINK_BIDIRECTIONAL)) {
      no_of_clusterheads--;

    }else if ((tmp->neighbor_status == CLUSTER_HEAD) &&
              (prte->neighbor_status == CLUSTER_HEAD)) {
      if ((tmp->link_status == LINK_FROM) &&
          (prte->link_status == LINK_BIDIRECTIONAL)) {
        no_of_clusterheads++;
      }else if ((tmp->link_status == LINK_BIDIRECTIONAL)&&
                (prte->link_status==LINK_FROM)) {
        no_of_clusterheads--;
      }
    }

//if this entry is a new one
  }else if ((prte->neighbor_status == CLUSTER_HEAD)&&
           (prte->link_status == LINK_BIDIRECTIONAL)) {
    no_of_clusterheads++;
  }
 
  if (prev_tmp && tmp) {
    prev_tmp->next = prte;
    prte->next = tmp->next;
    tmp->next = NULL;
    delete tmp;
  } else if (tmp) {
    prte->next = tmp->next;
    head = prte;
    tmp->next = NULL;
    delete tmp;
  } else {
    prte->next = head;
    head = prte;
  }      

  Packet *p; 

  if ((my_status == CLUSTER_HEAD) && 
      (prte->neighbor_status == CLUSTER_HEAD) &&
      (prte->link_status == LINK_BIDIRECTIONAL)) {
    
    if (!in_contention) {
      in_contention = 1;
      s.schedule(c_contention_handler,c_contention_event,2*BROADCAST_INTEVAL);
    }
  }else if ((my_status == CLUSTER_UNDECIDED)&&
            (prte->neighbor_status == CLUSTER_HEAD) &&
            (prte->link_status == LINK_BIDIRECTIONAL)) {
    s.cancel(c_form_event);
    my_status = CLUSTER_MEMBER;
    p = getBroadcastPacket();
    s.schedule(a->ll, p, 0);


  }

  //check if I have lost all cluster heads
  if ((my_status == CLUSTER_MEMBER) && no_of_clusterheads == 0) {
    lostClusterHeads();
  }

}

bool
NeighborTable::isNeighbor(nsaddr_t addr) 
{

  ntable_ent *ent = GetEntry(addr);
  if (ent == NULL) {
    return false;
  }else {
    return true;
  }

}

bool
NeighborTable::existsLink(nsaddr_t from, nsaddr_t to)
{
  int i;
  int size;
  unsigned char *d;
  ntable_ent *ent;
  nsaddr_t dest;

  assert(my_status == CLUSTER_HEAD);
  
  if (to == a->myaddr_) {
    return isNeighbor(from);
  }else if (from == a->myaddr_) {
    return isNeighbor(to);
  }
  
  ent = GetEntry(to);
  
  if (!ent || !ent->n_pkt) return false;

  //Jinyang -need to be improved
  //assert(ent->n_pkt);

  d = (ent->n_pkt)->accessdata ();

  d++;
  size = *(d++);
  d++;

  for (i = size; i>0; i--) {

    dest = *(d++);
    d++;
    
    if (dest == from) {
      return true;
    }
  }
  return false;
}

#ifdef CBRP_DEBUG
char *
NeighborTable::printNeighbors()
{
  static char buf[200];
  char *ptr = buf;
  char *rtn_buf = ptr;
  ntable_ent *ent = head;

  if (!my_size) {
    sprintf(rtn_buf,"[<empty table>]");
    return rtn_buf;
  }

  *ptr++ = '[';
  while (ent) {
    ptr += sprintf(ptr,"%d ",ent->neighbor);
    ent = ent->next;
  }
  *ptr++ = ']';
  *ptr++ = '\0';
  return rtn_buf;
}

char *
NeighborTable::printHELLOpkt(Packet *p)
{
  static char buf[500];
  char *ptr = buf;
  char *rtn_buf = buf;
  unsigned char *d;
  int n_count;
  int adj_count;
  hdr_ip *iph = (hdr_ip *) p->access (a->off_ip_);
  int i;

  d = p->accessdata();
  ptr += sprintf(ptr, "neighbor %d ", iph->src_);
  ptr += sprintf(ptr, "status %d ", *(d++));
  n_count = *(d++);
  ptr += sprintf(ptr, "n_count %d ",n_count); 
  adj_count = *(d++);
  ptr += sprintf(ptr, "adj_count %d ", adj_count);

  for (i=0;i<n_count;i++) {
    ptr += sprintf(ptr, "(");
    ptr += sprintf(ptr, "%d %d", *(d++), *(d++));
    ptr += sprintf(ptr, ")");
  }

  for (i = 0; i<adj_count;i++) {
    ptr += sprintf(ptr, "%d", *(d++));
  }
  *ptr++ = '\n';
  *ptr++ = '\0';
  return rtn_buf;

}

char *
NeighborTable::PrintTwoHopNeighbors()
{
  static char buf[2000];
  char *ptr = buf;
  char *rtn_buf = ptr;
  double now = Scheduler::instance().clock();

  *ptr++ = '[';
  for (int i = 0;i<MAX_NODE_NUM;i++) {
    if (GetEntry(i+1)|| !adjtable[i].the_node ) {
      continue;
    }
    ptr += sprintf(ptr," (%d %d %.5f) ", i+1, adjtable[i].the_node, adjtable[i].last_updated);
  }
  *ptr++ = ']';
  *ptr++ = '\0';
  return rtn_buf;
}
#endif CBRP_DEBUG

void
NeighborTable::DeleteAdjEntry(nsaddr_t dest,int primary) 
{

  //check if adjtable caused the timeout
  adjtable_ent *p;
  adjtable_ent *p_prev=NULL;
  nexthop_ent *phop = NULL;
  nexthop_ent *phop_prev = NULL;

  if (primary) {
    p = adjtable_1;
  }else{
    p = adjtable_2;
  }

  while (p) {

    //double loop
NEXT:
    phop = p->next_hop;
    phop_prev = NULL;

    while (phop) {

      if (phop->next_node== dest) {

        if (phop_prev) {
          phop_prev->next = phop->next;
        }else {
          p->next_hop = phop->next;
        }

        if (!p->next_hop) {
          if (p_prev) {
            p_prev->next = p->next;
          }else {
            if (primary) {
              adjtable_1 = p->next;
            }else {
              adjtable_2 = p->next;
            }
          }
          adjtable_ent *tmp = p->next;
          delete p;
          p = tmp;
     
          if (primary) {
            adjtable_size--;
          }

          delete phop;
      
          if (!p) {
            return;
          }
          goto NEXT;
        }else {
          delete phop;
          break;
        }
      }
      phop_prev = phop;
      phop = phop->next;
    }
    p_prev = p;
    p = p->next;
  }
}