linkstats_util.c from EmStar at Krugle
Show linkstats_util.c syntax highlighted
/*
*
* Copyright (c) 2003 The Regents of the University of California. 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.
*
* - Neither the name of the University 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 REGENTS 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 REGENTS 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.
*
*/
/*
* linkstats_util.c: Some utilities for linkstats, e.g. updating the
* statistical information on a neighbor.
*
* $Id: linkstats_util.c,v 1.8 2004/07/20 00:18:45 fabio Exp $
*/
char linkstats_util_c_cvsid[] = "$Id: linkstats_util.c,v 1.8 2004/07/20 00:18:45 fabio Exp $";
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "link/link.h"
#include "linkstats_i.h"
/**** Calculating the connectivity estimation ****/
/*
* The strategy for calculating the connectivity estimation is as
* follows.
*
* We first calculate a connectivity rate using the following procedure.
* We keep an array of recent packets per neighbor. This array contains
* all packets recieved and the packet lost. We detect packet losses by
* using sequence numbers. Whenever a packet arrives, all the packet
* lost (if any) and the new packet are added to the head of the array,
* and the others slide down.
*
* We also keep two pointers into this array: the total number of
* entries in the array, and the number of "recent" entries in the
* array. Each time a packet arrives, both of these counters are
* incremented by the total number of packet lost (if any) and the new
* packet. So, the array looks like this:
-------------------------------------------------------------------
| | | | | | | | | | | | | | | | | | | | | | |
-------------------------------------------------------------------
^most recent entry ^ ^ num_heard (oldest entry)
|num_heard_recently
* Using this array, we calculate the connectivity rate by dividing the
* total number of packets received by the total number of entries.
* This calculation is done whenever we fill the max array size, or
* periodically every 30 seconds (whatever comes first).
*
* Aging packets out in the array is simple: periodically (every 30
* seconds), num_entries is set back to num_recent_entries, and
* num_recent_entires is set back to 0. This is computationally
* cheap, and guarantees that a packet will be kept in the array for at
* least 30 seconds and at most 60 seconds.
*
* Finally, we calculate the final connectivity estimation, by
* performing an Exponential Weighted Moving Average (EWMA) on the
* connectivity rate calculated above. The formula used is:
*
* EWMAnew(conn) = alpha*conn_rate + (1 - alpha)*EWMAprev(conn)
*
* -Al
*/
#define LINKSTATE_TIMEOUT_PERIOD 30 /* see above :-) */
/*******************************************************************/
/* calculate the connectivity value of the neighbor packet array */
conn_t get_connectivity(neighbor_el_t *ne)
{
int i, pkts_recv = 0;
/* if no entires, we assume zero connectivity */
if (!ne->num_entries)
return 0.0;
for (i = 0; i < ne->num_entries; i++)
if (ne->array_pkts[i] == RECEIVED)
pkts_recv++;
return (100.0 * ((conn_t) pkts_recv)/((conn_t) ne->num_entries));
}
/*
* Log the connectivity info, update the connectivity estimate of
* this neighbor and clear out the queue of recent packets
*/
void update_estimate(neighbor_list_t *nl, neighbor_el_t *ne)
{
/* log info for this neighbor if necessary */
if ((nl->log) && (nl->fp != NULL)) {
fprintf(nl->fp, "%f\n", get_connectivity(ne));
fflush(nl->fp);
}
/* recalculate connectivity estimate (this is equivalent to the
* formula written above) */
ne->info.conn_in +=
nl->alpha * (get_connectivity(ne) - ne->info.conn_in);
elog(LOG_DEBUG(1), "Conn value for neighbor [%s] is: %.5f",
print_if_id(ne->info.if_id), ne->info.conn_in);
/* age out the packets in the history array */
elog(LOG_DEBUG(4), "aging out %d packets (%d remain) for neighbor %s",
ne->num_entries - ne->num_recent_entries,
ne->num_recent_entries, print_if_id(ne->info.if_id));
ne->num_entries = ne->num_recent_entries;
ne->num_recent_entries = 0;
}
/*
* Periodically clear out our queue of recently seen packets and
* recalculate the connectivity estimate. In addition,
*/
static gboolean periodic_update(void *data, int interval,
g_event_t *event)
{
neighbor_list_t *nl = (neighbor_list_t *) data;
neighbor_el_t *ne;
//struct timeval tv;
/* print timestamp in the log file if necessary */
if ((nl->log) && (nl->fp != NULL)) {
//gettimeofday(&tv, NULL);
nl->tick += LINKSTATE_TIMEOUT_PERIOD;
fprintf(nl->fp, "%d ", nl->tick);
fflush(nl->fp);
//fprintf(nl->fp, "%d %s\n", nl->tick, misc_tv_to_str(&tv));
}
for (ne = neighbor_list_top(nl) ; ne; ne = neighbor_list_next(ne))
update_estimate(nl, ne);
/* print separator line in the log file if necessary */
if ((nl->log) && (nl->fp != NULL) && (neighbor_list_empty(nl))) {
fprintf(nl->fp, "0.00\n");
fflush(nl->fp);
}
return TIMER_RENEW;
}
/* Get the neighbor from the neighbor queue */
static neighbor_el_t * get_neighbor(neighbor_list_t *nl,
const link_pkt_t *lpkt,
linkstats_pkt_t *spkt)
{
neighbor_el_t *ne;
/* first see if this neighbor already exists */
for (ne = neighbor_list_top(nl); ne; ne = neighbor_list_next(ne))
if (ne->info.if_id == lpkt->src.id)
return ne;
/* not found - create a new neighbor */
if ((ne = malloc(sizeof(neighbor_el_t))) == NULL) {
elog(LOG_CRIT, "cannot allocate memory for neighbor elem: %m");
return NULL;
}
memset(ne, 0, sizeof(neighbor_el_t));
/* initialize neighbor element fields */
ne->info.if_id = lpkt->src.id;
/* set the initial connectivity */
ne->info.conn_in = INIT_EWMA;
/* init to (seqno - 1) so only 1 recv pkt gets added to the array */
ne->last_seqno_heard = spkt->seqno - 1;
/* add the new neighbor to the queue */
neighbor_list_push(nl, ne);
return ne;
}
/* clear the neighbor entry */
void clear_neighbor(neighbor_el_t *ne)
{
ne->info.conn_in = INIT_EWMA;
ne->info.last_heard.tv_sec = 0;
ne->info.last_heard.tv_usec = 0;
ne->last_seqno_heard = 0;
ne->status_conn = 0;
ne->num_entries = 0;
ne->num_recent_entries = 0;
}
/*
* Update the link statistics for this neighbor.
*/
void update_stats(neighbor_list_t *nl, const link_pkt_t *lpkt,
linkstats_pkt_t *spkt)
{
neighbor_el_t *ne;
int num_pkts, i;
struct timeval now;
elog(LOG_DEBUG(0), "updating stats for neighbor: %d, with seqno: "
"%llu", spkt->src_id, spkt->seqno);
/* Find out if neighbor exist in our list */
if ((ne = get_neighbor(nl, lpkt, spkt)) == NULL)
return;
/* find out how many packet we need to add */
num_pkts = (int) (spkt->seqno - ne->last_seqno_heard);
/* if the difference is negative (neighbor reboot?) or too large (huge
* losses), we clear the array and start again */
if ((num_pkts < 0) || (num_pkts >= MAX_PKTS)) {
elog(LOG_NOTICE, "Possible neighbor reboot or huge losses, clearing"
"stats array and restarting...");
clear_neighbor(ne);
num_pkts = 1;
goto addone;
}
/* if we receive a packet with the same seqno, we ignore it */
if (num_pkts == 0) {
elog(LOG_WARNING, "Received duplicate seqno: %llu from neighbor "
"[%d], alas ignoring it...", spkt->seqno, spkt->src_id);
return;
}
/* verify we won't exceed the array size */
while ((ne->num_entries + num_pkts) >= MAX_PKTS)
/* update estimate for this neighbor NOW */
update_estimate(nl, ne);
/* put the new packet(s) at the front of the array... slide everything
* else down by num_pkts */
memmove(&(ne->array_pkts[num_pkts]), &(ne->array_pkts[0]),
sizeof(pkt_t) * ne->num_entries);
/* add all the losses if any */
for (i = 1; i < num_pkts; i++)
ne->array_pkts[i] = LOSS;
addone:
/* add the packet just recieved */
ne->array_pkts[0] = RECEIVED;
/* remember how many entries are in the array */
ne->num_entries += num_pkts;
ne->num_recent_entries += num_pkts;
/* update the seqno */
ne->last_seqno_heard = spkt->seqno;
/* update the time */
/* NOTE: we should use lpkt->rcv_time, but it is not set!! **FIX** */
gettimeofday(&now, NULL);
ne->info.last_heard = now;
}
void linkstats_util_init(neighbor_list_t *nl)
{
char filename[1024];
struct timeval tv;
time_t time;
/* open log file if necessary */
if (nl->log == TRUE) {
/* open (truncate if exists) connectivity info file */
memset(filename, 0, 1024);
sprintf(filename, "%s-%d", LOG_FILENAME, my_node_id);
if ((nl->fp = fopen(filename, "a+")) == NULL) {
elog(LOG_WARNING, "Error opening %s: %m", filename);
exit(1);
} else {
/* print experiment header */
fprintf(nl->fp, "\n\n\n******************************************"
"******************\n");
fprintf(nl->fp, "NEW EXPERIMENT\n");
gettimeofday(&tv, NULL);
time = tv.tv_sec;
fprintf(nl->fp, "DATE: %s", asctime(localtime(&time)));
fprintf(nl->fp, "************************************************"
"************\n\n");
fflush(nl->fp);
}
}
g_timer_add(LINKSTATE_TIMEOUT_PERIOD * 1000, periodic_update, nl,
NULL, NULL);
}
See more files for this project here