基于Kautz图和OPS的多层光分组交换网络调度准则研究*

郑 羽，胡积宝，董甲东,

(1.安庆师范大学 现代教育技术中心，安徽 安庆 246133； 2.安庆师范大学 物理与电气工程学院，安徽 安庆 246133)

基于Kautz图和OPS的多层光分组交换网络调度准则研究*

郑 羽1，胡积宝2，董甲东1,2

(1.安庆师范大学 现代教育技术中心，安徽 安庆246133；2.安庆师范大学 物理与电气工程学院，安徽 安庆246133)

多跳光网络是满足日益增长的互联网服务应用的最合适的解决方案。将常规的Kautz图从一层扩展为多层，以产生更多架构上的变化。相邻层之间采用常规Kautz图的系统连接方式，并由此提出了一种基于属性的路由算法。采用光无源星形耦合器来实现新的拓扑结构。为了解决中间节点争用问题，评估并比较了三个调度准则，主要原则是它们提高可用性的能力。

光分组交换；Kautz图；无源星形耦合器；拓扑设计

0 引言

光纤技术在当前的通信网络中发挥着重要的作用。光网络可能是单跳或者多跳。一个多跳网络不需要快速调整收发器或任何预传输的协调。从源节点到目的节点的流量可能会经过一个或多个中间节点。流量在这些节点间经历了光-电-光(O/E/O)的转换，在被处理前以不同的波长通过另一个连接被发送。节点可以是任何产生、接收和路由数据包的终端。关于多跳光网络的设计已经提出了很多的逻辑拓扑结构，其中Kautz图是一个可行的选择。相比于其他已知的正则图，如de Bruijn图(DBG)或Shuffle Net图[1]，Kautz 图在相同节点度的情况下平均跳数最小。此属性使得Kautz图是作为多跳光网络拓扑结构的很好的选择[2-3]。Kautz图已在光网络中有不同形式的应用，如单一的Kautz图和栈Kautz图(SKG)[4]。SKG网络的设计通过堆叠系列的正则Kautz图和两层节点之间的连接形成一个小的分区OPS(光学无源星形)网络。这种拓扑结构通过使用低度操作耦合器可以支持大型的网络。在这种网络中，设备的总数仍然很多，控制任务繁重。

本文目的在于设计一个灵活、易于实施的数据包交换网络拓扑结构[5-6]。一个主要目标是决定在复杂度、灵活性和可实施方面具有良好性能的逻辑网络架构，还要对建议的拓扑结构的路由算法进行检查。为了实现目标，结合Kautz图和多层拓扑的优点。此网络架构能够克服Kautz图网络的一些缺陷。同时也会考虑OPS耦合器的实施以及用于解决争用的三个调度方案[7-8]的分析。

本文首先提出了一个多层网络模型；然后使用单波长和多波长OPS耦合器来设计模型的架构；接着提出了模拟结果，并对其进行了比较和分析，讨论了如何用目前的技术来实现；最后，基于分析做了讨论。

1 网络模型和运用

为了介绍多层拓扑的定义和操作，总结了Kautz图KG(d，k)的属性。G=(V，E)是一个Kautz图，V是节点集，E是边集，点入度和点出度为d，直径为k。每个顶点被标记为一个长度为k的串，如(x1，x2，…,xk)。每个字母都是从d+1个字母表中选择的。每个标签的串都有一个条件，即没有两个连续的字母是一样的。当且仅当顶点X的最后k-1个字母和顶点Y的最后k-1个字母是一样的，两个顶点间才会有一条边。如顶点(x1，x2，…，xk)与d个顶点(x2，x3，…,xk，z)相邻，这里z是任意一个与Xk不一样的字母。在Kautz图中，从节点X到节点Y的最优化(短)的路由路径是由一个路由串(x1，x2，…,xn+d)决定的，这个串代表了一系列的n跳。图1是一个(2，3)图。作为一个正则图，Kautz图的应用非常有限，因为每个节点都要遵守定义好的连接模式。表1所示为KG图与OBG图及ShuffleNet图在各个性能参数上的比较。

图1 KG(3，2)Kautz图

节点数/N平均跳数/h链路负载/LKG(3，3)362．5918．44(4，4)3203．67212．58(4，5)12804．651168．39DBG(3，3)272．4821．48(4，5)10244．582344．92ShuffleNet(3，3)182．7212．33(4，7)10245．171323．00

MKG网络用于光分组交换网络，这样可以以类似Kautz图的方式定义路由规则。对于同一层的两个节点，可以使用一个Kautz图的最优路由算法，这在新的结构中也是最优的。当源节点(ls，x)和目的节点(ld，x)根据层的位置判断处于不同层时，可以把路由算法分成两种情况。假设在一个单一Kautz图上的最优路由线路从一个节点x到节点y是 (x1，x2，…，xn，y1，y2，…，yk)，跳数等于n，这样就知道:

(1)如果n≥(ld-ls+m) modm：路由串将和在单一Kautz图上一样。路由的开始n-m个节点将位于源层中。剩余m节点的标签和最短路由上最后m个节点的是一样的，在每一个步骤中，每个节点的层数将增加1。

