/*
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
* * Neither the name of olsr.org, olsrd nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Visit http://www.olsr.org for more information.
*
* If you find this software useful feel free to make a donation
* to the project. For more information see the website or contact
* the copyright holders.
*
* $Id: link_set.c,v 1.74 2007/10/05 20:10:24 bernd67 Exp $
*/
/*
* Link sensing database for the OLSR routing daemon
*/
#include "defs.h"
#include "link_set.h"
#include "hysteresis.h"
#include "mid_set.h"
#include "mpr.h"
#include "neighbor_table.h"
#include "olsr.h"
#include "scheduler.h"
#include "lq_route.h"
static clock_t hold_time_neighbor;
struct link_entry *link_set;
static int
check_link_status(const struct hello_message *message, const struct interface *in_if);
static void
olsr_time_out_hysteresis(void);
static void olsr_time_out_packet_loss(void);
static struct link_entry *
add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *, double, double, const struct interface *);
static void
olsr_time_out_link_set(void);
static int
get_neighbor_status(const union olsr_ip_addr *);
clock_t
get_hold_time_neighbor(void)
{
return hold_time_neighbor;
}
struct link_entry *
get_link_set(void)
{
return link_set;
}
void
olsr_init_link_set(void)
{
/* Timers */
hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;
olsr_register_timeout_function(&olsr_time_out_link_set, OLSR_TRUE);
if(olsr_cnf->use_hysteresis)
{
olsr_register_timeout_function(&olsr_time_out_hysteresis, OLSR_TRUE);
}
if (olsr_cnf->lq_level > 0)
{
olsr_register_timeout_function(&olsr_time_out_packet_loss, OLSR_TRUE);
}
}
/**
* Get the status of a link. The status is based upon different
* timeouts in the link entry.
*
*@param remote address of the remote interface
*
*@return the link status of the link
*/
int
lookup_link_status(const struct link_entry *entry)
{
if(entry == NULL || link_set == NULL)
return UNSPEC_LINK;
/*
* Hysteresis
*/
if(olsr_cnf->use_hysteresis)
{
/*
if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK.
*/
if(!TIMED_OUT(entry->L_LOST_LINK_time))
return LOST_LINK;
/*
otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "true", the link SHOULD NOT be advertised at all;
*/
if(entry->L_link_pending == 1)
{
#ifdef DEBUG
OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&entry->neighbor_iface_addr));
#endif
return HIDE_LINK;
}
/*
otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "false", the link is advertised as described
previously in section 6.
*/
}
if(!TIMED_OUT(entry->SYM_time))
return SYM_LINK;
if(!TIMED_OUT(entry->ASYM_time))
return ASYM_LINK;
return LOST_LINK;
}
/**
*Find the "best" link status to a
*neighbor
*
*@param address the address to check for
*
*@return SYM_LINK if a symmetric link exists 0 if not
*/
static int
get_neighbor_status(const union olsr_ip_addr *address)
{
const union olsr_ip_addr *main_addr;
struct interface *ifs;
//printf("GET_NEIGHBOR_STATUS\n");
/* Find main address */
if(!(main_addr = mid_lookup_main_addr(address)))
main_addr = address;
//printf("\tmain: %s\n", olsr_ip_to_string(main_addr));
/* Loop trough local interfaces to check all possebilities */
for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
{
struct mid_address *aliases;
struct link_entry *lnk = lookup_link_entry(main_addr, NULL, ifs);
//printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
//printf("%s : ", olsr_ip_to_string(main_addr));
if(lnk != NULL)
{
//printf("%d\n", lookup_link_status(link));
if(lookup_link_status(lnk) == SYM_LINK)
return SYM_LINK;
}
/* Get aliases */
for(aliases = mid_lookup_aliases(main_addr);
aliases != NULL;
aliases = aliases->next_alias)
{
//printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
//printf("%s : ", olsr_ip_to_string(&aliases->address));
lnk = lookup_link_entry(&aliases->alias, NULL, ifs);
if(lnk != NULL)
{
//printf("%d\n", lookup_link_status(link));
if(lookup_link_status(lnk) == SYM_LINK)
return SYM_LINK;
}
}
}
return 0;
}
/**
* Find best link to a neighbor
*/
struct link_entry *
get_best_link_to_neighbor(const union olsr_ip_addr *remote)
{
const union olsr_ip_addr *main_addr;
struct link_entry *walker, *good_link, *backup_link;
int curr_metric = MAX_IF_METRIC;
float curr_lq = -1.0;
// main address lookup
main_addr = mid_lookup_main_addr(remote);
// "remote" *already is* the main address
if (main_addr == NULL)
main_addr = remote;
// we haven't selected any links, yet
good_link = NULL;
backup_link = NULL;
// loop through all links that we have
for (walker = link_set; walker != NULL; walker = walker->next)
{
// if this is not a link to the neighour in question, skip
if (!COMP_IP(&walker->neighbor->neighbor_main_addr, main_addr))
continue;
// handle the non-LQ, RFC-compliant case
if (olsr_cnf->lq_level == 0)
{
struct interface *tmp_if;
// find the interface for the link - we select the link with the
// best local interface metric
tmp_if = walker->if_name ? if_ifwithname(walker->if_name) :
if_ifwithaddr(&walker->local_iface_addr);
if(!tmp_if)
continue;
// is this interface better than anything we had before?
if ((tmp_if->int_metric < curr_metric) ||
// use the requested remote interface address as a tie-breaker
((tmp_if->int_metric == curr_metric) &&
COMP_IP(&walker->local_iface_addr, remote)))
{
// memorize the interface's metric
curr_metric = tmp_if->int_metric;
// prefer symmetric links over asymmetric links
if (lookup_link_status(walker) == SYM_LINK)
good_link = walker;
else
backup_link = walker;
}
}
// handle the LQ, non-RFC compliant case
else
{
float tmp_lq;
// calculate the bi-directional link quality - we select the link
// with the best link quality
tmp_lq = walker->loss_link_quality * walker->neigh_link_quality;
// is this link better than anything we had before?
if((tmp_lq > curr_lq) ||
// use the requested remote interface address as a tie-breaker
((tmp_lq == curr_lq) && COMP_IP(&walker->local_iface_addr, remote)))
{
// memorize the link quality
curr_lq = tmp_lq;
// prefer symmetric links over asymmetric links
if(lookup_link_status(walker) == SYM_LINK)
good_link = walker;
else
backup_link = walker;
}
}
}
// if we haven't found any symmetric links, try to return an
// asymmetric link
return good_link ? good_link : backup_link;
}
static void set_loss_link_multiplier(struct link_entry *entry)
{
struct interface *inter;
struct olsr_if *cfg_inter;
struct olsr_lq_mult *mult;
float val = -1.0;
union olsr_ip_addr null_addr;
// find the interface for the link
inter = if_ifwithaddr(&entry->local_iface_addr);
// find the interface configuration for the interface
for (cfg_inter = olsr_cnf->interfaces; cfg_inter != NULL;
cfg_inter = cfg_inter->next)
if (cfg_inter->interf == inter)
break;
// create a null address for comparison
memset(&null_addr, 0, sizeof (union olsr_ip_addr));
// loop through the multiplier entries
for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next)
{
// use the default multiplier only if there isn't any entry that
// has a matching IP address
if ((COMP_IP(&mult->addr, &null_addr) && val < 0.0) ||
COMP_IP(&mult->addr, &entry->neighbor_iface_addr))
val = mult->val;
}
// if we have not found an entry, then use the default multiplier
if (val < 0)
val = 1.0;
// store the multiplier
entry->loss_link_multiplier = val;
}
/**
*Delete all interface link entries
*
*@param interface ip address
*/
void
del_if_link_entries(const union olsr_ip_addr *int_addr)
{
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(COMP_IP(int_addr, &tmp_link_set->local_iface_addr))
{
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);
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);
tmp_link_set = link_set;
continue;
}
}
last_link_entry = tmp_link_set;
tmp_link_set = tmp_link_set->next;
}
return;
}
/**
*Nothing mysterious here.
*Adding a new link entry to the link set.
*
*@param local the local IP address
*@param remote the remote IP address
*@param remote_main the remote nodes main address
*@param vtime the validity time of the entry
*@param htime the HELLO interval of the remote node
*@param local_if the local interface
*/
static struct link_entry *
add_link_entry(const union olsr_ip_addr *local,
const union olsr_ip_addr *remote,
const union olsr_ip_addr *remote_main,
double vtime,
double htime,
const struct interface *local_if)
{
struct link_entry *new_link;
struct neighbor_entry *neighbor;
struct link_entry *tmp_link_set = lookup_link_entry(remote, remote_main, local_if);
if (tmp_link_set) {
return tmp_link_set;
}
/*
* if there exists no link tuple with
* L_neighbor_iface_addr == Source Address
*/
#ifdef DEBUG
OLSR_PRINTF(1, "Adding %s=>%s to link set\n", olsr_ip_to_string(local), olsr_ip_to_string(remote));
#endif
/* a new tuple is created with... */
new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");
memset(new_link, 0 , sizeof(struct link_entry));
/* copy if_name, if it is defined */
if (local_if->int_name)
{
new_link->if_name = olsr_malloc(strlen(local_if->int_name)+1, "target of if_name in new link entry");
strcpy(new_link->if_name, local_if->int_name);
} else
new_link->if_name = NULL;
/*
* L_local_iface_addr = Address of the interface
* which received the HELLO message
*/
//printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
COPY_IP(&new_link->local_iface_addr, local);
/* L_neighbor_iface_addr = Source Address */
COPY_IP(&new_link->neighbor_iface_addr, remote);
/* L_SYM_time = current time - 1 (expired) */
new_link->SYM_time = now_times - 1;
/* L_time = current time + validity time */
new_link->time = GET_TIMESTAMP(vtime*1000);
new_link->prev_status = ASYM_LINK;
/* HYSTERESIS */
if(olsr_cnf->use_hysteresis)
{
new_link->L_link_pending = 1;
new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
new_link->last_htime = htime;
new_link->olsr_seqno = 0;
new_link->olsr_seqno_valid = OLSR_FALSE;
}
new_link->L_link_quality = 0.0;
if (olsr_cnf->lq_level > 0)
{
new_link->loss_hello_int = htime;
new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);
new_link->loss_seqno = 0;
new_link->loss_seqno_valid = 0;
new_link->loss_missed_hellos = 0;
new_link->lost_packets = 0;
new_link->total_packets = 0;
new_link->loss_index = 0;
memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));
set_loss_link_multiplier(new_link);
}
new_link->loss_link_quality = 0.0;
new_link->neigh_link_quality = 0.0;
new_link->loss_link_quality2 = 0.0;
new_link->neigh_link_quality2 = 0.0;
new_link->saved_loss_link_quality = 0.0;
new_link->saved_neigh_link_quality = 0.0;
/* Add to queue */
new_link->next = link_set;
link_set = new_link;
/*
* Create the neighbor entry
*/
/* Neighbor MUST exist! */
if(NULL == (neighbor = olsr_lookup_neighbor_table(remote_main)))
{
neighbor = olsr_insert_neighbor_table(remote_main);
#ifdef DEBUG
OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(remote_main));
#endif
}
/* Copy the main address - make sure this is done every time
* as neighbors might change main address */
/* Erik Tromp - OOPS! Don't do this! Neighbor entries are hashed through their
* neighbor_main_addr field, and when that field is changed, their position
* in the hash table is no longer correct, so that the function
* olsr_lookup_neighbor_table() can no longer find the neighbor
* entry. */
/*COPY_IP(&neighbor->neighbor_main_addr, remote_main);*/
neighbor->linkcount++;
new_link->neighbor = neighbor;
if(!COMP_IP(remote, remote_main))
{
/* Add MID alias if not already registered */
/* This is kind of sketchy... and not specified
* in the RFC. We can only guess a vtime.
* 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;
}
}
syntax highlighted by Code2HTML, v. 0.9.1