CN1206525A - 动态同步传输模式网络中的碎片整理方法和装置 - Google Patents

Abstract

本发明涉及一种碎片整理方法和装置,用于增大DTM(动态同步传输模式)网络网点中自由令牌的平均块长度。碎片整理包括:按照共享相同起始网点的令牌总是定义至少部分连续时隙区的方式在启动网络时为每个令牌规定一个起始网点,在经过明显时间后把自由令牌回送到起始网点,以及当在网点的自由令牌存储区中存在二个或多个具有相同时隙区的时隙相连的令牌时把它们合并成单个令牌。可以在集中式或者分布式令牌管理方式下实现碎片整理。

Description

动态同步传输模式网络中的 碎片整理方法和装置

本发明涉及用于增大DTM(动态同步传输模式)网络的网点中自由令牌的平均块长度的碎片整理方法和构局。

通信产业和学术界在不断地开发新的高容量的通信网络和协议。这样的开发是频繁变化的，并且对于把实时音频、视频和异步通信服务集成到应用中的应用开发者而言新的结果是重要的。可以在各种网络访问终端上得到这些应用。终端充当网络主机并且几乎可以是任何一种电子设备，包括小型电话机或小型电视机、多媒体工作站以及数百万美元的超级计算机。各种主机的处理能力的数量级以及通信通信量的要求各不相同。当前这些完全不同的要求反映在独立网络分类上。每种网络类别最适用于其特定的通信量和应用。有线电视网络采用单向广播网络，其中其容量被划分成传送视频的固定尺寸的子信道。电话网络只采用保证吞吐量以及严格控制延迟变化的64千比特／秒的双工电路。例如因特网的计算机网络通过无连接的包交换提供大量的并行网络话路。计算机网络还采用统计复用设备以便有效地利用链路。用于移动系统的基干网络为了动态跟踪所有的现用终端需要附加的控制(或信令)能力。

在当今这样广泛的并且将来还要扩大的应用下，不可能为新的服务种类持续发明新的(有时是全球的)网络和新的终端接口。替代地，需要开发支持现有通信量及新通信量的综合通信量网络。这种网络的总体目标是全球范围性以及为使成本最低而最大地共享昂贵的网络部件。光传输技术已显示出可以在足够低的价格上提供必需的链接能力，从而使综合通信量网络成为一种现实的解决方案。

但是，具有更高容量的新的综合光网络会带来当今更专用的以及性能较低的网络中未经受的新问题。首先，当网络容量增大并且仍因光速限制而存在信息传输等待延时时，增加带宽延迟的产品将更需要使用户的通信量和第三方的网络通信量相隔离的机制。例如，电话通话不应该受到另一个用户打开高容量视频信道的影响。其次，要在增大的正在传输的信息量下使应用和协议可靠地运行，以便得到网络容量增大的好处。这在网络中将导致更大的猝发串和更大的事务处理。

采用诸如IP(因特网协议)的无状态包交换协议的现有网络已变成是特别大规模的。这种网络已经从70年代中期只把几台DARPA(高级国防研究计划局)研究计算机连成小网络进化到当前全球处处存在的因特网。在因特网中把诸如CSMA／CD(载波侦听多重访问／冲突检测)、令牌环和FDDT(光纤分布数据接口)的共享媒体LAN(局域网)用作由路由器和网桥连接的简单构件。易扩充、低网点递增成本以及对故障网点的容忍的结合产生简单、灵活和可靠的网络。此外，共享媒体允许有效地应用诸如IP多点播送的新多点播送协议。

共享媒体的缺点在于，一般它在任何时刻只允许单个终端发送，不能有效地利用网络的所有部分。可以设计允许重用媒体容量的方法，但这通常是以复杂的高速访问控制硬件为代价的。共享媒体的访问控制机制还强烈依赖于网络的大小并且一般仅对局域环境是有效的。

两种主要类型的网络是用于电话的面向连接的电路交换网络和以因特网为例的无连接的包交换网络。当为数据通信采用电路交换网络时，在信息猝发串之间需要保持线路是接通的，从而浪费网络的容量。出现这个问题是因为和用户请求的动态变化相比电路管理操作过慢。电路交换网络中的另一个开销源是对所需的对称双工信道的限制，当信息流是单向的时这将带来100％的开销。这种限制还造成多点播送电路是难以实现的并且是低效的。相反，无连接的包交换网络缺少资源保留，在传输前必须对每条报文增添报头信息。此外，在无连接的包交换网络中不能准确地预测等待时间，并且由于缓冲器溢出或者报头损坏甚至会丢失包。后两个因素使得难以支持实时通信量。拥塞防避机制可以隔离不同用户的通信量流。但是，这些方法限制了时间尺度上可和往返包延迟相比的运行。

为了解决上述的问题，通信界集中于对ATM(异步传输模式)的开发。ATM是为LAN和众多未来的公用网络提出的。CCITT(国际电报电话咨询委员会)还采用ATM作为B-ISDN(宽带综合通信量数字网)中的传输标准。ATM网络是面向连接的并且和电路交换网络一样建立信道，但是采用用于信息传输的称为信元的小的固定长度的包。ATM的包交换性质意味着这种网络需要例如缓冲器资源管理程序和链路调度程序这样的新机制，以便建立用于连接(如虚拟信道／通路)的实时保证。

提供实时保证的另一种方案集中在电路交换网络上，从而必须解决上面说明的线路交换所涉及的问题。还开发了新的共享媒体控制协议，它考虑了共享媒体的共同问题。这种称为DTM(动态同步传输模式)的设计(参见Christer Bohm、Perl Lindgren、lars Ramfelt和Peter Sjdin的“DTM吉比特网络”，Journal of High SpeedNetworks，3(2)：109-126，1994，以及Lars Gauffin、Lars Hakansson和Birn Pebrson的“基于DTM的多吉比特连网”，ComputerNetworks and ISDN Systems，24(2)：119-139，April 1992)把信道作为通信的抽象概念。这种信道在几方面上不同于电话线路。首先，建立延迟短，从而可以和用户需求变化一样快地动态分配／解除分配资源。第二，它们是单工的，从而单向通信时使开销为最小。第三，它们提供多种比特率以支持用户容量要求中的大的变化。最后，它们是多点播送的，允许任何数量的目的地。

