New SRLG-diverse path selection algorithm in survivable GMPLS networks

In conventional shared risk link group (SRLG)-diverse path selection (CSPS) algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection method is the same as the algorithms without SRLG constraint. A problem of CSPS algorithm is that, after a primary path is selected, the success probability to select an SRLG-diverse backup path for it is low. If SRLG is taken into account when computing the primary path, then the probability to successfully select an SRLG-diverse backup path will be much increased. Based on this idea, an active SRLG-diverse path selection (ASPS) algorithm is proposed. To actively avoid selecting those SRLG links, when computing the primary path, a link that share risk with more links is assigned a larger link cost. To improve the resource utilization ratio, it is permitted that the bandwidth resources are shared among backup paths. What is more, differentiated reliability (DiR) requirements of different customers are considered in ASPS algorithm. The simulation results show that, compared with CSPS algorithm, ASPS algorithm not only increases successful protection probability but also improves resource utilization ratio.     

Integrated dynamic shared protection algorithm for GMPLS networks

The path protection approach is widely investigated as a survivability solution for GMPLS networks, which has the advantage of efficient capacity utilization. However, there is a problem of the path protection approach that searching a disjoint backup path for a primary path is often unsuccessful. In order to resolve this problem, an integrated dynamic shared protection （IDSP） algorithm is proposed. The main idea of the proposed algorithm is that the path protection approach is first used to establish a backup path for the primary path; if the establishment is unsuccessful, then the primary path is dynamically divided into segments whose hop count are not fixed but not more than the limitation calculated by the equations introduced. In this proposal, backup bandwidth sharing is allowed to improve the capacity utilization ratio, which makes the link cost function quite different from previous ones. Simulation experiments are presented to demonstrate the efficiency of the proposed method compared with previous methods. Numerical results show that IDSP can not only achieve low protection failure probability but can also gain a better tradeoff between the protection overbuild and the average recovery time.     

可靠性与拓扑感知的服务功能链备份保护方法

在网络功能虚拟化环境中, 针对服务功能链部署时的可靠性研究存在资源利用率较低的问题, 提出一种可靠性与拓扑感知的服务功能链备份保护方法。首先, 利用最小费用最大流算法将服务功能链请求中的虚拟网络功能部署在可靠性较高的服务器节点上, 尽可能提高服务功能链的可靠性。其次, 针对未能达到可靠性需求的服务功能链, 通过为部署在可靠性较低服务器节点上的虚拟网络功能预留备份资源的方式提高其可靠性。最后, 通过备份资源共享的方式尽可能减少备份资源消耗。仿真结果表明,该方法提高了可靠部署成功率和资源利用率。     

面向SDN的生存性虚拟网络映射算法

针对软件定义网络环境下生存性虚拟网络映射问题,提出了基于网络资源关键度的虚拟网络可靠性映射算法。该算法首先通过提出底层网络资源和拓扑重要度度量方式,构建资源关键度排序集合,同时备份控制网络,考虑到控制器位置部署,设置链路时延权重进行最短物理路径的选取,映射时依据位置约束进行虚网映射,在此基础上针对不同物理网络故障类型采用备份切换和可行迁移方式进行恢复,确保虚拟网络服务连续不间断。仿真结果表明,与以往算法相比,该算法在请求接受率、故障恢复率、底层网络整体负载均衡度以及平均控制延迟4个指标上具有更好的网络性能。     

基于二分图最优匹配的虚拟网络映射算法

针对现有虚拟网络映射存在开销较大、资源利用不够合理的问题,提出了一种基于二分图最优匹配的虚拟网络映射算法。首先以虚拟节点和物理节点为顶点构建二分图,将节点映射问题转化为二分图最优匹配问题;其次将节点资源评价最高的物理节点与节点需求评价最高的虚拟节点优先匹配,并利用Kuhn-Munkres算法求解二分图最优匹配,依据匹配结果进行节点映射;最后利用 k-最短路径算法实现链路映射。实验表明,与以往的映射算法相比,提出的映射算法在保持较高映射成功率的同时,提高了长期收益开销比,且资源利用更加合理。     

