link_set.c

wifi 无线网络路由协议OLSR linux下C代码

       * We'll go for one that is hopefully long
       * enough in most cases. 10 seconds
       */

    /* Erik Tromp - commented out. It is not RFC-compliant. Also, MID aliases
     * that are not explicitly declared by a node will be removed as soon as
     * the olsr_prune_aliases(...) function is called.
     *
     * OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
     * OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
     * insert_mid_alias(remote_main, remote, MID_ALIAS_HACK_VTIME);
     */
    }

  return link_set;
}


/**
 *Lookup the status of a link.
 *
 *@param int_addr address of the remote interface
 *
 *@return 1 of the link is symmertic 0 if not
 */

int
check_neighbor_link(const union olsr_ip_addr *int_addr)
{
  struct link_entry *tmp_link_set;

  tmp_link_set = link_set;

  while(tmp_link_set)
    {
      if(COMP_IP(int_addr, &tmp_link_set->neighbor_iface_addr))
	return lookup_link_status(tmp_link_set);
      tmp_link_set = tmp_link_set->next;
    }
  return UNSPEC_LINK;
}


/**
 *Lookup a link entry
 *
 *@param remote the remote interface address
 *@param remote_main the remote nodes main address
 *@param local the local interface address
 *
 *@return the link entry if found, NULL if not
 */
struct link_entry *
lookup_link_entry(const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main, const struct interface *local)
{
  struct link_entry *tmp_link_set;

  tmp_link_set = link_set;

  while(tmp_link_set)
    {
      if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
	 (tmp_link_set->if_name
          ? !strcmp(tmp_link_set->if_name, local->int_name)
          : COMP_IP(&local->ip_addr, &tmp_link_set->local_iface_addr)
          ) &&
         /* check the remote-main address only if there is one given */
         (remote_main == NULL || COMP_IP(remote_main, &tmp_link_set->neighbor->neighbor_main_addr))
         )
	return tmp_link_set;
      tmp_link_set = tmp_link_set->next;
    }
  return NULL;

}







/**
 *Update a link entry. This is the "main entrypoint" in
 *the link-sensing. This function is called from the HELLO
 *parser function.
 *It makes sure a entry is updated or created.
 *
 *@param local the local IP address
 *@param remote the remote IP address
 *@param message the HELLO message
 *@param in_if the interface on which this HELLO was received
 *
 *@return the link_entry struct describing this link entry
 */
struct link_entry *
update_link_entry(const union olsr_ip_addr *local, 
		  const union olsr_ip_addr *remote, 
		  const struct hello_message *message, 
		  const struct interface *in_if)
{
  struct link_entry *entry;

  /* Add if not registered */
  entry = add_link_entry(local, remote, &message->source_addr, message->vtime, message->htime, in_if);

  /* Update ASYM_time */
  //printf("Vtime is %f\n", message->vtime);
  /* L_ASYM_time = current time + validity time */
  entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
  
  entry->prev_status = check_link_status(message, in_if);
  
  //printf("Status %d\n", status);
  
  switch(entry->prev_status)
    {
    case(LOST_LINK):
      /* L_SYM_time = current time - 1 (i.e., expired) */
      entry->SYM_time = now_times - 1;

      break;
    case(SYM_LINK):
    case(ASYM_LINK):
      /* L_SYM_time = current time + validity time */
      //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
      entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);

      /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
      entry->time = entry->SYM_time + hold_time_neighbor;

      break;
    default:;
    }

  /* L_time = max(L_time, L_ASYM_time) */
  if(entry->time < entry->ASYM_time)
    entry->time = entry->ASYM_time;


  /*
  printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
  printf("REMOTE: %s\n", olsr_ip_to_string(remote));
  printf("VTIME: %f ", message->vtime);
  printf("STATUS: %d\n", status);
  */

  /* Update hysteresis values */
  if(olsr_cnf->use_hysteresis)
    olsr_process_hysteresis(entry);

  /* Update neighbor */
  update_neighbor_status(entry->neighbor, get_neighbor_status(remote));

  return entry;  
}


/**
 * Fuction that updates all registered pointers to
 * one neighbor entry with another pointer
 * Used by MID updates.
 *
 *@old the pointer to replace
 *@new the pointer to use instead of "old"
 *
 *@return the number of entries updated
 */
int
replace_neighbor_link_set(const struct neighbor_entry *old,
			  struct neighbor_entry *new)
{
  struct link_entry *tmp_link_set;
  int retval;

  retval = 0;

  if(link_set == NULL)
    return retval;
      
  tmp_link_set = link_set;

  while(tmp_link_set)
    {

      if(tmp_link_set->neighbor == old)
	{
	  tmp_link_set->neighbor = new;
	  retval++;
	}
      tmp_link_set = tmp_link_set->next;
    }

  return retval;

}


/**
 *Checks the link status to a neighbor by
 *looking in a received HELLO message.
 *
 *@param message the HELLO message to check
 *
 *@return the link status
 */