DTM信道与电路分享许多有利性质。在信道建立后不传输控制信息，对于大的数据传输这导致网络资源很高的利用。支持实时通信量是固有的；从而无须制定政策进行拥塞控制或者网络内的流控制。控制信息和数据是分开的，这使得多点播送不那么复杂。传输延迟可以忽略(即小于125μs)并且不会如在ATM中因缓冲器溢出而丢失数据。误码率取决于底层链接技术，并且由于在信道建立时严格保留资源所以交换是简单的和快速的。

在传统电路交换网络的不足之处，例如动态带宽分配、信道建立延迟和作为共享媒体网络上，DTM可以显示好的性能。

使用带有块令牌的DTM，尤其是带有分布式令牌管理程序的DTM的一个主要问题是碎片化(fragmentation)。由于令牌的随机移动和用户请求的不同容量，DTM网络网点上相连自由时隙的平均数量并不大。对于高容量信道，尤其在中到高负载下，这造成较长的访问延迟(毫秒范围)。

本发明的目的是解决这种碎片问题。这是利用增大DTM网络网点上自由令牌的平均块长度的碎片整理方法和装置达到的。

根据本发明碎片整理包括：在网络启动时或网络运行期间为每个令牌规定一个起始(home)网点并使共享相同起始网点的令牌总是定义着至少部分的连续时隙区，在历经明显的时间后把自由令牌送回到起始网点，以及当在网点的自由存储区中存在二个或更多的时隙相连的令牌时把它们合并成为单个令牌。

根据本发明的碎片整理方法避免了上面所述的问题。把令牌回送到它们的起始网点的方法是一种提高在网点的自由合用池中合并二个相连令牌的概率的途径，从而减少碎片。

本发明的优点是它可以在中央式或者分布式令牌管理方法下实现，或者在这两种方法的组合下实现。在分布式令牌管理方法下对访问延迟可得到最好的改进。

另一个优点是可以在网络运行期间为令牌定义新的起始网点。

再一个优点是可以用几种方式选择有效时间；如在空闲时刻、如在最后的本地时刻或者在一定数量的信号传输之后或者是这些方式的组合。必须选择有效时间以便优化性能；若时间太短该碎片整理方法和格局将产生较少的资源共享，但若时间太长则碎片仍旧是个问题。

又一个优点是在和时隙重用方法组合时的性能改进，以在网络的不相交区段中允许使用数据时隙进行同时传输。接着在时隙维上和在区段维上使用本碎片整理方法和装置。最好根据本发明的碎片整理方法和构局在合并时隙前首先合并区段。

下面参照附图将更详细地说明本发明，附图是：

图1表示双总线DTM网络，

图2表示带有一个根据本发明为每个数据时隙定义的起始网点的DTM125μs周期，

图3表示显示时隙数量和区段的令牌图，

图4表示显示根据本发明的重用时隙的时隙区段图，

图5表示采用根据本发明的分布式令牌服务器时对于小的用户请求(16K字节)和对于不同的最小可接受容量模拟出的性能(分别为吞吐量对所提供的负载及访问延迟对所提供的负载)，

图6表示采用根据本发明的分布式令牌服务器对于小的用户请求(16K字节)和对于请求阻塞前所允许的不同的重试次数下的所模拟出的性能，

图7表示A、B、C下作为模拟时间的函数的访问延迟，其中：A)按照本发明的碎片整理方法并且在模拟开始时没有碎片，B)按照本发明的碎片整理方法并且在模拟开始时碎片为最大，以及C)无碎片整理方式并且在模拟开始时碎片为最大，

图8表示带有和不带有时隙重用的双总线DTM网络中双总线和DTM吞吐量对所提供的负载的理论曲线，

图9表示在不带有时隙重用的10km长的双总线DTM网络中采用中央令牌管理程序所模拟出的不同包长度的性能，

图10表示根据本发明在带有时隙重用的10km长的双总线DTM网络中采用中央令牌管理程序所模拟出的不同包长度下的性能，

图11表示根据本发明的在带有时隙重用的1000km长的双总线DTM网络中采用中央令牌管理程序所模拟出的不同包长度下的性能，

图12表示在双总线DTM网络中采用带有本发明的碎片整理和时隙重用的分布式令牌管理程序所模拟出的不同包长度下的性能，

图13表示采用带有根据本发明的碎片整理和时隙重用的分布式令牌管理程序所模拟出的不同总线长度下的性能，以及

图14表示在双总线DTM网络中采用带有根据本发明的碎片整理和时隙重用的分布式令牌管理程序所模拟出的不同通信量状态下的性能。

首先描述DTM MAC(媒体访问控制)协议。如图1所示，DTM网络的基本拓扑结构是一条带有二条单向的连接着所有网点的光纤的总线。可以把不同速度的几条总线连接在一起，以形成一个任意多级的网络。在现有的原型实现中，总线可以组合成二维网状。二条总线交点处的网点可以在二条总线之间同步交换数据时隙。这允许经过网点的具有固定延迟的有效交换。DTM中通信的主要抽象概念是多速率多点播送信道。

DTM的媒体访问协议是时分多路复用模式。总线的带宽划分为125μs的周期，各周期又划分为64位的时隙(简称隙)，如图2所示。从而一个周期内的时隙数量取决于网络的位率；例如，在6．4吉位／秒网络上每个周期约有12500个时隙。

时隙分为二类，控制时隙和数据时隙。控制时隙用于传送用于网络内部操作的报文，例如用于信道建立和带宽再分配的报文。数据时隙用于传送用户数据并且不由中间网络网点解释。中间网点是源和目的地之间的网点。