动态优先级下防空相控阵雷达在线交错调度算法

针对防空相控阵雷达中时间资源分配主观性强、利用率低的问题,结合任务内部结构,提出一种新的在线交错调度算法。该算法在将任务的重要性和紧急性均置于动态优先级的基础上,使得雷达任务收、发波束之间的等待期可以用来执行其他波束的发射期或接收期。仿真结果表明,相比于原有的动态优先级算法,所提算法的调度成功率提升了25%,时间利用率提升了35%,执行威胁率提升了25%。     

基于GPU的大规模多阶段任务系统可靠性并行计算方法

针对大规模多阶段任务系统(phased-mission system, PMS)的可靠性求解,引入并行计算思想,通过分析传统的一致化方法(uniformization method, UM),基于Nvidia提出的CUDA(compute unified device architecture)架构,实现了基于图形处理器(graphics processing unit, GPU)的UM并行算法(GPU-UM),并采用合并访问和共享内存技术,提高了GPU中数据负载的利用率;PMS中不同阶段参与任务的设备及其数量通常会发生变化,导致阶段间依赖性处理困难。通过对新设备加入、已有设备暂时退出任务或完全退出任务等3种基本情况的分析,提出了阶段间状态映射机制,实际中的阶段变化情况更加复杂,可综合上述3种基本情况进行处理。通过算例对比了GPU-UM、CUDA-UM、传统UM和Krylov子空间等4种算法的计算时间和可靠性结果,分析表明GPU-UM算法的计算耗时优于其他方法,且结果精度也能满足可靠性计算需求;同时,通过对比分析UM算法和Krylov子空间算法与仿真方法的结果误差,表明提出的阶段间映射机制能够正确处理PMS中阶段间的复杂依赖关系。     

基于混合遗传-粒子群算法的相控阵雷达调度方法

针对相控阵雷达中的任务调度问题,提出一种融合了粒子群算法、遗传算法和启发式交错调度算法的混合算法。采用混沌理论优化粒子群算法的飞行参数,设计递减的动态惯性权重,以及引入遗传算法中的交叉、变异操作,使得算法能够快速收敛,并跳出局部最优实现全局最优。在智能算法的框架下,提出一种启发式的任务交错算法,使得雷达任务中等待期的时间资源进一步得到利用。仿真结果表明,相比于遗传算法,所提算法的收敛速度更快,结果更优;相比于传统的启发式算法,所提算法的调度成功率提升了42%,时间利用率提升了40%,实现价值率提升了33%,时间偏移率减少了73%。     

基于产品回收定价的逆向物流车辆路径优化问题

针对逆向物流车辆路径优化问题,研究在产品回收定价调整和车辆路径优化调度结合方面存在的不足,以智能回收箱为研究对象,考虑多频次回收和车辆共享调度策略,提出基于产品回收定价的逆向物流车辆路径优化方案。首先构建了智能回收箱回收量与回收定价的线性函数,然后构建了包含共享车辆运输成本、维护成本、违反时间窗惩罚成本和环境外部性收益之和最小化的逆向物流回收运营成本模型,并建立了回收中心产品的最大化收益模型。其次,根据模型特点设计了考虑智能回收箱地理位置、回收频次和回收时间窗的K-means时空聚类算法,进而提出一种改进的GA-PSO混合算法。该混合算法结合了遗传算法全局搜索能力强与粒子群算法收敛速度快的特点进行了算法间的优势互补,同时采用了精英保留策略,增强了混合算法的搜索性能,并通过与HGA、GA-TS和HACO等算法进行比较分析,验证了模型和算法的有效性。最后,结合重庆市某智能回收物流网络的实际数据进行优化研究,分析了不同产品定价下的回收频次和车辆共享调度情况。结果表明,本文所提出的模型和算法能够进行产品回收定价策略的有效选择、产品回收车辆的资源共享以及合理的车辆路径优化调度,并可在回收中心获得...     

移动自组织网络中自适应分段路径保护机制

