ospfh_abstract.c

实现禁位自动排列在禁位中具体实现了此方法所以这是一个创新很有应用价值在VC平台上调试通过

/* The topology aggregation */


#include "ospfh.h"
#include "ospfh_patch.h"


#define TOPO_MAX_NODE_NUM    10
#define DEFALT_COST          100
void
ospfh_abstract(struct ospf *top,struct list* lsa_list,struct list* inter_lsa_list)
{
	int  **topo;
	int  bordernodenum;
	int nodenum=0;
	int layernum=0;
	int  **cost;
    struct in_addr  *border=NULL;
	struct in_addr *node_id=NULL;
	struct mpls_te_link *lp;
	struct  ospf_lsa  *newlsa;
	int i,j,p,q,m,n;

	node_id=malloc(sizeof(struct in_addr)*TOPO_MAX_NODE_NUM);
	border=malloc(sizeof(struct in_addr)*TOPO_MAX_NODE_NUM);
//根据给出的LSALIST构造出对应的网络拓扑矩阵
	nodenum=nodenum_caculate(lsa_list,node_id);
	topo=topology_matrix_create(lsa_list,nodenum,node_id);
//计算网络中的边界节点数
  bordernodenum=bordernodenum_caculate(inter_lsa_list,border);
  	cost=malloc(sizeof(int *)*bordernodenum);
	for(i=0;i<bordernodenum;i++)
	{
		cost[i]=malloc(sizeof(int)*bordernodenum);
		for(j=0;j<bordernodenum;j++)
		{
       		cost[i][j]=DEFALT_COST;
		}
	}
	for(i=0;i<bordernodenum;i++)
	{
		for(j=0;j<bordernodenum;j++)
		{
			if(i!=j)
			{

			for(p=0;p<TOPO_MAX_NODE_NUM;p++)
			{
				if(border[i].s_addr==node_id[p].s_addr) 
				{m=p;break;}
				else continue;
			}
			for(q=0;q<TOPO_MAX_NODE_NUM;q++)
			{
				if(border[j].s_addr==node_id[q].s_addr)
				{ n=q;break;}
				else continue;
			}

//调用dijkstra算法计算任意两个边界节点之间的最短路经
			cost[i][j]=dijkstra(topo,nodenum,m+1,n+1);
//每算出一个值，就对应生成一条抽象链路，用下列一个新的LINKTLV来表示


			lp=malloc(sizeof(struct mpls_te_link));

//给lp各个字段赋值
			initialize_linkparams (lp,cost[i][j],border[i],border[j]);

//产生新的lsa

 //           newlsa=malloc(sizeof(struct ospf_lsa));
//			newlsa->lp=lp;
			 newlsa=ospf_mpls_te_lsa_new (top,lp);
		newlsa->data->ls_seqnum=htonl(top->lsa_originate_count+1);
			    top->lsa_originate_count++;
       	     	ospf_flood_out(top,NULL,newlsa);
			layernum=id_to_layernum(top->self_rc_id);
//写入数据库
        	ospf_lsa_install(layernum,newlsa);
			}
			else continue;
		}
	}
}


//use the lsalist to create an matrix
int  **
 topology_matrix_create(struct list *lsa_list,int nodenum,struct in_addr *node_id)
{
	int i,j;
	int **topo;
	int count;
	struct listnode *node;
	struct ospf_lsa  *lsa;
    struct in_addr temp_local_id,temp_remote_id; 
 
//构建一个新的数组
		topo=malloc(sizeof(int *)* nodenum);
	for(i=0;i<nodenum;i++)
	{
		topo[i]=malloc(sizeof(int*)* nodenum);
		for(j=0;j<nodenum;j++)
		{
       		topo[i][j]=DEFALT_COST;
		}
	}
for(i=0;i<nodenum;i++)
	{
		for(j=0;j<nodenum;j++)
		{
       	  printf("%d ",topo[i][j]);
		}
		printf("\n");
	}
 
count=lsa_list->count;

if (count)
    {
	 for (node = lsa_list->head; node;  node = node->next)
	 {
         if (count)
		 {
		   count--;
           lsa =(struct  ospf_lsa  *)(node->data);
           temp_local_id=lsa->lp->local_id.value;
		   temp_remote_id=lsa->lp->remote_id.value;
                 for(i=0;i<nodenum;i++)
				 {
					 if(temp_local_id.s_addr==node_id[i].s_addr) break;
					 else continue;
				 }
				 for(j=0;j<nodenum;j++)
				 {
					 if(temp_remote_id.s_addr==node_id[j].s_addr) break;
					 else continue;
				 }
				 if((i<nodenum)&&(j<nodenum))
				 topo[i][j]=ntohl(lsa->lp->te_metric.value);
				 else NULL;
		 }
		 else break;
	 }
}
for(i=0;i<nodenum;i++)
	{
		for(j=0;j<nodenum;j++)
		{
       	  printf("%d ",topo[i][j]);
		}
		printf("\n");
	}
 return topo;

}



