计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999　Vol.36　No.6　P.737-744



支持资源预定的多目通信的路由算法及其性能分析
黄浩　杜建成　谢立　孙钟秀
摘　要：目前Internet上的路由协议仅支持“尽力传送服务”.新型的应用问题如视屏会议、分布式模拟等需要有保障的服务质量.资源预定协议如RSVP等可以用来提供有保障的服务质量，但是它需要有新的路由协议.文中研究了支持资源预定的多目通信的路由问题，提出了两个路由算法.算法2采用了避免使用高负载链路的机制，从而使得多目通信的通信树的分配成功率有很大的提高.文中还给出了模拟实验的结果，并对其进行了分析.
关键词：单目通信， 多目通信， 资源预定， 服务质量
分类号：TP393
MULTIPOINT TO MULTIPOINT COMMUNICATION ROUTING
SCHEME AND PERFORMANCE ANALYSIS
HUANG Hao，DU Jian-Cheng，XIE Li，SUN Zhong-Xiu
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093)
(Department of Computer Science and Technology, Nanjing University, Nanjing 210093)
Abstract：The current routing protocols in the Internet only support “best effort service”. New applications, such as videoconference and distributed emulation, need guaranteed quality of service. Resource reservation protocols such as RSVP are used to guarantee the quality of service, but they need new routing protocols to cooperate with them. In the paper here, routing algorithms for multipoint to multipoint communication supporting resource reservation are studied. Two routing schemes are proposed. Using the routing algorithm 2, a feasible communication distribution tree can be constructed. Since algorithm 2 adopts the mechanism that avoids using the high load links, more communication distribution tree can be allocated in a network. Simulation results and their analysis are also given.
Key words：unicast, multipoint-to-multipoint conmmunication, resource reservation, quality of service▲
1　引　　言
　　计算机网络技术已成为计算机应用的核心技术之一.它是分布式计算、计算机辅助协同工作、计算机多媒体应用技术、自动化技术、通信技术、信息系统工程等新技术的基础.
　　目前Internet所提供的服务主要是“尽力传送(best effort)”的服务.即尽最大努力传送但不能保证质量.为了能满足不断涌现的新型应用的要求，例如远程视频会议、分布式模拟等，计算机网络除了在硬件设备，如光缆、通信卫星等提供支持外，还必须在网络协议、软件方面予以支持.如提供实时的服务质量保障，提供合理地共享链路的带宽等网络资源的控制措施［1］.资源预定协议(RSVP)［2,3］为网络资源利用提供了一个控制方法.为了在Internet 上提供综合业务的服务，支持资源预定协议，现有的路由协议必须加以扩充.
　　计算机通信从信息发送者和信息接收者的个数来看，有一个发送者和一个接收者的通信，即单目通信.还有一个发送者和多个接收者以及多个发送者和多个接收者的通信，即多目通信.一些多目通信协议已经提出，例如MOSPF［3］，DVMP［4］.它们建立一个以发送者为根的最短距离树.对于MOSPF，DVMP协议来说，同一个通信组中若有多个发送者就会建立多棵以发送者为根的通信树.对于以往的以“尽力传送”的服务来说，多棵通信树除了在路由器上保留的路由信息比一棵通信树保留的要多一些之外，其它的网络资源利用效率方面本质的区别不大.可是，“尽力传送”服务已不能满足不断涌现的新型的通信任务的要求.当前一些应用问题对通信的质量很敏感，例如视屏电视会议、分布式模拟等要求保证有足够带宽，对时延和丢失率都有具体的限制.因此，对于这类通信问题不仅要求根据当前的拓扑结构寻找通信路径或通信树，而且要求在所找到的路径或通信树上有足够的资源.网络系统通过资源预定等机制来保障服务质量.一个多目通信任务往往有多个发送者.例如，视频会议有几个有发言权的与会者就有几个发送者.若给每一个发送者都预定一棵通信树，则会占用大量的网络资源.而像视频会议这样的通信任务多个有发言权的与会者同时发言的情况是很少的，这样可能造成预定的大量的网络资源被闲置，而需要使用网络资源的通信任务又无法使用网络资源.
　　在任一时期，网络资源总是有限的.为了利用有限的网络资源提供尽可能多尽可能高的服务质量，我们研究了在提供资源服务也能充分利用带宽资源的路由算法.给出了两个不同的多目通信的路由算法.它们为每个通信组预定一棵共享的通信树，同一通信组的成员利用这棵通信树接收和发送数据.第2节给出了一些基本概念.第3节阐述了我们提出的两个算法.第4节对算法的性能进行了分析与比较.
2　多目通信的路由问题
　　为了研究路由问题我们首先将一个计算机网络抽象成一个赋权有向图.图1描述了一个计算机网络的自治系统［4］.图2是图1所示的计算机网络的抽象的赋权有向图，图中每对相邻结点之间应该有两条不同方向的弧(为了简单起见，图2中每对相邻结点之间只画了一条弧，并且表示方向的箭头及弧上的权也都省略了).图1中RT1～RT12是路由器，用椭圆表示；N1～N11是共享介质的局域网，用一条直线或折线(如N3，N6，N9)表示；H1，Ma都是局域网中的主机，用矩形表示.各主机Ma都是同一通信组A中的成员.从路由的角度来讲，从局域网中的一个主机到自治系统中的某结点的路径与从这个局域网到这个结点的路径是一样的.所以从路由的角度来讲，我们可以不区分局域网和局域网中的主机，在下面的讨论中结点集的成员往往位于局域网中的主机中.例如图2中的结点集中没有画出局域网N1，N2，N3，N6，N7，N11等局域网中通信组A的组成员Ma.实际上，从某个主机Ma到某个结点的路径与图中Ma所在的局域网到这个结点的路径是一样的.由此，我们在下面给出了计算机网络的抽象表示.


