N1通信网地最佳容量分配与延迟计算-通信网课设报告材料

1、CENTRAL SOUTH UNIVERSITY通信网原理课程设计报告选题N1 通信网的最佳容量分配与延迟计算专业班级电子信息1202姓名学号指导教师完成日期2015年7月14日备注：目 录1. 设计目的2. 设计要求3. 设计原理和方法4. 程序清单5. 测试数据及其结果6. 总结7. 参考文献1. 设计目的用TC、Visual BASIC、Visual C+、Java等编程工具和路由器、交换机、主机等网络设备提供的接口，解决网络用户之间通信的有关 问题，如通信实现、编码分析、协议分析、程序设计等。进一步深入 掌握通信网原理。使学生对通信网的原理及其设计实现有较深的了解, 培养较高的通信网开

2、发应用能力。2. 设计要求总体要求：了解常用通信网络设备的操作和应用，掌握常用的通信协议的工作原理，能利用 TC、Visual、BASIC、Visual C+、Java 等至少一种开发工具完成相应的通信程序的设计工作。学习简明地介绍自己的设计工作。程序设计课题方面，要求：程序操作简单、方便，界面布 局合理美观。环境要求：Win dows2000/XP/7/8功能要求：(1)设有n个节点的通信网络，三个 n阶方阵A、R、V分别表 示该网络的邻接矩阵、端对端的信息量和路由。编写一个程序，对于输入的n、A、R、V、报文长度1/口，总容量C,设计一个程 序，计算出网络的最佳容量分配及相应的延时。注意，

3、一条链路的平 均延时时间计算参考公式 T=1/(成 入)，其中1/口是以比特为单位 的报文分组平均长度；C是以该链路的容量，单位是比特/秒；入是平 均流量，单位是分组/秒。给出：n = 6,l/= 800比特/分组,厂n厂Jri1 OJ,OALO|11 094亿4 11 0222Q1 1A1A0J I11 9,0影2,4 |1 1A3,6,6,6|A= | OJA1,1,O|1R = 1 4,&0小 Iv =1 2.2,0,45,5 |1 0A1A0J I11 133A3,4 |1 gO30|1 1A1A0J I11 7233Q5 |1 1A3,36|1 OJAlJ.Ol11 442

