一种基于距离自适应路由与频谱分配的预计算恢复方法

摘要

本发明涉及一种基于距离自适应路由与频谱分配的预计算恢复方法，该方法通过设计软件定义弹性光互联数据中心网络架构，将网络控制平面和数据转发平面分离，并对控制器功能模块和OpenFlow协议进行扩展，实现快速灵活地定制网络功能；根据链路上频谱隙数量对网络拓扑划分层次，构建频谱窗口分层辅助图模型，并通过距离自适应选择合适的调制格式，利用频谱窗口分层辅助图模型对业务进行路由和频谱分配；在对故障业务进行恢复时，使用预计算恢复技术提前为业务计算恢复路由，当业务发生故障后，使用预计算恢复方案为中断业务开通网络资源，快速建立恢复路由。本方法能够满足频谱邻接性和连续性的双重约束，避免造成阻塞，同时可以保证故障业务的快速恢复，提升网络的整体性能。

说明书

技术领域

本发明属于弹性光互联数据中心网络技术领域，涉及一种基于距离自适应路由与频谱分配的预计算恢复方法。

背景技术

近年来，随着大数据、云计算以及高清多媒体视频等高带宽业务的出现，使得数据中心网络中的IP业务突飞猛进增长[Index C V N.Forecast and Methodology,Technical Report,CiscoWhite Paper[R].2015:2014-2019.]。数据中心海量信息的交换，业务流量和流向的不确定性，迫切要求光网络能够灵活、快速、可靠地承载并传输数据中心业务。传统的波分复用(wavelength-division-multiplexing,WDM)光网络由于固定ITU-T波长间隔限制，导致其频谱利用率较低。基于光正交频分复用技术(OFDM)的弹性光网络(EON)被作为未来的第三代光网络提出。EON使用OFDM技术将光层的带宽分配粒度降低到副载波信道的亚波长量级(6.25GHz或12.5GHz)，即光层信号传输的基本单元不再是粗粒度的波长，而是更精细粒度的“频隙”(Frequency Slot,FS)。当带宽需求不同的混合粒度业务出现时，只要为其分配所需数目的FS。从而有效实现了光层资源的虚拟化和按需配置，大大提高了网络带宽利用率和灵活率，以致其能够支持1Tb/s的业务传输。弹性光网络由于带宽高、资源按需分配以及调度灵活的特性，因此非常适用于光互联的数据中心网络[ShiehW,BaoH,TangY,Coherent optical OFDM:theory and design[J].Optics Express,2008,16(2):841–859.]。然而，应用于光互联数据中心场景的弹性光网络是连接数据中心大规模服务器的桥梁，也是承载网络化存储和计算的基础，单根光纤的传输容量非常大，其高带宽的优势同时会导致故障后海量数据中心业务的中断。因此，近年光互联数据中心网络的生存性问题得到了广泛的关注。

