卫星融合交换系统负载均衡异构路径算法

李静玲，黎军，张怡，崔涛，梁薇

中国空间技术研究院西安分院 空间微波技术重点实验室，西安 710100

空间信息网络中的微波激光混合通信技术集成了微波通信的高灵活性和激光传输的大带宽、低损耗、高电磁兼容性的优势[1]。未来的空间信息网络必然是微波、激光等多种异构信息混合组网的形式，因此如何解决异构信息在卫星网络节点上的混合交换成为未来空间异构信息组网的关键问题之一[2-3]。

地面网络的迅速发展促使路由与交换技术不断突破，其中光网络由最初的SDH、MSTP、WDM、PTN/OTN逐渐演化到POTN，光、分组业务的路由与交换技术也由各自封闭独立逐渐发展到相互融合[4]。其中，POTN网络[5-6]集成了WDM/ROADM光层、SDH/OTN层和分组传送层等的优良特性，在OTN层实现分组和电路业务的接入、汇聚和疏导，在光层实现损伤感知以及带宽可变光波长级交换，但光骨干业务采用全光交换方式，将光、分组业务转换为电业务进行分组交换，光、分组业务的交换属于不同分层，并没有在统一的交换系统中进行。在管理与控制面，地面通用多协议标签交换(GMPLS)[7-8]对光、分组业务进行一体化标记，促进了光层与IP层的有机联系，使得以光物理层为代表的传输网与以IP分组为代表的业务网进一步融合。

由地面光、电网络的演化进展可以看到，光电进行深度融合是其技术发展的必然趋势，光电交换也在进一步融合。

随着与地面网络的进一步融合，空间信息网络包括大量异构信息的聚合、分发、管理和控制，异构信息交换可能发生在物理层、链路层或网络层，仅靠现有的光交换或分组交换等独立交换方式或其简单组合形式，都无法适应空间信息的交换需求。文献[9]提出由于星上资源的有限性，可借鉴光突发交换思想，在边缘节点将控制信息采用分组格式封装，提前发送进行资源预留，核心节点根据控制信息对突发包光域交换。但该方法还是一种光交换方式，没有解决空间网络多颗粒度统一交换问题。文献[10]提出一种分布式交换模型，分别构建不同的光、分组交换矩阵模型，再通过交换矩阵模型的组合来完成多颗粒度业务的交换。文献[11]提出一种光电融合交换信令模型，可对光电路径进行一体化预约。文献[1]提出空间光、射频、分组融合交换的概念，指出其异构及多颗粒度等交换特点，并提出融合交换内部多路径智能选择问题。

由上述内容可知，卫星光电融合交换系统中，可能包含光数据流、分组数据流之间的数据交换，大颗粒度到小颗粒度数据流之间的数据交换，甚至单一数据流到多种数据流之间的数据交换。不同颗粒度业务可能通过不同的光、分组内部路径组合的交换路径进行聚合或分发交换，选择不同的内部交换路径对整体交换性能影响巨大，需要对其进行择优选择。若选择不合理的交换路径，可能造成交换网络中部分路径负载过于饱和，形成瓶颈链路，甚至导致路径拥塞，而同时交换系统中的其他可用路径处于空闲状态，路径资源没有得到合理利用，使交换系统路径负载不均衡、资源利用率不高。

文献[12-13]基于经典的路由和波长分配(RWA)算法，提出根据各路径上可用波长数来计算路径的权值函数。文献[14]提出针对LEO卫星网络的并行链路不相交多径路由算法SPEMR，该算法具有相对更强的实时传输海量数据的能力，主要聚焦于路径的承载能力和传输时延等性能。文献[15-16]提出以网络链路剩余波长数量的方差为标准选择路由，但该方法无法准确衡量分组路径资源。文献[17]根据链路时延因素和链路负载因素进行负载代价计算，但对于星上融合交换系统，其路径跳数是确定的，链路时延因素并不是关键因素，而星上光、电链路负载本身差异巨大，无法单纯通过负载进行路径计算。文献[18]针对空间信息网络特点，提出基于负载均衡思想的虚拟网划分方法，可以有效提高资源利用率。文献[19]在所提出的光电混合数据中心网络架构下，提出基于流量预测矩阵的负载均衡流量调度机制，但并没有充分考虑光电异构特性。