4、炖 11 525Q0ILL的网络的最佳容量分配及相应的延时。(3)当该网络增加1个节点，其链路、路由、信息量需求自行定义，给出对应的延时。3. 设计原理和方法分析问题：这个课程设计的题目是要在已知网络结构、端对端的路由的信息 量和路由、以及网络总容量的前提下，求取最佳的容量分配方案，使 网络处于最佳状态，另外还需求这时的网络延时。一个网络的好坏可以用很多参数来衡量， 其中比较重要的有延时、 网速、稳定性等，为了简化问题这里只选取延时作为指标，因而本课 题也就是问在怎样的容量分配方法下，网络的延时最小。从已知的计算一条链路延时的公式 Ti=1/( QCi-为可知，是已知 常数，而平均流量入可以由

5、信息量以及路由矩阵可以求得，因而影响 一条链路延时的唯一因素就是该链路的容量 Ci。既然单个链路的延时已经找到控制方法，接下来的问题是如何定 义整个网络的延时？简单的将所有链路的延时相加吗， 显然这时不科 学的，因为不同链路对整个网络的影响程度显然是不同的。一种更好的方法是把平均流量作为权重得到所有链路延时的加权和，作为整个 网络的延时。原因很明显，假如流量最大的链路发生阻塞对整个网络 的影响明显比流量几乎为零的链路发生阻塞要严重的多。转化为数学问题:从上面的分析可以定义整个网络的延时为:"?-伽刀？?1?- ?由于我们关心的并不是该值的大小，而是相对大小，故可以简化为:f(?,?,

6、？d题中还有个约束条件是：?= C?2?？于是很自然的转化为在约束条件 E?- C=0下求f(?,?, ,?最 小值的问题，这是一个经典的多元函数求极值的问题， 可以用拉格朗 日乘数法求解。拉格朗日乘数法简介设给定二元函数z=?(x,y)和附加条件© (x,y)=0，为寻找z= ? (x,y)在附加条件下的极值点，先做拉格朗日函数：其中入为参数。求L(x,y)对x和y的一阶偏导数，令它们等于 零，并与附加条件联立，即L'x(x,y)= ?'x(x,y)+ 入 Mx,y)=0 ,-L'y(x,y)= ?'y(x,y)+ 入椒(x,y)=O ,L O(x,

7、y)=0由上述方程组解出x, y及入，如此求得的(x,y)，就是函数z= ? (x,y)在附加条件© (x,y)=0下的可能极值点。求解方法:构造拉格朗日函数:?,?,?1=刀?誌?务 + a?(?+?+ ? + 畑?分别对?,?,？?求一阶偏导数，并使其为零，再与联立得：?+ ?= 0(?- ?)2?- + ?= 0 (?- ?)2一 ?+?+? + ?- ?= 0观察上式可知：?=?将?,?,？?弋入最后一个方程可得V?+? - ?=上式中只包含一个变量？只要求出？整个问题就可以得到解决了,不幸的是该方程的形式比较复杂,并不是很好求解。但是细心点就会观察到关于？的函数f(?=刀V

8、?+ ? ? - ?是个单调递减的函数，使用二分法就可以很容易的求解了二分法简介：二分法(英语：Bisection method )，是一种方程式根的近似值求 法。若要求已知函数f(x) = 0的根(x的解)，则：1. 先找出一个区间a, b，使得f(a)与f(b)异号。根据介值定理，这个区间内一定包含着方程式的根。_ a + b2. 求该区间的中点-，并找出f(m)的值。3. 若f(m)与f(a)正负号相同则取 m, b为新的区间，否则取a, m.4. 重复第2和第3步至理想精确度为止。忆+ ?求出？后，代入？?= -?7-就可以得到最佳容量分配，再代入T=1/( pC-为就可以得到相应链路

9、的延时。至此问题完全的解决了。更多的思考:在上面定义整个网络延时的时候，我们是基于一个事实：流量更 大的链路对整个网络的影响更大，也就是说流量更大的链路应该分配 更多的流量。那么是否可以认为直接流量的比例分配容量呢？其实对于这种方法，我同样给出了程序实现，并且同样用公式 衡量整个网络的延时，实验结果证明了这个方法能达到同样的延时指 标。4. 程序清单/多元函数求极小值方法#in elude viostream>#in elude vcstri ng>#in elude <stdio.h>#in elude <math.h>#in elude <algo

10、rithm>using n amespace std ;const int MAXN = 10 ;int N ;intAMAXNMAXN,RMAXNMAXN,VMAXNMAXN, namdaMAXNMAXN double C_sum ,U, CMAXNMAXN , TMAXNMAXN;void add_li nk(i nt u , int t , int val) if(u = t) return ;int next = Vut;n amdau next += val;add_li nk(n ext , t , val);double f(double alpha)double ans=

11、 0 ;for(i nt i=1; i<=N; i+) for(int j=1; jv=N; j+) if(Aij) ans += ( sqrt(U / alpha) + n amdaij ) / U ;ans -= C_sum ; return ans;/二分法求“ Lagrange乘数法"中的待定常数alphadouble cal_alpha() double eps = 1e-10 ;double low = eps , high = 1e8 ;while(high - low > eps) double mid = (high + low) /2 ;if(f(mi

12、d) > 0) low = mid ; else high = mid ;retur n (high + low) / 2 ;int mai n()printf("n请输入节点数 N : n");scan f("%d", &N);printf("n请输入邻接矩阵 A : n");for(i nt i=1; i<=N; i+)for(int j=1; jv=N; j+)scanf("%d", &Aij);printf("n请输入端对端的信息量 R: n");for(i

13、nt i=1; i<=N; i+)for(int j=1; jv=N; j+)sca nf("%d", & Rij);printf("n请输入路由 V: n");for(i nt i=1; i<=N; i+)for(int j=1; j<=N; j+)sca nf("%d", &Vij);printf("n请输入报文分组平均长度U : n");scan f("%lf", &U);prin tf("n请输入链路总容量 C_sum:n")

14、;scan f("%lf", & C_sum);for(i nt i=1; i<=N; i+)for(int j=1; jv=N; j+)addnk(i , j, Rij);prin tf("n平均流量矩阵为：n");for(i nt i=1; i<=N; i+) for(i nt j=1; jv=N; j+) pri ntf("%-5d " , namdaij);prin tf("n");double alpha = cal_alpha();prin tf("nalpha = %fn

15、" , alpha);for(int i=1; i<=N; i+)for(int j=1; j<=N; j+)if(Aij) Ci j= ( sqrt(U / alpha) + namdaij) / U ;Ti j= 1.0 / ( U*Cij - namdaij);double fans = 0;for(i nt i=1; i<=N; i+)for(int j=1; jv=N; j+) if(Aij) fans += n amdaij / ( U * Ci j - namdai j);pri ntf("f = %fn" , fan s);pri

16、n tf("n");printf("个链路的最佳容量分配为：n");for(i nt i=1; i<=N; i+) for(int j=1; j<=N; j+)if(!Aij) pri ntf("-");else printf(%10.3f", Cij);prin tf("n");prin tf("n");printf("个链路的平均延时为：n");for(i nt i=1; i<=N; i+) for(int j=1; jv=N; j+)if(A

17、ij) pri ntf("%-10.5f", Tij); else printf("");prin tf("n");prin tf("n");return 0;/按流量比例分配方法#in clude <iostream>#in clude <cstri ng>#in clude <stdio.h>#in clude <math.h>#i nclude <algorithm> using n amespace std ;const int MAXN = 10

18、 ;int N ;intAMAXNMAXN,RMAXNMAXN,VMAXNMAXN, namdaMAXNMAXN double C_sum ,U, CMAXNMAXN , TMAXNMAXN;void add_li nk(i nt u , int t , int val) if(u = t) return ;int next = Vut;n amdau next += val;add_li nk(n ext , t , val);int mai n()printf("n请输入节点数 N : n");scan f("%d", &N);printf(

19、"n请输入邻接矩阵 A : n");for(i nt i=1; i<=N; i+)for(int j=1; jv=N; j+)sea nf("%d", &Aij);printf("n请输入端对端的信息量 R: n");for(i nt i=1; i<=N; i+)for(int j=1; j<=N; j+)sca nf("%d", & Rij);printf("n请输入路由 V: n");for(i nt i=1; i<=N; i+)for(int j=1

20、; j<=N; j+)sca nf("%d", &Vij);printf("n请输入报文分组平均长度U : n");scan f("%lf", &U);prin tf("n请输入链路总容量 C_sum:n");scan f("%lf", & C_sum);for(i nt i=1; i<=N; i+)for(int j=1; j<=N; j+)add_li nk(i , j, Rij);prin tf("n平均流量矩阵为：n");fo

21、r(i nt i=1; i<=N; i+) for(i nt j=1; jv=N; j+) pri ntf("%-5d " , namdaij);prin tf("n");double n amda_sum =0 ;for(i nt i=1; i<=N; i+)for(int j=1; j<=N; j+)n amda_sum += n amdai j;double k = C_sum / n amda_sum ;pr in tf("k = %.2fn" , k);for(int i=1; i<=N; i+)fo

22、r(int j=1; j<=N; j+)Cij=k * namdaij;if(Aij) Tij= 1.0 / ( (U*k - 1.0)* namdaij);double fans = 0;for(i nt i=1; i<=N; i+)for(int j=1; jv=N; j+) if(Aij) fans += namdai j / ( U * Ci j - namdai j);pri ntf("f = %fn" , fan s);pri ntf("n");printf("个链路的最佳容量分配为：n");for(i nt

23、i=1; i<=N; i+) for(int j=1; jv=N; j+)if(!Aij) pri ntf("")；else prin tf("%-10.3f", Cij);prin tf("n");pri ntf("n");printf("个链路的平均延时为：n");for(i nt i=1; i<=N; i+) for(int j=1; jv=N; j+)if(Aij) pri ntf("%-10.5f", Tij); else printf("&q

24、uot;);prin tf("n");prin tf("n");return 0;5. 测试数据及其结果多元函数求极值方法的结果：1 D:AC Mcode2015xingxingwangbinDebugxin,0100101010010101100 01 00I10 100 In1 o11(I橋输人扁对端的信WR：0 9 4 174 2 463 0 ? 3 24 $ 0 3 3 U $ 0 S7 2 3 5 B4 4 2 4 50 22255109606t 20455SCS036163306惰输入报文分组平旳长度U：5l1400121200609800c

25、0000140 ID08130时h& = 0.000123 f = 0,065070金前路的最住咨里分酉珑：3.1303.1273.1273_1203.12?3.123<J.12S3.1273.12G 3.1258.1203.122gj22 31289.1223 J90个阴的平均延时为:0.00040U血啊0.00040Looooo |：| .00CI400.000400.000400,90040a.900400,000400.CQ04O0.OUO4O0.000400.000400JOO4O0,00040 D:ACMcode2015xingxingw3ngbirADQbugxi门.0 3 4 17 4 19 0 8 3 2 4