基于分布式转发交换的并行路由器关键技术研究

第３０卷第３期　国　防　科　技　大　学　学　报　ＪＯＵＲＮＡＬ　ＯＦ　ＮＡＴＩＯＮＡＬ　ＵＮＩＶＥＲＳＩＴＹ　ＯＦ　ＤＥＦＥＮＳＥ　ＴＥＣ　０１０ＧＹｖ０　．　：兰至　文章编号：１００１—２４８６（２００８）０３—００５３—０６　基于分布式转发交换的并行路由器关键技术研究　戴　艺，孙志刚，苏金树，管剑波　（国防科技大学计算机学院，湖南长沙４１００７３）　摘要：随着Ｉｎｔｅｍｅｔ链路速率和ＩＩ）前缀数目的不断增长，对路由器的转发和交换能力提出了更高的要　求。提出一种基于分布式转发交换的并行路由器体系结构，采用多个低速的能够独立转发和交换报文的功能　部件构成多级流水线，以流水的方式执行报文转发和交换。对该结构实现关键技术——基于子树映射的ＩＩ）　流水查找机制进行了深入的研究，提出了相应的解决方案，并指出了下一步的研究方向和思路。　关键词：并行路由器体系结构；路由表分解；基于子树的ＩＩ）查找　中图分类号：ＴＰ３９３　文献标识码：Ａ　Ｒｅｓｅａｒｃｈ　０ｆ　Ｋｅｖ　Ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　Ｐａｒａｌｌｅｌ　Ｒｏｕｔｅｒ　Ｂａｓｅｄ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｆｏｒｗａｒｄｉｎｇ　ａｎｄ　Ｓｗｉｔｃｈｉｎｇ　ＤＡＩ　Ｙｉ，ＳＵＮ　Ｚｈｉ・ｇａｎｇ，ＳＵ　Ｊｉｎ－ｓｈｕ，ＧＵＡＮ　Ｊｉａｎ－ｂｏ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｎａｔｉｏｎａｌ　Ｕｎｉｖ．ｏｆ　Ｄｅｆｅｎｓｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｌｍｎ￣ｈａ　４１００７３，Ｃｈｉ￣）　Ａｂｓｔｒａｃｔ：Ｃｏｎｔｉｎｕｉｎｇ　ｇｒｏｗｔｈ　ｉｎ　ｌｉｎｋ　ｓｐｅｅｄｓ　ｎｄ　ａｔｈｅ　ｎｕｍｂｅｒ　ｏｆａｄｖｅｒｔｉｓｅｄ　ＩＰ　ｐｒｅｉｆｘｅｓ　ｐｌａｃｅｓ　ｉｎｃｒｅａｓｉｎｇ　ｄｅｍａｎｄｓ　ｏｎ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　Ｉｎｔｅｍｅｔ　ｒｏｕｔｅｒｓ．Ｉｎ　ｖｉｅｗ　ｏｆｔｈｉｓ　ｆａｃｔ，ａ　ｐａｒａｌｌｅｌ　ｒｏｕｔｅｒ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｂａｓｅｄ　ｏｎ　ｐａ　ａｌ　ｆｏｒｗａｒｄｉｎｇ　ａｎｄ　ｐｅｌｉＩｌｉｎｇ　ｓｗｉｔｃｈｉｎｇ　ｉｓ　ｐｒｏｐｏ￣ｔ．　Ｔｈｅ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｃｏｎｓｉｓｔｓ　ｏｆ　ｍｕｌｔｉ—ｓｔａｇｅ，ｌｏｗｅｒ　ｓｐｅ州ｎｏｄｅｓ　ｐｅｒｆｏｒｍ￣ｇ　ＩＰ－ｌｏｏｋｕｐｓ　ａｎｄ　ｓｗｉｔｃｈｉｎｇ　ｉｎｄｅｐｅｎｄｅｎｔｌｙ，ｔｈｕｓ　ＩＰ－ｌｏｏｋｕｐｓ　ａｎｄ　ｓｗｉｔｃｈｉｎｇ　ｆｏｒ　ｍｕｌｉｔｐｌｅ　ｐａｃｋｅｔｓ　ｈａｖｅ　ｂｅｅｎ　ｐｉｐｅｌｉｎｅｄ．Ｗｅ　ｉｎｖｅｓｔｉｇａｔｅ　ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｏｆ　ｔｈｉｓ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｉｎｃｌｕｄｉｎｇ　ｔｈｅ　ｌｏｇｉｃａｌ　ｍａｐｐｉｎｇ　ｆｒｏｍ　ｓｕｂｔｒｉｅｓ　ｔｏ　ｆｉｍｅｆｉｏｎ　ｃｏｍｐｏｎｅｎｔｓ　ａｓ　ｗｅｌｌ　ａｓ　ｔｈｅ　ｐｉｐｅｌｉｎｉｎｇ　ＩＰ－ｌｏｏｋｕｐ　ｍｅｅｈａｌ＇ｌｉｓｍ　ｂａｓｅｄ　ｏｎ　ｓｕｂｔｒｉｅ．Ｆｉｎａｌｌｙ，ｆｕｔｕｒｅ　ｄｉｒｅｃｔｉｏｎｓ　ａｎｄ　ｐｏｓｓｉｂｌｅ　ｏｐｅｎ　ｐｒｏｂｌｅｍｓ　ａｒｅ　ｄｉｓｃｕｓｓｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｐａｒａｌｌｅｌ　ｒｏｕｔｅｒ　ａｒｃｈｉｔｅｃｔｕｒｅ；ｐａｒｉｔｔｉｏｎ　ｏｆ　ｒｏｕｔｉｎｇ　ｔａｂｌｅ；ＩＰ－ｌｏｏｋｕｐ　ｂａｓｅｄ　ｏｎ　ｓｕｂｔｒｉｅ　Ｉｎｔｅｍｅｔ网络流量、网络规模和上层应用的快速发展，对Ｉｎｔｅｍｅｔ互联的核心设备——路由器提出了　越来越高的要求。目前路由表前缀数目已经达到２４万并在继续增长中，不久的将来就会达到１００　万　Ｊ，在链路速率为１６０　Ｇｂｐｓ、最小报文为４０个字节的情况下，ＩＰ路由查找速率必须达到２　ｎｓ／ｐａｃｋｅｔ。　随着ＩＰｖ６协议的应用，前缀长度将从３２位增长到１２８位，这无疑对ＩＰ查表技术提出了更大的挑战。基　于ＴＣＡＭ的ＩＰ路由查找策略能够满足目前路由器对ＩＰ路由查找性能的需求，但ＴＣＡＭ成本高、功耗大、　可扩展性差，难以支持日益庞大的路由表。基于算法的ＩＰ路由查找策略可扩展性好、性价比高，但速度　慢，难以适应高速链路的发展。另一方面，随着ＷＩ）ＩＶＩ通道速率的不断提高，链路速率已经从ＯＣ１９２　（１０Ｇｂ／ｓ）到０ｃ７６８（４０Ｇｂ／ｓ），甚至达到了０Ｃ３０７２（１６０Ｇｂ／ｓ），在路由器交换结构中缓冲报文已经变得很困　难甚至是不可能的。例如，链路速率为１６０Ｇｂ／ｓ时，缓冲存储器必须在不到ｌｎｓ的时间里完成对４０字节　信元的写入和读出操作，而商业ＤＲＡＭｓ的随机访问时间为５０ｎｓ　。　目前已有的路由器采用转发与交换分离的体系结构，即首先由转发部件对报文进行精确查表，确定　其转发决策，然后由多级交换网络将报文发送到目的端口。在这种体系结构中，转发阶段与交换阶段在　逻辑上是分离的；转发部件按照特定的ＦＩＢ容量及ＦＩＢ处理能力进行设计，ＩＰ转发机制对链路速率及　ＦＩＢ容量的增长不具备可扩展性；交换部件则难以匹配高速链路，提供延迟保证。必须同时开发转发和　交换操作的并行度，实现转发延迟与交换延迟的相互隐藏。　本文提出一种基于分布式转发交换的并行路由器体系结构，路由器由多个结点构成，每个结点是独　★收稿日期：２００７一ｌ２—２ｏ　基金项目：国家自然科学基金资助项目（９Ｏ６Ｏ４ＯＯ６）　作者简介：戴艺（１９８ｏ．一），女，博士生。　维普资讯 http://www.cqvip.com

