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

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

基于主机标识的平面路由技术研究

随着Internet的发展,现有网络将位置与身份绑定的做法,使得终端在安全性、移动性和扩展性等方面的弊端日渐显现.提出一种新型的基于主机的平面标识路由,这是一种基于分布式哈希表算法的平面标识路由方式,支持变长主机标识数据通信.本方案设计的路由机制采用网状拓扑,可以在接入路由器之间形成良好的物理连接,为现有各类终端和网络提供了统一接入路由方案,改善了可扩展性,在网通层对数据包进行处理,能够保证终端的灵活出入,并支持终端的移动.     

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

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

采用高维路由节点构建直连式可扩展路由器

可扩展路由器是当前核心路由器研究的热点,直连式可扩展路由器是可扩展路由器研究的一种重要分支.但是,目前直连式可扩展路由器的研究局限于采用低维路由节点的方式进行扩展,这种方式构建的路由器其可扩展互连结构的网络直径增长较快而等分带宽增长较慢.针对该问题,提出采用高维路由节点构建直连式可扩展路由器的思想,认为构建直连式可扩展路由时,路由节点的维要根据路由节点的交换容量和分组延时决定.在分组延时小于某个界的情况下,路由节点的交换容量越大它的维也应该越高这样才能使路由器的可扩展互连结构有最大的等分带宽和最小的网络直径,使路由器在满足分组延时要求的情况下具有最大的交换容量.从理论上分析了该思想的可行性,仿真结果进一步验证了理论分析的正确性.     

互联网可扩展路由

全球路由表的高速膨胀,使互联网路由系统的可扩展性面临着严峻的挑战.为了缩减路由表,很多研究提出了新的路由解决方案.在介绍了互联网路由系统现状之后,从较高层次上将存在的解决方案分为短期方案、路由架构和可扩展路由算法3部分.着重介绍了路由算法和路由架构这两类工作,对经典的可扩展路由算法和路由架构进行了深入的分析和比较.最后讨论了有待解决的关键问题和未来的研究方向.     

一个2D-Mesh路由器模型系统

自适应路由器是ＭＰＰ研究领域中的一个重要研究课题。本文实现了一个路由器模型系统,介绍了几种自适应无死锁路由算法,并利用模型系统对路由算法进行了测试。     

基于可扩展路由体系的路由均衡存储转发模型

路由表的急剧扩张使得可扩展分布式路由器中线卡的硬件成本迅速增长。提出一种路由表的均衡存储转发模型RESD(Storage and Decomposition Model based on Even Routing),它属于非完全存储方式。RESD模型通过初始化分配将长度相邻的前缀尽可能地分配到相同或是相邻的线卡上,然后通过分段式分配均衡每个线卡上的路由数目,最后通过路由特征位信息表和定位路由来实现路由信息的查找。实验证明,该模型可以在路由表分解存储均衡的同时大大减少LPM匹配中各线卡的并行查找次数。RESD模型的设计和实施原型都是以真实的环境为基础的,因此,RESD模型与现有网络的体系结构具有良好的兼容性,易于实施。     

基于可重构路由单元的软件构件描述语言研究与设计

随着路由器的研究重点从对路由器性能的提升发展到对路由器功能的扩展,可重构路由单元成为解决路由器功能扩展方面的一个很好的尝试。可重构路由单元的构件化设计引入了软件构件模型的思想。基于软件模型构件化开发,对可重构路由单元构件模型的描述及管理方法做了研究。软件构件描述语言和描述方法的研究与设计为下一步进行路由器构件化开发也打下了坚实的基础。     

基于Tcl的策略路由协议一致性测试

协议一致性测试是保证协议实现满足协议描述的重要手段,策略路由是一种路由转发协议,它根据协议类型、IP源地址和报文大小选择转发路径。论文从策略路由协议的特点出发,设计并实现了基于Tcl语言的协议分布式测试系统,并应用于路由器的策略路由测试。     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.     

基于端用户可控的IP网络路由体系结构和算法

IP网络的路由体系结构及算法是网络有效运行的关键技术.现行的路由体系结构及算法在实际应用中存在着一些问题.针对该问题,提出一种端用户可控的IP网络路由体系结构和具体的路由算法.在提出的端用户可控的路由体系中,利用用户级别的自组织路由方法来简化路由器的负荷,增强端用户的智能性.模拟仿真实验表明,该路由体系的使用,将使路由器的任务简化为通报网络信息和协调用户决断这两个较为简单的功能,且路由选择的决断考虑到端用户的实际需求.该体系结构可以更好地适应网络规模和应用需求的不断扩大,形成一个分布式、扩展性较好的路由体系和有效的路由算法.     