文献[Walkowiak K,Klinkowski M,Rabiega B,et al.Routing and spectrum allocation algorithms for elastic optical networks with dedicated path protection[J].Optical Switching and Networking,2014,13:63-75.]提出弹性光网络中带有专有保护的路由和频谱分配方法，保证了业务的快速恢复以及高可靠性。然而，专有保护中不允许备份频谱资源共享，大大地增加了网络的保护开销。文献[Shao X,Yeo Y K,Xu Z,et al.Shared-path protection in OFDM-based optical networks with elastic bandwidth allocation[C]//Optical Fiber Communication Conference.Optical Society ofAmerica,2012:OTh4B.4.]提出了两种资源共享保护方法：保守共享策略和积极共享策略，相对于专有保护极大地提高了备份资源共享度，减少了频谱消耗。但是，该算 法的保护频谱资源共享度较低。为了进一步增加保护频谱资源共享度，文献[Wei Yue,Shen Gangxiang.Span restoration for flexi-grid optical networks under different spectrum conversion capabilities[C]//20139th International Conference on the Design of Reliable Communication Networks(DRCN 2013).Budapest:IEEE Press,2013:79-87.]中提出了全频谱转换下的带宽压缩共享保护算法，虽然该算法增加了保护频谱资源的共享度，提高了资源利用率。但是该算法没有考虑物理层损伤可能导致工作路径和保护路径使用不同调制格式。文献[Wang C,Shen G,Bose S,et al.Distance Adaptive Dynamic Routing and Spectrum Allocation in Elastic Optical Networks with Shared Backup Path Protection[J].Lightwave Technology,2015,33(14):2955-2964.]考虑了数据中心业务，在数据中心弹性光网络中根据数据中心业务端到内容的特性，提出了一种基于内容连通性的带宽自适应保护算法，不仅保证了业务的连通性，而且降低了阻塞率。但是随着网络中数据中心业务的突飞猛进增长，各种各样的业务给数据中心网络控制平面带来了极大地调度压力。因此，迫切需要一种高效的网络控制方式，灵活地调度网络中的资源。在分布式的数据中心弹性光网络中，算法的执行效率和灵活性较低，网络成本高。新兴的软件定义网络(Software-Defined Networking，SDN)技术可以对大容量光网络快速部署、资源灵活调度以及可编程控制等要求，因此SDN控制方式是光互联数据中心网络中比较利息那个的控制方式。文献[Ma C,Zhang J,Zhao Y,et al.Bandwidth-adaptability protection with content connectivity against disaster in elastic optical datacenter networks[J].Photonic Network Communications,2015,30(2):309-320.]使用新兴的软件定义网络技术(Software-Defined Networking，SDN)将网络的控制功能从转发设备中分离出来，并首次通过国际试验平台，验证了SDN光网络架构的可行性，同时证明SDN可以有效解决光网络带宽利用率低，新业务部署麻烦且时间长的问题。文献[Yang.H,Cheng.L,Yuan.J,et al.Multipath protection for data center services in OpenFlow-based software defined elastic optical networks[J].Optical Fiber Technology,2015,23:108-115]引入弹性光网络，提出了一种基于OpenFlow的软件定义弹性光网络架构，并设计了基于业务优先级的多路径保护策略，实现了对网络的实时监测以及远程集中控制，保证了业务的服务质量、降低成本。然而，保护算法需要在备份路径上为业务预留保护资源，资源冗余较大，而恢复算法则不需要预留资源。为此，文献[Giorgetti A,Paolucci F,Cugini F,et al.Fast restoration in SDN-based flexible optical networks[C]//Optical Fiber Communication Conference.Optical Society ofAmerica,2014:Th3B.2.]针对软件定义弹性光网络，提出了一种快速恢复算法，通过SDN的集中控制方式，控制器首先快速感知故障信息，然后使用重路由程序为受损业务重新计算路由，最后并行地下发配置命令，完成业务的恢复。然而，该恢复算法没有考虑业务重路由的计算时间占整个恢复时间比重较大的问题。

发明内容

有鉴于此，本发明的目的在于提供一种基于距离自适应路由与频谱分配的预计算恢复方法，该方法基于频谱窗口分层辅助图模型，对业务进行距离自适应路由与频谱分配，满足频谱双重约束的同时，有效地提高了网络资源利用率；同时，对故障业务采用预计算恢复方法，有效地降低了恢复时延，保障了业务的服务质量。

为达到上述目的，本发明提供如下技术方案：

一种基于距离自适应路由与频谱分配的预计算恢复方法，该方法包括：首先，设计软件定义弹性光互联数据中心网络架构，实现将网络控制平面和数据转发平面分离，并对控制器功能模块和OpenFlow协议进行扩展，从而实现快速灵活地定制网络功能；其次，根据链路上频谱隙数量对网络拓扑划分层次，构建频谱窗口分层辅助图模型，并通过距离自适应选择合适的调制格式，利用频谱窗口分层辅助图模型对业务进行路由和频谱分配，在保证频谱双重约束条件的同时，保证业务的服务质量要求；最后，在对故障业务进行恢复时，使用预计算恢复技术提前为业务计算恢复路由，当业务发生故障后，直接使用预计算恢复方案为中断业务开通网络资源，快速地建立恢复路由，从而实现受故障影响的业务快速恢复。

进一步，所述软件定义弹性光互联数据中心网络架构的设计为：通过软件定义网络技术，将网络的控制平面和数据转发平面分离，控制器通过扩展的OpenFlow协议对数据转发平面进行集中控制；对控制器的功能模块进行扩展，在控制器中添加了故障检测模块和预计算模块。

进一步，所述路由和频谱分配的方法为：首先根据链路上频谱隙数量创建频谱窗口(Spectrum Window,SW)，每个SW包括一个频谱隙，基于SW提出一种频谱隙窗口平面(Spectrum slotWindow Plane,SWP)分层辅助图模型，每一层代表一个频谱隙，分层图中以频谱隙剩余量矩阵记录频谱资源剩余容量；其次，根据业务的实际传输距离自适应选择调制格式，计算业务所需要的频谱系数量，并利用SWP分层辅助图模型创建多频谱宽度的频谱隙窗口平面(Multiple Spectrum slotWindowPlane,MSWP)分层辅助图模型，实现不同业务的路由和频谱分配一步算法，具体包括以下步骤：

步骤1：创建SWP分层辅助图模型，计算每一层对应的频谱隙剩余量矩阵

步骤2：从16QAM到BPSK，对每个调制格式，计算业务请求r所需的频谱隙个数；若所有调制格式都被遍历过，则阻塞业务，转到步骤8；

步骤3：根据公式计算MSWP对应的剩余量矩阵，创建MSWP分层辅助图模型；

步骤4：对每个MSWP(从索引值最低索开始)，通过Dijkstra最短路径算法为业务选择最短路径p_w；

步骤5：如果路径p_w找到，则记录该路由信息和MSWP索引值，并跳到步骤7；否则，执行下一步；

步骤6：若索引值未达到最大值，移至下一个MSWP，重复步骤4到5，否则返回步骤2；

步骤7：如果路由信息w_route＝NULL，则将p_w→w_route，当前MSWP的起始索引值→w_index；否则，如果p_w的跳数小于w_route的跳数，则将p_w→w_route，当前MSWP的起始索引值→w_index；

步骤8：算法结束。

进一步，所述的预计算恢复方法为：首先，在网络发生故障前，控制器通过网络状态数据库以及网络拓扑抽象模块对网络进行实时更新，通过预计算功能模块提前为业务计算恢复路由，并将结果存储在控制器中，以备业务中断后使用；其次，当网络发生故障后，控制器中的故障检测模块很快能够接收到故障节点返回的信息，此时控制器会启用预计算功能模块提前计算好的备用恢复路由信息，通过OpenFlow协议将恢复路由流表信息下发到底层的OF-BVOS中，各OF-BVOS为其进行频谱资源预留和交叉连接；与此同时，控制器会发送Flow-Mod消息删除源、目的节点中的原工作路由流表项，在备用恢复路径被建立之后，就完成了该恢复业务的故障恢复过程。

本发明的有益效果在于：本发明所述方法设计软件定义弹性光互联数据中心网络架构，实现将网络控制平面和数据转发平面分离，并对控制器功能模块和OpenFlow协议进行扩展，从而实现快速灵活地定制网络功能；根据链路上频谱隙数量对网络拓扑划分层次，构建频谱窗口分层辅助图模型，并通过距离自适应选择合适的调制格式，利用频谱窗口分层辅助图模型对业务进行路由和频谱分配，保证业务的服务质量要求；在对故障业务进行恢复时，使用预计算恢复技术提前为业务计算恢复路由，当业务发生故障后，直接使用预计算恢复方案为中断业务开通网络资源，快速地建立恢复路由，从而实现受故障影响的业务快速恢复。

附图说明

为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行说明：

图1为软件定义弹性光互联数据中心网络架构；

图2为扩展的控制器功能模块示意图；

图3为单光纤链路的频谱隙窗口图；

图4为频谱隙窗口分层辅助图模型；

图5为多频谱宽度的窗口分层辅助图模型；

图6为恢复过程时序图；

图7为本发明所述方法的流程示意图。

具体实施方式

下面将结合附图，对本发明的优选实施例进行详细的描述。

本发明提供了一种基于距离自适应路由与频谱分配的预计算恢复方法，图7为该方法的流程示意图。在该方法中，设计软件定义弹性光互联数据中心网络架构，实现将网络控制平面和数据转发平面分离，并对控制器功能模块和OpenFlow协议进行扩展，从而实现快速灵活地定制网络功能；根据链路上频谱隙数量对网络拓扑划分层次，构建频谱窗口分层辅助图模型，并通过距离自适应选择合适的调制格式，利用频谱窗口分层辅助图模型对业务进行路由和频谱分配，保证业务的服务质量要求；在对故障业务进行恢复时，使用预计算恢复技术提前为业务计算恢复路由，当业务发生故障后，直接使用预计算恢复方案为中断业务开通网络资源，快速地建立恢复路由，从而实现受故障影响的业务快速恢复。

具体来说：

一、软件定义弹性光互联数据中心网络架构

软件定义弹性光互联数据中心网络架构如图1所示，将网络分为控制平面和底层的数据平面。控制器通过扩展的OpenFlow协议(OpenFlow Protocol，OFP)对底层数据中心弹性光网络进行集中控制。为了实现控制器的控制功能，数据平面网络的节点应由OFP代理和OpenFlow使能的带宽可变光交换机(bandwidth variable optical switch，OF-BVOS)组成。OFP代理接收控制器下发的流表，并将其翻译成底层的硬件设备可以理解的逻辑语言，进而控制底层的OF-BVOS交叉连接过程。为了在故障情况下，实现对故障业务的快速恢复需要对控制功能进行扩展。当网络发生故障时，控制器首先快速感知故障信息，然后使用故障恢复模块为受损业务重新计算路由并进行资源分配，最后通过OFP并行地下发配置命令完成业务的恢复。

控制器的功能模块扩展如图2所示，软件定义数据中心弹性光网络中控制器功能模块如图2所示。控制器集中了数据平面节点设备的控制运算部分，包括插件程序模块、预计算模 块、故障恢复模块、网络抽象模块、网络拓扑信息数据库模块等。其中网络抽象模块主要功能是从物理网络中抽象网络资源，动态地维护网络拓扑信息数据库，网络拓扑信息数据库是网络进行其它决策的基础。当网络中的链路发生故障时，故障恢复模块启用相应的恢复策略对业务进行恢复。PCE模块通过与OF-BVOS的代理器进行交互，可以计算工作路径和恢复路径，且各种计算策略均可作为插件程序被选择。控制器中预计算模块，负责为业务计算一条备用的恢复路由，备用路由并不占用路径上的资源，存储在控制器中。当网络中的业务发生故障时，便可以直接调用预计算模块计算出的路由对业务进行恢复。

二、频谱窗口分层辅助图模型

在弹性光网络中，为业务路由与资源分配时必须满足以下2方面重要特性：(1)频谱连续性，即对无频谱转换能力的弹性光网络，一条光通路必须使用相同的频谱块；(2)频谱邻接性，即为业务分配的频谱块必须是一段连续可用的频谱隙。在两个约束条件下，为了找到具有连续可用频谱资源的路由，即实现RSA一步算法，同时查找到路由、可用的连续频谱，引入了频谱窗口(Spectrum Window,SW)[Y.Liu,N.Hua,X.Wan,et,al.A spectrum-scan routing scheme in flexible optical networks,in Proc.Asia Commun.Photon.Conf.Exhib.,2011,pp.1–6.]概念。规定每个SW由一个频谱隙单位组成，假设每条光纤链路有n个频隙，单根光纤的频谱窗口如图3所示。基于频谱窗口的概念，提出了一种频谱隙窗口分层(Spectrum slotWindow Plane,SWP)辅助图模型。6个节点10条链路的网络拓扑，其频谱隙窗口分层辅助图模型如4所示。每个SWP对应一个SW，而且每个SWP都对应一个矩阵R_si，如公式(1)所示，表示该频谱层中链路上频谱资源使用情况的一种矩阵形式的记录。矩阵中的元素m_ij值为1时，表示链路(i,j)上有可用频谱资源，m_ij值为0时，表示链路(i,j)上无可用频谱资源。

由于网络中数据中心业务的多样性，不同业务往往需要分配不同带宽大小的连续可用频谱资源。因此，在SWP基础上提出了多频谱宽度的频谱隙窗口分层辅助图MSWP，不同宽度频谱隙窗口层对应的资源剩余量矩阵计算方法如式(2)所示，其中n_i代表业务所需的频隙个数。根据矩阵计算结果可以映射出多频谱宽度的分层辅助图。

$R=\underset{i\in (1,n_i)}{\cap }{R}_{si}---\left(2\right)$

例如，对2个频隙大小的业务r，在图4中6个节点10条链路的网络拓扑中进行路由和 频谱分配，从索引值最低的SWP1开始，根据公式(2)计算出两个频谱隙宽度的2SWP。其对应的资源剩余量矩阵如图5所示，若矩阵中的元素为1，说明对应节点之间有一条链路；若元素为0，则说明对应节点之间的链路上没有连续可用频谱隙，需删除该条链路。根据计算结果映射出分层图，如图5所示，在图中的每一窗口层上直接进行路由便可实现RSA一步算法。

三、距离自适应路由与频谱分配方法

在弹性光网络中，带宽分配时可以根据业务的实际传输距离自适应选择调制格式。通过自适应调制技术和比特率/带宽转换器，为长距离路径采用低调制格式与宽频谱带宽，为短距离路径采用高调制格式与窄频谱带宽，从而进一步提高频谱效率。假设每个频谱隙带宽大小为12.5GHz，4种不同调制格式(Modulation Format,MF)的子载波负载能力以及所支持的传输距离范围如表1所示。

表1不同调制格式的子载波负载能力以及传输距离范围参数

调制格式子载波的负载能力传输距离Bit/符号BPSK12.5(Gbit)4000(km)1QPSK25(Gbit)2000(km)28-QAM37.5(Gbit)1000(km)316-QAM50(Gbit)500(km)4

对任意大小的业务请r(s,d,Φ)，在某一确定的调制格式下所需分配的频谱隙个数n_i可以通过公式(3)求得。式(3)中B表示每个FS的带宽大小，单位是GHz；s、d和Φ分别表示源节点、目的节点和业务请求带宽。

$n_i=\frac{\Phi }{B·{\log }_2{M}_i}---\left(3\right)$

基于窗口分层图模型，设计了动态距离自适应RSA启发式算法。定义参数w_route和w_index分别记录工作路由信息和工作路由的起始FS索引值，基于SWP分层辅助图的路由和频谱分配全过程包括以下几个步骤：

步骤1：创建SWP分层辅助图模型，根据公式(1)计算每一层对应的频谱隙剩余量矩阵R_si；

步骤2：从16QAM到BPSK，对每个调制格式，计算业务请求r所需的频谱隙个数；若所有调制格式都已被遍历过一次，则阻塞业务，转到步骤8；

步骤3：根据公式(2)计算MSWP对应的剩余量矩阵R，创建MSWP分层辅助图模型；

步骤4：对每个MSWP(从索引值最低索开始)，通过Dijkstra最短路径算法为业务选择最短路径p_w；

步骤5：如果路径p_w找到，则记录该路由信息和MSWP索引值，并跳到步骤7；否则，执 行下一步；

步骤6：若索引值未达到最大值，移至下一个MSWP，重复步骤4到5；否则返回步骤2

步骤7：如果路由信息w_route＝NULL，则将p_w→w_route，当前MSWP的起始索引值→w_index；否则，如果p_w的跳数小于w_route的跳数，则将则将p_w→w_route，当前MSWP的起始索引值→w_index；

步骤8：算法结束。

四、预计算恢复方法

(1)故障前预计算过程

基于链路状态的多约束路由预计算恢复策略，大大降低了恢复算法的重路由计算时间。但是在这种分布式网络中，预计算是通过节点间交互大量的控制信令(如G-MPLS)实现的，而这些信令的传输会消耗大量的网络资源。

在数据中心弹性光网络中，使用软件定义网络技术对恢复路径进行预计算，只需在控制器中额外开启一个线程，占用少许CPU计算资源，不需要消耗网络的传输资源即可实现对保护路径的预计算；其次，SDN控制器能够快速、准确的收敛网络状态信息，并行地对网络节点进行配置，因此基于SDN控制技术的预计算性能也更加优越。由于数据中心网络的业务量较大，这里只对比较重要的数据中心业务进行恢复路径预计算。该预计算恢复策略在链路发生故障前，假设被保护的重要数据中心业务中断情况发生，为业务进行恢复路由预计算，将计算结果存储在控制器中，不执行建路过程。当业务真正发生故障后，控制器可直接使用预计算恢复方案，为中断的业务开通网络资源，建立恢复路由。

(2)故障后快速恢复过程

当业务发生中断时，控制器中的故障检测模块很快能够接收到故障节点返回的信息。控制器会查询之前预计算功能模块提前计算好的备用恢复路由，然后通过OFP将备用恢复路由的流表信息下发到底层的OF-BVOS中，各OF-BVOS为其进行频谱资源预留和交叉连接；与此同时，控制器会发送Flow-Mod消息删除源、目的节点中的原工作路由流表项。在备用恢复路径被建立之后,就完成了该恢复业务的故障恢复过程，基于预计算的恢复过程时序图如图6所示。其中τ_ps表示从故障链路节点向控制器上传故障信息所用的时间；τ_search表示预计算恢复路由结果查询所用时间；τ'_i表示控制器下发流表删除信息，到达原工作链路上各节点所用的时间。Δt则是控制器下发插入恢复路由流表信息与删除原工作路由流表信息二者之间的时间间隔,一般Δt≥0。因此，整个预计算恢复策略的恢复时间如公式(4)所示。

$t_{pc}={\tau }_{ps}+{\tau }_{search}+Max[(\Delta t+\underset{i\in \left[1.n\right]}{Max}{{\tau }^{\prime }}_i),\underset{i\in [1,n]}{Max}{\tau }_i],\Delta t\ge 0---\left(4\right)$

传统的恢复算法具有较大的时延，这些时延主要由带宽、中心频率的计算和各设备的交叉连接过程产生，其中带宽和中心频率的计算过程占时间比重较大。通过使用预计算恢复算法，可以解决因计算带宽、中心频率而产生的时延过大的问题。该预计算恢复算法，在时延性能上可以比拟保护算法，在资源利用率上可以比拟恢复算法，它结合了保护算法和恢复算法的优点。

最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。