Nothing Special   »   [go: up one dir, main page]

CN108184175B - 基于mc节点受限的弹性光网络组播路由和频谱分配方法 - Google Patents

基于mc节点受限的弹性光网络组播路由和频谱分配方法 Download PDF

Info

Publication number
CN108184175B
CN108184175B CN201711482743.7A CN201711482743A CN108184175B CN 108184175 B CN108184175 B CN 108184175B CN 201711482743 A CN201711482743 A CN 201711482743A CN 108184175 B CN108184175 B CN 108184175B
Authority
CN
China
Prior art keywords
multicast
nodes
node
network
tree
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201711482743.7A
Other languages
English (en)
Other versions
CN108184175A (zh
Inventor
何阿成
石鹏涛
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Chongqing University of Post and Telecommunications
Original Assignee
Chongqing University of Post and Telecommunications
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Chongqing University of Post and Telecommunications filed Critical Chongqing University of Post and Telecommunications
Priority to CN201711482743.7A priority Critical patent/CN108184175B/zh
Publication of CN108184175A publication Critical patent/CN108184175A/zh
Application granted granted Critical
Publication of CN108184175B publication Critical patent/CN108184175B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/0001—Selecting arrangements for multiplex systems using optical switching
    • H04Q11/0005—Switch and router aspects
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/0001—Selecting arrangements for multiplex systems using optical switching
    • H04Q11/0062—Network aspects
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/0001—Selecting arrangements for multiplex systems using optical switching
    • H04Q11/0005—Switch and router aspects
    • H04Q2011/0037—Operation
    • H04Q2011/0047—Broadcast; Multicast
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/0001—Selecting arrangements for multiplex systems using optical switching
    • H04Q11/0062—Network aspects
    • H04Q2011/0073—Provisions for forwarding or routing, e.g. lookup tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/0001—Selecting arrangements for multiplex systems using optical switching
    • H04Q11/0062—Network aspects
    • H04Q2011/0086—Network resource allocation, dimensioning or optimisation

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明涉及一种基于MC节点受限的弹性光网络组播路由和频谱分配方法，属于光纤通信系统领域。该方法综合考虑组播调制格式、网络中具有组播能力(MC)节点个数、组播节点选取等因素，提出有效的预计算最短路径树的组播路由和频谱分配算法(PSPT‑DMRSA)，在组播路由之前，在网络中预先选取适当的MC节点，然后对已选取的MC节点建立最小生成树，以减少整个组播请求所占用的链路条数。本发明在频谱资源分配时采用距离自适应的调制制式，对组播请求选择适当的调制制式，提高频谱资源利用率，降低网络阻塞率。

Description

基于MC节点受限的弹性光网络组播路由和频谱分配方法
技术领域
本发明属于光纤通信系统领域，涉及一种基于MC节点受限的弹性光网络组播路由和频谱分配方法。
背景技术
全球通信的快速增长和互联网的普及已经显著改变了我们的生活方式，这一革命导致了每年的通信带宽的巨大增长。为满足未来互联网的需要，光传输技术正朝着高效，灵活和可扩展性的目标发展。2008年日本NTT公司首次提出了频谱切片弹性光网络(SpectrumSliced Elastic Optical Networks，SLICE)的概念。SLICE作为一种新颖的、高频谱效率、可扩展的光传送网络体系架构能够提供子波长业务通道和超波长业务通道，满足动态高效的带宽服务需求。SLICE网络打破了传统WDM网络中固定栅格的限制，利用O-OFDM信号调制技术，进行频谱分配和子载波多路复用，因此，相对于基于DWDM的光网络，网络利用效率大大提高。另外，在弹性光网络中，固定在当前部署的网络中的某些传输参数将会变得可以调节，如信号速率，调制格式和通道间隔。近年来，由于弹性光网络具有在光路中根据客户的带宽需求分配频谱的潜力，已被业界确定为未来光通信网络技术演进的方向。此外，云计算、交互式远程学习、视频会议、股票交易等业务的出现，高效的组播传输技术应用到网络中来，区别于单播的点对点传输，点对多点的组播传输方式大大提高了传输效率，节省了网络资源。随着用户对新型组播业务的需求持续增长，越来越多的大数据传输业务需要组播传输技术的支持，网络中组播业务量所占的比重持续增加，使得在弹性光网络中对组播的研究变的非常紧迫。
为了支持光网络的组播，引入了光树的概念，这是光路径的点对多点扩展(即非同步信道)。光树的主要优点是传输只需要一个光发射机，并且多个目的地可以共享中间树形链路。在为了有效地支持全光学组播，弹性光网络中的节点必须具有光分裂能力。具有分光能力的节点可以通过多个输出信道转发输入消息，因此具有多播传输能力(MulticastCapable,MC)，然而，MC节点的价格是比较昂贵的。文献首次提出稀疏分光的概念，是指网络中仅有部分节点是MC节点，其余的节点不具有分光能力(Multicast Incapable,MI)。这样可以有效的减少网络的成本，然而，如何将MC节点放置在网络中，以最大限度地减少MC节点个数，是一个有待解决的问题。文献(Zhou F,Ait-Ouahmed A,Cheref A.QoT-awaremulticast provisioning using column generation in mixed-line-rate opticalnetworks[C]//Computing,Networking and Communications(ICNC),2016 InternationalConference on.IEEE,2016:1-5.)在WDM光网络中对稀疏分光问题进行了研究，基于改进的现代启发式算法对路由和波长分配(RWA)问题进行研究，但是对于弹性光网络中的路由和频谱分配(RSA)并不适用，因为弹性光网络中的RSA问题需要满足诸多的约束，如频谱连续性约束、频谱一致性约束和频谱不重叠约束。文献(Ruiz M,Velasco L.Serving multicastrequests on single-layer and multilayer flexgrid networks[J].Journal ofOptical Communications and Networking,2015,7(3):146-155.)研究了两种不同的方法，其中通过使用多路径或单个光树来执行弹性光网络中的组播。作者提出了相应的ILP模型和启发式算法，在本研究中场景中，没有考虑组播节点的限制和放置问题。文献(Moharami M,Fallahpour A,Beyranvand H,et al.Resource Allocation and MulticastRouting in Elastic Optical Networks[J].IEEE Transactions on Communications,2017.)介绍了一种组播路由和频谱分配算法(DMRSA)，在组播路由时，依次求目的节点到源节点的最短路径，构建组播树，然后根据构建的组播树自适应的选择适当调制制式进行频谱分配。但是DMRSA算法每次都由目的节点向源节点路由，不能保证最优的组播树结构。所以频谱利用率不高，且网络的阻塞率较高。
针对上述弹性光网络中组播传输RSA策略，在一定的情况下提高了网络的性能，但是没能充分利用组播树结构使得频谱利用率不高，并且具有较高的阻塞率。
发明内容
有鉴于此，本发明的目的在于提供一种基于MC节点受限的弹性光网络组播路由和频谱分配方法，针对弹性光网络中仅有部分节点为MC节点，对组播的路由和频谱分配。利用MC节点可以有多个输出链路的特点，构建较优的组播树结构，提出了预计算最短路径树组播路由和频谱分配，即PSPT-DMRSA(Pre-computing Shortest Path Tree-Distanceadaptive Routing and Spectrum Allocation)，用来减少链路中消耗的带宽槽的数量，来达到减少光树总成本的目的。根据网络中MC节点的分布，在组播路由之前预先建立源节点到所有MC节点的MC树，然后依次将目的节点加入到组播树中。充分考虑了网络中组播节点的个数，组播节点位置的选取。在路由和频谱分配上充分利用网络中的MC节点，根据组播树结构选取适当的调制等级，从而提高频谱资源利用率，降低网络阻塞率。
为达到上述目的，本发明提供如下技术方案：
基于MC节点受限的弹性光网络组播路由和频谱分配方法，该方法为：在组播路由之前，在网络中预先选取适当的MC节点，然后对已选取的MC节点建立以源节点为根的MC树，然后依次将目的节点路由到源节点或MC节点，减少整个组播请求所占用的链路条数，减少请求占用的带宽资源。
进一步，所述在网络中预先选取适当的MC节点具体为：在考虑MC节点选取时，排除网络中度数小于3的节点，然后将网络中所有节点按照度数由大到小排序，然后求网络中任意两点间的最短路径，统计节点在这些路径中出现的总次数，记为counti，再按照counti由大到小对度数相同的节点排序，最终这个排序确定网络中节点被选为MC节点的优先级次序。
进一步，所述建立以源节点为根的MC树具体为：先确定网络中MC节点的个数N，然后选取前N个节点为MC节点；输入组播请求，设组播源节点为组播节点，构建选取的MC节点和组播源节点的斯坦纳树，使整个MC树的路径总代价最小，即为最短路径MC树。
进一步，所述组播路采用KSP算法，具体为：构建源节点到所有目的节点的组播树结构，依次求目的节点到所得MC树中MC节点的距离，或者到当前组播树中度数为1的MI节点的距离，根据当前网络状态选取最短路、次最短路或者第K最短路，设置一个合理的K降低网络的阻塞率，直到所有目的节点加入到当前组播树当中。
本发明的有益效果在于：本发明主要考虑弹性光网络中仅有部分节点为MC节点的组播路由和频谱分配问题，实现较高的频谱资源利用率而采用一种预计算最短路径树策略。为实现预计算最短路径树策略，首先要在网络中选取适当的MC节点，构建包括源节点在内的MC树，这样改变了组播路由的方式，由目的节点向源节点路由变为目的节点到当前所有MC节点路由，避免陷入局部最优，使频谱利用率得到提高。并且选路时使用KSP算法可以有效地避开较拥塞的链路，降低网络阻塞率。
附图说明
为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行说明：
图1为弹性光网络中的RSA；
图2为本发明中组播节点选取流程图；
图3为本发明中路由和频谱分配算法流程图；
图4为策略的整体流程图。
具体实施方式
下面将结合附图，对本发明的优选实施例进行详细的描述。
本发明所述的方法大体由两部分组成，基于度数大小的MC节点选取、基于组播树结构的路由和频谱分配。MC节点的选取即在给定网络中选取合适的节点设为MC节点，实现较大限度的分光能力，提高使用频率。路由和频谱分配即对请求选取适当的路由结构并分配合适的带宽槽，实现较高的频谱资源利用率，降低网络阻塞率。
因此，为实现专利在MC节点个数受限的弹性光网络中组播路由和频谱分配策略，具体内容如下：
网络中MC节点的选取，就是在给定的网络中选取MC节点，所以要对所有节点的优先级进行排序。优先级确定规则为度数优先，因为度数较大的节点能提供更多的分光能力，如公式1所示；
Figure GDA0002618646330000041
其中
Figure GDA0002618646330000042
表示节点的最大分光输出，vdegree表示节点的度数。
因为网络中存在许多度数相同的节点，所以仍需进一步确定优先级，其具体流程如图2所示。
组播树结构的路由和频谱分配，本发明针对弹性光网络中仅有部分节点为MC节点，对组播的路由和频谱分配。利用MC节点可以有多个输出链路的特点，构建较优的组播树结构，提出了一种预计算最短路径树组播路由和频谱分配策略，即PSPT-DMRSA(Pre-computing Shortest Path Tree-Distance adaptive Routing and SpectrumAllocation)，用来减少链路中消耗的带宽槽的数量，来达到减少光树总成本的目的。根据网络中MC节点的分布，在组播路由之前预先建立源节点到所有MC节点的MC树，然后依次将目的节点加入到组播树中。如图1(a)所示，图中节点1为源节点，目的节点为4、5和6，假设节点1和4为MC节点，其余为MI节点，预先建立节点1到节点4的一条光路1-2-4，然后用K-最短路算法依次求目的节点到当前MC树的最短路或次最短路(根据链路资源使用状态)，整个组播树包含的光纤链路为1-2-4-5和4-6。所占用的总带宽槽个数为8个。另外，将目的节点加入到当前组播树中时，也可以选择当前组播树中节点度数为1的MI节点，如图1(b)所示，整个组播树包含的光纤链路为1-2-4-5-6。
(1)将弹性光网络的物理拓扑抽象为有向图G＝(V,E)，其中V和E分别是网络的节点和有向链路的集合。其中对于每一条链路e∈E具有BGHz的频谱资源。对于基于MC节点的组播方案，所得到的光树T由MC树和光路组成，其中光路用于将MI节点与剩余目的节点连接到MC树。因此，光树的总成本就等于MC树的成本和与之相连的MI节点之间链路所需的带宽槽之和。
优化目标：
Minimize ∑e∈E∑f∈SSlot(f) (2)
其中S表示链路上可用的的带宽槽；f表示标号为f的带宽槽；Slot(f)为布尔变量，当标号为f的带宽槽被占用时为1。
(2)同时，弹性光网络中的频谱分配还需要满足频谱连续性限制、频谱一致性限制和频谱不重叠限制。对于多个组播请求定义ξi和
Figure GDA0002618646330000051
分别为组播请求Ri的组播树和在链路e∈E上频谱的占用，那么将三个限制条件表示如下：
Figure GDA0002618646330000052
Figure GDA0002618646330000053
Figure GDA0002618646330000054
公式3表示频谱连续性约束，其中fi,e表示其实带宽槽序号，ni表示组播请求Ri在链路e上占用的带宽槽个数，公示保证了这ni个带宽槽是连续的；公式4表示频谱一致性约束，保证组播请求Ri在所有链路上分配相同的带宽槽；公式5为频谱不重叠约束，保证组播请求
Figure GDA0002618646330000055
和
Figure GDA0002618646330000056
在链路e上分配的带宽槽没有重叠(若在不同的时间则不受此限制)。
(3)弹性光网络中请求占用的网络资源以带宽槽来计算，不同的调制制式选择会改变请求占用的带宽槽个数，同时会对最大传输距离产生影响，其对应关系如表1所示。对于带宽请求为b的组播业务，根据表1选择适当的调制等级m。可以确定所需的带宽槽个数为：
Figure GDA0002618646330000057
其中CBPSK是一个带宽槽使用BPSK时的容量，我们有CBPSK＝12.5Gb/s，Δg为保护带宽。因为采用不同调制格式，所以为了避免交叉相位调制的影响，相邻请求之间需要加入保护带宽。
组播树的构建和频谱分配的具体步骤如下：1)网络初始化，设定MC节点个数N，输入组播请求r＝{s,D,b}；2)假设源节点为MC节点，构建源节点到所有MC节点的斯坦纳树，MC节点集合记为Vk；3)依次将目的节点到MC节点的最短路径，构建组播树；4)根据组播树源到目的节点的最远距离确定调制等级，并分配带宽槽。算法流程图如图3所示。
下面将结合附图4将本发明实现资源节约的组播路由和频谱分配策略的整体流程进行说明：
Step1：在网络中按度数优先原则对所有节点优先级排序
Step2：网络初始化，设定MC节点个数N，输入组播请求r＝{s,D,b}；
Step3：计算各MC节点间的最短路径，以s为根节点构建斯坦纳树，当前MC树中MC节点集合记为Vk；
Step4：m＝4，由公式6求所需带宽槽个数n；
Step5：根据网络状态求di到vki的K最短路径dik，其中vki∈Vk。如果dik不存在则转入Step7；
Step6：Vk＝Vk∪di，循环执行Step5、6直到所有的组播目的节点加入到组播树中，
Step7：m＝m-1,m>0，转入Step5。
声明：假定所有的组播请求源节点为MC节点。一个组播内部存在多个请求，如果某个请求不可到达，即链路不能提供足够的带宽槽，则定义这个组播业务阻塞。步骤4-7包含了频谱分配过程，采用经典的First-Fit(FF)算法，m的值确保当前组播请求选择了最优的调制制式，最短路径dik需要满足表1所示的调制等级与最大传输距离之间的关系。
表1调制制式、调制等级与传输距离的关系
Figure GDA0002618646330000061
最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。

