一种基于链路状态的域间出口优化选择框架及关键算法

随着Internet的快速发展,域间路由变得越来越重要.域间出口选择优化问题成为域间路由协议研究的一个重要问题.当前的域间出口选择机制通常缺乏灵活性和有效性,例如,这些机制往往忽略路由的稳定性、网络的动态性、选择的实时性、流量工程等诸多因素.基于以上因素,作者提出了一种基于链路状态变化的高效的BGP出口选择框架.该框架能够根据AS的多目标提供一种灵活的路由优化方法.基于控制规则和当前的链路状态,每个BGP路由器能够在线选择合适的出口.该框架具有灵活性、可扩展性以及健壮性.在此基础上,讨论了其中的一个基于链路故障的关键算法.模拟实验表明,该文所提出的机制对网络管理者是灵活而有效的.     

基于树结构的分布式BGP路由计算迭代算法

随着互联网规模的迅速增长,下一代核心路由器的研究重点正在向可扩展体系结构的方向发展.分布式路由协议计算是可扩展路由器需要解决的关键问题之一.作为已经在骨干网上广泛部署的重要路由协议,BGP协议的分布式模型及其相关算法的研究是可扩展路由器体系结构中的重要研究课题.本文基于BGP路由计算模型,对“路径选优”这一BGP基本操作的特性进行了深入分析,提出了一种按照树状结构来组织路由计算过程的模型,基于此模型可以分布式计算BGP路由.针对两类典型的可扩展路由器体系结构,本文分别提出了相应的迭代树算法,对算法给出了性能改进的理论分析.通过模拟实验,验证了本文所述模型的实际性能.     

TRUST-TIE:可信的域间出口选择算法

域间出口选择算法虽然考虑的是本域内流量的出口选择,但BGP出口的改变会影响邻居域流量模式的改变,从而可能会造成邻居域的网络拥塞并引起邻居域流量的重计算,进而引发路由振荡风险。针对以往出口选择算法主要根据域内网络状况选择出口的不足,依据社会交往中会形成一定的信任关系,然后指导今后交互的特点,提出了一种基于信任的域间出口选择算法,算法的主要思想是在基于域内网络状况来选择出口的基础上,综合了对到达目的路径上其它域的考虑,在达到充分利用网络资源的基础上,以减少协议代价,提高路由的稳定性。理论实验分析表明,算法具有经典热土豆算法同样功能的同时,在请求拒绝率、网络吞吐量、平均路径长度和路由的稳定性等方面都比较理想。     

MED欺骗与域间出口选择 *

BGP(边界网关协议 )是目前用于广域网中最主要的域间分布式动态路由协议 ,具有丰富的路由控制机制。 BGP MED( multi-exit-disc)属性的正确使用可以避免热土豆路由和 MED振荡。提出了一种称之为 MED欺骗的路由策略技术 ,用于实现域间的出口选择。详细阐述了 MED欺骗的原理与具体策略 ,并对其进行了优化 ,最后利用仿真软件加以验证。     

ITIE:一种改进的域间出口选择算法

一般的域间出口选择算法,如经典的热土豆算法只是根据域内事件来调整路由,故少量网络拓扑事件的变化就可导致BGP路由的大量变化;虽然TIE算法改进了对域内事件的敏感性,使其能对域间出口的选择进行调节,减轻路由的动荡性,但未给出阈值参数T的计算方法,且T也不能随负载的变化而变化。域间邻居事件的影响也对域间出口的选择产生重要影响。该文提出一种自适应的可调域间出口选择算法——ITIE算法,能够针对TIE算法的不足,通过对参数的动态自调整来适应当前网络负载和域间通信能力的改变,更好地满足流量工程和网络健壮性要求。模拟实验表明,ITIE算法能够在域间协同性以及随负载变化的流量自适应性上达到合理的折中。     

自治系统间的安全路由协议GesBGP