每个网络网点处有一个网点控制器NC，它控制对数据时隙的访问并且执行例如网络启动和出错恢复的网络管理操作。网点控制器的主要任务是根据用户的命令建立和终止信道并且根据用户请求在后台管理网络资源。

控制时隙专用于网点控制器之间的报文。每个网点控制器对每个周期内的至少一个控制时隙具有写允许，其用于沿下行通道向其它网点广播控制报文。因为对控制时隙的写访问是排它的，网点控制器总是和别的网点及网络负载无关地访问自己的控制时隙。在网络运行期间网点使用的控制时隙的数量可能改变。

网络并不局限于双总线，而是可以用其它类型的结构实现，例如带有任意数量网点的环形结构。除光纤外传输介质可以是同轴电缆或者任何其它的高带宽传输介质。下文中传输介质将看作是光纤。在最佳实施方式中DTM双总线的带宽被划分成各为125μs的周期，每个周期又被划分成各为64位的时隙。本发明并不局限于具有这些数值的DTM网络，而是可用于具有任意长度的周期和时隙的网络。

下面说明资源管理(称为令牌管理)的原则。一个周期内的大部分时隙是数据时隙。根据通信量请求，对数据时隙的访问随时间变化。对时隙的写访问是由时隙令牌(或简称令牌)控制的。仅当网点控制器拥有相应的令牌时它才能对一个时隙写数据。令牌协议保证时隙访问是无冲突的，这意味着几个网点不对相同的时隙写数据。

用于信道建立和带宽再分配的控制报文按参数的方式传送时隙或令牌组。但是，控制报文为64位，从而只能具有少量参数。这意味着如果用户需要大带宽传送，则必须发送几个控制报文以建立信道。这带来额外的访问延迟并且消耗信令容量。

我们考虑用几种机制降低在信道建立和令牌再分配期间所需发送的信息量。令牌管理中的第一个优化是引入块令牌。块令牌在单个控制报文中传送并代表一组令牌，但是只能用于令牌的特殊组合。例如，在模拟器中块令牌是用一个时隙号以及给出该组中相连时隙数量的偏移量表示的。块令牌优化假设令牌存储区未分裂为小的部分。这将称之为令牌存储区的碎片。

令牌协议保证总线上不会由二个网点同时使用一个数据时隙。有时该协议太保守。图3表示一个如何为三个信道保留三个令牌(A、B和C)的例子。网点是由总线区段连接的并且典型地信道使用总线上的区段子集(灰色)，其它的区段是保留白色和不使用的，因此浪费共享资源。一种更好的代替办法是如图4中的例子所示，使信道仅在发送者和接收者之间的区段上保留容量。在这种情况中可以在总线上多次使用单个时隙。信道D和E在不同的区段上使用和信道A和C相同的时隙。这称为时隙重用。时隙重用能够在总线的不相连区段上同时在相同的时隙中进行传输。

在环形网络和总线网络中时隙重用是更好地利用共享链路的一种通用方法。DQ DB(分布式队列双总线)、Simple和CRMA(循环保留多重访问)中的时隙重用算法取决于时隙中的控制信息。如METARING中和目的地释放结合下的缓冲插入网络可以重用独立链路的容量并且可以通过经弹性缓冲器延迟入局包流解决可能发生的争用。

在时隙重用下，不论是用硬件例如DQ DB simple和CRMA还是用软件例如DTM实现访问模式，访问模式的复杂性都会增加。当在不同于DTM的系统中实现时，时隙重用还对经过网点的关键高速通路增加复杂的硬件从而增大网点延迟。

为了在DTM中重用时隙，根据本发明块令牌格式扩充为包含着描述其代表的区段的参数。根据本发明令牌管理协议修改成避免时隙号维中以及区段维中的冲突。最重要的假定是对于原始的原型实现不考虑或不需要硬件改变。性能提高也是非常清楚的：对于源和目的地对均匀分布的双总线已经证明吞吐量可以增加二倍。在其它的网络设计下性能提高甚至更高，例如在源网点和目的的地网点均匀分布的双环结构中，吞吐量可以增加四倍。不均匀分布的源网点和目的地网点提高甚至为更大。

但是DTM网络中时隙重用的潜在缺点是较高的算法复杂性以及网点控制器和信令信道上最终的较大负载(尤其当平均信道持续时间短时)。

已经对二种令牌管理方式进行了评估。第一种最简单的方式是使单个网点控制器管理一条光纤的所有自由令牌。这种集中式服务器机制已在诸如CRMA的系统中采用，在这些系统中起始网点向所有的其它网点分配光纤容量。模拟器配置为使得对于每条光纤距时隙发生器1／3距离处的网点是令牌服务器(当总线上有100个网点，网点33和67将是令牌服务器)。对于二条单向光纤中的每条光纤，这对应于请求的中点，从而令牌管理器在两侧上具有相等的通信量。

每当用户请求到达网点时，该网点首先对管理程序请求令牌并且在信道的整个生命期中锁定这些令牌。当用户发出断开该信道的请求时，立即把这些令牌返回给管理程序。在令牌请求期间所有请求是延迟的，并且经过中央管理程序所有访问是串行的。

分布式令牌管理程序本质上比集中式复杂。我们使它尽可能简单。在我们的方法中每个网点定期广播它具有多少自由令牌的状态信息。其它网点把该信息存储在它们的状态表中。希望更大容量的网点查阅它的状态表以决定从哪个网点请求时隙。启动端的协议按如下方式进行工作。当网点上得到用户请求时：

1．若该网点具有满足该请求的足够多的自由令牌，则向该用户分配请求数量的时隙，并通过向目的网点发送信道建立报文启动信道，然后利用保留时隙发送数据。

2．反之该网点把它可使用的令牌标记为保留并接着检查它的状态表：若网络中全部数量的自由令牌不足以执行该请求，则拒绝(阻塞)该请求。反之使网点向具有未使用容量的网点请求令牌。

若接收令牌请求的这些网点中的一个网点不具有请求数量的自由时隙，它仍给出它所拥有的全部时隙。在任何情况下，它对请求网点回送应答。网点按严格的先进先出次序执行入局请求。

