基于拓扑感知的虚网映射算法框架（英文）

The virtual network embedding/mapping problem is an important issue in network virtualization in Software-Defined Networking(SDN).It is mainly concerned with mapping virtual network requests,which could be a set of SDN flows,onto a shared substrate network automatically and efficiently.Previous researches mainly focus on developing heuristic algorithms for general topology virtual network.In practice however,the virtual network is usually generated with specific topology for specific purpose.Thus,it is a challenge to optimize the heuristic algorithms with these topology information.In order to deal with this problem,we propose a topology-cognitive algorithm framework,which is composed of a guiding principle for topology algorithm developing and a compound algorithm.The compound algorithm is composed of several subalgorithms,which are optimized for specific topologies.We develop star,tree,and ring topology algorithms as examples,other subalgorithms can be easily achieved following the same framework.The simulation results show that the topology-cognitive algorithm framework is effective in developing new topology algorithms,and the developed compound algorithm greatly enhances the performance of the Revenue/Cost(R/C) ratio and the Runtime than traditional heuristic algorithms for multi-topology virtual network embedding problem.     

Routing optimization based on topology control in satellite network

A new double-layer satellite network model for space networking was established and a routing algorithm based on topology control (TCRA) was proposed considering the advantages of low earth orbit and stationary earth orbit satellite networks.This model used virtual node strategy and satellite grouping idea,which regarded the coverage area of each low earth orbit satellite as a virtual node.The network took into account the influence of the polar area on the division of the satellite footprints,such that the upper management satellites can accurately acquire the topology of the lower satellites.Using the improved virtual node strategy,the time slices were superior to other network models in quantity,length and other aspects.Based on the network topology,stationary earth orbit satellites calculate routing for low earth orbit satellites,while low earth orbit satellites were responsible for forwarding data.The simulation results show that the routing algorithm is superior to other algorithms in average end-to-end delay and packet loss rate.     

保证航电波分复用网络实时性的虚拓扑设计

针对航空电子波分复用网络消息的实时性要求,对航空电子网络的结构进行了研究,分析了在该网络中造成消息延迟的主要因素为转发延迟。进而对航空电子网络建模,根据WDM网络的资源特性进行拓扑的约束,提出了基于综合考虑虚拓扑跳数以及消息的带宽保证为目标的线性规划算法,在此基础上给出了大型网络的一个启发式算法,采用该线性规划算法对NSFNet网络拓扑进行了仿真验证。仿真结果表明,综合考虑虚拓扑跳数和消息带宽能减少消息的延迟,保证了网络实时性。     

基于滑动区域的粒子群虚拟网节能映射算法

针对传统虚拟网节能映射中存在的节点映射分散、链路映射跳数多等问题,利用虚拟网请求的最小生成树拓扑将节点和链路同时映射,该文提出了基于滑动区域的粒子群虚拟网节能映射算法(EVNE_SRPS)。当一个虚拟网请求到达时,生成其最小生成树拓扑,根节点为路径和最短的节点;在底层网络随机选取多个区域作为粒子对象,并在区域中心映射虚拟网请求的最小生成树拓扑;计算粒子的适应度,求出群体和个体最优解,并在最优解的指导下确定滑动方向、更新区域位置,经过迭代后得到虚拟网的映射方案。实验结果表明,与现有算法相比,该算法降低了网络能耗,提高了运营商的收益成本比。     

基于链路可靠性的无线虚拟网络分配方法

针对无线网络链路可靠性差影响无线虚拟网络的分配这一问题,提出了一种基于链路可靠性的无线虚拟网络分配算法（WVNEA-LR）。该算法通过物理网络拓扑预处理和允许同一个虚拟请求中的多个虚拟节点映射到同一个物理节点上的方法,提高了Vn构建成功率和节约了物理链路资源。利用Q因子改善了因拓扑分配稀疏时Vn构建成功率低的问题。此外,WVNEA-LR的节点分配为链路分配作了准备,并通过选择可靠性高的承载路径保证了分配后的Vn具有高可靠性。仿真结果表明, WVNEA-LR获得较好的虚拟网络构建成功率、较高的收益成本比和资源利用率。     

基于资源区域聚集度的虚拟网映射算法

