计算机应用研究
APPLICATION RESEARCH OF COMPUTERS
2000　Vol.17　No.5　P.33-35



新型的ATM网络资源分配体系结构
黄德能　薛小平　阮永良
摘  要  介绍了一种新型的ATM网络资源分配体系结构，它对分配了的信元具有可恢复性，并能实现VP的快速恢复。该体系结构中有两种空间：虚拟工作空间(WC)和虚拟备用空间(SC)。采用两种空间比传统的资源分配方式只采用一种空间有更大的优点，能更好地恢复故障。为了缩短呼叫处理时延，此结构采用了分布式的并行处理方式。
关键词 ATM  VP  资源  路由  QoS   信元分配
1  序言
　　许多可以预见的ATM服务，如实时图象传输、远程信息数据的交互式应用、远程监测和控制、商业(交互式的或非交互式的)处理、紧急通讯等业务，都要求网络提高速度并能在瞬间从故障中恢复。这一点相当重要，因为网络故障会同时影响到很多用户，也正是因为这一点，完全、快速地恢复网络连接成了ATM网络的QoS要求。这些是通过管理ATM网络节点中缓冲空间和中继线带宽实现的。传统的快速资源管理方法有两种：带宽预留和缓冲器预留。本文要介绍的是具有快速恢复功能的资源管理方法。下面对这几种方法略作介绍：
　　(1)快速带宽预留
　　快速带宽预留就是沿着端到端路由的在每个节点上预留带宽。带宽预留有两种方式：立即不保证方式和延迟保证方式。
　　延迟带宽预留方法使端到端的带宽预留得到保证。其过程如下：在发送突发业务前，业务源必须申请预留带宽。为此，业务源要给端到端路由上的每个中间节点发送快速带宽预留请求。该预留请求逐节点向前传递。每个节点要么接收带宽预留申请，并向前传递该请求(OK)；要么因为带宽不够，废弃该请求(NOTOK)，并向发端返回一个失败的消息。成功的情况下，所有的中间节点预留带宽，并将带宽承诺响应返回业务源，然后开始传送突发业务。一旦完成突发业务的发送，业务源发送一个释放带宽预留的消息，该消息沿各个中间节点传播直到收端。为了确保释放带宽的消息不会因丢失或误码受到干扰，传送释放消息时必须利用某种可靠的消息传输协议或定时器。这种机制对突发长度远远大于往返传播时延的突发业务非常有效。
　　对于立即方式，用户在发送一个包括某个突发要求的流量参数FRM信元后，立即发送实际的突发业务，输入节点和中间节点可以利用FRM信息决定是否可以处理整个突发业务。由于中间节点可能发生拥塞，因此，该方式不能保证突发业务的顺利传送，可能造成整个或部分突发业务的丢失。
　　(2)快速缓冲器预留
另一个可管理的资源是中间节点的缓冲器资源。在这类协议中，在发送突发业务之前先请求中间节点预留缓冲器空间，基本操作过程如下：当每个突发业务到达某个节点时，该节点比较每个(AAL域)FRM信元所要求的缓冲器长度和可利用的缓冲器空间。如果请求的缓冲器长度大于可利用的缓冲器空间，则不受理整个突发业务；反之，受理整个突发业务。网络通过确保整个突发业务能够在节点缓冲来保证整个突发业务不被丢失。
　　(3)具有快速恢复功能的资源分配
本论文介绍的具有快速恢复功能的资源分配体系结构，其基础是将节点的缓冲器预先分成两种空间：工作空间和备用空间，并提供备用路由。它能在ATM网络中实现可恢复的呼叫分配和快速VP恢复。为了缩短呼叫处理时间，工作空间和备用空间的动态分配和释放采用了并行分布式方式。在呼叫建立阶段，工作虚拟路径(WVP)和备用虚拟路径(SVP)上的当前的虚拟负载都会受到并行分布式方式的检测，以确保有足够的空间用于恢复故障和满足其它方面的QoS要求。如果有足够的空间，则该呼叫被接收，并容纳到WVP中，同时，用于呼叫分配和故障恢复的虚拟工作空间(WC)和备用空间(SC)也就被预定了。相反，如果没有足够的空间，该呼叫就会被拒绝。
2  实现可恢复的呼叫分配和快速VP恢复的结构
　　实现可恢复的呼叫分配和快速VP恢复的结构如图1所示。本结构分为两层：VP层和呼叫层。VP层负责VP集的分配、调整以及自愈合。呼叫层执行可恢复的呼叫分配，包括呼叫接收、路由选择、SVP选择(如果有多个可用的SVP)，以及工作空间和备用空间的预定和释放。呼叫接收、路由选择和SVP的选择是由源节点和目的节点通过并行分布式方式完成的。其间源节点和目的节点需要检测WVP集和SVP集上网络资源的可用性。