图1　一个计算机网络自治系统


图2　一个计算机网络自治系统对应的图
　　计算机网络的抽象表示：在研究计算机网络的路由问题时，其拓扑结构可用一个赋权有向图来表示.在本文中，用赋权有向图G=(V,E,C,D)表示一个计算机网络，其中V是结点的集合，一个结点或者是路由器或者是一个局域网；E是弧的集合；权函数C：E→R是弧的集合E到实数集R的函数，若e∈E, 则 C(e) 表示链路e上的可用的资源总量(如总的可用的带宽)；权函数D：E→R是弧的集合E到实数集R的函数，若e∈E, 则 D(e) 表示报文经过链路e时的长度(如平均时延).
　　在计算机网络中通信问题按照发送者和接收者的数量来分可以分成两类.单目通信，即一个发送者和一个接收者.多目通信，即一个(多个)发送者和多个接收者.单目通信的路由问题就是要寻找一条从发送者到接收者的路径.参加一个多目通信的发送者和接收者全体称为多目通信组.一个多目通信组使用一个D类IP地址.多目通信的路由问题就是要寻找一条连接这个多目通信组的所有成员的一棵树，称为通信树.不同的多目通信的路由算法构造不同的通信树.目前主要有两种.一种是整个多目通信组共享的通信树.另一种是以发送者为根的通信树，在这种情况下若有多个发送者，则有多棵通信树.每个路由器利用路由表的一个项来标记通信树的一个结点.一个路由器通过路由表中的一项来表示自己是某个多目通信组的通信树上的一个结点.路由器根据报文的目标地址(单目通信是接收者的地址，多目通信是组地址)以及路由表中相应的项来确定向哪个接口(单目通信是一个接口，多目通信可能是多个接口)转发.路由协议的任务就是要规定在路由器之间交换路由信息的方式，根据收集的路由信息利用路由算法计算出到任意一个目标地址应向哪些接口转发，即构造出路由表.
　　为了叙述问题和描述算法方便起见，先对本文中将要用到的几个符号做一些说明.
　　一个多目通信，一般有一个或多个发送者和多个接收者.在考虑像电视会议这样的多目通信时，往往要考虑这个多目通信任务要求保障的带宽.设有向赋权图G=(V,E,C,D)是一个计算机网络的抽象，我们用(S,T,f)表示一个通信任务，其中SV，TV，f为一正数，S称为通信任务的发送者集，T称为通信任务的接收者集合.f称为通信任务的通信量，即这个多目通信任务要求保障的带宽，关于f的商定的问题我们将在下面作进一步讨论.G上的通信任务全体记为T(G).当S，T为单点集时，即|S|=1，|T|=1时，通信任务就成为单目通信(unicast); 当|S|≥1，|T|＞1时通信任务就成为多目通信(multicast).
　　设有向赋权图G=(V,E,C,D)是一个计算机网络的抽象，若有ai∈V，i=1,2,…,k，s,t∈V,使得(s,a1)∈E，(ak,t)∈E，(ai,ai+1)∈E，i=1,2, …,k-1.则将s到t的路径s(s,a1)a1(a1,a2)a2…ak (ak,t)记为p(s,t)，s到t的不同的路径的全体记为(s,t). 对于任一图G，用V(G)表示图G的结点的集合，用E(G)表示图G的边的集合.设s,t∈V，从s到t的最短距离记为d(s,t) (在本文中距离d(s,t)都是按权函数D计算的)，T是G的一棵子树，则记d(s,T)=min{d(s,t) |t∈T }为结点到子树T的距离，记p(s,T)=arg min{d(s,t) | p(s,t)∈P(s,t), t∈T}为s到子树T的一条最短路的路径，为了符号简单起见，我们也用p(s,T)表示在这条路径上所有边的集合.
　　当为一个通信任务预定一棵通信树时，就是要在计算机网络的抽象图中选择一个边的集合，对这个边的集合中每条边所对应链路预定这个通信任务所有求的带宽.设有向赋权图G=(V,E,C,D)是一个计算机网络的抽象，q=(S,T,f)为一个通信任务，DTE，若s∈S，t∈T，p(s,t)∈P(s,t)，使E(p(s,t))DT，则称DT为通信任务q=(S,T,f)的一个通信树.DT(q)表示通信任务q的所有通信树的集合.也就是说通信任务q的一个通信树是一棵包含通信任务q的所有发送者和所有接收者的一棵子树.
　　问题1. 设有向赋权图G=(V,E,C,D)是一个计算机网络的抽象，q=(S,T,f)为一个通信任务，问题称为最小资源通信树问题.若R*∈DT(q)，且对任意的R∈DT(q)满足，则称R*为通信任务q的最小资源通信树.
　　设G=(V,E,D)是一个有向赋权图，SV，T是G的子树，若SV(T)，且任意给定G的子树T′,当V(T′)S，必有则称T为G中关于S的Steiner树.(V,S,E,D)表示上述的Steiner树问题.
　　对于单目通信来说最小资源通信树就是两结点间的最短路.对于多目通信来说最小资源通信树就是Steiner树.
　　在支持资源预定的路由协议中，为一个通信组选择通信树时，不仅要考虑通信树要能连接所有的通信组成员，还要考虑这棵通信树的每条边是否都能满足资源预定的条件.而通信树的每条边是否都能满足资源预定的条件又与网络系统内的当前的负载状态有关.设有向赋权图G=(V,E,C,
D)是一个计算机网络的抽象，我们用赋权图S=(V,E,F)表示G的一个状态，其中F是E到实数集R的映射，e∈E，F(e)表示当前链路e上的可用带宽.S(G)表示G的所有的状态的集合.设S=(V,E,F)是G的一个状态，q=(S,T,f)是一个通信任务，DT∈DT(q)是通信任务q的一棵通信树，若min{F(e)|e∈DT}≥f，则称DT是在状态S下通信任务q的可行通信树，即一个任务的可行通信树中的每一条边的剩余可用带宽都必须大于该通信任务所要求的带宽.映射P：S(G)×T(G)→2E称为G的一个路由算法，其中2E为集合E的所有子集的集合，符号×是笛卡尔积，也就是说一个路由算法就是根据网络的当前状态和一个给定的通信任务选择出一个可行通信树的方法.
　　设有向赋权图G=(V,E,C,D)是一个计算机网络的抽象，P为G的一个路由算法； qi=(Si,Ti,fi)，i=1,2,…,n，是一个通信任务序列，记为Q；s0=(V,E,F0)是分配q1之前的状态；若p(si-1,qi)是在状态si-1=(V,E,Fi-1)下qi的可行通信树，则当e∈p(si-1, qi-1)时，令Fi(e)=Fi-1(e)-fi；当ep(si-1,qi)时，令Fi(e)=Fi-1(e)；并令Si=(E,V,Fi)，继续分配任务qi+1；否则停止分配，并称i为在状态s0下分配任务序列Q：q1,q2, …，qn的首次失败时刻，记为t(s0, q1,q2, …， qn)或t(s0,Q).
　　问题2. 在网络某一个状态下，随后到达的通信任务序列一般是随机的，因而t(s0,Q)是一个随机变量.随机变量t(s0,Q)的数学期望反映了一个网络分配通信树时首次失败时间的平均值.所以我们希望找到一个路由算法P*,使得首次失败时间的数学期望达到最大：
E(t*(s0,Q))=max{E(t(s0,Q))|P是G的路由算法}
其中E(X)表示随机变量X的数学期望.
3　多目通信的路由算法
　　设有向赋权图G=(V, E, C, D)是一个计算机网络的抽象，本节研究 (S, S, f)类型的通信任务的路由算法.通信组S中的每个成员既是发送者又是接收者.我们给出两个路由算法的方案，在下一节通过模拟实验比较了它们的性能，即首次失败时间的数学期望.
3.1　算法1
　　设q=(S, S, f)是网络G=(V,E,C,D)的一个通信任务.若R是Steiner树问题(V,S,E,D)的一个解.显然，R是通信任务q的占用资源最少的通信树.但遗憾的是一般Steiner树的求解是一个NP难题［6］.所以一般只能用启发式方法来求其近似解.对于Steiner问题(V,S,E,D)，目前构造Steiner树的启发式算法主要有两类.一类是从树T={{w},}开始，其中w∈S，逐步将不在T中的基本点(S中的结点)到T的路径添进T中.另一类是从G的子图T={S,}开始，逐步将链接T的两个不同的连通子图的链路添进T中.如果用Zopt表示Steiner树的总权数(即树上所有的弧的权的总和)，Z表示用启发式算法得到的近似解的总权.许多Steiner问题的启发式算法的计算结果在最坏的情况下比值Z/Zopt≤2(1-|S|/|V|).大量的统计结果表明，大多数算法的比值(Z-Zopt)/Zopt小于10%［6］.下面给出的算法1和算法2的统计结果表明比值(Z-Zopt)/Zopt小于3%.在设计网络路由算法的时候，要考虑通信树占用的资源要少，但更要考虑协议设计的问题，即使得传送的路由信息要少，计算量要少，算法简单且易于实现并能适应多目通信组成员的动态变化.本文考虑了协议实现的因素后，提出以下的基于Steiner树的路由算法.
　　算法1.
　　① 考虑赋权有向图Q=(V,E,D).计算集合S中任意两点间的最短距离.
　　② 找出S中距离最小的两点，记为s1，s2，令DT={s1,s2 }.
　　③ 如果S\DT=，则停止;否则转④.
　　④ 求S\DT中到DT距离最短的点s*=arg min{d(s,DT) |s∈S\DT }, 令DT=DT∪p(s*,DT)，S=S
\{s*},转③.
3.2　算法2
　　为了能使更多的通信任务得到分配，当给一个通信任务分配通信树时,应尽量避免分配那些剩余带宽少的链路.这在网络带宽资源紧张的情况下尤其重要.为了使网络中能容纳下尽可能多的通信任务，我们通过求解以下图论的优化问题来分配通信任务的通信树.
　　适当地选择一个数M，当链路e∈E的剩余带宽F(e)≥M时，则认为链路e∈E是低负载的链路；否则，则认为链路e∈E是高负载的链路.设f为通信任务的流量，当F(e)≥M时，令σ(e)=0；当M≥F(e)≥f时，令σ(e)=1；当f>F(e)时，令σ(e)=∞.考虑下面的问题：
　　(1)
其中

