当前位置：文档之家 › 路由器中的硬件IP路由表查找技术

路由器中的硬件IP路由表查找技术

  • 格式：doc
  • 大小：75.50 KB
  • 文档页数：13

路由器中的硬件IP路由表查找技术 Internet的迅速发展给我们的生活带来了巨大的变化。随之而来的是网络流量的迅速增长。网络流量的增长对于Internet上的路由器来说是一个很大的挑战，特别是核心路由器。它需要高速有效的包调度.转发和路由策略。本文针对路由器的路由查找，提出了一种高效的.便于用硬件实现的技术。

1. 路由器的体系结构

图1给出了一般路由器的逻辑体系结构。它主要由下面几部分组成 ：路由引擎、转发引擎、 路由表、网络适配器和相关的逻辑电路等。转发引擎负责把从一个网络适配器来的数据包转发到另一个网络适配器出去。IP协议，包括对路由表的查找，构成了转发引擎中最主要的部分。由于每个通过路由器并需要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决定了整个路由器的性能。路由引擎则包括了高层协议，特别是路由协议，它负责对路由表的更新。由于路由引擎不涉及通过路由器的数据通路，故它可用通用的CPU代替。

2．硬件路由表的数据结构设计 一般路由器中路由表的每一项至少有这样的信息：目标地址、网络隐码、下一跳地址。如果对每一个IP地址都要一个表项，那么需要占用很大的2323*4字节的存储器，而且其中必定有很多的表项没有被使用，这就会造成极大的资源浪费。 为了用硬件实现路由表的查找，查找算法需要满足如下的条件： 1） 实时的实现路由表的查找； 2） 有效的实现路由表的插入和删除； 3） 提供有效的最长前缀匹配； 4） 具有良好的可扩展性； 5） 支持广播和组播； 6） 有效的对Memory进行利用； 7） 硬件上容易实现，并具有良好的性能 。 我们考虑，如果在对路由表的查找中，把子网隐码和IP地址结合起来，对IP地址进行相应的分段，并把它们相连。这样在路由表的表项中，只有IP地址的一部分及其相应的隐码部分，可以实现良好的可扩展性，只要对Memory进行有效的管理，可以灵活的动态的实现对路由的插入和删除。鉴于此，我们设计该表的结构（如下面的表一所示 ）： 它的思想是：把32位IPv4地址主要分成4部分，每部分8位。在该结构中，Address-part[0-4]是IP地址中的一部分，Mask-part[0-4]是相应的掩码部分。Hit-next[0-4]是需要查找的目标IP地址与掩码部分相与后，与Address-part一致时所要查找的下一路由项所在地址的指针。,Miss-hit[0-4]则是相互不一致时，下一路由项所在地址的指针。Shift位则用于判断是否需要对IP地址中的下8位进行查找和判断。它只有在当前的8位IP地址与目标地址中相应的8位一致时，才会被置位。Stop位用于判断是否还需进行查找。它在IP地址查找结束时被置位，或没有比当前项所对应的IP地址更长的路由表项时被置位。 图2就是一个表1的例子 ： 在该例子中，每一方框中上面一行表示相应的IP地址部分和隐码部分。下面一行表示相关的隐码部分的二进制表示。 相应的查找算法如下： ／＊ 查找算法开始 */ search = TRUE ; WHILE ( search ) { masked_key = key & ( entry ->mask_part ) ; result = ( entry ->address_part ) = = masked_key IF ( result = = TRUE ) { best_match = entry ; entry = entry ->hit_next; }ELSE{ entry = entry ->miss_next; IF ( entry ->stop = = TRUE ) search = FALSE; } } RETURN best_match ； ／＊ 查找算法结束 */

