neo-ptr-client.c

/*
 * Copyright (c) 2006
 * Ningning Hu and the Carnegie Mellon University.
 * All rights reserved. 
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 * 3. The name of the author(s) may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission.  
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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.
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/param.h>
#include <sys/socket.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <sys/time.h>
#include <pthread.h>

#include "setsignal.h"
#include "common.h"

#define PhaseSleep (0)
#define ABS(a) (((a) < 0) ? -(a) : (a))

extern char *optarg;
extern int optind, opterr, optopt;

char version[] = "2.1";

int delay_num = 0;
int packet_size = PacketSize;
int phase_num = 3;
int probe_num = ProbeNum;
FILE *trace_fp = NULL;
int verbose = 0;
int debug = 0;

double b_bw = 0, competing_bw, PTR_bw, a_bw, c_bw[MaxRepeat];
int probing_phase_count = 0;
double probing_start_time = 0, probing_end_time = 0;

uint16 dst_port = START_PORT, src_port = 0, probing_port;
uint32 dst_ip, src_ip;
char dst_hostname[MAXHOSTNAMELEN], src_hostname[MAXHOSTNAMELEN];
char dst_ip_str[16], src_ip_str[16];
char dst[MAXHOSTNAMELEN], src[MAXHOSTNAMELEN];
int control_sock, probing_sock;
struct sockaddr_in probing_server, probing_server2;

RETSIGTYPE (*oldhandler)
(int);

double src_gap_sum = 0; // entry value
double avg_src_gap;		// entry value
struct pkt_rcd_t dst_gap[MaxProbeNum];
double dst_gap_sum;
double avg_dst_gap;
int dst_gap_count, src_gap_count;
int total_count;
double send_times[MaxProbeNum];
double tlt_src_gap, tlt_dst_gap;

/* keep the data from dst machine, 128 is for other control string */
char msg_buf[sizeof(struct pkt_rcd_t) * MaxProbeNum + 128];
int msg_len;

/* trace item: record the item used to dump out into trace file */
struct trace_item
{
	int probe_num, packet_size, delay_num;

	double send_times[MaxProbeNum];
	struct pkt_rcd_t rcv_record[MaxProbeNum];
	int record_count;

	double avg_src_gap;
	double avg_dst_gap;

	double b_bw, c_bw, a_bw, ptr;

	struct trace_item *next;
};
struct trace_item *trace_list = NULL;
struct trace_item *trace_tail = NULL;
struct trace_item *cur_trace = NULL;

/* usage message */
void Usage()
{
	printf("IGI/PTR-%s client usage:\n\n", version);
	printf("\tptr-client [-n probe_num] [-s packet_size] [-p dst_port]\n");
	printf("\t           [-k repeat_num] [-f trace_file] [-vdh] dst_address\n\n");
	printf("\t-n      set the number of probing packets in each train [60]\n");
	printf("\t-s      set the length of the probing packets in byte [500B]\n");
	printf("\t-p      indicate the dst machine's listening port [10241]\n");
	printf("\t        This is optional, it can itself search for the port\n");
	printf("\t        that the igi_server is using.\n");
	printf("\t-k      the number of train probed for each source gap [3]\n");
	printf("\t-f      dump packet-level trace into trace_file\n");
	printf("\t-v      verbose mode.\n");
	printf("\t-d      debug mode.\n");
	printf("\t-h      print this message.\n");
	printf("dst_address     can be either an IP address or a hostname\n\n");
	exit(1);
}

/* combine the sec & usec of record into a real number */
double get_rcd_time(struct pkt_rcd_t record)
{
	return (record.sec + (double)record.u_sec / 1000000);
}

