hyper.cpp

包分类算法Hypercuts算法

/*
The code is contructed by Borland C++ v5.02 and C++ BuilderX.
I hope to release a GCC version in a short time.
The file formats of filter database and trace are come from ClassBench.

  There are five parameters to control the construction of decision tree.
  
1) common_filter_extraction (defined in hyper.h)
	The most important optimization skill in HyperCuts. It extracts the common filters in all branches.
	To avoid a long filter list for linear search, we apply the common_bucket_size to restrict its maximal length.
	
	Also, we force to generate cuts on multiple dimensions as the number of filters is large.
	This is because adopting only one-dimensional cuts might incur replication of a huge number of filters with wildcard on that dimension.
	Applying cuts on both dimensions could alleviate such condition.
	  
2) redundant_removal (defined in hyper.h)
	If the categoried filters in different branches are identical, these two branches are merged.
	However, the space corresponding to these filters are augumented.
	In the worst case, the resulted space might be identical to the original space before performing cutting.
	In such a case, we should abort the construction since the phenomenon will result in an infinite loop.
		
	In our experiments, the optimization may cause a performance degradation since the occupied space of
	the resulted filters cannot be reduced fast.
		  
3) cut_threshold (defined in hyper.h)
   If the number of cuts is less than cut_threshold, the construction procedure is stopped.
			
4) spfac (input by argument)
	Space factor, control the maximal number of generated branches.
			  
5) common_bucket_size (input by argument)
	Control the maximal number of filters in bucket. These filters are searched by using linear search.
				
The region compaction is also implemented in the codes; however, it seems not very effective.
				  
	If you have any idea to improve our codes, please let me know! Thank you.
	My email address is: [e-mail]
*/

#include "hyper.h"

#define information_2

UINT node_count=0, branch_count=0, filters_count=0, spfac, common_bucket_size;
char *filter_file, *trace_file;

int main(int argc, char * argv[]) {
	int i, j;
	void hyper(filter *);
	filter *filters=NULL, *current;
	original_filter *original_filters;
	
	if ( argc <5) {
	printf("Execution: hyper.exe spfac common_bucket_size filter trace\n\n");
	printf("For example: hyper.exe 1 64 filter.txt filter.txt_trace");
	return 0;
	}
	
	  spfac = atoi(argv[1]);
	  common_bucket_size =atoi(argv[2]);
	  filter_file=argv[3];
	  trace_file=argv[4];
	
	
/*	spfac = 1;
	common_bucket_size =72;
	filter_file="my.rtf";
	trace_file="my_trace.rtf";
*/	
	/*if ( argc > 1 ) {
	spfac = atoi( argv[1] );
	if ( argc > 2)
	common_bucket_size =atoi(argv[2]);
	else
	common_bucket_size =0;
	}
	else {
	spfac = 1;
	common_bucket_size =64;
	}
	*/
#ifdef information_2
	time_t t;
	struct tm * area;
	t = time( NULL );
	area = localtime( & t );
	// printf( "Parameter:  spfac %d, common bucket size %d\n", spfac, common_bucket_size );
	// printf( "Size of each filter: %d, header: %d", sizeof( original_filter ), sizeof( header ) );
	//  printf( ", local time is: %s", asctime( area ) );
#endif
	
	original_filter *transform_filter(int *);
	original_filters=transform_filter(&i);
	
	// Transfer the filter format of ClassBench into a generalized form
	for (j=0; j<i; j++) {
		if (filters==NULL) {
			filters=(filter *)calloc(1, sizeof(filter));
			current=filters;
		}
		else {
			current->next=(filter *)calloc(1, sizeof(filter));
			current=current->next;
		}
		current->start[0]=original_filters[j].sa;
		current->end[0]=original_filters[j].sa+pow(2, 32-original_filters[j].sa_len)-1;
		current->start[1]=original_filters[j].da;
		current->end[1]=original_filters[j].da+pow(2, 32-original_filters[j].da_len)-1;
		current->start[2]=original_filters[j].sp[0];
		current->end[2]=original_filters[j].sp[1];
		current->start[3]=original_filters[j].dp[0];
		current->end[3]=original_filters[j].dp[1];
		
		if (original_filters[j].prot_num > 0)
			current->start[4]=current->end[4]=original_filters[j].prot_num;
		else {
			current->start[4]=0;
			current->end[4]=255;
		}
		
		if (original_filters[j].flags_mask > 0)
			current->start[5]=current->end[5]=original_filters[j].flags;
		else {
			current->start[5]=0;
			current->end[5]=65535;
		}
	}
	
	UINT k=0;
	for (current=filters; current!=NULL; current=current->next) {
		current->id=k;
		k++;
	}
	printf( "Parameter:  spfac %d, common bucket size %d\n", spfac, common_bucket_size );
	//  printf("Original Filters: %d, Current Filters: %d, ", i, k);
	//original_filter的内存空间没有释放，释放它的空间
	//修改时间：08.2.28
	free(original_filters);
	//读取规则的过程:首先在函数read_filters()从文件中读取规则库，数据结构是FilteList,是链表形式的，
	//然后在函数transform_filter,将链表形式的规则库转化为数组形式的，数据结构是original_filter的，返回函数main
	//第三步又将数组形式的规则库转化为范围形式的链表规则，数据结构是filter,main函数运行到此处
	//hyper函数运行hypercuts算法
	hyper(filters); 
	
#ifdef information_2
	t = time(NULL);
	area = localtime(&t);
	// printf("Local time is: %s", asctime(area));
#endif
	return 0;
}