int
nodenum_caculate(struct list *lsa_list, struct in_addr *node_id)
{
	struct listnode *node;
    int count = lsa_list->count;
    struct ospf_lsa  *lsa;
    int nodenum;
    int k;
    struct in_addr temp_local_id,temp_remote_id;



	lsa=listnode_head(lsa_list);
	node_id[0]=lsa->lp->local_id.value;
	node_id[1]=lsa->lp->remote_id.value;
    nodenum=2;

	if (count)
    {
	 for (node = lsa_list->head; node;  node = node->next)
     {
         if (count)
		 {
		   
           lsa = (struct  ospf_lsa *)(node->data);
           temp_local_id=lsa->lp->local_id.value;
		   temp_remote_id=lsa->lp->remote_id.value;
//判断这个本地地址表示的节点是否已经写入，没有则写入
		   for(k=0;k<nodenum;k++)
		   {
			   if(temp_local_id.s_addr==node_id[k].s_addr) break;
			   else continue;
		   }
		   if(k==nodenum) 
		   {
			   node_id[nodenum]=temp_local_id;
			   nodenum++;
           }
//判断这个对端地址表示的节点是否已经写入，没有则写入
		   for(k=0;k<nodenum;k++)
		   {
			   if(temp_remote_id.s_addr==node_id[k].s_addr) break;
			   else continue;
		   }
		   if(k==nodenum) 
		   {
			   node_id[nodenum]=temp_remote_id;
			   nodenum++;
           }
           count--;
		 }
		 else break;
	 }
	
	}
	return nodenum;
}

int
bordernodenum_caculate(struct list *lsa_list,struct in_addr *node_id)
{
	struct listnode *node;
    int count = lsa_list->count;
    struct ospf_lsa  *lsa;
    int nodenum;
    int k;
    struct in_addr temp_local_id;



	lsa=listnode_head(lsa_list);
    node_id[0]=lsa->lp->local_id.value;
    nodenum=1;

	if (count)
    {
	 for (node = lsa_list->head; node;  node = node->next)
     {
         if (count)
		 {
		   lsa =(struct  ospf_lsa  * )(node->data);
           temp_local_id=lsa->lp->local_id.value;
//判断这个本地地址表示的节点是否已经写入，没有则写入
		   for(k=0;k<nodenum;k++)
		   {
			   if(temp_local_id.s_addr==node_id[k].s_addr) break;
			   else continue;
		   }
		   if(k==nodenum) 
		   {
			   node_id[nodenum]=temp_local_id;
			   nodenum++;
           }
           count--;
		 }
		 else break;
	 }
	
	}
	return nodenum;
}


/*dijkstra.c*/


int dijkstra(int ** topology, int nodenum, int src,int dst)
{
	int * lasthop;
    int * N;
    int * D;
	int * retp;
    int i,k,t,m;
    int min,temp,temphop;
	int a_end,z_end;
	int cost;
	int ** path;


    lasthop=malloc(sizeof(int)*nodenum);
    for(i=0;i<nodenum;i++)
	    lasthop[i]=i+1;
    N=malloc(sizeof(int)*nodenum);
    D=malloc(sizeof(int)*nodenum);
	retp=malloc(sizeof(int)*nodenum);
    memset(N, 0, sizeof(int)*nodenum);
    memset(D, 0, sizeof(int)*nodenum);
    memset(retp, 0, sizeof(int)*nodenum);

	path=malloc(sizeof(int *)*nodenum);
	for(i=0;i<nodenum;i++)
	{
		path[i]=malloc(sizeof(int)*nodenum);
		memset(path[i],0,sizeof(int)*nodenum);
	}


    N[src-1]=1;
    for(i=0; i<nodenum; i++)
		D[i]=topology[src-1][i];

    t=1;
    while(t<nodenum)
	{ 
		k=-1;
		min=WEIGHT_VALUE_INFINIT+1;
		for(i=0; i<nodenum; i++)
		{
			if(N[i]==0)//寻找一个不在N中的节点，其D值最小
			{
				if (D[i]<min)
				{ 
					min=D[i];
					k=i;
				}
			}

        }
        if(k!=-1)
		{
			N[k]=1;//D值最小的节点加入到N中
			
			for(i=0;i<nodenum;i++)//对所有不在N中的节点，用较小值去更新原有的D值
				if((N[i]==0)&&(D[k]+topology[k][i]<D[i]))
				{
					D[i]=D[k]+topology[k][i];
					lasthop[i]=k+1;
				}
		}
		else
		{
            for(i=0;i<nodenum;i++) //如果没有则其他节点为不可达
            if(N[i]==0)
            lasthop[i]=0;
			
		}
		t++;
	}
	for(i=0;i<nodenum;i++)
	{
		if(lasthop[i]==src)
			path[i][0]=src;
		else
			if(lasthop[i]==i+1)
            {
				path[i][0]=src;
				path[i][1]=i+1;
			}
			else
            {
				path[i][0]=src;
				k=1;
				temphop=lasthop[i];
				path[i][k]=temphop;
				while(lasthop[temphop-1]!=temphop)
				{
                    k++;
					temphop=lasthop[temphop-1];
					path[i][k]=temphop;
				}
				for(m=1;m<=(int)(k/2);m++)
				{
					temp=path[i][k+1-m];
					path[i][k+1-m]=path[i][m];
					path[i][m]=temp;
				}
				k++;
				path[i][k]=i+1;
			}
	}
	for(i=0;i<nodenum;i++)
		retp[i]=path[dst-1][i];

	//calculate the cost of the path
	cost=0;
	for(i=0;i<nodenum-1;i++)
	{
		a_end=retp[i];
		z_end=retp[i+1];
		if(z_end!=0)
			cost=cost+topology[a_end-1][z_end-1];
		else
			break;

	}
	free(lasthop);
    free(N);
    free(D);
	free(retp);

	return cost;

}