基于距离向量深度的多约束路径选择算法

 为各种应用提供不同的服务质量(Quality of Service,QoS)保证是下一代高速网络面临的一个重要难题,而服务质量路由(Quality of Service routing,QoSR)则是其中的一项核心技术.本文针对不精确状态信息下的多约束QoSR问题,建立了一种用于求解此类多约束QoSR问题的临界点模型,提出了一种基于距离向量深度的多约束QoS路径选择算法(MCPSA),该算法以已有的QoS路由预计算算法为基础,设法选择一条能够最大程度适应不精确网络状态信息的路径,理论分析表明该算法具有一定的优势.最后,结合已有的路由预计算算法进行了大量的仿真试验,结果表明MCPSA具有很强的问题求解能力,能够有效克服路由状态信息的不确定性.     

QoS路由度量参数的选择问题研究

具有服务质量保证的QoS路由技术是为具有QoS要求的多媒体等网络业务提供有保证的网络服务的核心要素。QoS路由技术由路由选择算法以及用于反映网络状态的路由度量参数的选择、获取与更新两部分内容组成。正确选取合适的度量参数是减小寻路开销，得到简单、具有扩展性的选路算法并获得满足业务要求的QoS路由的前提与基础。本对QoS路由所需要的度量参数的基本性质、选取方法等问题进行了较全面的分析讨论，并简要介绍了度量信息更新的基本策略。     

模糊QoS路由算法及其性能分析

我们将模糊理论引入QoS路由领域中,提出了模糊QoS路由算法,在只增加相对较少的计算开销的基础上,有效地提高了QoS路由在离网络负载下的路由成功率和对链路信息滞后性的适应性。     

基于链路状态的多约束路由预计算算法

作为下一代高速网络的核心问题之一,多约束的服务质量路由(QoSR)至今尚无有效算法,为此基于线性能量函数设计了预计算算法MEFPA.该算法将每个QoS度量的重要性均匀分成若干个等级,从而在多维QoS度量空间中构造出多个均匀分布的线性能量函数;算法通过能量函数将QoS链路状态转化成单一能量值,再使用Dijkstra算法计算最小能量树,最终产生QoS路由表.文章分析了多约束下的线性能量函数对算法性能的影响,给出了判定多维空间中QoS约束的可行区域和不可行区域的方法,最后基于这些理论为多约束QoSR问题给出了预计算算法.广泛深入的实验结果表明,高可扩展性、高性能、易实现的预计算算法MEFPA是一种值得在下一代网络中考虑的路由算法.     

QoS路由选择:问题与解决方法综述

保证服务质量的QoS路由(Quality of Service Routing)是网络中解决QoS问题的一项关键技术.QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用.度量参数选择问题、寻路问题和路由信息不准确问题是QoS路由中的几个主要研究内容.本文围绕这三个方面,介绍了QoS路由中的主要问题及相关的解决办法,并探讨了今后QoS路由可能的研究方向.     

下一代网络中多约束路由算法述评

随着新业务的不断涌现,对网络QoS的需求也呈现出多样性,未来网络必然需要提供多约束的QoS路由能力.首先介绍了QoS路由及其路由策略和路由信息发布机制,并在对路由中特征值的选择和构成规则进行分析的基础上,着重讨论了当前多约束路由算法几种类型,分析了算法的性能和特点.最后,分析探讨多约束路由未来可能的研究方向.     

竞争型脉冲耦合神经网络及用于多约束QoS路由求解

在脉冲耦合神经网络的基础上提出了竞争型脉冲耦合神经网络模型,分析了该模型用于求解网络最短路由时的脉冲波传播特性,并提出了脉冲波任务的产生、分解和状态转换理论,在模型中实现了脉冲波的多约束传播,成功地应用于网络多约束QoS路由问题的求解,并可得到全局最优解.仿真实验表明,与其他算法相比,该方法的计算迭代次数最少,且减少较多;而且迭代次数只与网络路由图中源点与目的点之间的最优QoS路由长度有关,而与节点数、链路数和网络的分布构成复杂性无关,体现出较好的计算性能和优势.     

具不确定信息的延迟受限QoS路由研究

QoS路由的目的是找到一条或多条具有足够资源,以满足某种约束条件(如延迟,带宽等)的路径。在实际情况中,关于链路状态的信息并不总是确定的,这种不确定性对QoS路由的选择有着不可避免的影响。探讨其原因,在约束条件为延迟保证的前提下,讨论处理不确定信息的QoS单播路由算法。     

移动无线网络的安全QoS路由

本文结合网络的安全性来考虑QoS路由,定义一种反映无线链路安全状态的安全性度量作为QoS度量之一,同时讨论定义安全性度量面临的一些挑战。     

基于卫星时变网络的时延受限最小费用路由算法

卫星网络是一种特殊的时变网络,其QoS路由问题比地面网络QoS路由问题更为复杂.本文利用卫星拓扑的可预测性,通过引入业务的中断概率和费用模型来描述链路切换对业务QoS以及网络的影响,并给出时延受限最小费用路由(SDCMCR)算法来解决在卫星链路时延长的情况下寻找满足时延限制条件且受切换影响最小的路径的问题,该算法可兼顾网络业务中断率和业务阻塞率等性能,且计算复杂度低,可适应星上设备处理能力的要求.仿真表明算法在计算复杂性、业务请求被阻塞的概率等方面都优于同类算法.     

