2. 重庆邮电大学 自动化学院, 重庆 400065
组播的应用使光交换节点的丢包率和分组竞争概率增加.为解决这个问题, 综合考虑节点的结构代价和丢包率性能因素, 设计一种反馈共享的有限范围多波长转换器和输出共享的基于逻辑运算的全光网络编码器结合的光组播节点结构, 并在光组播调度策略中着重考虑最小化波长转换度的组播冲突问题, 提出一种基于改进的最大权重独立集算法的波长分配方法.仿真结果表明, 相比现有的光组播节点及算法, 该结构能够在低成本代价和低时延的基础上降低丢包率, 提升了光组播节点的性能.
2. School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Increasing of multicast application makes the packet loss probability and the probability of packet collision increase in optical switching node. To improve it, a novel optical multicast switching node architecture integrating with the advantage of multi-wavelength conversion technology and network coding technology is designed. A group of feedback shared limited range of multi-wavelength converters and a group of output shared network encoders are configured in the optical multicast node architecture. With respect to the minimal wavelength conversion degree in optical multicast scheduling, an improved maximal weighted stable set is designed to optimize the wavelength assignment. Comparing with the existing optical multicast nodes and algorithms, the simulation results show that the proposed node architecture and algorithm largely reduce the packet loss probability with low node cost and low delay to improve the optical node performance.
近年来，随着组播应用的不断增加，人们对于多点传输的需求越来越大.但组播在光交换节点处的复制和转发都加大了光分组在交换节点处资源竞争的概率.因此，在光组播节点中如何高效率地解决分组冲突是实现全光组播的关键问题.波长转换是一种将承载冲突分组的波长转换到另一个空闲的波长的冲突解决方案.刘焕淋等[1]提出一种基于有限范围多波长转换器和全范围波长转换器的双层波长转换(TLWC，two layers wavelength conversion)节点结构.
随着网络编码的不断发展，Manley等[2]提出在节点结构设计中，将冲突分组编码为一个分组包，发送到目标波长上，可以有效解决分组冲突[3]. Qu等[4]提出一种基于逻辑运算的全光网络编码机制，有效避免基于光/电/光(O/E/O，opto-electro-opto)换降低处理速度问题[5].
1 光组播节点结构及其工作原理笔者设计一种综合波长转换技术和网络编码技术的光组播交换节点结构(OMN-MCNC，optical multicast node with of multi-wavelength conversion and network coding)，如图 1所示.该结构包含1个交换矩阵，N根输入(输出)光纤，N个复用器，r个有限范围多波长转换器(LMWC，limited multiple wavelength converter)，(N+r)个解复用器和h个异或单元XOR.每根光纤上承载M个波长，每个波长都是一个独立信道.有限范围多波长转换器采用反馈共享的配置方式，基于逻辑运算的全光网络编码器采用输出共享方式配置.
|
图 1 OMN-MCNC节点结构 |
在一个时隙周期内，当分组到达光交换矩阵时，若没有冲突，则分组无延时地直接送到目的端口.若2个或2个以上分组去往同一输出光纤的波长端口，首先判断冲突分组是单播还是组播.若冲突分组是组播分组，随机选取一个LMWC进行竞争解决.若无可用多波长转换器或波长信道全部被占用，则将冲突分组送到网络编码器解决冲突.若冲突分组是单播分组，则直接送到网络编码器解决.
在网络编码器解决冲突的阶段，若同一波长信道上有3个或3个以上的分组到达，则随机选择2个冲突的分组送入1个异或单元XOR上，进行全光网络编码操作后发送到目标波长上.
在OMN-MCNC中，编码器的编码操作采用一种基于逻辑运算的全光网络编码器件[4]，有效克服O/E/O转换中代价高、异或网络编码的适用范围窄的缺点.该全光网络编码器件采用无溢出的逻辑左移表示乘法运算，采用逻辑异或取代传统的加法运算，2种运算的结合可在光网络中实现编码操作.具体地说，定义2个编码向量为
|
(1) |
|
(2) |
其中：pn和qm分别为列向量，N为自然数.当二进制数据包a和b经过编码向量pn时，编码为C=(a⊕2n×b)，即将b左移n位之后与a异或编码，然后将编码结果发送到目标波长上.
2 基于最大权重独立集的最小转换度调度算法设计光组播交换调度算法的主要目的有2个：丢包率最小和转换度最小.需要设计合适的调度算法来分配有限范围多波长转换器，因为在使用波长转换器时，总转换度的大小直接影响到成本的高低.
2.1 组播调度算法全光组播调度算法分为3个步骤.
步骤1 首先初始化各到达分组，确定分组的承载波长和目标端口是否冲突，若不冲突，直接传输；若冲突，判断到达分组是否为组播分组.若是组播，进入步骤2；若是单播，进入步骤3.
步骤2 随机选择1个LMWC处理1个冲突组播分组，优化目标是波长转换器的总波长转化度最小.对产生冲突的组播分组，选择相邻的空闲波长作为新的承载波长进行传输.转换每进行1次，波长转换器r的数目就减1，直到r减为0，或可用波长信道为0，或没有冲突的组播分组，该阶段算法结束.还没解决冲突的分组则发送到步骤3.
步骤3 目标是解决步骤2未成功调度的组播分组和单播分组的冲突.编码操作每进行1次，编码器数目h减1.当编码器数目为0，或不存在冲突组播/单播分组时，调度算法结束.
2.2 最小转换度的实现分配LMWC的目标是最小化总转换度，进而最小化节点成本代价.首先，根据到达分组的承载波长和LMWC的转换度(假设d=2)，建立转换图，如图 2所示.在图 2中，设到达分组p1、p2、p3分别由λ1、λ2、λ3承载，则p1的承载波长可转换到λ2、λ3或直接由λ1承载.类似地，可得3个分组完整的转换图.
|
图 2 转换度d=2的转换图 |
根据已建立的转换图，采用改进的最大权重独立集(MWSS，maximal weighted stable set)算法求出最小权重独立集[6]，其中独立集为在1个时隙内可进行转换的分组集，保证独立集权重最小就能保证总转换度最小.具体包括4个步骤.
步骤1 根据完整的转换图建立冲突图.
将转换图中的边作为冲突图的顶点，即冲突图的顶点表示所有分组的所有可行转换.如p3(λ3，λ2)，p3(λ3，λ3)和p3(λ3，λ4)分别代表p3(λ3)的1种可行转换.冲突图中2个顶点之间存在1条边有2种情况：1)2个顶点转换前的波长相等，用于限定该转换为一对一的转换；2)2个顶点转换后的波长相等，用来避免冲突再次发生(2个不同的波长转换到同一个波长信道上).如图 3所示为已建的波长转换冲突图.
|
图 3 波长转换冲突图 |
步骤2 为冲突图中的每个顶点赋1个权重值为
|
(3) |
其中：k为第k个分组，ik为转换前的承载波长，h为转换后的承载波长，每个顶点附上的权重值为w(k，h)，用于表示每个可行转换的转换度.如p3(λ3，λ2)的权重值为1.
步骤3 根据图 3的匹配算法得出冲突图中所有独立集.如p2(λ2，λ4)，p1(λ1，λ3)，p3(λ3，λ2)就是其中1个独立集.
步骤4 求得每个独立集中所有元素的权重和值进行升序排列.将独立集中元素最多、权重和值最小的独立集作为所求最小转换度的集合.
3 仿真结果及分析为验证OMN-MCNC节点结构的性能，基于VC++6.0开发平台，与刘焕淋等[1]提出的节点结构TLWC进行比较，仿真条件假设如下：1) 每个时隙分组到达每个波长信道的概率独立且相等，均为λ；2) 同时考虑单组播业务，组播概率PM设为0.5，且平均组播数E(X)=4；3) 为保证正常的通信质量，将LMWC的反馈次数设为2；4) 有效负载ρe的计算为
|
(4) |
首先讨论波长转换范围d对节点性能的影响.只考虑波长转换解决冲突的情况下，ρe=0.6，d分别取2，4，6.如图 4所示为在不同转换度的情况下，LMWC的数目与丢包率的关系.由图 4可知，随着波长转换度的增大，丢包率呈下降趋势.这是由于随着波长转换度的增大，波长转换策略解决的冲突分组数增多，被丢弃的分组数就会减少，最小丢包率分别为0.03，0.01和0.007.另外，丢包率的增量是递减的，证明增大波长转换度只能在一定范围内降低丢包率.折中考虑，在后面的仿真中，d取4.
|
图 4 LMWC的数目与丢包率的关系 |
如图 5所示，考虑波长转换器和编码器的配置对丢包率的影响，在配置方案1~3中，(r，h)的取值分别为(5，9)，(15，7)，(20，6)，d=4.其中，r为LRWC的数目，h为网络编码或全范围波长转换器的数目.
|
图 5 负载与丢包率的关系(d=4) |
图 5表示在配置不同器件数目的情况下，负载与丢包率的关系.由图 5可知，随着负载的增大，丢包率都呈上升趋势.这是由于随着负载的增大，波长转换器、网络编码器及波长资源逐渐减少，很多处于竞争状态的分组得不到解决，导致丢包率持续上升.但采用方案1的分组配置的丢包率性能始终优于其他2种配置，且随着负载越增大，优势越凸显.这是因为方案1中网络编码器的个数多于其他2种配置，而随着负载的增大，波长资源逐渐减少，节点主要依靠网络编码器解决竞争，而网络编码超大的吞吐量恰恰有效降低了丢包率.
如图 6所示为2种结构下，随着负载的增加，丢包率的变化情况.参数配置如下：r=15，h=7，d=2，4.
|
图 6 负载与丢包率的关系 |
图 6表示在不同负载下的2种节点结构丢包率性能的对比.结果显示，随着负载不断增大，2种结构的丢包率都呈上升趋势.这是由于随着负载的不断增大，空闲的波长信道越来越少，而可进行编码的目标数固定为2，所以丢包率会不断上升.但OMN-MCNC节点结构有明显的优越性.该现象证明，在光组播节点发生分组冲突时，2种分组冲突解决机制的结合使用，大大提高了解决光分组冲突的效率.同时，随着负载的增加，2个结构之间性能的差距增大，这是因为全光网络编码器将产生冲突的分组进行快速编码，丢包率性能得以提升.此外，相比于TLWC，OMN-MCNC成本代价大大降低，这是因为1个全波长转换器的代价远远高于1个网络编码器的代价[7].
4 结束语当分组在光组播交换节点处发生冲突时，为降低多波长转换的代价，提高有限数目多波长转换器解决分组冲突的效率，减小丢包率，提出波长转换和网络编码2种机制的结合使用设计的光组播节点结构.同时，为最小化波长转换度进而减小节点成本，使用改进的MWSS算法实现波长分配调度.仿真结果表明，相比于现有的多播交换光节点结构，OMN-MCNC结构在保证低代价、低时延的同时提升了交换节点的性能.
| [1] |
刘焕淋, 陈高翔, 石嵩磊, 等. 共享有限范围多波长和全单波长转换器的光组播冲突解决方案[J]. 光电子·激光, 2012, 23(12): 2304–2309.
Liu Huanlin, Chen Gaoxiang, Shi Songlei, et al. A scheme of shared LMWC and FRWC for optical multicast contention resolution[J].Journal of Optoelectronics·Laser, 2012, 23(12): 2304–2309. |
| [2] | Manley E D, Deogun J S, Xu Lisong, et al. All-optical network coding[J].Optical Communications and Networking, IEEE/OSA Journal of, 2010, 2(4): 175–191. doi: 10.1364/JOCN.2.000175 |
| [3] |
刘焕淋, 秦亮, 谢芸徽. 多速率分层光组播的波长带宽优化分配[J]. 北京邮电大学学报, 2013, 36(2): 60–63.
Liu Huanlin, Qin Liang, Xie Yunhui. Optimization of wavelength bandwidth allocation in multi-rate layered multicast[J].Journal of Beijing University of Posts and Telecommunications, 2013, 36(2): 60–63. |
| [4] | Qu Zhijian, Ji Yuefeng, Bai Lin, et al. Key module for a novel all-optical network coding scheme[J].Chinese Optics Letters, 2010, 8(8): 753–756. doi: 10.3788/COL |
| [5] |
曹张华, 吉晓东, 刘敏. 变信息率线性网络编码的构造[J]. 重庆邮电大学学报, 2014, 26(1): 62–67.
Cao Zhanghua, Ji Xiaodong, Liu Min. Construction of variable rate linear network coding[J].Journal of Chongqing University of Posts and Telecommunications, 2014, 26(1): 62–67. doi: 10.3979/j.issn.1673-825X.2014.01.011 |
| [6] | Wang Wei, Li Yu, Zhu Guangxi, et al. Coding-driven scheduling for frame-based multicast switches[C]//2011 International Symposium on Network Coding (NetCod). Beijing: [s.n.], 2011: 1-4. |
| [7] |
曲志坚, 纪越峰. 基于网络编码的波长冲突解决方法[J]. 中国科技论文在线, 2011, 6(1): 15–19.
Qu Zhijian, Ji Yuefeng. Wavelengths conflict resolution based on network coding[J].Journal of China Science and Technology Papers Online, 2011, 6(1): 15–19. |