static int
check_link_status(const struct hello_message *message, const struct interface *in_if)
{
  int ret = UNSPEC_LINK;
  struct hello_neighbor  *neighbors;

  neighbors = message->neighbors;
  
  while(neighbors!=NULL)
    {
      /*
       * Note: If a neigh has 2 cards we can reach, the neigh
       * will send a Hello with the same IP mentined twice
       */
      if(COMP_IP(&neighbors->address, &in_if->ip_addr))
        {
	  //printf("ok");
	  ret = neighbors->link;
	  if (SYM_LINK == ret) break;
	}

      neighbors = neighbors->next; 
    }


  return ret;
}


/**
 *Time out the link set. In other words, the link
 *set is traversed and all non-valid entries are
 *deleted.
 *
 */
static void
olsr_time_out_link_set(void)
{

  struct link_entry *tmp_link_set, *last_link_entry;

  if(link_set == NULL)
    return;
      
  tmp_link_set = link_set;
  last_link_entry = NULL;

  while(tmp_link_set)
    {

      if(TIMED_OUT(tmp_link_set->time))
	{
	  if(last_link_entry != NULL)
	    {
	      last_link_entry->next = tmp_link_set->next;

	      /* Delete neighbor entry */
	      if(tmp_link_set->neighbor->linkcount == 1)
		olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
	      else
		tmp_link_set->neighbor->linkcount--;

	      //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
	      changes_neighborhood = OLSR_TRUE;
	      free(tmp_link_set->if_name);
	      free(tmp_link_set);
	      tmp_link_set = last_link_entry;
	    }
	  else
	    {
	      link_set = tmp_link_set->next; /* CHANGED */

	      /* Delete neighbor entry */
	      if(tmp_link_set->neighbor->linkcount == 1)
		olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
	      else
		tmp_link_set->neighbor->linkcount--;

	      changes_neighborhood = OLSR_TRUE;

	      free(tmp_link_set->if_name);
	      free(tmp_link_set);
	      tmp_link_set = link_set;
	      continue;
	    }	    
	}
      else if((tmp_link_set->prev_status == SYM_LINK) &&
	      TIMED_OUT(tmp_link_set->SYM_time))
	{
	  tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
	  update_neighbor_status(tmp_link_set->neighbor, 
				 get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
	  changes_neighborhood = OLSR_TRUE;
	}
      
      last_link_entry = tmp_link_set;
      tmp_link_set = tmp_link_set->next;
    }

  return;
}




/**
 *Updates links that we have not received
 *HELLO from in expected time according to 
 *hysteresis.
 *
 *@return nada
 */
static void
olsr_time_out_hysteresis(void)
{
  struct link_entry *tmp_link_set;

  if(link_set == NULL)
    return;

  tmp_link_set = link_set;

  while(tmp_link_set)
    {
      if(TIMED_OUT(tmp_link_set->hello_timeout))
	{
	  tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
	  OLSR_PRINTF(1, "HYST[%s] HELLO timeout %0.3f\n", olsr_ip_to_string(&tmp_link_set->neighbor_iface_addr), tmp_link_set->L_link_quality);
	  /* Update hello_timeout - NO SLACK THIS TIME */
	  tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
	  /* Recalculate status */
	  /* Update hysteresis values */
	  olsr_process_hysteresis(tmp_link_set);
	  
	  /* update neighbor status */


	  /* Update neighbor */
	  update_neighbor_status(tmp_link_set->neighbor, 
				 get_neighbor_status(&tmp_link_set->neighbor_iface_addr));

	  /* Update seqno - not mentioned in the RFC... kind of a hack.. */
	  tmp_link_set->olsr_seqno++;
	}
      tmp_link_set = tmp_link_set->next;
    }

  return;
}

void olsr_print_link_set(void)
{
  struct link_entry *walker;
  const int addrsize = olsr_cnf->ip_version == AF_INET ? 15 : 39;

  OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
              nowtm->tm_hour,
              nowtm->tm_min,
              nowtm->tm_sec,
              (int)now.tv_usec/10000U);
  OLSR_PRINTF(1, "%-*s  %-6s %-6s %-6s %-6s %-6s %s\n", addrsize, "IP address", "hyst", "LQ", "lost", "total","NLQ", "ETX");

  for (walker = link_set; walker != NULL; walker = walker->next)
  {
    float etx;

    if (walker->loss_link_quality < MIN_LINK_QUALITY || walker->neigh_link_quality < MIN_LINK_QUALITY)
      etx = 0.0;
    else
      etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);

    OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n",
                addrsize, olsr_ip_to_string(&walker->neighbor_iface_addr),
                walker->L_link_quality,
                walker->loss_link_quality,
		walker->lost_packets,
                walker->total_packets,
		walker->neigh_link_quality,
                etx);
  }
}