(2)如果n≤(ld-ls+m) modm：在这种情况下，路由字符串将扩展匹配层的差异。一些冗余的节点必须插入到最优(最短)路由路径以保持连接关系，即在路由串中不能分配两个相同的相邻字母。新的路由串的跳数大于或等于处在不同层的源节点和目的节点的跳数。路由规则将类似于第一种情况，即首先在源层拿一些跳数。

以MKG(4，2，3)中节点(4，121)到节点(3，101)的路由为例，在KG(2，3)中，从(121)到(101)的最短路由是由跳数n为2的路由串(12101)决定的。在MKG(4，2，3)中，(4，121)到(3，101)的层差异是3(即(ld-ls+m) modm=(3-4+4) mod 4)，这个值比2大，因此，新的路由串是(12101)的扩展，会把跳数增加到至少3。因为新的路由串的左端和右端分别就是源节点和目的节点，这是不会变化的，最短的新的路由串的形式将变成121…101。因为源节点121的最后一个字母和目标节点的首字母101是相同的，一个不同于字母“1”的冗余的字母需要插入两者之间，所以新的路由串是跳数等于4的(1212101)。表2说明了一些MKG的典型性能结果。

表2 一些MKG的性能

从表2中能看出，当层数m接近单个图的直径d的时候，跳度的平均数量会变得更小。通过选择不同的组合层和图的大小，可以获得不同给定大小的MKG，然后可以选择具有最佳性能的MKG。这种类型的网络设计显然有更多的灵活性。

注意，路由路径可以动态地取决于所需的网络条件和所需要的跳度数。首先，只要未完成的跳度的数量不小于从当前节点到目标节点的层数，跳度数可以在同一层或两个相邻层上。在上面的例子中，不改变节点的标签，可以让层序列变成4-1-1-2-3或4-1-2-2-3或4-1-2-3-3。其次，可以使用自适应路由，而不是固定的路由，因为整个路由路径可以用路由字符串(x1，x2，…，xn，y1，y2，…，yk)表示，通过插入一些冗余的字母到字符串来调整中间节点，同时保持第k个和最后k个字母分别成为源节点和目的节点。这个插入将产生更多的跳度数，不过改变流量将变得更加灵活。

2 OPS耦合器的实现

采用d×d的OPS耦合器来实现。网络中的每个节点连接到两个OPS耦合器，一个连接同一层的节点，另一个连接到下一层的节点。那些连接到相同目的节点的节点也会连接到相同的OPS耦合器上。尽管MKG的节点的度数是2d，但是需要d×d的OPS耦合器。度数偏低，更易于实现。需要一个时间段(或是称为一个时间步)的数据包从一个节点传播到另一个节点。因此，整个网络可以被认为是运行在连续的时间段。所有时段都包含这一系列步骤。

2.1控制问题

对MKG的每一层，选择一个节点作为节点组的控制节点，节点组共享两个相同的OPS耦合器。节点的操作受节点组的控制节点的控制。组中的任何节点组都可以成为控制节点组，它的任务是为了收集所有传递节点组的数据包的头信息和发送控制信息，并指导节点的操作。当两个或两个以上的数据包到达一个或多个与目的地相同的输出链接节点时，需要访问相同的具有相同波长的OPS耦合器，这就可能发生争用。必须采取一些调度原则来解决争用问题，比如在数据包通过OPS耦合器时，赋予它们不同的优先级。只要缓冲区非满，不能获得传输许可的数据包存储在缓冲区中。

(1)“延迟”法：在当前序列步骤中累计最长延迟的数据包将获得最高优先级。延迟包括缓冲时间和传输时间。

图2 单一波长环境中的平均延迟

(2)“距离”法：距离目标节点路径最短的数据包将获得最高优先级。

(3)“时间等待”法：在当前缓冲区具有等待时间最长的数据包将获得最高优先级。

2.2使用单波长OPS耦合器

图3 采用多波长的MKG(4.2.3)性能考虑(“延迟”的方法)

OPS耦合器是一种能够匹配网络需求和应用组件技术的可行的选择。设备虽简单，但潜力无限。第一个实现模型利用单波长OPS耦合器，它不需要昂贵和复杂的可调收发器。目前，可调组件仍然昂贵，很难制造，所以单波长法被认为是第一个可行的方法。每个节点配备固定波长发射端和接收端。在任意时间，每个耦合器中只有一个波长是可用的，这意味着一次只有一个节点可以访问某个OPS耦合器。如果没有控制机制来区分输入和输出，每个输入和输出连接都能够接收和传输同等优先级的信号。在各个时间段，在一个OPS耦合器中允许一个节点发送一个数据包。当发生争用时，只有满足某些条件的数据包可以通过耦合器。虽然信号传递到所有输出链接，但只有一个接收端可以接收数据包。

3 性能评估

这里模拟的主要性能标准是延迟，定义为持续时间(在数量的序列步骤)即数据包的生成时间到其服务完成时间，即数据包需要传输和缓冲的时间总数。之所以选择延迟作为分析的目标，与光信号的传输特性有关。为了补偿长距离光纤传输中的功率损耗，将使用光放大器，这将带来更多的非线性效应，降低信噪比。因此，在一个良好的光学结构设计中，减少延迟是一个重要的目标。选择了两个网络来进行分析，分别为有48节点的MKG(4，2，3)和有540个节点的MKG(5，3，4)。

