基于FPGA的路由技术研究_路由技术
时间：2019-03-30 03:32:47 来源：雅意学习网 本文已影响 人 
摘要：该文针对路由器的路由查找，简单概述了路由技术的发展，路由器的体系结构，硬件路由表的数据结构设计等，介绍了FPGA，及基于FPGA的路由技术，研究了如何用FPGA硬件实现高效的路由技术。
关键词：网络；路由器；FPGA；硬件；路由技术
中图分类号：TP393文献标识码：A文章编号：1009-3044(2012)16-3806-02
核心路由器由于需要执行复杂的IP路由查找操作,已成为制约因特网性能的新的瓶颈，我们需要高速有效的包调度、转发和路由策略，此技术的研究受到业界的广泛关注[1]。
1路由技术
英特网的体系结构是分层次的，每个层次结构上都需要对应功能的路由器。接入网上的路由器主要负责的是将家庭用户和小型企业网连接到ISP，它面临的主要问题是将使用不同的网络技术的PC接入Internet，这就要求其提供高速的端口，丰富的协议支持；而企业级的路由器则是连接整个企业或校园中的所有PC,所以要求其必须易于配置，能提供高密度的端口，支持QoS等功能；骨干网上的路由器是不需要直连用户端系统的，它们连接的是ISP和企业级网，需要能提供高速路由功能。所以,路由技术对于整个网络是至关重要的。
1.1路由器简介
路由器的逻辑体系结构主要由路由引擎，转发引擎，路由表，网络适配器和相关的逻辑电路等几部分组成。转发引擎中最关键的就是IP协议，控制对路由表的查找，负责把数据包从一个网络适配器转发到另一个网络适配器。而路由表的查找效率是整个路由器的性能的关键因素，因为每个通过路由器的数据包都需要首先对路由表进行查找然后决定如何进行转发。路由引擎不涉及通过路由器的数据通路，只负责对路由表更新，包括了高层协议，特别是路由协议，所有往往用通用的CPU代替。
1.2硬件路由表设计
路由表的实现方法主要有两大类：基于软件和基于硬件。但是基于软件的查找次数至少为5次，这距离高速链路的要求已经远远不够了；而基于硬件的方法中则有很多结构简单，查找速度快，其中最少的只需访问一次存储器，最多只需要访问两次存储器。
通常路由器中路由表的表项都含有以下这些域：目的IP地址域，距离向量度量域，下一跳IP地址域，路由变化标志域，路由计时器域。如果每一个IP地址都对应一个表项，那么就会占用很大的存储器空间，但是其中有很多的表项必定没有被使用，所以在设计路由查找算法时就需要根据如下的原则来设计：容易在硬件上实现，并具有良好的性能和可扩展性；能有效的对存储器进行利用；能提供有效的最长前缀匹配，并且实时的实现路由表的查找；能实现路由表的插入和删除并且支持广播和组播。
2基于FPGA的路由技术
在传统的路由器设计中，ASIC设计占主导地位，但随着硬件技术的不断发展，新业务不断涌现，为了能够快速地响应市场需求，形成自己产品独特的特色和卖点，基于FPGA实现的路由器成了一种很好的选择。
2.1 FPGA简介
现场可编程门阵列的简称叫FPGA，是专用集成电路（ASIC）领域中的一种半定制电路，是在PAL、GAL、CPLD等可编程器件的基础上发展得来的产物，解决了定制电路的不足，还克服了原有可编程器件门电路数有限的缺点，具有较高的灵活性，并且其设计周期短，具有成本低、风险小等优势。越来越多的设计都开始从ASIC转向FPGA，成为现代IC设计验证的主流技术。以硬件描述语言Verilog或VHDL设计完成的电路，都可以通过简单的综合与布局，快速烧写到FPGA上进行测试。
FPGA的主要特点如下：设计周期短，能够快速成品，可以反复修正使用，风险小，更便宜的造价，开发费用低。FPGA采用高速CMOS工艺，功耗低，与TTL电平兼容，其内部有丰富的触发器和I/O引脚；所以，FPGA芯片是开发路由器的最佳选择之一。
2.2基于FPGA的路由技术
在路由器的设计过程中，选择合适的FPGA来完成路由器中需要灵活处理的业务部分，如路由表的查找，能大大的降低开发风险，有效地缩短开发周期，提高性价比，增强特色。而IP核的使用也使得FPGA的设计可以规模化、产业化[2]。随着FPGA的发展，越来越多的厂商都开始采用FPGA来设计实现路由器。利用现今一些成熟的IP核，如FIR滤波器、SDRAM控制器、PCI标准接口、HDLC控制器、以太网MAC控制器等，将不同的IP核连接起来，并有效地进行数据控制、管理，就可以实现路由器功能设计。从系统安全的角度出发，基于FLASH的技术硬件出错的概率较小，具有更可靠的安全性，还可以经过现场处理就能实现产品的升级换代，支持通过公共网络实现远程升级等特性，这样就减少了现场解决问题的麻烦和代价。
FPGA的一般设计流程是由电路设计与输入、功能仿真、综合、再仿真、布线和上板调试等步骤组成。具体流程如图1所示。
图1 FPGA开发流程图
2.3基于硬件的路由查找实现
报文在经过路由器的时候都要经过一系列的操作后才能被转发，如查路由表，包转发，队列调度等操作，这些通常是由硬件来实现的。要提高路由器的性能必须从优化报文转发路径入手，而其中涉及的最重要的环节就是在转发表中进行路由查找，当入端口接收到一个报文，它需要根据报文的目的IP地址查找出端口。转发表中数据形式是。假设接收到报文的目的地址是address1，理论上路由器需要对路由表中所有表项进行匹配查找：将掩码和address1进行与运算，若结果和网络地址一致，则将此端口加入到候选端口的集合中。最终选择的出端口是候选端口集合中掩码最长的一项，称为最长前缀匹配[3]。
在硬件设计实现路由卡时，主要需要设计实现状态机，存储器，译码器，掩码器，比较器，地址寄存器等部分。根据所需查找的目的IP地址，状态机用来控制路由表的查找，路由表中存储的是所要查找的路由信息。主要的工作原理如下：当路由器从某一个网络适配器接收到一个需要转发的数据包后，会对IP路由表进行查找，这个过程也就是把IP数据包的目的IP地址送到IP地址寄存器中，同时对状态机发一个指令，状态机收到后，会从存储器中读出路由表中对应的表项，然后和IP地址寄存器中的相应几位经译码器，掩码器后进行比较，反馈比较后结果给状态机，状态机接着控制下一轮的比较，当所有的比较结束后，转发引擎在路由信息寄存器中读取最终的结果，并且状态机在某一特定的端口设置标志，来告诉CPU查找的状态是否已经结束。
通常路由查找算法的速度依赖于这个算法为了找到路由表项需要访问内存的次数。假设一个路由算法需要访问5次内存，访问内存的速度是70ns，那么总共的查找时间就是350ns，也就是说在1秒钟大约能完成300000次路由查找。优化路由查找性能的方法主要有三类：基于硬件的方法，表紧缩技术和哈西表技术。文献[4][5]中提出了提高更新的速度的解决方案。
3小结
针对网络流量的增加，及对路由器性能要求的提高，该文简单介绍了路由器和硬件路由表的设计，并结合FPGA技术，介绍了基于FPGA的路由技术，从硬件的角度对IP路由查找的硬件实现做了简单的介绍和分析，同时可以得出结论，为了使路由表的查找速率更快，基于ISA总线的实现已经远远不够了，由于VHDL语言固有的灵活性和可编程性，可以实现更为灵活和高效的路由查找，因此使用FPGA芯片来实现路由查找技术，是未来不可避免的趋势。
参考文献：
[1] RuizSanchez M A,Biersack E W,Dabbous W.Survey and taxonomy of IP address lookup algorit hms[J].IEEE Network,2001,15(2):8-23.
[2]汪超.以太网交换架构路由器中基于FPGA的E1接口设计[D].上海:上海交通大学,2009.
[3]谭明锋，龚正虎.基于AsIc实现的高速可扩展并行IP路由查找算法[J].电子学报，2005，33(2)：209-213.
[4] Gupta P,Lin S, McKeown N.Routing Lookups in Hardware at Memory Access Speeds[C]//Guerin R. Proceedings of IEEE INFOCOM’98, San Francisco, CA:IEEE Computer Society Press,1998:1240-1247.
[5] Brodnik A.Small Forwarding Tables for Fast Route Lookups[J].ACM Computer Communication Review,1997,27(4):3-14.