目前，针对卫星网络提出了大量负载均衡机制[18]及星间路由算法[20-21]，但并没有提出针对空间光电融合交换系统的负载均衡路径计算方法。本文提出异构光电交换路径算法，根据异构路径带宽的不同定义最小粒度路径带宽；根据异构路径与最小粒度路径带宽的关系来计算路径可用负载，并针对异构路径分发和聚合所导致的路径个数差异；提出路径个数参数来衡量异构路径资源权值，而不是路径跳数；通过选择具有最大路径资源权值的交换路径，获得满足负载均衡准则的最优交换路径。

1 空间光电融合交换结构

空间信息网络主要包括光、分组两类异构信息，通过单颗卫星节点或多颗紧耦合卫星节点，完成光、分组等多粒度业务的聚合及分发交换功能。如图1所示，空间光电融合交换系统的交换结构[10]主要包括3个层级，即前级交换单元、中间级交换单元及后级交换单元，每个交换单元由不同光、分组交换矩阵模块组合而成。交换系统中与外部输出/输入端口相连的光、分组端口称为外部端口，内部交换矩阵模块之间的互联端口称为交换系统的内部端口。光业务到分组交换矩阵模块需要经过分发模块，将一路光业务转换为多路分组业务，而分组业务到光交换矩阵模块需要经过聚合模块，将多路分组业务转换为一路光业务。

其中，分发和聚合模块的作用是采用光电/电光转换模块对输入业务进行转换。由于光业务带宽远大于电业务带宽。因此分发和聚合模块主要针对业务带宽。若由光业务转换为电业务，即由高带宽业务转换为多路低带宽业务，可视为数据的分发；若由电业务转换为光业务，即由多路低带宽业务转换为高带宽业务，可视为数据的聚合。通过上述准则来完成数据的分发和聚合功能。

2 异构交换系统负载均衡路径算法

2.1 异构交换系统拓扑描述

在空间光电融合交换系统中，由某外部输入端口经过交换系统中若干光、分组交换矩阵模块，到外部输出端口，所经过的路径组合称为该交换系统中的交换路径；系统中光、分组交换矩阵模块的某输入端口到该矩阵模块输出端口称为交换系统中的子路径；系统中光、分组交换矩阵模块的某输出端口经过聚合/分发模块到另一交换矩阵模块的输入端口称为子路径转换。将该交换系统中的端口视为点，子路径视为边，其交换系统拓扑可表示为N=(V,E,T,X,Y)，其中V为网络中所有端口(点)集合；E为网络中所有子路径(边)集合；T是E上的资源(权值)函数；X为输入端口(源点)集合；Y为输出端口(汇点)集合。

在该交换系统中，业务从外部输入端口，经过不同的光、分组交换子路径组合，最终交换到外部输出端口。其中业务经过的路径跳数(即交换次数)相同，而由于光、分组承载的数据量不同，不同交换路径(包含不同子路径组合)对应的子路径个数可能不同。

为了便于算法描述，定义以下相关符号：

T(l,w)：该参数表示空间交换系统路径资源状态信息表，标注当前所有子路径的可用路径资源，其中l代表交换系统中的子路径，w表示该子路径的可用路径资源。

R(x,y)：该参数表示由外部输入端口x到外部输出端口y的交换信令请求。

P(x,y)：该参数表示由外部输入端口x到外部输出端口y的交换路径集合。

L(x,y)：该参数表示由外部输入端口x到外部输出端口y的交换路径所包含的子路径个数。

H(x,y)：该参数表示由外部输入端口x到外部输出端口y的交换路径所包含的路径跳数，由交换结构所确定，图1所示空间异构融合交换结构中的路径跳数H(x,y)=3。

C(x,y)：该参数表示由外部输入端口x到外部输出端口y的交换路径所包含的路径转换次数。业务在异构交换系统中，每经过一次分发或聚合处理，其业务类型即发生变化(由光业务转换为分组业务或者由分组业务转换为光业务)，该过程称为业务经过一次路径转换。

2.2 异构路径资源的统一衡量方法

在空间异构融合交换系统中，光、分组异构业务的交换资源差异巨大，光业务交换主要包括光波长、光开关、光时隙等资源形式，分组业务交换主要包括报文可用路由表项/转发表项、可用缓存容量、分组时隙等资源形式。光、分组交换资源的异构特性从本质上是由于光业务的物理特性导致其无法缓存，必须提前配置交换路径；而分组业务可以通过缓存进行存储转发。由于光、分组业务都是承载在路径中的，虽然无法对交换资源进行直接衡量，但可以考虑间接通过路径承载业务的能力来对异构资源进行定量衡量。因此本文提出构建最小粒度路径带宽因子作为异构路径负载能力的衡量标准，将交换子路径与该因子的关联倍数作为衡量该子路径资源的有效权值，构建异构路径影响因子υα。