static void update_packet_loss_worker(struct link_entry *entry, int lost)
{
  unsigned char mask = 1 << (entry->loss_index & 7);
  const int idx = entry->loss_index >> 3;
  double rel_lq, saved_lq;

  if (lost == 0)
    {
      // packet not lost

      if ((entry->loss_bitmap[idx] & mask) != 0)
        {
          // but the packet that we replace was lost
          // => decrement packet loss

          entry->loss_bitmap[idx] &= ~mask;
          entry->lost_packets--;
        }
    }

  else
    {
      // packet lost

      if ((entry->loss_bitmap[idx] & mask) == 0)
        {
          // but the packet that we replace was not lost
          // => increment packet loss

          entry->loss_bitmap[idx] |= mask;
          entry->lost_packets++;
        }
    }

  // move to the next packet

  entry->loss_index++;

  // wrap around at the end of the packet loss window

  if (entry->loss_index >= olsr_cnf->lq_wsize)
    entry->loss_index = 0;

  // count the total number of handled packets up to the window size

  if (entry->total_packets < olsr_cnf->lq_wsize)
    entry->total_packets++;

  // the current reference link quality

  saved_lq = entry->saved_loss_link_quality;

  if (saved_lq == 0.0)
    saved_lq = -1.0;

  // calculate the new link quality
  //
  // start slowly: receive the first packet => link quality = 1 / n
  //               (n = window size)
  entry->loss_link_quality =
    (float)(entry->total_packets - entry->lost_packets) /
    (float)(olsr_cnf->lq_wsize < (2 * 4) ? olsr_cnf->lq_wsize: 
    4 * (((float)olsr_cnf->lq_wsize / 4 - 1) * entry->total_packets + olsr_cnf->lq_wsize) / olsr_cnf->lq_wsize);
    
  // multiply the calculated link quality with the user-specified multiplier

  entry->loss_link_quality *= entry->loss_link_multiplier;

  // if the link quality has changed by more than 10 percent,
  // print the new link quality table

  rel_lq = entry->loss_link_quality / saved_lq;

  if (rel_lq > 1.1 || rel_lq < 0.9)
    {
      entry->saved_loss_link_quality = entry->loss_link_quality;

      if (olsr_cnf->lq_dlimit > 0)
      {
        changes_neighborhood = OLSR_TRUE;
        changes_topology = OLSR_TRUE;
      }

      else
        OLSR_PRINTF(3, "Skipping Dijkstra (1)\n");

      // create a new ANSN

      // XXX - we should check whether we actually
      // announce this neighbour

      signal_link_changes(OLSR_TRUE);
    }
}

void olsr_update_packet_loss_hello_int(struct link_entry *entry,
                                       double loss_hello_int)
{
  // called for every LQ HELLO message - update the timeout
  // with the htime value from the message

  entry->loss_hello_int = loss_hello_int;
}

void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interface *loc,
                             olsr_u16_t seqno)
{
  struct link_entry *entry;

  // called for every OLSR packet

  entry = lookup_link_entry(rem, NULL, loc);

  // it's the very first LQ HELLO message - we do not yet have a link

  if (entry == NULL)
    return;
    
  // a) have we seen a packet before, i.e. is the sequence number valid?

  // b) heuristically detect a restart (= sequence number reset)
  //    of our neighbor

  if (entry->loss_seqno_valid != 0 && 
      (unsigned short)(seqno - entry->loss_seqno) < 100)
    {
      // loop through all lost packets

      while (entry->loss_seqno != seqno)
        {
          // have we already considered all lost LQ HELLO messages?

          if (entry->loss_missed_hellos == 0)
            update_packet_loss_worker(entry, 1);

          // if not, then decrement the number of lost LQ HELLOs

          else
            entry->loss_missed_hellos--;

          entry->loss_seqno++;
        }
    }

  // we have received a packet, otherwise this function would not
  // have been called

  update_packet_loss_worker(entry, 0);

  // (re-)initialize

  entry->loss_missed_hellos = 0;
  entry->loss_seqno = seqno + 1;

  // we now have a valid serial number for sure

  entry->loss_seqno_valid = 1;

  // timeout for the first lost packet is 1.5 x htime

  entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
}

static void olsr_time_out_packet_loss(void)
{
  struct link_entry *walker;

  // loop through all links

  for (walker = link_set; walker != NULL; walker = walker->next)
    {
      // find a link that has not seen any packets for a very long
      // time (first time: 1.5 x htime, subsequently: 1.0 x htime)

      if (!TIMED_OUT(walker->loss_timeout))
        continue;
      
      // count the lost packet

      update_packet_loss_worker(walker, 1);

      // memorize that we've counted the packet, so that we do not
      // count it a second time later

      walker->loss_missed_hellos++;

      // next timeout in 1.0 x htime

      walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
    }
}

void olsr_update_dijkstra_link_qualities(void)
{
  struct link_entry *walker;

  for (walker = link_set; walker != NULL; walker = walker->next)
  {
    walker->loss_link_quality2 = walker->loss_link_quality;
    walker->neigh_link_quality2 = walker->neigh_link_quality;
  }
}