当网点接收对令牌请求的应答时，它把它从应答中接收的时隙(若存在)标记为保留的。当该网点接收到对它发出的全部请求的全部应答时，取决于是否得到足够的容量，该网点启动信道或者拒绝该用户请求。若拒绝用户请求，则重新把保留的时隙标记为自由的。

当启动时在网络的网点之间均匀地分配所有的自由令牌，每个网点取其自由令牌中的至少一个令牌，把这样的令牌移动到现用状态并说明为控制时隙。现在可以接收用户请求并且根据请求在网点之间移动令牌。

这种方式的弱点是仅当用户请求时才触发时隙再分配，并且待定的令牌再分配延迟用户请求。为补偿这一点我们所实施的一种优化是还在后台进行时隙再分配。这造成对于小型到中等大小的请求不太需要再分配。

可以以非均匀的其它方式分配自由令牌存储区以提高再分配的成功率和利用率。若较少的网点管理令牌存储区，随着令牌再分配失败概率的降低信道阻塞也减少。

在这种情况下，在所有的网点中按比例(靠近时隙发生器的网点得到的令牌比远离时隙发生器的网点得到的令牌多)分配整个令牌存储区。可以在任何一对网点之间发生令牌传送，以代替总是要牵扯到服务器网点。当本地网点含有足够令牌以执行入局的用户请求时，可以在不必任何令牌再分配下接受该请求。此外，只要入局的用户请求很好地和令牌存储区分布匹配，甚至不需要再分配。

在决定如何分配令牌存储区之前需要回答几个问题。下面是提出的问题：

1．当网点上的本地资源不足以满足用户请求时，应该向哪个网点要求令牌?

2．若一个网点向几个网点要求令牌，它应该要求多少个令牌?并且当它只接收到请求容量的一部分时它是否应该拒绝信道?

3．若令牌在网点之间自由地移动，令牌存储区会分裂成小片吗?这会使块令牌优化方式无用吗?

决定用状态报文来区分有关自由令牌存信区的信息。状态报文信息用于帮助网点在要求更多的资源时选取适当的网点。这个方法解决上述的第一个问题。

我们的方式按如下工作。每个网点定期广播它具有多少自由令牌的状态信息。其它网点把该信息存储到它的状态表中。希望更多容量的网点查阅它的状态表来决定向哪个网点请求时隙。这种广播状态信息对令牌信息的当前状态给出近似的和过时的估计，从而由于把令牌请求发送到不再具有可给出的令牌的网点而可能使令牌请求被拒绝。

在即使当状态表是过时的或者不能得到时系统仍能工作的意义上，状态表是“软”信息。但是，它们能够提高再分配过程的成功率。

在对集中式(图9)和分布式(图12)令牌管理程序的基本性能进行此较时，我们发现当系统中仍有未使用的资源时在分布式中经常出现一种新的拒绝类型。

网点利用状态表挑选向其请求令牌的网点。当该请求到达目标网点时可使用的总容量可能已经改变从而向请求网点回送的量可能小于所请求的量，从而造成用户拒绝。

这种行为甚至造成更多的不必要的令牌移动并且从而还增大其它网点接收到少于请求数量令牌的概率。在这种情况中移动的令牌是阻塞的并且在传输中是不能使用的。

若在大量(数百个)网点中按比例地分配令牌存储区，则存储区的平均大小将较小。当负载大时，各存储区中的自由令牌数量甚至进一步减少。若网点还以很高的速度建立和取消信道，则各个网点中的自由容量在小容量和空容量之间跳跃。此时，若用户请求的平均容量大于一个网点的自由令牌数，则执行该请示需要要求几个网点。此时被请求中的一个网点不具有自由容量的概率增大，导致用户拒绝。

有几种解决该问题的方法而不必回到集中式模型。第一，当整个请示不能被满足时我们可以根本不放弃任何时隙。这种协议适用于仅向单个网点要求自由令牌，但是若向几个网点提出要求该协议则仍可能造成令牌移动并阻塞成不能使用的。第二，若在令牌请求后我们接收到比要求少的令牌，我们可以简单地重试几次令牌请求过程。这可以提高接收用户请求的概率并且会使用接收到的令牌。重试的代价是会增加信令和增大访问延迟，并且在过载网络中可能使性能变坏。用户的重试还会对重试的请求带来更长的启动延迟。第三，有时用户可能希望接收比要求的容量小的信道，而不是被拒绝。

例如，假定用户接收到50％的他所希望接收的请求。在图5中给出小(16K字节)用户请求在各种最小可接收容量〔100％(40个时隙)、50％(20个时隙)和5％(1个时隙)〕下所提供的负载对吞吐量的曲线以及所提供的负载对访问延迟的曲线，其中吞吐量是所传送的用户数据和允许发送的总位数之比，而访问延迟是从用户请求抵达至发送该请求的第一数据之间的时间。较低的平均最小可接收带宽将导致较大的吞吐量。图6中表示若在最终阻塞请求前用户(请求16K字节的数据传输)最多重试8次下的性能。在更多的信令和更长的延迟的代价下利用率得到提高(并减少阻塞)。若经常发生大次数的重试会不利于生产率。

显而易见，灵活的用户请求策略的好处是拒绝概率较低并且总吞吐量较高。可以在请求抵达时决定图5和图6中所示的配置中的一种。对于信息容量具有严格需求的用户可以重试直至分配足够的容量，而另外的用户可能宁愿接受具有容量少于请求量的信道。本文中下面所显示的模拟里最小可接收带宽定义为请求容量的50％。

