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

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

可扩展路由器

对可扩展路由器的研究现状进行了综述,并在可扩展路由器体系结构和模型研究的基础上提出其分层模型,将可扩展路由器"自底向顶"地划分为互连结构和数据交换层,路由查找层、标准接口层、分布式操作系统层、分布式路由行为层和单映像管理层6层,并综述了每层的研究进展.最后进行了总结并分析了当前可扩展路由器发展的难点.     

RIP和OSPF路由协议在Click软件路由器中的实现

Click是一种模块化的软件路由器体系结构,基于该体系结构用户可以根据自己的需求搭建不同功能的路由器.针对Click软件路由器支持静态路由协议的局限性,引入模块化路由器软件协议栈XORP(eXtensible Open Router Platform),实现了动态路由协议在Click软件路由器上的扩展.通过搭建实验网络拓扑环境,验证了基于Click转发平台的两种不同的动态路由协议RIP和OSPF,并进行了相关测试和性能分析.实验结果表明,Click软件路由器的转发性能与Linux内核基本一致,但相比较而言,Click软件路由器具有灵活、可扩展、模块化等不可比拟的优势.     

MED诱发Ⅱ型路由振荡的分析与研究

边界网关协议（BGP）是目前用于广域网中最主要的域间分布式动态路由协议,具有丰富的路由控制机制.为了更好地控制路由策略,当前大部分的营运商均将BGP部署到骨干路由器.随着网络的不断扩展,路由器数目的增多以及路由信息条目的激增,解决BGP的扩展问题变得越来越重要.在采用路由反射和路由联盟方法中,MED属性的使用通常会引起路由持久的振荡.介绍了含有MED属性的路由选择算法,给出了常见的MED配置方案,分析了MED诱发Ⅱ型路由持久振荡的过程,提出了如何避免此类路由振荡的一般方法.     

基于安全多方计算的BGP策略冲突检测算法

边界网关协议BGP是当前因特网域间路由协议的事实标准，基于策略的路由选择过程使它不再是严格意义上的距离矢量协议，也不再具有距离矢量协议的收敛性。Varadhan指出，自治系统各自为政的策略配置方式会导致全局策略冲突，引起永久性的路由振荡。针对该问题，Griffin利用稳定路径问题SPP模型形式化地抽象出BGP协议行为，并以此为基础提出了一种分布式的策略冲突检测算法，尽管该算法完全避免了传统方法的缺陷，但仍然存在泄漏策略信息、对BGP协议改动太大以及浪费网络资源的问题。本文提出了一种基于安全多方计算的检测路由策略冲突的方法，用于在怀疑BGP路由发生振荡时，动态地检测系统中是否存在策略冲突。该方法采纳了Griffin的理论基础，同时由于巧妙地运用了安全多方计算协议，可以完全解决Griffin算法的问题，具有很好的实用性。     

分布式路由器转发引擎性能分析

提出了一种基于泊松分布的排队模型，该模型能够有效地描述分布式路由器体系结构，通过对该模型的分析和计算，可以得了分布式路由体系结构中系统的性能，在多处理器分布式路由器样机上，采集了真实网络环境的性能数据，这种经过验证的性能分析方法可以用于系统的前期设计，与软件仿真或样机仿真相比，该方法具有简单性和先验性。     

基于集群路由器体系结构的BGP分布并行实现技术研究

本文分析了BGP协议在因特网环境中面临的巨大路由表容量、消耗大量控制平面计算资源、支持邻居会话数量有限等难以解决的问题;基于集群路由器体系结构的特点,提出并讨论了BGP协议的四种分布式实现技术;最后对这几种实现技术进行了比较,指出了分布式实现技术相对于传统集中控制方式的优势及特点。     

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

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

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

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

MED诱发II型路由振荡的分析与研究

边界网关协议(BGP)是目前用于广域网中最主要的域间分布式动态路由协议,具有丰富的路由控制机制。为了更好地控制路由策略,当前大部分的营运商均将BGP部署到骨干路由器。随着网络的不断扩展,路由器数目的增多以及路由信息条目的激增,解决BGP的扩展问题变得越来越重要。在采用路由反射和路由联盟方法中,MED属性的使用通常会引起路由持久的振荡。介绍了含有MED属性的路由选择算法,给出了常见的MED配置方案,分析了MED诱发II型路由持久振荡的过程,提出了如何避免此类路由振荡的一般方法。     

可扩展路由器BQ5000的设计与实现