/* dump out all the trace packet time stamps */
void dump_trace()
{
	struct trace_item *p;
	int i, index;

	if (trace_fp == NULL)
	{
		printf("-w not specified, no trace to dump\n");
		return;
	}

	/* first dump out the summary data */
	p = trace_list;
	index = 0;
	fprintf(trace_fp, "\n%%probe_num packet_size delay_num avg_src_gap arv_dst_gap b_bw c_bw a_bw ptr\n");
	fprintf(trace_fp, "summary_data = [\n");
	while (p != NULL)
	{
		index++;
		fprintf(trace_fp, "%2d %4d %5d %f %f %12.3f %12.3f %12.3f %12.3f\n",
				p->probe_num,
				p->packet_size,
				p->delay_num,
				p->avg_src_gap,
				p->avg_dst_gap,
				p->b_bw,
				p->c_bw,
				p->a_bw,
				p->ptr);
		p = p->next;
	}
	fprintf(trace_fp, "];\n");
	fprintf(trace_fp, "phase_num = %d; \n\n", index);

	/* then the detail packet trace */
	p = trace_list;
	index = 0;
	while (p != NULL)
	{
		index++;

		fprintf(trace_fp, "send_time_%d = [\n", index);
		for (i = 1; i < p->probe_num; i++)
		{
			/*fprintf(trace_fp, "%f %f %f ", 
			p->send_times[i-1], p->send_times[i], 
			p->send_times[i] - p->send_times[i-1]);*/
			fprintf(trace_fp, "%f ",
					p->send_times[i] - p->send_times[i - 1]);
		}
		fprintf(trace_fp, "];\n");
		fprintf(trace_fp, "send_array_size(%d) = %d; \n\n",
				index, p->probe_num - 1);

		fprintf(trace_fp, "recv_time_%d = [\n", index);

		for (i = 0; i < p->record_count - 1; i++)
		{
			/*fprintf(trace_fp, "%f %f %f %d ", 
			get_rcd_time(p->rcv_record[i]),
			get_rcd_time(p->rcv_record[i+1]),
			get_rcd_time(p->rcv_record[i+1]) - 
			get_rcd_time(p->rcv_record[i]),
			p->rcv_record[i+1].seq);*/
			fprintf(trace_fp, "%f %d ",
					get_rcd_time(p->rcv_record[i + 1]) -
						get_rcd_time(p->rcv_record[i]),
					p->rcv_record[i + 1].seq);
		}
		fprintf(trace_fp, "];\n");
		fprintf(trace_fp, "recv_array_size(%d) = %d; \n\n",
				index, p->record_count - 1);

		p = p->next;
	}
}

/* make a clean exit on interrupts */
RETSIGTYPE cleanup(int signo)
{
	if (trace_fp != NULL)
	{
		dump_trace();
		fclose(trace_fp);
	}

	close(probing_sock);
	close(control_sock);

	/* free trace list */
	if (trace_list != NULL)
	{
		struct trace_item *pre, *p;
		p = trace_list;

		while (p != NULL)
		{
			pre = p;
			p = p->next;
			free(pre);
		}
	}

	exit(0);
}

void quit()
{
	fflush(stdout);
	fflush(stderr);
	cleanup(1);
	exit(-1);
}

/* get the current time */
double get_time()
{
	struct timeval tv;
	struct timezone tz;
	double cur_time;

	if (gettimeofday(&tv, &tz) < 0)
	{
		perror("get_time() fails, exit\n");
		quit();
	}

	cur_time = (double)tv.tv_sec + ((double)tv.tv_usec / (double)1000000.0);
	return cur_time;
}

/* find the delay number which can set the src_gap exactly as "gap" */
int get_delay_num(double gap)
{
#define Scale (10)
	int lower, upper, mid;
	double s_time, e_time, tmp;
	int k;

	lower = 0;
	upper = 16;
	tmp = 133333;

	/* search for upper bound */
	s_time = e_time = 0;
	while (e_time - s_time < gap * Scale)
	{
		s_time = get_time();
		for (k = 0; k < upper * Scale; k++)
		{
			tmp = tmp * 7;
			tmp = tmp / 13;
		}
		e_time = get_time();

		upper *= 2;
	}

	/* binary search for delay_num */
	mid = (int)(upper + lower) / 2;
	while (upper - lower > 20)
	{
		s_time = get_time();
		for (k = 0; k < mid * Scale; k++)
		{
			tmp = tmp * 7;
			tmp = tmp / 13;
		}
		e_time = get_time();

		if (e_time - s_time > gap * Scale)
			upper = mid;
		else
			lower = mid;

		mid = (int)(upper + lower) / 2;
	}

	return mid;
}

