论文摘要
Internet网络流量、规模和应用的快速发展对互联网核心路由器设计提出了重大挑战。随着光纤传输带宽和入网主机数目的日益增长,路由器交换容量及端口密度难以适应网络流量的增长需求;随着网络规模的急剧扩张尤其是多宿主技术的广泛应用,路由器转发能力难以适应FIB（Forwarding Information Base）表容量的指数级增长;随着IPv6、QoS、组播、安全等应用的发展,路由器报文处理能力难以解决网络流量增长和报文处理复杂度增长之间的矛盾。在路由器中引入并行处理技术的并行路由器体系结构为提高路由器转发交换能力提供了有效途径。采用并行设计给路由器带来了负载均衡和报文乱序两大问题。负载均衡是实现延迟和吞吐率保证的关键,但负载均衡可能导致报文乱序,进而可能触发TCP连接不必要的重传和超时,降低TCP吞吐率,增加报文延迟。如何解决这对矛盾是并行路由器设计的难点。已有的维序调度算法,要么需要复杂的通信或集中式的调度,要么依赖简单的分布式调度而缺乏吞吐率保证。针对以上问题,本文通过深入分析并行路由器体系结构队列模型和信元分布特性,提出了兼顾负载均衡和报文保序,降低调度复杂性和通信开销,并能提供延迟和吞吐率保证的分布式负载分配方法和协同调度机制。现有的路由器包含转发和交换两个连续的处理阶段,它们在硬件实现上是分离的,报文转发与交换的串行执行不利于路由器并行性的开发。本文原创性地提出一种同时开发转发与交换平行度的报文处理机制,将FIB查找功能分解并映射到交换网络中分布执行,为解决目前骨干路由器设计所面临的FIB处理极限问题提供理论、技术和实践支持。论文针对目前并行路由器设计所面临的负载均衡、报文乱序、延迟和吞吐率保证、通信复杂性及FIB极限等问题进行了深入研究,主要研究成果及创新包括以下几个方面:1.针对并行路由器设计负载均衡与报文保序之间的矛盾,提出一种基于流映射的细粒度负载分配算法UFFS-k（Uniform Fne-grain Frame Spreading,k为聚合粒度,简称UFFS-k）,UFFS-k算法分布于各输入端口独立执行,根据本地VOQ队列信息分派信元,不需要任何通信开销,以O（1）时间复杂度实现了100%的吞吐率并能保证报文的顺序。模拟结果显示,UFFS-k算法能够有效降低信元延迟并具有较好的负载均衡特性。2.针对异构型并行路由器设计受限于通信及调度的复杂性,难以保证报文的顺序且硬件实现复杂的问题。基于CIOQ交换平面,提出一种具有按序排队特性的IOQ（In-order Queueing）PPS体系结构,在输入端轮询（round robin）分派算法和中间级CIOQ交换平面同步调度算法之间设计了一种简单的协同调度机制,保证同一条流的信元按序从交换平面读出,避免了输出端报文重定序开销。IOQPPS在多个独立的交换平面间执行报文流级的负载均衡,消除了中间级交换平面的加速需求。模拟结果表明,IOQ PPS在同类PPS设计中具有最优延迟性能。3.针对并行路由器设计所面临的FIB处理极限问题,提出一种在交换网络中执行转发操作的新型报文:处理机制FIS（Forwarding in Switching）。FIS将IP查找功能进行分解并映射到多个硬件同构的具有独立转发交换功能的FSN（Forwardingand Switching Node）结点分布执行,通过分解FIB表,构建FIB表到FSN结点的映射,降低了IP查找复杂度;FIB表的分布式存储,解决了并行查找机制访存瓶颈问题,提高了路由器FIB扩容能力。论文对FIS实现关键技术——转发表的分解、子树到FSN结点的映射及面向FIS的IP查找机制进行了深入的研究,给出了相应的解决方案,为FIS原型验证系统的设计与实现奠定了基础。4.面向FIS处理特性,提出了基于前缀范围的IPv6二分查找算法PSB-BS（Prefix Scope Based Binary Search）:基于前缀范围的子树表示法消除了对路径信息的保存,降低了存储开销;基于前缀范围的二分查找策略能有效压缩查找路径,减少访存次数。通过构造PSB-BS算法二分查找树实现IPv6转发表到FSN结点的映射,仿真实验结果表明,随前缀数目的增加,每一级FSN结点的平均查找次数几乎没什么变化,反映了PSB-BS算法良好的可扩展性。综上所述,本文针对并行路由器设计的几个关键问题提出了有效的解决方案,对提高路由器的性能、规模、可扩展性,以及推进路由器并行技术的实用化具有一定的理论意义和应用价值。