《计算机工程与科学》论文排版样稿.doc

一种支持高速IPv6转发的路由器体系结构FIS*基金资助：国家自然科学基金资助项目（*）A Router ArchitectureFIS Facilitating High-speed IPv6 Forwarding*，*D* Y*-b*，S* J*-s*（国防科技大学计算机学院， 湖南 长沙 410073）（School of Computer Science, National University of Defense Technology, Changsha 410073, China）摘 要：本文提出了一种在交换网络中执行转发操作的路由器体系结构（Forwarding In Switch, FIS），采用多个低速的具有独立转发和交换功能的转发交换结点FSN（Forwarding and Switching Node），组成多级流水线结构，以流水的方式执行报文转发和交换。本文对FIS中实现IPv6转发的关键技术IPv6转发表的分解、转发表到FSN结点的映射、IPv6转发引擎的设计及报文调度算法进行了深入的研究，基于FIS体系结构，提出了易于硬件实现的IPv6查找机制和基于hash老化的报文调度算法，为下一步FIS原型系统的实现提供了切实可行的方案。Abstract: A router architecture performing forwarding in switch (FIS) is proposed that consists of multi-stage, lower speed nodes called FSN performing IP-lookups and switching independently, thus IP-lookups and switching for multiple packets being pipelined. We investigate the key technologies of IPv6 forwarding for this architecture including the partition of IPv6 forwarding table, the logical mapping from forwarding table to FSN nodes, the design of IPv6 forwarding engine as well as the packet scheduling algorithm. Consequently based on FIS architecture a scalable IPv6 lookup mechanism and a packet scheduling algorithm based on hash miss are proposed which provide a practical way to implement FIS prototype.关键词：FIS路由器体系结构；转发表分解；转发表映射；IPv6转发Keywords: FIS router architecture; partition of forwarding table; mapping of forwarding table; IPv6 forwarding中图分类号：TP393 文献标识码：A1. 引言目前IPv4 地址枯竭问题日益凸显，以IPv6为核心的下一代互联网随之提上日程。IPv6采用128位地址长度，地址资源极其丰富，有人形容，世界上的每一粒沙子都会有一个IP地址。与IPv4相比，除了丰富的地址空间，IPv6还兼具QoS、组播、安全和IP移动性等方面的优势。IPv6核心路由器是用于下一代互联网建设的关键技术设备，IPv6路由器设计的主要障碍是相对较慢的IP 查找算法。目前路由器采用精确转发、集中式交换的体系结构，即首先由转发部件对报文进行精确查表确定其转发决策，然后由集中式的交换网络将报文交换至目的端口。在这种传统的路由器体系结构中，转发部件难以满足FIB表容量增长和线速转发的需求，而集中式的交换网络难以满足端口速率和端口密度的需求。本文提出一种基于部分转发和流水交换的并行路由器体系结构，路由器由多个结点构成，每个结点是独立的具有一定转发和交换能力的功能部件，称之为转发交换结点FSN（Forwarding and Switching Node）。每个FSN结点仅保存转发表的一部分，完成报文的部分转发操作，直至出口FSN结点才得到报文的最终转发决策，称之为部分转发技术。FIS体系结构的优势在于通过分解路由表，降低了单个转发部件的查找复杂度；报文流被分派到多个FSN结点并行处理，降低了高速报文缓冲对存储器带宽的需求。FIS通过同时开发报文转发和交换操作的并行度，缓解了高链路速率和FIB处理极限在路由器体系结构设计中的尖锐矛盾。2. FIS关键技术IPv6路由查找仍然是最长前缀匹配，在FIS中实现IPv6转发有着得天独厚的优势：部分查找技术通过分解IPv6转发表降低了查找复杂度，流水处理方式有利于执行IPv6更长位宽（128bits）的查找。本节基于FIS体系结构，突破了IPv6转发表的分解、转发表到FSN结点的映射及FSN结点转发引擎设计一系列关键技术，提出了一种可扩展的流水化IPv6查找机制。该方案硬件实现简单，以低成本的执行部件FSN获得更高的交换性能和IPv6查找性能。2.1 FIS体系结构在如图1所示基于FIS的并行路由器体系结构实例中，3级33的转发交换结点FSN构成3级流水线, 到达报文被分派到3个FSN结点并行处理。每个FSN结点保存路由转发表的一部分，执行部分IP查找，降低了报文转发操作的硬件实现复杂度；FSN结点直接对变长报文进行交换，消除了对报文的分割和重组操作（Segmentation and Reassembly，简称SAR），报文调度过程简单，避免了系统加速，易于低成本的硬件实现并获得较高性能。FIS体系结构的实现取决于以下三大关键技术：（1）IP路由表的分解算法：如何合理地分解IP查找树，有效降低报文转发复杂度。（2）子树到FSN结点的映射算法：研究分解后的路由转发表在多个FSN结点的映射算法，保证报文部分转发的正确性和路由转发表在FSN结点分布的均衡性。（3）FSN结点的IP查找和交换机制：设计单个FSN结点的报文转发和交换策略，以高效的查表和简单的报文调度机制实现多路径负载均衡及报文流的顺序。图1 基于FIS的路由器体系结构2.2 IPv6转发表的分解图2 IPv6转发表的分解为了降低单个FSN结点的IP查找复杂度，需要对原始的IP路由表进行分解。我们将IPv6转发表分解成种前缀长度范围的前缀集合，属于同一种前缀长度范围的前缀信息被表示为二叉Trie的形式，以子树为单位存储前缀信息。如图2所示，IPv6转发表被分割成层，表示根结点位于第级，子树最大高度为的子树集合。与其他基于二叉Trie 树的IP查找算法不同的是，这里的子树只需保存与前缀相关的结点信息，忽略与前缀无关的结点。定义前缀长度为PLen，hash函数hx,y(IP)，该函数的结果是IP地址的第x位到第y位。涵盖了前缀长度范围为的全部前缀，并以子树的形式保存这些将前缀信息。我们为每一层子树关联一个hash函数。子树的访问过程为：对子树的根结点作hash运算，得到的hash值就是访问子树的地址。文献1中的研究结果表明：hash函数应选取靠近前缀长度的位作为其结果,实际上这是因为不同的前缀,越靠近前缀长度的那些位差异性越大。为了能够把子树尽量均匀地映射到hash表内，我们选取靠近子树根结点的地址域作为hash函数的值。假设层共有子树12777 个，那么hash表的地址宽度为，的Hash 函数为h16,29 。2.3 子树的表示我们将IPv6转发表组织成分层结构，并以子树为逻辑单元组织前缀信息。子树可以表示为与根结点相关的全部前缀的集合，如图3所示，每个子树块保存子树的根结点信息和子树中包含的前缀信息。我们采用文献2提出的CAM结点的存储方式来保存子树的前缀信息：每个前缀表项包含匹配位（match bits）、匹配长度（match length）、下一跳（next hop）三个信息域。最大子树高度为，每个前缀项包含h bits的匹配位，bits的匹配长度和10 bits的下一跳信息（支持1024个端口）。例如，子树高度为3，包含前缀*，10*，111*，可将这些前缀分别表示为（未显示10 bits的下一跳信息）：000 00，100 10，111 11。子树块只能保存固定数目的前缀，当子树块内所有前缀项已被占满而出现溢出前缀时，开辟专用的存储空间存储少量的溢出前缀，子树块中保存溢出前缀指针。 图3 子树的表示2.4 子树到FSN结点的映射二分映射算法子树到FSN结点的映射算法用于建立子树到FSN结点的逻辑映射关系，它一方面要保证报文流水转发的正确性，实现IPv6最长前缀匹配；一方面要使子树在FSN结点的分布尽量均匀。FIS体系结构采用一种基于二分查找策略的子树映射算法。二分查找算法由Waldvogel等人提出，其基本思想为：按照前缀长度组织hash表，每一个hash表保存一种长度的前缀，采用二分查找策略对hash表进行搜索3。该方案可扩展性好，能有效降低查找过程中的访存开销，访存次数独立于路由表的增长。最坏情况下的hash查找次数为log2(IP地址长度)。图4 hash表的二分查找过程为了实现二分查找算法，需要在高层子树中加入指向低层子树更长前缀的标记。标记保存在hash表中，图4显示了根据标记进行二分查找的例子。假设存在前缀P1 = 00*，P2 = 1011*，P3 = 10100*，P4 = 101000*，子树高度为1，那么这些前缀在层，hash表中的分布状态如图4b所示。假设查找101000，按照二分查找算法，从中间层hash表开始查找，地址信息的高4位1010命中根结点为101的子树块，但未匹配子树块中的任何前缀，也没有任何信息指明下一步查找的方向查找高半层子树或低半层子树。为了解决这个问题，我们在中间层hash表中加入标记0，此时查找1010将命中标记0，这表明下一步应搜索低层子树。在中查找101000时，匹配前缀P4，从而得到最长匹配前缀。需要指出的是，若查找底层子树失败，仍需查找高层子树。如图3所示，每个hash表项设有1 bit的类型域，用于区分前缀和标记。查找hash表时，若匹配标记，则搜索低层子树hash表；若匹配前缀则记录下一跳信息，将报文转至下一级FSN结点处理；若未命中任何表项，则搜索高层子树hash表。IETF RFC 3587规定IPv6地址的最长前缀为64位4，按照二分映射算法，各层hash表到每一级FSN结点的映射结果如图5所示。图5 hash表到FSN结点的二分映射结果2.5 FSN转发引擎设计FSN结点IPv6转发引擎结构如图6所示，SRAM保存映射到FSN结点的hash表，转发引擎模块、存储管理模块及更新模块通过SRAM仲裁器读写hash表。转发引擎模块对报文IP地址对应的根结点作hash运算，根据hash值读取子树块，若命中前缀则返回下一跳信息，若命中标记则访问低层hash表，若未命中任何表项则访问高层hash表。当查找低层hash表失败时，仍需查找高层hash表，因此最坏情况下的访存次数为3。存储管理模块负责溢出前缀块的申请与释放，在初始化阶段，转发引擎在写入hash表项的过程中可能需要申请溢出前缀块保存子树中少量的溢出前缀，另一方面，在前缀更新的过程中，前缀的删除操作可能需要释放溢出前缀块，前缀的增加则可能需要申请溢出前缀块。图6 FSN转发引擎逻辑结构3. 基于Hash老化的报文调度算法FIS体系结构存在负载均衡和报文乱序两大问题。负载均衡是提高FIS吞吐率的关键。FIS将到达报文分派到不同的FSN结点处理。如果能够均匀地分配负载，使所有FSN结点保持相近的忙闲程度，那么系统的吞吐率等于各FSN结点的吞吐率之和。否则，会降低处理的并行度，影响系统的吞吐率。报文的并行交换使同一条流的报文通过不同的路径到达输出链路，从而引发报文乱序。为了保证报文的顺序，路由器需要完成大量额外的工作，这会影响路由器的性能。定义路由器功能要求的标准RFC1812并没有禁止在路由器中出现报文乱序现象5，并且报文乱序在Internet中也时有发生。从Internet的分层结构来看，路由器工作在网络层，它只需快速转发报文，传输层协议（如TCP）负责提供报文传输的正确性保证。从这个角度考虑，报文乱序并非路由器所必须解决的问题。另一方面，报文乱序会影响TCP连接的性能。乱序报文使TCP协议误认为发生了报文丢失，从而导致不必要的重传和TCP超时6。这些重传和超时会降低TCP的吞吐率增加报文延迟。既然TCP流量构成了绝大部分的Internet流量，网络管理者普遍认为路由器应尽量保证同一条流报文的顺序。负载均衡能够提高并行路由器的吞吐率，但是它可能导致报文乱序，从而影响TCP连接的性能和网络利用率。负载均衡和报文保序是一对矛盾，也是并行路由器设计必须权衡的关键问题。本节在FIS中采用了一种基于Hash老化的报文调度算法，该策略在保证报文顺序的同时兼顾负载均衡。3.1 hash老化时间的选取报文乱序总是发生在同一条流的报文选择了具有不同延迟的不同路径的情况，保证报文顺序最简单的办法就是让同一条流的报文按照相同的路径到达输出端口，所有的报文经历相同的延迟，从而保证报文的顺序。每个FSN结点维护一个转发控制hash表，记录每条流的交换路径即每条流的下一级FSN结点。对报文头中的一些信息域（例如，源IP地址、目的IP地址和协议类型）进行hash运算，根据hash结果访问转发控制hash表，确定报文流的出口FSN结点。同一条流的报文返回相同的hash值，若该值对应hash表项有效，则按照出口FSN结点交换报文；否则根据下一级FSN结点的负载状况，选择轻负载FSN结点交换报文。 hash老化时间T，是指hash表项的有效时间，它定义了连续两次访问hash表项的最大时间间隔，交换部件为每一个hash表项维护一个老化定时器，用于记录连续两次访问hash表项的时间间隔。若在hash老化时间内，hash表项从未被访问过，那么该表项失效，这意味着该表项对应的报文流不需要按照原来的交换路径转发，可以根据交换网络拥塞状况选择新的低延迟转发路径。假设表示后续各级FSN处理报文的最大延时，表示后续各级FSN处理分组的最小延时，那么hash老化时间T可定义为：。当hash表项命中时，报文必须按照原路径转发，以保证报文的顺序。当hash表项老化失效时，报文流可以根据下游FSN负载情况进行转发，不会导致报文乱序。3.2 报文调度交换部件对每个到达报文的处理流程为：（1）根据报文头的hash结果访问转发控制hash表，若命中则转第2步，否则转第3步。（2）刷新hash表项老化定时器，根据hash表项内容交换报文到下一级FSN结点。（3）从下游FSN结点中选择负载最轻的FSN结点作为报文的目的FSN结点，将该FSN结点标识送hash表项更新，启动老化定时器。（4）将报文缓冲到目的FSN对应的输出队列，等待发送。4. 结束语本文提出了一种在交换网络中执行转发操作的路由器体系结构FIS。FIS技术从路由器体系结构的角度寻求创新和突破，提高路由器的整体转发和交换能力。在报文转发方面，FIS体系结构采用部分转发技术，FSN结点仅在一定范围内的前缀中对部分IP地址进行查找，大大降低了查找复杂度；流水化查找方式通过开发报文转发的并行度进一步提高了查找效率。在报文交换方面，FIS采用多级可扩展并行交换结构，将高速报文流分派到多个FSN结点并行处理，降低了高速报文缓冲对存储器带宽的需求，通过聚合多个低速交换部件提高了路由器的整体交换性能。参考文献1谭明锋,龚正虎. 基于ASIC 实现的高速可扩展并行IP 路由查找算法J.电子学报,2005,33(2):210-213. 2Eatherton W. Hardware-Based Internet Protocol Prefix Lookups MS ThesisD. Washington University Electrical Engineering Department, 1999.3Waldvogel M, Varghese G, Turner J, and Plattner B. Scalable High Speed IP Routing Lookups J. ACM Transactions on Computer Systems, 2001，19(4):440-482,.4 De