2020, Vol. 41
随着经济社会和全球化趋势的发展, 互联网正在经历从未有过的迅猛发展, 人们每时每刻都要连接和使用互联网, 导致了每年带宽消耗的快速增长.弹性光网络(elastic optical networks, EONs)突破了波分复用(wavelength division multiplexing, WDM)网络带宽固定的限制, 可以根据用户需求确定所需的频谱资源, 极大地提高了频谱资源的利用率.
为了满足服务质量的要求, 出现了网络虚拟化技术.网络虚拟化技术允许多个虚拟网络共享同一个底层物理网络, 每一个虚拟光网络(virtual optical networks, VONs)都是底层网络的一个资源片, 它能有效地解决当前网络体系结构中的僵化问题.虚拟光网络嵌入(virtual optical network embedding, VONE)技术作为网络虚拟化的核心问题, 可以实现频谱的分配和管理, 缓解当前网络压力[1-3].
多播技术采用一点对多点的通信方式[4], 不仅可以将要传输的数据一次性地传送给特定的目的节点, 并且可以在广域网上进行传输.将多播技术与虚拟网络映射技术相结合, 能够提高网络资源利用率, 改善网络的性能.文献[5]研究如何在通用IP网络和基于正交频分复用(orthogonal frequency division multiplexing, OFDM)的EONs上有效地映射虚拟网络用于多播服务, 同时考虑在不同的虚拟网络之间的可靠性方面的最大-最小公平性.文献[6]以软件定义网络为底层网络, 将虚拟光多播树映射到软件定义网络中.文献[7]提出了新颖的主动风险感知多播虚拟网络映射算法, 以提高网络嵌入的效率.文献[8]研究如何有效地映射虚拟请求以获得可靠的多播服务, 还提出了一种混合整数线性规划模型来确定最大-最小公平可靠性的上界.文献[9]提出了一种新的多播映射算法, 它基于路径收敛, 灵活地识别和配置多播树中的节点.
对于虚拟网络嵌入技术, 不仅要关注其有效性和利用率, 网络的生存性也至关重要.网络生存性是指当网络发生故障时, 仍然能够正常分配带宽资源, 进行虚拟网络的嵌入, 将数据传输给用户, 不会产生请求的中断.文献[10]提出的影响因子优先映射的算法同时映射虚拟节点和虚拟链路, 将虚拟光多播树嵌入到底层光网络中.文献[11]提出了一种结合物理节点和多逻辑链路保护机制的虚拟网络映射方法, 此方法基于p-Cycle的保护技术使备份资源最小化.文献[12-13]引入一种新的度量——虚拟网络故障概率, 去评估弹性光网络中虚拟嵌入的生存性.文献[14]研究了节点和跨域保护策略以及节点环绕p-Cycle保护.文献[15]使用两个线性规划模型和遗传算法研究可到达的多播虚拟光网络嵌入的在线和离线映射.文献[16]引入遗传算法和模拟退火算法去减少弹性光网络的多播服务的频谱分配, 并为其增加多播请求保护.
与上述网络嵌入算法相比, 本文针对多播业务的特点, 研究了嵌入过程中的生存性问题.提出一种基于节点关联度的双树嵌入保护算法(dual-tree embedding protection based on node correlation degree, DEP-NCD).
1 问题描述 1.1 虚拟光多播请求通过采用多播[17]的传输模式, 所有目的节点的数据可以同时传输, 并且可以传输到特定的节点.对于多播请求, 要实现一点到多点的通信, 必须要建立一个光树的形式连接一个源节点和所有的目的节点.因此, 本文中的虚拟拓扑的主要形式是虚拟光多播树(virtual optical multicast tree, VOMT)的形式.一个虚拟网络可以描述为GV=(NV, LV), 其中, NV是虚拟节点的集合, LV是虚拟链路的集合, 对于每个虚拟节点, cV表示请求的节点计算资源, bV表示带宽请求.将虚拟光多播请求(virtual optical multicast request, VOMR)表示为R{S, (D1, D2, …, Dn)}，其中S表示源节点, Di表示第i个目的节点, 一个多播数据从源节点传输到多个目的节点.图 1所示为一个拥有4个节点和3条链路的虚拟光多播树, 其中虚拟节点A表示源节点, 虚拟节点C和D表示目的节点.在虚拟节点方框内的数字表示这个节点的计算资源.
|
图 1 虚拟光多播树 Fig.1 The virtual optical multicast-tree |
底层网络用一个带权无向图表示为GS=(NS, LS), 其中NS表示底层节点的集合, LS表示底层光纤链路的集合.每个底层节点有一定的计算资源支持虚拟节点的映射, 用cS表示, 每条光纤链路的可用频谱时隙表示为bS.图 2给出了一个底层物理网络拓扑的例子, 底层节点(a—g)附近方框内的数字表示该节点可用的计算资源, 每个底层链路上面的小格表示该链路频谱资源的使用情况.
|
图 2 底层弹性光网络 Fig.2 The substrate elastic optical network |
保护机制主要思想是建立一个备份的系统.当服务器或者路由器因为出现故障而中断时, 受故障影响的原有系统的工作链路或节点, 此时将系统切换到备份系统, 保证请求的正常传输.
如图 3所示, 工作路径为A—B—C—D, 为其设置一条保护路径A—G—H—D, 如果映射过程出现链路故障, 就会出现映射失败的情况, 路径A—B—C—D出现故障, 会出现网络服务停止.此时, 将请求转移到保护路径A—G—H—D上传输, 切换时间很短, 不会影响用户的使用.
|
图 3 保护路径和工作路径 Fig.3 The protection path and working path |
本文所提出的启发式算法是针对以上嵌入完成后底层资源可能存在故障这一问题提出的, 在进行虚拟光多播树嵌入的时候, 根据各虚拟节点的关联度进行嵌入.
2.1 虚拟光多播树的双树嵌入保护算法首先计算虚拟光多播树VOMT中每个虚拟节点的关联度, 将其中的节点分别按关联度递减顺序排列.如果关联度相同, 则优先选择计算资源较大的底层节点.将VOMT中的虚拟节点嵌入到其对应的底层候选节点集合中.同时, 根据VOMT的节点之间的邻居关系, 使用Dijkstra算法寻找最短路径, 将虚拟链路嵌入到对应的底层链路.循环此过程依次将虚拟节点以及之间的虚拟链路映射到底层光网络中.至此, 虚拟光多播树嵌入底层光网络成功.
当被嵌入虚拟链路的底层链路发生中断时, 将虚拟多播请求转移到预先设置的保护链路上进行传输, 其具体的方法为:虚拟光多播树建立保护光树, 对产生的每个虚拟光多播请求建立两棵多播树, 一棵为工作树, 另一棵为保护树, 它们都覆盖多播请求的所有虚拟成员节点.将工作树映射完成后, 从底层网络链路集合中去除已被工作树映射的部分, 将保护树嵌入到底层链路中, 保证保护树和工作树完全链路分离；当映射了工作树的底层弹性光网络的链路发生故障时, 就可以将多播请求转换到保护树上进行传输.DEP-NCD算法见表 1.
|
表 1 DEP-NCD算法 Table 1 DEP-NCD algorithm |
为了详尽说明DEP-NCD算法, 对启发式算法的详细过程做出解释.仍然使用图 1的虚拟光多播树和图 2的底层弹性光网络, 计算各虚拟节点的节点关联度, 可知, 虚拟节点B的关联度为3, 因此在嵌入过程中优先嵌入虚拟节点B.其他的虚拟节点A, C, D的关联度都为1, 要根据A, C, D节点的计算请求资源排序, 得到表 2.
|
|
表 2 虚拟光多播树的节点关联度排序 Table 2 Sorting nodes in virtual optical multicast-tree according to node correlation degrees |
对于每个虚拟节点, 将其对应的底层光网络的候选节点也根据节点关联度排序, 得到表 3.接下来根据节点关联度优先的原则进行虚拟节点和虚拟链路的嵌入.如图 1、图 2所示, 虚拟节点B的候选节点集合Ω(B)={a, b, c, d, e, f, g}, 底层节点a, e的关联度为4, 剩余的节点关联度为3或者2, 选择节点关联度大的a, e, 再选择两者中节点计算资源较大的.因此选定虚拟节点B嵌入的底层节点为a.类似地, 将虚拟节点A嵌入到关联度较大的底层节点e, 因为在虚拟光多播树中, 节点A是节点B的邻居, 在底层光网络中, 找到对应的底层光链路e—a.C嵌入到底层计算资源较大的节点g, 同样, 因为C是B的邻居, 将B—C嵌入到a—g.最后, 虚拟节点D嵌入到d, B—D嵌入到光链路a—d.
|
|
表 3 候选底层节点的关联度排序 Table 3 Sorting the node correlation degrees of candidate substrate nodes |
如图 4所示, 当虚拟光多播树使用节点关联度优先的方法嵌入到底层网络中后, 即将虚拟节点A, B, C, D分别映射到底层节点e, a, g, d上, 将虚拟链路A—B, B—C, B—D分别映射到底层链路a—e, a—g, a—d上, 作为工作树, 如图 4中虚线的部分为工作树.然后去除掉底层网络中已经映射了虚拟链路的底层链路 a—e, a—g, a—d, 在图中设置为灰色.保护算法需要预先设置保护路由, 将虚拟光多播树仍然使用节点关联度优先的方法嵌入到底层网络中, 如图 5所示, 将虚拟节点A, B, C, D分别映射到底层节点g, e, f, d上, 将虚拟链路a—b, b—c, b—d分别映射到底层链路g—e, e—f, e—d上, 作为备份链路, 如图 5中虚线的部分为保护树.当工作链路a—e发生故障中断的时候, 见图 6, 多播请求转移到保护树上传输, 其中实线所指为传输路径.
|
图 4 底层弹性光网络中工作树 Fig.4 The work tree in substrate elastic optical networks |
|
图 5 底层弹性光网络中保护树 Fig.5 The protection tree in substrate elastic optical networks |
|
图 6 故障转移图 Fig.6 Fault transfer graph |
在仿真实验中, 使用20个节点32条链路的ARPANet网络作为底层光网络拓扑, 如图 7所示.虚拟多播请求使虚拟请求的节点数量为[4, 14], 每个请求的虚拟链路所占用的频谱时隙的数量是[5, 25], 每个频谱的带宽为12.5 GHz.在实验过程中, 本文还使用了传统的虚拟网络嵌入DEP算法[18]用于对比.
|
图 7 ARPANet网络 Fig.7 ARPANet network |
实验首先测试了DEP-NCD算法和DEP算法在底层弹性光网络ARPANet上的嵌入成本, 嵌入成本就是底层链路中的频隙.从图 8a可以看出, 当通信网络负载为90爱尔兰时, 嵌入成本非常小, 大约150个频隙.当网络负载增加到120爱尔兰时, DEP-NCD算法优于一般的嵌入算法DEP, 两者之间的差距也在增大.同时, 随着虚拟节点数量m的增加, 嵌入成本也随之增加.DEP-NCD算法能够为具有高关联度的节点提供最高优先级.在相同条件下, 可以观察到DEP-NCD算法可以降低嵌入成本并减少资源的浪费.
|
图 8 嵌入成本比较 Fig.8 Comparison of the embedding costs (a)—不同虚拟节点数量；(b)—业务占不同频隙数量. |
如图 8b所示, 底层网络中单个频隙的带宽为12.5 GHz, 每个带宽的平均频隙数量n为5到15.可以看出, 随着网络负载的增加, 提出的DEP-NCD启发式算法在嵌入成本方面优于传统的嵌入算法DEP, 说明最短路径优先算法有效地找到了底层弹性光网络中的最短链路, 并且必须通过选择最短的底层链路来最小化嵌入成本.因为嵌入成本也与虚拟链路的带宽资源有关.当虚拟链路嵌入到底层链路上的时候, 需要为虚拟光多播请求的每个虚拟光链路分配相同数量的频隙.虚拟光链路的带宽请求越大, 对应的嵌入成本越大.
如图 9a所示, 随着虚拟节点数量的增加, DEP算法与DEP-NCD算法之间的差距十分明显.这可以解释为:当虚拟节点数量增加时, DEP-NCD算法映射更具选择性并且优先级更高.因此, 该算法几乎不在底层弹性光网络上传输冗余请求.当DEP算法根据计算资源进行映射时, 与计算资源值大的节点相关联的链路数量不一定很多, 因为虚拟光多播树是随机生成的.在嵌入之后, 将有许多虚拟链路在底层弹性光网络上进行多播请求的冗余传输, 极大地浪费资源.因此, DEP-NCD算法可以有效地映射虚拟光多播请求, 并且在底层网络中几乎不存在冗余的多播请求的传输.图 9b显示, 即使虚拟光多播树的平均频隙增加, 但DEP-NCD算法中的底层网络的冗余成本始终为0, 这意味着底层网络上的冗余多播请求传输很少.因此, DEP-NCD算法可以有效地减少冗余嵌入.
|
图 9 冗余成本比较 Fig.9 Comparison of the redundancy costs (a)—不同虚拟节点数量；(b)—业务占不同频隙数量. |
从图 10a可知, 工作链路与保护链路相比, 路由器的跳数有一些变化, 这是因为设置的工作路由一般选择嵌入的链路都是按照最短路径优先的原则进行嵌入的, 但是保护链路的选择是在剩余的底层物理资源中尽量选择最优的路径.总体来看DEP-NCD算法在故障前后的路由器跳数基本不变.但是DEP算法的路由器跳数大概率会增加, 因为DEP算法在嵌入的时候不考虑节点链接链路的情况, 设置保护链路的时候, 经过的路由器的跳数会比工作链路的更多.
|
图 10 路由器跳数比较 Fig.10 Comparison of router hops (a)—不同虚拟节点数量；(b)—业务占不同频隙数量. |
从图 10b可知，在频隙相同的情况下, 比较工作链路和保护链路的路由跳数, 保护链路的跳数会更多；这是因为在设置保护树的时候, 是将已经嵌入工作树的链路从底层网络中去除, 在剩余的底层网络中寻找保护树, 这时的被嵌入保护树的链路可能不是最优的.不管是工作链路还是保护链路, DEP算法的路由器跳数均大于DEP-NCD算法的路由器跳数.
在图 11中, 对于加了保护的系统, 请求接受率在5 000 s时很高, 但是下降也很快, 这是因为刚开始的时候对于虚拟光多播请求, 有充足的底层资源.当这些虚拟光多播请求在系统中足够多的时候, 即大约在10 000 s之后, 接受率保持一致.而相比于未加保护的系统, 请求接受率总是低于加了保护的系统, 这是因为在发生链路中断的时候, 有保护的系统可以直接将多播请求转移到保护链路上, 保证请求的接受率.图 11也表明一般的嵌入算法DEP在加了保护之后虽然接受率也很高, 但是仍然低于相对应的启发式算法, 很大一部分原因是传统的嵌入算法占用太多的底层资源, 有的链路不能设置专门的保护链路.同时, 随着时间的增加, 所有请求的接受率都在下降, 这是因为底层资源在一直减少, 能够嵌入成功的请求也随之减少.
|
图 11 请求接受率的比较 Fig.11 Comparison of acceptance rates of requests |
本文提出的启发式算法DEP-NCD在嵌入的过程中, 从底层网络来看, 占用的成本要小于DEP算法, 几乎没有冗余资源产生.同时, 使用DEP-NCD算法之后, 发生故障时有了双树的保护，路由器跳数基本不变, 并且加了保护的请求接受率明显高于未加保护的请求, 在发生故障时能够快速恢复, 节约了请求的时间和资源.
| [1] |
Lin R, Luo S, Zhou J, et al. Virtual network embedding with adaptive modulation in flexi-grid networks[J]. Journal of Lightwave Technology, 2017, 36(17): 3551-3563. |
| [2] |
Zhu M, Zhang S Y, Sun Q, et al. Fragmentation-aware VONE in elastic optical networks[J]. Journal of Optical Communications and Networking, 2018, 10(9): 809-822. DOI:10.1364/JOCN.10.000809 |
| [3] |
Fischer A, Botero J F, Beck M T, et al. Virtual network embedding:a survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(4): 1888-1906. |
| [4] |
Panayiotou T, Chatzis S P, Ellinas G. Performance analysis of a data-driven quality-of-transmission decision approach on a dynamic multicast-capable metro optical network[J]. Journal of Optical Communications and Networking, 2017, 9(1): 98-108. |
| [5] |
Gao X, Ye Z, Fan J, et al. Virtual network mapping for multicast services with max-min fairness of reliability[J]. Journal of Optical Communications and Networking, 2015, 7(9): 942-951. DOI:10.1364/JOCN.7.000942 |
| [6] |
Guler E, Zheng D, Luo G, et al.Embedding virtual multicast trees in software-defined networks[C]//2017 IEEE International Conference on Communications(ICC).Paris: IEEE, 2017: 1-6.
|
| [7] |
Saridis G M, Peng S, Yan Y, et al. Lightness:a function-virtualizable software defined data center network with all-optical circuit/packet switching[J]. Journal of Lightwave Technology, 2016, 34(7): 1618-1627. DOI:10.1109/JLT.2015.2509476 |
| [8] |
Gao X, Zhong W, Ye Z, et al.Virtual network mapping for reliable multicast services with max-min fairness[C]//2015 IEEE Global Communications Conference(GLOBECOM).San Diego: IEEE, 2015: 1-6.
|
| [9] |
Zhang M, Wu C, Jiang M, et al.Mapping multicast service-oriented virtual networks with delay and delay variation constraints[C]//2010 IEEE Global Communications Conference(GLOBECOM).Miami: IEEE, 2010: 1-5.
|
| [10] |
Guler E, Zheng D, Luo G, et al.Virtual multicast tree embedding over elastic optical networks[C]//2017 IEEE Global Communications Conference(GLOBECOM).Singapore: IEEE, 2017: 1-6.
|
| [11] |
Jarray A, Song Y H, Karmouch A.P-cycle-based node failure protection for survivable virtual network embedding[C]//2013 IFIP Networking Conference.New York: IEEE, 2013: 1-9.
|
| [12] |
Miao Y, Yang Q, Wu C, et al. Multicast virtual network mapping for supporting multiple description coding-based video applications[J]. Computer Networks, 2013, 57(4): 990-1002. DOI:10.1016/j.comnet.2012.11.013 |
| [13] |
Liao D, Sun G, Anand V, et al. Survivable provisioning for multicast service oriented virtual network requests in cloud-based data centers[J]. Optical Switching and Networking, 2014, 14: 260-273. DOI:10.1016/j.osn.2014.05.019 |
| [14] |
Doucette J, Giese P A, Grover W D.Combined node and span protection strategies with node-encircling p-cycles[C]//2005 Design of Reliable Communication Networks.Ischia, 2005: 1-9.
|
| [15] |
Shahriar N, Taeb S, Chowdhury S R, et al.Achieving a fully-flexible virtual network embedding in elastic optical networks[C]//IEEE INFOCOM 2019—IEEE Conference on Computer Communications.Paris: IEEE, 2019: 1756-1764.
|
| [16] |
Casellas R, Giorgetti A, Morro R, et al. Virtualization of disaggregated optical networks with open data models in support of network slicing[J]. Journal of Optical Communications and Networking, 2020, 12(2): A144-A154. |
| [17] |
林慕清, 徐剑, 刘泽超, 等. Ad Hoc中基于双线性对和证书的组密钥管理协议[J]. 东北大学学报(自然科学版), 2012, 33(10): 1407-1410. (Lin Mu-qing, Xu Jian, Liu Ze-chao, et al. Group key management protocol based on bilinear pairing and certificate in Ad Hoc network[J]. Journal of Northeastern University(Natural Science), 2012, 33(10): 1407-1410. DOI:10.12068/j.issn.1005-3026.2012.10.010) |
| [18] |
Chu Y H, Rao S G, Seshan S, et al. A case for end system multicast[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1456-1471. DOI:10.1109/JSAC.2002.803066 |