路由器的发展需要可扩展路由器。文章描述了BQ5000可扩展路由器的设计和实现过程。BQ5000采用SBER可扩展路由器软件体系结构,在保证性能的同时实现了功能服务的可扩展性。此外,该文还把BQ5000和其它可扩展路由器进行了对比说明。     

可扩展路由器性能策略

BQ2800是基于可扩展路由器软件体系结构SBER设计的路由器。在路由器性能因素分析的基础上，并结合BQ2800的成功设计经验。总结了可扩展路由器的性能策略，并给出在BQ2800样机上的测试结果。     

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

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

一种带有路由反射的BGP路由预测算法

由于路由反射器的影响,路由器可能只知道非常有限的到达外部目的地的路由的子集,BGP路径选择过程并不会形成一个确定的路径等级顺序,使得路径预测变得非常困难.给出了一种算法,该算法不需要对路由协议动态进行复杂的模拟,只需要静态的路由数据就可以计算出带有路由反射的路由选择结果,并在一个模拟的大型ISP上验证了预测算法的正确性.结果显示配置的改变可以引起路由表的变化.     

可扩展路由器EBP2800的设计与实现

描述了EBP2800可扩展路由器的设计和实现过程。EBP2800采用SBER可扩展路由器软件体系结构，在保证性能的同时实现了功能服务的可扩展性。此外，还把EBP2800和其它可扩展路由器进行了对比。     

LOARD：分层的开放分布式路由器结构

现有的路由器体系结构研究中，很大部分是从纯软件角度展开，忽略了目前ASIC和NP广泛应用的事实。传统的按USER和KERNEL来划分的方式，已经不能准确地描述真实分布式路由器环境的实际需求。本文针对下一代路由器结构的分布式通信需求和扩展性需求，提出了具备分布式通信机制和平台无关特性的LOARD结构。该结构采用虚拟接口、虚拟通道，为分布式路由器的各模块提供了统一的抽象平台，不仅可以适应控制模块的软硬件环境，也可以适应转发模块的软硬件环境需求，对集中式路由器和分布式路由器都具有很好的扩展性和开放性，适合下一代路由器的发展需求。     

一种用于可扩展路由器的报文结构设计

路由器的发展需要可扩展路由器体系结构。本文设计和买现了一种用干可扩展路由器的报文结构。新的报文结构在方便实现路由器模块化，提高报文访问性能，减少模块问内存拷贝，实现报文结构容错性等方面具有显著优势。     

一种基于进程代数的路由器性能评价算法

性能评价是路由器设计中的一个重要环节，目前有多种方法，提出了一种基于进程代数的形式化方法，它能在系统进行正确性验证的同时得到系统的性能参数．首先定义了描述路由器模型的进程代数方法，然后介绍了建立路由器模型的方法，并给出了一个简单的例子，最后给出了计算路由器两个性能指标吞吐率和延时的算法．     

Building extensible routers using network processors

This paper describes our effort to build extensible routers using a combination of general‐purpose and network processors. We emphasize five overriding challenges that dictate our design decisions: (1) optimal resource allocation; (2) efficient but flexible scheduling of the CPU; (3) maintaining overall router robustness; (4) maximizing router performance; and (5) providing sufficient extensibility to enable the injection of new functionality into the router. We adopt a hierarchical architecture, in which packet flows traverse a range of processing/forwarding paths, thereby partitioning hardware and software in concert. This paper both presents the architecture, and describes our experiences implementing the architecture and addressing the five design challenges in a prototype built from Intel IXP 1200 and a Pentium. Copyright © 2005 John Wiley & Sons, Ltd.     

pp-mess-sim: a flexible and extensible simulator for evaluatingmulticomputer networks

The paper presents pp-mess-sim, an object-oriented discrete-event simulation environment for evaluating interconnection networks in message-passing systems. The simulator provides a toolbox of various network topologies, communication workloads, routing-switching algorithms, and router models. By carefully defining the boundaries between these modules, pp-mess-sim creates a flexible and extensible environment for evaluating different aspects of network design. The simulator models emerging multicomputer networks that can support multiple routing and switching schemes simultaneously; pp-mess-sim achieves this flexibility by associating routing-switching policies, traffic patterns, and performance metrics with collections of packets, instead of the underlying router model. Besides providing a general framework for evaluating router architectures, pp-mess-sim includes a cycle-level model of the PRC, a programmable router for point-to-point distributed systems. The PRC model captures low-level implementation details, while another high-level model facilitates experimentation with general router design issues. Sample simulation experiments capitalize on this flexibility to compare network architectures under various application workloads