该影响因子的计算方法如下：

首先根据系统中光路径和分组路径各自的最大路径带宽，计算两类路径带宽值的最大公约数，定义为最小粒度路径带宽α。α表征空间异构交换系统中光、分组交换带宽的最小衡量单位。计算光、分组路径所包含的最小粒度路径带宽α的个数，分别将光、分组路径所包含的α个数与光路径和分组路径所包含α个数的总和相除，得到光、分组异构路径带宽比值。

2.3 负载均衡路径算法约束设计

在详细介绍算法之前，首先明确以下几条约束。

1)由于空间异构交换系统包含的矩阵级数(前级、中级和后级)是确定的，因而业务在不同交换路径中所经过的路径跳数(即交换次数)是相同的；

2)由于光、分组路径承载业务的能力不同，导致不同交换路径所包含的子路径个数可能不同，在相同业务负载下子路径越多，交换系统的控制及调度功能就越复杂，因此本方法在同等业务负载下倾向于采用较少的子路径个数；

3)由于路径转换会增加系统复杂度，在进行业务交换时，本论文以路径转换次数较小的交换路径为优选路径。

在空间异构交换系统中，与通常路径算法不同的是，对于确定输入/输出端口的不同交换路径而言，其路径跳数是相同的，并不存在最短路径，但由于其异构特性，导致交换路径中的子路径个数和路径转换次数可能不同，因此将子路径个数和路径转换次数作为路径权值的衡量因子。

2.4 负载均衡路径算法思想

当空间异构交换系统接收到包含外部输入/输出端口信息的信令消息时，需计算该业务的交换路径，并预留相应的光、分组异构交换资源。为了避免空间异构交换系统中不同子路径上业务负载差异较大，从而形成瓶颈路径，导致交换系统资源利用率降低，需要采取一定的均衡机制调节业务流量分布。本文通过异构路径影响因子将异构特性对于路径负载均衡的影响转换为与异构路径可用带宽资源相关的具体数值，利于进行定量衡量；根据光、分组路径承载业务的颗粒度差异，将交换路径所包含的子路径个数作为衡量路径的关键参数之一，构建空间异构交换系统中异构路径权值函数，如下式所示：

式(1)用于计算由外部输入端口x到外部输出端口y的交换路径权值Cp(x,y)。其中Lwl为任意子路径的可用资源值；ωl为同构子路径影响因子；υαk为异构路径影响因子。路径生成流程如图2所示，具体算法步骤说明如下：

图2 卫星异构交换路径生成流程

步骤1：首先初始化空间异构交换系统，获取各交换矩阵模块中每条子路径的资源使用情况，建立资源状态信息表T(l,w)，当申请新的交换路径或释放已存在的交换路径时都要对其相关子路径的资源状态信息进行更新。

步骤2：当路径信令请求R(x,y)到达时，根据业务外部输入端口x与输出端口y，计算出交换系统中所有交换路径的集合P(x,y)。

步骤3：计算集合P(x,y)中的每一条交换路径的子路径个数L(x,y)、路径跳数H(x,y)以及路径转换次数C(x,y)。

步骤4：计算同构路径影响因子ω和异构路径影响因子υα，其中影响因子υα的计算方法见2.2节，影响因子ω的计算方法如下：

1)通过资源状态信息表T(l,w)查询每条子路径的可用路径资源Lw；

2)计算该交换路径中的同构路径中每条子路径的可用资源Lw占同构子路径可用资源总数的百分比，并将各资源比值按从小到大的顺序排列；

步骤5：通过式(1)异构路径权值函数计算交换路径集P(x,y)中每一条交换路径的路径权值Cp。

步骤6：将路径权值Cp按照由大到小的顺序排列，选取最大Cp值所对应的交换路径。

步骤7：若所选交换路径中存在子路径可用资源值Lwl小于业务申请资源最小值Lwmin，转到步骤9，否则转到步骤8。

步骤8：将所选交换路径作为交换路径，根据信令申请消息预留相应光、分组交换资源，并更新T(l,w)中子路径资源状态信息。

步骤9：从交换路径集P(x,y)中删除所选路径，继续判断P(x,y)是否为空，若不为空，转至步骤7，若为空，则本次信令申请失败。

