空分复用弹性光网络中串扰感知的虚拟网络映射算法

首先设计串扰影响评估方法，动态评估相邻纤芯之间的串扰影响；然后提出空分复用弹性光网络中串扰感知的虚拟网络映射算法。在虚拟节点映射阶段，为了增强虚拟节点与虚拟链路的关联性，采用虚拟节点邻近排序方法。物理节点优先级评估方法考虑节点相邻链路的芯间串扰，达到均衡芯间串扰效果。在虚拟链路映射阶段，设计频谱区域分配方法以减小芯间串扰。仿真结果表明，当负载为100~900 Erlang时，所提算法的平均提升虚拟光网络请求接受率比LCLC-VNM算法提高了6.45%，串扰改善了32.1%，但时间复杂度略高于LCLC-VNM算法。

Abstract

Objective

In recent years, the rapid increase in network traffic requires more network transmission capacity. Therefore, an elastic optical network based on orthogonal frequency division multiplexing technology is proposed. Its characteristic is to allocate spectrum resources according to the connection requests. By improving the utilization efficiency of spectrum resources in the frequency domain, the network transmission capacity can be expanded. However, restricted by the Shannon limit, the traditional single-core single-mode fiber is difficult to further expand the transmission capacity in the network. Therefore, on the basis of the proposed multi-core optical fiber (MCF), space division multiplexing elastic optical networks (SDM-EONs) are considered as one of the most potential solutions to break through the network capacity bottleneck. At the same time, the applications in the network have diversified demand characteristics, but it is difficult for physical facility providers to flexibly configure the network according to the specific needs of the applications. In recent years, the increasingly developed network virtualization technology has solved the problem of network rigidity and formed a diversified network structure. The combination of network virtualization technology and SDM-EONs can improve the utilization rate of the underlying physical resources, but it will make the virtual network mapping more complex. Furthermore, virtual network mapping inevitably needs to meet more constraints. There are also physical layer constraints of inter-core crosstalk (XT) in SDM-EONs. When the overlapping spectral segments of adjacent cores are occupied by different optical paths at the same time, the transmission quality of optical paths will be degraded, and high-quality transmission of normal signals cannot be realized. Therefore, this paper focuses on SDM-EONs based on MCF to solve the virtual network mapping problem of crosstalk perception.

Methods

In this paper, the crosstalk impact of the occupied spectrum resources on the adjacent core spectrum is considered, and a crosstalk impact assessment method is designed. Then a virtual network mapping algorithm for crosstalk awareness (CA-VNM) in SDM-EONs is proposed. The virtual network mapping method adopted by the algorithm is two-stage mapping. The first stage is virtual node mapping. In order to enhance the correlation between virtual nodes and virtual links, virtual nodes adopt the virtual node proximity ranking method, and physical nodes adopt the node degree classification method, so as to improve the virtual network acceptance rate and provide the underlying physical resources for the subsequent virtual services with greater demand. The priority evaluation method of physical nodes considers the XT on the adjacent links of nodes to improve the utilization rate of the underlying physical resources and balance the XT. The second stage is virtual link mapping, and the virtual link bandwidth is prioritized. Based on the prioritization, the K-shortest path method is used to find the K optical paths with the least hops, and the physical link priority method is used to rank the candidate physical links. Then the core load balancing and spectrum partition allocation methods are designed to balance the traffic of each core and reduce the XT.

Results and Discussions

The algorithm proposed in this paper optimizes the network performance. The request acceptance rate of CA-CVM achieves the best effect in the comparison algorithms, and the highest request acceptance rate of the virtual network is increased by 11% (Fig. 6). CA-CVM obtains the best spectrum utilization performance in the NSFNET network, and the spectrum utilization is increased by 17.1% (Fig. 7). The XT improvement rate gradually decreases with the increase in the load because the idle resources in the network gradually decrease, and other methods cannot reduce the XT. The XT improvement rate of CA-CVM is the best. At 100, 200, 300, 400, 500, 600, 700, 800, and 900 Erlang, the XT improvement rates are 67.7%, 54.6%, 46.3%, 39.3%, 32.8%, 20.5%, 11.8%, 9.1%, and 7.0%, respectively (Fig. 8).

Conclusions

In this paper, a virtual network mapping algorithm for crosstalk awareness in SDM-EONs is proposed, and the constraints of virtual network mapping in SDM-EONs are considered. When the priority of virtual nodes is evaluated, the proximity between virtual nodes is considered, and a virtual node proximity ranking method is proposed. When candidate physical nodes are selected, the physical node degree is considered so that more underlying physical resources can be provided to the virtual request service with greater demand. A crosstalk impact assessment method is proposed to evaluate the weight of physical nodes and balance the crosstalk between cores. In addition, the core is selected according to the bandwidth required by the virtual link to balance the core load. Finally, the spectrum is divided into several regions, and the first hit and the last hit are used alternately when the spectrum is allocated to reduce the influence of XT. The simulation results show that when the network load is small, the acceptance rate of the virtual network is optimized by 11%, the spectrum utilization rate is increased by 17.1%, and the XT improvement rate can reach 67.7%. In view of this, the proposed algorithm can effectively improve the acceptance rate of the virtual network and the XT in the SDM-EONs and optimize the mapping performance of the virtual network.

1　引言

近年来高清视频、云计算以及5G通信系统等新兴业务的蓬勃发展，网络流量急剧增加，这必然对网络传输容量有更高的要求。为此，研究人员提出基于正交频分复用技术的弹性光网络（EONs）。与传统的波分复用光网络相比，EONs根据连接请求的需求为其分配频谱资源，通过在频域提升频谱资源的利用效率，实现了网络传输容量的扩展^［1-2］。然而，受到非线性香农容量极限的限制，传统单芯单模光纤难以进一步拓展网络的传输容量^［3］，基于多芯光纤（MCF）的空分复用弹性光网络（SDM-EONs）被提出。SDM-EONs被视为突破网络容量瓶颈问题的最具潜力的解决方案之一^［4］。同时，网络应用具有多样化需求特征，但针对应用的特定需求，物理设施提供商很难灵活地配置网络。近年来网络虚拟化技术的快速发展，便于网络管理者抽象物理网络资源和灵活地部署网络应用，重点解决网络僵化问题，形成多元化的网络结构^［5］。网络虚拟化技术与SDM-EONs相结合，可以提高底层物理资源利用率，但是会使虚拟网络映射问题更加复杂^［6］。在SDM-EONs中，光信号在纤芯中传输时会有小部分信号功率泄漏至纤芯包层，影响相邻纤芯中占用相同频谱位置的信号，形成芯间串扰（XT），芯间串扰随着传输距离的增加而加剧，对信号的传输质量产生劣化影响，严重时会导致光路因不满足光纤传输质量的要求而无法正常传输。因此，基于SDM-EONs的虚拟网络映射需要满足的约束条件比底层网络是EONs的映射多一个串扰约束条件^［7］，而针对SDM-EONs中的芯间串扰，研究串扰感知的虚拟光网络映射问题具有重要的意义。