通常情况下，网点中相连自由块的平均数量是小的，这是因为令牌的随机移动以及用户请求的不同容量。这种碎片使得块令牌优化实际上是无用的，并使高容量信道的访问延迟相对较长(数毫秒)。为了使块分配有效必须减少自由令牌碎片，要不然在中等至高的负载下对于高带宽信道碎片将成为访问延迟的主要原因。和当前的碎片数量无关，低容量信道几乎总是具有非常短的信道建立延迟。在时隙重用的情况中，由于碎片可能出现在时隙(时间)维度和区段(空间)维度中(见图4)，碎片问题甚至更为严重。在集中式服务器方案该问题是通用动态存储分配问题的一个特定应用问题。在分布式令牌管理程序中大部分碎片是使用多个自由令牌存储区(每个网点一个)的结果。仅当在同一网点中找到二个相邻的自由令牌才能合并它们。

已经实施一种试图尽可能避免碎片并且增大网点中自由令牌的平均块长度的分布式方式。这种方式是在具有和不具有时隙重用下使用的。

该方式按如下工作：

1．在启动网络时为每个令牌规定一个起始网点，并且按照使得共享相同起始网点的令牌永远定义一个连续时隙区的方式分配令牌。如图4所示，这在令牌图中造成大的平均令牌区。

2．当在自由令牌存储区中存在二个具有相同时隙区或相同区段的时隙相连的令牌时把它们合并成单个令牌(有时需要递归的分离合并操作)。在进行合并时永远使区段合并优先于时隙号合并(其原因是只跨越一些区段的令牌组要比跨越许多区段的令牌组更少地用于其它的结点)。至少代表着相同时隙区的一部分并存在于某个网点的自由存储区中的二个区段相连的令牌被分离以得到代表着相同时隙区的区段相连的令牌，再把它们合并成单个令牌。

3．当某个网点得到来自本地用户或者远程用户的令牌请求时，利用时隙号维度和区段号维度的最优满足算法从令牌存储中挑选一个令牌(见图4)。一个令牌的值是按令牌图中令牌的面积计算的，并且我们试图挑选符合所需容量的具有最小面积的令牌。还可以把费用函数定义为例如时隙数量、区段数量、时隙位置以及区段位置的函数，应使该函数在符合所需容量下最小。当采用集中式令牌管理程序时还可由服务器采用该机制。

4．当某个网点需要向其它网点请求令牌时，如果它有可能向较少的网点要求较大的令牌块，则它不向较多的网点要求较小的令牌块。状态表提供这种信息。从而令牌的传送更为有效，并且存在较少的建立报文和较少的碎片。

5．当自由令牌空闲长时间后或者在长的传送后，把自由令牌回送到起始网点。

把令牌回送到“起始”网点的这种方式是一种增大在自由表中合并二个相连令牌的概率并减少碎片的方法。若起始网点的“引力”过强，则该方式会导致较少的共享资源以及不必要的信令。若该引力太弱，则碎片仍然是个问题。可以在总线的运行期间改变“引力”。

为了评估这种碎片整理机制我们进行了另外一组模拟。配置了三种不同的模拟器〔A、B、C〕。模拟器A配置成在模拟开始时不带有碎片并且采用上述的碎片整理方式。B在整个资源存储区具有最大的碎片下开始。所有的令牌具有单个时隙并且在启动碎片整理机制之前令牌都不位于“起始”网点。最后，在不采用碎片整理机制并且令牌存储区具有最大碎片下启动模拟器C。在所有的情况中启动时隙重用并把负载定义为80％。

图7表示10km网络中作为模拟时间函数的访问延迟。模拟器C从长的访问延迟开始，并且延迟随着信令信道过载以及报文队列增长而增长。采用碎片整理机制的模拟器B开始时和C一样差，但在10毫秒之后平均访问延迟已经低于500微秒。模拟时间一秒后B曲线几乎和A曲线重合，即它收敛于开始完全不带有碎片的模拟器的性能。收敛速度取决于网络中的总自由容量，从而也取决于负载。以上所有模拟期间的负载是80％。碎片整理机制明显地改善访问延迟并且还使块令牌优化在分布式实施中是有意义的。

主要感兴趣的是二种性能量测：利用率和访问延迟。利用率是实际用于数据传输的额定网络容量部分，它是网络有效性的量度。访问延迟是从用户请求抵达至发送该请求的第一数据之间的时间，它是能够多么好地支持计算机通信量的一个重要量度。

存在二个主要的影响DTM中的利用率的因素。首先，对每个网点以控制时隙的形式分配信令容量，这意味着在固定链接容量下在具有许多网点的总线上数据传输能使用的时隙变少。其次，令牌再分配导致系统开销，因为网点向正在再分配时隙令牌时不能把相应的时隙用于数据传输。

访问延迟主要取决于控制时隙上的负载，并且取决于建立信道需要发送多少控制报文。访问延迟通常是一些延迟的总和：例如，网点控制器处理延迟〔5μs〕、寻找并分配自由令牌的延迟〔100μs〕、等待第一个可使用的控制时隙通过〔50μs〕以及最后等待要填入用户数据的第一个分配的数据时隙〔62．5μs〕。另外，报文在网点控制器输入处的等待处理的队列中延迟。下面给出的模拟中平均延迟高达数百微秒。

下面将给出使DTM承受计算机通信中更可能见到的相对短期的传输(4-4000K字节)的通信量模式下的模拟结果。通信量为猝发内部抵达的、面向客户机／服务器的以及按指数分布抵达的。在模拟模型中，每次传输开始于新的信息“包”的抵达。网点控制器试图为该传输分配资源，发送数据并且最后释放信道。这是对实际系统机制的一种简化，在实际系统中信道建立、数据传输和信道撤消是由用户启动的独立操作。例如，知道传输就要发生的用户可以通过预先请求信道“隐藏”信道建立延迟，从而当开始传输时信道已经建立。在建立到撤消之间，信道容量全部为该用户保留。信道的最简单使用是用于简单传输，例如文件传输或者视频传送。

根据应用特征，有可能优化信道的使用。例如，信道可用于传送诸如ATM信元或IP包的高层报文序列(这类似于在ATM网络中为所有的IP通信量采用单个VC(虚拟信道))。若信道是多点播送信道，则可以将到达不同目的地的报文在信道上多路复用。这意味着每条报文将到达多点播送信道上的每个接收者并且接收者必须能够过滤报文。一种替代的解决办法是为每条报文建立和撤消一个信道，但是在报文之间保留令牌从而序列中的下一个报文立即就可得到令牌。