国防科技大学学报　２００８年第３期　立的具有一定转发和交换能力的功能部件，称之为转发交换结点ｒＳＮ（Ｆｏｒｗａｒｄｉｎｇ　ａｎｄ　Ｓｗｉｔｃｈｉｇ　Ｎｏｄｅ）。ｎ　通过分解路由表，构建路由表到ＦＳＮ结点的映射，每个ＦＳＮ结点仅保存转发表的一部分，执行部分转发　操作，大大降低了ＩＩ）查找复杂度；多个ＦＳＮ结点组成多级流水线结构，对报文转发交换执行流水操作。　这种体系结构通过同时开发转发和交换操作的并行度，降低对单个转发交换部件的要求，提高路由器的　整体转发和交换能力。　１基于分布式转发交换的并行路由器体系结构　在如图１所示的基于分布式转发交换的并行路由器体系结构实例中，４级２　Ｘ　２的转发交换结点　ＦＳＮ构成４级流水线，到达报文被分派到２个ＦＳＮ结点并行处理，每个ＦＳＮ结点执行部分ＩＩ）查找之后　确定下一级可用的ＦＳＮ集合，将报文缓冲到相应的输出队列中等待交换到下一级ＦＳＮ结点。在该体系　结构下，流水深度、资源复用度（每一级ＦＳＮ结点的个数）、ＦＳＮ节点端口数目均可自由配置，因而具有很　好的灵活度和可扩展性。通过深入研究基于路由表分解的部分转发和流水交换技术，提出了可行的能　够正确转发和交换报文、显著提高ＩＩ）转发速率及报文交换能力的并行路由器实现方案。该体系结构的　实现取决于以下三大关键技术：　（１）ＩＩ）路由表的分解技术：如何合理地分解ＩＩ）查找树，有效降低报文转发复杂度。　（２）子树到ＦＳＮ结点的映射技术：研究分解后的路由转发表在多个ＦＳＮ结点的映射算法，保证报文　部分转发的正确性和路由转发表在ＦＳＮ结点中分布的均衡性。　（３）ＦＳＮ结点的ＩＩ）查找和交换机制：设计单个ＦＳＮ结点的报文转发和交换策略，以高效的查表和简　单的报文调度机制实现多路径负载均衡及报文流的顺序。　第１级　１　Ｉ　第２级　１　Ｉ　第３级　１　Ｉ　第４级　１　图１基于分布式转发交换的路由器体系结构　Ｆｉｇ．１　Ａ　ｍｕｔｅｒ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｂａｓｅｄ　Ｏｉｌ　ｄｉｓｔｒｉｂｕｔｅｄ　ｆｏｒｗａｒｄｉｎｇ　ａｎｄ　ｓｗｉｔｃｈｉｎｇ　为了降低单个ＦＳＮ结点的ＩＩ）查表复杂度，需要对原始的ＩＩ）路由表进行分解。ＩＩ）路由查找的经典　算法是基于二叉Ｔｉｌｅ树的软件算法，如Ｒａｄｉｘ　Ｔｉｌｅ、Ｐａｔｒｉｃｉａ算法以及ＳＨｏｗｅｒ对Ｐａｔｒｉｃｉａ算法的改进算法　等。因此我们将ＩＩ）转发表表示为二叉Ｔｉｌｅ树的形式，在此基础上将原始的ＩＩ）查找树自上而下分解成Ｉｓ　层，其中Ｉｓ等于路由器流水线的级数。图２显示了一个最大级数为７、包含９个前缀的ＩＩ）查找树经过分　解后得到的子树结构，子树的最大级数为２。需要指出的是，每一层子树的最大级数可以不同，为了实　现原始ＩＩ）查找树分布的均衡性，可以根据ＩＩ）查找树的稀疏状况动态调整每一层子树的最大级数。　子树到ＦＳＮ结点的映射算法用于建立子树到ＦＳＮ结点的逻辑映射关系，它一方面要保证报文流水　交换的正确性（报文能够被交换到正确的目的端口），另一方面要实现转发表在ＦＳＮ结点的均衡分布。　提出一种基于输出端口集合的子树映射算法，根据子树输出端口集合和ＦＳＮ结点输出端口集合的包含　关系来映射子树。子树的输出端口集合定义为在原始的ＩＩ）查找树结构中，该子树的根结点可到达的所　有前缀结点对应的输出端口集合。如图２所示，第　层的第／棵子树记做ｓｔ０，，其输出端口集合表示为　维普资讯 http://www.cqvip.com 戴艺，等：基于分布式转发交换的并行路由器关键技术研究　５５　第一层　ｎ　第二层　笛。．∞８．　。．　．。ⅢⅢⅢ．。∞ｎ。．　Ⅲ。．　　ｎ　十　十　十　十　十　●　十　十　●　第三层　第四层　图２　ＩＰ查找树分解后得到的子树结构　Ｆｉｇ。２　Ｔｈｅ　ｔｌｉｅ　ｌｏｏｋ－ｕｐ　ｓｔｒｕｃｔｕｒｅ　ａｆｔｅｒ　ｂｅｉｎｇ　ｐａｒｔｉｔｉｏｎｅｄ　ＳＴＯ　其中，１≤ｉ≤Ｓ，．７　＝１，２，３，…；转发交换节点的输出端口集合则定义为位于第ｉ级的ＦＳＮ结点可　通过第ｉ＋１级……第Ⅳ级的ＦＳＮ交换可达的输出端口集合，第ｉ级的第＿『个ＦＳＮ结点记做　，其输出　端口集合表示为ＦＯ　，１≤　Ｋ，Ｋ为每级ＰＳＮ结点的个数。子树到ＦＳＮ结点的映射算法可描述如下：　从第ｉ级开始执行以下步骤，直到ｉ＝Ｓ，变量ｉ初始化为１：　（１）对于第ｉ级的每一个转发交换结点Ｆ　，将那些输出端口集合ＳＴＯ　包含于ＦＤ　的子树映射到　。　第ｉ层所有子树的集合表示为ｎ　，映射到　的子树集合表示为ｎ　。如果ｎ　ｃｎｉ　Ｕ…Ｕｎ　，则映射成　功，将变量ｉ加Ｉ返回到步骤Ｉ；否则，第ｉ层存在不能映射到第ｉ级任何转发交换节点的子树，跳转至　步骤（２）。　（２）采取子树迁移的办法来解决映射失败的问题：将不能映射的子树迁移到其父子树所在的ＦＳＮ　结点，由于在原始的ＩＩ）查找树中，子树的输出端口集合具有可包含性，即任何子树的输出端口集合必定　包含其孩子子树的输出端口集合，因此父子树所在的ＦＳＮ结点的输出端口集合也一定包含被迁移的孩　子子树的输出端口集合，故该迁移操作符合子树的映射条件。　①将被迁移的孩子子树从第ｉ层的子树集合ｎ　中删除；　②将被迁移子树的所有后代子树添加到其上一层的子树集合，变量ｉ加１返回到步骤１。　被迁移的孩子子树并不作为独立的子树而存在，也不为其分配子树标识，父子树和所有被迁移的孩　子子树作为一个整体构成一棵新的子树。因为任何查找过程都只会先访问父子树，由后继目的ＩＩ）地址　的位信息来触发对孩子子树的访问，父子树中保存指向孩子子树块的指针。报文到达ＦＳＮ结点时，ＦＳＮ　结点根据其目的ＩＩ）地址相应的位信息搜索子树，决定其交换路径。每棵子树包含有效前缀的下一跳信　息以及下一级可用的ＦＳＮ结点信息。　２分布式转发交换实现机制　２．１树位图算法　ＦＳＮ结点采用基于子树的ＩＩ）查找机制，以子树为逻辑单位进行流水化查找。大多数基于算法的ＩＩ）　查找策略均采用树的遍历法，即从根节点开始搜索，遍历树的各级，最后结束于叶节点。它们当中大部　分的查找算法既不是以子树为逻辑单位进行搜索也不利于流水实现。通过深入研究各种基于树的查找　算法，我们发现位图表示法能够以固定尺寸存储子树，并有利于各级ＦＳＮ结点的流水查找。假设子树　ｎ一１　ｎ一１　高度为ｎ，那么其孩子子树的数目至多为２　，最大前缀数目为　２　，可分别用２　ｉｔｓ和　２ｉｂｉｔｓ的向量　维普资讯 http://www.cqvip.com