虚拟网映射是网络虚拟化研究中亟待解决的问题,针对已有映射算法中存在的对于网络拓扑信息利用不足的现状,该文提出了基于资源区域聚集度的虚拟网映射算法(RCI-VNE)。在映射预处理阶段,根据局部拓扑信息和区域资源聚集度提出节点区域资源聚集评价算法。在节点映射阶段,提出一种基于节点区域资源聚集排名的2-近邻聚集映射算法,该算法将虚拟网节点集中映射到底层网络中可用资源丰富的区域,减小承载链路的长度。实验结果表明,该算法降低了虚拟网映射开销,且具有较高的虚拟网请求接受率和较低的平均执行时间。     

Green optical backbone networks: virtual topology adaptation using a page rank‐based rating system

An energy‐aware virtual topology rating system is proposed in this work, which can be utilized as a tool during the virtual topology reconfiguration procedure in an optical backbone network in order to reduce its energy consumption. It is well known that maintaining a static virtual topology in Internet Protocol (IP)‐over‐Wavelength Division Multiplexing (WDM) networks is not energy‐efficient. To that end, virtual topology adaptation algorithms have been developed to adjust the virtual topology to the constantly fluctuating traffic load. While these algorithms achieve significant energy savings, further reduction on the total network energy consumption can be achieved through the proposed rating system. The proposed rating system is a modified version of the page rank algorithm, which ranks websites in the Internet based on their importance. The proposed rating system attributes ratings to lightpaths, which indicate the relative significance of a lightpath in the virtual topology in terms of energy consumption. The rating can be used during the routing procedure as an energy efficiency indicator, in order to increase the number of lightpaths that are deactivated from the reconfiguration mechanism and increase the utilization per lightpath. The proposed reconfiguration scheme (page rank‐based virtual topology reconfiguration) achieves up to 12% additional energy savings in comparison to an existing virtual topology reconfiguration algorithm at the cost of slightly increased average hop distance. Copyright © 2015 John Wiley & Sons, Ltd.     

Efficient distributed address assignment algorithm based on topology maintenance in ZigBee networks

Adopting the borrowed address algorithm can decrease the orphan nodes in ZigBee networks that use distributed address assignment mechanism （DAAM）. The existing borrowed address algorithms can increase the success rate of address assignment, but they have defects such as greater cost of overhead and time in founding network caused by breaking topology. To solve such problems, we propose an more efficient distributed borrowed address assignment algorithm based on topology maintenance （A2BTM） that has a topology maintenance function. It borrows address firstly from the offspring nodes in the same branch for the orphan nodes and replies distributed the request of the borrowed address message immediately, to maintain the network topology and decrease the overhead and time spent on the mechanism of borrowed address. Theoretical and simulation analyses manifest that AZBTM algorithm outperforms DAAM and its improved algorithms in terms of the overhead and time spent in founding network, on the premise of keeping a higher success rate of address assignment. Furthermore, A2BTM can lessen the influence from detour phenomenon efficiently.     

基于约束路由的绿色虚拟拓扑设计算法

摘 要：针对Internet核心网日益严重的能耗问题,建立了绿色虚拟拓扑设计(GVTD)问题的形式化模型,通过业务汇聚、按需配置网络资源、动态虚拟拓扑设计和多粒度睡眠机制降低网络能耗。提出了一种基于约束路由的启发式算法——CBR-GVTD算法,利用单跳路由和多跳路由相结合的方法构建网络虚拟拓扑,并通过基于约束的路由实现网络功耗与路由性能的折衷。模拟结果表明,CBR-GVTD算法可在接口平均利用率为80%~90%和最大路由跳数不超过5的条件下,最多可降低62%~90%的网络功耗     

带有能量补给的异构无线传感器网络拓扑控制算法

针对当前算法主要对拓扑构建或拓扑维护单独研究的问题,提出了一种将两个过程组合的拓扑控制算法,可以适应于通信和能量异构的网络。拓扑构建以较少的通信开销构建连通支配集,而拓扑维护由sink节点基于时间、能量或故障机制执行局部或全局修复策略以节约能量。理论分析和仿真实验证实,算法能以较少的时间和通信开销构建拓扑并延长网络生命时间。     

基于拓扑势加权的动态PPI网络复合物挖掘方法