在模拟中没有考虑这种类型的用户行为，因为它们是为特殊应用优化的。而是将注意力放在不具有用户级优化下网络如何运行。

甚至在接收者接收到信道建立报文之前，一旦分配了资源发送者就可以开始发送数据。这称为信道建立。接收者最终将用控制报文对接受或拒绝信道作出应答。

用户请求具有下述参数：

·包长度，它是信道建立至信道释放期间所传输的用户数据量。我们模拟的包长度从几K字节到几兆字节。

·对信道的请求容量，它是网点试图分配的时隙数量。在本文中的所有模拟中请求容量固定为40个时隙或20．48M位／秒。

·最小可接受容量。若一个网点不能分配该数量的时隙，则该网点阻塞该请求。通常把它置为40个或20个时隙(请求容量的100％或50％)。

·源地址。

·目的地址。

源地址和目的地址是随机产生的(所有网点具有相同的概率)，用户内部抵达时间按指数形式分布。各次模拟观察信令容量以及时隙再分配开销对利用率、信道设置延迟以及阻塞的影响。对于具有下述特征的拓扑结构，我们模拟各种通信量状况：

·具有100个网点的双总线网络。尽管理论上一条总线可以连接多得多的网点，我们认为管理一条总线具有多于100个网点的网络可能是办不到的。带有100个网点的共享容量足以运用和测试本令牌管理协议。

·每条总线的容量的6．4G位／秒。我们相信对于一、二年内可实现的技术这是实际的；2．4G位／秒的光链路几年前起就可得到了，并且已经宣布10G位／秒的链路很快就要上市。6．4G位／秒对应于100M赫兹的时隙率，这是时隙处理MAC硬件利用现有的CMOS技术可在该速度下运行的速率。

·对于所有的网点总信令容量是相同的，但是在二个光纤方向上根据网点在总线上所处的位置按比例分配时隙。离时隙发生器较近的网点需要较多的控制容量。但是在二条总线上对于所有网点控制容量之和是相等的。在带有二个令牌服务器的网络中，和其它网点相比服务器具有更多的控制容量和更强的处理能力。

·总线的长度是10km，这是不能忽略传播延迟影响的足够长的网络。图11和13给出不同的总线长度在模拟中的传播延迟影响的研究结果。

·模拟二种不同的令牌管理方式：单个令牌管理程序管理一条光纤上的所有令牌的非对称方式以及每个网点控制器管理全局令牌存储区中的小部分令牌的对称方式。

当分析DTM双总线网络的性能时必须得到最大理论性能并和模拟出的性能进行比较。在本文中最大理论性能还用于比较不同的方式和比较我们所评估的各种实施。

在二条光纤都接收相同的通信量的前提下，不带有时隙重用的双总线系统的最大吞吐量可以定义为链路容量的两倍。在带有时隙重用的系统中系统的吞吐量还取决于源及目的地的分布。为了得到双总线的吞吐量我们采用在其中源地址和目的地地址均匀分布(见图8的左曲线)的蒙特卡罗模拟。在把这种模拟和其中用户请求大传输(20M位／秒容量下的4MB)和信令容量不是瓶颈的DTM网络(模拟器的配置按下面采用的集中式令牌管理程序定义；参见图8的右曲线)相比时，利用率接近理想情况。与此类似的实际通信量是成批数据传输以及音频／视频流。所显示出的不同是这样的结果：DTM中用于控制时隙的一些容量减少了数据传输中能使用的时隙数量。用于DTM系统中随机发生器在上行通道和下行通道中并不产生完全相同的通信量。这可能造成一个方向上的阻塞而另一方向上仍有容量。在信道建立期间资源可能阻塞未被使用，暂时性地消费某些容量。

在中央令牌管理程序的情况下，二个管理网点需要比其它网点具有更多的信令容量(对服务器网点分配为其它网点八倍的控制时隙)。

第一组模拟结果在图9中示出。用户请求20M位／秒信道，内部抵达时间按指数分布(经泊松处理产生)，并在各种包长度下进行模拟。若不能分配信道的整个容量，则拒绝请求并把令牌回送到令牌服务器。包长度从4M字节变化到4K字节，在4K字节处我们开始看到吞吐量降低。

若网点上的处理容量或控制信道容量太小，则可能出现吞吐量降低。尤其是服务器网点可能会过载。结果是含有控制报文的队列开始变得非常大。控制令牌意味着未使用的容量，从而吞吐量下降。

在每信道4K字节的模拟中，控制容量是限制因素，并且如果增加更多的控制时隙(信令容量)则可以更有效地支持4K字节及更小的包。

图10中的下一组曲线显示时隙重用机制如何改善系统的性能。在明显数量的信道被拒绝之前吞吐量几乎增加一倍。信道源和目的地的均匀分布限制了通过时隙重用获得的容量的提高量。已经证明，若如我们所做那样均匀产生源和目的地，则双总线上的吞吐量可以加倍。模拟中还可以发现所提供的负载超过2．5时我们实际上可以得到高于2．0的吞吐量。但是，在不拒绝某些信道下是不能达到这种吞吐量水平的。具有最高被拒绝概率的信道是使用许多时隙或区段的信道。从而系统“滤出”不太贪心的用户请求并且拒绝其它请求。通常这不是一种能接收的行为，所以我们不对它做更多的研究。吞吐量降低出现在4K字节传输并且所提供的负载为1的情况下。即使在令牌服务器中可以得到足够的资源，由于控制信道拥塞不可能足够快的建立和撤消信道。此外还发现所提供的负载为1．8时在8K字节模拟中出于相同原因的吞吐量降低。

