在线论文： 1. 组播OVERLAY网络分布式动态路由的研究1 2. 应用层主动网络中服务位置与路由算法的研究 3. Study on Exact Average Degree Model for Stochastic Network Simulation

余镇危, 刘克俭　  中国矿业大学(北京)，北京，100083 zwyu@cumtb.edu.cn    摘要：本文给出了组播覆盖网络MON动态路由的定义，并在此基础上提出了MON动态组播路由计算所应考虑的问题，给出了基于分布式触发重组的MON动态组播路由算法NPPR-N和NPPR-D，并在本文的最后对算法的复杂度进行了推证，对算法的有效性进行了以EAD模型为基础平台的网络模拟。 关键词：OVERLAY；组播；动态路由；分布式触发重组 1　引言 现实的网络环境，还不具备为实现某一种应用而全部改造或重新定制现有路由器或交换机的可能，如何利用已改造的有限的功能节点来完成与其新型应用需求线性逼近的网络性能，这就是OVERLAY网络目前所热衷研究的问题。就组播问题来说，所有节点都具有组播功能的网络称为全组播网络，这是为简化问题的研究，而对网络参数进行的极度弱化，过去包括目前所提出的几乎所有的组播路由算法，虽然解决问题所使用的技术会有所不同，比如启发式，蚂蚁或遗传，但都是针对全组播网络而言。显然这些在全组播网络基础上所提出的算法，距真正的应用于实际网络，还有很大的距离。                                      2 MON组播树问题的描述 目前在实际的网络环境中，具有组播功能的结点的比率还不是很高，大约只有20%左右(2000年为17%)。而如何利用不足五分之一的组播功能节点来完成组播应用的需求呢？这就是我们研究组播OVERLAY网络的初衷。网络中只有部分节点具有组播功能的网络我们称其为部分组播网络。在部分组播网络中，所有的具有组播功能的节点就构成了对整个网络的一个组播覆盖（multicast overlay）,因此对部分组播网络组播问题的研究就转化为覆盖网络路由研究的一部分。组播覆盖网络组播树与全组播网络组播树的不同之处在于，前者会包含很多重复的链路，而后者则没有。因为组播覆盖网络中，如果从一个节点到几个节点的路径中有相同的链路，而相同链路中的节点如不具有组播功能，则这些相同的链路就无法共享。因此在组播覆盖网络中，组播树的求解问题，就与一般定义的全组播网络的组播树的求解问题有所不同。 本文中有如下定义 定义1.1：在MON组播覆盖网络中，具有组播功能的结点为MV(multicastable Vertex)节点，反之，不具有组播功能的结点称为NMV(Non-multicastable Vertex)节点。 定义1-2：组播覆盖网络组播树：给定一个网络有向图G=(V,M,E,C),V由MV结点(组播功能结点)和NMV结点(非组播功能结点)组成，MV结点的集合为M，E为图中所有边的集合，C为边所对应的权值的集合，从V中选择一组结点(terminal)D,一个源结点s D,从G中生成一个树T=(VT，MT，ET，CT)，使得树的费用最小，生成的树就称为组播树，其中TG ，VT V，DVT，，MTVT，ETE，T中的源结点s到每一个D中的结点都有通路，且s的入度为0，其中非端结点的NMV结点入度与出度相等，而非端结点的MV结点的出度至少等于其入度。 1基金项目：高等学校博士学科点专项科研基金资助课题（20030290003） 定义1-3：最短路径：结点u,vV之间的最短路径是指从u到v的费用最小的路径，用P(u,v)表示，若沿P(u,v)的结点有u,v0,v1…vk-1,vk,v,则P(u,v)={u,v0,v1…vk-1,vk,v}。结点到树的最短路径是指结点到该树所有结点中路径最短的那一条。 定义1-4：组播覆盖网络组播树费用CT：设组播树T中的链路有N条，而其中某一非组播链路如果出现的次数为ni次，如图3-1中边E(2，4)：则组播树的总费用可表示成为： CT   3 MON动态组播树问题的描述 动态路由优化问题是多点通信所特有的。在点到点通信中，不会有第三方的介入。如果其中有一方想离开，整个通信进程也就终止了，因此不存在动态路由问题。而在多点通信中，参与通信组的成员可以随时地离开，新的结点也可以随时地加入而不影响整个通信进程。通信成员的动态性决定了多点路由的动态性。当然，动态路由的概念还可以扩展。由于链路失败、局部拥塞、网络拓扑变化等原因使某些成员脱离了通信组，那么这些成员重新加入到通信组的过程也就相当于一个新成员的加入过程。静态路由优化是在通信开始之前，在一组己知的成员之间，利用某种优化算法来寻找路由。而对于动态路由，由于无法事先预测哪些成员将会加入或离开通信组。原则上还要求路由调整时对其它成员不造成影响或影响的程度很小。因此，动态路由的优化问题比静态路由的更为复杂，但其研究成果却对实际网络更具现实意义。 多点动态路由优化同样可分为网络费用优化和目的地费用优化。由于目的地费用优化与目的结点加入或离开通信组的次序无关，只与该目的结点和源有关，因此动态路由中目的地费用优化问题和静态路由中目的地费用优化问题是一样的。本文主要研究动态路由中网络费用优化问题。如不作特别说明，动态路由优化专指动态路由的网络费用优化。 动态路由网络费用优化问题可以描述为：给定连通的的平面图G＝(V，E，c)。G有n个顶点，m条边，即 ，，边费用函数c：ER+。r是组成员更新请求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，(加入，离开)。除了撤消整个通信进程的请求之外，每次请求只包括一个结点。 在ri请求后的组成员集合Si为： 因为Si集合不知道请求rj(j>I)的情况，所以动态路由优化属于在线问题。 动态路由优化问题可以分为四大类： 1．不允许结构重组的路由优化方案：指在有成员离开或新结点加入到通信组时，优化路由的原则，是对通信组内的其他成员的通信路径不作改动。 2．完全结构重组的路由优化方案：指在现有的成员之间建立一个网络费用最优路由树。一旦有成员离开通信组或有新结点加入通信组，在更新后的成员之间再建立一个网络费用最优路由树。这实际上是退化到静态路由优化问题。 3．部分结构重组的路由优化方案：指在成员更新后，只对路由树的某些部分进行调整，被调整的路由链路数不超过一定上限。避免了全局调整的复杂计算，同时也将对其它成员的影响降低到最小。 4．触发结构重组的路由优化方案：指在成员更新后，开始按不允许结构重组的优化方案来更新路由，同时监视更新后路由树的费用。一旦路由树费用与最优费用之比超过某个门限值，就进行一次结构重组。这时的结构重组可能是完全结构重组，也可能是部分结构重组。触发结构重组的优化方案减少了路由重组的次数，节省了计算费用，并可将路由树的费用和最优费用之比维持在一定的水平。它的缺点也在于没有从根本上克服路由结构重组带来的问题，并且需要不断监视路由树的费用，会增加路由优化的复杂性和额外开销。 4 MON动态组播路由算法PRRN-N 全组播网络的组播树生成算法目前已提出了很多，在其时间复杂度可以忍受的前提下，目前所提出的算法大多是在寻求次优解，许多用启发式算法或者遗传算法、蚂蚁算法等求解组播路由问题的文章相继发表。然而应该认识到，启发式算法有其自身的缺陷，即只能找到局部最优，遗传算法和蚂蚁算法虽然都是全局算法，但是其编解码方法都比较复杂，个体编解码复杂度为O(n2)~ O(n3)。另外，目前对组播路由问题的表述模型尚不统一。所以，在此本文利用简洁的Prüfer编码，通过构造完全图的方式，把MON组播树“树核”的求解问题改为全组播路由问题来求解，以得到更快的通用的全组播网络组播树的遗传算法。 4．1　PRRN－N覆盖层组播“树核”生成算法 MON中具有组播功能的结点，其组播路由问题的概念模型可以表示为：设网络G(V,E)，V是节点 (表示所有具有组播功能及非组播功能结点的总和)的集合, E是边(表示节点之间的点到点连接)的集合，边权表示节点之间的组播代价。 给定源的集合 ,具有组播功能的结点集合，对要求解一棵满足网络费用代价最小的组播树，使得：T以s为根节点，且，这里VT表示T的节点集合。 先将V中的带有组播功能的结点集合D中的所有结点，以Dijkstra算法由图G中的最短路构造其完全图Kn，E是边(任两组播结点之间的连接)的集合，边权表示结点之间的“组播代价”，在此为图G中两点间的最短路。 完全图Kn的不同生成树共有nn-2棵，正好可以用n-2位的n-进制整数来表示，每位数字都在[1..n]之间，它对应为Kn的节点编号，这就是Prüfer编码，它为设计基于生成树的优化问题的遗传算法提供了最简洁的编码方案之一。由Prüfer序列到生成树T的解码算法seqToTree如下：  算法1   seqToTree [算法开始] 输入：Prüfer编码序列P； 输出：Kn的生成树T； [算法开始] 确定节点数n:=P的长度+2； 统计每个节点在P中的出现次数A[1..n]； 生成具有n个孤立节点的图T,节点依次标记为1,2,…,n； 令Q为T的所有不在P中的节点编号集合,并非减有序； 当P非空，循环做 从P中移出第一个元素v, 从Q中移出第一个元素u, A[v]:=A[v]-1； 在T中增加边<v,u>； 如果A[v]=0, 则折半插入v到Q中； 从Q中移出最后两个元素v和u, 在T中增加边<v,u>； 输出T. [算法结束] 由于Prüfer编码代表的生成树是无序树（不指定根），而组播树需要指定根，所以我们扩充Prüfer编码为n-1位，最后一位代表根节点编号。另外，还需要对解码得到的Kn的生成树进行剪枝，删除不在组播终点集D中的叶子节点才能得到所求的组播树，剪枝算法prune的设计见如下： 算法2   prune 输入：Kn的生成树T,组播终点集合D; 输出：组播树T； [算法开始] 对T做后根次序遍历,一边遍历一边做： a)如果当前被遍历节点v是叶子节点并且不在D中,则: 从T中删除v； 输出T. [算法结束] 遗传算法设计： 遗传算法基于达尔文进化论的思想，将待求问题的解空间看成自然界，将解空间中的每个变量的目标函数值看成个体对环境的适应性，然后通过（自然）选择、交叉、变异等遗传操作不断进化，在一个可以接受的时间内到达一代比较优秀的种群，其中包含了我们要求的最优或近似最优个体。 一个特定的遗传算法主要由染色体编码、种群初始化、适应值标定和遗传算子（选择、交叉和变异）设计等方面组成。基于前面的讨论，我们设计了求解模型的遗传算法：染色体用扩充的Prüfer编码表示；给定具有n个节点的网络G和种群规模P后，初始种群由随机生成的P行n-1列的矩阵表示，其中的每个元素为[1..n]之间的整数，代表G中的节点编号；计算每个染色体（Prüfer序列）的适应值时，依次用算法seqToTree和prune得到组播树T，通过计算该个体的优化目标值g，再对g做标定得到个体适应值f=1/(1+g)；选择算子采用改进的一次旋转赌轮方法；交叉算子采用随机多点交叉；变异算子采用基因位变异和基因片变异（包括迁移和翻转）；保优策略，即每代最优秀个体直接进入下一代而不参与交叉和变异。  算法复杂性分析： 从算法中可以看出，对每一染色体解码求生成树的复杂度为O(nlogn)，对生成树进行剪枝得到组播分布树的算法复杂度为O(n)；而对得到的组播树进行优化目标值计算和适应值标定所需要的复杂度可以从如下方面分析： 根据Dijkstra的算法，计算每对节点间最短路径需要O(n3)的复杂度。但是，我们注意到是在给定的组播树T中，若求解的是有源树，给定组播源点s后，对任意的d，计算节点对(s,d)之间的距离时只需从s出发对T做一次遍历即可，复杂度为O(n)；若计算的是共享树，则对任意的组播源点s，组播信息都是先从s通过第一跳单播到共享根，再从共享根到达每个组播终点d，所以计算节点对(s,d)之间的距离时也只需从共享根出发对T做一次遍历，复杂度也为O(n)；   交叉算子和变异算子的复杂度均不超过O(n)； 于是，给定群规模P和最大进化代数maxG，该算法的计算复杂度为O(P×maxG×O(mlogm))式中m为组播功能结点数，相对于求解同类问题的其它算法而言，这个结果确实令人鼓舞。所有利用遗传算法求解组播路由问题的算法都需要进行优化目标值的计算和适应值标定，以上的设计实现了一种更快的求解全组播网络组播路由问题的遗传算法。然而，应该注意的是，Prüfer数表示的是Kn的生成树，而不是给定网络G(V,E),|V|=n的生成树；组播数T也不是G的生成树，而是针对组播源点集S和组播功能结点集MV的steiner树。在求得最优解后，需要将得到的组播树按图G中的最短路展开，并对相同路作归并操作。以此才能得到所求部分组播网络组播生成树的“树核”。如图1.   图1　覆盖层组播“树核”生成 4.2　PRRH-N结点动态加入算法： [算法开始]    1)以部分组播网络基于网络费用最优的静态组播树生成算法先生成动态组播树的“树核”T。 2)当新的一个结点Di要加入组播组时，先计算其到“树核”T中各组播结点MVi(其取值范围是MVS集合的成员)的最短路。 3)比较此结点Di到源s的最短路近还是到离它最近的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 4)如到最近的MVi近，则检查此MVi是否已是组播组内成员(本身是端结点或有别的结点通过此组播功能结点接入组播组)，如是，以此MVi结点为“登陆结点”接入组播组(如有两个结点满足要求，选择距s近的那一MV结点)。树中加入结点Di及其到此MVi结点的边 5)如最近的MVi结点还不是组内结点，则向它注册, 并告之此Di到它的最短路是多少及到源的最短路是多少，同时计算所有向此结点注册的结点经它连入组播树的费用和是否小于直连源的费用和，如是所有注册结点由其连入组播树，反之计算此Di到“树核”T上各组播功能结点MVi及MVi到源s的最短路径的值,找到T中含有组播结点MVi的到源s的最短路Pmin，比较此结点Di到源s的最短路近还是到拥有Pmin的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 6)反之，选择此拥有Pmin的组播结点MVi作为此结点的“登陆结点”连入组播组(如有多点满足要求，选择距s远的那一MV结点)。并在组播树中加入Pmin边。 [算法结束] 如图2.       图2. PRRH-N结点动态加入算法 4.3　PRRH-N结点动态退出算法： [算法开始] 1)如果此结点是直联到源的，且路径中没有别的组内成员，则将路中所有的结点从树中删除。并在距此点最近的MVi结点注消此结点 2)如果此结点是直联到源的，但路径中还有别的组内成员，则将此结点删除直到另一组内成员成为叶子结点为止。在距此点最近的MVi结点注消此结点的同时，注消新的叶子结点，并对这一刚成为叶子结点的组内成员用动态结点加入算法重新加入组播组。 3)如果此结点是联到“树核”T中的组播功能结点MVi上的，且MVi上还连着其它的组内成员，在删除此结点的同时，要计算所有经此MVi结点连入组播组的结点至源s的费用总和是否大于其向源直联的费用总和。如是注消这些结点，并用动态结点加入算法将这些结点重新加入组播组。 [算法结束]                           5 MON动态组播路由算法PRRN-D 目的地费用最优路由算法是用来优化路由的目的地费用。如果是点到点通信，那么目的地费用最优也就是网络费用最优。但在多点通信中，两者并不等价。在点到多点通信中，可以先计算源到每个目的结点的费用最优路径。然后将这些路径合并(全组播网络)。路径中相同的链路可以被共享。形成的路由树称为目的地费用最优组播路由树。虽然目的地费用最优组播路由树的网络费用不一定是最优的，但可以推测它的网络费用至少不会太差。并且目的地费用最优路由树的网络费用与目的结点加入或离开通信组的先后次序无关，这对于动态路由的优化是有益的。因此目的地费用最优路由算法也可以在多点动态路由中优化网络费用。 5.1 PRRH-D覆盖层组播“树核”生成算法  MON中具有组播功能的节点亦可依据目的地费用最优的思想，以启发的方法高速构成PRRN－D覆盖层组播“树核”。其算法如下： [算法开始] 1)选择组播功能结点集合MVS的成员，各组播功能结点先对组播源点s以Dijkstra算法最短路寻路，然后执行“归并操作”即合并相同边，“归并操作”后的组播树即为我们所要求的部分组播网络组播树的“树核”。 2)对“归并操作”后的组播结点“树核”，计算每一个组播结点到源s的路径长度，并写入各组播结点的路由表。 [算法结束] 5.2　PRRH-D结点动态加入算法： [算法开始] 1)以部分组播网络基于目的地费用最优的静态组播树生成算法先生成动态组播树的“树核”T。 2)当新的一个结点Di要加入组播组时，先计算其到“树核”T中各组播结点MVi(其取值范围是MVS集合的成员)的最短路。 3)比较此结点Di到源s的最短路近还是到离它最近的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 4)如到最近的MVi近，则检查此MVi是否已是组播组内成员(本身是端结点或有别的结点通过此组播功能结点接入组播组)，如是，以此MVi结点为“登陆结点”接入组播组(如有两点满足要求，选择距s近的那一MV结点)。树中加入结点Di及其到此MVi结点的边 5)如最近的MVi结点还不是组内结点，则向它注册, 并告之此Di到它的最短路是多少及到源的最短路是多少，同时计算所有向此结点注册的结点经它连入组播树的费用和是否小于直连源的费用和，如是所有注册结点由其连入组播树，反之计算此Di到“树核”T上各组播功能结点MVi及MVi到源s的最短路径的值,找到T中含有组播结点MVi的到源s的最短路Pmin，比较此结点Di到源s的最短路近还是到拥有Pmin的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 6)反之，选择此拥有Pmin的组播结点MVi作为此结点的“登陆结点”连入组播组(如有两点满足要求，选择距s远的那一MV结点)。并在组播树中加入Pmin边。 [算法结束] 5.3　PRRH-D结点动态退出算法： [算法开始] 1)如果此结点是直联到源的，且路径中没有别的组内成员，则将路中所有的结点从树中删除。并在距此点最近的MVi结点注消此结点 2)如果此结点是直联到源的，但路径中还有别的组内成员，则将此结点删除直到另一组内成员成为叶子结点为止。在距此点最近的MVi结点注消此结点的同时，注消新的叶子结点，并对这一刚成为叶子结点的组内成员用动态结点加入算法重新加入组播组。 3)如果此结点是联到“树核”T中的组播功能结点MVi上的，且MVi上还连着其它的组内成员，在删除此结点的同时，要计算所有经此MVi结点连入组播组的结点至源s的费用总和是否大于其向源直联的费用总和。如是，则注消这些结点，并用动态结点加入算法将这些结点重新加入组播组。 [算法结束] 以上算法参见图画3. 图3　覆盖层组播“树核”生成及节点动态加入、退出举例 6 两种算法复杂度及网络模拟 PRRH-D算法：其组播结点树核生成时，采用的是Dijkstra算法，然后对各组播结点向源结点s所寻到的最短路进行归并，设其MV结点数为m，网络规模即网络中总的结点数为n，则其树核生成最坏情况下时间复杂度为 。而各终端结点加入组播组时每一结点最坏情况下要调用Dijkstra算法三次，分别对源结点s及树核内距终端结点Di最近的MV结点和具有P(Di,MVi,s)min的MV结点寻最短路，最坏情况下，每一终端结点最终加入组播组的时间复杂度为。PRRH-D算法的每一结点退出操作的最差情况的时间复杂度为，t为组播树中所含的结点数，而因此而选择重新选路的各终端结点需再次调用Dijkstra算法三次，如这部分结点数为r,则最坏情况下，这部分终端结点最终加入组播组的时间复杂度为。 PRRH-N算法属于源路由算法(source-rooted routing)。源路由算法的结点经某一路由协议(如链路状态协议)获得完整的网络拓朴信息。网络中每一结点的拓朴信息是一样的，所以网络中每一结点都可以接受用户呼叫并进行路由计算。假设网络状态信息在算法执行之前已经完成，且在算法计算路由时，网络的拓朴状态不变。则NCH及DCH算法的时间复杂度的计算就可以分为两个独立的两个部分(组播结点树核的生成及终端结点最终完成加入组播组)来计算，综述如下： 其组播组结点树核生成时，首先要以组播功能结点间的最短路生成其全连通网络。采用Dijkstra算法，各组播结点及源结点s间彼此最短路寻径，设其MV结点数为m，网络规模即网络中总的结点数为n，则组播功能结点全连通网络生成在最坏情况下时间复杂度为。而树核生成的遗传算法和seqToTree算法的时间复杂度为O(P×maxG×O(mlogm))。同样每一终端结点加入组播组时每一结点最坏情况下要调用Dijkstra算法三次，分别对源结点s及树核内距终端结点Di最近的MV结点和具有P(Di,MVi,s)min的MV结点寻最短路，最坏情况下，每一终端结点最终加入组播组的时间复杂度为。PRRH-N算法的每一结点退出操作的最差情况的时间复杂度为，t为组播树中所含的结点数，而因此选择重新选路的各终端结点需再次调用Dijkstra算法三次，如这部分结点数为r,则最坏情况下，这部分终端结点最终加入组播组的时间复杂度为。 由于两种算法都采用了分布式触发的思想，无需覆盖层对整体的费用做出监控及评价，故而从基础解决了原触发重组费用优化方案的缺点，减轻了路由优化的复杂性和额外开销。 目前对于MON网络动态组播树的生成算法，还没有研究人员进行过系统的研究，因此也还没有基准算法来用于网络模拟和比较。因此，本文的网络模拟只能采用课题组MON静态组播树生成算法NCH来作为模拟基准。 ·图4  PRRH-N，PRRH-D算法EAD仿真网络模拟数据 本文以课题组EAD仿真模型所生成的模拟网络来做模拟平台，在EAD算法生成的模拟网络过程中，其MV结点比例是固定的(17%)，而长短边之比随着不同的需求，通过对 及F2的调节，也可以被定位于一很小的领域内，所以在同一网络规模前提下影响部分组播网络动态组播树生成算法的可变因素主要有：1.加入组播组的端结点的更新速度,2.在某一时刻，组播组成员数量在模拟网络的全部结点中所占的比例，对于这两点，都可以以一个无量纲的概念，对不同的网络规模进行一致的模拟，以利于后期实验结果的比较。 本文采用以下假设：加入组播组的端结点以一种稳定的速度进行更新，即某一时刻有占网络结点总数5%的组播组成员退出组播组，而另有占网络结点总数5%的非组播组成员加入组播组，而初始状态选择组播组成员占总结点数的20%和40%来进行模拟。这样就有可能选择相同的静态部分组播网络组播树生成算法来作为待模拟算法的基准算法，以便能从本质上把握待模拟算法的一些基本特征，并给出其性能评价。 由模拟数据可知(见图4)，PRRH-N和PRRH-D算法因为可以在结点加入组播组及结点退出组播组时都能触发树结构的部分重组。所以其费用能够被限定在基准以上的一个很小的区域内，因为考虑到现实网络中的实现问题，两种算法都没有终端结点向上归并的操作，所以，实验中可见费用会出现“跃点”，特别是当组播组成员比例相对较小时，这一点表现的尤为突出。在组播组成员比例进一步增加时，两种算法都表现出很好的收敛性，而且其费用的统计平均值也均被限定在不高于基准的10%，这一结果还是非常令人鼓舞的。 7  结束语 PRRH-N算法在费用优化方面是两种算法中最优的，基于结点费用最优触发重组操作，能最大限度的减小算法的散列跃度，算法收敛性能够有一个很好保证，但时间复杂度整体来说过大，在实际应用中，可操作性要明显低于PRRH-D算法。但在组播组成员相对较少时，对费用优化苛刻的前提下，该算法还是应该成为首选的。 PRRH-D算法在时间复杂度方面较PRRH-N算法为优，而其网络费用优化又明显的线性逼近 PRRH-N算法，在组播组成员比例达到40%左右时，该算法的费用优化性能已近似等于PRRH-N算法， 故在对算法计算时间及费用优化都有较高要求时，还是选用PRRH-D算法为好。 因两种算法都是基于“树核”的，所以两种算法都可以在一定路由协议的支持下进行多面体分级路由模式的改良，也可以方便的向多点对多点组播路由算法改进，这样就能够使算法在可扩展性方面有一个质的提高，同时也可以使其向多点对多点路由计算提供良好的支持。其次，基于“树核”的路由方式，也可以在链路负载平衡方面较原有的CBT算法(原针对全组播网络的一种多对多组播路由算法)有一个质的提高。以上方案都将是今后对于部分组播网络路由算法研究的很好的方向。 参考文献 [1]   董庆阳,  计算机通信网络组播路由算法和协议的研究, 上海交通大学博士学位论文, 2000年 [2]   王征应,  高速网络QOS路由技术的研究及路由仿真平台的研制, 华中科技大学博士学位论文, 2001年 [3]   李汉兵, 计算机网络路由算法, 西安电子科技大学博士学位论文, 2000年 [4]   Yunxi Sherlia Shi . Design of Overlay Networks for Internet Multicast.(PhD thesis ).[D]. Washington University. August, 2002 [5]   G.N.Rouskas and I.Baldine. Multicast Rjouting with End-to-End Delay and Delay Variation Constraints. IEEE Journal on selected Areas in Communications, 1997, Vol.15:346-356 [6]   Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active Distributed Dynamic Routing on the Multicast Overlay Network YU Zhenwei, LIU Kejian China University of Mining and Technology-Beijing, Beijing, 100083 zwyu@cumtb.edu.cn Abstract ： This text gives a definition for the dynamic routing in MON the Multicast Overlay Network, and put forward the problems of the dynamic route computing should be considerated for the first time, and a Arithmetic PRRH-N & PRRH-D according to the distributing triggers the reorganization , in the end ,the report  calculate the complexity of the Arithmetic , simulate the PRRH-N on the model of EAD . Key words:  overlay ; multicast ; dynamic routing ; distributed triggers the reorganization  余镇危, 刘克俭　  中国矿业大学(北京)，北京，100083 zwyu@cumtb.edu.cn  摘要：本文给出了组播覆盖网络MON动态路由的定义，并在此基础上提出了MON动态组播路由计算所应考虑的问题，给出了基于分布式触发重组的MON动态组播路由算法NPPR-N和NPPR-D，并在本文的最后对算法的复杂度进行了推证，对算法的有效性进行了以EAD模型为基础平台的网络模拟。 关键词：OVERLAY；组播；动态路由；分布式触发重组 1　引言 现实的网络环境，还不具备为实现某一种应用而全部改造或重新定制现有路由器或交换机的可能，如何利用已改造的有限的功能节点来完成与其新型应用需求线性逼近的网络性能，这就是OVERLAY网络目前所热衷研究的问题。就组播问题来说，所有节点都具有组播功能的网络称为全组播网络，这是为简化问题的研究，而对网络参数进行的极度弱化，过去包括目前所提出的几乎所有的组播路由算法，虽然解决问题所使用的技术会有所不同，比如启发式，蚂蚁或遗传，但都是针对全组播网络而言。显然这些在全组播网络基础上所提出的算法，距真正的应用于实际网络，还有很大的距离。                                      2 MON组播树问题的描述 目前在实际的网络环境中，具有组播功能的结点的比率还不是很高，大约只有20%左右(2000年为17%)。而如何利用不足五分之一的组播功能节点来完成组播应用的需求呢？这就是我们研究组播OVERLAY网络的初衷。网络中只有部分节点具有组播功能的网络我们称其为部分组播网络。在部分组播网络中，所有的具有组播功能的节点就构成了对整个网络的一个组播覆盖（multicast overlay）,因此对部分组播网络组播问题的研究就转化为覆盖网络路由研究的一部分。组播覆盖网络组播树与全组播网络组播树的不同之处在于，前者会包含很多重复的链路，而后者则没有。因为组播覆盖网络中，如果从一个节点到几个节点的路径中有相同的链路，而相同链路中的节点如不具有组播功能，则这些相同的链路就无法共享。因此在组播覆盖网络中，组播树的求解问题，就与一般定义的全组播网络的组播树的求解问题有所不同。 本文中有如下定义 定义1.1：在MON组播覆盖网络中，具有组播功能的结点为MV(multicastable Vertex)节点，反之，不具有组播功能的结点称为NMV(Non-multicastable Vertex)节点。 定义1-2：组播覆盖网络组播树：给定一个网络有向图G=(V,M,E,C),V由MV结点(组播功能结点)和NMV结点(非组播功能结点)组成，MV结点的集合为M，E为图中所有边的集合，C为边所对应的权值的集合，从V中选择一组结点(terminal)D,一个源结点s D,从G中生成一个树T=(VT，MT，ET，CT)，使得树的费用最小，生成的树就称为组播树，其中TG ，VT V，DVT，，MTVT，ETE，T中的源结点s到每一个D中的结点都有通路，且s的入度为0，其中非端结点的NMV结点入度与出度相等，而非端结点的MV结点的出度至少等于其入度。 1基金项目：高等学校博士学科点专项科研基金资助课题（20030290003） 定义1-3：最短路径：结点u,vV之间的最短路径是指从u到v的费用最小的路径，用P(u,v)表示，若沿P(u,v)的结点有u,v0,v1…vk-1,vk,v,则P(u,v)={u,v0,v1…vk-1,vk,v}。结点到树的最短路径是指结点到该树所有结点中路径最短的那一条。 定义1-4：组播覆盖网络组播树费用CT：设组播树T中的链路有N条，而其中某一非组播链路如果出现的次数为ni次，如图3-1中边E(2，4)：则组播树的总费用可表示成为： CT   3 MON动态组播树问题的描述 动态路由优化问题是多点通信所特有的。在点到点通信中，不会有第三方的介入。如果其中有一方想离开，整个通信进程也就终止了，因此不存在动态路由问题。而在多点通信中，参与通信组的成员可以随时地离开，新的结点也可以随时地加入而不影响整个通信进程。通信成员的动态性决定了多点路由的动态性。当然，动态路由的概念还可以扩展。由于链路失败、局部拥塞、网络拓扑变化等原因使某些成员脱离了通信组，那么这些成员重新加入到通信组的过程也就相当于一个新成员的加入过程。静态路由优化是在通信开始之前，在一组己知的成员之间，利用某种优化算法来寻找路由。而对于动态路由，由于无法事先预测哪些成员将会加入或离开通信组。原则上还要求路由调整时对其它成员不造成影响或影响的程度很小。因此，动态路由的优化问题比静态路由的更为复杂，但其研究成果却对实际网络更具现实意义。 多点动态路由优化同样可分为网络费用优化和目的地费用优化。由于目的地费用优化与目的结点加入或离开通信组的次序无关，只与该目的结点和源有关，因此动态路由中目的地费用优化问题和静态路由中目的地费用优化问题是一样的。本文主要研究动态路由中网络费用优化问题。如不作特别说明，动态路由优化专指动态路由的网络费用优化。 动态路由网络费用优化问题可以描述为：给定连通的的平面图G＝(V，E，c)。G有n个顶点，m条边，即 ，，边费用函数c：ER+。r是组成员更新请求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，(加入，离开)。除了撤消整个通信进程的请求之外，每次请求只包括一个结点。 在ri请求后的组成员集合Si为： 因为Si集合不知道请求rj(j>I)的情况，所以动态路由优化属于在线问题。 动态路由优化问题可以分为四大类： 1．不允许结构重组的路由优化方案：指在有成员离开或新结点加入到通信组时，优化路由的原则，是对通信组内的其他成员的通信路径不作改动。 2．完全结构重组的路由优化方案：指在现有的成员之间建立一个网络费用最优路由树。一旦有成员离开通信组或有新结点加入通信组，在更新后的成员之间再建立一个网络费用最优路由树。这实际上是退化到静态路由优化问题。 3．部分结构重组的路由优化方案：指在成员更新后，只对路由树的某些部分进行调整，被调整的路由链路数不超过一定上限。避免了全局调整的复杂计算，同时也将对其它成员的影响降低到最小。 4．触发结构重组的路由优化方案：指在成员更新后，开始按不允许结构重组的优化方案来更新路由，同时监视更新后路由树的费用。一旦路由树费用与最优费用之比超过某个门限值，就进行一次结构重组。这时的结构重组可能是完全结构重组，也可能是部分结构重组。触发结构重组的优化方案减少了路由重组的次数，节省了计算费用，并可将路由树的费用和最优费用之比维持在一定的水平。它的缺点也在于没有从根本上克服路由结构重组带来的问题，并且需要不断监视路由树的费用，会增加路由优化的复杂性和额外开销。 4 MON动态组播路由算法PRRN-N 全组播网络的组播树生成算法目前已提出了很多，在其时间复杂度可以忍受的前提下，目前所提出的算法大多是在寻求次优解，许多用启发式算法或者遗传算法、蚂蚁算法等求解组播路由问题的文章相继发表。然而应该认识到，启发式算法有其自身的缺陷，即只能找到局部最优，遗传算法和蚂蚁算法虽然都是全局算法，但是其编解码方法都比较复杂，个体编解码复杂度为O(n2)~ O(n3)。另外，目前对组播路由问题的表述模型尚不统一。所以，在此本文利用简洁的Prüfer编码，通过构造完全图的方式，把MON组播树“树核”的求解问题改为全组播路由问题来求解，以得到更快的通用的全组播网络组播树的遗传算法。 4．1　PRRN－N覆盖层组播“树核”生成算法 MON中具有组播功能的结点，其组播路由问题的概念模型可以表示为：设网络G(V,E)，V是节点 (表示所有具有组播功能及非组播功能结点的总和)的集合, E是边(表示节点之间的点到点连接)的集合，边权表示节点之间的组播代价。 给定源的集合 ,具有组播功能的结点集合，对要求解一棵满足网络费用代价最小的组播树，使得：T以s为根节点，且，这里VT表示T的节点集合。 先将V中的带有组播功能的结点集合D中的所有结点，以Dijkstra算法由图G中的最短路构造其完全图Kn，E是边(任两组播结点之间的连接)的集合，边权表示结点之间的“组播代价”，在此为图G中两点间的最短路。 完全图Kn的不同生成树共有nn-2棵，正好可以用n-2位的n-进制整数来表示，每位数字都在[1..n]之间，它对应为Kn的节点编号，这就是Prüfer编码，它为设计基于生成树的优化问题的遗传算法提供了最简洁的编码方案之一。由Prüfer序列到生成树T的解码算法seqToTree如下：  算法1   seqToTree [算法开始] 输入：Prüfer编码序列P； 输出：Kn的生成树T； [算法开始] 确定节点数n:=P的长度+2； 统计每个节点在P中的出现次数A[1..n]； 生成具有n个孤立节点的图T,节点依次标记为1,2,…,n； 令Q为T的所有不在P中的节点编号集合,并非减有序； 当P非空，循环做 从P中移出第一个元素v, 从Q中移出第一个元素u, A[v]:=A[v]-1； 在T中增加边<v,u>； 如果A[v]=0, 则折半插入v到Q中； 从Q中移出最后两个元素v和u, 在T中增加边<v,u>； 输出T. [算法结束] 由于Prüfer编码代表的生成树是无序树（不指定根），而组播树需要指定根，所以我们扩充Prüfer编码为n-1位，最后一位代表根节点编号。另外，还需要对解码得到的Kn的生成树进行剪枝，删除不在组播终点集D中的叶子节点才能得到所求的组播树，剪枝算法prune的设计见如下： 算法2   prune 输入：Kn的生成树T,组播终点集合D; 输出：组播树T； [算法开始] 对T做后根次序遍历,一边遍历一边做： a)如果当前被遍历节点v是叶子节点并且不在D中,则: 从T中删除v； 输出T. [算法结束] 遗传算法设计： 遗传算法基于达尔文进化论的思想，将待求问题的解空间看成自然界，将解空间中的每个变量的目标函数值看成个体对环境的适应性，然后通过（自然）选择、交叉、变异等遗传操作不断进化，在一个可以接受的时间内到达一代比较优秀的种群，其中包含了我们要求的最优或近似最优个体。 一个特定的遗传算法主要由染色体编码、种群初始化、适应值标定和遗传算子（选择、交叉和变异）设计等方面组成。基于前面的讨论，我们设计了求解模型的遗传算法：染色体用扩充的Prüfer编码表示；给定具有n个节点的网络G和种群规模P后，初始种群由随机生成的P行n-1列的矩阵表示，其中的每个元素为[1..n]之间的整数，代表G中的节点编号；计算每个染色体（Prüfer序列）的适应值时，依次用算法seqToTree和prune得到组播树T，通过计算该个体的优化目标值g，再对g做标定得到个体适应值f=1/(1+g)；选择算子采用改进的一次旋转赌轮方法；交叉算子采用随机多点交叉；变异算子采用基因位变异和基因片变异（包括迁移和翻转）；保优策略，即每代最优秀个体直接进入下一代而不参与交叉和变异。  算法复杂性分析： 从算法中可以看出，对每一染色体解码求生成树的复杂度为O(nlogn)，对生成树进行剪枝得到组播分布树的算法复杂度为O(n)；而对得到的组播树进行优化目标值计算和适应值标定所需要的复杂度可以从如下方面分析： 根据Dijkstra的算法，计算每对节点间最短路径需要O(n3)的复杂度。但是，我们注意到是在给定的组播树T中，若求解的是有源树，给定组播源点s后，对任意的d，计算节点对(s,d)之间的距离时只需从s出发对T做一次遍历即可，复杂度为O(n)；若计算的是共享树，则对任意的组播源点s，组播信息都是先从s通过第一跳单播到共享根，再从共享根到达每个组播终点d，所以计算节点对(s,d)之间的距离时也只需从共享根出发对T做一次遍历，复杂度也为O(n)；   交叉算子和变异算子的复杂度均不超过O(n)； 于是，给定群规模P和最大进化代数maxG，该算法的计算复杂度为O(P×maxG×O(mlogm))式中m为组播功能结点数，相对于求解同类问题的其它算法而言，这个结果确实令人鼓舞。所有利用遗传算法求解组播路由问题的算法都需要进行优化目标值的计算和适应值标定，以上的设计实现了一种更快的求解全组播网络组播路由问题的遗传算法。然而，应该注意的是，Prüfer数表示的是Kn的生成树，而不是给定网络G(V,E),|V|=n的生成树；组播数T也不是G的生成树，而是针对组播源点集S和组播功能结点集MV的steiner树。在求得最优解后，需要将得到的组播树按图G中的最短路展开，并对相同路作归并操作。以此才能得到所求部分组播网络组播生成树的“树核”。如图1.   图1　覆盖层组播“树核”生成 4.2　PRRH-N结点动态加入算法： [算法开始]    1)以部分组播网络基于网络费用最优的静态组播树生成算法先生成动态组播树的“树核”T。 2)当新的一个结点Di要加入组播组时，先计算其到“树核”T中各组播结点MVi(其取值范围是MVS集合的成员)的最短路。 3)比较此结点Di到源s的最短路近还是到离它最近的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 4)如到最近的MVi近，则检查此MVi是否已是组播组内成员(本身是端结点或有别的结点通过此组播功能结点接入组播组)，如是，以此MVi结点为“登陆结点”接入组播组(如有两个结点满足要求，选择距s近的那一MV结点)。树中加入结点Di及其到此MVi结点的边 5)如最近的MVi结点还不是组内结点，则向它注册, 并告之此Di到它的最短路是多少及到源的最短路是多少，同时计算所有向此结点注册的结点经它连入组播树的费用和是否小于直连源的费用和，如是所有注册结点由其连入组播树，反之计算此Di到“树核”T上各组播功能结点MVi及MVi到源s的最短路径的值,找到T中含有组播结点MVi的到源s的最短路Pmin，比较此结点Di到源s的最短路近还是到拥有Pmin的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 6)反之，选择此拥有Pmin的组播结点MVi作为此结点的“登陆结点”连入组播组(如有多点满足要求，选择距s远的那一MV结点)。并在组播树中加入Pmin边。 [算法结束] 如图2.       图2. PRRH-N结点动态加入算法 4.3　PRRH-N结点动态退出算法： [算法开始] 1)如果此结点是直联到源的，且路径中没有别的组内成员，则将路中所有的结点从树中删除。并在距此点最近的MVi结点注消此结点 2)如果此结点是直联到源的，但路径中还有别的组内成员，则将此结点删除直到另一组内成员成为叶子结点为止。在距此点最近的MVi结点注消此结点的同时，注消新的叶子结点，并对这一刚成为叶子结点的组内成员用动态结点加入算法重新加入组播组。 3)如果此结点是联到“树核”T中的组播功能结点MVi上的，且MVi上还连着其它的组内成员，在删除此结点的同时，要计算所有经此MVi结点连入组播组的结点至源s的费用总和是否大于其向源直联的费用总和。如是注消这些结点，并用动态结点加入算法将这些结点重新加入组播组。 [算法结束]                           5 MON动态组播路由算法PRRN-D 目的地费用最优路由算法是用来优化路由的目的地费用。如果是点到点通信，那么目的地费用最优也就是网络费用最优。但在多点通信中，两者并不等价。在点到多点通信中，可以先计算源到每个目的结点的费用最优路径。然后将这些路径合并(全组播网络)。路径中相同的链路可以被共享。形成的路由树称为目的地费用最优组播路由树。虽然目的地费用最优组播路由树的网络费用不一定是最优的，但可以推测它的网络费用至少不会太差。并且目的地费用最优路由树的网络费用与目的结点加入或离开通信组的先后次序无关，这对于动态路由的优化是有益的。因此目的地费用最优路由算法也可以在多点动态路由中优化网络费用。 5.1 PRRH-D覆盖层组播“树核”生成算法  MON中具有组播功能的节点亦可依据目的地费用最优的思想，以启发的方法高速构成PRRN－D覆盖层组播“树核”。其算法如下： [算法开始] 1)选择组播功能结点集合MVS的成员，各组播功能结点先对组播源点s以Dijkstra算法最短路寻路，然后执行“归并操作”即合并相同边，“归并操作”后的组播树即为我们所要求的部分组播网络组播树的“树核”。 2)对“归并操作”后的组播结点“树核”，计算每一个组播结点到源s的路径长度，并写入各组播结点的路由表。 [算法结束] 5.2　PRRH-D结点动态加入算法： [算法开始] 1)以部分组播网络基于目的地费用最优的静态组播树生成算法先生成动态组播树的“树核”T。 2)当新的一个结点Di要加入组播组时，先计算其到“树核”T中各组播结点MVi(其取值范围是MVS集合的成员)的最短路。 3)比较此结点Di到源s的最短路近还是到离它最近的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 4)如到最近的MVi近，则检查此MVi是否已是组播组内成员(本身是端结点或有别的结点通过此组播功能结点接入组播组)，如是，以此MVi结点为“登陆结点”接入组播组(如有两点满足要求，选择距s近的那一MV结点)。树中加入结点Di及其到此MVi结点的边 5)如最近的MVi结点还不是组内结点，则向它注册, 并告之此Di到它的最短路是多少及到源的最短路是多少，同时计算所有向此结点注册的结点经它连入组播树的费用和是否小于直连源的费用和，如是所有注册结点由其连入组播树，反之计算此Di到“树核”T上各组播功能结点MVi及MVi到源s的最短路径的值,找到T中含有组播结点MVi的到源s的最短路Pmin，比较此结点Di到源s的最短路近还是到拥有Pmin的组播结点MVi的最短路近，如到源近直联到源。在树中加入结点Di及其到源的边。 6)反之，选择此拥有Pmin的组播结点MVi作为此结点的“登陆结点”连入组播组(如有两点满足要求，选择距s远的那一MV结点)。并在组播树中加入Pmin边。 [算法结束] 5.3　PRRH-D结点动态退出算法： [算法开始] 1)如果此结点是直联到源的，且路径中没有别的组内成员，则将路中所有的结点从树中删除。并在距此点最近的MVi结点注消此结点 2)如果此结点是直联到源的，但路径中还有别的组内成员，则将此结点删除直到另一组内成员成为叶子结点为止。在距此点最近的MVi结点注消此结点的同时，注消新的叶子结点，并对这一刚成为叶子结点的组内成员用动态结点加入算法重新加入组播组。 3)如果此结点是联到“树核”T中的组播功能结点MVi上的，且MVi上还连着其它的组内成员，在删除此结点的同时，要计算所有经此MVi结点连入组播组的结点至源s的费用总和是否大于其向源直联的费用总和。如是，则注消这些结点，并用动态结点加入算法将这些结点重新加入组播组。 [算法结束] 以上算法参见图画3. 图3　覆盖层组播“树核”生成及节点动态加入、退出举例 6 两种算法复杂度及网络模拟 PRRH-D算法：其组播结点树核生成时，采用的是Dijkstra算法，然后对各组播结点向源结点s所寻到的最短路进行归并，设其MV结点数为m，网络规模即网络中总的结点数为n，则其树核生成最坏情况下时间复杂度为 。而各终端结点加入组播组时每一结点最坏情况下要调用Dijkstra算法三次，分别对源结点s及树核内距终端结点Di最近的MV结点和具有P(Di,MVi,s)min的MV结点寻最短路，最坏情况下，每一终端结点最终加入组播组的时间复杂度为。PRRH-D算法的每一结点退出操作的最差情况的时间复杂度为，t为组播树中所含的结点数，而因此而选择重新选路的各终端结点需再次调用Dijkstra算法三次，如这部分结点数为r,则最坏情况下，这部分终端结点最终加入组播组的时间复杂度为。 PRRH-N算法属于源路由算法(source-rooted routing)。源路由算法的结点经某一路由协议(如链路状态协议)获得完整的网络拓朴信息。网络中每一结点的拓朴信息是一样的，所以网络中每一结点都可以接受用户呼叫并进行路由计算。假设网络状态信息在算法执行之前已经完成，且在算法计算路由时，网络的拓朴状态不变。则NCH及DCH算法的时间复杂度的计算就可以分为两个独立的两个部分(组播结点树核的生成及终端结点最终完成加入组播组)来计算，综述如下： 其组播组结点树核生成时，首先要以组播功能结点间的最短路生成其全连通网络。采用Dijkstra算法，各组播结点及源结点s间彼此最短路寻径，设其MV结点数为m，网络规模即网络中总的结点数为n，则组播功能结点全连通网络生成在最坏情况下时间复杂度为。而树核生成的遗传算法和seqToTree算法的时间复杂度为O(P×maxG×O(mlogm))。同样每一终端结点加入组播组时每一结点最坏情况下要调用Dijkstra算法三次，分别对源结点s及树核内距终端结点Di最近的MV结点和具有P(Di,MVi,s)min的MV结点寻最短路，最坏情况下，每一终端结点最终加入组播组的时间复杂度为。PRRH-N算法的每一结点退出操作的最差情况的时间复杂度为，t为组播树中所含的结点数，而因此选择重新选路的各终端结点需再次调用Dijkstra算法三次，如这部分结点数为r,则最坏情况下，这部分终端结点最终加入组播组的时间复杂度为。 由于两种算法都采用了分布式触发的思想，无需覆盖层对整体的费用做出监控及评价，故而从基础解决了原触发重组费用优化方案的缺点，减轻了路由优化的复杂性和额外开销。 目前对于MON网络动态组播树的生成算法，还没有研究人员进行过系统的研究，因此也还没有基准算法来用于网络模拟和比较。因此，本文的网络模拟只能采用课题组MON静态组播树生成算法NCH来作为模拟基准。 · 图4  PRRH-N，PRRH-D算法EAD仿真网络模拟数据 本文以课题组EAD仿真模型所生成的模拟网络来做模拟平台，在EAD算法生成的模拟网络过程中，其MV结点比例是固定的(17%)，而长短边之比随着不同的需求，通过对 及F2的调节，也可以被定位于一很小的领域内，所以在同一网络规模前提下影响部分组播网络动态组播树生成算法的可变因素主要有：1.加入组播组的端结点的更新速度,2.在某一时刻，组播组成员数量在模拟网络的全部结点中所占的比例，对于这两点，都可以以一个无量纲的概念，对不同的网络规模进行一致的模拟，以利于后期实验结果的比较。 本文采用以下假设：加入组播组的端结点以一种稳定的速度进行更新，即某一时刻有占网络结点总数5%的组播组成员退出组播组，而另有占网络结点总数5%的非组播组成员加入组播组，而初始状态选择组播组成员占总结点数的20%和40%来进行模拟。这样就有可能选择相同的静态部分组播网络组播树生成算法来作为待模拟算法的基准算法，以便能从本质上把握待模拟算法的一些基本特征，并给出其性能评价。 由模拟数据可知(见图4)，PRRH-N和PRRH-D算法因为可以在结点加入组播组及结点退出组播组时都能触发树结构的部分重组。所以其费用能够被限定在基准以上的一个很小的区域内，因为考虑到现实网络中的实现问题，两种算法都没有终端结点向上归并的操作，所以，实验中可见费用会出现“跃点”，特别是当组播组成员比例相对较小时，这一点表现的尤为突出。在组播组成员比例进一步增加时，两种算法都表现出很好的收敛性，而且其费用的统计平均值也均被限定在不高于基准的10%，这一结果还是非常令人鼓舞的。 7  结束语 PRRH-N算法在费用优化方面是两种算法中最优的，基于结点费用最优触发重组操作，能最大限度的减小算法的散列跃度，算法收敛性能够有一个很好保证，但时间复杂度整体来说过大，在实际应用中，可操作性要明显低于PRRH-D算法。但在组播组成员相对较少时，对费用优化苛刻的前提下，该算法还是应该成为首选的。 PRRH-D算法在时间复杂度方面较PRRH-N算法为优，而其网络费用优化又明显的线性逼近 PRRH-N算法，在组播组成员比例达到40%左右时，该算法的费用优化性能已近似等于PRRH-N算法， 故在对算法计算时间及费用优化都有较高要求时，还是选用PRRH-D算法为好。 因两种算法都是基于“树核”的，所以两种算法都可以在一定路由协议的支持下进行多面体分级路由模式的改良，也可以方便的向多点对多点组播路由算法改进，这样就能够使算法在可扩展性方面有一个质的提高，同时也可以使其向多点对多点路由计算提供良好的支持。其次，基于“树核”的路由方式，也可以在链路负载平衡方面较原有的CBT算法(原针对全组播网络的一种多对多组播路由算法)有一个质的提高。以上方案都将是今后对于部分组播网络路由算法研究的很好的方向。 参考文献 [1]   董庆阳,  计算机通信网络组播路由算法和协议的研究, 上海交通大学博士学位论文, 2000年 [2]   王征应,  高速网络QOS路由技术的研究及路由仿真平台的研制, 华中科技大学博士学位论文, 2001年 [3]   李汉兵, 计算机网络路由算法, 西安电子科技大学博士学位论文, 2000年 [4]   Yunxi Sherlia Shi . Design of Overlay Networks for Internet Multicast.(PhD thesis ).[D]. Washington University. August, 2002 [5]   G.N.Rouskas and I.Baldine. Multicast Rjouting with End-to-End Delay and Delay Variation Constraints. IEEE Journal on selected Areas in Communications, 1997, Vol.15:346-356 [6]   Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active Distributed Dynamic Routing on the Multicast Overlay Network YU Zhenwei, LIU Kejian China University of Mining and Technology-Beijing, Beijing, 100083 zwyu@cumtb.edu.cn Abstract ： This text gives a definition for the dynamic routing in MON the Multicast Overlay Network, and put forward the problems of the dynamic route computing should be considerated for the first time, and a Arithmetic PRRH-N & PRRH-D according to the distributing triggers the reorganization , in the end ,the report  calculate the complexity of the Arithmetic , simulate the PRRH-N on the model of EAD . Key words:  overlay ; multicast ; dynamic routing ; distributed triggers the reorganization 刘克俭 余镇危  窦巍 （中国矿业大学研究生院，北京，100083） 摘要：本文在分析研究主动应用的基础上，针对应用层主动网络节点对费用的影响，提出了一个新的费用模型，并基于此模型设计了一个灵活的主动路由算法。实验证明此算法具有高效性和可扩展性，在大规模网络环境下也表现出很高的可用性。 关键词：应用层主动网络，移动代理，服务位置，主动路由算法 中图分类号：TP393　　　文献标识码：A 引言 当前为了解决传统计算机网络体系结构面临的困难，研究界提出了应用层主动网络的思想[2][6]。应用层主动网络就是在现有的网络基础之上建立一个虚拟网络用来支持原有网络没有提供的分组处理功能。它的主要优点是不需要整个网络范围内的网络组件的支持，加快了所需网络功能和服务的部署，并且由于支持不同的服务功能的多个应用层主动网络可以共存，也增加了其灵活性。由此，应用层主动网络的提出迅速成为主动网络研究的分支。 为了在应用层主动网络上支持用户的对多样服务的需求，需要在应用层主动网络上选择合理的位置注入特定的服务（如压缩、处理、缓存、重新编码等）来为用户服务[1]，我们称之为proxy[6]。如何优化服务位置是本文考虑的主要问题。首先给出了适合应用层主动网络的费用模型；其次提出并抽象应用层主动网络中的服务位置问题；最后给出算法解决该问题并对算法的特性进行了验证。 2　应用层主动网络上的费用模型 2.1传统网络费用模型的不适应 目前的Internet形成了基本的费用模型，包括接纳控制、路由和资源预留等方面。总的来看，费用包括节点对负载进行分类交换、排队和调度的费用，以及传输到下一个节点的传输费用。当前Internet的实际证明，这一模型是高效和鲁棒的，并依赖这一模型设计了许多有效的协议，比如“最短路径路由”就是基于此费用模型，寻找在源与目的之间的一条路由，使得每跳的费用之和最小。 但是，以上所有协议的设计都是只限于被动网络。在带服务的应用层主动网络中，则不仅仅需要一般的传输资源，而且必须满足中间结点对流的处理。这种情况下，路由的费用包括了结点的处理费用（压缩、处理、缓存、重新编码等），而且因为传输过程中随着流的属性的变化（如重新编码、混合），也在不断影响后续传输的费用，因此在应用层主动网络中路由成为了一个非常有挑战性的问题。 2.2 应用层主动网络应用的一个例子 图 1 主动压缩费用变化 为了避免拥塞控制，比如可以利用proxy进行数据的压缩，节省proxy到用户的带宽。proxy与server之间的流速率将大于proxy与client之间的数据流 ，用ri表示这个变化的比率。在该例子中，费用模型需要考虑压缩代价和由于压缩考虑流量的变化。 如下所示分别标注了链路费用和节点费用。在节点注入主动压缩proxy之后增加了节点处理费用，并对后续的费用（节点和边）产生了影响。很明显，传统的最短路径算法（如Dijkstra算法）应用于以上模型是无效的，无法计算出的最优费用的路径，如下例子可以说明。假设主动节点c、d压缩率0.5。 图2  传统的路由算法的不适应性 结果，Dijkstra算法由于不计节点费用，求出路径（a-b-d-g）费用为50（20+10+20）；在各节点分别注入proxy，考虑主动节点的压缩率和费用，计算出最短路径（a-c-d-g）费用为25.25（20*0.5+3+13*0.5+2+8.5*0.5），优于Dijkstra算法。当然，某些主动服务有可能使费用增加，而不是减少，比如主动加密，但由于中间节点产生费用导致总体费用的变化，所以仍然不能使用传统的路由算法。 因此，得出结论，采用常规的最短路径算法在某些主动应用场合失效（不是所有场合），需要寻找最优的路由算法。 2.3 应用层主动网络的费用模型 主动服务节点的处理代价 ，对经历该主动节点的流的影响比率为，流经过的链路带宽代价为。 主动网络       （1） 被动网络             （2） 设共有n节点，节点k为要研究的对象，引入主动计算，因此主动网络总费用为： =   = =                （3） 引入proxy之后，主动流经过k节点发生改变，因此k之后的费用也发生变化，因此对后续节点费用也产生影响，我们用 表示这种变化。 （4） 3　服务位置问题 首先把问题抽象，网络模型可表示为带权图 ，是主动节点的集合，是边（表示节点之间的连接）的集合，为提供装载proxy服务的中间处理节点的集合（节点或者子网），每一条边的费用为；主动节点的节点处理费用为 。有一个源节点s，一个目的节点d，中间至少包括一个主动节点r装入proxy。我们的目标是找到从s到d最小费用的逻辑路径，以及装载proxy的位置r。这条逻辑路径的费用包括链路费用总和、路径中proxy主动节点的费用。 目的是求上述条件下的路由算法，计算出在哪些位置注入proxy或注入多少个proxy组成的路径的费用是最优的。如果 表示节点i对流的影响，Ai表示流速率（单位带宽），即有： f为最小的费用函数，Ci表示节点执行主动计算的费用，在每一次使用主动计算与是否执行主动计算相关，并且对后续流量是有影响的，根据流量变化不断乘上变化因子 .。 4　算法描述 假设事先获得了逻辑域内网络的拓扑（类似于OSPF链路状态协议），首先我们说明了如何解决一个proxy的位置问题，其次扩展到多个proxy的情形。 4.1网络中唯一proxy的路由 先看简单的情形，假设在网络中只有一个proxy，寻找注入这个proxy的位置，其余中间节点则仍是被动的。首先，复制一份原始拓扑图，形成两层，如图3所示。对于每个节点 ，都有可能装入proxy，因此，在两层中增加了若干有向边(r0,r1)，令这些边的费用等于节点r的费用C(r)。构成的新图中的源点为s，目的点则不再是d，而是1层的d1点。 主动路径的问题即可转化为：求0层的s到的1层的d1的一条不计节点费用的最短路径。所以可以使用一般的最短路径算法，计算好的这条路径跨越两层，合并之后即是原图的最小费用的路径。     图3 单个proxy的主动路由方法 容易证明这一方法的正确性。我们求得从s到d1的最小费用路径 , 在原图有一条路径相对应，且费用相同。假设原图另有一条费用更低的路径，那么在展开图也有一条与之对应的s到d1的路径，这条路径费用则比我们求得的费用要低，因此矛盾。得证。 上一节公式（4）说明，主动节点处理后的主动流会引起后续路由的费用的变化，因此需要考虑带宽变化因子的影响。设0层到1层的带宽变化率为，解决办法是，把0层到1层的费用乘上，再利用最短路径算法求得。 路径确定之后，proxy的位置也就相应确定下来，路径中跨越0层到1层的那个节点就是注入proxy的最合理的位置。 4.2 多proxy的路由和位置 （1） 网络中只有1个proxy的算法可以扩展到多个proxy节点。 有n个可选的主动节点，则最多需扩展到n+1层。因此，如果在网络中装入k个proxy（ ），则复制后需排列为k+1层，类似于4.1问题转化常规最短路径问题，即求s到dk+1的边的费用最低的路径。 而且，仍然要考虑带宽变化的影响。对于第i层的边，边的费用要乘上；从第i层到i+1层的边的费用乘上。 （2）全局最短路径 求原图的任意数量的proxy构成的最短路径，实际上就是从1个proxy到n个proxy的情况都考虑一遍。在4.1的基础上，我们可以得出 Pathmin = Min(Min(s,d),Min(s,d1)), …  Min(s,dn＋1))最短路径即在所有0至n个proxy情况下求得的最短路径中取最小值。 图4 多个proxy的主动路由方法 （3）算法复杂性分析 网络具有k个proxy，则分层图包含 个节点，和条边，求最短路径的时间复杂度为。显然，这种方法空间复杂度是随着proxy数量的增加而线性增长的。 5　实验验证与结论 本论文在Intel Celeron 1.4GHZ ，256MRAM的微机上利用Sun Java（J2SDK1.4）语言编写了上述算法程序。为了验证仿真结果，网络的拓扑图生成使用了BRITE工具[3]，使用随机化的方法产生具有实际网络特性的图的模型，实验网络的拓扑生成基于Waxman[4]的拓扑生成模型： 在我们的实验和算法实施中，网络有如下属性：①边的费用在[10,200]范围上均匀分布。②中间处理节点的费用在[1,10 ]上均匀分布。③如果不特殊说明，则平均每个节点连接边数m=5，α=0.15，β=0.2。 5.1   算法正确性的实验验证 图5 一个简单的主动路由算法的例子 根据图5所示简单网络（节点费用为a0=1，b0=2，c0=1，d0=2，e0=1；λ=0.5），通过模拟程序求Dijkstra算法与主动路由算法结果如表1所示： 表1 λ=0.5，初始节点a0，终点e0的最短路径 Active算法 Proxy数量 0 1 2 3 费用 20.0 11.0 9.5 10.5 Dijkstra算法费用 20.0 DijkStra算法求得最短路径为（a－d－e），费用为20.0。而主动算法求得最小费用9.5，2个Proxy，这个2个Proxy位置分别为a和b，即最短主动路径为（a－b－e），其中主动算法0个Proxy情况相当于Dijkstra算法的结论。 上述两种算法计算的最短路径结论是不同的。首先说明了在节点增加了主动计算费用之后，传统路由算法不适合主动网络。其次说明本文的主动路由算法的可以得出正确的结论，并可求出Proxy所在路径上的位置。此实验只是在一个给定的较小网络拓扑中的实验，目的是说明算法的正确性。 5.2 大规模网络下算法特性的模拟实验 （1）随机拓扑节点总量变化的影响。实验统计了不同节点大规模节点总数的拓扑情况，从大量的实验数据中发现主动路径上的Proxy数量集中在一定范围内。以所有节点作为起始点计算Proxy个数对应的最短主动路径数量分布，并取均值（取整数），得出可信的分布结果。如图6所示： 图6 大规模网络下主动路径数量分布 从图中看出：实际网络拓扑中，在最短主动路径上部署的Proxy数量的分布集中在一个范围内。当流量变化率λ=0.5时，这个范围基本上在1至5个Proxy（包含起始节点本身）。这为我们大规模应用这个算法提供了依据。在主动压缩或主动缓存的应用中，依据主动应用的特点实际也不可能部署太多的Proxy，实验恰恰说明了网络中绝大多数节点使用较少的Proxy就可以达到主动最短路径的要求。 （2）流量变化率λ对主动路由算法的影响 上述是对固定的流量变化率λ=0.5进行的实验；还需要考虑在不同λ值的条件下（λ<1和λ>1）的变化。λ表示执行主动计算之后流量的变化率，λ<1表示主动计算使得流量的后续路径费用减少，带来减少带宽的好处；但是，某些主动应用利用主动计算改变流特性，不一定会有减少带宽的好处（如重新编码），所以用λ>1表示主动计算使流量的后续路径费用增大。当λ逐渐变大时，意味着主动计算的执行使流向着增加带宽费用的方向变化，λ>1变化对算法的效率和主动路径数量分布产生如图7所示的影响（节点总量为500）。 图7 不同λ条件下（λ<1）的主动路径数量分布 分析实验结果，当主动计算对流的改变程度变小时，即随着λ增加，不用Proxy的路径越来越多，使用Proxy的主动路径的数量呈下降趋势。从而得出结论，在λ<1时，λ越小则利用主动计算的价值就越大，反之则多数情况不必利用主动计算。所以，通过实验进一步验证了本文费用模型合理性。当λ等于1.0时是极限状态，几乎没有路径使用Proxy，主动路径数量的分布曲线成为一条逼近于0的直线。总之，当λ<1，λ越小则越适合（快速和普遍）用主动算法求解最短主动路径和Proxy的位置。 其次，当λ>1时，主动路由算法仍然是正确的。实验表明随着λ>1不断增加，主动路径分布出现不均匀的现象，各说明最短路径使用Proxy数量的差异比较大。并且，当λ>2.0之后的最短路径数量分布随着λ的变化是微小的，而且越来越逼近一个极值状态。 （3）算法的执行效率 主动算法的执行时间主要考虑两个方面：第一是计算层数k（即算法所限定的Proxy个数）对算法时间的影响是线性的，算法时间主要消耗在数据结构的建立和复制上；第二是不同变化率λ的算法时间比较，当拓扑总量为500，计算层数k=15不变的条件下，λ对算法所耗时间的影响如图8所示。 图8 算法时间随λ的变化 最后，本文还对Waxman模型中的连接边数、以及α和β参数值的变化进行了实验。发现，连接边数m对主动路径数量分布有较大影响，而α和β值对主动路径数量分布的影响不敏感。 6. 结束语 主动网络的费用模型不同于传统网络，沿用传统的费用模型和路由算法将导致不正确的结 论。本文提出一种新的主动网络费用模型考虑了数据流在主动节点环境中的执行费用，并在此基础上研究一种合理的主动路由算法，通过大量的模拟验证，说明算法各个方面的特性，得出一些非常有价值的结论。 最后，需要说明的是本文只针对单服务主动路由算法进行了研究，而在组播条件下和多服务约束条件下需要研究新的算法，比如利用遗传算法和启发式算法等。   参考文献： 1            Elan Amir. Steven McCanne, and Randy Katz,  An Active Service Framework and it’s Application to Real-time Multimedia Transcoding.[C]. Proceedings of ACM SIGCOMM’98，Vancouver， BC,Canada，Sep 1998. 2            A. Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active Networks (IWAN2000), October 2000. 3            Alberto Medina, Anukool Lakhina, Ibrahim Matta, John Byers. BRITE: An Approach to Universal Topology Generation. in Proceedings of MASCOTS 01, August 2001. 4            B.Waxman.”Routing of Multipoint Connections”.IEEE J.on Selected Areas in Comm.,6:1617-1622,December 1988. 5            Sumi Y. Choi, Jonathan Turner, and Tilman Wolf, Configuring session in programmable networks.  Proceedings of IEEE Infocom 2001,Apr. 2001. 6            窦巍,余镇危,潘耘.基于移动agent的应用层主动网络.第六届全国计算机应用联合学术会议.2002.10  Service Placing Problem on Application Layer Active Network LIU Ke-Jian   YU Zhen-Wei (Graduate Student College　of China University of Mining and Technology,Beijing,100083,China) Abstract By the studying of classical Active Applications (AA), we proposed a novel open Mobile Agent-based Application Layer Active Network。 Proxy server allow to deliver service tasks to any place in the network. We presented a new cost modal and it’s routing algorithm to solve the problem of proxy placement. Key words ：ALAN，active network，mobile agent，proxy placing，active routing algorithm LIU Ke-jian   YU Zhen-wei (Graduate College of China University of Mining and Technology, Beijing, 100083, China) Abstract: The model for stochastic network simulation of exact average degree (EAD) is proposed in this paper, including the following contents: regional distribution of stochastic nodes, selection of core nodes and overlay functional nodes, deduction of new probability connectivity formula, classifying and restricting strategy of increasing degree, fast connectivity strategy of stochastic network, etc. In addition, this paper also makes further explanation, deduction and simulation for the unplugging performance of random network model. Key words: model for stochastic network simulation, exact average degree, overlay nodes 0 Introduction The research on routing issue cannot do without simulation and testing. It is impossible to carry out routing test in the real network for most researchers at present, while a routing test carried out in a specific network will restrict the test result to the specific experimental network unavoidably. A routing protocol or algorithm performing well in a specific network cannot always demonstrate equally good performance once there is a great change in the network topology or when it is transplanted to another different network. Therefore, tests of performance of routing protocols or algorithms have to be based on stochastic network. First of all, the model for stochastic network simulation must give prominence to randomicity, that is, stochastic network generated by the same algorithm should not be the same every time from node distribution to connection so as to guarantee the randomicity of routing tests and the corresponding results carried out in stochastic network, as well as the reliability of simulation results. Second, the main features of the model for stochastic network simulation should be consistent with those of real network in order to guarantee the reliability of routing tests. If the main features of the generated model for stochastic network simulation differ much from those of real network, the performance of the algorithm in real network would be on suspicion. As a result, a superior model for stochastic network simulation is not only the presupposition and foundation of a simulation test of routing algorithm, but also the primary assurance of verification of successful design accurately. 1 Meaning of Research on EAD Simulation Model In previous documents, Waxman proposed two kinds of models generated by stochastic networks: RGl and RG2. The network nodes generated by RGl randomly distributed in rectangular grids, the coordinates of nodes are stochastic integers in consistent distribution, and the distance between every two nodes is a Euclid length. As is different from model RGl, for the network nodes generated by RG2, the distance between every two nodes is a random value between (0, L) in consistent distribution. In both models, there is a certain probability determining whether to connect the two nodes. The probability is determined by distance between the two nodes. The probability of connecting nodes u and v is determined by formula (2-1):     (2-1) A random value Rd in uniform distribution is generated between 0 and RMAX, and if:                    (2-2) Then the connection exists between nodes u and v, otherwise the connection does not exist. In formula (2-1), d (u, v) is the distance between nodes u and v, L is the longest distance between nodes, and parameters  and  control the features of network graph generated, the values of which are in (0，1). The bigger  is, the bigger the average degree; and the bigger  is, the bigger the ratio of long side to short side. After simulation of its performance, we can find out many defects, such as: as for networks with the same scale,  and , the average degrees would always differ much. And if the network scale changes, the average degree would not have a bit consistency. Consequently, some distinct improved modes were brought out on basis of RG1 model in order to improve such defects, such as: Exponential Model: relate the distance between nodes to probability p (u, v), and then the probability of total sides generated would present a downward trend of exponential as the distance between nodes increases. The probability formula is as following:   (2-3) Doar-leslie Model: factor  (where  is estimated average degree, n is number of nodes in the network, and k is a constant) is used to adjust probability p (u, v) to control the number of sides generated in the network. The probability formula is as following:       (2-4) Further research discovered that the convergence of average degree in these models above were still not satisfying. There still are differences between the situation of real network and the ratio of long side to short side as well as the probability of connection of over-lengthy sides. The high connection rate of core nodes and the defect of impact on network routing of special node clusters (such as overlay functional nodes) in the network are neglected. So it becomes a hot issue how to generate a model of network simulation more consistent to the real network in order to support more complicated routing strategies (such as active overlay network routing or partial multicast network). 2 EAD Model for Stochastic Network Simulation The computer network can be abstracted as the graph in graph theory. As for graph G=(V, E, C), V represents the set of nodes in G, E represents the set of oriented sides in G, and C represents the set of weights corresponding to oriented sides. The weight of side is also called the cost of side. Every side corresponds to two nodes u, v V. Every two nodes correspond to two sides (u, v) and (v, u). If the costs of these two sides are equal, the graph G is called symmetric graph, and if the costs of these two sides are not equal, the graph G is called asymmetric graph, i.e. oriented graph. In this thesis, V represents the set of routers in the network, E represents the set of all links, and C represents the set of bandwidth, delay, data loss rate or their assemblies. The research of algorithm to generate model for network simulation is based on unoriented graphs to map to real network, namely full symmetric network. The research of this thesis is also based on such prerequisite. 2.1 Generation of EAD Stochastic Nodes The nodes in stochastic network mentioned above are all scattered in a fixed plane according to probability of uniform distribution. What is worth of attention is that, the nodes in real network is not distributed uniformly, but often incline to partial center-focused distribution. For example, in domestic network, the distribution density of network nodes in the east inshore area with dense population and more developed economy is generally heavier than that of west area with sparse population and less developed economy. In overseas network, this trend is more obvious. The distribution density of network nodes in developed countries is heavier than that of developing countries. In addition, there is hardly a network node in oceans covering more than 75% of the surface of the Earth. In order to eliminate this difference, EAD makes improvement to distribution of network nodes as following: Divide network plane into several sub-areas, and mark these sub-areas as dense areas (D areas), sparse areas (S areas) and 0 distributing areas (Z areas) separately according to actual requests (or at random). When generating network, nodes can be generated separately with different density for each area. In real network, connectivity of most nodes is from 3 to 4, and only the connectivity of a few nodes at network center (3% up to 2000) could exceed 20. These core nodes (expressed with set O) include ISP suppliers, large-scale research institutions, industrial network centers, telecommunication providers and so on. Previous simulation models did not consider connectivity of core nodes. Therefore the guard conditions of all nodes are the same without distinguishing between the primary and the secondary. There is very great disparity with real network, so it will unavoidably bring uncertain factors to the network simulation of some algorithms. Furthermore, previous models for stochastic network simulation did not involve the concept of special node cluster in network (such as overlay functional nodes, multicast functional nodes, etc.), neither. But these nodes may be supporting a certain service of the whole network. For example, there are nearly 20% of the nodes in real network bearing multicast function (17% in 2000). These nodes are able to execute multicast throughout the network. How to generate partial nodes as simulation network of multicast nodes, and how to offer the possibility of simulation verification for partial multicast routing algorithm, become a very realistic problem. In EAD, randomly select from the nodes generated in dense area (D area) of simulation network generated according to areas,  nodes ( is the scale of simulation network, i.e. total of network nodes, taking partial multicast network as an example) as core nodes and multicast nodes, and select from the rest nodes 14% as multicast nodes. 2.2 Generation of EAD Stochastic Linkage According to the above explanation, if  and do not change, the average degree will increase with network scale n increases. In order to decrease such impacts, formula (2-1) has to be modified. As we have already known, as for 0 that is when p is in direct proportion to ( ) , the limits of maximum degree and minimum degree of stochastic network are determined. Therefore the average degree of network will not increase unlimitedly. According to this definition, we get the following formula through comparison of repeated convergence and experimental verification:         (2-5) We can see from formula (2-5) that connection probability P (u, v) approaches to 0 as network scale n increases. In this way, the average degree of network adopting formula (2-5) as connection probability formula will not increase with the increase of network scale n. Our experiments also discover that when F1=16, F2=2.8, the average degree will have a very good convergence. If F1 increases, network connectivity will increase; if F2 decreases, the scale of long side will decrease further. EAD applies this connection probability formula to connection of non-core nodes. That is, when u, v ; u, v, the available connection formula of two nodes is (2-5). Certainly, this also brings some problems. Since formula (2-5) will increase with the increase of network scale n, the scale of long side will tend to decrease. In fact, the result will come out that all nodes tend to connect to adjacent nodes, while in a real network, the long distance connection between core nodes and some special nodes among regions and countries cannot be embodied. In such cases, if there is core node between two nodes, then EAD adopts the following formula:        (2-6) to make a supplementary restriction for network connection probability formula. In order to make average degree of network more exact, EAD makes further restraint to the generation of stochastic network: when there isn’t core nodes between two connected nodes, adopt connection probability formula (2-5), at the same time make restraint to connection node degree: that is, if node degree of any one nodes of the two exceed +1, then the other nodes do not connect to it, where  is expected average degree. However, if one of the two nodes is the core node, then adopt connection probability formula (2-6), where the upper limit of core node is 12;25 (when n>64), that is when node degree of the core node is bigger than 12;25 (when n>64), then EAD will not permit other nodes to connect to it. In course of connection, in order to maintain the probability of participating in connection for every node in consistence, we adopt the algorithm of connecting out-nodes in order, while selecting randomly in-nodes that are not marked (nodes with such marks will not participate in computation). Select in-nodes for current computation of connection probability, and reject the second connection when the same two nodes generate the second connection. In course of computation of connection probability, when node degree of an out-node equals to +1 (non-core node) or 12;25 (core node and n>64), drop the connection computation of this node, mark it (as not to participate in computation), and select the next node orderly as the out-node to continue connection computation. If the in-node has already satisfied the condition of dropping connection, reject computation of connection probability of this node to out-node, mark it (as not to participate in computation), and select the next node orderly to continue computation of connection probability. Experiments show that EAD model for stochastic network generation accord with existing real network both in average degree and in the ratio of long side to short side better than previous model for stochastic network. 2.3 Fast Connection Strategy of EAD In course of generating connection, since the existence of every connection is independent to one another, therefore the resulting stochastic network may not in connectivity after the generation of connections. The practice of previous simulation models is: to make connectivity test for the resulting network after generation of stochastic connections of nodes. If it is not a connected network, then reject it and re-generate stochastic connections. Make repeatable tests until we get a connected stochastic network. Experiments show that we have to attempt many times to generate a connected stochastic network when there are many network nodes. There is nearly an exponential grade relationship between the average attempt times and connection rate (the rate of total connected nodes to total nodes). For example, if 200 nodes are connected completely and stochastically, the requisite average attempt times would be more than 5000, but if only 95% of nodes need to be connected, the requisite average attempt times would be no more than 20. This is of much importance for connected stochastic network with more nodes generated. When there are more nodes, EAD will first apply the generation method of simulation model above to get a quasi-connection network with more than 95% nodes connected, then link the unconnected nodes or subnets to the connected network through the fastest path. So EAD can get a completely connected stochastic network in a shorter period. 3 Compare Performance of EAD with Previous Models When compare our model with previous models, we set out from this principle: under the limit of equal average degree, priorly select parameter values more close to actual network characteristics, that is to regard characteristics most close to the real network as precondition to adjust according to the different adjusting function to connection probability formula of  and . Refer to Graph 3-1 and 3-2 for the comparison of average degrees of RG1 and EAD: Graph 3-1: Comparison of RG1 and EAD Average Degree Where: F1=16, F2=2.8, L=100 raph 3-2: Comparison of Various Models According to the comparison of characteristics of node degrees of models above, we can find out that EAD is obviously better than RG1 in the aspect of average degree. When network scale rises to 1024, RG1 average degree has already arrived at 89.17. In fact, since such stochastic network generated shows much difference to real network, so there is no realistic meaning of it. However, when we control =0.01 or so, for the stochastic network R generated by G1, although the average degree can still bear preferable convergence if network scale is larger than 512, it does not accord with real network seriously due to over-high loss rate of long side. In fact, this network does not bear much realistic meaning. As for the characteristics of average degree, RG1 and exponential model are fundamentally the same: when network scale increases continuously, the algorithms present strong ascending tendency of average degree with very bad convergence. Although exponential model is better, it cannot adjust , while  is responsible for control the ratio of long side to short side, so there is great gap between the resulting simulation network and real network. As can be seen from those graphs, after EAD algorithm applies restraint in node degree, its convergence becomes excellent, and the average degree is always limited within a very small range, at the same time network scale expends with multiples. Because when the distance between two nodes increases, EDA algorithm will apply formula   to calculate the connection probability. Actually connection probability will decrease with exponent as network scale increases, however, many long sides connected to core nodes in real network will be lost while EDA algorithm guarantee the average degree. As a result, EAD algorithm also takes into account long-distance connection of core nodes to other nodes while it adjusts the ratio of long side to short side through  and . By adopting formula , calculate connection probability between a core node and another node, EAD algorithm prompts to compensate the lost long side while guarantee connection of high node degree in core nodes 12;25 (n>64), so that the generated simulation network is more close to real network than before. EAD algorithm greatly improves previous algorithm. No matter in the aspect of core node and its behaviors of high connection node degree, or in the aspect of embodiment of multicast node in the network, or in the aspect of convergence of average degree that we have been caring in the past, EAD algorithm is more close to our real network. EAD algorithm provides a good experimental platform for network simulation of partial multicast network routing algorithm in the latter part of the text. 4 Conclusion This thesis researches the impacts on simulation network of core nodes, node clusters of special functions, convergence of average degree and ratio of long side to short side, and brings forward a method to generate simulation network from a new aspect. The simulation network generated by EAD algorithm is more close to real network, and provide an excellent experimental platform for network simulation of algorithm, especially simulation of special network (such as active overlay network or partial multicast network). As for further research, if we randomly assign a value from 0 to MAX while EAD generates real connection between two nodes, then we can simulate to generate an asymmetric network. And if we execute multi-target restraints to special functional nodes in the algorithm, we can provide support to a good many hotspot simulation of overlay network. There still are a lot of work to done about the algorithm research of stochastic network model. Aiming at different demands (such as new-type polyhedron layered routing strategy), we can make necessary alteration to EAD, however, as for exact average degree, it has already laid a good foundation for further research in the future. References: 1.        Dong Qingyang, Research on Computer Communication Network Multicast Routing Algorithm and Protocol, Doctoral academic dissertation, Shanghai Jiaotong University, 2000 2.        Wang Zhengying, Research on High-speed Network QOS Routing Technology and Development of Routing Simulation Platform, Doctoral academic dissertation, Huazhong University of Science and Technology, 2001 3.        Li Hanbing, Computer Network Routing Algorithm, Doctoral academic dissertation, Xidian University, 2000 4.        Wang Xingren, Development of System Simulation Technology in the 21st Century, Journal of System Simulation, Issue 2, Vol. 11, 1999 5.        Jochen Behrens, “Distributed Routing for Very Large Networks Based on Link Vectors”, June 1997,Ph.D thesis, Computer Science College, University of California, Santa Cruz 6.        M. B. Doar. A Better Model for Generating Test Networks. In Proceedings of Globecom ’96. Global Internet ’96, 1996. 7.        Sandeep Bajaj, Lee Breslau, Deborah Estrin, Kevin Fall, etc. Improving Simulation for Network Research, Technical Report 99-702, University of Southern California, March, 1999 8.        Miguel Angel Olabe, Juan Carlos Olabe, Telecommunication Network Design Using Modeling and Simulation, IEEE Transaction on education, vol. 41, No. 1, February 1998. Project supported by foundation: this work was supported by a national grant from Ph.D. Programs Foundation of China (20030290003) and Project for the Open Research Foundation of the State Key Laboratory of Novel Software Technology at Nanjing University (2002-2003) Authors brief introduction: Mr. Liu Ke-Jian (1969－), Ph.D. student, Graduate College of China University of Mining and Technology, Beijing, mainly engaged in active overlay network key technology, new network architecture, and partial multicast network routing technology. E＿mail: lkj_s116@263.net

其它PDF论文列表：

A Chaotic Neural Network Algorithm for Task Scheduling

A Genetic Algorithm for the Overlay Multicast Routing Problem

Hierarchical Semantic Perceptron Net based Neural Network

On the Model of OoS Multicast Routing Problems in Active Networks

Overlay网络上的服务部署问题的研究（一）

Overlay网络上的服务部署问题的研究（二）

基于Overlay Network的网格虚拟端到端带宽分配问题研究

拓扑感知的分层对等Overlay网格架构及其聚类算法研究

网络流量行为分析的小波加权混沌局域模型

网络体系结构建模和性能评价的形式化方法

应用层组播树分裂恢复算法研究

支持QoS的覆盖组播分布式动态路由研究