５６　国防科技大学学报　２００８年第３期　表示孩子子树和有效前缀的分布信息。　Ｉ匝－－ｏ．３．盘３．，￣ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ／，．；３　－，　—　＇，／／　一Ｐ／　，　　二图３子树位图表示法　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　ｏ　Ｏ　ｌ　Ｌ　Ｆｉｇ．３　Ｔｈｅ　ｂｉｔｍａｐ　ｐｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　ａ　ｓｕｂｔｒｉｅ　图３显示了高度为４的子树位图表示法，任何形式的高度为４的子树都可以保存在固定尺寸的子　树块中。前缀位向量ＰＢＶ（Ｐｒｅ￡ｂｃ　Ｂｉｔ　Ｖｅｃｔｏｒ）描述了子树内与前缀相关的节点。ＰＢＶ将原始子树表示为　线性格式：按照从上到下从左至右的顺序记录前缀信息。ＰＢＶ中的每一位依次对应前缀：＊，０＊，１＊，　０ｏ＊，０１＊，１０＊，ｌｌ＊，…，１１１＊。图３中ＰＢＶ中的两个“１”分别对应前缀Ｐ１（０＊）和Ｐ２（１＊）。子树中　所有前缀的下一跳信息存储在下一跳表连续的空间里，下一跳表指针（Ｎｅｘｔ　Ｈｏｐ　Ｔａｂｌｅ　Ｐｏｉｎｔｅｒ）记录了第　一个有效前缀下一跳信息的位置，通过偏移量计算其他前缀下一跳信息地址。孩子位向量ＣＢＶ（Ｃｈｉｌｄ　Ｂｉｔ　Ｖｅｃｔｏｒ）描述了孩子子树的分布状态。ＣＢＶ长度为２４＝１６ｂｉｔｓ，末尾２个“１”分别对应根节点为１１１０和　１１１１的孩子子树。需要注意的是，前缀Ｐ３作为根节点前缀（＊）保存在下一级孩子子树中，在这里Ｐ３作　为孩子子树根节点而不是前缀而存在。孩子子树标识及其可用的ＦＳＮ结点的集合保存在孩子路由表　片连续的空间里，子树块保存访问这些信息的基地址即孩子路由表指针（Ｃｈｉｌｄ　Ｒｏｕｔｅｒ　Ｔａｂｌｅ　Ｐｏｉｎｔｅｒ）。　对于给定的ＦＳＮ结点，孩子子树可用的ＦＳＮ结点集合就是那些与其相连且包含该孩子子树的ＦＳＮ结　一点。　采用类似于文献［３］所提出的树位图算法对子树块进行搜索，假设子树高度为＾，树位图算法以＾　为步长，读取目的ＩＩ）地址对应的信息位执行以下操作：　（１）读位向量ＣＢＶ，若第．ｓ，．ｓ　．ｓ　．ｓ。位为“１”，计数命中位左边“１”的个数（包括命中的“１”本身），以此　为偏移量，根据孩子路由表指针读取孩子路由表，获取孩子子树标识及其可用的ＰＳＮ结点的集合。　（２）读位向量ＰＢＶ，按照．ｓ。．ｓ　．ｓ　＊，．ｓ。．ｓ：＊，．ｓ。＊，＊的顺序匹配ＰＢＶ，一旦命中ＰＢＶ，计数命中位左　边“１”的个数（包括命中的“１”本身），以此为偏移量根据下一跳表指针读取匹配前缀的下一跳信息。　步骤（１）和步骤（２）并行执行可提高查找速率。为了避免回溯并实现最长前缀匹配，需要记录最近　匹配前缀的下一跳信息，若下一级子树没有匹配的前缀也没有匹配的孩子子树，那么最近匹配前缀就是　最长匹配前缀。步骤（２）在搜索匹配前缀时，从最长前缀开始搜索，一旦命中则结束本次匹配，记录命中　前缀的下一跳信息。　２．２　ＩＰ查找优化策略　２．２．１初始阵列优化　几乎所有的ＩＩ）查找算法都可以通过初始阵列优化来提高查找速率　Ｊ。初始阵列优化的基本思　想是，通过在搜索树的顶端牺牲少量的存储开销达到大大减少查找次数的目的。若初始阵列为８ｂｉｔｓ，　则表示目的口地址的前８位将用于检索包含２　（＝２５６）个条目的初始阵列。每个条目至多存储一个前　缀信息和一个孩子子树标识。初始阵列优化的缺点是更新性能差，例如更新前缀００００＊时，需要检查　００ｏ０ｏ０００到００００１１１１的所有条目，其中所有前缀长度小于４（更新前缀００００＊长度为４）的前缀都要被更　新。在硬件实现中，可以采用三端口ＲＡＭ存储初始阵列，一个读端口用于查表，另外一读一写两个端口　维普资讯 http://www.cqvip.com 戴艺，等：基于分布式转发交换的并行路由器关键技术研究　５７　用于更新操作，查找和更新操作可同时进行，查找性能不会受到慢速更新的影响。　２．２．２子树存储优化　有统计显示，大多数的子树只包含少量的前缀。文献［６］对子树内前缀数目的分布信息进行统计，　初始步长为８，子树高度为４，统计结果显示：超过５０％的子树不包含任何前缀信息；大多数子树只包含　少量的前缀，其中含１个前缀的子树又比含多个前缀的子树的总和还要多。因此，树位图算法采用特殊　的存储方式来保存那些含少量前缀的子树，这就是ＣＡＭ块。ＣＡＭ块由ＣＡＭ条目构成，每个ＣＡＭ条目　由匹配位、匹配长度和下一跳信息构成。以步长为４的子树为例，匹配位为４ｂｉｔｓ，匹配长度需要２ｂｉｔｓ来　存储。这样前缀的下一跳信息可以从下一跳表中移除，避免了子树查找的第二次访存，提高了查找效　率。采用ＣＡＭ块存储末端子树时，超过５０％的下一跳信息从下一跳表中转移到ＣＡＭ块中。　ＩＩ）查找结构中存在既不包含前缀也不包含孩子子树的“单路径”子树。为了进一步降低存储开销，　通过在子树块中引入跳步长度的方法避免对“单路径”子树的存储，这就是路径压缩策略。子树高度为　４、跳步长度为１时，直接忽略目的ＩＩ）地址中对应本级的４ｂｉｔｓ地址信息，使用下一级４ｂｉｔｓ地址信息进行　子树搜索操作。　２．３　ＦＳＮ转发引擎设计　子树步长的选择对ＩＩ）查找性能有着极大的影响，步长越大，存储空间利用率越低，存储管理和前缀　更新机制也越复杂。综合多方面因素考虑，我们将子树步长定为４，初始步长为１２。如图４所示，第一　级ＦＳＮ结点采用初始步长为１２的初始阵列，初始阵列的每个条目保存：前缀长度，前缀下一跳信息（目　的端口），下一级孩子子树标识。为了进一步降低存储开销，孩子子树标识只在其所属层保持唯一特性，　而不是全局唯一，既然子树查找操作是分级流水进行的，因而这样做并不会影响ＩＩ）查找的正确性。假　设端口数目Ｎ＝１０２４，那么初始阵列大小为（４＋１０＋１２）Ｘ　２控ｂｉｔｓ　１３ＫＢ，而文献［６］中１２ｂｉｓｔ的初始阵列　大小为２８ＫＢ。为了保持子树在ＦＳＮ结点分布的均衡性，我们将第二层子树全部映射到第一级ＦＳＮ结点　（不违反基于输出端口集合的子树映射规则，因为第一级的每个ＦＳＮ结点一定能够到达所有的输出端　口）。第一级ＩＩ）查找结构如图４所示：转发引擎首先根据目的ＩＩ）地址的高１２位访问初始阵列，若命中　前缀则记录下一跳信息；然后以孩子标识为地址读取相应的子树块，计算访问孩子路由表和下一跳表的　地址；若命中ＣＢＶ，读孩子路由表，获取下一级孩子子树标识及其可用的ＦＳＮ结点集合；若命中ＰＢＶ，读　下一跳表，记录匹配前缀的下一跳信息，孩子路由表和下一跳表可并行访问。这样，经过三次访存完成　了第一级报文转发操作。第二级和第三级ＦＳＮ结点采用相同的报文转发机制，结构如图４红色虚线所　示。与第一级ＦＳＮ结点转发引擎不同的是，二、三级ＦＳＮ结点转发引擎需要维护子树标识到子树块的　映射表，根据映射表访问子树块，而不是通过子树标识直接访问。　２１２Ｅｎｔｒｉｅｓ　１ｔｈ　Ｌｅｖｅ１　ＬＰｒｅｆｉｘ　ｌ　Ｄｅｓｔ　ｌ　Ｃｈｉｌｄ　Ｔｆｉｅ　Ｂｌｏｃｋ　４ｅｂｎｉｇｔｓｈ　Ｉ　ｌｎｉｔＰａｏｌｒＡｔｓｒ　ａｙＩ　ｄｅｎｔｉｅｒ　＿］＿．　ＡｅｒＢａ￣ｌｏ　ｃｋ　图４　４级ＦＳＮ结点流水转发结构　Ｆｉｇ．４　Ｔｈｅ　ｐｉｐｅｌｉｎｉｎｇ　ＩＰ－ｌｏｏｋｕｐ　ｓｔｒｕｃｔｕｒｅ　ｆｏｒ　ｆｏｕｒ　ｓｔａｇｅｓ　ｏｆ　ＦＳＮ　ｎｏｄｅｓ　２８～３１地址段全是末端子树，即不含孩子子树的子树，只需保存其前缀信息；另一方面，含４个以　上前缀的末端子树较少，约占全部末端子树的２０％，因此我们采用ＣＡＭ块存储２８～３１地址段的末端子　树并将其合并到第４级转发结构中（注：在执行基于输出端口集合的子树映射算法时，将２４～３１地址段　的子树集合映射到第４级ＦＳＮ结点）。如图４所示，转发引擎读取子树块，若命中前缀，获取下一跳信　息；若命中孩子子树，则获取下一级子树ＣＡＭ块地址。每个ＣＡＭ块保存３个前缀及其下一跳信息，可　维普资讯 http://www.cqvip.com