从图10中的模拟可以得出，只要控制和服务器处理能力不是瓶颈，仅对集中式令牌协议进行少量修改，时隙重用机制几乎能使系统吞吐量翻一番。从这些曲线中还可以意外的发现，当负载从0．1增加到0．5时实际上访问延迟减小。这是如何把时隙分配给信道的结果，并不是由于更快的令牌请求过程。向服务器请求令牌所使用的时间绝对是增加的。

当把图10中的DTM性能和图8中的理论值进行比较时，可以看出即使是短猝发(几毫秒持续时间)仍能得到有效的支持。

当采用单个令牌服务器时，在网点能够建立信道之前，各信道建立首先需要向服务器请求一个令牌。若增加总线长度，则该令牌请求需要更长的时间，从而也可能限制吞吐量并增加访问延迟。

图11中显示总线从100km增加到1000km的模拟结果(此时网点之间的距离为50μs)。访问延迟和吞吐量现在都被到令牌服务器的往返等待时间限制。

这种情况下访问延迟取决于到服务器的距离，但和传输量无关。由于建立阶段会被长的数据传输阶段遮掩掉，利用率主要取决于传输量。当总线长度为1000km时仍能有效地支持传输大量信息例如256K字节持续时间为十分之一秒的信道。

采用集中式令牌管理程序具有几个好处。因为客户机只需要含有和它们自己打开的信道有关的状态信息，所以客户机可以是简单的。由于时隙服务器尝试满足用户请求时具有所有可选择的自由令牌，所以时隙重用也是简单的和有效的。服务器还能执行与其他策略有关的操作，如许可控制和公平性。服务器中自由令牌存储区中的碎片是非常适度的，从而即使对高容量用户请求也只对每个信道产生非常少的连接建立报文。

但也存在缺点。频繁建立并撤消信道的用户可能通过总是在使用后回送令牌但在短期内又接着请求令牌而引入过多的信令。若总线上存在许多网点或者如果平均包长度非常小，则服务器网点的处理容量可能变为过载。如果相对于位周期、每包的位数和媒体速度的乘积媒体长度非常大，则到服务器的往返时间也会限制性能。最后，服务器网点包含着所有网点所依赖的用于建立信道的状态信息。从而服务器网点的故障可能影响所有的网点。

下一节中模拟并研究全分布式令牌管理程序的特性。

在评估带有时隙重用和碎片整理的分布式令牌管理程序的性能时，采用和中央令牌管理程序情况中相同的通信量和参数，但是还带有若可以分配50％的请求容量则接受请求的策略。

图12中所给出的结果是从带有时隙重用、全分布式令牌管理程序、说明网点拥有多少容量的状态报文以及去碎片模式的模拟器得到的。所有的网点具有相同的处理容量并且处理负载远低于图10中服务器所接收的负载。网点之间的相关性也小得多，从而造成更高的可靠性。该系统的运行优于不具有时隙重用的任何系统，但是不如前面所描述的集中式系统。

当把以上配置的性能和图10中的集中式令牌管理程序进行比较时，可以看出在分布式实施中阻塞更高并且在低得多的负载上可能阻塞某些请求。

一个未预料的结果是当包长度增加时性能实际上下降。在再次检查该结果之后发现大的平均传输量造成令牌的较少运动并且状态信息实际上给出网络中的自由资源要比短的传输下甚至更差的估计。在这种情况下，若我们不认为会找到资源则会拒绝请求。引入这种机制是为了在用尽资源时避免浪费控制容量。

这种现象的原因在于状态报文仅描述覆盖总线的所有区段的“全局”令牌。全局令牌可以由任何网点使用并且是不带有时隙重用的DTM系统中唯一一种令牌。在负载高于1．00时，大量的令牌是分区段的并且重用方式在它们被新的请求使用时需要它们。从而，这里所使用的这种为不具有重用的系统开发的状态报文机制在帮助新请求找到自由容量的能力上是受限制的，其最坏的情况是造成更高的阻塞。

图13中示出总线长度从1km到1000km下分布式令牌管理程序的吞吐量和访问延迟。在建立和撤消信道之间发送小的16K字节的包，对于大的包(数百K字节)系统的吞吐量性能不大受总线长度的影响。1km和100km给出大致相同的吞吐量并且访问延迟结果和10km总线一样，这是由于因采用125μs周期引入的等待时间超过系统中的传输等待时间。对于1000km长的总线可以看出访问延迟要比采用集中式令牌服务器的访问延迟短得多，尤其在低负载时在离用户请求抵达处很近的地方可以得到令牌并对于整个系统延迟大致是相同的。即使在很大负载下访问延迟要比带有集中式服务器的系统的延迟短1毫秒。

只要处理和信令是充足的，集中式令牌管理程序系统就具有几乎和通信量无关的相同性能。为了评估分布式系统使用另外二个通信量发生器。首先，我们使用一个模拟用户请求按猝发方式抵达的发生器。当一个请求到达时我们规定200μs后一个新请求以90％的概率抵达。结果是猝发的请求组抵达某个网点并强制源地址的高度暂时局域性。第二，为了产生和客户机／服务器行为更加相似的通信量，增加5个服务器网点0、25、50、75和99的通信抵达量。服务器目的地的概率也为更高。

在图14中给出分布式令牌服务器系统的吞吐量以及访问延迟性能。

和集中式令牌服务器相比很清楚分布实现具有几个好处但也具有缺点。网点可以共享处理负载，不太需要高性能的令牌服务器，冗余可以更高并且对于低容量请求访问延迟可能更短。缺点是对于呆板的用户阻塞较高，从而可能需要多次重试方可得到对所需资源的访问。此外很清楚为了避免允许时隙重用下的不必要阻塞必须改变状态报文和状态表机制。

当负载增大到某点时，难以找到自由令牌，阻塞变成明显并且利用率仅在一定程度上随负载提高。给定负载上的阻塞程度主要取决于用户请求的最低容量要求。最低容量越小，网点能满足请求的概率越高。此外，在这些模拟中对每个用户请求只发出一轮令牌请求。通过采用几轮(即采用重试)可以提高利用率，其代价是更长的访问延迟。

假定上述等待时间是独立的，若具有单个控制时隙并且若网络是轻负载的(意味着借用不频繁)，则平均媒体访问延迟将造成约为125μs(单个周期)的平均访问延迟。

此外，由于碎片为了建立信道可能需要许多控制报文，这会进一步增加控制信道的负载，并且还会增加访问延迟。事实上，当不具有有效的碎片整理方式时碎片是模拟中的访问延迟的主要起因。

DTM的时隙重新分配机制的一个后果是建立要求高带宽的信道需要较长的时间。这种权衡关系是由于：只需短的媒体访问延迟的通信量类型通常对分配给传输的带宽量不太敏感，从而这种通信量可以在无须大量涉及再分配协议下接收。对于要求高宽带的传输，访问延迟要大得多并且几乎总是要涉及再分配协议。但是，高带宽传输通常可能对访问延迟不太敏感。

这些模拟显示DTM快速电路交换协议在双总线共享媒体环境中运行良好。对二种时隙(令牌)管理方式作了分析，二者都运行良好并且可以从时隙重用中得到好处。集中式模式的运行和理想协议最接近并且还可导致简单的实现。分布式系统对用户行为更敏感，从而为了减少信道建立及时隙再分配所需的控制报文的数量，必须依赖频繁广播的状态信息并且必须依赖根据本发明的碎片整理方法和装置。当对长总线采用碎片整理方法和装置时，分布式模型显示出优于集中式模型的性能(比较图11和13)。组合集中式及分布式模型并采用小量令牌服务器网点的资源管理系统也是可能的。

另外，可以把连接建立开销设计成非常小，从而甚至对小的(几K字节)传输也可产生高使用率。即使在高负载下访问延迟得知为数百微秒。时隙重用方法可以在不必向网点引入附加硬件下把性能提高一倍。由于在时隙维度上和区段维度上都会出现碎片，采用时隙重用方式甚至比采用根据本发明的碎片整理方法和装置更为重要。

Claims (17)

1．一种碎片整理方法，用于增大动态同步传输模式DTM网络网点的自由令牌的平均块长度，其特征在于

-在网络启动或者网络运行期间按照共享相同起始网点的令牌定义着至少部分连续的时隙区的方式为每个令牌规定一个起始网点，

-在经过明显时间后把自由令牌回送给各自的起始网点，以及

-当在网点的自由令牌存储区中存在二个或更多的时隙相连的令牌时把它们合并为单个令牌。

2．根据权利要求1的碎片整理方法，其特征在于，在网络启动时或者网络运行期间对所有的令牌规定单个起始网点。

3．根据权利要求1的碎片整理方法，其特征在于，在网络启动时或者网络运行期间把所有的网点都规定成在其中分配令牌的起始网点。

4．根据权利要求1的碎片整理方法，其特征在于，在网络启动时或者网络运行期间把一组网点规定成在其中分配令牌的起始网点。

5．根据权利要求1-4中任一要求的碎片整理方法，其特征在于，在网络运行期间可以把令牌重新分配到新的起始网点。

6．根据权利要求1-5中任一要求的碎片整理方法，其特征在于，当自由令牌空闲明显时间后把它们回送到各自的起始网点。

7．根据权利要求1-5中任一要求的碎片整理方法，其特征在于，当自由令牌在明显时间内即所谓的最后起始时间内不处于其各自的起始网点处时把自由令牌回送到各自的起始网点处。

8．根据权利要求1-5中任一要求的碎片整理方法，其特征在于，在明显的信号传输次数之后把自由令牌回送到各自的起始网点处。

9．根据权利要求1-8中任一要求的碎片整理方法，其特征在于，当网点得到来自本地用户或远程用户的令牌请求时，利用最优匹配算法从某个网点的自由令牌存储区中挑选一个令牌，在该算法中选择满足所请求能力的最少时隙数量的令牌。

10．根据权利要求1-8中任一要求的碎片整理方法，其特征在于，当某网点需要从其它网点请求令牌并且不存在满足所请求容量的令牌时，使必备的令牌数为最小。

11．根据权利要求1-10中任一要求的碎片整理方法，其特征在于，该方法和时隙重用方法结合，在时隙重用方法中：

-将DTM块令牌格式扩充为包含描述源和目的网点之间的区段(组)的参数，

-仅在源和目的网点之间的区段(组)上保留块令牌容量，并且

-在相同的时隙内允许在网络不相邻区段的相同时隙内同时传送。

12．根据权利要求11的碎片整理方法，其特征在于，当在网点的自由令牌存储区中存在二个或更多的相同时隙区中的区段相连的令牌时把它们合并为单个令牌。

13．根据权利要求11的碎片整理方法，其特征在于，当在网点的自由令牌存储区中存在二个或更多的代表着相同区段的时隙相连的令牌时把它们合并为单个令牌。

14．根据权利要求13的碎片整理方法，其特征在于，分离代表着至少部分相同时隙区并存在于某网点的自由令牌存储区中的二个区段相连的令牌，以得到代表着相同时隙区的区段相连的令牌，并把它们合并为单个令牌。

15．根据权利要求11-14中任一要求的碎片整理方法，其特征在于，当网点得到来自本地用户或远程用户的令牌请求时，利用时隙号维度和区段号维度中的最优匹配算法从令牌存储区中挑选一个令牌，该算法选择满足所请求的容量并具有令牌图中的最小面积或者最低费用函数的令牌。

16．根据权利要求11-14中任一要求的碎片整理方法，其特征在于，当某网点需要从其它网点请求令牌并且不存在满足所请求容量的令牌时，使必备的令牌数为最小。

17．一种碎片整理装置，用于增大动态同步传送模式DTM网络的网点上自由令牌的平均块长度，其特征在于其包括：

-起始网点，对这些起始网点规定令牌，以使共享相同起始网点的令牌定义至少部分连续的时隙区，

-排列成当经过明显时间后把自由令牌回送到它们各自的起始网点的网点，以及

-排列成用于把二个或更多的时隙相连的自由令牌合并为单个令牌的网点。

Images