图1
　　(1)VP集分配和备用空间(SC)分配
　　VP控制机制为每对节点分配两个VP集、WVP集和SVP集。为了合理利用网络资源和优化网络性能，WVP集和SVP集应该一起给出。因为每对节点的SVP对于保护任意一段链路免出故障都相当重要，如图2所示。图中虚线表示SVP，实线表示WVP。当节点S、D间的WVP发生了链路故障时，就会启用SVP进行恢复。

图2
　　为了处理多个故障同时发生的情况(如两条链路同时失败)，该机制要求有多个链路分开的SVP，如图3所示。图中虚线表示SVP，实线表示WVP。如果节点S、D之间的WVP发生了链路故障，同时SVP1也发生了链路故障，就可以启用SVP2进行恢复。SVP上分配的SC必须足够大才能恢复WVP。对于那些属于意料之外的故障事件，可以采用某些紧急恢复措施，如自愈合型的分布式算法。另外，WVP既可以支持低优先级的事务，也可以支持高优先级的事务。开始紧急恢复的时候，低优先级的WVP集将会被断掉。至于高优先级事务，则可以采用发送者—选择者算法在VP层并行建立连接进行恢复。

图3
　　为了简便起见，下面讨论的都是单个链路故障的情况，实际中大多数故障都是此种类型。
首先作一些定义：
　　．链路的WC—链路上所有VC当前分配的总的虚拟带宽。
　　．WVP的SC—WVP上所有VC当前分配的总的虚拟带宽。
　　．链路的SC—SVP中某条链路上WVP所分配的带宽，SC是共享资源。
注释：
　　Xs1(a)—表示链路上为保护链路a所需要的虚拟SC。只有当链路属于保护链路a的SVP集时，才会是肯定值。
　　Xs1—链路1上的分配的虚拟SC。很容易看出，Xs1的最小值等于Xs1(a)的最大值，即：
Xs1=max(Xs1(a))　　(1)
　　表达式(1)可以作为SC的分配规则。因为SC是共享资源，呼叫分配并不一定会导致SVP链路上分配的SC总数的增加。为了在分布式体系中使用分配原则(1)，每个节点都必须掌握相邻节点的SC，每次发生呼叫接收或呼叫终止时，SC的值都应该得到更新。
　　(2)自愈型VP恢复
　　出故障的WVP的源节点一旦收到链路故障信息，马上开始恢复，恢复工作是在VP层完成的。在无需寻找备用路由和检测SC的可用性的情况下，就可以将故障WVP的事务转到相应的SVP上，转换工作也是在VP层完成的。对于每个受损的WVP，源节点按以下步骤实行自愈型WVP恢复。
　　第一步：将故障WVP上的VP标志(VPI)改成SVP上的VPI。
　　第二步：沿着SVP发送第一步中改变了的信息，SVP上所有节点将SVP视为新的WVP，并在相邻链路上更新WC原来的值。
　　第三步：如果故障已经涉及到一个SVP，则需要用VP集的调整策略。
注意：在第二步无需将确认信息送到源节点，这样可以加速VP的恢复。
　　(3)VP集调整策略
　　为了适应事务要求的变化和网络状况的变化需要不断调整VP集。如果指定的时间内被阻塞的呼叫个数超过门限值Q，就会触发VP集的调整机制。门限值Q必须根据业务类型进行确定，对那些连接成功率要求很高的业务，Q值必须设置得小一些。
　　调整一对节点的VP集实质就是为该对节点建立一个新的WVP，在有些情况下还要建立新的SVP。具体方法取决于拥塞发生的原因：因为拥塞原因可能是WVP空间不足或者是SVP空间不足，甚至可能是两者都空间不足。
　　为了降低第一种情况下的拥塞，VP集的调整过程会努力寻找一个有足够空间的WVP来容纳这些事务。只有当某个VP的每个链路上剩余的虚拟空间大于要求值D时，才会将该VP设立为新的WVP。新的WVP不仅要满足空间可用性这一条件，还须和SVP在链路上分开。
　　在第二种或第三种情况下，当SVP拥塞时，VP集的调整过程会努力寻找一条或几条新的WVP以及一个有足够空间的新SVP来满足需要，从底层网络拓扑中找出来的新WVP和SVP应该在链路上分开。
　　一旦呼叫阻塞数超过门限值Q时，就会触发下面的发送者—选择者算法。发送者向选择者发送一个询问WVP和SVP上资源可用性的请求，其目的是为了确定发生拥塞的源节点。
　　为了选择新的WVP，中间节点只在满足下面两个条件的节点上向前传送请求信息，其条件是：
　　1)虚拟剩余链路容量超过门限值D
　　2)链路不属于SVP
　　如果拥塞情况要求选择新的WVP和SVP，需并行执行最大流算法来完成查找工作。如果查找成功，发送者就会将新的WVP加到一对节点的VP集中。
3  将呼叫接收、路由选择以及分配WC和SC结合起来的算法
　　接下来本文将介绍一下将呼叫接收、路由选择以及分配WC\SC结合起来的算法，其基础是并行分布式呼叫处理结构。
　　如果路由选择策略(在下面将讲到)能找到一个WVP和相应的SVP，它们有足够空间分配和恢复到达呼叫，同时保证能恢复正在进行的呼叫，那么到达源节点的呼叫就会被接收，否则呼叫被拒绝。如果每段链路的虚拟空间都比到达呼叫要求的带宽大，则该WVP/SVP具有足够的空间。
　　空间检测用发送者—选择者机制完成。发送者位于源节点，它沿着WVP和SVP向各个节点发送虚拟WC分配请求和SC分配请求。请求中包含到达呼叫的带宽请求和VPI，所有分配请求都是并行处理的，其结果由选择者在目的节点收集。
　　空间分配如下执行：选择者根据底层的路由策略从通过了空间检测的WVP和SVP表中选择用于呼叫分配的WVP和SVP，并沿着选定的WVP和SVP发送WC分配请求和SC分配请求。两种请求中都包含了呼叫的带宽请求和选定了的WVP的VPI。
　　WC的分配是直接进行的，SC的分配需要满足SC的恢复要求Xs1(a)，这个工作是在SC分配请求经过SVP链路时完成的。对于SVP的每条链路，相关的每条WVP链路a的Xs1(a)值都得到更新，Xs1(a)的新值等于当前值加上呼叫要求的带宽，分配的SC，Xs1也根据表达式(1)得到更新。选定了的WVP的VPI在分配请求中用来标识链路a。
　　本结构中用到的路由策略通常有两种：固定路由选择和可变路由选择。
　　(1)固定路由选择
　　在固定路由选择机制中，每个WVP都有一个预先设置好的提供可用负载的函数，被接收的呼叫容纳在预先分配的WVP中。如果采用自适应的固定路由，函数值的大小可以每小时或每天调整一次，以便适应需求的变化。固定路由的呼叫接收、WC的分配和SC的分配操作如下：发送者沿着分配好的WVP和SVP发送WCAR(WC分配请求)和SCAR(SC分配请求)。
　　1)如果某中间节点的下一个WVP/SVP链路有足够的空间，则该中间节点通过了空间检测，并将请求沿着WVP/SVP传到下一个节点。否则，该节点给发送者和选择者发送否定消息。
　　2)如果选择者从WVP和SVP收到肯定的确认信息，就会沿着WVP和SVP向发送者发回合适的WC和SC分配信息。
　　3)WVP/SVP的每个中间节点更新WC/SC。
　　4)如果发送者从选择者那里接收到肯定的确认消息，就会将呼叫置于WVP中，否则呼叫被拒绝。
　　(2)可变的路由选择
　　在可变的路由选择机制中，源节点和目的节点间的所有WVP都分配了等级(通常情况下，最小跳数的路径等级最低，固定路由中用到的空间可用性的检测方法也适用于检测可变路由中WVP和SVP，选择者将选择既通过了空间检测又具有最小等级的WVP。这种情况下的呼叫处理过程基本上类似于固定路由中的呼叫处理过程，只是有以下两点修改：
　　1)WCAR和SCAR并行地传送到WVP和SVP上的所有节点。
　　2)选择者选择既满足空间要求又具有最小等级的WVP来容纳呼叫。
　　WVP等级可以根据需求的变化每小时或每天更新一次。
4  总结
　　本文介绍了用于ATM网络中的一种新型资源分配体系结构。该种资源分配方式比传统的资源分配方式能更好地恢复网络故障。由于传统的资源分配方式最多只能保证业务有一条路径到达目的节点，所以，一旦该路径上某段链路或某个节点发生了故障，就会丢失部分业务甚至丢失全部业务。而新的资源分配方式就不会出现这种情况。因为它不仅提供一条正常情况下的工作虚拟路径，还提供一条备用虚拟路径。一旦工作虚拟路径发生故障，就可以启用备用虚拟路径，这样就可以避免丢失业务。
　　当然，这种方式也不是完美的，它虽然能快速恢复故障，但是，它也会造成一定的带宽和节点空间的浪费。目前由于各种技术的发展，可用带宽已相当大，而网络的稳定性和可靠性却是急待解决的问题。鉴于这种情况，牺牲一定量的带宽换取网络的稳定性和可靠性还是可取的。
黄德能(上海铁道大学计算机科学技术系  上海 200331)
薛小平(上海铁道大学计算机科学技术系  上海 200331)
阮永良(上海铁道大学计算机科学技术系  上海 200331)
参考文献
1，杨宗凯. ATM理论及应用. 西安: 西安电子科技大学出版社, 1997
2，Uyless Black. ATM宽带网络技术基础. 北京: 清华大学出版社, 1998
收稿日期：1999-12-27