为了实现有效的插入和删除，我们还要在路由表的数据结构中再另外添加几个域 ：parent指针（指向本结点的父结点），路由信息（routeinfo）等。它们的用途是在路由表的查找过程中，特别是在指针的回溯（pointer reversal）中，可以大大的节省查找时间。由于IP路由的插入和删除比较复杂。我们只是粗略得说明一下。 IP路由的插入： /* 插入算法开始 */ /* 先用上面提到的查找算法找出best-match */ best_match = search ( new_entry ); /* 确定需要加入的路由中没有被best-match包括的那几位 */ for ( count = first_unmatched_bit ; count <= sizeof ( new_entry) ; count+= sizeof ( address_part ) { /* 创建新的结点 */ create new node ; /* 将该结点连入best_match的hit_next */ link node into hit branch of best_match ; } /* 插入算法结束 */ IP路由的删除要分几种情况讨论 。如 best_match 是叶子结点 ，best_match的hit_next指针为空, best_match的miss_next指针为空 和hit_next指针和miss_next指针都不为空等四种情况。这里就不再讨论。

3．路由表查找的硬件实现： 图3就是对应与上面提及的路由表结构的IP路由表查找的硬件实现（简称为路由卡）的系统框图。 在路由卡中，主要有IP地址，状态机，路由信息，Memory，译码器，掩码器，比较器，地址寄存器组成。IP地址用于保存所要查找的目标地址。状态器用于控制IP路由表的查找。路由信息就是我们所要查找的信息。它的工作原理是这样的： 当路由器从某一个网络适配器中接受到一个需要转发的数据包后，在需要进行IP路由表的查找时，把IP包的目的地址送到IP地址寄存器中，同时给状态机发一个指令。状态接到这一指令后，从Memory中读出路由表的相应的表项，并和IP地址寄存器中的相应几位经译码器，掩码器后，进行比较，把比较的结果反馈给状态机。再由状态机来控制下一轮的比较。当比较结束后，把比较的结果放在路由信息寄存器中，供路由器（如转发引擎）读取。同时状态机在特定的某一端口设置标志，来通知CPU查找是否已经结束或还在进行当中。下面对其性能进行分析。

4．性能分析 由于路由表项中，地址掩码的引入，使得路由结构变得非常灵活。但相应的，由此产生的内存的开销也相当的大。这是性能和硬件开销一对矛盾的必然体现。 该路由卡原型的实现是利用微机上的ISA总线，采用存取时间为70ns 的SRAM存储器（所需容量为6*123k*8bit）。除了使用ISA总线上提供的总线外，本身还带了33M的晶振。对某一路由表项的查找，最多只需32步查找。 在最坏情况下，共需32次查找，查找时间为： 32* 1 /(33*106) ≈ 9.7 * 10 -7秒 此时每秒可查找 1/（9.7 * 10 -7）≈ 1.03 * 106次 虽然该路由卡是基于ISA总线，但平均来说，该路由卡的查找速率为每秒8百万次。这也从另一方面说明该路由卡的设计是可行的。 针对网络流量的增加，及对路由器性能要求的提高，本文从硬件的角度对IP路由查找算法用硬件实现做了一系列的分析，并提出了相应的便于用硬件实现的IP路由表的数据结构。同时对该路由卡的性能进行了分析。 同时也该看到：为了更快的提高路由表的查找速率，基于ISA总线是不可能满足要求的。由此，使用FPGA芯片不可避免。由于VHDL语言固有的灵活性和可编程性，可以更为灵活和高效的实现路由查找。所以，使用FPGA芯片来实现路由查找，是未来的趋势。

因特网最短路径优先(OSPF)路由算法的实现 因特网中，路由器中路由表的生成是非常关键的技术问题。目前，在因特网中的路由器中，都支持开放最短路径优先（OSPF）路由生成算法。OSPF算法生成速度快，而且收敛快、性能稳定，是目前已知的因特网中路由表生成的最好算法之一。 OSPF最重要的内容是路由器如何根据已接收到的本路由器所在的自治系统（AS）的路由器拓扑结构以及各路由器之间的传输费用（代价、权），生成一条从本路由器到AS中各路由器的最短路径，进而生成路由表。 本实验的目的是根据一个给定的网络拓扑结构及路由器之间的传输费用，生成指定路由器到其它路由器的最短路径的实现方法，并且根据求得的最短路径，生成路由表。 最短路径算法是因特网（Internet）路由算法中最重要的算法，关系到因特网的网络交换性能以及网络的稳定性，因此，解决最短路径算法的实现问题，具有非常重要的应用价值。本设计型实验，紧密结合最短路径在因特网中的实际应用，通过最短路径算法的程序实现过程和路由表的生成过程，更深地领会最短路径在因特网中实现快速路由以及路由表生成的原理，培养学生解决实际问题的能力。 二、实验要求 熟悉C语言编程, 熟练使用C语言实现图形结构的说明、创建以及图的存储表示；要求学生熟练应用图形数据结构编程实现最短路径的算法；了解AS中路由器与网络、网络与路由器代价计算方法；了解根据OSPF生成路由表的原理。 三、实验内容 根据给定的网络拓扑图求某路由器到其它路由器的最短路径，并生成路由表 下图为因特网中某自治系统（AS）路由器及网络连接拓扑图。

按照因特网的规定，从网络到路由器的费用为0,因此上图（无向图）可表示为下图（有向图）形式。

求从某路由器（如R1）至其它路由器的最短路径。即从始点（如R1）开始，逐步求始点（如R1）到其它可达的各路由器的最短路径，直到所有路由器计算完成为止。 根据最短路径的求解结果，可以生成路由表。 路由表主要由两个表项组成，即目的网络（目的路由器所在网络）及下一路由器（或下一跳，即所求路由器相邻的某一路由器），如N5,R4，表示到达N5的最短路径通过R4，

合集下载

计算机网络应用 路由器硬件技术

计算机网络应用 路由器硬件技术

计算机网络应用路由器硬件技术目前，与路由器硬件相关的技术主要表现在优化的硬件体系结构、ASIC技术及三层交换技术三个方面。

1．优化的硬件体系结构快速IP路由通常使用ATM方法，采用交叉开关方式实现端口之间的线速（交换机有足够的能力处理最小的数据封包的转发）、无阻塞的互连。

高速交叉开关技术已经十分成熟，在ATM交换机和高速交行计算机中广泛应用。

提示ATM（异步传输模式），在这一模式中，传输信息被组织成信元，同时包含来自某用户信息的各个信元不需要周期性出现，从而实现信息的快速交换。

信元专用于ATM网络，丛原到目标传输是信元，它是一种特殊的数据结构，长度只有53个字节，其中5个字节是信元头，其它为信息段。

2．ASIC技术由于厂商需要降低成本，因此ASIC技术在路由器中得到了越来越广泛的应用。

在路由器中，ASIC可以极大地提高数据转发速度，有的用ASIC做包转发，有的则用ASIC查路由，并且已经有专门用来查找IPv4路由的ASIC芯片。

通常来说，ASIC只用于已经完全标准化的处理，但由于网络的结构和协议变化频繁，因此在相应的网络领域，出现了“可编程ASIC”。

目前，有两种类型的“可编程ASIC”，一种是以3Com公司为主的FIRE（Flexible Intelligent Routing Engine）芯片；另一种是以Vertex Network的HISC专用芯片，后者专门为通信协议处理而设计的CPU，通过改写微代码，使它具有同协议能力。

3．三层交换技术自从Ipsilon制造商在1994年推出一次路由多次交换之后，各大公司也相继推出了各自专有的三层交换技术，在综合所有三层交换技术优势后，国际互联网工程任务组（The Internet Engineering Task Force）终于在1998年推出了性能优越的多协议标记交换（MPLS）。

与“一次路由再交换”技术相比，MPLS多网络结构这一更高层次的三层交换技术解决了三层交换网络流量管理问题，目前这一技术的研究仍在进行。

基于分组TCAM的T比特高性能路由器快速查找更新技术

基于分组TCAM的T比特高性能路由器快速查找更新技术

2021年2月第42卷 第2期计算机工程与设计C O M P U T E RE N G I N E E R I N GA N DDE S I G NF e b .2021V o l .42 N o .2基于分组T C A M 的T 比特高性能路由器快速查找更新技术刘宗宝,赵 鑫,张 力,李之乾,张 琨(中国航天科工集团第二研究院七〇六所,北京100854)摘 要:针对传统T C A M 查找更新方法复杂度高㊁无法满足高性能路由器线速查找转发需求的问题,提出一种基于分组T C A M 的路由查找更新技术㊂介绍T 比特高性能路由器的系统架构,提出基于分组T C A M 的路由查找更新架构,以及基于统计预测的预留表项空间算法,进行路由查找更新算法的设计㊂搭建测试验证环境,采用M A E -W E S T 和M A E -E A S T 路由表项数据,进行线速查找转发处理性能的分析测试㊂关键词:T 比特路由器;分组T C A M ;统计预测;查找更新;预留表项空间方法中图法分类号:T N 915.05 文献标识号:A 文章编号:1000-7024(2021)02-0343-06d o i :10.16208/j.i s s n 1000-7024.2021.02.007收稿日期:2019-10-21;修订日期:2020-11-02作者简介:刘宗宝(1988),男,山东泰安人,博士,高级工程师,研究方向为网络与计算机体系架构;赵鑫(1987),女,北京人,硕士,工程师,研究方向为计算机网络;张力(1985),男,陕西西安人,硕士,高级工程师,研究方向为网络与计算机体系架构;李之乾(1983),男,河南安阳人,硕士,高级工程师,研究方向为计算机体系架构;张琨(1987),男,山东青岛人,硕士,高级工程师,研究方向为计算机体系架构㊂E -m a i l :J A Y 7575@163.c o mF a s t l o o k u p a n du p d a t i n g f o r t e r a b i t r o u t e r b a s e d o nT C A M g r o u ps L I UZ o n g -b a o ,Z H A OX i n ,Z H A N GL i ,L I Z h i -qi a n ,Z H A N GK u n (I n s t i t u t e 706,S e c o n dA c a d e m y o f C h i n aA e r o s p a c e S c i e n c e a n d I n d u s t r y C o r p o r a t i o n ,B e i j i n g 100854,C h i n a )A b s t r a c t :T r a d i t i o n a l l o o k u p s c h e m e b a s e d o nT C A Mu s u a l l y n e e d s c o m p l e x u p d a t e o p e r a t i o n s d u e t o t h e p r e f i x -l e n g t h o r d e r i n gc o n s t r a i n t ,w h i c h c a n n o tm e e t t h ede m a n dof t e r a b i t r o u t e r .Af a s t l o o k u p a n du p d a t i ng m e th o d f o r t e r a bi t r o u t e rb a s e do n T C A M g r o u p sw a s p r o p o s e d .T h e a r c h i t e c t u r e o f t e r a b i t r o u t e r w a s i n t r o d u c e d ,a n d a l o o k u p a n d u p d a t i n g a r c h i t e c t u r e b a s e d o n T C A M g r o u p sw a s d e s i g n e d .W i t h t h e c h a r a c t e r i s t i c s o f p r e f i x d i s t r i b u t i o n ,a n e n t r y r e s e r v e d a l g o r i t h mb a s e d o n s t a t i s t i c a l p r e -d i c t i o nw a s d e s i g n e d .T e s t e n v i r o n m e n tw a s b u i l t t o v e r i f y p e r f o r m a n c e o f t h e p r o po s e dm e t h o dw i t h r e a l d a t aM A E -W E S Ta n d M A E -E A S T .K e y w o r d s :t e r a b i t r o u t e r ;T C A M g r o u p s ;s t a t i s t i c a l p r e d i c t i o n ;l o o k u p a n d u p d a t i n g ;s p a c e r e s e r v e dm e t h o d 0 引 言信息技术的发展推动核心路由器的线速转发率达到40G b ps 以上[1],路由查找是核心路由器实现高性能线速转发的关键技术㊂目前路由查找算法主要有软件查找算法和硬件查找算法,基于软件的路由查找方法需要多次内存操作才能完成路由查找,无法满足高速接口线速转发的要求㊂基于硬件的路由查找算法大多基于T C A M (t e r n a r y c o n t e n t a d d r e s s a b l em e m o r y)[2-4]技术实现,执行速度快,可以在一个时钟周期内完成路由表项的匹配查询,优先级编码器(p r i o r i t y en c o d e r ,P E )从多个匹配结果中选择最长前缀匹配(l o n ge s t p r ef i x m a t c h ,L P M )作为查找结果,因此T C A M 特别适合于高性能路由器,实现快速路由查找和转发㊂但是,传统T C A M 的更新性能较差[5]:路由表是动态变化的并且规模大幅增长,T C A M 中路由表项按照前缀长度降序排列,为保证路由表项的优先级,对路由表项的插入㊁删除等更新操作会造成大量的内存移动[6],最坏情况下的更新算法复杂度为O (N )(N 为T C A M 中的路由表项数量),导致路由查找性能大幅下降,无法满足高性能路由器线速查找转发的要求㊂针对T C A M 路由表项的更新算法国内外学者进行了大量的研究,提出了许多性能优化的算法,参见文献[7-9]等㊂P L O -O P T 更新算法是对选择移动更新算法的改进,即空闲前缀表项从T C A M 的底部移动到了T C A M 的中间,计算机工程与设计2021年因此一次更新操作最多需要L/2次(L是路由前缀的长度)路由表项移动㊂C A O_O P T更新算法把路由表转化为t r i e 树,只对同一条链路(从根节点到叶子节点)上的规则排序[10],一次更新操作最多需要D/2次(D是相互重叠的前缀的最大个数)路由表项移动㊂目前大部分基于T C A M 的路由表项更新算法都要求前缀表项按照前缀长度排序,时间复杂度高,影响了路由查找更新性能㊂为满足高性能路由器数据交换对快速路由查找功能的需求,本文提出了一种基于分组T C A M的T比特高性能路由器查找更新方法㊂1T比特高性能路由器系统架构T比特高性能路由器的系统架构为分布转发㊁集中控制,如图1所示,主要由热备份主控板㊁交换网板和多个接口业务板组成,各板之间通过高速背板总线互联㊂主控板是T比特高性能路由器的核心,完成以太网数据包处理㊁网络管理等功能,并为其它各板提供高精度的时钟源㊂交换网板具有高性能交换芯片,完成T比特级的高速数据包转发㊂接口业务板具有单独的控制系统,支持I P v4㊁I P v6㊁M P L S V P N㊁Q o s/H-Q o s㊁G R E㊁组播V P N等全业务功能㊂图1 T比特高性能路由器系统架构2基于分组T C A M的路由查找更新2.1路由查找更新架构本文提出的基于分组T C A M的路由查找更新架构如图2(a)所示,T C A M被分成几组T C A M1~T C A M m a x,每组内各T C A M表项的前缀互不相交,即T C A M i,jɣT C A M i,k=Ф,因此T C A M i(iɪ{1,m a x})是互不相交路由表项的集合,T C A M i中最多只有一个匹配前缀㊂m a x为路由表项前缀的最大长度,根据网络环境的不同可动态变化㊂由于在执行某项前缀的插入㊁删除等更新操作时,不需要对其它前缀进行操作,因此相比于传统T C A M,本文提出的路由查找更新架构的操作执行速度更快,算法复杂度低,高性能路由器的查找转发效率更高㊂本文提出的架构中还有一个T C A M e x为传统T C A M结构,用于存储无法放在T C A M i中的路由表项㊂选择逻辑基于最长前缀匹配算法(L P M)实现㊂图2基于分组T C A M的高性能路由器查找更新架构T C A M i(iɪ{1,m a x})和T C A M e x采用基于统计预测的预留表项空间设计,如图2(b)所示,灰色部分表示预㊃443㊃第42卷第2期刘宗宝,赵鑫,等:基于分组T C A M的T比特高性能路由器快速查找更新技术留的空间,预留空间大小由前缀的概率密度函数确定,对于T C A M i,前缀长度为m的表项预留空间为n i m= N T C A Mˑp d f m/(m a x+1),前缀为k的表项预留空间为n i k=N T C A Mˑp d f k/(m a x+1),详细计算过程在2.2.2节㊂通过基于统计预测的预留表项空间设计,有效减少了路由表项前缀的插入操作引起的其它表项的移动,路由表项更新效率大幅提升㊂2.2路由查找更新算法2.2.1搜索算法搜索算法基于最长前缀匹配(L M P)搜索技术,具体实现过程为:对于T C A M1~T C A M m a x,每个T C A M i独立地并行执行前缀匹配过程m a t c h(T C A M i,i p_a d d r),其中i p_a d d r为目的I P地址㊂由于T C A M i中的前缀互不相交,因此每个T C A M i中最多搜索到一个与i p_a d d r匹配的前缀;然后从多个匹配的前缀中选择e n t r y[k].l e n g t h 值最大的前缀,相应的e n t r y[k]即为i p_a d d r的路由查找结果,并返回路由转发表中相应的输出端口号(e n t r y [k].o u t p o r t)㊂如果所有T C A M i中没有匹配的前缀,前缀长度e n t r y[i].l e n g t h值为0,根据路由转发表中默认的表项信息进行转发㊂搜索算法的步骤如下:S e a r c h(i p_a d d r)(1)f o r i=1t o e x(2)e n t r y[i]=m a t c h(T C A M i,i p_a d d r)(3)e n d f o r(4)对于满足上述条件的路由表项e n t r y[i](iɪ{1,e x}),根据L M P原则,寻找kɪi,使得e n t r y[k].l e n g t h 值最大(5)r e t u r n e n t r y[k].o u t p o r t2.2.2基于统计预测的预留表项空间算法对于骨干网络,路由表项前缀的统计特性变化较小㊂基于统计预测的预留表项空间算法根据高性能路由器的历史表项数据,计算路由表项前缀的统计分布特性,进行预留表项空间的预测和分配,当有新的表项插入时,直接添加在预留空闲位置㊂算法步骤如下:(1)根据历史表项数据,计算长度为i的前缀的统计概率密度p d f i=N i N,其中N i是历史表项中长度为i的前缀数量,N是前缀的总数量;(2)计算长度为i的前缀的总预留空间大小n i= N T C A Mˑp d f i;(3)T C A M i中为长度为i的前缀预留大小为n i= N T C A Mˑp d f i/m a x+1的空间,路由表项动态更新时,新的路由表项直接插入预留空间内㊂2.2.3插入算法路由转发表中插入一个新的路由表项(前缀为p)的过程如下I n s e r t(p)函数所示㊂首先,从T C A M i~T C A M m a x中寻找出前缀p可以插入的所有T C A M i(iɪ{1,m a x}),要求前缀p与T C A M i中的任意前缀互不相交;如果存在满足上述条件的T C A M i,并且T C A M i中至少有一个空闲表项位置,标志变量a v a i l a b l e[i]值为t r u e;否则,前缀p的预留空间被占用,a v a i l a b l e[i]值为f a l s e㊂如果a v a i l a b l e[i]值为t r u e并且存在多个T C A-M i,插入函数i n s e r t_t o_t c a m()从可用的T C A M i中随机选择一个插入位置;如果a v a i l a b l e[i]值为f a l s e,则T C A M0~T C A M6中不存在可用的空闲表项位置,前缀p 插入传统T C A M e x㊂i n s e r t_t o_t c a m()函数对传统T C A M e x的插入操作需要满足传统T C A M的顺序约束,插入过程需要进行多次的内存移动;而T C A M1~T C A M m a x中的路由表项无顺序约束,因此对T C A M1~T C A M m a x的插入操作可在任意空闲位置执行㊂I n s e r t(p)(1)f o r i=1t om a x(2)I n i t i a l i z e a v a i l a b l e[i]=f a l s e(3)I f(对于任意的前缀e pɪT C A M i,p和e p是不相交的,并且T C A M i中有空余位置)(4)a v a i l a b l e[i]=t r u e(5)e n d i f(6)e n d f o r(7)i f(a v a i l a b l e[i]=f a l s e,对于任意的0ɤiɤm a x)(8)i n s e r t_t o_t c a m(p,T C A M e x)(9)e l s e(10)从a v a i l a b l e[i]中任意选取k,i n s e r t_t o_t c a m(p, T C A M k)(11)e n d i f2.2.4删除算法从转发表中删除前缀p的过程如下D e l e t e(p)函数所示㊂首先,需要寻找哪个T C A M含有前缀p(假设为k);然后,前缀可从T C A M k中删除㊂对于T C A M1~T C A M-m a x,删除过程不需要任何内存移动㊂对于传统T C A M,内存移动次数因更新算法的不同而有差异;如果相邻位置是空闲的,每次删除过程需要至少一次前缀移动操作㊂D e l e t e(p)(1)寻找k,使得pɪT C A M k(2)d e l e t e_f r o m(p,T C A M k)3实验验证与分析为验证本文提出算法的性能,搭建了测试验证环境,如图3所示,由T比特高性能路由器㊁S p i r e n t网络测试仪㊁以太网交换机㊁便携式P C机等组成㊂其中网络性能测试软件使用S p i r e n t公司的T e s t C e n t e rS T P-N11U,版本为v4.33.0086㊂㊃543㊃计算机工程与设计2021年图3 测试验证环境本文采用I P M A 的M A E -W E S T 和M A E -E A S T [11,12]路由表作为仿真数据来源,见表1㊂表1 仿真数据统计前缀数量插入删除M A E -W E S T 35217341141103M A E -E A S T43344342049140图4是数据1和数据2的前缀数量和内存移动次数关系,可以看出,96%的前缀只需要1次内存移动,仅有不到4%的前缀需要2次以上的内存移动㊂图4 前缀数量和内存移动次数关系分别采用本文提出的算法以及经典的P L O _O P T 算法㊁C A O _O P T 算法,计算M A E -W E S T 和M A E -E A S T路由表每次更新操作(插入㊁删除)的平均内存移动次数,结果见表2和表3㊂从对比结果可以看出,由于本文算法的路由表项没有顺序约束和优先级编码器,并且进行了预留表项空间的设计,对于插入和删除操作,本文算法的平均内存移动次数远小于P L O _O P T 算法和C A O _O P T 算法㊂由于传统T C A M e x 的存在,本文算法的插入操作和删除操作所需的平均内存移动次数不相同㊂需要指出,该算法以计算概率密度函数为代价,通过减少内存移动次数降低了路由表项更新的时间复杂度,但相比于频繁的内存移动操作,概率密度函数的计算复杂度较小㊂表2 不同算法每次更新操作的平均内存移动次数(M A E -W E S T )分组T C A M P L O _O P TC A O _O P T 插入删除0.210.163.561.05表3 不同算法每次更新操作的平均内存移动次数(M A E -E A S T )分组T C A M P L O _O P TC A O _O P T 插入删除0.190.164.11.02对采用本文提出的算法的T 比特高性能路由器的转发性能(吞吐量㊁时延)进行测试,测试中选用的数据包长分别为64㊁128㊁256㊁512㊁1024㊁1280㊁1518,测试时间为30s ,端口流量负载为100%,网络的转发方式选择F u l l m e s h e d 全双工对发㊂运行S pi r e n t 公司的T e s t C e n t e r R F 2544测试集,测试界面如图5所示㊂测试的T 比特高性能路由器的吞吐量及时延分别如图6㊁图7所示㊂可以看出,在以上7种数据包大小时,路由器的测试吞吐量与理论最大吞吐量吻合,包大小为1518b y t e s 时可达最大80G b ps 的线速转发,报文的丢包率为0㊂路由器的转发时延最大为6.12μs (包大小1518b yt e s )㊂测试结果表明,本文提出的算法可有效提高T 比特高性能路由器的线速查找转发性能㊂4 结束语针对传统T C A M 查找更新方法时间复杂度高㊁效率低的问题,以及T 比特路由器对高性能查找转发的需求,本文提出了一种基于分组T C A M 的路由查找更新架构,T C A M 被分成几组互不相交的路由表项的集合,路由表项不需要按优先级进行排序;提出了基于统计预测的预留表项空间算法,预留空间大小由前缀的概率密度函数确定,根据历史表项数据分配相应的空间大小㊂搭建了测试验证环境,测试结果表明,基于本文设计的T C A M 的内㊃643㊃第42卷 第2期 刘宗宝,赵鑫,等:基于分组T C A M 的T 比特高性能路由器快速查找更新技术图5 T e s t C e n t e r测试界面图6包转发吞吐量测试比较图7 系统转发时延比较存移动次数有效降低,T 比特高性能路由器可达最大80G b p s 的线速转发,转发时延最大为6.12μs ㊂因此,本文提出的基于分组T C A M 的T 比特高性能路由器查找更新技术,可有效提高T 比特路由器的查找转发性能,支撑未来网络发展的需要㊂由于T 比特路由器的动态变化特性,基于时变概率密度函数的预留表项空间算法是下一步的研究方向㊂参考文献:[1]Z h a n g B i n ,Q i n D o n g h o n g,D i a o X i n c h u n ,e ta l .E f f i c i e n t s e a r c h i n g w i t h aT C A M -b a s e d p a r a l l e l a r c h i t e c t u r e [J ].J o u r -n a l o f I n t e r n e tT e c h n o l o g y,2018,19(7):2215-2226.[2]M a W a n l i ,Z h a n g J i a n w e i ,T e n g F e i .A h yb r i dsc h e m ef o r r o u t i n g l o o k u p w i t h f a s t u pd a te sb a s e do nT C A M s [C ]//2n d I E E EI n t e r n a t i o n a lC o nf e r e n c eo n C o m pu t e ra n dC o m m u n i c a -t i o n s .I E E E ,2016:1985-1991.[3]W A N G H u i ,L I X i a o g e ,Z H A N G B i n ,e ta l .S u r v e y on T C A M -b a s e d p a r a l l e l I Pr o u t e l o o k u p s c h e m e [J ].C o m p u t e r A p pl i c a t i o n s a n dS o f t w a r e ,2016,33(7):139-144(i nC h i -n e s e ).[王辉,李晓歌,张宾,等.基于T C A M 的并行路由查找方案综述[J ].计算机应用与软件,2016,33(7):139-144.][4]S y e dF ,U l l a hZ ,J a i s w a l M K .F a s tc o n t e n tu p d a t i n g a l go -r i t h mf o r a n S R A M -b a s e dT C A Mo n F P G A [J ].I E E EE m b e d -d e d S ys t e m s L e t t e r s ,2017,10(3):73-76.[5]Z H A N G W e n y u a n .D e s i g n a n d i m p l e m e n t a t i o n o f T C A Mu pd a -t i n g a l g o r i t h m [D ].Be i j i n g :U n i v e r s i t y o fC h i n e s eA c a d e m y of S c i e n c e s ,2016:1-9(i nC h i n e s e ).[张文远.T C A M 更新算法的设计与实现[D ].北京:中国科学院大学,2016:1-9.][6]M A W a n l i .R e s e a r c ha n di m p l e m e n t a t i o no fe f f i c i e n tr o u t i n gs c h e m eb a s e do n T C A M [D ].D a l i a n :D a l i a n U n i v e r s i t y of T e c h n o l og y,2017:1-24(i n C h i n e s e ).[马万里.基于㊃743㊃计算机工程与设计2021年T C A M的高效路由方案研究与实现[D].大连:大连理工大学,2017:1-24.][7]A y y i l d i zN,S c h m i d tE G,G u r a n H C.S-D I R E C T:S c a l a b l ea n dd y n a m i c a l l y r e c o n f i g u r ab l e T C A M a rc h i t e c t u r ef o rh i g h-s p e ed I P l o o k u p[J].T h eC o m p u te r J o u r n a l,2015,58(6): 1443-1455.[8]C h a n g D Y,W a n g P C.T C A M-b a s e dm u l t i-m a t c h p a c k e t c l a s s i-f i c a t i o n u s i ng m u l t i d i m e n s i o n a l r u l e l a y e r i n g[J].I E E E/A C M T r a n s a c t i o n s o nN e t w o r k i n g,2015,24(2):1125-1138.[9]V a g i o n a sC,M a n i o t i sP,P i t r i sS,e ta l.I n t e g r a t e do p t i c a lc o n t e n t ad d re s s a b l em e m o r i e s(C A M)a n do p t i c a l r a n d o ma c-c e s sm e m o r i e s(R A M)f o r u l t r a-f a s t a d d r e s s l o o k-u p o p e r a t i o n s[J].A p p l i e d S c i e n c e s,2017,7(7):1-18.[10]H s uP C,S u nY H.M u l t i-i n h e r i t e d s e a r c h t r e e f o r d y n a m i c I P r o u t e r-t a b l e s[J].I E E E T r a n s a c t i o n so nC o m p u t e r s,2017, 66(1):114-126.[11]M e r i t N e t w o r k s,I n c.T h e I P M A(i n t e r n e t p e r f o r m a n c em e a s u r e m e n t a n da n a l y s i s)p r o j e c t[E B/O L].[2020-01-30].w w w.m e r i t.e d u/i p m a.[12]X UZ h o u b o,H U K u i,C H A N G L i a n g,e t a l.R o u t i n g l o o-k u p a l g o r i t h mb a s e d o n a l g e b r a i c d e c i s i o nd i a g r a m[J].C o m-p u t e r E n g i n e e r i n g,2017,34(3):99-104(i nC h i n e s e).[徐周波,胡魁,常亮,等.基于代数决策图的路由查找算法[J].计算机工程,2017,34(3):99-104.]㊃843㊃。

计算机网络基础学习路由和交换技术的原理

计算机网络基础学习路由和交换技术的原理

计算机网络基础学习路由和交换技术的原理计算机网络是信息时代的重要基础设施，而计算机网络中的路由和交换技术是网络通信中至关重要的环节。

本文将介绍路由和交换技术的原理、分类以及其在计算机网络中的应用。

一、路由技术的原理和分类路由技术是实现不同网络之间互联通信的关键技术，其原理是通过判断目标网络地址，将数据包从源网络传输到目标网络。

路由器是实现路由技术的关键设备。

1. 静态路由和动态路由静态路由是指由网络管理员手动配置的路由表，它通过手动设置静态路由表项来确定数据包的转发路径。

这种方式简单易懂，适用于较小的网络环境。

动态路由则是通过路由协议自动学习网络拓扑和更新路由表，以实现自动的数据转发。

常见的动态路由协议有RIP（Routing Information Protocol）和OSPF（Open Shortest Path First）。

动态路由能够适应复杂的网络环境，并提供更好的可伸缩性和容错性。

2. 内部网关协议（IGP）和外部网关协议（EGP）内部网关协议用于同一个自治系统（AS）内部的路由选择，常见的内部网关协议有OSPF（Open Shortest Path First）和IS-IS （Intermediate System to Intermediate System）。

而外部网关协议则用于互连不同自治系统的路由选择，常见的外部网关协议是BGP（Border Gateway Protocol）。

二、交换技术的原理和分类交换技术是在本地网络中实现数据包转发的重要技术，常见的交换技术包括局域网交换和广域网交换。

1. 局域网交换局域网交换主要通过交换机实现，其原理是基于MAC地址进行数据帧的转发。

当数据包到达交换机时，交换机会查找目标MAC地址，并将数据包直接转发到目标地址所连接的端口上，从而实现快速的数据传输。

2. 广域网交换广域网交换是通过路由器实现的，其原理是基于IP地址进行数据包的传递。

路由交换技术基础知识

路由交换技术基础知识

路由交换技术基础知识路由交换技术是现代计算机网络中的重要概念，它是实现网络连接和数据传输的关键。

在本文中，我们将介绍路由交换技术的基础知识，包括路由器、交换机、路由表以及路由选择算法等内容。

一、路由器的概念和功能路由器是计算机网络中的一种设备，主要用于实现数据的转发和传输。

它通过查找目标地址并根据路由表进行转发选择，将数据包从源地址传输到目标地址。

路由器在网络中起到了连接各个子网和传输数据的关键作用。

除了传输数据包的功能，路由器还具有一些其他的功能，比如网络地址转换（NAT）、QoS（Quality of Service）等。

通过网络地址转换，路由器可以将内部网络的私有IP地址转换为公网IP地址，实现内部网络和外部网络的连接。

QoS功能可以根据网络连接的需求，为不同的数据流分配带宽和优先级，保证网络服务的质量。

二、交换机的概念和功能交换机是计算机网络中的另一种设备，用于实现局域网内部的数据交换。

它可以根据MAC地址识别数据包的目标设备，并将数据包仅转发到目标设备所在的端口，从而实现数据的高效传输。

交换机具有避免网络冲突、提高网络性能、实现安全隔离等功能。

通过避免网络冲突，交换机可以避免数据包在网络中的碰撞，提高数据传输的效率。

通过提高网络性能，交换机可以提供更高的数据传输速率和带宽，满足用户对网络性能的需求。

通过实现安全隔离，交换机可以将网络分割成多个虚拟局域网（VLAN），实现不同网络之间的隔离和安全控制。

三、路由表的概念和作用路由表是路由器中的一种数据结构，用于存储路由器所知道的网络之间的连接关系。

每个路由表条目包含了目标网络的网络地址、下一跳路由器的IP地址以及用于选择下一跳路由器的路由选择算法。

路由表的作用是指导路由器在传输数据时选择最佳路径。

路由器通过查找目标地址，并根据路由表中的信息进行转发选择，将数据包沿着最佳路径传输到目标地址所在的网络。

路由表的更新是由路由选择协议来完成的，路由选择协议可以根据网络拓扑的变化动态地更新路由表信息。