3 仿真分析与性能评价

在图1所示卫星异构交换模型基础上进行异构路径算法(LBHP)的仿真分析。通过对比采用传统的路由与波长分配(RWA)算法[12-13]，仿真了LBHP算法在随机业务请求下的路径负载平衡度、路径阻塞概率性能，并对算法仿真结果进行分析。

3.1 仿真设置

为了验证所提算法性能，采用Matlab与OMNET仿真工具进行联合仿真，通过OMNET搭建卫星异构交换模型如图3所示。该模型包括2个光业务输入模块(Port0，Port1，每个模块设置2个端口)，2个分组业务输入模块(Port2，Port3，每个模块设置4个端口)；输出模块(Port4，Port5，Port6，Port7)负责接收相应业务；交换矩阵包括前、中、后3级，其中前级包含2个2×2光交换矩阵(SwitchA、SwitchA1)和2个4×4分组交换矩阵(SwitchA2、SwitchA3)；中间级包含1个4×4光交换矩阵(Optical_switch)和一个16×16(Packet_switch)分组交换矩阵；后级与前级的架构相同。

图3 卫星异构交换仿真模型

3.2 评价指标

本文所仿真的卫星异构交换系统总交换容量为15 Gbit/s，端口数为12×12，其中光端口为4×4，分组端口为8×8。光端口速率为2.5 Gbit/s，分组端口速率为625 Mbit/s，光、分组路径带宽比为4:1。采用增加业务模式进行仿真，当业务连接建立后，除非收到拆除信令，否则交换系统中的交换资源一直占用，不会被自动释放。

定义参数路径负载平衡度(LBD)：

定义参数路径阻塞概率(PCP)：

PCP=LB/|L|

(3)

式中：若当前子路径可用资源数w(l)

3.3 仿真分析

图4、图5展示了在随机业务下，传统RWA(路由与波长)算法与本文所提LBHP(异构交换负载均衡路径)算法的路径负载平衡度(LBD)和路径阻塞概率(PCP)指标，分析算法性能及适用范围。

图4 不同业务请求下的网络负载平衡度

图5 不同业务请求下的网络路径阻塞率

如图4(a)所示，在0～120个随机业务请求下，传统RWA算法在进行路径选择时，并没有综合考虑光、分组交换路径的相互影响。将该算法进行了10次仿真，每次计算得到的交换路径及LBD值都不同，而LBHP算法得到的结果都相同，其算法稳定度更优。当业务量为120个时，LBHP算法的LBD值接近0.06，小于传统RWA算法得到的最低LBD值，其性能优于传统算法。如图4(b)所示，将传统RWA算法经过10次仿真得到的路径负载平衡度值进行平均，并与本文LBHP算法比较，可以看到LBHP算法可以有效降低负载平衡度，在网络负载值达到120时，可将LBD值降低约32%，有效增强网络负载平衡能力，提高交换系统路径利用率。

图5(a)比较了LBHP算法和传统RWA算法在0～240个随机业务请求下的阻塞概率。可以看到，传统负载均衡算法无法综合权衡光电融合交换系统的整体路径资源情况，在进行的10次仿真下得到的结果都不同，且在随机业务请求接近50时开始出现路径阻塞；而LBHP算法不仅在不同次计算时的结果都保持一致，且在业务到达率接近200时才开始出现路径拥塞。如图5(b)所示，将传统算法的10次仿真结果进行平均，在相同业务到达率下，LBHP算法的路径阻塞概率均等于或低于传统算法，当随机业务请求达到240个时，LBHP算法的路径阻塞率相对于传统算法降低约51%。

综上可以看到，在算法稳定性及算法性能方面，本文所提LBHP算法均优于传统RWA算法。

4 结束语

卫星光电融合交换系统是未来空间卫星组网中的关键技术之一。由于空间体系架构特点以及对资源高效利用的需求，卫星光电交换系统并不适合采用现有的光电独立交换或仅部分模块融合的方式，而应寻求更进一步的融合机制。

基于卫星异构融合交换结构以及光电一体化信令方案，本文所提出的光电异构资源负载均衡路径算法，不仅可以保证交换路径计算结果的一致性，也可获得基于负载平衡度以及路径阻塞率指标的交换路径的优化计算结果，对于卫星光电异构交换系统的深度融合有着较大的研究及应用意义，可极大提升卫星光电交换系统整体性能。在未来工作中，需要进一步加强本文所提算法的数学模型分析及构建。