从动态蛋白质相互作用（PPI）网络中挖掘蛋白质复合物是当前复合物挖掘研究的一个热点,但是目前大都采用未加权网络进行聚类分析,由于不能准确地描述网络的拓扑特性,因此其正确率不高.鉴于此,本文提出采用拓扑势场的方法来构造加权网络,网络中的每一个蛋白质都被视作一个物理粒子,在它周围存在一个虚拟的作用场,由此网络中所有蛋白质的相互作用联合形成一个拓扑势场,文中定义了结点间的拓扑势的概念,并以此来构造加权网络,之后采用马尔科夫聚类算法在DIP数据和Krogan数据上进行复合物挖掘.与其它经典算法相比,该方法的precision和f-measure值较高,能更好地识别蛋白质复合物.     

基于拓扑感知的可重构服务承载网动态重构算法

可重构信息通信基础网络通过构建服务承载网的方式为业务提供自适应的承载服务。针对高效利用有限底层资源的问题,提出一种基于资源关键度进行动态映射的服务承载网构建算法。算法将通过节点或链路的最短路径数作为资源关键度的衡量指标,区别对待底层资源;并实时动态感知关键资源的使用状况,依据不同业务需求对服务承载网进行自适应调整。仿真结果表明,算法在构建成功率、收益花费比和资源均衡度等方面均具有良好性能。     

Robust Design of Virtual Topology for WDM Networks under Bandwidth Demand Uncertainties

In this paper, a novel method is proposed to address the problem of designing virtual topology over wavelength division multiplexing （WDM） networks under bandwidth demand uncertainties. And a bandwidth demand model under uncertainties is presented. The optimization goal of virtual topology design is defined as minimizing the maximum value amongp percentiles of the bandwidth demand distribution on all Hght-paths. Correspondingly, we propose a heuristic algorithm called an improved decreasing multi-hop logical topology design algorithm （ID-MLTDA） that involves with a degree of uncertainties to design virtual topology. The proposed algorithm yields better performance than previous algorithms. Additionally, the simplicity and efficiency of the proposed algorithm can be in favor of the feasibility for topology design of large networks.     

一种新的动态流量疏导算法

文章主要研究WDM(波分复用)光网络中动态业务流量疏导的选路算法,提出了基于拓扑融合的动态流量疏导算法。该算法的最大特点在于融合了物理拓扑及其抽象出来的虚拓扑,利用最小权重优先方法进行选路。仿真结果表明,该算法在不增大建路时延的基础上,可以有效提高资源利用率,降低阻塞率,尤其是在高负载情况下,效果显著。     

支持网络编码的认知无线自组网拓扑控制算法

对认知无线自组网中有限的带宽进行研究,提出支持网络编码的拓扑控制算法。算法分为3个阶段：初始拓扑构建阶段,利用最短路径算法为单播业务构建拓扑,利用基于网络编码的最短路径算法为多播业务构建K冗余拓扑;拓扑优化阶段,通过逐条删除满足一定条件的链路优化拓扑;拓扑恢复阶段,针对关键点失效,利用与失效链路不在同一路径簇且开销最小的链路恢复网络连通。仿真结果表明,算法能够提高无线资源复用率,增强网络抗毁性。     

Virtual network construction with K‐shortest path algorithm and optimization problems for robust physical networks

In network virtualization, it has been considered that virtual networks are constructed over a physical network where conventional data transmission services have been utilized. Here, virtual networks have to be constructed while keeping qualities of the conventional services. In this paper, we propose a new virtual network construction in order to construct many virtual networks while keeping the robustness of a physical network by using network resources effectively. The proposed method consists of three processes: K ‐shortest path algorithm and Prim's minimum spanning tree algorithm, path splitting, and path migration. In the proposed method, at first, multiple topologies are designed by using the K ‐shortest path algorithm and the Prim's MST algorithm according to the user's request. After the topology design is completed, an admission control with network robustness of the physical network is performed. Then, if one of the designed topologies can satisfy the construction conditions, a virtual network is constructed and provided with the user. Otherwise, the path splitting and path migration are performed. Here, the path splitting is utilized to design another topology of a virtual network and path migration is used to change the topologies of the virtual networks that have already been constructed. These processes are formulated as optimization problems and those are processed by solving the optimization problems. In numerical examples, we show that our proposed method can construct a higher number of virtual networks while keeping the robustness of a physical network by comparing with the conventional method where only the Kou–Markowsky–Berman algorithm is used. Copyright © 2015 John Wiley & Sons, Ltd.     

