IP路由查找（共7篇）
IP路由查找 篇1
1 MP RM-WOP (Modifie d pre fix ra nge ma tch s che me for IP a ddre s s lookup without pre computa tion) 产生背景
MPRM-WOP是一种基于按前缀范围检索的算法。Butler Lampson等在[1]中提出了第一个按前缀范围检索算法。因为前缀之间可能存在着包含关系, 这些包含关系是由实际的网络应用产生的, 如多穴 (Multi-homed) 主机, 或负载均衡等。在[1]中需要预先计算并保存信息来完成最长前缀匹配, 如果目的前缀在地址空间上分割的小区间, 每个基本区间记为Ik (k>0, k∈Z) , 那么对每个Ik都需要预先计算出落入该区间的数据报的最长匹配前缀。由于[1]需要预计算, 导致了该算法在无法支持动态更新。作者基于对[1]的研究发现目的前缀的包含关系是导致预计算的必要因素, 如果解决了目的前缀的包含关系, 预计算就可以避免, 进而动态更新问题就可以想办法解决。
本文按照该将被包含前缀划分成层次的思路, 提出了一种新的机制来解决路由地址查找问题。首先将所有前缀按包含关系划分成层次, 在每一个层次的前缀集合里, 没有任何一个前缀包含 (或被包含) 其他前缀。然后按照该机制设计相应的支持快速查找及动态更新的数据结构, 最后产生相应的查找算法。
2 MP RM-WOP算法的基本机制
MPRM-WOP算法的基本机制的基本构想是, 首先将所有第1层被包含前缀, 划分成不相交前缀集合, 并将每个不相交前缀集合都用同一种适宜于快速查找与更新的数据结构来表示, 同时, 每个不相交前缀集合中的每个基本元素--路由前缀都应包含一个索引, 这个索引用来指向所有该前缀所包含的前缀。递归地, 在由索引指向的所有被包含前缀又可以按相同的方法划分成不相交的前缀集合, 同时使用该数据结构递归地表示这些被划分出来的更小的不相交前缀集合。
如图1中所示, 对左边的前缀按以下步骤建立起右边所示的数据结构:
所有第0层的前缀组织称集合A;
所有第一层被包含前缀Prefix2和Prefix7, 划分成不相交的前缀集合, 它们都属于集合B{Prefix2, Prefix7}, 同时Prefix2维持一个指向它的被包含前缀集合{Prefix3, Prefix4, Prefix5, Prefix6}的索引, Prefix7也维持一个指向它的被包含前缀集合{Prefix8}的索引;
对Prefix2的被包含前缀集合{Prefix3, Prefix4, Prefix5, Prefix6}进行下一个层次的不相交划分, {Prefix3, Prefix6}被划为集合C, 同时Prefix3维持一个指向它的被包含前缀集合{Prefix4, Prefix5}的索引, Prefix6没有被包含前缀集合;
对Prefix3的被包含前缀集合{Prefix4, Prefix5}进行下一个层次的不相交划分, 由于{Prefix4, Prefix5}不能再划分, 并且该集合中没有任何前缀有指向被包含前缀集合的索引, 因此生成集合D{Prefix4, Prefix5}, 并返回递归调用的上一层, 5) 执行对集合Prefix7的被包含前缀集合{Prefix8}的划分, 生成集合E{Prefix8}。
3 MP RM-WOP算法的数据结构设计
如上小节描述, 我们需要选取一种适宜于快速查找与更新的数据结构来储存不相交前缀集合里的前缀, 基于[1]的研究表明多分支的查找树有利于利用计算机的层次存储器特性来提供更高速的查找, 同时B树作为一种高度平衡的平衡树, 能保证最坏情况下的O (Lg N) 的时间复杂度, 因此作者也选取B树作为基本的数据结构来表示不相交前缀集合里的前缀, 同时由于没有前缀包含关系的存在, 预计算问题也不复存在, 因此在单个的B树结构中的动态更新也能在O (Lg N) 时间内完成。
该结构的根节点是一棵存储了所有第0层前缀信息的B树。
4 MP RM-WOP算法的查找
如图2所示, 当到来一个如左边所示的数据报时, 在MPRM-WOP算法中的查找过程如右图所示, 步骤如下: (1) 在第0层的前缀B树Btree A中, 目的IP与Prefix1匹配 (在图中用黑色方框显示) ; (2) 通过Prefix1的索引跳转到被它包含的前缀前缀B树Btree B; (3) 在前缀B树Btree B中目的IP匹配上Prefix2; (4) 通过Prefix2的索引跳转到被它包含的前缀前缀B树Btree C; (5) 在前缀B树Btree C中目的IP匹配上Prefix3; (6) 通过Prefix3的索引跳转到被它包含的前缀前缀B树Btree D; (7) 在前缀B树Btree D中目的IP匹配上Prefix4, 并且Prefix4没有下一级索引, 查找结束, 返回Prefix4的下一跳端口号。
值得一提的是, 在每一次B树的匹配中, 由于消除了包含关系, 精确的值得匹配就可以找到在该B树种与目的IP匹配的前缀。
参考文献
[1]Butler Lampson, V.Srinivasan, and George Varghese.IP Lookups Using Multiway and Multicolumn Search.IEEE/ACM Transactions on Networking, 1999, 7 (3) :324-334.
路由查找算法研究与分析 篇2
当前，因特网的规模、链路速度、带宽、流量等都呈指数级增长，这对路由器中IP路由查找算法对大容量路由表处理的适应性以及报文转发查表的能力提出了更高要求。路由器是构成因特网的中间结点，其转发性能决定了因特网的整体性能。路由器的发展面临三个难题：交换结构、缓冲调度、报文处理。随着半导体技术和光交换技术的发展，分组交换可以在很高的速率下得到实现。因此，IP路由查找是实现高速分组转发的关键，其优劣直接影响了当前和未来因特网网络的整体性能[1]。本文首先对现有的典型IP路由算法进行介绍，总结其优缺点，并基于此提出一种基于多分枝trie树的路由查找算法。
2 常用的路由查找算法分析
2.1 硬件算法
目前使用最多的硬件实现方法是使用CAM (Content AddressableMemory) 内容可寻址存储器[2]，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。
另一种基于硬件的改进CAM算法是基于TCAM (三值CAM) 的算法[3]。在进行搜索的时候，所有的TCAM项都需要同时进行匹配，在有多个匹配项时，TCAM规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM具有速度快、实现简单的优点，但它也具有几个不足之处： (1) 单位比特昂贵; (2) 容量小; (3) 并行匹配导致功耗很大; (4) 更新复杂。
2.2 软件算法
2.2.1 二进制trie树[4]
IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie表示前缀并不存储在Trie的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。如图1所示就是二进制trie树结构来表示的地址前缀结构。
IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。
2.2.2 多分支trie树
直接用二进制trie树的方式来实现路由查找，查找一个比特即对二叉树向下遍历一个深度，这样会导致查找速度太慢。如果一次从目的IP中取出多个比特，就可以开有效的减少查找过程中的存储访问次数。多分支trie树的查找过程与二进制trie树的查找过程类似，在每次结点访问过程时，记录下到目前为止匹配上的最长地址前缀，直到到达叶子结点搜索过程结束。例如，如果每次检查地址的4个比特，那么IPv4地址查找最多只需要8次存储访问就可以了。图2是和前面图1中采用同样IP前缀表生成的多分支trie树结构图。
每次从目的IP中取出的比特长度K称为查找步长。由于存储树中的前缀长度各不相同，如果每次检查步长为K的比特数，则小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配。解决的方法是将无法匹配的前缀扩展为同K相同或者和K的整数倍。例如，K=3时，可以将1*扩展为100*、101*、110*、和111*。这种采用扩展前缀进行查找多分支trie树的算法称为可控前缀扩展算法。
当然，这种地址前缀扩展的多分支trie树在减少访存次数的同时也带来了消耗存储空间增大以及更新复杂的问题。假设步长K=5，那么就有4/5的IP前缀需要扩展(假设IP前缀长度均匀分布)，最大的扩展长度前缀都要进行扩展到24个，这样就消耗了大量的存储空间。此时要更新某个IP前缀，最多需要更新24个结点。
文献[5]中列举了多分支trie树算法取不同步长时的实际运行性能比较。当步长K较大时，多分支trie树的深度相对较小，因此查找性能较好，但是需要耗费较多的存储空间。当步长K较小时，多分支trie树的深度相对较大，查找性能较差，但是存储空间需求较小。可见，对于多分支trie树来说，查找速度和存储容量是一对互相矛盾的性能指标。
3 路由查找算法的衡量标准及性能提高方法
在评价一种地址查找算法的优劣时，必须综合考虑以下性能[6]：
3.1 查找速度。
一般所使用的指标是每秒查找分组数。考虑到各种方案在测试时所使用硬件不同、测试条件的不同会对测试结果产生很大影响，所以使用一次查找、特别是最差情况下一次查找需要进行的存储器访问次数作为衡量速度的标准更为合理。
3.2 所需存储器的大小。
实施方案所需的存储器应尽可能的小，在一定的空间中存储尽可能多的路由前缀，以便于硬件实现和满足不断增长的前缀数目的需要。
3.3 路由表更新的开销。
包括路由表周期更新开销和表项插入、删除操作开销两部分。路由信息的变化所引起的查找性能的下降应尽可能的小。
提高路由查找速度的主要途径有3个[7]：(1)减少存储器访问次数;(2)减小转发表的存储空间;(3)采用硬件流水并行处理。只采用一种方法或者算法所得到的查找性能受到一定的限制，既使能够取得很快的查找速度，往往也存在转发表更新困难或者扩展性差等问题。所以很多算法都是把这3个方向上的改进结合起来的结果。
4 一种改进的多分支trie树算法
我们提出一种多分支trie树改进算法。在多分支trie树结构基础上，不需要进行前缀扩展。假设检查步长为K的比特数，为解决小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配问题，把小于K或者不是K整数倍的前缀挂载到K的整数倍结点上，以整数倍结点为根结点，组成一个大的中间结点。即，中间结点之间采用多分支步长查询，中间结点的内部使用二进制trie树来表示。
图3列举了步长K=3时，某个中间结点的表示方法。前缀100110是K的整数倍结点，即中间结点。1001100, 1001101, 10011010都不是K的整数倍结点，把他们挂载在100110的中间结点上。图4是使用前面的IP前缀表生成的结构图。
在路由查询时，使用步长为K访问中间结点，找到中间结点后，以步长为1访问中间结点内部。一个长度为N的前缀，所需要的访存次数为N/K的结果加上N/K的余数。以步长K为3为例，假设前缀长度N为11，那么访存次数为3+2=5次。最坏情况下，IPv4地址前缀最长为32，访存次数为10+2=12次，仅比原来的多分支trie树的10次访存多2次，而又远少于二进制trie树的32次访存，这就保留了原来多分支trie树查询速度快的优点。
同时，普通的多分支trie树，对于前缀长不是整数倍的结点，要进行前缀扩充，最多扩充为2K-1个，占用了大量的存储空间，而本算法于没有对前缀进行扩展，占用空间小;而且更新结点不需要涉及到其他结点，和二进制trie树路由表更新的开销其实是一样小的。
5 结束语
本文在分析传统路由算法的基础上，提出了一种基于多分支trie树的路由查找算法。该保留了多分支trie树访存次数少，查询速度快的特性，并具有占用存储空间不大，更新开销小的特点，对IPv4和IPv6地址都可以使用。由于使用硬件实现往往能使得路由查找算法性能得到数量级的提升，接下来的工作可以在硬件实现技术上进行研究。
摘要：随着互联网络链路速率的不断提高, 路由查找已成为路由器报文转发的瓶颈。本文首先介绍和分析了路由器中广泛使用的各种典型IP路由算法方法, 并提出一种基于多分枝trie树的改进路由查找算法。该算法保留了多分支trie树访存次数少, 查询速度快的特点, 并具有占用存储空间少, 更新开销小等特点, 对IPv4和IPv6地址都可以适用。
关键词：因特网,路由查找,最长前缀匹配,trie树
参考文献
[1]Marc Friedman, AlonLevy, Todd Millstein.NavigationalPlans for Data Integration[C].Proc of t he16t h National Confon Artificial Intelligence (AAAI'99) [C].1999.6:72-73.
[2]A MCAULEY, P FRANCIS.Fast Routing Table Lookup using CAMs[J].Proc.IEEE INFOCOM1993, Vol3, pp1382-1391, San Francisco, USA.
[3]吴彤, 杨嗣超, 诸鸿文.路由表快速查找算法[J], 通信技术, No4, 2000:52-59.
[4]刘永锋, 杨宗凯.高速路由器中基于树型结构路由查找算法的研究与实现[J].计算机工程与科学.vol.26, No1, 2004:77-80.
[5]徐格, 吴建平, 徐明伟等.高等计算机网络-体系结构、协议机制、算法设计与路由器技术[M], 机械工业出版社, 北京, 2006:522-544.
[6]谭明锋, 高蕾, 龚正虎, IP路由查找算法研究概述[J].计算机工程与科学.vol, 28, No6, 2006:87-91.
IP路由查找 篇3
随着网络带宽的急剧增加,网络的链路速率提升到40Gbit/s,甚至更高,因此应用高性能的多核处理器硬件平台和高速的路由查找算法,设计出满足网络性能要求的路由器显得非常必要。传统的单核处理芯片的处理能力受到主频和功耗等因素的制约[1],在性能上难以满足日益增长的网络数据处理要求。高性能的多核处理器在数据处理过程中能够实现并行处理,并且具有网络延时小、数据吞吐量大等特点,在当前的高端路由器中有着一定的应用范围。但是,传统的基于RadixTrie(基数排序树)、多分支Trie(字典树)和分段地址等的路由查找算法多应用在串行数据流处理的单核处理器中,这些算法应用到多核处理器后,由于并行的数据处理容易形成路由资源竞争,造成数据“瓶颈”,使得多核处理器的并行处理能力无法完全发挥,造成极大的资源浪费。而路由查找的专用芯片TCAM(三态内容寻址存储器),由于其价格昂贵、路由表项更新复杂,不适合广泛应用于一些对成本敏感的路由器中。因此在多核处理 器平台下,设计并实 现一种基 于SDRAM(同步动态随机存取存储器)的快速路由查找算法显得尤为重要。
1基于分割多分枝Trie树的并行路由查找算法
多分枝Trie树[2]是在二进制Trie树的基础上,一次存储IP前缀中的多个比特位。它的查找过程与二进制Trie树类似,即在每次节点访问过程中,记录下到目前为止匹配上的最长地址前缀,直到到达叶子节点搜索过程结束。由于存储树中的前缀长度各不相同,如果每次检查步长K(即每次从目的IP中取出的比特长度)的比特数,则小于K或者不是K整数倍的前缀将无法与多分支Trie树的某个节点匹配。通常采取扩展前缀查找的方法来解决此问题。
1.1基于多核处理器的并行算法思想
传统的路由查找算法大多针对单核处理器,应用到多核处理器中时,由于并行处理,容易形成共享资源间的竞争,造成数据“瓶颈”。当处理的路由条目
较多时,多个核可能同时在对某一节点进行操作,从而导致查找失败。当路由条目比较少时,只需要一个或者几个核去查找,而其他核因分配不到资源处于等待状态,对处理器资源就造成了一定的浪费。本文通过对多分枝Trie树和多核处理器任务调度特点进行研究,提出并实现了一种基于多分枝Trie树的并行路由查找算法。
本算法的思想是,将传统的多分枝Trie树根据处理器的核数分割成若干子树,一个核只在它对应的子树上操作,如图1所示。更新路由表时,同样将IP前缀从高位到低位分成对应的若干段,每一段到对应的子树中更新,如果子树中存在相同的IP段,则不做任何操作;否则,在对应的子树中添加该IP段的节点。对某一IP进行路由查找时,将IP分割成相应的若干段,分别到对应的子树中匹配,从第一棵子树开始,在规定前缀位数的子树上匹配成功,则查找成功,否则查找失败。
1.2分割的多分枝Trie树的子树设计
子树采用多分枝Trie树的存储结构,但不需要前缀扩展,即以步长K的整数倍节点为根节点,组成一个大的中间节点。中间节点之间采用多分支步长查询,中间节点内部使用二进制Trie树来表示。假设检查步长为K比特,小于K或者不是K整数倍的前缀,无法与多分支Trie树某个节点匹配,则把小于K或者不是K整数倍的前缀挂载 到K的整数倍节点上。图2是步长K =3时,某个中间节点的表示方法。其前缀100是K的整数倍节点,即中间节点。1000,1001,10010都不是K的整数倍节点,把它们挂载在100的中间节点上。
基于分割多分枝Trie树的并行路由查找算法流程如图3所示,多个核在对应的子树中同时匹配后,返回各自的匹配结果,根据每棵子树返回的匹配结果,判断是否查找成功。在子树中,对需要匹配的02IP段进行判断,看是否为子树步长的整数倍,若不是步长的整数倍,则采取中间节点的方式查找,并返回匹配结果。
并行路由查找算法流程图
假设为IPv4查找,硬件处理器为8核,则可将图4中的前缀树分割成8棵子树,每棵子树对应的查找位数为4位。子树的步长设置为2,则每棵子树的深度为2,如图4所示。子树1存放这些IP前缀的前四位,分别为:0*、1*、011*、100*、0100*、1100*、1101*、1110*、1111*;子树2存放IP前缀的5~8位,分别为:0*、0010*、0011*;依此类推(由于图4中最长前缀为8位,因此后面对应的子树没有列出),子树8存放8个IP前缀的29~32位。当前缀L不是步长K的整数倍或者小于K时,采取中间节点的方式,即先找到对应的中间节点,然后按步长为1访问中间节点内部的节点。例如,在图4中,要匹配前缀011*,在子树1中,按照步长为2,先找到01的中间节点,然后以该中间节点为根节点,按步长为1遍历子节点,找到下一个节点C,则匹配成功。如果要匹配前缀0100001*,则先将前缀分成两部分,第一部分为前四位0100,在对应的子树1中查找;第二部分为后三位001*,在对应的子树2中查找。在子树1中0100匹配成功,在子树2中,由于查找位数为3,不是步长2的整数倍,需要采用中间节点的方式查找,即先找到00的中间节点,然后按步长为1依次遍历各子节点,发现00的节点下并无步长为1的子节点,在子树2中匹配失败,则前缀为0100001*时查找失败。
对于IPv4地址,前缀最长为32位,假如是8核处理器,可以将IP前缀分成8棵子树,每棵子树查找4位,子树步长K取2,则在最坏情况下,单棵子树查找3位,需要访问内存次数为1+1=2,总次数最多为8次。对于IPv6地址,最坏情况下单棵子树查找15位,需要访问内存次数为7+1=8。同时,普通的多分枝Trie树对前缀不是步长K整数倍的节点需要扩充前缀,最多扩充2k-1个,将占用大量的存储空间,而本算法采用先查找中间节点的方式,没有扩展前缀,占用空间小。更新节点不涉及到其他节点,与二进制Trie树路由表更新节点的开销相同。并且算法中每个核负责查找对应的子树,核与核之间不存在共享某棵子树,因此避免了以往并行算法中因多个核共享一棵树而带来的资源竞争问题。
2实验与结果分析
影响路由查找算法性能的主要因素包括算法的时间复杂度、空间复杂度和路由更新复杂度[3,4]。由于采用分割Trie树的数据结构,时间复杂度与路由更新复杂度基本相同,因此着重对路由查找的时间复杂度进行了分析,空间复杂度则通过内存开销来体现。本实验在高端路由器上进行,路由器的多核卡采用10核处理器,SDRAM容量为8G;实验仪表为SpirentTestCenter。分别采用传统的多分枝Trie树和分割的多分枝Trie树这两种并行路由查找算法作对比实验。
2.1路由查找时间复杂度
考虑到不同的测试环境会对测试结果产生很大的影响,一般把最坏情况下一次查找的时间复杂度作为衡量速度的标准。假设子树个数为N,单棵子树最大的存储位数为W ,取步长为K进行查找,最坏情况下 查找单棵 子树的时 间复杂度 为O(logKW),总时间复杂度为N*O(logKW)。二进制Trie树在最坏 情况下的 时间复杂 度则为N*O(W),多分枝Trie树为O(logK(N*W))。
表1和表2分别列出了两种算法在IPv4和IPv6下的延时数据。发送的数据包大小为128字节,路由表中的路由条目为50000条,分别注入不同速率的流量,并测出流量的延迟时间。从表中可以看出,数据流量较小时,由于在SDRAM的一个时钟周期内,多个核同时查找各自的子树,分割的多分枝Trie树算法明显快于传统的多分枝Trie树算法,且IPv4和IPv6的数据延迟相差不大;当数据流量较大时,这两种算法的查找效率基本持平,但在IPv6查找上,分割的多分枝Trie树比传统的算法数据延迟要小。
2.2路由表内存开销
内存的耗损统计主要包括树的节点和路由表项占用的内存。因为在树的每个叶子节点上存放这个路由的前缀和下一跳信息,所以整个算法中内存开销是由树的叶子节点个数决定的。由于传统的多分枝Trie树算法需要扩展前缀,尤其是IPv6地址,扩展后叶子节点较多,因此内存开销很大。而分割的多分枝Trie树算法采取了中间节点的方式,故不需要前缀扩展,极大地减少了内存空间的占用。这两种算法的内存使用情况分别如图5和图6所示。
3结束语
IP路由查找 篇4
3G时代的数据业务迅猛增长, 传统的传输网络已经很难适应[1,2], 为了适应新的网络需求, PTN (分组传输网络) 随即出现。PTN作为一种面向分组的传送网络, 具有端到端连接、多业务支持、低成本、高QoS (服务质量) 、高效的带宽管理机制等优点[3,4,5]。高带宽多媒体应用的涌现, 导致网络数据量的急剧增加, 带来了带宽的急剧消耗和网络拥挤问题。这对PTN芯片的转发容量、速率、拥塞避免和流量管理等方面提出了更高的要求。IP组播查找电路作为PTN芯片中转发单元的核心电路, 它的查找速度及延迟决定了转发单元的工作频率和转发延迟。PTN芯片中的IP组播查找通常需要根据VLAN (虚拟局域网) 表的内容确定组播数据的输出端口, 而一次调度只能将组播数据输出到一个目的端口, 这就需要大量的存储资源来记录当前组播的扫描位置, 以便下次调度到该队列时, 能够根据记录的扫描位置继续查找下一个组播输出端口。另一方面, 在进行目标端口扫描时, 需要完成最多64位的bitmap图的查找、比较操作, 所以实现查找功能需要用大量的逻辑电路, 因此应该尽量降低查找组合电路的延迟。
为了提高PTN芯片中IP组播查找电路的工作速率, 同时降低电路设计的复杂度, 本文采用流水线结构, 利用RAM (随机访问存储器) 记录查找中间状态信息等技术, 完成了对IP组播查找电路的设计。所设计的IP组播查找电路能够根据要求从VLAN表中正确地查找到输出端口信息, 并将该信息发送给下一级处理单元, 最终电路设计在Altera系列FPGA (现场可编程门阵列) 开发板EP4SGX230KF40C2ES上进行了验证。
1 设计与实现
IP组播查找电路的主要功能是通过顶层的接口完成Vlan表和Group表的配置, 同时, 对三层组播包进行IP组播查表, 查找出该组播包的下一跳地址, 并随组播包一起发送到调度模块。因此将IP组播查找电路分为第一次请求判断模块、Vlan地址选择模块和输出端口扫描模块3个部分, 如图1所示。
当接收到Ipmc查找请求信号Ipmc_req后, 首先判断该请求是否为第一次请求, 如果是, 将请求状态寄存器相应位的值置1, 根据Group_ptr和Ipmc_req_num信息查找Group表, 得到14位的Vlan地址信息;如果不是, 根据Ipmc_req_num信息查找INF_RAM缓存, 得到20位的数据信息, 其中包含了Vlan地址信息。然后, 根据得到的Vlan表的地址信息读取出IP组播包的Vlan索引值, Vlan索引值有模式0和模式1两种, 针对不同的索引模式进行扫描, 得到下一跳地址, 进而记录当前的扫描位置和Vlan表项地址, 并将纪录值写入到对应的信息存储RAM中, 最后判断当前的查找是否结束, 如果结束, 将请求状态寄存器对应位的值置0。
1.1 第一次请求判断模块
第一次请求判断模块的主要功能是接收IP组播查找请求, 并根据目的端口号、Impc_index和请求状态寄存器的内容, 首先判断是否为第一次请求, 如果是, 则将请求状态寄存器相应位的值置1, 并根据请求的地址从Group表中查找到Valn表的地址;如果不是, 则根据请求地址, 从信息存储RAM中读取出Valn表地址以及扫描标识。第一次请求判断模块的电路实现结构图如图2所示。
1.2 Vlan地址选择模块
Vlan地址选择模块的主要功能如下:根据第1次查表的结果, 如果是第一次请求, 则查找到的是Vlan_ptr信息, 反之, 得到的是current_ptr信息;然后根据第一次请求判断的结果进行二选一, 得到Vlan表的查找地址信息, 查找Vlan表, 得到Vlan表的88位数据信息。Vlan地址选择模块的结构如图3所示。
其中, 信息存储RAM主要用于存储从Vlan中读取出来的数据信息, 以便完成后续的查表和发送下一跳地址等工作。数据格式由两部分构成, 即14位current_ptr信息和6位的Cnt_sent信息, 其中current_ptr用于存储当前查找的Vlan表的地址, Cnt_sent用于存储当前发送到的bitmap (在模式0下即为64位Lsb_vlan_bm中的某一位地址;在模式1下即为Mode_1_bitmap中的某一位地址) 的位置。
1.3 输出端口扫描模块
输出端口扫描模块的主要功能是根据接收到的88位数据信息及上一次查找结束时的状态信息完成对模式0和模式1的扫描, 根据扫描结果得到最终的输出端口信息。其中, 模式0主要针对64位bitmap信息进行扫描, 模式1则针对4位bitmap信息进行扫描, 因此将输出端口扫描模块分为去已扫描模块、64位bitmap扫描器、4位bitmap扫描器以及输出选择器4个部分, 如图4所示。
去已扫描模块的主要功能是滤除64位bitmap和4位bitmap中已经扫描过的端口, 并将滤除后的结果分别送给64位bitmap扫描器和4位bitmap扫描器;64位bitmap扫描器的主要功能是完成64位bitmap从低位到高位的扫描, 直到扫到第1个“1”出现的位置, 并将扫到的结果输送到输出选择器;4位bitmap扫描器的主要功能是完成4位bitmap从低位到高位的扫描, 直到扫到第1个“1”出现的位置, 并将扫到的结果输送到输出选择器;输出选择器的主要功能是根据当前的模式, 选择64位bitmap扫描结果或者4位bitmap扫描结果进行输出, 各模块实现电路图如图5所示。
2 仿真验证
本文设计的IP组播查找电路应用于PTN芯片的存储转发单元中, 在Altera系列FPGA开发板EP4SGX230KF40C2ES上对存储转发单元进行了验证。为了验证电路的正确性, 增加了必要的外围电路:流量产生器和数据包收集器。在200MHz的工作频率下, 通过NiosII软核对Vlan表和Group表进行配置, 启动电路工作后, 从数据包收集器中读取出统计的结果。PTN存储转发单元FPGA测试界面如图6所示。测试结果显示, IP组播查找电路能够完成IP组播查找功能, 并能稳定工作在200 MHz频率下。
3 结束语
为了提高电路工作频率, 本文设计的IP组播查找电路采用4级流水线操作完成IP组播输出端口扫描:第1级完成第1次请求的判断并从Group表和信息RAM中读取出相关数据;第2级完成Vlan表的信息读取操作;第3级完成部分64位bitmap以4位bitmap的扫描;第4级完成剩余部分64位bitmap的扫描及输出结果选择。同时采用信息存储RAM记录上一次IP组播输出端口扫描的状态, 与采用寄存器存储方式相比较, 信息存储RAM技术降低了电路的复杂度, 保证了系统的可靠性。为了进一步提高速度, 对两种模式并行扫描, 这种扫描模式减少了两种模式判断的等待时间, 有效地提高了电路的速度。最后, 在Altera系列FPGA开发板EP4SGX230KF40C2ES上对所设计的电路进行了验证, 验证结果表明, 该电路能够完成IP组播查找功能, 并能稳定工作在200MHz频率下。
参考文献
[1]圣钱生, 张桂英.PTN的关键技术及优势[J].信息技术, 2010, (12) :202-205.
[2]彭霖.面向3G和全业务运营的PTN组网策略探讨[J].信息系统工程, 2011, (12) :88-89, 98.
[3]赵科然, 张小红, 郑晶晶.PTN技术及应用前景[J].科技传播, 2011, (22) :170.
[4]赵亚光, 何崇博, 龚军辉, 等.关于分组传送网络 (PTN) 关键技术研究[J].科技创新导报, 2012, (6) :35.
高速IP路由器市场风生水起 篇5
Infonetics Research 2013年1季度的数据显示, 全球运营商级路由器及交换机市场的销售收入为32亿美元, 同比下降6%, 其中思科同比市场份额有所下滑, 而华为、阿尔卡特朗讯、Juniper分别上升了1~2个百分点。思科、华为、阿尔卡特朗讯、Juniper占据了全球核心及边缘路由器市场91%的市场份额。
超100G路由器受热捧
在核心路由器市场, 思科2010年发布了CRS-3运营商级路由器, 领衔全球100G路由器的发展, 同年, 阿尔卡特朗讯也推出了其100G路由器产品, 随后又推出了400G PSE芯片, 支持最高400Gbit/s的数据吞吐速率, 成为业界最高速率的网络处理器, 2012年, 推出7950XRS核心路由器后, 进一步冲击核心路由器市场, 推动了400G路由器的商用, 同时也进一步带动了100G路由器的大规模应用。与此同时, 华为超100G市场的布局也非常迅速, 甚至超过思科。2012年9月19日, 华为在全球发布400G路由线卡实物, 并快速实现全球全面商用, 在400G路由器的推出时间上, 早于思科9个月的时间, 2013年, 华为又发布了1T路由线卡和业界最大容量的100T多框集群路由器, 继续保持其业界领先地位。
在核心路由器市场, 已有的市场格局短期内难有较大变化, 而各系统设备商在更高速率的路由器产品上的竞争也在撼动着既有的格局。
国家安全问题带来的新机遇
“斯诺登”事件的出现对于思科等美国通信设备厂商也带来了新的发展危机, 尤其是从中国市场来看, 国内运营商在一定程度上已经开始规避这种潜在风险, 思科在国内运营商IP集采份额上大幅的下滑也明显反映出了这一局势, 这为国内的路由器厂商带来了难得的发展机遇。
一位国内运营商高层透露, 对于国家安全问题, 运营商也会高度重视, 目前在一些IP路由器的集采上已经开始向国内厂商倾斜, 而对于一些关键节点的路由器设备, 仍需要经过多重测试才能验证是否可以替换。据了解, 中国联通169江苏无锡节点核心路由器现已由华为搬迁, 取代了原有的思科路由器设备。
IP路由查找 篇6
(1) IP协议概述。
网际协议或互联网协议 (Internet Protocol, IP) 是用于报文交换网络的一种面向数据的协议, 是网络层通信的标准协议, 它负责提供基本的数据封包传送功能, 让每一块数据包都能够到达目的主机, 但不检查是否被正确接收。与IP协议配套使用的还有四个协议:地址解析协议ARP、逆地址解析协议RARP、网际控制报文协议ICMP、网际组管理协议IGMP。
(2) 虚拟互连网络中IP数据报的传输。
如一个互联网中的源主机要把一个IP数据报发送给目的主机。根据分组交换的存储转发的概念, 源主机先要查找自己的路由表, 看目的主机是否就在本网络上。如果是, 则不需要经过任何路由器而是直接交付, 任务就完成了。如果不是, 则必须把IP数据报发送给某个路由器A。A在查找了自己的路由表后, 知道应当把数据报转发给路由器B进行间接交付。这样一直转发下去, 最后由路由器C知道自己是和目的主机连接在同一个网络上, 不需要再使用别的路由器转发了, 于是就把数据报直接交付给目的主机。而各个网络之间可以是异构的。
(3) IP地址。
IP地址是为每个网络连接 (网卡) 分配一个在全世界范围内惟一的标识。报文头中的源IP地址、宿IP地址分别表示源主机、目的主机的IP逻辑地址。
IP地址长度为32比特, 由网络号、主机号组成, 常用的IP地址有A类、B类、C类地址, 路由器就根据IP地址进行寻址。
现在的国际互联网普遍的采用了IP协议。而现在正在网络中运行的IP协议是IPv4;IPv6 为IPv4的后续的一个版本。互联网现在正慢慢的耗尽IP地址, 而IPv6的出现解决了这个问题, 与IPv4的32位的地址相比较而言, IPv6拥有128位的地址空间可以提供比前者多很多的地址。
(4) IP层转发分组。
在TCP/IP系统中, 选路是指在网络中选择一条用于传送IP数据包路径的过程。路由器是承担选路任务的网络设备。用于决策选路的信息称为IP选路信息。路由器使用IP选路信息, 对所传输的IP数据包进行IP转发。
由于Internet是由许多不同的物理网络连接而成的, 加入Internet的计算机在与其他入网计算机通信时, 发送信息的源计算机可能与接收信息的目的计算机在同一个物理网络中;也可能不在同一个物理网络 (如以太网) 中。IP数据包在从源计算机发送到网络上后, 根据上述两种不同情况, 被传递到目的计算机时也有两种方式:直接交付和间接交付。
①直接交付:
IP数据包被直接交付时不需要经过路由器。因为在运行TCP/IP协议的以太网中, 入网的计算机TCP/IP协议族的ARP协议软件, 会帮助查询到本物理网络中其他计算机的MAC地址, 使IP数据包可以直接从源计算机传递到目的计算机。
②间接交付:
当送出IP数据包的源计算机与接收数据包的目的计算机不在同一个物理网络时, 就需要借助跨接不同物理网络的路由器实现间接交付。特别是当源计算机与目的计算机被多个物理网络隔开, 且它们之间可能有多条信息传输路径时, IP数据包的间接交付不但需要借助多台路由器, 还有一个选择最佳路径的问题。
2 路由选择协议
2.1 路由原理
当IP子网中的一台主机发送IP分组给同一IP子网的另一台主机时, 它将直接把IP分组送到网络上, 对方就能收到。而要送给不同IP于网上的主机时, 它要选择一个能到达目的子网上的路由器, 把IP分组送给该路由器, 由路由器负责把IP分组送到目的地。
路由动作包括两项基本内容:寻径和转发。寻径即判定到达目的地的最佳路径, 由路由选择算法来实现。路由选择算法将收集到的不同信息填入路由表中, 根据路由表可将目的网络与下一站 (nexthop) 的关系告诉路由器。路由器间互通信息进行路由更新, 更新维护路由表使之正确反映网络的拓扑变化, 并由路由器根据量度来决定最佳路径。这就是路由选择协议 (routing protocol) , 例如路由信息协议 (RIP) 、开放式最短路径优先协议 (OSPF) 和边界网关协议 (BGP) 等。
转发即沿寻径好的最佳路径传送信息分组。路由器首先在路由表中查找, 判明是否知道如何将分组发送到下一个站点, 如果路由器不知道如何发送分组, 通常将该分组丢弃;否则就根据路由表的相应表项将分组发送到下一个站点, 如果目的网络直接与路由器相连, 路由器就把分组直接送到相应的端口上。这就是路由转发协议 (routed protocol) 。
2.2 路由协议
典型的路由选择协议有静态路由选择策略与动态路由选择策略。静态路由选择的特点是简单和开销小, 但不能及时适应网络状态的变化。对于很简单的小网络, 完全可以采用静态路由选择, 用人工配置每一条路由。动态路由选择的特点是能较好地适应网络状态的变化, 但实现起来较为复杂, 开销也比较大, 因此, 动态路由选择适用于较复杂的大网络。
根据是否在一个自治域内部使用, 动态路由协议分为内部网关协议 (IGP) 和外部网关协议 (EGP) 。自治域内部采用的路由选择协议称为内部网关协议, 常用的有RIP、OSPF;外部网关协议主要用于多个自治域之间的路由选择, 常用的是BGP和BGP-4。
(1) RIP协议。
RIP协议最初是为Xerox网络系统的Xerox parc通用协议而设计的, 是Internet中常用的路由协议。RIP采用距离向量算法, 所以也称为距离向量协议。路由器收集所有可到达目的地的不同路径, 并且保存有关到达每个目的地的最少站点数的路径信息, 除到达目的地的最佳路径外, 任何其它信息均予以丢弃。同时路由器也把所收集的路由信息用RIP协议通知相邻的其它路由器。这样, 正确的路由信息逐渐扩散到了全网。
RIP使用非常广泛, 它简单、可靠, 便于配置。但是RIP只适用于小型的同构网络。而且RIP每隔30s一次的路由信息广播也是造成网络的广播风暴的重要原因之一。此外, 它还有慢收敛的问题, 即好消息传播快, 坏消息传播慢。
(2) OSPF协议。
20世纪80年代中期, RIP已不能适应大规模异构网络的互连, OSPF随之产生。它是网间工程任务组织 (1ETF) 的内部网关协议工作组为IP网络而开发的一种路由协议。
OSPF是一种基于链路状态的路由协议, 需要每个路由器向其同一管理域的所有其它路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其它一些变量。利用OSPF的路由器首先必须收集有关的链路状态信息, 并根据一定的算法计算出到每个节点的最短路径。
(3) BGP协议。
BGP是为TCP/IP互联网设计的外部网关协议, 用于多个自治域之间。它既不是基于纯粹的链路状态算法, 也不是基于纯粹的距离向量算法。它的主要功能是与其它自治域的BGP交换网络可达信息。各个自治域可以运行不同的内部网关协议。BGP更新信息包括网络号/自治域路径的成对信息。自治域路径包括到达某个特定网络须经过的自治域串, 这些更新信息通过TCP传送出去, 以保证传输的可靠性。
2.3 新一代路由器
由于多媒体等应用在网络中的发展, 以及ATM、快速以太网等新技术的不断采用, 网络的带宽与速率飞速提高, 传统的路由器已不能满足人们对路由器的性能要求。
新一代路由器使用转发缓存来简化分组的转发操作。在快速转发过程中, 只需对一组具有相同目的地址和源地址的分组的前几个分组进行传统的路由转发处理, 并把成功转发的分组的目的地址、源地址和下一网关地址放入转发缓存中。当其后的分组要进行转发时, 应先查看转发缓存, 如果该分组的目的地址和源地址与转发缓存中的匹配, 则直接根据转发缓存中的下一网关地址进行转发, 而无须经过传统的复杂操作, 大大减轻了路由器的负担, 达到了提高路由器吞吐量的目标。
参考文献
[1]谢希仁.计算机网络 (第5版) [M].北京:电子工业出版社, 2008.
IP路由查找 篇7
博科推出BrocadeRMLXR系列路由器新的硬件模块和软件, 提供业内最全面的功能, 满足当今网络对带宽、规模和性能的需求, 以期迈向开放式软件驱动可编程网络的无缝路径, 也就是业内所说的“新IP”。
很多当今的机构面临巨大挑战, 必须扩展现有网络带宽并支持更多的用户和设备, 这就需要高度动态的网络。这些机构正在努力过渡到更敏捷、软件驱动的基础架构。特别是在转向混合云模式之后, 应对双重挑战的能力对于业务成功更加重要。
为了满足这些需求, 博科为Brocade MLXe运营商级路由平台加强了软件, 支持OpenFlow 1.3等重要的功能, 帮助企业安全地部署针对具体应用和用户的新服务。博科OpenFlow 1.3实施在独特的Brocade MLXe可编程硬件中提供, 为高度定制的大规模服务提供精细的控制能力。通过博科混合端口模式, Brocade MLXe是唯一支持传统路由网络和新软件定义网络之间互联的运营商级平台。
新的硬件模块恰当地平衡了高端口密度、线速横向扩展单机箱性能以及行业领先的规模, 同时支持IPv4和IPv6, 帮助防止因为路由表爆炸而出现断网。作为博科的一项创新, 这个第六代可编程芯片采用博科VersaScale?处理器, 提供软件功能的灵活性, 以及硬件的性能和规模。这些组件为要求最为苛刻的服务提供商和数据中心网络而设计, 立即满足业务需求, 同时提供面向未来的灵活性和投资保护。
通过这些新产品, 博科实现了最为开放且可扩展的网络, 并且拥有满足当今用户越来越高预期的敏捷性。因此, 这个解决方案促进了在传统网络和为新IP设计的网络之间的平滑过渡。新IP的崛起要归功于越来越高的社交技术、移动设备和云计算需求。
AMS-IX首席技术官Henk Steenman表示:“平台可扩展性一直是我们关注的重点。为了解决可扩展性问题, 我们不断寻求最新、最强大的设备。博科多年来一直是我们值得信赖的创新硬件和软件解决方案供应商。我们很高兴地为我们的平台选择博科的最新功能。Brocade MLXe非常合适我们采用多厂商网络的基础架构。随着网络需求的不断演进, 它轻松地支持我们所需的带宽。”
通过近期发布的Brocade VyattaR控制器和Brocade MLXe, 博科提供真正的开放且全面的软件定义网络解决方案, 作为值得信赖的合作伙伴, 支持提供开放式SDN的灵活性。企业可以通过动态而灵活的框架加速软件网络的变革, 实现业务现代化。The robust carrier-class architecture of the Brocade Vyatta控制器拥有稳健的运营商级架构, 使用Brocade MLXe运营商级路由器中的OpenFlow 1.3实施进行了全面测试, 实现了完整的SDN解决方案, 满足服务提供商和数据中心网络的特殊需求。
博科交换、路由与分析部门副总裁Jason Nolet表示: “当前的企业对网络的要求越来越高。支持新IP, 我们提供最稳健、可扩展、灵活且开放的解决方案, 努力帮助客户实现网络现代化。通过在实施中支持OpenFlow 1.3来实现传统转发和新型软件定义转发之间的互联, Brocade MLXe还提供向真实世界SDN的无缝过渡。对于把OpenFlow集成到现有网络的网络运营商来说, 这种功能提供了一个合理的路径。”
新的支持元素
20端口10 GbE接口模块, 支持10/1G组合和MACsec加密;
2端口100 GbE接口模块, 包含CFP2接口;
重要的OpenFlow 1.3功能包括SSL/TLS以及Accounting with QoS、Group Table和QinQ;
无与伦比的SDN性能, 全面的12元组L2+L3+L4匹配实现最高128k数据流, 并支持全面的100G数据流;
第一个面向端到端多数据中心编排 (通过OpenStack) 的运营商级开放式解决方案;
先进的转发规模, 最高200万个IPv4和80万个IPv6路径;
通过博科VersaScale处理器实现敏捷的可编程网络;
行业领先的线速横向扩展性能, 深度缓存和高端口密度。
Brocade MLX系列