基于事件驱动的边界网关协议BGP-4的设计与实现

边界网关协议BGP(border gateway pr otocol)是Internet上用于自治系统之间交换路由信息的动态路由协议.介绍了在清华大学研 制的国产高性能路由器中分布式路由协议BGP-4的具体实现.为了实现这一复杂的动态协议, 提出基于事件驱动的设计和实现方法.事件驱动机制能够精确地反映网络报文交换行为的实 现机制,因而很适合Internet高层协议的实现.该方法也可以用于实现其他的Internet高层协议.     

一种新的路由优化计算方法

随着网络规模的扩大,路由算法的优劣对改善整个网络的可扩展性起到至关重要的作用。传统中分级路由算法既保持源路由算法的优点,又有分布式路由算法的优越性,但因路由计算由许多节点承担必然带来路由质量的代价,如聚合信息不精确会严重影响路由的质量甚至影响网络的连通性。为了适当地减少路由计算的频度并快速提高计算效率,本文基于传统的路由算法提出了一种新的并行路由优化计算方法。     

SoMR: A scalable distributed QoS multicast routing protocol

Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. The requirements can be additive (end-to-end delay), multiplicative (loss rate), or of a bottleneck nature (bandwidth). Given such diverse requirements, it is a challenging task to build QoS-constrained multicast trees in a large network where no global network state is available. This paper proposes a scalable QoS multicast routing protocol (SoMR) that supports all three QoS requirement types. SoMR is scalable due to small communication overhead. It achieves favorable tradeoff between routing performance and routing overhead by carefully selecting the network sub-graph in which it searches for a path that can support the QoS requirements. The scope of search is automatically tuned based on the current network conditions. An early-warning mechanism helps detect and route around the long-delay paths in the network. The operations of SoMR are completely decentralized. They rely only on the local state stored at each router.     

域间路由连通不完全性分析

论文从应用需求的角度出发,研究了分布式应用系统与网络层端到端连接性之间的关系,认为分布式系统的模型和部署应独立于网络层端到端连接。指出目前Internet域间路由中AS之间路由策略独立定义和实施对这种独立性带来了不利影响,它导致Internet跨域的端到端连接是连通不完全的。并试图提出初步的解决思路和方案。     

支持时延-带宽约束的动态层次组播路由

层次网络及层次路由成为解决大规模网络QoS路由可扩展性问题的一个主要手段.文中对PNNI层次网络模型下的时延-带宽多QoS约束的动态组播路由问题进行了全面研究:在已提出支持时延-带宽约束的拓扑聚集算法(Stair)的基础上,进一步对组播树节点需维护的组播树状态信息及其聚集问题进行研究,并提出"伪树上边界节点"模式的域内组播树状态信息的聚集方法,最后设计了基于聚集拓扑信息和组播树状态信息的动态层次组播路由算法.仿真结果显示,该路由不仅大量压缩了存储和扩散的拓扑信息和组播树状态信息,同时还保持了与平面网络近似的路由效率,实现了大规模网络情况下组播路由的扩展.     

采用泛播路由构建高效中继路由系统

中继路由系统由一组中继路由器组成,为不能交换路由信息的路由域提供中继路由.该系统的关键是为路由域配置恰当的中继路由器.为所有中继路由器分配一个泛播地址,将它们当作一个逻辑节点,借助泛播路由以最短路径到达该逻辑节点.此外,采用源路由的方法将数据报文路由至中继路由器.基于泛播的中继路由系统实现了中继路由的自动配置,提高了中继路由的性能和可靠性,并且与现有网络系统兼容,实施代价很小.     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

一种适用于2D Mesh片上网络的可重构容错路由算法

适用于2D Mesh片上网络的可重构容错路由算法,在芯片某些区域由于制造缺陷、使用老化等原因拓扑结构变得不再规整的时候,可以对网络节点重新进行配置,从而保证健康节点间的正常通信.基于SystemC的平台仿真表明该算法相对于传统算法可以获得更佳的网络性能.该算法是免于死锁的,同时对其可重构机制也给出了详细的论述.它还具有良好的扩展性,当系统规模增大的时候每个路由器的硬件开销保持恒定,而其容错能力也得到了增强.