Claims (1)

1.基于MC节点受限的弹性光网络组播路由和频谱分配方法，其特征在于：该方法为：在组播路由之前，在网络中预先选取适当的MC节点，然后对已选取的MC节点建立以源节点为根的MC树，然后依次将目的节点路由到源节点或MC节点，减少整个组播请求所占用的链路条数，减少请求占用的带宽资源；
所述在网络中预先选取适当的MC节点具体为：在考虑MC节点选取时，排除网络中度数小于3的节点，然后将网络中所有节点按照度数由大到小排序，然后求网络中任意两点间的最短路径，统计节点在这些路径中出现的总次数，记为counti，再按照counti由大到小对度数相同的节点排序，最终这个排序确定网络中节点被选为MC节点的优先级次序；
所述建立以源节点为根的MC树具体为：先确定网络中MC节点的个数N，然后选取前N个节点为MC节点；输入组播请求，设组播源节点为组播节点，构建选取的MC节点和组播源节点的斯坦纳树，使整个MC树的路径总代价最小，即为最短路径MC树；
所述组播路采用KSP算法，具体为：构建源节点到所有目的节点的组播树结构，依次求目的节点到所得MC树中MC节点的距离，或者到当前组播树中度数为1的MI节点的距离，根据当前网络状态选取最短路、次最短路或者第K最短路，设置一个合理的K降低网络的阻塞率，直到所有目的节点加入到当前组播树当中。
CN201711482743.7A 2017-12-29 2017-12-29 基于mc节点受限的弹性光网络组播路由和频谱分配方法 Active CN108184175B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201711482743.7A CN108184175B (zh) 2017-12-29 2017-12-29 基于mc节点受限的弹性光网络组播路由和频谱分配方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201711482743.7A CN108184175B (zh) 2017-12-29 2017-12-29 基于mc节点受限的弹性光网络组播路由和频谱分配方法