其中DT (q)是通信任务q的所有的可行的通信树.
　　问题1表明给通信任务分配通信树时，在包含所有组成员集S 的子树中先选择出包含高负载链路最少的子树，然后再在这些子树中选择出总权最小的子树.
　　如果直接求解问题1，则计算量非常大.为此我们先将它变换成另一容易求解的问题.在算法1中，计算距离时用的是网络图G=(V,E,C,D)中的权函数D.这里我们根据权函数D和网络的状态构造新的权函数D′，然后将问题1变换成问题2，然后再求解.设分配通信任务q=(S, S, f)时，网络的状态为(V, E, F)，适当选择两个充分大的正数N1<N2.当F(e)>M时，令D′(e)=D(e)； 当M≥F(e)≥f时，令D′(e)=N1，当f>F(e)时, 令D′(e)=N2.
　　(2)
容易证明适当选择两个正数N1，N2，问题1与问题2是等价的.
　　算法2. 基于Steiner树的多目通信(S,S,f)的减少拥塞的路由算法
　　① 构造函数D′及赋权有向图Q′=(V,E,D′).
　　② 计算赋权有向图Q′=(V,E,D′)的结点集合S中任意两点间的最短距离.
　　③ 找出S中距离最小的两点，记为s1，s2，令DT={s1, s2}，k=2.
　　④ 如果S\DT=，则停止；否则转⑤.
　　⑤ 求S\DT中到DT距离最短的点s′=arg min{d(s,DT)|s(S\DT}, 令DT=DT∪p(s′,DT)，S=S\{s′},转③.
3.3　网络路由信息的传播和路由表的构造与修改
3.3.1　路由信息的交换
　　网络的拓扑结构和各链路上的负载情况等路由信息是动态变化的.为了获得当前的路由信息，所有的路由算法都必须定期地与相邻的结点交换路由信息.算法1和算法2所需要的路由信息包括每条链路的链接状态、链路允许的最大带宽、当前的可用带宽等.我们可以用OSPF的Hello 报文、Database Description报文、Link State Request 报文、Link State Update 报文、Link State Acknowledgment 报文.但是必须增加这些报文的域，用来交换关于链路的带宽等资源的路由信息.
　　多目通信通过相应的通信树来传送数据报文.通信树的结点就是网络当中的路由器.例如，在图1所示的网络系统中，设子网N1，N2，N3，N6，N7，N11中的标记为Ma的主机为通信组A的组成员，这个通信组的一棵通信树可用图2中的子树：

　　　　　
来表示.为了记录这些路由信息，每个路由器都维护一个多目通信路由表，表中的每一项记录一个通信组的路由信息，表中的每一项包括组地址、转发接口等内容： (组地址，接口1，…，接口n)，其中组地址就是多目通信组的地址.当一个路由器收到一个报文时，首先从报文头中找出其组地址，然后再从多目通信路由表中找到与其组地址相匹配的项，最后将报文向该项中所列的每一个接口转发出去.这样，在路由器RT1，RT2，RT3，RT6，RT10，RT8，RT11，RT9都有组地址为A的表项.例如在RT3上具有表项(A,1,3).当RT3从接口1收到给组A的报文时，向接口3转发；从接口3收到给组A的报文时，向接口1转发；从接口2收到给组A的报文时，丢弃这个报文.
3.3.2　通信树的建立
　　当一个不在现有的通信组中的主机要加入这个组时，这个主机所连接的路由器必须为其寻找一条到这个通信组的通信树的最短路径.
　　为了阐述通信树的建立方法，我们先举一个具体的例子.假设多目通信组A的成员为图1标记为Ma的主机而且目前每一条链路都是低负载链路.现在子网N5的一台主机要加入多目通信组A.则子网N5所连接的路由器RT5根据当前的路由信息，N5到多目通信组A的通信树的最短路径为L： N5(N5,RT5)RT5(RT5,RT6)RT6.RT5就向RT6发送“加入”消息，而路径L上的路由器收到这个消息后都在自己的多目路由表中增加多目通信组A的表项，而路由器RT6则在已有的多目通信组A的表项中增加一个RT5到N5的接口.多目通信组A的通信树就成为T∪L了.在此之后子网N5中的主机就可以收到发给多目通信组A的报文或向子多目通信组A发送报文了.
　　(1) 当一个路由器要加入一个通信组A时，并按算法1构造通信树时：
　　① 发送一个广播消息，表明要加入通信组A，我们称其为“组加入请求消息”.
　　② 收到“组加入请求消息”的路由器，检查这条“组加入消息”是否从到发送这条“组加入消息”的源结点的接口上到达，若不是，则丢弃这条消息.否则继续处理：检查自己的路由表中是否有与通信组A匹配的表项；若无，则向除了这条“组加入消息”的到达接口外的所有接口转发；若有，则向发送这个“组加入请求消息”的路由器发送一个“组加入回答消息”，表明自己处于这个通信组的通信树的一个结点上，再向除了这条“组加入请求消息”的接口外的所有接口转发.
　　③ 发送“组加入请求消息”的路由器收到所有的“组加入回答消息”(用计时器控制，即等待一段时间后，认为所有能给予回答的路由器的回答消息都应收到)后，选择一个距离自己最近的结点(假设为B)，向B发送“组加入消息.收到“组加入消息”的路由器，检查这条“组加入消息”是否从到发送这条“组加入消息”的源结点的接口上到达，若不是，则丢弃这条消息.否则继续处理：往自己的路由表中增加一项组地址为A的表项；若这个路由器不是这条“组加入消息”的目的结点，则向到达结点B的接口转发.
　　(2) 当一个路由器要加入一个通信组A时，并按算法2构造通信树时：
　　① 发送一个广播消息，表明要加入通信组A，我们称其为“组加入请求消息”；启动定时器.
　　② 收到“组加入请求消息”的路由器，检查这条“组加入消息”是否从到发送这条“组加入请求消息”的源结点的接口上到达，若不是，则丢弃这条消息.否则继续处理：检查自己的路由表中是否有与通信组A匹配的表项；若无，则向除了这条“组加入请求消息”的到达接口外的所有低负载链路的接口转发.若有，则向发送这个“组加入请求消息”的路由器发送一个“组加入回答消息”，表明自己处于这个通信组的通信树的一个结点上，再向除了这条“组加入请求消息”的到达接口外的所有低负载链路的接口转发.
　　③ 如果发送“组加入请求消息”的路由器在定时器超时之前，收到了至少一条“组加入回答消息”，选择一个距离自己最近的发送“组加入回答消息”的结点(假设为B)，向B发送“组加入消息”.若在定时器超时之前，未收到一条“组加入回答消息”，则广播一条“组通信树请求消息”.收到“组通信树请求消息”的位于通信树上的路由器向源结点发送“组通信树回答消息”.收到所有的“组通信树回答消息”之后，该结点则掌握了整棵通信树，从而可以计算出自己到这棵通信树的最短路径，这条路径的另一端假设为B.向B发送“组加入消息”.收到“组加入消息”的路由器，处理方法同前.
4　性能分析
4.1　实验的目的
　　本文给出的多目通信不同的路由算法，从不同的方面考虑网络的利用效率.算法1的目的是使得每一个正在分配通信树的任务占用的网络资源尽可能地少.而算法2不仅考虑使得每一个正在分配通信树的任务占用的网络资源尽可能地少，而且考虑怎样使网络能容纳下尽可能多的通信任务.我们通过实验来观察这两个算法的性能.本文研究了以下两个性能指标：
　　(1) 首次分配失败时已分配的任务数.从一个给定的网络状态开始，按照一定的路由算法给随后到达的一系列通信任务分配通信树，直到按照此算法不能给某一个到达的任务分配通信树时已经分配到通信树的通信任务的数量.在此我们称此性能指标为首次失败时刻FFT(first failure time).
　　(2) 通信树的直径.通信树的直径是在一棵通信树中相距最远的两个结点的距离.如果两点间的距离表示的是通信的时延，则通信树的直径反映了多目通信的最大时延.
4.2　模拟实验方法
　　(1) 每一个阶段随机地产生一组结点号，作为多目通信的通信组成员.
　　(2) 根据路由算法生成通信树，并计算通信树的直径.
　　(3) 记录下网络中各条边的剩余的带宽，即分别记录下各个阶段网络的状态.分配通信树后，则根据通信树来修正网络的状态.
　　(4) 如果所分配的通信树中有某条边的剩余带宽为0，则通信树分配失败.记录下首次通信树分配失败时已经连续分配的通信组的组数，即首次失败时间.并记录下通信树的平均直径.否则进入下一阶段.
4.3　实验结果分析
　　我们选择了几个典型的网络拓扑结构作为实验对象．从初始状态开始，连续分配随机产生的一系列多目通信任务，观察它们的首次失败时间和通信树的平均直径.图3所示的是江苏省数字数据网(JSDDN)的拓扑结构（为了避免连线在示意图上相交，我们将淮阴与连云港两个结点的位置略作了改变）.图4所示的是APARNET的网络拓扑结构.图5是10×10共100个结点的mesh网.4×4共16个结点的mesh网与图5相似，故略去其网络示意图.我们在这4个不同的网络上进行了模拟实验.网络中的每条边的初始带宽设置为4个单位，通信树中每条边占用的带宽为1个单位.每个数据都从100次的实验结果求平均值得到.实验在IBM RS6000工作站上进行.


图3　JSDDN


图4　ARPANET拓扑结构


图5　mesh网络
　　图6描述了在JSDDN、ARPANET、16结点的mesh网、100结点的mesh网4个不同的网络中经过模拟实验得到的首次失败时间的平均值.图7描述了在4个不同的网络中经过模拟实验得到的平均直径.


图6　几种网络的平均首次失败时间


图7　几种网络的通信任务通道的平均直径
　　从图6可以看出，算法2的首次失败时间明显比算法1的迟，约从50％到90％.也就是说在同样的网络资源条件下算法2能容纳的通信任务数比算法1的要多50％到90％.算法2由于采用避免使用剩余带宽少的链路而使路径长度有所增加，但从图7的实验结果可以看出两个算法分配通信树的平均直径差别极小，即算法2对通信的最大时延基本没有影响.从图6还可以看出，mesh网的首次失败时间明显比JSDDN和ARPANET的要迟.其原因是mesh网的各结点的度的平均值比JSDDN和ARPANET的要大.所以网络的拓扑结构对网络资源利用率会产生影响，结点的度大的在同等的网络带宽的条件下将容纳更多的通信任务.
5　结　　语
　　本文提出了构造共享的通信树的算法，根据算法2构造的通信树能够满足多目通信的通信量的要求.由于算法2避免使用高负载链路，从而增加了通信树预定成功的概率.这样的路由算法能与资源预定协议相配合，并能支持资源的重新商定的服务.如何确定多路复用链路(例如以太网)上的服务质量的可用性仍然是一个公开问题，IETF的ISSLL(integrated service over specific link layer)工作组与IEEE802.1组正设法解决这个问题.关于通信的安全与权限等问题本文还未涉及，需要进一步地研究.■
基金项目：本课题得到国家基础研究攀登计划基金和日本邮政省TAO(Telecommunication 　　　　　　Advances Organization) 项目基金的资助.
作者简介：黄浩，男，1957年6月生，博士研究生，副教授，主要研究方向为计算机网络、分　　　　　　布式计算.
　　　　　杜建成，男，1971年5月生，博士研究生，主要研究方向为并行编译、计算机网络.
　　　　　谢立，男，1942年5月生，副校长，教授，博士生导师，主要研究方向为分布式计　　　　　　算、并行处理、计算机网络.孙钟秀，男，1936年12月生，中国科学院院士，教　　　　　　授，博士生导师，主要研究方向为分布式处理系统.
作者单位：黄浩（南京大学计算机软件新技术国家重点实验室　南京　210093）
　　　　　杜建成（南京大学计算机软件新技术国家重点实验室　南京　210093）
　　　　　谢立（南京大学计算机软件新技术国家重点实验室　南京　210093）
　　　　　孙钟秀（南京大学计算机软件新技术国家重点实验室　南京　210093）
　　　　　黄浩（南京大学计算机科学与技术系　南京　210093）
　　　　　杜建成（南京大学计算机科学与技术系　南京　210093）
　　　　　谢立（南京大学计算机科学与技术系　南京　210093）
　　　　　孙钟秀（南京大学计算机科学与技术系　南京　210093）
参考文献：
［1］Braden R, Clark D, Shanker S. Integrated service in Internet architecture. RFC 1633, 1994
［2］Braden R, Zhang L, Berson S et al. Resource reservation protocol (RSVP) version 1—Functional specification. Internet Draft, http:/ftp.ietf.org/internet-drafts/draft-ietf-rsvp-spec-16.txt/.1997
［3］黄浩,谢立,孙钟秀.支持综合业务的Internet-ATM网络及互联,计算机研究与发展,1999,36(1): 8～14
　　　(HUANG Hao, XIE Li, SUN Zhong-Xiu. Internet-ATM network for integrated service and internetworking. Journal of Computer Research and Development, 1999,36(1): 8～14)
［4］Moy J. Multicast extention to OSPF. RFC 1584, 1994
［5］Pusateri T, Distance vector multicast protocol. Internet Draft, http:/ftp.ietf.org/ internet-drafts/draft-ietf-idmr-dvmrp-v3-04/,1997
［6］Duin C, VoβS. Efficient path and vertex exchange in Steiner tree algorithms. Networks, 1997, 29(2): 89～105
收稿日期：1998-06-03
修稿日期：1999-03-15