Xuan等^［8］提出基于多芯纤芯SDM-EONs的虚拟网络映射算法，并通过改进全局优化算法来解决多芯光纤弹性光网络中的虚拟网络映射问题。然而芯间串扰是基于MCF的SDM-EONs中主要的物理层损伤来源，该算法没有考虑芯间串扰，未解决SDM-EONs中的关键问题。Chen等^［9］引入了链路重要度和节点重要度的概念，定义了虚拟光网络（VON）映射优化的计算公式。为了降低频谱碎片化程度，他们引入了分段的概念，在虚拟链路映射之前，将虚拟链路的带宽需求划分为几个线速率，并在此基础上建立了3种启发式VON映射方法和2个整数线性规划（ILP）模型，然而该算法只考虑了串扰约束，未能减小SDM-EONs所产生的芯间串扰。刘焕淋等^［10］在设计物理节点优先级公式时，考虑了物理节点的相邻链路上频谱资源的精确匹配度属性和候选物理节点到已被映射物理节点的跳数距离，从而降低了频谱资源浪费并且提高了虚拟网络映射成功率，但他们未重点考虑芯间串扰问题，只是采用纤芯优先级排序方法。Chen等^［11］提出一种将最大资源需求的虚拟节点优先映射到资源最多的光节点的最短光路映射算法（LCLC），然而其底层光网络是弹性光网络。Liu等^［12］提出频谱状态评估方法来评估当前网络中的芯间串扰，在频谱分配过程中，选择串扰较弱的频谱块进行分配，有利于后续业务请求持续分配。Zhang等^［13］提出全网串扰辅助图来评估链路所受串扰的影响，实现了对全网串扰影响的动态评估，确保了全网串扰影响均衡。刘仕鑫^［14］提出了频谱状态评估方法并对频谱进行区域划分，有效地减小了芯间串扰的影响。文献［12-14］提出的芯间串扰评估方法都没有体现出多芯光纤中最中间的纤芯对周围纤芯串扰的影响最大。在现有的相关工作中，研究者已经提出一些SDM-EONs与虚拟网络结合的算法^［8-10］，但是未见对虚拟光网络映射中的串扰问题以及芯间串扰评估的报道。

本文聚焦基于MCF的SDM-EONs解决串扰感知的虚拟网络映射问题。当芯间串扰超过串扰阈值时，不满足SDM-EONs中的串扰约束条件，导致虚拟网络映射失败。因此，本文提出一种基于SDM-EONs 的串扰感知虚拟光网络映射算法，通过减小芯间串扰提高虚拟光网络的请求接受率、频谱利用率和串扰改善率。

2　SDM-EONs下的虚拟网络映射模型

2.1　网络模型

底层SDM-EONs被抽象为无向图 $G_{s} = (N_{s}, L_{s}, C_{s})$ ，其中： $N_{s}$ 为物理节点集合，每个物理节点 $n_{s}$ 都包含可用的计算资源 $C_{n}^{(s)}$ ； $L_{s}$ 为该网络的物理链路集合，每条物理链路 $l_{s}$ 的可用带宽用 $B_{l}^{(s)}$ 表示； $C_{s}$ 为每条光纤链路上的纤芯集合，每个纤芯的频谱被划分为多个频谱隙（FS）。每个虚拟光网络请求表示为 $G_{v} = (N_{v}, L_{v})$ ，其中： $N_{v}$ 为虚拟节点集合，每个虚拟节点 $n_{v}$ 的计算资源需求为 $C_{n}^{(v)}$ ； $L_{v}$ 为虚拟链路集合，每条虚拟链路 $l_{v}$ 的带宽需求为 $B_{l}^{(v)}$ 。

2.2　约束条件

通常，虚拟网络映射问题需要遵循对应的约束条件。在虚拟节点映射过程中，除了物理节点的计算资源需要满足虚拟节点的计算资源外，还需要满足的约束条件分别为

C_{M} [n_{v}^{(1)}] \neq C_{M} [n_{v}^{(2)}], \forall n_{v}^{(1)}, n_{v}^{(2)} \in N_{v}, n_{v}^{(1)} \neq n_{v}^{(2)}

，（1）

D_{s} (n_{s}) \geq D_{v} (n_{v}), n_{s} \in N_{s}, n_{v} \in N_{v}

，（2）

式中： $C_{M} [n_{v}^{(a)}]$ （a=1,2）为虚拟节点所映射的物理节点； $D_{s} (n_{s})$ 为物理节点的节点度。式（1）确保一个虚拟网络的虚拟节点不能映射多个物理节点，式（2）确保所映射物理节点的节点度大于或等于虚拟节点的节点度^［15］。

在虚拟链路映射过程中，物理链路的可用带宽需要满足虚拟链路带宽需求；在频谱分配过程中，需要满足频谱一致性、连续性、不重叠的约束条件。此外，网络节点不进行纤芯转换，即在属于其路径的所有MCF链路中，将同一个纤芯分配给一条光路，这就是所谓的空间连续性约束。