EA-HD: a novel link state update mechanism for ASON

When a connection request comes in a mesh optical network, the routers automatically choose the suitable routing paths and wavelength to it according to the network topology and link-state information saved in its global link-state database. Because some of these wavelengths may be released or occupied at any time, the global state database is always out of date and need update by some update policy. A suitable link-state update policy is critical, since a high-frequency update policy imposes heavy burden on the network, while a low-frequency update would increase the inaccurate of the global link-state database. In this paper, we propose a link-state update policy, named the EA-HD policy, which considers two index of a link, one is the Hamming distance between the local link-state database and the global link-state database, and the other is the used ratio of its wavelengths. The proposed update policy gets a trade-off between the accurate of link-state information and its update cost. Simulation results prove that our scheme achieves a good performance in traffic blocking probability while maintaining moderate volume of update traffic.     

A novel method of link-state update in wavelength-routed networks

Link-state update is a critical component of the routing protocol in wavelength-routed networks. High-frequency updates impose heavy traffic on network control channels as well as excessive burden of electronic processing, while stale link-state information seriously degrades network performance. Therefore, a tradeoff has to be made between control overhead and network blocking probability. This paper proposes a novel link-state update method. By actively regulating the link-state update rate, the proposed method efficiently handles the inherent burstiness of link-state changes without overloading control network with excessive update messages. To improve the blocking performance under limited control bandwidth, it assigns different types of updates with different priorities such that the stale link-state information of more negative impact has a higher chance to be removed. Comprehensive performance evaluations show that the method successfully enforces the control bandwidth quota while achieving much lower blocking probability than existing link-state update methods.     

Simulated Annealing Based Multi-constrained QoS Routing in Mobile ad hoc Networks

Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, which is a big challenge for mobile ad hoc networks (MANETs) where the topology may change constantly. It has been proved that such a problem is NP-complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions, most of which suffered either from excessive computational complexities or from low performance were proposed only for wired networks and cannot be used directly in wireless MANETs. In this paper a novel QoS routing algorithm based on Simulated Annealing (SA_RA) is proposed. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR in MANETs. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximation algorithms showing better performance than the other pertinent algorithm in seeking the (approximate) optimal configuration within a period of polynomial time.     

A generalized protection framework using a new link-State availability model for reliable optical networks

This paper investigates a generalized protection framework for availability-guaranteed connection provisioning in an optical wavelength-division-multiplexed (WDM) network. Reliability is a crucial concern in high-speed optical networks. A service level agreement (SLA), which mandates high service availability even in the face of network failures must be met in provisioning a reliable connection. In this study, a new link-state-modeling mechanism is developed to form a dynamic link-state parameter called link and resource availability (LRA), which represents physical-layer availability and resource status for an optical link. Such up-to-date link-state information can be used by a standard link-state routing protocol to efficiently provision reliable connections. Based on the link-state availability model, LRA, a connection-provisioning algorithm is then proposed which can guarantee customers' availability requirements. A new generalized protection model is developed through dynamic LRA-based provisioning. Numerical results demonstrate the performance of the proposed provisioning approach to be promising.     

一种非精确状态下满足多QoS约束的 动态组播路由算法

提出了一种非精确状态下满足多QoS约束的动态组播路由算法——DMIQ,该算法采用改进的BF算法作为路径搜索算法,WFQ作为分组调度机制,链路延迟不确定且服从均匀分布,能在非精确状态且满足带宽、延迟抖动和丢包率约束的前提下确定具有最小跳数和开销的动态组播路由.仿真实验表明,DMIQ能在非精确状态且满足多QoS约束的前提下建立动态组播路由,在路由请求平均成功率、平均延迟和平均跳数等衡量指标下表现出良好的性能.     

卫星网络中基于最小中断概率的时延受限路由算法

针对卫星网络链路时延长和拓扑时变的特点,给出一种可满足时延限制且在业务持续时间内尽可能不发生中断的时延受限最优寻路(SDCOP)算法,该算法通过预测拓扑链接情况来有效降低链路切换对网络QoS的影响,且具有计算复杂度低,可适应星上设备处理能力的要求等优点。仿真表明算法在计算复杂性、业务阻塞率以及业务中断率方面都优于同类算法。     

多约束路由的分层计算方法

针对多约束参数限制下服务质量路由的寻找问题，提出一种分层式计算思想。设想把路由计算方式分为两层，第一层工作是计算源与目的节点间的可达路径集，第二层则是在路径集中寻找满足条件的路由。研究出一种可达路径集计算方法，在此基础上推出了具体的分层式路由计算方法，采用由少到多逐一增加串联链路和节点数量递进方式进行，一旦寻找到满足条件的路由，则给出结果，退出计算。通过算例详细介绍了路径集与路由寻找的计算方法，并论证了路径集算法的正确性，阐明了路由新算法的时间复杂性及诸多优点，提出了适应多约束参数传输的状态信息交换协议改进建议。通过仿真实验验证了路由新算法的正确性，同时也说明新算法完全能够满足实际需要。