Virtual topology reconfiguration on optical WDM networks considering traffic grooming

This paper investigates the virtual topology reconfiguration (VTR) problem of optical WDM networks by taking the traffic grooming factor into consideration. Firstly, by applying a common “divide and conquer” approach, the problem is categorized and handled as two independent sub-problems, triggering policy and the proper algorithm. Secondly, the VTR problem considering traffic grooming is formulated with new variables and constraints by a mixed-integer linear program (MILP). In order to handle the tradeoff between the advantages and disadvantages of VTR, both network resource utilization and network disruption are examined and quantified in terms of measurable parameters. A new multi-objective VTR algorithm called integrated reconfiguration (IR) algorithm is proposed to provide better overall VTR performance. Different from previous studies this newly proposed VTR algorithm combines three main factors (traffic load, traffic grooming ratio and route length of lightpaths) into one single objective and considers them all when reconfiguring. The results of simulations indicate that proposed VTR policy, periodic VTR triggering policy with IR algorithm, achieves performance improvements for overall VTR performance.     

Virtual topology transition sequence problem on WDM networks with dedicated protection

Wavelength-division multiplexing (WDM) technology has emerged as a promising technology for backbone networks. The set of all-optical communication channels (lightpaths) in the optical layer defines the virtual topology for the upper layer applications. Since the traffic demand of upper layer applications fluctuates from time to time, it is required to reconfigure the underlying virtual topology in the optical layer accordingly. However, the reconfiguration for the virtual topology is reluctantly disruptive to the network since some lightpaths should be torn down and some traffic has to be buffered or rerouted during the reconfiguration process. Therefore, it needs to have an efficient transition method to shift the current virtual topology to the new one so as to minimize the effect of the reconfiguration on the upper layer traffic. In this article, the WDM virtual topology transition sequence problem (WVTTSP) which minimizes the average weighted delay (AWD) is studied. Since the WVTTSP is NP-hard, a heuristic solution model is proposed to solve it. Simulation results show that the proposed least weighted distance first (LWDF) method can find the best result and the time spent by it is less than 4 s for a middle-sized network with 100 links and with 30 wavelengths per link.

交换式局域网物理拓扑发现系统的研究与设计

物理拓扑发现对于网络管理及性能分析具有重要的作用。给出生成树协议与地址转发表相结合的到主机的物理拓扑发现算法。并针对大部分网络设备是CISCO产品的网络,提出运用CDP协议和子网内ping技术相结合的开发方法。此方法既提高开发效率又增强了拓扑发现的完整性,为进一步的网络管理提供详细的可视化物理拓扑结构。     

Waveband Grooming based on Layered Auxiliary Graph in multi-domain optical networks

With the number of wavelengths on fibers keeps increasing, the size and the cost of Optical Cross-Connect (OXC) are greatly enhanced and then the control and management of optical switches become more and more complicated. Therefore, the technique called waveband switching is proposed to reduce the size and the cost of OXC; that is, to save the All-Optical (OOO) switching ports in OXC. However, the existing waveband switching algorithms are all limited in single-domain optical networks. Actually, with the scale of optical backbone keeps enlarging, the network is divided to multiple independent domains to perform the hierarchy routing for achieving the scalability. In order to reduce the size and the cost of OXC meanwhile to achieve the scalability in multi-domains, in this paper we propose a new heuristic algorithm called Waveband Grooming with Layered Auxiliary Graph (WGLAG) since the waveband grooming problem is the NP-hard to perform the inter-domain routing based on the virtual topology of multi-domain network and the intra-domain routing based on the physical topology of single-domain network. In intra-domain routing with waveband grooming of each single-domain, we propose the Layered Auxiliary Graph (LAG) that includes one virtual topology layer and multiple waveband-plane layers to compute a single-hop, or multi-hop or hybrid waveband route for each connection request based on the sub-path waveband grooming scheme. Simulation results show that, WGLAG not only can effectively save more switching ports to reduce the cost of OXC but also can obtain lower blocking probability than other algorithm.