Publications (2)

Publication Number Publication Date
CN108184175A CN108184175A (zh) 2018-06-19
CN108184175B true CN108184175B (zh) 2020-09-22

Family

ID=62549209

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201711482743.7A Active CN108184175B (zh) 2017-12-29 2017-12-29 基于mc节点受限的弹性光网络组播路由和频谱分配方法

Country Status (1)

Country Link
CN (1) CN108184175B (zh)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2020061790A1 (zh) * 2018-09-26 2020-04-02 深圳大学 基于距离自适应的波带交换方法
CN109889928B (zh) * 2018-12-07 2022-01-25 中国南方电网有限责任公司 多播光树传输质量预测方法、装置、设备和存储介质
CN112203165B (zh) * 2020-09-07 2022-04-12 烽火通信科技股份有限公司 一种otn中实现灵活栅格业务的方法及系统

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106535012B (zh) * 2016-11-23 2019-06-07 重庆邮电大学 基于遗传算法优化组播光森林的能效路由频谱分配方法
CN106850427A (zh) * 2017-01-17 2017-06-13 北京工业大学 面向网络编码使能的弹性光组播网络的路由频谱分配方法

Also Published As

Publication number Publication date
CN108184175A (zh) 2018-06-19

Similar Documents

Publication Publication Date Title
Abkenar et al. Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs)
CN105141517B (zh) 一种基于资源感知的灵活光网络任播业务节能路由方法
Wang et al. Holding-time-aware scheduling for immediate and advance reservation in elastic optical networks
WO2013037570A1 (en) Allocation of spectral capacity in a wavelength-division multiplexing optical network
Yuan et al. A RMSA algorithm for elastic optical network with a tradeoff between consumed resources and distance to boundary
CN108184175B (zh) 基于mc节点受限的弹性光网络组播路由和频谱分配方法
Goścień Two metaheuristics for routing and spectrum allocation in cloud-ready survivable elastic optical networks
CN103260094B (zh) 一种路由方法、路由策略的通知方法及相应的装置
Yu et al. Multicast routing and spectrum assignment in elastic optical networks
CN106535012B (zh) 基于遗传算法优化组播光森林的能效路由频谱分配方法
CN103581006A (zh) 用于灵活栅格光网络全局优化的系统架构及其全局优化方法
CN105007223A (zh) 一种基于光层次架构的光网络动态多播路由波长分配方法
Biswas et al. Energy-efficient network planning and traffic provisioning in IP-over-elastic optical networks
Cai et al. Coordinating multiple light-trails in multicast elastic optical networks with adaptive modulation
Xu et al. Dynamic routing and spectrum allocation to minimize fragmentation in elastic optical networks
Liu et al. Traffic load-aware dynamic energy-efficient routing strategy with spectrum reservation and load balance in elastic optical networks
Liu et al. Energy-efficient multicast traffic grooming strategy based on light-tree splitting for elastic optical networks
CN104506442A (zh) 一种灵活网格光网络的多点到多点组播业务光疏导方法
Shirin Abkenar et al. The energy minimization algorithm for elastic optical networks
Wei et al. Anycast service grooming algorithm of cloud computing based on wireless communication network
Mahala et al. Weight distributed spectrum allocation in flexible-grid optical networks
Pradhan et al. Knapsack based multicast traffic grooming for optical networks
Petale et al. CLARA: Capacity Loss-Aware Resource Assignment Algorithm for Translucent SDM EONs
CN109698982B (zh) 控制通道实现方法、装置、设备、存储介质和处理方法
Lin et al. Dynamic Multicast Traffic Grooming Using Light Trails in Elastic Optical Networks

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant