DPP.rar_dpp_protection path_专用保护算法_光网络_光网络路由

/**********************************************************************/ /* */ /* File "rand.h" */ /* Random Variate Generation */ /* */ /* */ /**********************************************************************/ #ifndef _RAND_H #define _RAND_H #include <stdio.h> #include <math.h> #define A 16807L /* multiplier (7**5) for 'ranf' */ #define M 2147483647L /* modulus (2**31-1) for 'ranf' */ static long In[16]= {0L, /* seeds for streams 1 thru 15 */ 1973272912L, 747177549L, 20464843L, 640830765L, 1098742207L, 78126602L, 84743774L, 831312807L, 124667236L, 1172177002L, 1124933064L, 1223960546L, 1878892440L, 1449793615L, 553303732L}; static int strm=1; /* index of current stream */ float ranf(); //uniform [0, 1] random number generator int stream(int n); //select generator stream long seed(long Ik, int n); //set/get seed float uniform(float a, float b); //uniform [a, b] random number generator int random(int i, int n); //random integer generator float exponential(float x); //exponential random variate generator float erlang(float x,float s); //erlang random variate generator float hyperx(float x,float s); //hyperexponential random variate generator float normal(float x,float s); //normal random variate generator #include <iostream> using namespace std; const int reqstnum=70; //请求的次数 const int MAXVEX=6; //节点数 const float MAXBAND=20; //为了使输出的tempcost的值为float，把 MAXBAND设为float型 const int NOUT=-1; //NOUT定义为没有意义的数为-1 float INF=9999; #endif /*------------- UNIFORM [0, 1] RANDOM NUMBER GENERATOR -------------*/ float ranf() { short *p,*q,k; long Hi,Lo; /* generate product using float precision simulation (comments */ /* refer to In's lower 16 bits as "L", its upper 16 bits as "H") */ p=(short *)&In[strm]; Hi=*(p+1)*A; /* 16807*H->Hi */ *(p+1)=0; Lo=In[strm]*A; /* 16807*L->Lo */ p=(short *)&Lo; Hi+=*(p+1); /* add high-order bits of Lo to Hi */ q=(short *)&Hi; /* low-order bits of Hi->LO */ *(p+1)=*q&0X7FFF; /*0111 clear sign bit */ k=*(q+1)<<1; if (*q&0X8000) k++; /* Hi bits 31-45->K */ /* form Z + K [- M] (where Z=Lo): presubtract M to avoid overflow */ Lo-=M; Lo+=k; if (Lo<0) Lo+=M; In[strm]=Lo; return((float)Lo*4.656612875E-10); /* Lo x 1/(2**31-1) */ } int random(int i, int n) //产生1-25间的一个随机整数 { /* 'random' returns an integer equiprobably selected from the */ /* set of integers i, i+1, i+2, . . , n. */ if (i>n) printf("random Argument Error: i > n"); n-=i; n=(int)((n+1.0)*ranf()); return(i+n); } void dijkstra(float cost[MAXVEX][MAXVEX],int n,int v,int des,int store[reqstnum][MAXVEX+2],int retime)//des是终点，v是源点,retime---require time请求的次数 { float dist[MAXVEX], mindis; int s[MAXVEX], i,j,u,pre,k,path[MAXVEX]; int zancun[MAXVEX+1]; for (i=0;i<(MAXVEX+1);i++) { zancun[i]=-1;} for (i=0;i<n;i++) { dist[i]=cost[v][i]; //距离初始化 s[i]=0; //s[]置空 if(cost[v][i]<INF) //路径初始化 path[i]=v; else path[i]=-1; } s[v]=1;path[v]=0; //源点编号v放入s中 for(i=0;i<n;i++) //循环直到所有的顶点的最短路径都求出 { mindis=INF; u=-1; for(j=0;j<n;j++) //选取不再s且具有最小距离的顶点u if(s[j]==0 && dist[j]<mindis) { u=j; mindis=dist[j]; } if(u!=-1) { s[u]=1; for(j=0;j<n;j++) if(s[j]==0) if(cost[u][j]<INF && dist[u]+cost[u][j]<dist[j]) { dist[j]=dist[u]+cost[u][j]; path[j]=u; } } } //输出最短路径的长度，路径顺序输出 cout<<" "<<v<<"->"<<des<<":"; if(s[des]==1) { cout<<"路径长度为"<<dist[des]<<" "; k=0; zancun[MAXVEX]=dist[des]; zancun[MAXVEX-1]=v; pre=des; while(pre!=v) //一直回溯到初始顶点 { zancun[k]=pre; pre=path[pre]; k=k+1; } //开始往请求数组里存储 j=0; for(i=0;i<(MAXVEX+1);i++) { if(zancun[MAXVEX-i]!=-1) { store[retime][j]=zancun[MAXVEX-i]; j=j+1; } } i=1; cout<<" 经历的节点是:"; while(store[retime][i]!=-1) { cout<<store[retime][i]<<","; i++; } cout<<"\n"; } else cout<<"不存在路径"<<endl; } //dijkstra算法结束 //主函数开始 void main() { int i,j,s1,s2,blocknum=0,baohublocknum=0;//记录工作路径和保户路径被阻塞的次数 float costshuzu[MAXVEX+1];// 用来存储为了寻找保护路径暂时变成无穷的工作通路的代价.+1是为了与以后计算的下标对应 int pertectstore[reqstnum][MAXVEX+2];//该二维数组用来存储与store对应的保护通路的路径和长度 int store[reqstnum][MAXVEX+2]; //第0个元素存储路径的总长度，路径最多MAXVEX个点，最后一个用作数组结束循环语句控制的标志 void dijkstra(float cost[MAXVEX][MAXVEX],int n,int v,int des,int store[reqstnum][MAXVEX+2],int retime);//示第retime次业务请求 float cost[MAXVEX][MAXVEX]={ {0,50,10,INF,INF,INF}, {50,0,15,50,10,INF}, {10,15,0,15,INF,INF}, {INF,50,15,0,35,INF}, {INF,10,INF,30,0,3}, {INF,INF,INF,3,4,0}}; float tempcost[MAXVEX][MAXVEX]; for(i=0;i<MAXVEX;i++) //设tempcost的初始值与cost相同 { for(j=0;j<MAXVEX;j++) tempcost[i][j]=cost[i][j]; } for(i=0;i<reqstnum;i++) //设工作业务矩阵的初始值都是-1，无效。只有存入数字的元素有效 { for(j=0;j<(MAXVEX+2);j++) store[i][j]=NOUT; } for(i=0;i<reqstnum;i++) //设保护业务矩阵的初始值 { for(j=0;j<(MAXVEX+2);j++) pertectstore[i][j]=NOUT; } int freeband[MAXVEX][MAXVEX]={ {0,20,20,0,0,0}, {20,0,20,20,20,0}, {20,20,0,20,0,0}, {0,20,20,0,20,0}, {0,20,0,20,0,20}, {0,0,0,20,20,0}}; //设置存储设需带宽的数组 int busyband[MAXVEX][MAXVEX]; //设置存储工作带宽的数组 for(i=0;i<MAXVEX;i++) //初始化占用带宽为0 { for(j=0;j<MAXVEX;j++) busyband[i][j]=0; } for(i=0;i<reqstnum;) { s1=random(0,5); s2=random(0,5); if(s1!=s2) { cout<<"第"<<i<<"次业务请求工作路径:"; dijkstra(tempcost,6,s1,s2,store,i); //计算工作路径 if(store[i][0]!=-1) //判断是否找到了工作路径，如果找到那么store[i][0]!=-1 { for(j=1;store[i][j+1]!=-1;j++) //从第一个元素开始是路径的而第一个节点，store设置的MAXVEX+2是因为这一步的极限当路径经过的节点为节点总数时 { freeband[store[i][j]][store[i][j+1]]=freeband[store[i][j]][store[i][j+1]]-1; if(freeband[store[i][j]][store[i][j+1]]<=0) { tempcost[store[i][j]][store[i][j+1]]=INF; //当链路上没有可利用的带宽时，代价设为无穷 } else tempcost[store[i][j]][store[i][j+1]]=cost[store[i][j]][store[i][j+1]]+(MAXBAND-freeband[store[i][j]][store[i][j+1]]+1)/MAXBAND; busyband[store[i][j]][store[i][j+1]]=busyband[store[i][j]][store[i][j+1]]+1; } for(j=1;store[i][j+1]!=-1;j++) //把工作路径的代价都设为无穷以便寻找保护路 { costshuzu[j]=tempcost[store[i][j]][store[i][j+1]]; tempcost[store[i][j]][store[i][j+1]]=INF; } cout<<"第"<<i<<"次业务请求保护路径: "; dijkstra(tempcost,6,s1,s2,pertectstore,i);//计算工作通路的专用保护路径 for(j=1;store[i][j+1]!=-1;j++) { tempcost[store[i][j]][store[i][j+1]]=costshuzu[j]; //把变成无穷的工作通路的代价变回原来的值 } if(perte