节点稀疏情况下,源节点无法建立完备的保护路径,端到端连接的可靠性降低。提出了一种适合于动态网络拓扑的自适应分段路径保护机制,该机制把端到端路径分成多个较短的段,并按照当前拓扑情况为其建立保护路径,以提高端到端路径的可靠性。仿真结果表明,通过适当的额外数据包开销所得到的分组投递率、端到端时延和路由发现次数都比传统路径保护机制有明显改善。     

多功能相控阵雷达实时驻留的自适应调度算法

灵活有效的调度算法是实现多功能相控阵雷达工作性能优化和资源合理利用的基础。从调度代价的角度建立了实时驻留调度的数学模型,提出一种求解次优调度序列的自适应算法。该算法利用任务自身工作方式属性及任务中所含目标的先验信息分配任务的综合优先级,采用一步回溯的策略来确定每个驻留任务的调度属性,利用二次规划获取其最佳执行时间,并与传统的基于优先级调度算法进行了比较。仿真结果表明,提出的自适应调度算法提高了任务调度成功率,降低了截止期错失率。     

安全虚拟网络映射的启发式算法

针对安全虚拟网络映射过程中虚拟节点与物理节点之间匹配不合理,导致映射开销大、请求接受率低等问题,将安全虚拟网络映射过程建模为多目标混合整数线性规划模型,并提出了基于节点多属性综合评估与路径优化的安全虚拟网络映射算法。该算法在节点映射过程中,以节点的资源丰富度、安全属性和拓扑邻近性为考核对象,通过建立节点映射函数将虚拟节点映射至最佳的物理节点;在链路映射过程中,以可用带宽和路径跳数为考核对象,通过建立路径映射函数将虚拟链路映射至最佳的物理路径。实验表明,该算法在满足虚拟网络映射请求的安全需求的条件下,在虚拟网络请求接受率、映射收益和映射开销等方面优于现有的算法。     

基于流量优化的可靠服务功能链部署方法

针对网络功能虚拟化环境中服务功能链部署的资源开销问题, 提出一种基于流量优化的可靠服务功能链部署方法。首先, 根据虚拟链路流量变化对虚拟网络功能进行聚合, 使带宽需求大的虚拟链路部署到底层网络后, 其流量变为服务器的内部流量。其次, 综合考虑可靠性、综合时延以及拓扑属性, 利用离差最大化的多指标决策算法对物理节点进行评价, 并使用链路约束降低流量的乒乓效应。最后, 采用k-最短路径算法将虚拟链路部署到满足带宽需求的物理链路上。仿真实验表明, 所提方法在保证服务功能链可靠性的基础上, 对长期收益开销比、映射成功率、端到端时延以及带宽开销有较大优化。     

基于MST的拓扑感知度约束覆盖网构建算法

