/****************************************************************************
* Pathneck: locating network path bottlenecks
* Copyright (C) 2004
* Ningning Hu and the Carnegie Mellon University
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License (in the COPYING file) for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
****************************************************************************/
/* Copied from get-choke.c, used by pathneck.c for on-line processing
* to get the choke points */
#include <stdio.h>
#include <stdlib.h>
#ifdef SUN
#include <strings.h>
#else
#include <string.h>
#endif
#include "choke.h"
#include "pathneck.h"
#include "util.h"
struct node_t in_node[MAX_PATH]; /* the original reading */
struct node_t node[MAX_PATH]; /* used for processing, by discarding
the unuseless elements from in_node */
int in_path_len = 0;
int path_len = 0;
char * selected[MAX_PATH];
double conf[MAX_SEG_NUM];
double conf_gap[MAX_SEG_NUM];
int choke_gap[MAX_SEG_NUM];
int num_choke = 0;
/* out is a sorted index for the values in "in" */
void sort(double *in, int *out, int len)
{
int i, j;
int tmp[MAX_PATH];
double max;
int maxi;
for (i=0; i<len; i++)
tmp[i] = in[i];
for (i=0; i<len; i++) {
max = -1;
for (j=0; j<len; j++) {
if (tmp[j] >= 0 && tmp[j] > max) {
maxi = j;
max = tmp[j];
}
}
out[i] = maxi;
tmp[maxi] = -1;
}
}
int sanity_check()
{
int sg[MAX_PATH];
double gap[MAX_PATH];
int i, j, k;
int mean_gap;
if (in_path_len < 4)
return 0;
path_len = in_path_len;
for (i=0; i<path_len; i++) {
node[i].gap = in_node[i].gap;
node[i].rtt = in_node[i].rtt;
strcpy(node[i].as, in_node[i].as);
strcpy(node[i].hostname, in_node[i].hostname);
strcpy(node[i].ip_str, in_node[i].ip_str);
node[i].index = i;
node[i].gap1 = 0;
}
/* detect routing loops */
i = 1;
while (i < path_len) {
j = 0;
while (j < i) {
if (strcmp(node[i].hostname, node[j].hostname) == 0) {
/* remove this one */
for (k=i+1; k<path_len; k++)
memcpy((void *)&node[k-1], (void *)&node[k],
sizeof(struct node_t));
path_len --;
i --;
break;
}
j ++;
}
i ++;
}
/* remove 0 gaps */
k = 0;
for (i=0; i<path_len; i++) {
if (node[i].gap < 1) {
k ++;
continue;
}
if (k)
memcpy((void *)&node[i-k], (void *)&node[i],
sizeof(struct node_t));
}
path_len -= k;
if (path_len < 4)
return 0;
for (i=0; i<path_len; i++)
gap[i] = (double)node[i].gap;
sort(gap, sg, path_len);
i = sg[(int) path_len/2];
mean_gap = node[i].gap;
/* deal with the first few small gaps */
node[0].gap1 = node[0].gap;
i = 0;
while (i<path_len && node[i].gap < mean_gap/5)
i ++;
if (i >= path_len) return 0;
for (j=0; j<i; j++)
node[j].gap1 = node[i].gap;
/* deal with the middle gaps */
for (k=1; k<path_len-1; k++) {
if (node[k].gap < mean_gap/5) {
node[k].gap1 = node[k-1].gap1;
} else if (node[k].gap > node[k-1].gap1 &&
node[k].gap > node[k+1].gap) {
node[k].gap1 = (node[k-1].gap1 > node[k+1].gap) ?
node[k-1].gap1 : node[k+1].gap;
} else if (node[k].gap < node[k-1].gap1 &&
node[k].gap < node[k+1].gap) {
node[k].gap1 = (node[k-1].gap1 < node[k+1].gap) ?
node[k-1].gap1 : node[k+1].gap;
} else {
node[k].gap1 = node[k].gap;
}
}
k = path_len - 1;
if (node[k].gap < mean_gap / 5) {
node[k].gap1 = node[k-1].gap1;
} else {
node[k].gap1 = node[k].gap;
}
#if DEBUG
for (k=0; k<path_len; k++)
printf("%6.3f %5d %5d %s\n",
node[k].rtt,
node[k].gap,
node[k].gap1,
node[k].hostname);
#endif
return 1;
}
/* calculate the segment distance for [si, ei], return the average and
* distance sum for this segment */
void init_segment(int si, int ei, struct rec_t * rec)
{
int j;
double sum, cur_avg;
cur_avg = 0;
for (j=si; j<=ei; j++)
cur_avg += node[j].gap1;
cur_avg /= (ei-si+1);
sum = 0;
for (j=si; j<=ei; j++)
sum += abs(node[j].gap1 - cur_avg);
rec->opt = sum;
rec->ls = cur_avg;
rec->fs = cur_avg;
}
void bit_merge(char * in1, int k, char * in2, char * dst)
{
int i;
for (i=0; i<MAX_PATH; i++) {
dst[i] = in1[i] | in2[i];
if (k >= 0 && k < 8)
dst[i] |= (0x1 << k);
k -= 8;
}
}
void segment_all()
{
struct rec_t rec[MAX_PATH][MAX_PATH][MAX_PATH];
int i, j, l, k, m, i1, i2;
char * map, mask;
double diff[MAX_PATH];
int sd[MAX_PATH];
int diff_len, index, pos[MAX_PATH];
/* initialization */
bzero((void *)&rec,
sizeof(struct rec_t) * MAX_PATH * MAX_PATH * MAX_PATH);
for (i=0; i<path_len; i++)
for (j=i; j<path_len; j++)
init_segment(i, j, &rec[i][j][0]);
/* the dynamic algorithm */
for (l=1; l<path_len; l++) {
for (i=0; i<path_len; i++) {
for (j=i; j<path_len; j++) {
rec[i][j][l] = rec[i][j][l-1];
for (m=0; m<l; m++) {
for (k=i; k<j; k++) {
#if DEBUG
printf("%d %d %d %d | %.2f %.2f | %.3f %.3f %.3f\n",
i, j, k, l,
rec[i][k][m].ls, rec[k+1][j][l-m-1].fs,
rec[i][k][m].opt, rec[k+1][j][l-m-1].opt,
rec[i][j][l].opt);
#endif
if (abs(rec[i][k][m].ls - rec[k+1][j][l-m-1].fs) > GAP_THRESHOLD
&& rec[i][k][m].opt + rec[k+1][j][l-m-1].opt < rec[i][j][l].opt) {
/* add in one more split point for "k" */
rec[i][j][l].opt = rec[i][k][m].opt + rec[k+1][j][l-m-1].opt;
bit_merge(rec[i][k][m].sp, k, rec[k+1][j][l-m-1].sp, rec[i][j][l].sp);
rec[i][j][l].ls = rec[k+1][j][l-m-1].ls;
rec[i][j][l].fs = rec[i][k][m].fs;
}
}
}
}
// sleep(1);
}
}
/* now all the splitting points are in SP[0][path_len-1][path_len-1] */
/* calculate the gap differences at the splitting points */
diff_len = 0;
index = 0;
map = rec[0][path_len-1][path_len-1].sp;
for (i=0; i<PATH_MAP_LEN; i++) {
mask = 0x1;
for (j=0; j<8; j++) {
if (map[i] & mask) {
diff[diff_len] =
abs(rec[index+1][path_len-1][path_len-1].fs -
rec[0][index][path_len-1].ls);
pos[diff_len] = index+1;
diff_len ++;
}
index ++;
mask = mask << 1;
}
}
/* if there is no splitting point */
if (!diff_len) {
selected[0] = (char *)malloc(10);
sprintf(selected[0], "[1]");
return;
}
/* here it is */
sort(diff, sd, diff_len);
/* the last 3 diff are: * diff[sd[0]], diff[sd[1]], diff[sd[2]] */
l = (diff_len < 3) ? diff_len : 3;
for (k=0; k<l; k++) {
i1 = pos[sd[k]];
i2 = sd[k] + 1;
if ((i1 == path_len-1) ||
((sd[k]+1 < diff_len &&
pos[sd[k]+1] - i1 == 1 &&
(sd[k]+1 == sd[0] ||
sd[k]+1 == sd[1] ||
sd[k]+1 == sd[2])))) {
selected[i1] = (char *)malloc(10);
sprintf(selected[i1], "(%d)", k+1);
} else {
selected[i1] = (char *)malloc(10);
sprintf(selected[i1], "[%d]", k+1);
}
}
}
void dump(int real_dump)
{
int i, j, conf_i;
char num_str[2];
j = 0;
for (i=0; i<in_path_len; i++) {
if (i == node[j].index) {
if (real_dump)
printf("%-5d %-5d ", in_node[i].gap, node[j].gap1);
if (j==0)
/* first hop is always considered as an upper bound */
node[j].bw_flag = 1;
else
/* assume this is not a choke point yet, most of hops are
* lower bounds */
node[j].bw_flag = -1;
/* the choke nodes */
if (selected[j] != NULL) {
if (real_dump)
printf("%s ", selected[j]);
choke_gap[num_choke] = node[j].gap1;
num_choke ++;
num_str[0] = selected[j][1];
num_str[1] = 0;
conf_i = atoi(num_str) - 1;
if (j==0) {
conf[conf_i] = 1;
conf_gap[conf_i] = 1;
} else {
conf[conf_i] = abs(1/(double)node[j-1].gap1 - 1/(double)node[j].gap1) / (1/(double)node[j-1].gap1);
conf_gap[conf_i] = abs((double)node[j-1].gap1 - (double)node[j].gap1) / (double)node[j-1].gap1;
if (node[j].gap1 < node[j-1].gap1)
node[j].bw_flag = 0;
else
node[j].bw_flag = 1; /* upper bound */
}
}
else
if (real_dump)
printf(" ");
} else {
if (real_dump)
printf("%-5d %-5d ", in_node[i].gap, in_node[i].gap1);
}
if (real_dump)
printf("%7.3f %-15s %6s %s\n",
in_node[i].rtt, in_node[i].ip_str,
in_node[i].as, in_node[i].hostname);
if (i == node[j].index && j < path_len-1)
j++;
}
/* out the confidence line */
if (real_dump) {
printf("conf = ");
for (i=0; i<num_choke; i++) {
printf("%.3f ", conf[i]);
}
printf("\n\n");
}
}
void clean_choke_data()
{
memset(in_node, 0, sizeof(struct node_t) * MAX_PATH);
memset(node, 0, sizeof(struct node_t) * MAX_PATH);
in_path_len = 0;
path_len = 0;
memset(selected, 0, sizeof(char *) * MAX_PATH);
memset(conf, 0, sizeof(double) * MAX_SEG_NUM);
memset(conf_gap, 0, sizeof(double) * MAX_SEG_NUM);
memset(choke_gap, 0, sizeof(int) * MAX_SEG_NUM);
num_choke = 0;
}
void get_choke()
{
int i;
clean_choke_data();
for (i=0; i<=ip_path_len; i++) {
in_node[i].rtt = 0;
in_node[i].gap = (int)(ip_path[i].avg_gap * 1000000);
in_node[i].ip_str[0] = 0;
in_node[i].as[0] = 0;
strcpy(in_node[i].hostname, ip2str(ip_path[i].ip));
in_node[i].gap1 = 0;
}
in_path_len = ip_path_len + 1;
if (sanity_check())
segment_all();
dump(0);
}
syntax highlighted by Code2HTML, v. 0.9.1