５８　国防科技大学学报　２００８年第３期　开辟额外的存储空间保存少量的溢出前缀，为提高查找性能，子树的前３个最长前缀保存在ＣＡＭ块中。　每一级ＦＳＮ结点采用ＣＡＭ块存储前缀数目小于等于３的末端子树，既降低了存储开销，又减少了　访存次数，ＣＡＭ块和子树块设有跳步长度，用于路径压缩操作，消除了“单路径”子树开销。为简化存储　管理，ＣＡＭ块和子树块具有相同尺寸。　２．４交换部件设计　在报文流水转发的过程中，一旦匹配最长前缀，则根据最长匹配前缀的下一跳信息为报文附上目的　端口，后继ＦＳＮ结点根据报文的目的端口交换报文，无须再进行子树查找操作。目的端口对应的下一　级可用ＦＳＮ结点就是那些输出端口集合中包含了该输出端口的下一级ＦＳＮ结点，这些路由信息完全由　ＦＳＮ结点的互联拓扑结构决定，与子树的映射结果无关。为了确保报文能够被发送到正确的目的端口，　ＦＳＮ结点需保存其输出端口集合中每个输出端口的下一级可用ＦＳＮ结点集合，这些和输出端口相关的　路由信息保存在ＦＳＮ结点交换部件的交换表中（Ｓｗｉｔｃｈｉｎｇ　Ｔａｂｌｅ）。经转发引擎处理后的报文可分为两　种：命中ＣＢＶ还需进一步匹配前缀的报文；没有命中ＣＢＶ已完成最长前缀匹配的报文。对于第一种报　文，交换部件根据交换表来确定下一级ＦＳＮ结点；对于第二种报文，交换部件需根据孩子子树下一级可　用的ＦＳＮ结点集合确定下一级ＦＳＮ结点。　接下来的问题是：如何从多个可用的ＦＳＮ结点中选择有利于降低报文延迟、提高系统吞吐率的下　一级ＦＳＮ结点。我们采用了一种基于信用的流控机制：下一级ＦＳＮ结点向上一级ＦＳＮ结点发送信用　值，通知可用缓冲区容量；上一级ＦＳＮ结点交换部件选择信用值大的ＦＳＮ结点发送报文，如果报文长度　大于最大信用值则等待。基于信用的流控机制能有效提高缓冲区利用率、系统吞吐率，并在一定程度上　避免了缓冲区溢出。　３总结　本文提出了一种分布式转发交换的并行路由器体系结构，是目前唯一将转发技术和交换技术有机　融合在一起的新型路由器体系结构。随着该体系结构关键技术的突破，路由器大量的硬件资源将从繁　重的ＦＩＢ处理中释放出来，专注于组播、ＱｏＳ、安全等方面的应用。下一步的研究内容包括：结合网络报　文流的特性，分析ＦＳＮ结点的拓扑连接关系对负载均衡和报文乱序的影响，研究路由器内部报文保序　和流量集中问题及如何在ＦＳＮ结点中支持Ｉ／Ｎ，６转发。　参考文献：　［１］Ｈｕｓｔｏｎ　Ｇ．ＣＩＤＲ　Ｒｅｐｏ￣［Ｒ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｃｌｄｒ－ｒｅｐｏｒｔ．ｏｗｅ，２ＯＯ８．　［２］Ｉｙｅｒ　Ｓ，ＭｃＫｅｏｗｎ　Ｎ．Ｍａｋｉｎｇ　Ｐａｒａｌｌｅｌ　Ｐａｃｋｅｔ　Ｓｗｉｔｃｈｅｓ　Ｐｒａｃ６ｃａｌ［ｃ］，，ＰＩｏｃ．ｏｆ　ＩＥＥＥ　Ｉｎｆｏｅｍ．，２００１：１６８０—１６８７．　［３］Ｂａｂｏｅｓｃｕ　Ｆ，Ｒａｊｇ０】　Ｓ，Ｈｕａｎｇ　Ｌ　Ｂ，ｅｔ　ａ１．ＨａｒｄｗａｒｅＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆａＴｒｅｅ　ＢａｓｅｄＩＰＩ＿ｏｏｋｕｐ￣ＪｇｏｉｒｔｈｍｆｏｒＯＣ７６８　ａｎｄ　Ｂｅｙｏｎｄ［Ｃｌ／／Ｐｒｏ￣．ｏｆ　ＤｅｓｉｇｎＣｏｎ．，２００５：１６８０—１６８７．　［４］Ｄｅ　Ｍ，ＢｒｏｄｎｉｋＡ，Ｃａｒｌｓｓｕｏ　Ｓ，ｅｌ　ａ１．ＳｍａｌｌＦｏｒｗａｒｄｉｎｇＴａｂｌｓｅｆｏｒ　ＦａｓｔＲｏｕｔｉｎｇｔ￣ｋｕｐｓ［Ｃ］／／Ｐｒｏ￣．ｏｆＡＣＭ　ＳＩＧＣＯＭＭ’９７，Ｃ４ＵＵｌｅ８（１４一　Ｉ８　ＳｅｐｔｅｒＩ１ｂｅｒ　１９９７），１９９７．　［５］Ｗａｌｄｖｏｇｅｌ　Ｍ，Ｖ时ｅｓｅ　Ｇ，Ｔｕｒｎｅｒ　Ｊ，ｅｔ　ａ１．Ｓｃａｌａｂｌｅ　Ｈｉｇｈ　ｓｐ。。ｄ　Ｒｏｕｔｉｎｇ　Ｌｏｎｋ￣［Ｊ］．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２００１，１９（４）：　４４０—４８２．　［６Ｊ　ＥＤ／］￣ｏｎ　Ｗ．Ｈａｒｄｗａｒｅ－ｂａｓｅｄ］ｎｔｅｍｅｔ　Ｐｒｏｔｏｃｏｌ蹦ｘ　Ｌｏ０ｌ（Ｉ　．Ｈａｒｄｗａｒｅ－ｂａｓｅｄ　Ｉｎｔｅｍｅｔ　Ｐｒｏｔｏｃｏｌ　Ｐｒｅｉｆｘ　Ｌｏｎｋｕｐｓ［Ｄ］．Ｗａｓｈｉｎｇｔｏｎ　Ｕｎｉｖｅｒｓｉｔｙ　Ｅｌｅｃｔｒｉｃａｌ　ＥｎｇｉｎｅｅｒｉｎｇＤｅｐａｒｔｍｅｎｔ，１９９９．