覆盖网能有效分离网络应用与底层网络基础设施,提升服务质量(quality of service, QoS)和用户体验(quality of users’ experience, QoE)。设计了一种普适性较强的覆盖网拓扑构建算法--基于最小生成树（minimum spanning tree, MST）的拓扑感知度约束(minimum spanning-tree based topology-aware degree bound, MST-TADB）覆盖网构建算法。该方法感知网络拓扑,逐步生成MST,同时参考节点的转发和计算能力作为节点度约束收敛算法。由仿真结果可知,和同类算法相比,本文方法的故障恢复率、恢复路径跳数惩罚、服务节点平均节点度和时间复杂度综合权衡较好,并保证了所构建的覆盖网的自愈性。     

面向异构分布式计算环境的并行任务调度优化方法

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是NP(non deterministic polynomial)完全问题。首先给出了异构分布式计算系统的形式化描述,建立了静态任务调度问题的理论体系,通过分析总结最长动态关键路径(longest dynamic critical path,LDCP)算法的核心思想及存在的不足,提出一种运用结点信息流量减少CPU空闲时间碎片的并行任务调度优化算法,其时间复杂度为O(M×N3)。实验表明改进后的算法在调度长度、加速比及计算效率3个指标上均优于LDCP算法和分层结点排序算法(sorted nodes in leveled directed acyclic graph division,SNLDD),其中,与LDCP、SNLDD相比,调度长度平均缩短19.03%、8.02%,加速比平均提升18.42%、7.96%,计算效率平均提高10.17%、3.72%,进一步提高了并行系统的资源利用率。     

GO-FLOW方法及其改进的精确算法

GO FLOW方法是一种有效的系统可靠性分析方法,直接进行系统可靠性定量计算是GO FLOW方法的优点。但对于包含共有信号的复杂系统,不能直接按GO FLOW方法提供的算法计算,必须保留共有信号项并对其进行修正才能得到精确的计算结果。给出对共有信号进行修正的计算公式推导过程,提出了有共有信号的复杂系统中GO FLOW新的定量精确算法,并用算例加以说明和验证。算例结果表明该方法是精确而有效的。     

面向软件定义航空集群机载网络的更新策略

软件定义网络（software-defined networking，SDN）的出现为突破机载网络在航空集群作战应用背景下存在的性能瓶颈提供了全新的思路。针对航空集群机载网络的更新问题，提出适用于软件定义架构下航空集群机载网络的更新策略——可靠性增强的两阶段提交更新策略（reliability-enhenced two-phase commit，RE-TPC）。首先设计最高可靠性算法以及多路径算法搜索下发指令消息的高可靠路径。然后引入基于ACK（acknowledge）消息的确认机制和ACK消息高效融合传输机制，进一步提升网络更新过程的可靠性和实时性。仿真结果表明，与已有经典网络更新策略相比，所提更新策略能够有效提高更新的可靠性，同时更新持续时间更低、开销更小。     

基于深度强化学习的卫星光网络波长路由算法

针对由卫星光网络拓扑动态变化、业务多样化和负载不均引起的路由收敛慢和波长利用率低的问题, 提出了一种基于深度强化学习的卫星光网络波长路由分配方法。基于软件定义中轨/低轨(medium earth orbit/low earth orbit, MEO/LEO)双层卫星网络架构, 利用深度强化学习算法动态感知网络当前的业务负载和链路状况, 构造基于时延、波长利用率和丢包率的奖励函数进行选路决策。为了解决单跳链路对整个光路的影响, 引入链路瓶颈因子, 搜索符合服务质量(quality of service, QoS)约束的最优路径。研究结果表明, 与传统卫星网络分布式路由(satellite network distributed routing algorithm, SDRA)算法和Q-routing算法相比, 所提算法降低了网络的时延、丢包率, 提高了波长利用率, 同时也降低了高优先级业务的阻塞率。     

Bandwidth constrained QoS routing scheme for MPLS traffic engineering

Traffic engineering has been essential to optimize the utilization of network resource and to provide for QoS,QoS routing is a basic component of traffic engineering in MPLS networks. Aiming at some shortages of certain existing routing algorithms, we propose an efficient bandwidth constrained QoS routing scheme with additional traffic engineering objectives. The objectives of traffic engineering considered in our algorithm are to reduce the blocking probability of requests and to evenly distribute the traffic load. Accordingly, the algorithm avoids using critical links as far as possible by assigning large weights to them as a function of their criticality. The critical links can be specified according to max-flow reduction weight, a new link weight introduced by the algorithm. Then, a new defined additive metric, path saturation,is used to select optimal path. Extensive simulations are carried out to evaluate the performance of the proposed algorithm in terms of call blocking probability and link resource utilization. Compared to other several routing algorithms, the simulation results show the new algorithm performs well.     

基于位置感知的大规模LEO星座分布式路由算法

针对传统星座路由算法应用在大规模低地球轨道(low earth orbit, LEO)星座中, 存在鲁棒性差、资源开销大、路由效率低等缺点。根据卫星运行时的位置可预测特性, 提出了基于位置感知的分布式路由算法。考虑卫星资源受限, 大规模LEO星座具有卫星节点多、动态性大等特点, 基于位置感知提出一种路径预选机制, 初步确定数据包的传输路径。在此基础上, 考虑业务服务质量(quality of service, QoS)需求, 基于状态和传播矢量函数提出一种路径收敛机制, 无重合确定数据包传输主路径和备用路径。理论和仿真结果证明, 相比于传统路由算法, 所提算法降低了路由存储和开销, 随着中断概率的增大, 提高了星座的吞吐量, 降低了端到端时延。