为了适应超大规模超高速信息网络的需求,下一代Internet应具备安全性、实时性、可管理性、可用性和可扩展性等特点,而核心路由器作为构建Internet网络的重要基础设施,其现有硬件体系结构及协议软件结构已无法满足上述要求。特别是,随着Internet规模的快速增长以及各种网络应用的大量涌现,路由系统中关键域间路由协议BGP(Border Gateway Protocol)逐渐面临着性能与多维可扩展性等方面的严峻挑战。多核处理器具有较强计算能力、支持多个层次的并行性、拥有更高存储与I/O带宽、易扩展以及功耗低等巨大优势,为解决BGP协议所面临的问题提供了广阔的研究空间,成为构建下一代Internet网络的基石。因此,研究BGP协议如何充分利用多核处理器在结构与性能方面的优势来满足未来Internet需求,为下一代互联网基础设施建设提供理论基础和技术支撑,具有非常重要的实践意义。本文面向多核处理器平台,以BGP协议性能优化为重点,展开BGP协议线程级并行技术方面的研究。首先,通过分析BGP协议行为与潜在的并行特征,提出了两种线程化BGP(T-BGP)协议并行软件结构:多实例T-BGP与多任务T-BGP,并给出了它们的体系结构设计;继而,重点研究了多任务T-BGP协议中的推测线程划分,以及多实例T-BGP协议中的路由表并行访问与线程间路由通告技术;最后,在多实例T-BGP协议基础上完成了T-BGP原型系统的设计与实现。本文取得的研究成果主要包括以下几个方面:1、提出了两种T-BGP协议并行软件结构:多实例T-BGP协议与多任务T-BGP协议。多实例T-BGP协议以邻居会话划分为基础,由一个管理线程和一组BGP实例线程组成,利用数据并行思想将邻居会话分布在不同BGP实例线程上并行处理。该并行结构具有性能优化效果好、多维可扩展性强、路由选择实时性高等优势,程序开发设计难度较低,且易实现线程间的负载均衡,然而,其运行效率的提升还取决于对路由表并行访问冲突与线程间路由通告阻塞等关键问题的有效解决。多任务T-BGP协议以缓解BGP协议运行瓶颈为目标,采用了任务并行方式,将协议执行核心的更新报文处理过程分解在解析线程、路由更新线程和封装线程上并行执行,而其余功能仍由管理线程处理。该协议旨在挖掘程序内部的任务并行性,其并行性能的发挥取决于线程划分与线程调度等关键因素。2.提出了一种基于局部推测的线程划分技术,挖掘多任务T-BGP协议中更细粒度的线程并行来有效提高协议并行度。通过分析多任务T-BGP协议各功能线程中潜在的可推测性,采用基于最小割的启发式算法对各功能线程进行独立的局部推测线程划分。同时,还提出相应的线程推测策略来实现多线程并行执行,采用推测提交策略和写后读相关检测机制确保了线程推测执行与程序运行结果的正确性。最后,完成了基于局部推测技术的多任务T-BGP协议的功能验证与性能模拟,实验结果显示,该方法具有线程划分效果好且计算复杂性低的特点,采用局部推测技术之后显著减少了各功能线程的执行时间,获得了较好的性能提升。3.提出了一种高效路由表并行访问技术,有效解决了多实例T-BGP协议沿用传统路由表结构带来的路由表并行访问冲突问题。该方法将传统路由表重新组织成为一种动态可重构路由表结构,提出了细粒度动态拆分重组算法,周期性地动态调整路由表结构,根据路由节点访问频度来划分子树进而重组为多个子树集合。动态可重构路由表通过两级访问、局部子树加锁等途径支持不同线程并行访问路由表,有效克服了串行访问路由表的性能瓶颈。同时拆分重组算法通过均衡各子树集合上的访问负载,使得路由表并行访问冲突降低了92.5%。另外,还修改了路由表操作以支持简捷的访问行为。实验结果显示,在三种线程数量配置下,单线程最大路由更新耗时较使用传统路由表时平均降低了约48.7%、50.5%与71.1%,有效缓解了路由更新阶段的性能瓶颈。4.提出一种适用于多实例T-BGP协议的无阻塞线程间路由通告技术,克服了采用传统基于锁机制共享队列的路由通告方式所带来的大量共享访问冲突问题。在该方法中,每个线程为所有邻居各维护一个邻居播报队列,将更新后路由仅写入本线程所有播报队列;在获取播报路由时,各线程将根据本地处理的邻居会话标识从所有线程匹配的邻居播报队列中读取路由信息,避免了各线程竞争访问邻居播报队列。同时每个邻居播报队列都设计为SCLF(Speedy Concurrency Lock-free FIFO)无锁队列,实现了线程间无阻塞快速路由信息传播;还设计了带cache乒乓缓解的路由播报过程以降低因cache数据颠簸所造成的cache失效开销。实验结果显示,该方法使得线程间路由通告时间平均降低了约79.4%,设计的SCLF无锁队列显著改善了队列操作时间,较Lamport队列的操作耗时减少了56.5%左右。5、在多实例T-BGP协议的基础上,完成了T-BGP原型系统的设计与实现,并重点阐述了主线程与从线程设计的实现细节。该系统应用了动态可重构路由表技术与无阻塞线程间路由通告技术,较多实例T-BGP协议能够提供更加高效的并行处理能力。继而,还对T-BGP原型系统的路由学习时间、eBGP邻居切换速度、CPU使用率及系统加速比等关键指标进行了测试与分析,实验结果显示,与传统BGP协议相比,主要性能指标均得到了明显改善。综上所述,本文的工作针对BGP协议性能优化提出了有效的解决方案,对于推进新型域间路由技术的理论研究和实用化具有一定的理论价值与应用价值。