y_{r_{k}}^{(i)} = y_{r_{k}}^{(i^{'})}, \forall r_{k} \in R

，（3）

式中： $y_{r_{k}}^{(i)}$ 、 $y_{r_{k}}^{(i^{'})}$ 为业务 $r_{k}$ 所占用的路径上两条不同链路所占用的纤芯号； $R$ 为业务请求集合。式（3）确保了不同链路的业务所占用的纤芯号不变^［16］。

除此之外， $X_{T}$ 作为SDM-EONs的关键物理约束，在沟槽辅助型七芯光纤（图1）中，文献［17］提出多芯光纤纤芯的平均串扰模型为

X_{T} = \frac{n - n e x p [- (n + 1) 2 h L]}{1 + n e x p [- (n + 1) 2 h L]}

，（4）

h = \frac{2 k^{2} r}{β ω}

，（5）

式中： $X_{T}$ 为业务选择传输纤芯时产生的平均串扰值； $n$ 为某根纤芯的相邻纤芯数量； $L$ 为光纤的传输长度； $h$ 为单位传输长度的 $X_{T}$ 增量； $k 、 r 、 β 、 ω$ 为光纤参数，分别表示光纤的耦合系数、弯曲半径、传播常数以及沟槽宽度。

图 1. 沟槽辅助型七芯光纤

Fig. 1. Trench-assigned seven-core optical fiber

下载图片查看所有图片

为了确保所有分配到一个链路的串扰值小于其串扰阈值（ $X_{T, t h r e s h o l d}$ ），需要确保分配给链路的受影响最大的频谱隙串扰小于阈值^［18］，即

X_{T, m a x} < X_{T, t h r e s h o l d}

，（6）

式中： $X_{T, m a x}$ 为受影响最大的频谱隙串扰。

3　串扰影响评估方法

芯间串扰是SDM-EONs传输质量的最重要影响因素之一。芯间串扰是信号在纤芯间传输时一部分功率泄漏所产生的，且其在包层中传播时，泄漏的功率大小会随纤芯距离呈指数式下降。因此，本文仅考虑多芯光纤中的相邻纤芯占用相同频隙进行资源传输时会产生芯间串扰，而不相邻纤芯间的串扰忽略不计。由多芯光纤的纤芯构造可知，中心纤芯所产生的芯间串扰更大^［14］，为此对芯间串扰影响的评估需要增加中心纤芯所产生串扰影响的权重值。本文将多芯光纤中的光纤分为两类，第一类为中间光纤周围的纤芯 $\geq 3$ 的中心纤芯，第二类为中间光纤周围的纤芯 $< 3$ 的普通纤芯。

本文采用七芯光纤SDM-EONs^［19］。由图1可知，标号为1~6的每根光纤都有3根相邻光纤，而MCF的7号光纤由于与其余6根光纤都相邻，因此7号光纤为七芯光纤的中心光纤。此时的芯间串扰影响动态评估公式为

C_{A} [f_{j}^{(i l)}] = \{\begin{array}{l} 3 \sum_{m \in n} f_{j}^{(m l)} + 6 f_{j}^{(7 l)}, i < 7 \\ 3 \sum_{m \in n} f_{j}^{(m l)}, i = 7 \end{array}

，（7）

式中： $f_{j}^{(m l)}$ 为光纤链路 $l$ 上与光纤标号为 $i$ 相邻的标号为 $m$ 的光纤中第 $j$ 个频隙的频谱占用状态， $f_{j}^{(m l)} = 1$ 表示第 $j$ 个频隙资源被占用，否则表示第 $j$ 个频隙资源未被占用； $C_{A} [f_{j}^{(i l)}]$ 为物理链路 $l$ 上的标号为 $i$ 的光纤与相邻光纤 $m$ 在相同索引的频谱隙的重叠状态； $n$ 为相邻的标号不为7的光纤总数。可以利用式（7）推算该频隙相应的芯间串扰的数值， $C_{A}$ 的数值越大，当前状态下的芯间串扰越强。

4　SDM-EONs中串扰感知的虚拟网络映射算法

虚拟网络映射算法分为虚拟节点优先映射算法与虚拟节点和链路同时映射算法，但是虚拟节点和链路同时映射算法的时间复杂度非常高，所以本文采用虚拟节点优先映射算法，该算法先映射所有虚拟节点，然后映射虚拟链路。虚拟节点映射：当一个虚拟网络请求到达时，对虚拟节点和物理节点的优先级进行排序，实现一一对应映射。首先，利用虚拟节点邻近排序方法对虚拟节点的优先级进行排序，根据此排序方法寻找候选物理节点；然后，在选择候选物理节点的过程中，利用物理节点度分类方法把物理节点分为两类，并且根据所提出的物理节点优先级评估方法进行物理节点排序。虚拟链路映射：对虚拟链路和物理链路的优先级进行排序并且进行纤芯选择和频谱分配，最后完成虚拟网络映射。本文根据虚拟链路带宽大小进行优先级排序，基于此排序使用K最短路径算法寻找K条最短跳光路并使用所提出的物理链路优先级方法对候选物理链路排序。

4.1　虚拟节点邻近排序方法

在映射虚拟节点时，需要评估所有虚拟节点映射的优先程度，虚拟节点权重大则优先级高，且优先级高的虚拟节点先进行映射。而虚拟节点目前所能考量的属性为节点度、计算资源和节点相邻链路的带宽，故本实验参考文献［20］中虚拟节点权重 $W [n^{(v)}]$ 的评估方法进行计算，即

W [n^{(v)}] = C_{n}^{(v)} \sum_{l^{(v)} \in a [n^{(v)}]} B_{l}^{(v)} D_{v} [n^{(v)}]

，（8）

式中： $a [n^{(v)}]$ 为与 $n^{(v)}$ 相邻的虚拟链路集合。

式（8）将所有虚拟节点按照节点度、计算资源和节点相邻链路的带宽计算排序，未考虑相邻虚拟节点的邻近性会使相邻虚拟节点映射到相距较远的物理节点，从而造成底层物理带宽的资源浪费，并且会导致同一个虚拟网络中的虚拟链路映射到相同物理链路上，不满足链路约束条件，从而造成虚拟链路映射失败，因此需要把虚拟节点之间的邻近性与式（8）相结合。在式（8）计算排序后添加虚拟节点邻近排序方法再次排序，并将排序结果作为最终虚拟节点的优先级结果。首先根据式（8）计算虚拟节点的权重并且降序排列，记为集合 $V$ ，以序列中第一个节点为起始节点加入集合 $V_{1}$ ，从此节点的相邻节点中选取权重最大的节点加入集合 $V_{1}$ ，再以此节点为中心寻找相邻节点，若无相邻节点则回溯至上一个节点并找其相邻节点中权重最大的节点，重复上述过程，直至所有虚拟节点加入集合 $V_{1}$ ，集合 $V_{1}$ 就是最终虚拟节点的优先级序列。在图2中，节点旁的数值表示该虚拟节点所需的计算资源，链路上的数值表示虚拟链路所需的频隙。经式（8）计算可得虚拟节点的权重排序为B、A、D、C，但使用虚拟节点邻近排序方法的结果为B、A、C、D，此时虚拟节点排序完成。

图 2. 虚拟网络模型

Fig. 2. Virtual network model

下载图片查看所有图片

4.2　物理节点度分类方法

在第一步筛选候选物理节点过程中，若要提高虚拟网络映射率，需要满足以下4个条件：待映射物理节点的计算资源大于虚拟节点所需资源、虚拟节点所映射的物理节点度大于或等于虚拟节点度、未被同一虚拟光网络中的其他虚拟节点使用、此物理节点的相连物理链路上连续频谱隙数超过虚拟链路所需的频隙数，可以提高虚拟网络映射率。如图3所示，黄色拓扑图为虚拟网络，蓝色拓扑图为物理网络，物理链路上的数字代表该物理链路上最大连续空闲频谱隙数。物理节点E满足虚拟节点A的计算资源和节点度要求，但是在虚拟节点映射后需要映射虚拟链路时可以发现，物理链路不能提供虚拟链路所需要的频隙数，故无法成功映射虚拟网络。因此，满足以上4个条件可作为第一步筛选的结果。为了避免带宽资源浪费，使节点度大、带宽资源丰富的物理节点服务后续到达所需节点度大和带宽资源多的虚拟节点，因此物理节点度分类方法是在第一步筛选的候选物理节点中寻找与虚拟节点度相同的物理节点作为第一组候选物理节点，而大于虚拟节点度的物理节点作为第二组候选物理节点。如图3所示，由物理节点分类方法可得出A的候选物理节点分组为［D］［］，B的候选物理节点分组为［B，C］［D］，C的候选物理节点分组为［B，C，E］［D］，D的候选物理节点分组为［A，F］［B，C，D，E］。

图 3. 虚拟网络和物理网络模型

Fig. 3. Virtual and physical network models

下载图片查看所有图片

4.3　物理节点优先级评估方法

现有的物理节点优先级评估方法^［10-11］考虑了物理节点的计算资源和物理节点相邻链路带宽资源碎片化程度，但是没有考虑与候选物理节点相连的物理链路上的芯间串扰，在虚拟链路频谱分配时，芯间串扰超过串扰阈值会使虚拟链路映射失败，最终导致虚拟网络映射失败。因此在选择候选物理节点时，应将其相连物理链路上串扰影响评估结果作为重要参考指标，均衡链路上的芯间串扰，以达到削弱全网的芯间串扰效果并且提高虚拟网络映射接受率的目的。定义候选物理节点优先级 $W [n^{(s)}]$ 的方法为

W [n^{(s)}] = \frac{C_{n}^{(s)} \{1 + F [b^{(s)}]\} (1 + μ D_{s})}{\{1 + \sum_{n^{'} \in N_{e} [n^{(v)}]} h [n^{(s)}, n^{'}]\} \{1 + \sum_{l \in E_{s}} \sum_{i = 1}^{7} \sum_{j = 0}^{|F| - 1} C_{A} [f_{j}^{(i l)}]\}}

，（9）

F [b^{(s)}] = \sum_{n^{'} \in N_{e} [n^{(v)}]} \sum_{c \in C_{s}} \frac{B_{F}^{(c)} [n^{(s)}, n^{'}]}{1 + Z_{F}^{(c)} [n^{(s)}, n^{'}]}

，（10）

式中： $h [n^{(s)}, n^{'}]$ 为 $n^{(s)}$ 与已映射 $n^{'}$ 之间的最短光路跳数； $N_{e} [n^{(v)}]$ 为 $n^{(v)}$ 的邻接节点所映射的物理节点集； $D_{s}$ 为物理节点度； $μ$ 为表征物理节点分组状态的参数，当候选物理节点分类后，候选物理节点分为两组，若计算第一组时 $μ$ =0，否则 $μ$ =1； $F [b^{(s)}]$ 为这条链路上频谱碎片化程度，其值越大，代表碎片化程度越低； $B_{F}^{(c)} [n^{(s)}, n^{'}]$ 为 $n^{(s)}$ 到已映射 $n^{'}$ 最短光路上满足频谱一致性约束的可用频隙总数； $Z_{F}^{(c)} [n^{(s)}, n^{'}]$ 为 $n^{(s)}$ 到已映射 $n^{'}$ 最短光路的空闲带宽的总频隙数； $C_{s}$ 为多芯光纤的纤芯数； $E_{s}$ 为候选物理节点的相邻链路。

4.4　物理链路优先级评估方法

当链路带宽资源的评估方式只考虑链路带宽资源大小时，会出现链路带宽资源比较丰富，但是频谱碎片化程度较高、满足虚拟链路带宽需求的可用频谱块数量较少的情况。因此，定义候选工作光路的路径优先级 $W (l_{s})$ 的计算方法为

W (l_{s}) = \frac{C_{m} \sum_{l \in w} \sum_{c \in C_{s}} M_{F}^{(c)} l}{h^{α} (n_{1}, n_{2}) [1 + \sum_{l \in w} \sum_{c \in C_{s}} Z_{F}^{(c)} l]}

，（11）

式中： $C_{m}$ 为满足虚拟链路所需带宽的纤芯数； $w$ 为路径链路数； $M_{F}^{(c)} l$ 为链路 $l$ 上所有满足虚拟链路 $l_{v}$ 所需带宽的空闲频谱块的总频隙数； $Z_{F}^{(c)} l$ 为链路 $l$ 的所有空闲频谱块的总频隙数； $h (n_{1}, n_{2})$ 为 $n_{1}$ 与 $n_{2}$ 之间的最短光路跳数； $α$ 为 $h (n_{1}, n_{2})$ 的权重。

4.5　纤芯均衡负载方法

为了使各个业务带宽在每根纤芯上均匀分布，均衡纤芯负载，提高虚拟网络映射率，提出一种纤芯均衡负载方法。首先，根据以下公式计算得到每根纤芯平均负载的带宽频隙数 $D_{L}$ ，即

D_{L} = \frac{\sum_{i = 1}^{q} F_{i}}{C_{s}}

，（12）

式中： $q$ 为虚拟链路请求带宽分布范围总数； $F_{i}$ 为虚拟链路请求带宽分布范围内的频隙数。然后，根据计算出的平均负载数配置每根纤芯承载的虚拟网络请求频隙数。以虚拟链路请求带宽均匀分布1~10个FS为例，首先计算得到平均负载为7.8，因此将1~3个FS的虚拟链路配置到1号纤芯，4个和5个FS的虚拟链路分配到2号纤芯，6个FS的虚拟链路分配到3号纤芯，7个FS的虚拟链路分配到4号纤芯，8个FS的虚拟链路分配到5号纤芯，9个FS的虚拟链路分配到6号纤芯，10个FS的虚拟链路分配到7号纤芯。此方法保证所有的业务均匀分布到每个纤芯，减小单根纤芯的负载。由于每根纤芯所承载的虚拟带宽根据纤芯均衡负载方法划分整齐，可减少频谱碎片的产生。

4.6　频谱分区分配方法

确定虚拟链路映射的候选光路后，采用图顶点着色理论^［21］将不相邻的纤芯分为一组，如图1所示，纤芯分为三组：第一组（紫色）包括1号纤芯、3号纤芯和5号纤芯；第二组（蓝色）包括2号纤芯、4号纤芯和6号纤芯；第三组（黄色）包括中心纤芯——7号纤芯。本文将纤芯分组、均衡纤芯所承载业务和频谱分区思想相结合，如图4所示，将频谱分为S1、S2、S3、S4四个区域，每个区域分别占物理链路频隙总数的1/4，将S1~S3设为优先承载虚拟业务进行传输的区域集合；为减少相邻纤芯间重叠的频隙数量，减弱芯间串扰对业务传输的影响，最大化频谱资源的利用率，三组纤芯在每个区域的频谱分配方式和优先区域的划分方式都不相同。在分配频谱时，第二个纤芯组和第三个纤芯组采用的频谱分配方式是在为S1、S3区域分配频隙时采用首发命中（FF）算法，S2、S4区域采用最后命中（LF）算法，而第一组纤芯与之相反。如此分配方式使所划分的两个频谱域之间有公共区域（common area）。

图 4. 频谱分区图

Fig. 4. Spectrum partition diagram

下载图片查看所有图片

若虚拟业务在所应分配纤芯的S1~S3区域没有空闲频谱块可供分配，就在S4区域寻找；如果未寻找到满足虚拟业务的空闲频谱块，则依次遍历该纤芯所在的纤芯组中的S4区域和公共区域；如还未有满足需求的空闲频谱块，则遍历其他纤芯组的S4区域和公共区域，直至寻找到满足虚拟链路需求的频谱块并且所分配频隙产生的串扰影响小于串扰阈值，否则映射失败。这样的频谱区域分配方法可以减小芯间串扰，同时提高频谱利用率，最后达到降低带宽阻塞率的效果。

4.7　算法描述

CA-VNM算法的映射过程如下：

1）虚拟节点映射阶段：当一个虚拟网络请求 $G_{v}$ 到达时，先根据式（8）计算虚拟节点的优先级，并将其降序排放在集合 $V$ ；再在此集合中采用虚拟节点邻近排序方法对虚拟节点再次进行排序并存储在集合 $V_{1}$ ，然后为集合 $V_{1}$ 中的每个虚拟节点寻找候选物理节点集合。候选物理节点集合首先根据物理节点度分类方法寻找候选物理节点集合candidate 1、candidate 2，根据式（9）和式（10）计算物理节点集合candidate 1、candidate 2中的物理节点优先级，并降序排列，直至虚拟节点集合 $V_{1}$ 完成候选物理节点筛选，最后实现一一对应映射。

2）虚拟链路映射阶段：对于虚拟网络请求 $G_{v}$ 中的虚拟链路，首先根据其虚拟链路带宽降序排列并存储到 $B_{v}$ ；然后为虚拟链路 $l_{v}$ 计算k条候选映射光路并根据式（11）对候选光路降序排列并保存为 $B_{s}$ ，为了均衡光纤链路上的负载，根据所有虚拟网络请求的链路带宽范围用式（12）计算应分配的虚拟带宽大小；最后根据预定义的频谱分区分配方法分配频谱，计算光路中每一跳业务受到的芯间串扰，判断其是否小于串扰阈值，如若小于阈值，就为其分配物理资源。

CA-VNM算法的目的是在虚拟网络映射过程中动态评估芯间串扰、减小芯间串扰以及提高网络接收率。CA-VNM算法的执行过程如图5所示。

图 5. CA-VNM算法伪代码

Fig. 5. Pseudo code of CA-VNM algorithm

下载图片查看所有图片

CA-VNM的时间复杂度主要来源于3个部分：虚拟节点排序、物理节点排序和路由频谱分配。经过算法分析，虚拟节点排序的复杂度为 $O [{|N^{(v)}|}^{2}]$ ，物理节点排序复杂度为 $O \{|N^{(s)}| |N^{(v)}| + |N^{(s)}| |C^{(s)}| |F| [|L^{(s)}| + |N^{(s)}| l o g |N^{(s)}|]\}$ ，路由频谱分配复杂度为 $O \{K |C^{(s)}| I |F| [|N^{(s)}| l o g |N^{(s)}|]\}$ ，其中， $|N^{(v)}|$ 为虚拟节点数， $|N^{(s)}|$ 为物理节点数， $|F|$ 为链路频隙数， $K$ 为候选路径数， $|C^{(s)}|$ 为纤芯数， $I$ 为频谱分区数。因此CA-VNM算法复杂度为 $O \{{|N^{(v)}|}^{2} + |N^{(s)}| |N^{(v)}| + |N^{(s)}| |C^{(s)}| |F| [|L^{(s)}| + |N^{(s)}| l o g |N^{(s)}|] + K |C^{(s)}| I |F| [|N^{(s)}| l o g |N^{(s)}|]\}$ ，是多项式内可以解决的算法。

5　仿真验证与结果分析

5.1　实验环境配置及评价指标

为了验证SDM-EONs中串扰感知算法的性能，仿真使用Python语言在PyCharm2020.2.3平台上进行仿真。在图6所示的NSFNET网络^［22］进行仿真，其中有14个光节点、21条链路。采用七芯光纤，每根纤芯的可用频隙资源设置为320个频谱隙。该光纤的主要参数设置^［14］如表1所示。

图 6. NSFNET网络拓扑模型

Fig. 6. NSFNET network topology model

下载图片查看所有图片

表 1. 光纤参数

Table 1. Optical fiber parameters

Parameter	Value
$k$	3.16 $\times 10^{- 4}$
$r$ /mm	55
$β$ /m^-1	$4 \times 10^{6}$
$ω$ /μm	45
${X_{T}}_{,}_{t h r e s h o l d}$ /dB	-32

查看所有表

物理网络中每个物理节点包含400个计算资源。虚拟光网络请求到达服从参数为 $μ$ 的泊松分布，虚拟光网络请求持续时间服从参数为 $λ$ 的负指数分布。虚拟节点计算资源需求在［1，5］范围内均匀分布，虚拟链路的带宽请求在［1，10］范围内均匀分布。虚拟光网络请求的虚拟节点数目在［3，4］范围内随机分布，任意虚拟节点之间的连通概率为0.5。

仿真指标为虚拟网络请求接受率（VRR）、频谱利用率（SU）以及芯间串扰改善率（XTIR）。其中，虚拟网络请求接受率 $V_{R}$ 的定义式为

V_{R} = \frac{R_{s}}{R_{t}}

，（13）

式中： $R_{s}$ 为网络中被成功映射的虚拟网络请求总数； $R_{t}$ 为到达网络的虚拟网络请求总数。

频谱利用率 $S_{U}$ 的定义式为

S_{U} = \frac{λ (B_{t} - B_{b})}{L_{t} F_{n} C T}

，（14）

式中： $B_{t}$ 为网络中共需要服务的虚拟光网络请求带宽； $B_{b}$ 为被阻塞的总虚拟光网络请求带宽； $L_{t}$ 为底层网络拓扑的总物理链路数； $F_{n}$ 为每条物理链路总的频隙数； $T$ 为网络总的运行时间； $C$ 为纤芯数。

芯间串扰改善率 $X_{T I R}$ 的定义式为

X_{T I R} = \frac{P_{L C L C ‑ V N M} - P_{o t h e r}}{P_{L C L C ‑ V N M}}

，（15）

式中： $P_{o t h e r}$ 为其他算法中芯间串扰大于串扰阈值导致的业务阻塞率； $P_{L C L C ‑ V N M}$ 为LCLC-VNM算法中芯间串扰大于串扰阈值导致的业务阻塞率。

仿真的对比算法选取LCLC算法^［11］、SD-RCSA算法^［14］和文献［20］中的虚拟节点映射算法。这3种算法都没有采用SDM-EONs下的虚拟网络映射，因此将SDM-EONs下的虚拟网络映射记为LCLC-VNM、SD-VNM和SVNE-RMSC。同时，为验证所提虚拟节点映射方法的合理性，在LCLC算法的基础上增加了虚拟节点邻近排序方法、物理节点度分类方法和物理节点优先级评估准则，命名为LCLC-ND算法；为验证虚拟带宽请求分配的合理性，在LCLC算法的基础上增加纤芯均衡方法和频谱区域分配方法，命名为LCLC-FS算法。为了保证仿真的准确性，选取虚拟网络到达数为5000，并且每组仿真进行三次，取其平均值作为最终结果。

5.2　仿真结果与分析

表2所示为6种算法的时间复杂度对比，均在多项式内可解。LCLC-VNM算法、LCLC-FS算法和SD-VNM采用的节点排序算法简单，只是把最大资源需求的虚拟节点优先映射到资源最多的光节点，并且仿真结果表明它们的网络优化效果不好。相比之下，CA-VNM算法的虚拟节点排序和物理节点排序的时间复杂度计算公式中多了 $O \{|N^{(s)}| |C^{(s)}| |F| [|L^{(s)}| + |N^{(s)}| l o g |N^{(s)}|]\}$ 和 $O (I)$ ，这是因为CA-VNM算法在物理节点排序阶段加入物理节点度分类算法，并且在频谱分配时对频谱划分区域。

表 2. 不同算法的时间复杂度对比

Table 2. Comparison of time complexity for different algorithms

Algorithm	Time complexity
SD-VNM	$O \{{\|N^{(v)}\|}^{2} + \|N^{(s)}\| \|N^{(v)}\| + K \|C^{(s)}\| I \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$
CA-VNM	$O \{{\|N^{(v)}\|}^{2} + \|N^{(s)}\| \|N^{(v)}\| + \|N^{(s)}\| \|C^{(s)}\| \|F\| [\|L^{(s)}\| + \|N^{(s)}\| l o g \|N^{(s)}\|] + K \|C^{(s)}\| I \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$
LCLC-VNM	$O \{\|N^{(v)}\| + \|N^{(s)}\| \|N^{(v)}\| + \|C^{(s)}\| \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$
LCLC-FS	$O \{\|N^{(v)}\| + \|N^{(s)}\| \|N^{(v)}\| + K \|C^{(s)}\| I \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$
LCLC-ND	$O \{{\|N^{(v)}\|}^{2} + \|N^{(s)}\| \|N^{(v)}\| + \|N^{(s)}\| \|C^{(s)}\| \|F\| [\|L^{(s)}\| + \|N^{(s)}\| l o g \|N^{(s)}\|] + \|C^{(s)}\| \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$
SVNE-RMSC	$O \{{\|N^{(v)}\|}^{2} + \|N^{(s)}\| \|C^{(s)}\| \|F\| [\|L^{(s)}\| + \|N^{(s)}\| l o g \|N^{(s)}\|] + K \|C^{(s)}\| I \|F\| [\|N^{(s)}\| l o g \|N^{(s)}\|]\}$

查看所有表

图7所示为6种算法在NSFNET 网络中的虚拟网络请求接受率。由图7可知，在相同负载下LCLC-FS算法的接受率高于LCLC-VNM算法和SD-VNM算法，这是因为在纤芯选择阶段，LCLC-FS算法均衡了每根纤芯的负载业务，避免了纤芯负载过大。在频谱分配时，预先将频谱分区，当分配频隙时，每个纤芯组和区域的频谱分配方法不一致，从而减小芯间串扰。LCLC-ND算法的接受率高于LCLC-VNM算法，这是因为在物理节点优先级评估时，LCLC-ND算法考虑了物理节点相邻链路上频谱碎片化程度和芯间串扰，从而平衡了串扰的影响，为后续虚拟链路映射提供了更优的选择。SVNE-RMSC算法的请求接受率高于LCLC-VNM算法，是因为在虚拟节点排序时，考虑了虚拟节点的计算资源、虚拟节点度和虚拟节点的相邻链路所需的带宽资源，确保虚拟节点成功映射。CA-VNM算法的请求接受率优于其他5种算法，其虚拟网络请求接受率最高提升了11%。这是因为在虚拟节点映射时，CA-VNM 算法考虑了虚拟节点与虚拟链路之间的关系，提高了虚拟网络映射的成功率。在选择物理节点时，首先进行节点筛选，优先选择虚拟节点度和物理节点度相同的节点，再考虑物理节点度大于虚拟节点度的节点，这样可以节省底层资源，为后续虚拟请求业务提供更多的底层物理资源。在评估物理节点优先级时，综合考虑节点之间的距离、物理节点资源、相邻链路上的频谱碎片以及芯间串扰，可提高链路的频谱利用率并且平衡芯间串扰。除此之外，在纤芯选择阶段考虑了虚拟请求带宽，均衡每根纤芯的负载，在频谱分配时，优化频谱分区方式，以节省更多的频谱资源并且减小芯间串扰。以上操作都能使更多的剩余物理网络资源服务虚拟网络。

图 7. NSFNET 网络中虚拟网络请求接受率

Fig. 7. Virtual network request acceptance rate in NSFNET network

下载图片查看所有图片

图8所示为6种算法在NSFNET网络拓扑中频谱利用率的仿真情况，可以看出，6种算法的频谱利用率都随着网络负载的增加而增大。LCLC-FS算法的利用率高于LCLC-VNM和SD-VNM算法，这是因为LCLC-FS算法采用纤芯负载均衡方法，把业务均匀分配在每根纤芯上，降低频谱碎片化程度，在此基础上，对于无法在所属纤芯分配的业务，可以在公共区域为其寻找空闲的频谱块，从而增加频谱的利用率。LCLC-ND算法的利用率高于LCLC-VNM算法的利用率，是因为在虚拟节点映射时，物理节点排序考虑了相邻链路的芯间串扰影响和频谱碎片化程度。CA-VNM算法在NSFNET网络中获得最优的频谱利用性能，其中频谱利用率最高提升了17.1%。这是因为在选择候选链路时，考虑物理链路的频谱碎片化程度和节点之间的跳数，减少带宽资源的浪费，降低均衡频谱碎片化程度。除此之外，在频谱分配时，对频隙进行区域划分，此方法能减小芯间串扰，并且在所划分区域的最后一个区域可以分配其他纤芯无法分配的虚拟网络链路请求，提高频谱利用率，而分配方式为首次命中和最后命中方式在每个区交替使用，此时就会有公共区域，可以最大化频谱利用率。因此，CA-VNM算法的频谱利用率高于其他5种算法。

图 8. NSFNET 网络中频谱资源利用率

Fig. 8. Spectrum resource utilization rate in NSFNET network

下载图片查看所有图片

图9所示为5种算法在NSFNET网络拓扑中的XTIR。由图9可知，XTIR随着负载的增大而逐渐降低，这是因为网络中空闲资源逐渐减少，使用其他方法也不能降低芯间串扰。CA-VNM算法的XTIR高于其他4种算法，当负载为100、200、300、400、500、600、700、800、900 Erlang时，实现的XTIR分别为67.7%、54.6%、46.3%、39.3%、32.8%、20.5%、11.8%、9.1%、7.0%。这是因为在虚拟节点映射过程中，CA-VNM算法在候选物理节点排序时不仅考虑物理节点的计算资源大小，而且考虑相邻链路的芯间串扰影响，使虚拟节点映射在相邻链路串扰影响程度小的物理节点。此外，在频谱分配时，把频谱预先分区，并且频谱分配方法在不同纤芯组的分配方式不一样，以减小芯间串扰。综上可见，CA-VNM算法能有效降低芯间串扰。

图 9. NSFNET 网络中XTIR

Fig. 9. XTIR in NSFNET network

下载图片查看所有图片

6　结论

提出SDM-EONs中串扰感知的虚拟网络映射算法，探析基于SDM-EONs中虚拟网络映射的芯间串扰约束条件。在评估虚拟节点优先级时考虑虚拟节点之间的邻近性，提出虚拟节点邻近排序方法；在选择候选物理节点时，考虑物理节点度，使更多的底层物理资源提供需求更大的虚拟请求业务。此外，提出串扰影响评估方法，在此基础上评估物理节点的权重，平衡芯间串扰。在纤芯选择时，根据虚拟链路所需带宽大小进行纤芯选择，均衡纤芯负载。最后对频谱进行区域划分，并且在分配频谱时交替使用首次命中和最后命中方式，以减小芯间串扰影响。仿真结果表明，与LCLC-VNM算法相比，在网络负载较小时，所提算法的虚拟网络接收率最高优化了11%，频谱利用率最高提升了17.1%，芯间串扰改善率最好能达到67.7%，可见所提算法有利于提高虚拟网络的接受率，并且能有效改善SDM-EONs中的芯间串扰，达到优化虚拟网络映射性能的效果。

参考文献

[1] 刘彤彤, 何荣希, 陈晓静. 流量疏导SD-EON中的持续时间感知多径路由与频谱分配算法[J]. 激光与光电子学进展, 2020, 57(21): 210602.

Liu T T, He R X, Chen X J. Holding-time-aware multipath routing and spectrum allocation algorithm in SD-EON with traffic grooming[J]. Laser＆Optoelectronics Progress, 2020, 57(21): 210602.

[2] 刘岩, 何荣希, 王钜霖, 等. 弹性光网络中面向立即预留请求的碎片感知路由频谱分配算法[J]. 激光与光电子学进展, 2022, 59(5): 0506008.

Liu Y, He R X, Wang J L, et al. Fragmentation-aware routing and spectrum allocation algorithm for immediate reservation requests in elastic optical networks[J]. Laser＆Optoelectronics Progress, 2022, 59(5): 0506008.

[3] Essiambre R J, Kramer G, Winzer P J, et al. Capacity limits of optical fiber networks[J]. Journal of Lightwave Technology, 2010, 28(4): 662-701.

[4] Muhammad A, Zervas G, Forchheimer R. Resource allocation for space-division multiplexing: optical white box versus optical black box networking[J]. Journal of Lightwave Technology, 2015, 33(23): 4928-4941.

[5] Zhang P Y, Yao H P, Liu Y J. Virtual network embedding based on computing, network, and storage resource constraints[J]. IEEE Internet of Things Journal, 2018, 5(5): 3298-3304.

[6] Zhu R J, Zhao Y L, Yang H, et al. Dynamic virtual optical network embedding in spectral and spatial domains over elastic optical networks with multicore fibers[J]. Optical Engineering, 2016, 55(8): 086108.

[7] 涂佳静, 李朝晖. 空分复用光纤研究综述[J]. 光学学报, 2021, 41(1): 0106003.

Tu J J, Li Z H. Review of space division multiplexing fibers[J]. Acta Optica Sinica, 2021, 41(1): 0106003.

[8] Xuan H J, Wang Y P, Xu Z Q, et al. Virtual optical network mapping and core allocation in elastic optical networks using multi-core fibers[J]. Optics Communications, 2017, 402: 26-35.

[9] Chen Q, Chen B W, Zheng W W, et al. Virtual optical network mapping approaches in space-division-multiplexing elastic optical data center networks[J]. Journal of Lightwave Technology, 2022, 40(12): 3515-3529.

[10] 刘焕淋, 胡会霞, 马敬, 等. 光路可靠性和频谱整合因子感知的虚拟光网络生存性映射[J]. 电子学报, 2021, 49(4): 744-749.

Liu H L, Hu H X, Ma J, et al. Survivable embedding of virtual optical network based on lightpath reliability and spectrum integration factor-aware[J]. Acta Electronica Sinica, 2021, 49(4): 744-749.

[11] Chen B W, Zhang J, Xie W S, et al. Cost-effective survivable virtual optical network mapping in flexible bandwidth optical networks[J]. Journal of Lightwave Technology, 2016, 34(10): 2398-2412.

[12] Liu S X, Cheng B K, Hang C, et al. Combined routing and core-spectrum assignment scheme based on spectrum status for spatial division multiplexing elastic optical networks[J]. Proceedings of SPIE, 2020, 11435: 114350I.

[13] Zhang J, Yao Q Y, Bao B W, et al. Resource-oriented RMCSA scheme with low crosstalk effect in multi-core fiber-based elastic optical networks[J]. Optical Fiber Technology, 2022, 68: 102796.

[14] 刘仕鑫. 空分复用弹性光网络中路由纤芯和频谱分配策略及其应用的研究[D]. 南京: 南京邮电大学, 2020: 12-16.

LiuS X. Research on routing and core-spectrum assignment scheme and application in spatial division multiplexing elastic optical networks[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2020: 12-16.

[15] Ren D P, Wang W, Hu J H, et al. Survivable virtual optical network coordinated mapping with local backup[J]. Journal of Optical Communications, 2021, 42(2): 265-271.

[16] 宣贺君, 王宇平, 徐展琦, 等. 多纤芯弹性光网络中纤芯选择算法[J]. 光学学报, 2016, 36(12): 1206005.

Xuan H J, Wang Y P, Xu Z Q, et al. Core selection algorithm for multi-core elastic optical networks[J]. Acta Optica Sinica, 2016, 36(12): 1206005.

[17] Zhu R J, Zhao Y L, Yang H, et al. Crosstalk-aware RCSA for spatial division multiplexing enabled elastic optical networks with multi-core fibers[J]. Chinese Optics Letters, 2016, 14(10): 100604.

[18] KlinkowskiM, WalkowiakK. Impact of crosstalk estimation methods on the performance of spectrally and spatially flexible optical networks[C]//2018 20th International Conference on Transparent Optical Networks (ICTON), July 1-5, 2018, Bucharest, Romania. New York: IEEE Press, 2018.

[19] Zhu J, Zhu Z Q. Physical-layer security in MCF-based SDM-EONs: would crosstalk-aware service provisioning be good enough?[J]. Journal of Lightwave Technology, 2017, 35(22): 4826-4837.

[20] Liu H L, Ma J, Chen Y, et al. A survivable VON embedding algorithm based on resource mean and spectrum coherence-aware in elastic optical networks[J]. Optical Fiber Technology, 2020, 54: 102103.

[21] MoritaK, HirataK. Dynamic spectrum allocation method for reducing crosstalk in multi-core fiber networks[C]//2017 International Conference on Information Networking (ICOIN), January 11-13, 2017, Da Nang, Vietnam. New York: IEEE Press, 2017: 686-688.

[22] Zhao J J, Bao B W, Yang H, et al. Holding-time- and impairment-aware shared spectrum allocation in mixed-line-rate elastic optical networks[J]. Journal of Optical Communications and Networking, 2019, 11(6): 322-332.

4　SDM-EONs中串扰感知的虚拟网络映射算法

任丹萍, 张黎, 胡劲华. 空分复用弹性光网络中串扰感知的虚拟网络映射算法[J]. 光学学报, 2023, 43(5): 0506003. Danping Ren, Li Zhang, Jinhua Hu. Crosstalk-Aware Virtual Network Mapping Algorithm in Space Division Multiplexing Elastic Optical Networks[J]. Acta Optica Sinica, 2023, 43(5): 0506003.