刘昆宏，徐 永
福建师范大学 物理与光电信息科技学院 350007
摘 要：流量疏导是当今光网络研究中的一个前沿和热点问题，在波分复用(WDM)光网络中使用流量疏导技术能有效降低网络的成本，减少网络节点中业务信息的处理量.文章讨论了动态流量疏导的意义及其分类，分析了关于在各种网络结构中动态流量疏导的研究近况，最后对今后的发展方向做了一番展望.
关键词：波分复用；动态流量疏导；分插复用器
Internet的迅猛发展极大地推动了光网络研究的进展.随着波分复用（WDM）技术的日趋成熟，限制光网络中传输容量进一步提高的因素已不再是光纤带宽，而是网络中路由器、交换机和复用器等电子设备的处理速度造成的瓶颈，波长带宽与一个典型业务连接之间的巨大差距也开始成为一个新的热点.流量疏导技术的出现为解决这些问题提供了一种有效途径.流量疏导研究的是如何将不同速率、不同类型的低速业务打包成高速数据流，复用到一个波长上，用来实现某种设计目的的过程.在由SONET/WDM构成的网络中，每一波长可通过时分复用（TDM）方式承载很多低速业务流.由于上路或下路一个低速业务只能在该业务的两个终端节点上的分插复用器（ADM）中完成，且对每一个在节点处上/下路的波长都需要在该节点放置一个ADM对相应的业务进行处理.若每一波长都在每个节点处下路，则需要大量的ADM.为减少网络节点的信息处理量及ADM的用量，可以用波长上下路复用器（WADM）有选择地下路一些波长，而将未携带与该节点业务有关的波长进行光学直通.流量疏导的目的之一就是确定每个波长所携带的低速业务流，以减少波长和ADM的用量.但研究表明，大多情况下不能同时对波长与ADM的数量进行优化，所以目前流量疏导的主要目的是减少ADM的使用数量.已经证明单向环网中的流量疏导问题为NP-难问题，其计算量随网络中节点数的增加而呈指数增加，可知对一般网络中的流量疏导问题的计算必将更为复杂.本文将对流量疏导问题的有关概念、动态流量疏导问题的研究现状及今后的发展趋势做一评介.
1 动态流量疏导的意义及其分类
业务流量疏导，可以根据被疏导的业务是否随时间变化而分成静态流量疏导和动态流量疏导两大类.目前关于流量疏导问题的研究主要是针对静态业务流量进行的，它是指对一组已知的且不随时间变化的业务需求进行疏导，其目的是使用最少的ADM数来支持这组业务.但由于网络中的业务量通常是随时间不断变化的，因而，对动态流量的疏导将更具有实际意义.事实上，如果用一组静态业务来表示某一时刻的业务量，用多组有序的静态业务就可以反映业务随时间的变化，表示一组动态业务.因而静态流量疏导可以看成是动态流量疏导在某一时刻的特例，即一个动态流量疏导问题可以看成由多个静态流量疏导问题组成.尽管如此，一个动态流量疏导过程却不是多个静态流量疏导过程的简单迭加.动态流量疏导实际上是在一套逻辑拓扑中，在不改变ADM和波长的数量及ADM分布的情况下，通过动态改变各个波长所承载的业务，调节业务在波长中的分布以便用最少的ADM数来支持动态改变的业务.由于业务需求的动态变化，业务流量分布往往存在互补和匹配的情况，相同节点对间的业务在不同时刻具有不同的大小，从而有可能使多组业务共享相同的ADM、以达到减少ADM数、降低网络成本的目的.在动态情况下进行优化后的ADM及波长数将远远小于通过对其中每个静态业务流量分别疏导所得到的ADM及波长数量的总和.
对动态流量疏导的研究在1999年就提出了，但至今仍极少有文献涉及，主要原因是动态流量疏导算法的复杂性远远超过静态流量疏导，且随着节点数的增加与业务变化范围的扩大，找到有效的动态流量疏导方案将是极其困难的.由于大多数情况下实际网络中业务需求是随时间不断变化的，对动态流量疏导问题的研究必将成为今后的一个热点.
文献［1］根据网络在动态流量疏导过程中的阻塞特性将动态流量疏导分为3类：严格无阻塞疏导、广义无阻塞疏导和可重构无阻塞疏导.严格无阻塞疏导是指新业务需求中的所有业务请求都能不被中断地建立且无需任何算法；广义无阻塞疏导是指新业务需求中的所有业务请求都能不被中断地建立但需要某种算法对新的业务进行分配；可重构无阻塞疏导是指新业务需求中的所有业务请求都能被建立，但建立过程中有些请求可能被暂时中断且需要引入某种算法来对新的业务进行重新分配.这3种动态流量疏导的阻塞特性与网络的性能和造价密切相关，使用的优化算法也有较大的区别.
2 动态流量疏导的研究现状
目前关于动态流量疏导的研究工作尚处于刚刚起步阶段，相关的文献不多，且大多数文献未考虑波长在节点中的改变，即节点中只使用ADM与WADM上下路业务，对使用HUB、数字交叉连接（DCS）等器件的网络进行分析的文章只有文献［2］.由于网络的虚拓扑不同会影响到流量的路由，下面根据网络的结构分别进行说明.
2.1 对环形网的疏导
目前对环形网络中的动态流量疏导问题提出了多种不同的算法，下面分别进行讨论.
文献［3］提出了环形网中每个节点上/下路的业务总量不大于t个基本业务量（文中称之为t-allowable）的动态流量疏导问题，分析了最大业务流量的情况（即在每个节点上/下路的业务总量都为t，定义为t-maximal），以实现对所有t-allowable的动态业务流量进行严格无阻塞和广义无阻塞疏导.作者将求解最小ADM数问题转换为求解二分图的匹配问题，实现对t-maximal业务矩阵的疏导问题的求解，得到了比无疏导情况减少27％ADM数的较好结果.
文献［4］详细讨论了单、双向环网中的静态及动态流量的严格无阻塞和可重构无阻塞疏导问题，导出了一个统一描述静态和各种阻塞类型的动态流量疏导问题的多目标方程组.该方程组具有很好的通用性，允许对各部分业务信息的路由进行同步优化，适用于ADM与波长数的各自单独优化或混合优化.作者分别用遗传算法和禁忌搜索算法对动态流量严格无阻塞和可重构无阻塞疏导问题进行优化.作者还做了大量的计算机模拟，得出了最多比无疏导情况减少59％ADM数的很好的结果，并对结果进行了详细的分析和讨论.
文献［5］讨论了动态流量的广义无阻塞疏导.作者将流量疏导分两步进行：最佳匹配（Bestfit），其目标是在不添加ADM的情况下尽可能地将业务流量导入现有的网络中；充分匹配（Fullfit），其目标是在添加最少的ADM的基础上有效地支持新的业务流量.作者先用整数线性方程组进行描述，然后分别设计了贪婪算法和禁忌搜索算法寻求最优解.结果表明，用贪婪算法，当节点数为5、业务粒度为3时，所能建立的业务连接数与理论上限的比值最大，为92％；而节点数为20、业务粒度为12时，只有63％.对禁忌搜索算法，作者只讨论了对静态业务的流量疏导问题，并得到了比贪婪算法更优的结果.
2.2 对互连环网络的疏导
文献［6］研究了在光层中环网间互连的方案，构造了双点接入（Dualhoming）的互连网络.作者将二分图的算法拓展到环间互连的网络，采用分步计算的方法，首先将低速的数据流疏导入光路中，然后再将光路映射入拓扑中，并用遗传算法分别对这两步求解.为实现互连的环网中所有动态流量的疏导，作者将环间的业务矩阵分成3个独立的子矩阵，两个描述环内业务（Intraring），一个描述环间业务（Interring），然后分别使用上述算法计算这3个矩阵.作者将这一算法与其它文献中提出的方法进行了对比，得出了该算法较优的结论.
2.3 对格状网的疏导
文献［7］中作者使用自己定义的一种辅助图来推导格状网的动态流量疏导问题，并利用辅助图求解最短路径的方法来实现动态流量的疏导.通过改变辅助图中各边的权重可以实现不同的优化结果 和网络性能.应用这种方法可以实现严格无阻塞和广义无阻塞疏导.作者分析了发射机的成本对网络造价影响最大时的最优方案和波长链路资源紧张时的最佳方案，并设计了可调节疏导方案把上述两种方案结合起来.从计算机的模拟结果来看，可调节疏导方案在多种情况下均有较优的表现.
2.4 对含有DCS与HUB的网络的疏导
在文献［2］中，作者考虑了3个价格因素：波长数、ADM数和最大跳数.其中ADM数是作者最关注的优化对象.文章对网络模型进行了简化，在此基础上讨论了静态、动态和增长性（Incremental）3种类型业务.文中建立了一个静态全连接对称业务和两个动态业务模型，以这3个模型为基础，设计了6种网络结构，并使用了DCS与HUB.作者分别设计了计算构造网络所需的上述3个价格因素算法，并证明了它们的网络阻塞特性.最后，作者比较了6个网络的3个价格因素及它们所适用的业务模型.结果表明，当波长资源充分时，对动态业务，单HUB结构所需收发机的数量较少；而对静态业务，双HUB网络为较好的选择.当波长资源比较缺乏时，对于动态业务，能最有效地利用波长的是点到点WDM系统（PPWDM）结构；如果波长中存在空闲链路，则使用Hierarchical结构能减少收发机的数量；而对静态或增长型业务，Incremental结构能使波长和收发机的数量最小化.
2.5 小结
以上讨论的是针对不同的网络结构或不同的对象进行优化的算法，难以对它们进行直接比较，但这些文献中提出的算法都各有其优点，同时也存在不同程度的局限性.
文献［6］中使用的分步计算简化了算法，并且对单向环或双向环都适用.但因为每一步的最优解对全局可能不是最优的，使结果的优化程度依赖于各步的优化过程，所以最终得到的解可能不是全局最优解，并将不可避免地导致网络中某些ADM的闲置.随着业务组数的增加，该算法的复杂性将呈指数增加.另外，这种分步进行的算法不可避免地增加了运行时间.文献［1］和［4］中采用的方法就避免了上述问题.文献［3］中使用的二分图算法，只适用于两组业务需求的情况，当业务组数较多时，这种方法也可以使用，但将变得异常复杂.
分析上述文献中经过计算机的模拟计算得到的优化结果，我们可以看出，以上文献都采用数学规划方程、贪婪算法、遗传算法、禁忌搜索算法和图论方法.使用数学规划方程描述网络，能得到最优值，但其计算极其复杂；而用图论的方法也有其特有的复杂性，它们所需要的计算时间都随网络的规模呈指数增长，对较大的网络几乎是不可能得到结果的.用贪婪算法、遗传算法和禁忌搜索算法等启发性算法计算，可以得到较优的解且计算时间并不太长.
3 今后的研究方向
由于动态流量疏导的计算难度比静态流量疏导要大得多，即使在环网络这样一种相对简单的网络模型中，各种优化也是建立在一些特定模型或对某些特定目标的设定的基础上的，当节点数较多时更是难以设计出一种完善的算法.因此今后动态业务流量的疏导将存在许多挑战性的问题.
（1） 对不规则网络结构的流量疏导
当前的文献所讨论的流量疏导问题主要针对环网络，对格状网和树形网的研究极少，因为即便在环网络这样一个相对简单的网络结构中，流量疏导问题已经是一个NP-难问题，对格状网和树形网这样的网络结构自然更是复杂.由于实际应用中的网络结构往往是不规则的，并且对不同网络的规划过程中需要优化的目标也将不尽相同，因此，设计出广泛适用于不同的网络结构和优化目标的通用性较强的算法将是今后研究的重点.
（2） 动态流量疏导与一些相关技术的结合
到目前为止，极少有文献讨论有关路由技术在流量疏导中的应用.虽然已经有例子说明使用最短路径路由法对双向环网的网间连接的流量疏导没起到明显地优化ADM数量的作用，但它能减少使用的波长数，文献［4］对静、动态流量的疏导就得出双向环中所用的波长数约为单向环的1/3的结论.但无疑在网间的流量疏导中使用某些高级的路由技术能减少光信息传输过程中经过的中间节点并缩短物理路径.另外，在格状网中，由于每一对节点间的物理连接都可能有多种选路方案，使用路由技术将有更大的意义.但考虑到由于路由技术的引进，算法将变得更为复杂，因此，路由技术在动态流量疏导中的应用将会是今后的一个挑战.而在静态流量疏导过程中已经应用的一些技术，如业务分叉，尚未应用到动态流量疏导中.由于这些技术在静态流量疏导中的应用有明显的优化效果，能进一步减少ADM的数量，在动态流量疏导中必将有极佳的实用价值.此外，已经证明DCS、HUB和可调谐激光器等器件在流量疏导中的使用能有效地减少ADM的用量，但由于目前探讨这些器件及波长转换器在动态流量疏导中应用的文献还几乎没有，因而深入讨论这些器件对动态流量疏导所起到的优化效果仍是一个大有可为的课题.
（3） 流量疏导技术与网络新技术的结合
随着光网络应用的不断深入，一些新的技术开始成为研究的热点，主要有：光组播网络（Multicast Optical Network）、光任播网络(Anycast Optical Network)和IP over WDM等.如何将流量疏导技术与这些技术相结合将是极好的研究课题.特别是由于IP技术的广泛应用，IP over WDM技术将是未来光网络研究的一个重点.未来的IP网络将使用WDM交叉连接器通过路由器直接连接各个波长，而不是用ADM，每个波长必须携带来自不同路由器的多个业务信息，并通过相应的光学直通机制减少每个路由器的接口数量与交换的信息量.这与前面描述的对SONET网络中业务流量进行疏导的过程相似.但由于IP网络多是格状网或其他不规则网络，并且IP数据包的特点是高度动态和不能预知的，因而对IP动态业务流量进行疏导将更具有研究价值.
总之，对动态业务流量疏导的研究工作仍处于起步阶段，这是一个前沿且极具商业价值的研究领域.随着WDM技术在世界范围内的广泛应用，新的研究课题将不断涌现，动态业务流量疏导的研究与应用领域必将不断扩大.
参考文献
［1］Xu Y, Xu CS, Wu BX. Strictly nonblocking grooming of dynamic traffic in unidirectional SONET/WDM rings using genetic algorithm [J].ComputerNetwork，2003，41(2)：227-245.
［2］Gerstel O, Ramaswami R, Sasaki GH.Cost-effective traffic grooming in WDM rings [J]. IEEE/ACM Transactions on Networking，2000，8(5)：618-630.
［3］Berry R，Modiano EH.Reducing electronic multiplexing costs in SONET/WDMrings with dynamically changing traffic [J].IEEE Journal on Selected Areas in Communications，2000，18(10)：1961-1971.
［4］徐永.SONET/WDM光环网中业务流量的智能疏导 [D].厦门：厦门大学，2002.
［5］Zhang S，Ramamu B.Dynamic traffic grooming algorithms for reconfigurable SONET over WDM networks [DB/OL].http：//banyan.cm.nctu.edu.tw/broadband/no1168.pdf.
［6］Xu J, Zeng QJ. Dynamic traffic grooming in interconnected WDM SDH/SONETrings [A].In SPIE，Proc. Conf. Technologies,Protocols,and Sercices for Next-Generation Internet [C]. Proc. SPIE, 2001.
［7］Zhu HY, Zang H, Zhu KY,et al. Dynamic traffic grooming in WDM mesh networks using a novel graph model [DB/OL]. http://networks.cs.ucdavis.edu/publications/2002-zhuh-2003-07-20-06-12-19.pdf，2003-06-12.
摘自《光通信研究》
|