域间路由协议BGP的安全性直接影响着互联网路由的可用性.虽然现有很多改进的BGP安全方案可以解决这些安全问题,但这类方案存在很多设计缺陷(例如,路由资源消耗问题).在文中,作者充分考虑了安全BGP的目标并提出了一个Good-Enough-Security BGP(GesBGP)协议.GesBGP在可信计算技术的基础上使用基于身份的密钥(IBS)算法确保BGP协议中身份的真实性.IBS算法的引入有效地消除了传统安全BGP协议中部署集中公钥基础设施(PKI)以及公钥证书的分发和储存问题.此外,GesBGP不单纯依赖于安全密钥算法,基于可信计算技术的BGP可信服务从路由器系统本身防止了系统配置的非法篡改,消除了路由消息的多重累积签名.在提出的优化GesBGP协议中,通过部署BGP的安全规则建立AS之间强制信任关系,进一步消除了BGP通告消息中的累积签名.安全分析和性能评价表明,优化的GesBGP在确保BGP安全性的同时有效地改进了GesBGP的性能.     

分布式控制平面: 并行BGP路由计算自适应负载均衡算法

下一代互联网高度可扩展支持服务动态部署.越来越多延时和抖动敏感服务(如IPTV、VoIP等)的应用对BGP路由计算的性能提出了更高的需求.路由器采用分布式控制平面和实现并行BGP路由计算克服集中控制平面的性能瓶颈是解决这个问题的有效途径.但现有并行BGP路由计算方案因负载均衡性能差影响了系统的并行性能.文中基于Hashing技术提出了并行BGP路由计算自适应负载均衡模型.通过在线统计路由更新设计了自适应负载均衡算法P-AP(Prediction-based Adaptive Partition),自适应地动态调整路由更新在处理节点间的分配.最后设计和实现了原型系统,并利用Route Views 收集的BGP Update数据进行实验.实验结果表明,P-AP算法具有负载均衡性能好、负载调整频率小和路由计算加速性能好等特点,能够有效地提高并行BGP路由计算性能.     

一种基于故障时间的可调域间出口选择算法

在大型Internet服务提供商中,BGP (border gateway protocol)出口路径选择常常采用"热土豆"机制.然而研究表明,该机制具有相当大的局限性以及出口调节的间接性,它容易影响域间路由的健壮性.针对"热土豆"机制的缺点,出现了一些新的BGP出口路径选择机制和算法.然而,这些方法在解决问题时往往忽略网络运行过程中经常出现的IP链路故障或故障持续时间的影响.提出了一种基于故障时间的可调域间出口路径选择算法,该算法能够根据流量工程的目标、路由稳定性等要求进行动态的调整,同时满足路由变化的实时性.模拟实验结果表明,该算法能够有效地在多个目标之间达到平衡.     

一种互联网的稳定路由选择策略

互联网中网络故障频繁,域间路由协议(BGP)并不能很好地适应网络故障.一般情况下,域间路由协议会经历一个比较漫长的路由搜索过程,导致互联网中大量的数据包丢包.虽然目前已提出了很多改进的BGP算法,但这些算法复杂度非常高,给路由器增加很多额外的计算代价.为了解决这个问题,作者提出了一个稳定的域间路由选择算法sBGP.在sBGP中,当路由器收到由故障触发的路由通告后,采用启发式的路由选择算法选择目前可选的最稳定路由为最佳路由.通过稳定路由选择,路由器可以选择有效的稳定路由,以避免无效的路由搜索以及路由不断更新引入的路由器处理开销.分析和模拟实验表明sBGP不仅能够有效提高BGP的收敛性能,而且可以减少收敛过程中的通信开销.     

递归调用的内联策略分析

基于Tang提出的全控制流图研究了递归过程内联优化问题.提出妨碍递归过程内联的关键在于局部变量的副本问题,通过变量的定义使用关系分析,提出递归过程的可内联条件是在流图中任意局部变量的定义使用路径均不穿过递归调用语句.给出了内联时出口语句的模板,它能够处理存在多处递归调用的情况.最后通过实例说明了递归过程的内联.     

求解大规模全局优化问题的新型三层递归差分分组方法

协同进化算法在求解大规模全局优化问题上具有较好的效果,其核心思想是利用分而治之的策略将一个高维问题分解成若干个子问题,然后分别优化每个子问题.然而,现有的分解方法通常需要花费大量的计算成本来获得精确的变量分组.通过采用递归交互检测中的历史信息简化分组过程,能够避免检测某些集合的相互关系,本文提出了一种新型三层递归差分分组策略(NTRDG).与其他4种现有的分组方法相比, NTRDG在不影响分组精度的情况下计算成本消耗较低.仿真结果表明, NTRDG在求解大规模全局优化问题时具有很强的竞争力.     

全互连立方体网络在并行处理系统中的应用