//函数p_node()打印树的结构到文件node.txt中
//修改时间：3月3日
void  p_node(struct node *nodes,int level)
{
	struct node *cnodes;
	FILE * fp;
	int i=0,totalcuts=1;
	id_list *fs;
	
	if (!nodes)
		return ;
	if(nodes)
	{   
		fp=fopen("node.txt","a");
		totalcuts=1;
		fprintf(fp,"level:%d \n",level++);
		fprintf(fp,"filter count:%d \n",nodes->filter_count);
		if(nodes->rectangle)
			fprintf(fp,"rectangle:%u %u %u %u\n",nodes->rectangle->start[0],nodes->rectangle->end[0],nodes->rectangle->start[1],nodes->rectangle->end[1]);
		for(i=0;i<2;i++)
		{
			fprintf(fp,"region:%u %u %u\n",nodes->start[i],nodes->end[i],nodes->cut[i]);
			totalcuts=totalcuts*nodes->cut[i];
		}
		for(fs=nodes->filters;fs;fs=fs->next)
			fprintf(fp,"%d\t",fs->id);
		fprintf(fp,"totalcuts:%d\n",totalcuts);
		fclose(fp);
		cnodes=nodes;
		for(i=0;i<totalcuts;i++)
		{   
			nodes=cnodes->branch[i];
			p_node(nodes,level);
		}
	}
	
}

//函数sapce_node()打印树的结构到文件node.txt中
//修改时间：3月3日
void space_node(struct node *nodes,long int &space)
{
	struct node *cnodes;
	int i=0,totalcuts=1;
	struct id_list *list,*L;
	struct filter *fs,*F;
	int count_l=0,count_f=0;
	if (!nodes)
	 	return;
	else 
	{   
		space=space+sizeof(node);
		totalcuts=1;
	
		count_l=0;
		count_f=0;
		for(list=nodes->filters;list;)
		{  
			count_l++;
			for(fs=list->filters;fs;)
			{
			count_f++;	F=fs;fs=fs->next;
			//free(F);
			}
			L=list;
			list=list->next;
		//	free(L); 
		}
		space=space+sizeof(id_list)*count_l+sizeof(filter)*count_f;
		if(nodes->rectangle)
		space=space+sizeof(hyper_rectangle);
		for(i=0;i<DIMENSIONS;i++)
		{
			totalcuts=totalcuts*nodes->cut[i];
		}
		cnodes=nodes;
		if(nodes->branch)
		{for(i=0;i<totalcuts&&totalcuts!=1;i++)
		{   
			if(nodes=cnodes->branch[i])
			space_node(nodes,space);
			else{ space=space+sizeof(node *); }
		}}
	//	free(nodes->branch);
	//	free(nodes);
	}
	
}

//返回数据包中数据包头的个数
int count_f(const char *filename)
{	
	char ch ;
    FILE *fp;
	int count=0;	
	
	fp=fopen(filename, "r");
	if (!fp) 
	{
		printf("filename error!\n");
		return 0;
	}
	
	ch='\0';
	
	//读取文件，直到读到文件末尾，文件类型是文本文件
	while (ch!=EOF)
	{   
		ch=fgetc(fp);
		if(ch=='\n') count++;//buffer读取到下一条规则的开始处@，buffer最后一位赋值'0'	
	}
	fclose (fp);
//	printf("%d\n",count);
	return count;	
}
// The function repeatedly divide the filters into different groups according to different criterion.
void hyper(filter *filters) {
	UINT i;
	node *root, *tree_construction(id_list *, hyper_rectangle, UINT);
	//   filter *current;
	UINT filter_count(filter *), original=filter_count(filters);
	id_list *filter_lists=NULL, *add_id_list(id_list *head, filter *filters);
	
	clock_t first,second,third,forth; 
	double duration1=0,duration2=0; 
	
	first = clock(); 
	//add_id_list()函数的作用是将新规则filters对一个新的类型是id_list的内存进行赋值,然后加入到head的末尾
	for (filter *head=filters; head!=NULL; head=head->next)
		filter_lists=add_id_list(filter_lists, head);
	
	UINT id_list_count(id_list *);
	
	//为了计算初始化的时间，将这句输出语句隐去
	//修改时间:08.2.28
	//	printf("id list count: %d", id_list_count(filter_lists));
	//初始化
	hyper_rectangle rectangle;
	for (i=0; i<DIMENSIONS; i++) {
		rectangle.start[i]=0;
		rectangle.end[i]=0xffffffff;
	}
	root=tree_construction(filter_lists, rectangle, 1);
	//本函数运行在此之前为建树过程
	second = clock(); 
	duration1 = (double)(second-first); 
	int level=0;
	#ifdef DEBUG 
	p_node(root,level);
	#endif
    //空间是怎么计算？
	//	printf("Node count: %d, branch count: %d, filter count: %d (Storage: %d Kbytes)\n", node_count, branch_count, filters_count, (node_count*32+branch_count*4+filters_count*16)/1024);
	//函数space_node()返回树的空间，以byte计算
	
	//	UINT decision_tree_depth(node *, UINT);
	//   printf(", depth: %d", decision_tree_depth(root, 1));

	/******************************************************************************/
	/* Read the trace file generated by trace_generator.*/
	void trace_evaluation(header *, UINT, node *);
	//  struct stat statbuf;
	FILE *fd;
    int count_head=count_f(trace_file);
//	printf("%d\n",count_head);
	fd=fopen(trace_file, "rt");
	//先计算下有多少数据包，再分 配空间
     
	header *trace=NULL;
	if(count_head) trace=(header *)calloc(count_head, sizeof(header));
	i=0;
	UINT temp;
	while (fscanf(fd, "%d %d %d %d %d %d %d", &trace[i].value[0], &trace[i].value[1], &trace[i].value[2],
		&trace[i].value[3], &trace[i].value[4], &trace[i].value[5], &temp) != EOF)
		i++;