图2显示在单一波长情况下的平均时延随数据包到达率的变化。注意水平轴也是标准化的负载(一个新的数据包在每个时间段生成的节点概率)，因为服务时间也正好是一个时间段。图3和图4是多波长的平均延迟和延迟分布的情况，从图4可以看出，在MKG(4，2，3)网络的平均延迟与负载的增加呈指数增长，正如预期的一般延迟-吞吐量关系的经典排队论。当负载接近30%时，延迟大大增加。通常情况下，网络的性能将是不可接受的非常高的延迟。从图4(b)看到，MKG(5，3，4)中这种情况会出现得更早，也就是说，在图4(a)中负载是0.1而不是0.3。估计第二种网络的规模将是以前的10倍并且更复杂。

结果表明， 与MKG(4，2，3)单一波长的情况相比，图4中的平均延迟以同样的方式增加。可是，在相同的网络延迟情况下，多波长网络能够比单一波长网络支持两倍的负载。显然，这性能的改进是基于两个波长的代价而不是单一波长的使用率。类似的结论可以从MKG(5.3.4)中通过比较图3(b)和图4(a)得出。

图4 采用多波长的MKG(5.3.4)性能考虑(“延迟”的方法)

4 结论

本文提出了一个基于多层网络结构的Kautz图(MKG)，并且已经建模和模拟了使用光分组交换OPS耦合器的MKG网络的性能，这种被动的OPS可以将延迟限制到一个可接受的范围内。当使用可调的接收器和发射器时，性能有明显改善。提出了可以实现预定目标的三个调度争用解决方案。对一个低负载的小规模网络，它们没有表现出明显的差异。然而，对于一个更大网络或更高的负载，“距离”方法可以用更少的序列步骤提供更多的数据包，而“等待时间”方法在一定数量的步骤以后会变得更快。根据网络的需求，可以选择恰当的方法。

[1] BANERJEE S， JAIN V， SHAN S.Regular multihop logical topologies for lightware networks[J].IEEE Communications Surveys，1999,2(1): 2-18.

[2] PANCHAPAKESAN G，SENGUPTA A. On multihop optical network topology using Kautz digraphs[J].IEEE INFOCOM’1995, 1995: 675-682.

[3] RAVIKUMAR C P，RAI T，VERMA V.Kautz graphs as attractive logical topologies in multihop lightware networks[J]. ComputerCommunications，1997,20(14): 1259-1270.

[4] COUDET D，FERREIRA A，PERENNES S.Multiprocessor architectures using multi-hop multi-OPS lightwave networks and distributed control[J]. IEEE International Parallel Processing Symposium, IPPS 1998，1998: 151-155.

[5] GOUDERT D S，MARCHAND P J，HARVEY P，et al.Photorefractive beam splitter for free-space optical interconnections[J].Applied Optics，1998,37(26): 6178-6181.

[6] 蓝晓青,禹继国.基于Kautz图的新型多跳光网络拓扑结构[C]. 北京地区高校研究生学术交流会通信与信息技术会议,2008.

[7] Zhang Zhensheng，ACAMPORA A S. Performance analysis of multihop lightware networks with hot patato routing and distance-age-priorities[C]. IEEE Tenth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM’91,1994,42(8): 2571-2581.

[8] 王玉林，游红，李广军.基于Kautz图的服务覆盖网带宽约束路由算法[J].计算机应用，2010，30(6): 1443-1446.

2016-12-21)

郑羽(1981-)，通信作者，男，硕士研究生，高级工程师，主要研究方向：计算机网络、信息管理与信息系统。E-mail:fangshuan@126.com。

Research on scheduling criteria of multi layer optical packet switchingnetwork based on Kautz diagram and OPS

Zheng Yu1, Hu Jibao2, Dong Jiadong1,2

(1. Modern Education and Techonology Center, Anqing Normal University, Anqing 246133, China； 2. Physics and Electronic Engineering department, Anqing Normal University, Anqing 246133, China)

The multihop optical network is the most suitable scheme to satisfy the growing application of Internet service. This article develops the ordinary Kautz graph from one layer to multiple layers, which can produce more change in frame. Ordinary Kautz graph connecting system is used to connect adjacent layers, and by which a kind of routing algorithm based on its property has been put forward. Optical passive star is employed to achieve new topology. In order to solve the middle joints to be contented, we’ve evaluated and compared three dispatch criterions. The main principle is their ability to raise the possibility for use.

optical packet switching; Kautz graph; passive star coupler; topology design

TP399

A

10.19358/j.issn.1674- 7720.2017.22.019

郑羽，胡积宝，董甲东.基于Kautz图和OPS的多层光分组交换网络调度准则研究J.微型机与应用，2017,36(22)：70-73.

安徽省2016年高校自然科学基金重点项目(KJ2016A430)；安徽省教育厅教学研究项目(2016jyxm0628)