提出一种应用于大规模并行处理系统的结点度等于常数的递归多级分层互连网络 ,称为全互连立方体网络 (fully connected cubic network,FCCN) .FCCN具有可扩展性好、延伸性能好等优点 .一个 m- FCCN可以由 8个(m - 1) - FCCN递归得到 ,FCCN网络的结点度与网络的规模大小无关等于常数 4,网络的直径和平均结点距离都与结点数的立方根成正比 .提出 FCCN中的简单路由算法 .并将 FCCN互连网络结构在大规模光电混合处理系统中进行应用 ,通过实际计算结果证明 FCCN具有比较高的并行处理效率     

KMP算法中next数组的计算方法研究

next数组的计算方法是KMP(Knuth-Morris-Pratt)算法的难点和核心.当前数据结构教材中普遍采用递推的方式来计算next数组值.文中给出一种新的采用递归思想设计的计算next数组的算法;并对当前数据结构教材中对next数组定义的其它一些改进方式进行了讨论与分析.实验数据表明,递归算法的思想正确;并且,从算法设计上考虑,采用递归方法设计的算法具有思路清晰、易于理解和分析的优点.     

拓广的右线性递归变换算法及其正确性

本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个IDB谓词,它是右线性递归的一般化.和右线性递归计算算法一样,本文提供的算法遵循魔集的模式:首先改写规则,然后用半扑质的自底向上算法计算新规则.算法的有效性通过减少递归谓词的元数实现.     

一个递归算法非递归化的算法框架

虽然递归算法具有结构简练、清晰、可读性强等优点,但有时受执行效率和程序设计语言的限制,必须实现递归向非递归的转换.提出一个通用的算法框架实现一般递归算法向非递归算法的转换.该框架产生的非递归算法没有标号,适用于大多数程序设计语言.结合几个典型的实例说明该框架的应用方法和有效性.     

程序设计中递归的探讨

递归是一种较难掌握的程序设计结构,在C语言、数据结构等课程教学中时有涉及。就学生掌握的情况看,很多学生并未深刻地掌握递归,不能灵活地进行应用。因此,就递归算法在程序学习中的作用及使用范围进行探讨,以期深化学生对该部分知识的掌握及运用。     

改进的OTSU射线图像分割算法

为提高对工业X射线图像的分割效果,提出一种改进的OTSU图像分割算法.分析了经典OTSU算法存在的不足,将类内方差也作为计算最佳阈值的一个因素考虑,从而提出了一种改进的OSTU阈值选择函数.在阈值分割过程中,采用局部递归法逐次进行分割.采用目标背景面积差和类内方差的比值作为递归结束的条件.通过与最大熵法、经典OT-SU法、局部递归OTSU法进行实验对比,证明本算法对于射线图像是一种优秀的阈值分割算法.     

递归查询算法的研究

本文介绍了ＤｅＤＢ的递归查询算法，提出为减少冗余及回溯计算的基本原理．根据该原理，提出了一种高效的递归查询算法ＧＣＱＡ，它包括２部分，一是预编译算法；另一个是递归编译算法．实验结果表明这种算法是高效的．     

一种递归神经网络的快速并行算法

针对递归神经网络BP(Back Propagation)学习算法收敛慢的缺陷,提出一种新的递归 神经网络快速并行学习算法.首先,引入递推预报误差(RPE)学习算法,并且证明了其稳定性； 进一步地,为了克服RPE算法集中运算的不足,设计完整的并行结构算法.本算法将计算分配 到神经网络中的每个神经元,完全符合神经网络的并行结构特点,也利于硬件实现.仿真结果表 明,该算法比传统的递归BP学习算法具有更好的收敛性能.理论分析和仿真实验证明,该算法 与RPE集中运算算法相比可以大大节省计算时间.     

一种快速计算Zernike矩的改进q-递归算法

提出了一种快速计算Zernike矩的改进q-递归算法,该方法通过同时降低核函数中Zernike多项式和Fourier函数的计算复杂度以提高Zernike矩的计算效率。采用 q-递归法快速计算Zernike多项式以避免复杂的阶乘运算,再利用x轴、y轴、x=y和x=-y 4条直线将图像域分成8等分。计算Zernike矩时,仅计算其中1个区域的核函数的值,其他区域的值可以通过核函数关于4条直线的对称性得到。该方法不仅减少了核函数的存储空间,而且大大降低了Zernike矩的计算时间。试验结果表明,与现有方法相比,改进q-递归算法具有更好的性能。