void dump_bandwidth()
{
	printf("\nPTR: %7.3f Mpbs (suggested)\n", PTR_bw / 1000000);
	printf("IGI: %7.3f Mpbs\n", a_bw / 1000000);
	printf("Probing uses %.3f seconds, %d trains, ending at a gap value of %d us.\n", probing_end_time - probing_start_time,
		   probing_phase_count,
		   (int)(tlt_dst_gap * 1000000));

	if (trace_fp != NULL)
	{
		fprintf(trace_fp, "%%Bottleneck Bandwidth: %7.3f Mbps\n", b_bw / 1000000);
		fprintf(trace_fp, "%%Competing  Bandwidth: %7.3f Mpbs\n", competing_bw / 1000000);
		fprintf(trace_fp, "%%Packet Transmit Rate: %7.3f Mpbs\n", PTR_bw / 1000000);
		fprintf(trace_fp, "%%Available  Bandwidth: %7.3f Mpbs\n", a_bw / 1000000);
	}
}

int init_sockets(uint32 dst_ip)
{
	struct sockaddr_in client;

	probing_sock = socket(AF_INET, SOCK_DGRAM, 0);

	probing_server.sin_family = AF_INET;
	probing_server.sin_addr.s_addr = dst_ip;
	probing_server.sin_port = htons(probing_port);

	/* used for sending the tail "junk" packet */
	probing_server2.sin_family = AF_INET;
	probing_server2.sin_addr.s_addr = dst_ip;
	probing_server2.sin_port = htons(probing_port + 1);

	client.sin_addr.s_addr = htonl(INADDR_ANY);
	client.sin_family = AF_INET;
	client.sin_port = htons(0);

	if (bind(probing_sock, (const struct sockaddr *)&client,
			 sizeof(client)) < 0)
	{
		fprintf(stderr, "server: Unable to bind local address.\n");
		quit();
	}

#ifndef LINUX
	if (fcntl(probing_sock, F_SETFL, O_NDELAY) < 0)
	{
#else
	if (fcntl(probing_sock, F_SETFL, FNDELAY) < 0)
	{
#endif
		printf("fcntl fail \n");
		quit();
	}

	return 1;
}

/* any parameter can be NULL */
int get_host_info(char *string, char *name, uint32_t *ip, char *ip_str)
{
	struct hostent *hp;
	struct in_addr in_a;
	uint32_t tmp_ip;

#ifdef SUN
	if (inet_addr(string) == INADDR_BROADCAST)
	{
#else
	/* string is a hostname */
	if (inet_addr(string) == INADDR_NONE)
	{
#endif
		/* not interested in IP */
		if (!ip && !ip_str)
		{
			if (name)
				strcpy(name, string);
			return 0;
		}

		/* find hostname */
		if ((hp = gethostbyname(string)) == NULL)
		{
			printf("ERROR: couldn't obtain address for %s\n", string);
			return -1;
		}
		else
		{
			if (name)
				strncpy(name, hp->h_name, MAXHOSTNAMELEN - 1);
			if (ip)
				memcpy((void *)ip, (void *)hp->h_addr, hp->h_length);
			if (ip_str)
			{
				in_a.s_addr = *ip;
				strcpy(ip_str, inet_ntoa(in_a));
			}
		}
	}
	else
	{ /* string is an IP */

		/* not interested in name */
		if (ip_str)
			strcpy(ip_str, string);

		tmp_ip = inet_addr(string);
		if (ip)
			*ip = tmp_ip;

		if (name)
		{
			if ((hp = gethostbyaddr((char *)&tmp_ip, sizeof(tmp_ip), AF_INET)) == NULL)
				strncpy(name, string, MAXHOSTNAMELEN - 1);
			else
				strncpy(name, hp->h_name, MAXHOSTNAMELEN - 1);
		}
	}
	return 0;
}

/* the begining of the msg_buf should have the form $**$, return the string */
// TODO: simplify using index()
void get_item(int control_sock, char *str)
{
	int i, j, cur_len;

	/* check if two $ already exit */
	if (msg_len > 0)
	{
		if (msg_buf[0] != '$')
		{
			printf("get unknown msg, it will mess up everything, exit\n");
			quit();
		}
		i = 1;
		while ((i < msg_len) && (msg_buf[i] != '$'))
		{
			i++;
		}
		if (i < msg_len)
		{
			strncpy(str, msg_buf + 1, i - 1);
			str[i - 1] = 0;
			goto out;
		}
	}

	/* read until we get two $ */
	while (1)
	{
		if (debug)
		{
			printf("msg_len = %d  ", msg_len);
		}
		cur_len = read(control_sock, msg_buf + msg_len, sizeof(msg_buf) - msg_len);
		/* guard against control channel breaks */
		if (cur_len <= 0)
		{
			printf("read failed in get_item()\n");
			quit();
		}

		msg_len += cur_len;
		msg_buf[msg_len] = 0;

		i = 1;
		while ((i < msg_len) && (msg_buf[i] != '$'))
			i++;
		if (i < msg_len)
		{
			strncpy(str, msg_buf + 1, i - 1);
			str[i - 1] = 0;
			break;
		}
	}

out:
	/* get out the string and move the buf ahead, with i points
	 * to the 2nd $ */
	i++;
	for (j = i; j < msg_len; j++)
		msg_buf[j - i] = msg_buf[j];
	msg_len -= i;
}

void init_connection()
{
	struct sockaddr_in server, src_addr;
	int src_size, result, msg_len;
	char cur_str[16], msg_buf[64];

	/* Setup signal handler for cleaning up */
	(void)setsignal(SIGTERM, cleanup);
	(void)setsignal(SIGINT, cleanup);
	if ((oldhandler = setsignal(SIGHUP, cleanup)) != SIG_DFL)
		(void)setsignal(SIGHUP, oldhandler);

	/* Get hostname and IP address of target host */
	if (get_host_info(dst, dst_hostname, &dst_ip, dst_ip_str) < 0)
	{
		quit();
	}

	server.sin_addr.s_addr = dst_ip;
	server.sin_family = AF_INET;

	/* search for the right dst port to connect with */
	control_sock = socket(AF_INET, SOCK_STREAM, 0);
	server.sin_port = htons(dst_port);
	result = connect(control_sock, (struct sockaddr *)&server, sizeof(server));
	if (verbose)
			printf("dst_port = %d\n", dst_port);
	
	int cnt = 0;
	while ((result < 0))
	{
		close(control_sock);
		control_sock = socket(AF_INET, SOCK_STREAM, 0);
		result = connect(control_sock, (struct sockaddr *)&server, sizeof(server));
		if (verbose)
			printf("dst_port = %d\n", dst_port);
		
		++cnt;
		if (cnt > 100)
			break;
		
		sleep(1);
	};
	if (result < 0)
	{
		perror("connection fails\n");
		quit();
	}

	/* Get hostname and IP address of source host */

	src_size = sizeof(struct sockaddr);
	getsockname(control_sock, (struct sockaddr *)&src_addr, &src_size);
	strcpy(src, inet_ntoa(src_addr.sin_addr));

	if (get_host_info(src, src_hostname, &src_ip, src_ip_str) < 0)
	{
		printf("get source address info fails, exit\n");
		quit();
	}

	if (verbose)
	{
		printf("src addr: %s\n", src_ip_str);
		printf("dst addr: %s\n", dst_ip_str);
	}

	/* send START message */
	sprintf(msg_buf, "$START$%d$", probe_num);
	msg_len = strlen(msg_buf);
	write(control_sock, msg_buf, msg_len);

	/* wait for READY ack */
	get_item(control_sock, cur_str);
	if (verbose)
		printf("we get str: %s\n", cur_str);
	if (strncmp(cur_str, "READY", 5) != 0)
	{
		printf("get unknow str when waiting for READY from dst, exit\n");
		quit();
	}

	get_item(control_sock, cur_str);
	if (verbose)
		printf("probing_port = %s\n", cur_str);
	probing_port = atoi(cur_str);

	if (init_sockets(dst_ip) == 0)
	{
		perror("init sockets failed");
		quit();
	}
}

/* send out probe_num packets, each packet is packet_size bytes,   */
/* and the inital gap is set using delay_num                       */
void send_packets(int probe_num, int packet_size, int delay_num, double *sent_times)
{
	int i, k;
	double tmp = 133333.0003333;
	char send_buf[4096];

	/* send out probing packets */
	for (i = 0; i < probe_num - 1; i++)
	{
		/* TODO: the middle send_times are not useful any more, since
	     * we don't use sanity-check */
		sent_times[i] = get_time();
		send_buf[0] = i;
		sendto(probing_sock, send_buf, packet_size, 0, (struct sockaddr *)&(probing_server), sizeof(probing_server));

		/* gap generation */
		for (k = 0; k < delay_num; k++)
		{
			tmp = tmp * 7;
			tmp = tmp / 13;
		}
	}

	/* the last packets */
	send_buf[0] = i;
	sendto(probing_sock, send_buf, packet_size, 0, (struct sockaddr *)&(probing_server), sizeof(probing_server));

	sendto(probing_sock, send_buf, 40, 0, (struct sockaddr *)&(probing_server2), sizeof(probing_server2));
	sent_times[probe_num - 1] = get_time();
}

/* get dst gap_sum and gap_count from the records */
double get_dst_sum(struct pkt_rcd_t *rcv_record, int count, int *gap_count)
{
	double gap_sum, time1, time2;
	int i;

	gap_sum = 0;
	*gap_count = 0;
	for (i = 0; i < count - 1; i++)
	{
		/* only consider those gaps composed by two in-order packets */
		if (rcv_record[i + 1].seq - rcv_record[i].seq == 1)
		{
			time1 = get_rcd_time(rcv_record[i + 1]);
			time2 = get_rcd_time(rcv_record[i]);
			gap_sum += (time1 - time2);
			(*gap_count)++;
		}
	}

	return gap_sum;
}

/* get dst gap trace data through control channel 	*/
/* return 0 means fails in reading dst's data           */
int get_dst_gaps(struct pkt_rcd_t *rcv_record)
{
	int i, cur_len, data_size, total_count, ptr;
	char num_str[32];

	get_item(control_sock, num_str);
	data_size = atoi(num_str); // this depends on stdlib.h
	total_count = data_size / sizeof(struct pkt_rcd_t);
	if (verbose)
		printf("from dst: data_size = %d total_count = %d \n", data_size, total_count);

	/* get the data package */
	while (msg_len < data_size)
	{
		cur_len = read(control_sock, msg_buf + msg_len, sizeof(msg_buf) - msg_len);
		if (cur_len <= 0)
		{
			printf("read failed in get_dst_gaps()\n");
			quit();
		}
		msg_len += cur_len;
	}

	/* split out the record */
	ptr = 0;
	for (i = 0; i < total_count; i++)
	{
		memcpy((void *)&rcv_record[i], (const void *)(msg_buf + ptr), sizeof(struct pkt_rcd_t));

		rcv_record[i].sec = ntohl(rcv_record[i].sec);
		rcv_record[i].u_sec = ntohl(rcv_record[i].u_sec);
		rcv_record[i].seq = ntohl(rcv_record[i].seq);

		if (debug)
			printf("%d %d %d \n", rcv_record[i].sec, rcv_record[i].u_sec, rcv_record[i].seq);
		ptr += sizeof(struct pkt_rcd_t);
	}
	msg_len -= data_size;

	if (trace_fp != NULL)
	{
		memcpy(cur_trace->rcv_record, rcv_record, data_size);
		cur_trace->record_count = total_count;
	}

	return total_count;
}

/* here we use some a similar technique with nettimer, but the  */
/* implementation is much simpler 			        */
double get_bottleneck_bw(struct pkt_rcd_t *rcv_record, int count)
{
	double gaps[MaxProbeNum];
	int gap_count;

	struct bin_item
	{
		int value;
		int count;
	} bin[MaxProbeNum];
	int bin_count;

	double lower_time, upper_time;
	int max_index, max_count, max_value, cur_value, i, j;

	double gap_sum;
	int sum_count;

	// return 100000000;

	/* get valid dst gaps */
	gap_count = 0;
	for (i = 0; i < count - 1; i++)
	{
		if (rcv_record[i + 1].seq - rcv_record[i].seq == 1)
		{
			gaps[gap_count] = get_rcd_time(rcv_record[i + 1]) - get_rcd_time(rcv_record[i]);
			gap_count++;
		}
	}

	/* use 25us bins to go through all the gaps */
	bin_count = 0;
	for (i = 0; i < gap_count; i++)
	{
		cur_value = (int)(gaps[i] / BinWidth);
		j = 0;
		while ((j < bin_count) && (cur_value != bin[j].value))
		{
			j++;
		}
		if (j == bin_count)
		{
			bin[bin_count].value = cur_value;
			bin[bin_count].count = 1;
			bin_count++;
		}
		else
		{
			bin[j].count++;
		}
	}

	/* find out the biggest bin */
	max_index = 0;
	max_count = bin[0].count;
	for (i = 1; i < bin_count; i++)
	{
		if (bin[i].count > max_count)
		{
			max_count = bin[i].count;
			max_index = i;
		}
	}
	max_value = bin[max_index].value;
	lower_time = max_value * BinWidth;
	upper_time = (max_value + 1) * BinWidth;

	/* see whether the adjacent two bins also have some items */
	for (i = 0; i < bin_count; i++)
	{
		if (bin[i].value == max_value + 1)
			upper_time += BinWidth;
		if (bin[i].value == max_value - 1)
			lower_time -= BinWidth;
	}

	if (debug)
	{
		printf("get_bottleneck_bw: %f %f \n", lower_time, upper_time);
	}

	/* average them */
	gap_sum = 0;
	sum_count = 0;
	for (i = 0; i < gap_count; i++)
	{
		if ((gaps[i] >= lower_time) && (gaps[i] <= upper_time))
		{
			gap_sum += gaps[i];
			sum_count++;
		}
	}

	return (packet_size * 8 / (gap_sum / sum_count));
}

/* calculate the competing traffic rate using IGO method */
double get_competing_bw(struct pkt_rcd_t *rcv_record, double avg_src_gap, int count, double b_bw)
{
	double b_gap, cur_gap, m_gap;
	double gap_sum, inc_gap_sum;
	int i;

	b_gap = packet_size * 8 / b_bw;
	m_gap = MAX(b_gap, avg_src_gap);

	gap_sum = inc_gap_sum = 0;
	for (i = 0; i < count - 1; i++)
	{
		/* only consider those gaps composed by two in-order packets */
		if (rcv_record[i + 1].seq - rcv_record[i].seq == 1)
		{
			cur_gap = get_rcd_time(rcv_record[i + 1]) - get_rcd_time(rcv_record[i]);
			gap_sum += cur_gap;

			if (cur_gap > m_gap + 0.000005)
				inc_gap_sum += (cur_gap - b_gap);
		}
	}

	if (debug)
		printf("b_gap = %f %f %f \n", b_gap, inc_gap_sum, gap_sum);

	if (gap_sum == 0)
	{
		printf("\nNo valid trace in the last phase probing\n");
		printf("You may want to try again. Exit\n");
		quit();
	}

	return (inc_gap_sum * b_bw / gap_sum);
}

/* return summary of the "valid" src gaps */
double get_src_sum(double *times)
{
	int i;
	double sum;

	sum = 0;
	for (i = 0; i < probe_num - 1; i++)
		sum += (times[i + 1] - times[i]);
	return sum;
}

void get_bandwidth()
{
	if (dst_gap_count == 0)
		competing_bw = PTR_bw = a_bw = 0;
	else
	{
		if (b_bw < 1)
			b_bw = get_bottleneck_bw((struct pkt_rcd_t *)&dst_gap, total_count);
		competing_bw = get_competing_bw((struct pkt_rcd_t *)&dst_gap, avg_src_gap, total_count, b_bw);
	}
}

/* one complete probing procedure, which includes:			*/
/* 1. send out packets with (probe_num, packet_size, delay_num)  	*/
/* 2. retrieve the dst gaps values from dst machine			*/
/* 3. filter out those bad trace data and compute the src gap & dst 	*/
/*    gap summary and average						*/
void one_phase_probing()
{
	if (verbose)
		printf("\nprobe_num = %d packet_size = %d delay_num = %d \n",
			   probe_num, packet_size, delay_num);

	/* probing */
	send_packets(probe_num, packet_size, delay_num, send_times);
	if (trace_fp != NULL)
	{
		/* create a new trace item */
		cur_trace = (struct trace_item *)malloc(sizeof(struct trace_item));
		cur_trace->next = NULL;
		if (trace_list == NULL)
		{
			trace_list = cur_trace;
			trace_tail = cur_trace;
		}
		else
		{
			trace_tail->next = cur_trace;
			trace_tail = cur_trace;
		}
	}
	/* get dst gap logs */
	total_count = get_dst_gaps((struct pkt_rcd_t *)&dst_gap);

	/* compute avg_src_gap */
	src_gap_count = probe_num - 1;
	if (debug)
		printf("src_gap_count = %d \n", src_gap_count);

	src_gap_sum = get_src_sum(send_times);
	if (src_gap_count != 0)
		avg_src_gap = src_gap_sum / src_gap_count;
	else
		avg_src_gap = 0;

	/* compute avg_dst_gap */
	dst_gap_sum = get_dst_sum((struct pkt_rcd_t *)&dst_gap,
							  total_count, &dst_gap_count);
	if (debug)
		printf("%d dst_gap_count = %d \n", total_count, dst_gap_count);

	if (dst_gap_count != 0)
		avg_dst_gap = dst_gap_sum / dst_gap_count;
	else
		avg_dst_gap = 0;

	/* record total src gaps */
	tlt_src_gap += avg_src_gap;
	tlt_dst_gap += avg_dst_gap;

	if (verbose)
		printf("gaps (us): %5.0f %5.0f | %5.0f %5.0f\n",
			   tlt_src_gap * 1000000, tlt_dst_gap * 1000000,
			   avg_src_gap * 1000000, avg_dst_gap * 1000000);

	if (trace_fp != NULL)
	{
		double tmp1, tmp2, tmp3;

		cur_trace->probe_num = probe_num;
		cur_trace->packet_size = packet_size;
		cur_trace->delay_num = delay_num;

		memcpy(cur_trace->send_times, send_times,
			   sizeof(double) * probe_num);

		cur_trace->avg_src_gap = avg_src_gap;
		cur_trace->avg_dst_gap = avg_dst_gap;

		/* we can't use get_bandwidth() here since we want to record
	     * the current data, which may be wrong value*/
		if (dst_gap_count == 0)
			cur_trace->b_bw = 0;
		else
			cur_trace->b_bw = get_bottleneck_bw((struct pkt_rcd_t *)&dst_gap, total_count);

		tmp1 = PTR_bw;
		tmp2 = competing_bw;
		tmp3 = a_bw;
		get_bandwidth();
		cur_trace->ptr = PTR_bw;
		cur_trace->c_bw = competing_bw;
		cur_trace->a_bw = a_bw;
		PTR_bw = tmp1;
		competing_bw = tmp2;
		a_bw = tmp3;
	}

	probing_phase_count++;
}

void n_phase_probing(int n)
{
	int i, j, k;

	tlt_src_gap = 0;
	tlt_dst_gap = 0;

	for (i = 0; i < n; i++)
	{
		one_phase_probing();
		get_bandwidth();

		/* insert, so as to be able to pick the median easily */
		j = 0;
		while (j < i && c_bw[j] < competing_bw)
			j++;
		for (k = i - 1; k >= j; k--)
			c_bw[k + 1] = c_bw[k];
		c_bw[j] = competing_bw;
	}
	PTR_bw = packet_size * 8 * phase_num / tlt_dst_gap;
	a_bw = b_bw - c_bw[(int)(n / 2)];

	if (verbose)
		printf("------------------------------------------------------\n");
}

int gap_comp(double dst_gap, double src_gap)
{
	double delta = 0.05;

	if (dst_gap < src_gap / (1 + delta))
	{
		if (verbose)
			printf("smaller dst_gap, considered to be equal \n");
		return 0;
	}

	if (dst_gap > src_gap + 0.000005 * phase_num)
		return 1;
	else
		return 0;
}

void fast_probing()
{
	int double_check = 0, first = 1, tmp_num;
	double interval, pre_gap = 0;
	double saved_ptr, saved_abw;

	probing_start_time = get_time();

	delay_num = 0;
	n_phase_probing(phase_num);
	b_bw = get_bottleneck_bw((struct pkt_rcd_t *)&dst_gap, total_count);

	delay_num = get_delay_num(avg_dst_gap);
	interval = (double)delay_num / 4;
	delay_num /= 2;

	while (1)
	{
		if (gap_comp(tlt_dst_gap, tlt_src_gap) == 0)
		{
			if (double_check)
			{
				tlt_dst_gap = pre_gap;
				break;
			}
			else
			{
				pre_gap = tlt_dst_gap;
				double_check = 1;
			}
		}
		else
		{
			if (double_check && verbose)
				printf("DISCARD: gap = %d\n", (int)(tlt_dst_gap * 1000000));
			double_check = 0;
		}

		if (!first && tlt_dst_gap >= 1.5 * tlt_src_gap)
		{
			tmp_num = get_delay_num((tlt_src_gap + tlt_dst_gap) / (2 * total_count));
			if (tmp_num > delay_num)
				delay_num = tmp_num;
		}
		delay_num = (int)(delay_num + interval);

		/* TODO: need a better way to deal with them */
		saved_ptr = PTR_bw;
		saved_abw = a_bw;
		n_phase_probing(phase_num);
		first = 0;
	}
	PTR_bw = saved_ptr;
	a_bw = saved_abw;

	probing_end_time = get_time();
	dump_bandwidth();
}

int main(int argc, char *argv[])
{
	int opt;

	while ((opt = getopt(argc, argv, "k:l:n:s:p:f:dhv")) != EOF)
	{
		switch ((char)opt)
		{
		case 'k':
			phase_num = atoi(optarg);
			if (phase_num > MaxRepeat)
			{
				phase_num = MaxRepeat;
				printf("phase_num is too large, reset as %d\n", MaxRepeat);
			}
			break;
		case 'l':
			delay_num = atoi(optarg);
			break;
		case 'n':
			probe_num = atoi(optarg);
			if (probe_num > MaxProbeNum)
			{
				probe_num = MaxProbeNum;
				printf("probe_num is too large, reset as %d\n", MaxProbeNum);
			}
			break;
		case 's':
			packet_size = atoi(optarg);
			break;
		case 'p':
			dst_port = atoi(optarg);
			break;
		case 'f':
			if ((trace_fp = fopen(optarg, "w")) == NULL)
			{
				printf("tracefile open fails, exits\n");
				exit(1);
			}
			break;

		case 'd':
			debug = 1;
			break;
		case 'v':
			verbose = 1;
			break;
		case 'h':
		default:
			Usage();
		}
	}
	switch (argc - optind)
	{
	case 1:
		strcpy(dst, argv[optind]);
		break;
	default:
		Usage();
	}

	init_connection();
	/* allow dst 2 seconds to start up the packet filter */
	sleep(2);

	/* probing */
	if (delay_num > 0)
	{
		one_phase_probing();
		get_bandwidth();
		dump_bandwidth();
	}
	else
		fast_probing();

	/* finishing */
	cleanup(1);

	return (0);
}