第３５卷第５期 ２０１３年５月 电子与信息学报 Ｖ＿０ｌ＿３５ＮＯ．５ Ｍａｙ ２０１３ Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ 一种新的高速报文解析结构研究 郭云飞㈣ 黄万伟 郑州董永吉 夏军波⑨ ４５０００２） （国家数字交换系统工程技术研究中心（理工大学 南京（防空兵学院摘２１０００７） 郑州４５００５２） 要：随着新协议的不断涌现和网络速率的迅猛增长，报文解析结构在解析灵活度和解析速率上面临挑战。该文 结合流水线设计和二叉ｔｒｉｅ树查表思想，提出一种应用于路由转发的报文协议解析结构ｆＰａｒｓｉｎｇ Ｐｉｐｅｌｉｎｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｏｒｗａｒｄｉｎｇ，ＰＰＡＦ），通过构建协议二叉ｔｒｉｅ树来支持报文协议解析的灵活度，利用硬件多级流水 查表提升报文协议解析处理速率，采用节点映射算法解决协议二叉ｔｒｉｅ树节点到流水线映射过程中存储资源不均衡 的问题。基于ＮｅｔＦＰＧＡ平台的仿真结果表明，相对于现有的高速解析结构，ＰＰＡＦ在处理速率和资源占用上取得 较好的均衡的同时，能够提供基于接口的灵活解析能力。 关键词：信息处理；报文解析；二叉ｔｒｉｅ树；网络虚拟化；ＮｅｔＦＰＧＡ 中图分类号：ＴＰ３９３ ＤＯＩ：１０．３７２４／ＳＰ．Ｊ．１ １４６．２０１２．００３４４ 文献标识码：Ａ 文章编号：１００９—５８９６（２０１３）０５—１０８３．０７ Ａ Ｎｅｗ Ｈｉｇｈ－ｓｐｅｅｄ Ｐａｃｋｅｔ Ｐａｒｓｉｎｇ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｄｏｎｇ Ｙｏｎｇ－ｊｉ① Ｇｕｏ Ｙｕｎ—ｆｅｉ①②Ｈｕａｎｇ Ｗａｎ－ｗｅｉ①Ｘｉａ Ｊｕｎ—ｂｏ。 （Ｎａｔｉｏｎａｌ Ｄｉｇｉｔａｌ Ｓｗｉｔｃｈｉｎｇ Ｓｙｓｔｅｍ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｃａｌ Ｒ＆Ｄ Ｃｅｎｔｅｒ，Ｚｈｅｎｇｚｈｏｕ ４５０００２，Ｃｈｉｎａ） （ ｅ Ｐ己 Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ ２１０００７，Ｃｈｉｎａ） （Ａｉｒ Ｆｏｒｃｅｓ Ｄｅｆｅｎｃｅ Ｃｏｍｍａｎｄ Ａｃａｄｅｍｙ ｏｆ ，Ｚｈｅｎｇｚｈｏｕ ４５００５２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｉｎｃｒｅａｓｉｎｇ ｎｕｍｂｅｒ ｏｆ ｎｅｗ ｐｒｏｔｏｃｏｌｓ ａｎｄ ｔｈｅ ｒａｐｉｄ ｇｒｏｗｔｈ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ ｌｉｎｋ ｒａｔｅ，ｔｈｅ ｐａｃｋｅｔ ｐａｒｓｉｎｇ ａｒｃｈｉｔｅｃｔｕｒｅ ｈａｓ ｂｅｅｎ ｇｒｅａｔｌｙ ｃｈａｌｌｅｎｇｅｄ ｏｎ ｉｔｓ ｆｌｅｘｉｂｉｌｉｔｙ ａｎｄ ｒａｔｅ．Ｗｈｉｌｅ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｉｄｅａ ｏｆ ｐｉｐｅｌｉｎｅ ｄｅｓｉｇｎ ａｎｄ ｂｉｎａｒｙ－ｔｒｉｅ，ａ ｎｅｗ ｐａｒｓｉｎｇ ａｒｃｈｉｔｅｃｔｕｒｅ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｎａｍｅｌｙ Ｐａｒｓｉｎｇ Ｐｉｐｅｌｉｎｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｏｆｒ Ｆｏｒｗａｒｄｉｎｇ（ＰＰＡＦ）．Ｉｔ ｆｌｅｘｉｂｌｙ ａｎａｌｙｓｉｓ ｐａｃｋｅｔ ｐｒｏｔｏｃｏｌ ｂｙ ｃｏｎｓｔｒｕｃｔｉｎｇ Ｆｏｒｗａｒｄｉｎｇ Ｐｒｏｔｏｃｏｌ－ｔｒｉｅ，ｉｍｐｒｏｖｅｄ ｔｈｅ ｐｒｏｃｅｓｓｉｎｇ ｒａｔｅ ｂｙ ｅｍｐｌｏｙｉｎｇ ｈａｒｄｗａｒｅ ｐｉｐｅｌｉｎｅ ｌｏｏｋ－ｕｐ ｔａｂｌｅ，ａｎｄ ｓｏｌｖｅｄ ｔｈｅ ｕｎｂａｌａｎｃｅ ｏｆ ｎｏｄｅ ｍａｐｐｉｎｇ ｓｔｏｒａｇｅ ｒｅｓｏｕｒｃｅ ｂｙ ｕｓｉｎｇ ｔｈｅ ｎｏｄｅ ｔｏ ｐｉｐｅｌｉｎｅ ｍａｐｐｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｔｈｒｏｕｇｈ ｔｈｅ ＮｅｔＦＰＧＡ ｐｌａｔｆｏｒｍ ｓｕｇｇｅｓｔ ｔｈａｔ ＰＰＡＦ ｉｓ ｓｕｐｅｒｉｏｒ ｔｈａｎ ｔｈｅ ｅｘｔａｎｔ ｈｉｇｈ ｓｐｅｅｄ ｐａｒｓｉｎｇ ａｒｃｈｉｔｅｃｔｕｒｅ ｉｎ ｔｗｏ ｗａｙｓ：ＰＰＡＦ ａｃｈｉｅｖｅｓ ａｍｂｉｄｅｘｔｅｒｉｔｙ ｉｎ ｐＥ６ｃｅｓｓｉｎｇ ｓｐｅｅｄ ａｎｄ ｒｅｓｏｕｒｃｅ ｃｏｎｓｕｍｐｔｉｏｎ；ａｎｄ ｉｔ ｃａｎ ｐｒｏｖｉｄｅ ｉｎｄｅｐｅｎｄｅｎｔ ｉｎｔｅｒｆａｃｅ－ｂａｓｅｄ ｆｌｅｘｉｂｌｅ ｐｒｏｔｏｃｏｌ ｐａｒｓｉｎｇ ｃａｐａｂｉｌｉｔｉｅｓ． Ｋｅｙ ｗｏｒｄｓ：Ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ；Ｐａｃｋｅｔ ｐａｒｓｉｎｇ；Ｂｉｎａｒｙ－ｔｒｉｅ；Ｎｅｔｗｏｒｋ Ｖｉｒｔｕａｌｉｚａｔｉｏｎ；ＮｅｔＦＰＧＡ １ 引言 近年来，大量的新协议和技术【 】的涌现及随着网 络虚拟化［２，３１研究的兴起，网络节点需要能够实时地 调整报文解析能力，以适应网络创新实验及网络业 务动态变化的组网需求。斯坦福大学推出的 ＮｅｔＦＰＧＡ［ 】平台，Ａｎｗｅｒ等人【５】提出的Ｓｗｉｔｈｂｌａｄｅ 平台，Ｘｉｅ等人［０】设计的可编程虚拟化路由器 ＰＥＡＲＬ都为互联网创新提供了共享性、专用性和 基础性的试验环境。同时，为了加快新协议的解析 和部署，Ｋｏｚａｎｉｔｉｓ等人【 】提出利用ＴＣＡＭ（Ｔｅｒｎａｒｙ Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）和ｈａｓｈ配合查表的 Ｋａｎｇａｒｏｏ报文解析系统，可达到４０ Ｇ／ｓ的链路处 理速率，但由于ＴＣＡＭ高功耗的缺点［８】，了系 统的可扩展性；Ａｔｔｉｇ等人【。］提出了一种可以简单直 观描述报文解析的语言ＰＰ（Ｐａｃｋｅｔ Ｐａｒｓｉｎｇ），根据 ＰＰ编译器可以离线生成一个协议解析处理器，经在 ２０１２—０３—２９收到，２０１３．０３－２２改回 ＸＩＬＩＮＸ ＦＰＧＡ上测试可达到４００ Ｇ／ｓ的处理能力， 但由于算法占用资源巨大，导致通用可移植性较差。 本文将流水线设计和二叉ｔｒｉｅ树查表思想加以 国家９７３计划项目（２０１２ＣＢ３１５９０１），国家８６３计划项目（２０１１ＡＡ ０１Ａ１０３）和国家科技支撑计划（２Ｏｌ１ＢＡＨ１９Ｂ０１）资助课题 通信作者：董永吉ｙｏｎｇｊｉｄ＠ｇｍ＆ｉｌ．ｃｏｉｎ １０８４ 电子与信息学报 第３５卷 结合，设计了一种应用于路由转发的协议解析结构 路径匹配的解析结果。在基于ＭＰＬＳ（Ｍｕｌｔｉ— （Ｐａｒｓｉｎｇ Ｐｉｐｅｌｉｎｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｏｒｗａｒｄｉｎｇ， ＰＰＡＦ１，通过ＮｅｔＦＰＧＡ实验平台对结构进行了仿 真验证，取得了良好的效果。 Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）Ｓ１ ＩＰ协议作为转发关键 词的场景下，如图２中（ａ）协议树１和（ｂ）协议树２ 分别描述了协议树Ｅｔｈｅｒｎｅｔ—ＶＬＡＮ—ＭＰＬＳ— ＩＰｖ４一ＩＰｖ６和８０２．３ ＳＮＡＰ—ＩＰｖ４的ＦＰ—ｔｒｉｅ树结 构。 图２中Ｐ１和Ｐ１３为无法识别的解析结果；Ｐ４， Ｐ８分别代表了ＭＰＬＳ和ＩＰｖ６的协议识别结果，Ｐ６ 和Ｐ１２为ＩＰｖ４的协议识别结果；其余节点均为协 议的判定节点，表１对两个ＦＰ—ｔｒｉｅ树的节点进行了 解释，具体如下所示。 ２ ＰＰＡＦ结构介绍 ＰＰＡＦ由转发协议二叉ｔｒｉｅ树（Ｆｏｒｗａｒｄｉｎｇ Ｐｒｏｔｏｃｏｌ－ｔｒｉｅ，ＦＰ—ｔｒｉｅ）和流水线结构两部分组成， 如图１所示。转发协议二叉ｔｒｉｅ树将传统报文解析 过程抽象成一种二叉ｔｒｉｅ树的查表描述，达到解析 的灵活性表示；并采用节点映射算法（Ｎｏｄｅ Ｔｏ Ｐｉｐｅｌｉｎｅ，ＮＴＰ）将ＦＰ—ｔｒｉｅ树节点映射到流水结构 上，通过硬件并行流水查找ＦＰ—ｔｒｉｅ树节点信息，实 现报文协议解析。 啦 螅 强 曜 （ａ）褂议树１ 图１ ＰＰＡＦ结构组成图 图２ ＦＰ—ｔｒｉｅ树结构 ２．１转发协议二叉ｔｒｉｅ树 结合表１给出ＦＰ—ｔｒｉｅ树的定义： 定义１ ＦＰ—ｔｒｉｅ树叶子节点只包含解析结果， 二叉ｔｒｉｅ树是一种用于快速检索的二叉树结 构［１０］，ＦＰ—ｔｒｉｅ树依据二叉ｔｒｉｅ树的特点，对链路层 和网络层协议以网络转发为目的进行解析，将报文 其中包含正常解析内容的称实叶子节点，反之包含 无法解析的称虚叶子节点。 定义２节点深度为该节点到根节点的最大节 点数，定义根节点的深度为１，则其余节点深度为 头部的相应协议字段转化称为待查找的关键词，结 合网络协议的层次结构和协议公开标准，将协议解 析过程转换成一个有序的查找序列。 在ＦＰ—ｔｒｉｅ树结构中每个内部节点都包含一个 判定协议的规则方法及两个指针，两个指针分别指 向两个子节点，最后一级叶子节点包含与当前解析 双亲深度的最大值加１，并定义ＦＰ—ｔｒｉｅ树中最大节 点深度为ＦＰ—ｔｒｉｅ树的深度。 定义３若二叉ｔｒｉｅ树满足如下的约束： 约束１ 每个协议的识别判定可能需要多个定 表１ ＦＰ．ｔｒｉｅ树节点内容表 第５期 董永吉等：一种新的高速报文解析结构研究 １０８５ 位规则，但每个非叶子节点内只存储一个定位规则 和两个跳转的指针，其中定位规则包含该协议相关 字段的判定取值及判定方法； 约束２每个ＦＰ—ｔｒｉｅ树有且仅有一个虚叶子 节点； 约束３任一非叶子节点必须有两个不同为实 叶子节点的子节点； 则称该二叉ｔｒｉｅ树称为ＦＰ—ｔｒｉｅ树。 由上述的定义可知，协议二叉ｔｒｉｅ树具有如下 的性质： 性质１任一个ＦＰ—ｔｒｉｅ树描述的协议可以被 有限个非叶子节点判别表示。 证明 用反证法证明。假设协议Ｐ可以被无限 个ＦＰ—ｔｒｉｅｅ树的非叶子节点表示，由约束１可知， 每个非叶子节点都存储一个协议相关字段判别值， 则该协议Ｐ需要无限个协议字段来表示判定，这与 协议的物理实现相悖，故不可能出现。所以ＦＰ—ｔｒｉｅ 树描述的协议可以被有限个节点来判别表示。证毕 性质２深度为 的ＦＰ—ｔｒｉｅ树的节点数 ， 满足Ｌ ＳＬ ２ 一１。 证明用数学归纳法证明。 归纳基础：当Ｌ＝Ｉ时，Ｌ＝２ 一１－－１，则当深 度为１时，ＦＰ—ｔｒｉｅ树只有１个节点，由定义２可知， 有且仅有根节点的深度为１，故命题成立。 归纳假设：假设对所有的ｊ（１ Ｊ＜ ）命题成立， 即 ｓｊ＜２ｊ一１，证明ｊ＝Ｌ时命题亦成立。 归纳步骤：根据归纳假设，深度为 一１的 ＦＰ—ｔｒｉｅ树的节点数Ｓ 满足 一１ ＳＬ一】 ２ 一１。由约束３可知，深度为 的ＦＰ—ｔｒｉｅ树节 点数至多比深度为 一１的点数多２ 个，故即．ｊ＝＝ 时，深度为 的ＦＰ—ｔｒｉｅ最多有节点２ 一１＋２ ＝ ２ 一１个，满足ＳＬ ２ 一ｌ；由定义２可知，ＦＰ—ｔｒｉｅ 树深度为 意味至少有一个节点的父节点的深度为 一１，故 一１＋１＝Ｌ＜Ｓ 综上可知，当．ｊ＝ 的 时候，满足Ｌ ＳＬ≤２ 一１，故命题成立。 证毕 综合性质１和性质２可知，若待解析协议可以 用标准的ＦＰ～ｔｒｉｅ树表示，则生成的ＦＰ—ｔｒｉｅ树节点 数存在界限，即表明ＦＰ—ｔｒｉｅ树资源占用有限。 ２．２ ＰＰＡＦ流水结构 ＰＰＡＦ中流水线结构用来承载ＦＰ—ｔｒｉｅ树节点， 通过流水查找ＦＰ—ｔｒｉｅ树节点的方式实现协议报文解 析，如图３所示，硬件流水线结构主要由节点的存储 空间双通道ＲＡＭ，比较器和移位器３个部分组成。 其中，双通道的ＲＡＭ可以在同一时刻并发访问两个 图３硬件流水线结构图 地址，因而每一级流水线上任意时刻可以支持两个 查表操作，使得报文解析算法提高了一倍的吞吐率。 在每一阶段的流水处理中，首先要判断输入的 流水线级内容和本级流水线ＩＤ是否匹配，如匹配命 中则进行下一步操作，否则跳过本级流水线；其次 若匹配，则根据输入节点地址在双通道ＲＡＭ中读 取出对应的节点内容，按照图４描述的数据格式判 定该节点是内部结点还是叶子节点，如果是叶子节 点则输出解析结果，并且不再进行查找；如果是内 部节点则与输入的协议类型在比较器中进行判别比 较，选择匹配节点的左或是右子节点作为输出，并 根据数据偏移量使用移位器在数据包存储中提取新 的数据，最后将节点地址、流水线级和协议类型作 为输入，在下一时刻送入后一级流水线阶段。 匝 匝 ［ （ａ）实叶子节点格式 ｆｂ）￣ｌｔｔ子节点格式 （Ｃ）内部节点格式 图４ ＦＰ—ｔｒｉｅ树的节点数据格式 双通道ＲＡＭ中存储经过映射转换后ＦＰ—ｔｒｉｅ 树的节点，每个节点的具体字段如图４所示：操作 类型（２ ｂｉｔ），用于标识参与比较的协议类型字段与 预定值的判定关系，同时也指示节点的类型。 当操作类型为“００”的时候，代表该节点是一 个实叶子节点，后续内容为提取信息的长度，如图 ４（ａ）所示；当操作类型为“ｌｌ”的时候，如图４（ｂ） 所示，该节点代表一个虚叶子节点。当操作类型为 “０ｌ”或是“１０”的时候，代表该节点是一个内部 节点，“０１”对应着比较类型为大于，“１０”对应着 比较类型为等于，如图４ｆｃ）所示的内部节点格式中 的判定字段（１６ ｂｉｔ），为报文协议头部中的相关的协 １０８６ 电子与信息学报 第３５卷 议字段的判定值，比特掩码（４ ｂｉｔ）用于指示判定字 段的无效长度（０—１５ ｂｉｔ）；左／右子节点相距层数用 于指示ＦＰ—ｔｒｉｅ树左／右子节点所在流水线级与其父 节点所在流水线级之间的相对距离，左／右子节点地 址用于指示ＦＰ—ｔｒｉｅ树左／右子节点在流水线上的地 址；左／右子节点数据偏移用于指示提取下一个字段 需要偏移的比特位个数。 ＰＰＡＦ结构中比较器用于流水查找时选择匹配 的子树，为协议解析判断选择出正确的路径。将报 文头部中提取出的１６ ｂｉｔ协议字段与ＲＡＭ中存储 的协议字段预定值进行比较，比较的位宽由比特掩 码决定，最长为１６ ｂｉｔ比较、最短为１ ｂｉｔ比较；比 较的关系根据操作类型来决定，分为大于、等于两 种关系。比较操作的结果若是为真，则选择左子节 点对应的存储信息，并输出下一次待解析节点相距 本级流水线的距离，下一个解析节点所在流水级上 的地址以及下一次从数据包存储中提取相关字段的 相对偏移比特位；比较结果若为假，则选择右子节 点进行相应操作。 ＰＰＡＦ结构中移位器用于实现报文信息的萃 取，为了节约存储空间，采用相对偏移累加的方法 完成萃取报文头部信息。如图５所示，使用移位累 加寄存器记录上一次移位偏移的量值，并采用该值 参与下次偏移值的计算；比特移位器根据前一级的 计算结果在数据包存储中寻找萃取信息的起始位 置，并按照指定的长度，从起始位置提取连续的比 特串作为结果输出。 ３ ＰＰＡＦ结构实现 ＰＰＡＦ通过在每个接口都对应的建立ＦＰ—ｔｒｉｅ 树，实现接口灵活的解析能力。如图６所示， 硬件流水线上映射了两个网络接口的ＦＰ—ｔｒｉｅ树， 和Ｐ９分别为两个ＦＰ—ｔｒｉｅ树的根节点。每次到 达系统的报文，首先根据网络接口的不同，将报文 送至对应的解析树根节点，每经过一级ＦＰ—ｔｒｉｅ树的 节点，都会被进行一次协议规则的判断，进而在两 个两子树中选择一路进行下一步查找，直到找到叶 子节点为止；若在流水线的最后一级匹配到叶子节 图５移位器结构图 ｌ级 ２级 ３级 ４级 ５级 ６级 图６ ＰＰＡＦ流水查表示意图 点，则直接输出结果，若是在前几级流水线上匹配 到叶子节点，则该报文仍需要等待未处理的流水线 长的时间，用以保证报文的处理时延等长，进而达 到结构对报文的顺序处理。 ３．１节点映射算法 ＦＰ—ｔｒｉｅ树节点需要被映射到流水线上才能完 成协议解析的功能，最简单的映射方式就是按照ｔｒｉｅ 树的深度将节点顺序分配到硬件流水级上，虽然这 种简单的方式可以保证流水线正常的线速操作，但 是ＦＰ—ｔｒｉｅ树结构的不规则性，会导致映射后的流水 线存储空间不均衡的占用，降低存储空间的利用率， 同时也会影响节点维护的效率，甚至影响系统整体 的性能。针对ＦＰ—ｔｒｉｅ树映射过程中存储空间的均衡 问题，提出最优化的数学模型，首先给出模型中的 符号含义，如表２所示。 节点映射的最优化数学模型为 ｍｉｎ ０爨＝ｌ…， ，． Ｄｉ （１） 条件１若ＦＰｔｒｉｅ 和ＦＰｔｒｉｅ８为ＦＰ—ｔｒｉｅ树中 表２公式及符号的含义 符号 含义 第ｉ级流水线上映射的节点数 接口对应结构不同的ＦＰ—ｔｒｉｅ树的总数 流水线的深度 第Ｊ个接口对应的ＦＰ—ｔｒｉｅ树节点数 第ｉ个ＦＰ．ｔｒｉｅ树 ＦＰ—ｔｒｉｅ树中的节点 ＦＰ—ｔｒｉｅ树节点的子节点 ＦＰ—ｔｒｉｅ树的根节点 ＦＰ—ｔｒｉｅ树的节点总数 ＦＰ—ｔｒｉｅ树中节点的深度 ＦＰ—ｔｒｉｅ树节点映射在流水线的深度 节点映射的条件判定规则 第５期 董永吉等：一种新的高速报文解析结构研究 １０８７ 节点， ＦＰｔｒｉｅ ＝ｃｈｉｌｄ ｎｏｄｅ（ＦＰｔｒｉｅ日），则ｐｉｐｅ ｄｅｐｔｈ（ＦＰｔｒｉｅ ） ｐｉｐｅ—ｄｅｐｔｈ（ＦＰｔｒｉｅＢ）。即为了保 证硬件流水查找的有序性，ＦＰ—ｔｒｉｅ树的父节点 （ａｎｃｅｓｔｏｒ）－－定映射在子节点（ｄｅｓｃｅｎｄａｎｔ）所在流水 ３．２ ＦＰ－ｔｒｉｅ树节点更新 根据不同网络业务的组网需求，ＰＰＡＦ需要动 态调整ＦＰ—ｔｒｉｅ树节点内容来实现解析能力的灵活 变更。而ＦＰ—ｔｒｉｅ树的更新对应到节点的变化有３ 线之前。 日∑ 条件２若ＦＰｔｒｉｅＲ为ＦＰ—ｔｒｉｅ树的根节点ＦＰ ｔｒｉｅＲ＝ｔｒｅｅ＋ —ｒｏｏｔ（ ）， ｐｉｐｅ—ｄｅｐｔｈ（ＦＰｔｎ ｒｉｅＲ）＝１。 根据条件１和条件２可知有且仅有ＦＰ—ｔｒｉＩ ｌｅ树的 根节点映射在第１级流水线上，即Ｄ ＝ 。∑芦 条件３ 结合建立的最优化模型，本文提出了一种类似 二叉树前序遍历的启发迭代的节点映射算法ＮＴＰ， 实现所有ＦＰ—ｔｒｉｅ树节点到流水线上的映射关系，算 法流程如表３所示。其中，ｍａｐ ｃｏｎｄｉｔｉｏｎｆ・）为映 射节点的条件判定规则，判断结果为真的节点必须 映射到当前对应的流水线上。 代表除了第１级 流水线外，其余流水线级上节点数量的理论平均值。 表３节点映射算法ＮＴＰ 节点映射算法ＮＴＰ （１） Ｓｏｒｔ ｔｈｅ ａｌｌ ｔｈｅ ＦＰ—ｔｒｉｅｓ ｉｎ ｄｅｃｒｅａｓｉｎｇ ｏｒｄｅｒ ｏｆ ｎｏｄｅ ａｍｏｕｎｔ， ｛ ， ，…， ｝，ｔｒｅｅ—ｓｉｚｅ（ ） ≥ｔｒｅｅ—ｓｉｚｅ（ ） … ｔｒｅ—ｓｉｚｅ（ ） （２） ｆｏｒ ｉ＝１ ｔｏ ｎ （３） ＦＰｔｒｉｅ￣ｔｒｅｅ—ｒｏｏｔ（ ）； （４） ＦＰｄｅｐｔｈ￣ｔｒｅｅ—ｄｅｐｔｈ（ＦＰｔｒｉｅ）； （５） ＭＡＰ（ＦＰｔｒｉｅ，ＦＰｄｅｐｔｈ）ｂｅｇｉｎ （６） ｉｆ（ＦＰｔｒｉｅ ｉｓ ｎｏｔ ｍａｐｐｅｄ） （７） ｉｆ ｍ印一。。ＩＩｄｉｔｉ。“（ＦＰｔｒｉ。）＝ＴＲＵＥ∞ Ｄ｝Ｐ Ｄｔｈ Ｄ ｔｈｅｎ （８）ｐｉｐｅ—ｄｅｐｔｈ（ＦＰｔｒｉｅ）￣ＦＰｄｅｐｔｈ； （９） Ｐｄ印ｔｈ一 Ｐｄｅｐｔｈ＋１； （１０） ｅｌｓｅ （１１） ＦＰｄｅｐｔｈ￣ＦＰｄｅｐｔｈ＋ｌ （１２） ＭＡＰ（ＦＰｔｒｉｅ，ＦＰｄｅｐｔｈ）； （１３） ｅｎｄｉｆ （１４） ｅｎｄｉｆ （１５） ＦＰｄｅｐｔｈ￣ＦＰｄｅｐｔｈ￣ｌ （１６） ＭＡＰ（ＦＰｔｒｉｅ￣ｌｃｈｉｌｄ，ＦＰｄｅｐｔｈ）； （１７） ＭＡＰ（ＦＰｔｒｉｅ￣ｒｃｈｉｌｄ，ＦＰｄｅｐｔｈ）； （１８） ｅｎｄ （１９） ｅｎｄ ｏｆ 种情况：（１）修改协议节点的内容；（２）插入新的节点： （３）删除已有的节点。第（１）种类型的更新相对容易操 作，只需要根据节点的存储地址，在相应的流水线 上定位到该节点，并更改相应的内容即可完成更新。 而第（２）和第（３）种类型的更新相对复杂，由于 ＦＰ—ｔｒｉｅ树的非叶子节点都有两个子节点，所以任一 个节点的插入或删除操作至少涉及到两个节点，而 在一些复杂情况下，大量的节点插入或删除操作甚 至会导致整个流水线节点分布不均衡，需要及时迅 速地完成节点的重新映射。 ＰＰＡＦ采用了一种在流水线空闲作业中通过插 入读写双口ＲＡＭ操作实现节点内容的快速更新。 在更新过程中，首先根据流水级ＩＤ找到匹配的流水 线，然后根据节点地址找到需要更新的节点，利用 正常协议解析流水查找的空隙，按照读／写指示在存 储空间上更新节点。如图７所示，利用流水空闲在 时刻可以对节点Ｆ进行更新，在ｔｉ＋ 时刻可以更 新节点Ｄ，这种方法既能保证协议解析的吞吐量， 又可以完成协议解析能力的快速更新。 图７节点更新方法 ４测试结果 ４．１实验环境设计 本文采用ＮｅｔＦＰＧＡ一１０ Ｇ板卡上Ｘｉｌｉｎｘ Ｖｉｒｔｅｘ－ ＸＣＶＴＸ２４０Ｔ一２ＦＦ１７５９—２ ＦＰＧＡ来验证ＰＰＡＦ算法 和结构。该ＦＰＧＡ可用的逻辑资源为１８，７２０可编程 逻辑单元（ｃｏｎｆｉｇｕｒａｂｌｅ ｌｏｇｉｃ ｂｌｏｃｋｓ）、２．４００ ｋｂｉｔ分 布式存储单元（Ｄｉｓｔｒｉｂｕｔｅｄ ＲＡＭ）和１１．６６４（３２４× ３６）ｋｂｉｔ块存储单元（Ｂｌｏｃｋ ＲＡＭｓ），实验验证使用 Ｘｉｌｉｎｘ ＩＳＥ １３．３和Ｓｙｎｐｌｉｆｙ Ｐｒｏ Ｅ ２０１１—３ ＳＰ１工具 软件。 鉴于ＮｅｔＦＰＧＡ板卡的接口数量被为４× １０ Ｇ，无法进行扩展，为了验证ＰＰＡＦ结构的有效 １０８８ 电子与信息学报 第３５卷 性，在ＦＰＧＡ内部模拟搭建了一个３２路接口的 水线的ＰＰＡＦ结构资源与性能对比，其中资源逻辑、 ＰＰＦＡ结构，该结构为３２接口分别提供的解析 ＢＲＡＭ的占用和时钟频率来源于ＩＳＥ的Ｐｏｓｔ ｐｌａｃｅ 能力，并有一个可配的深度最大为８的流水结构。 ａｎｄ ｒｏｕｔｅ ｒｅｐｏｒｔ的报告。观察可以发现，随着硬件 在流水线的构建上，己知操作类型、判定字段 流水线层数的递增，ＰＰＡＦ结构中ＢＲＡＭ使用的个 和比特掩码的长度一定，分别为２ ｂｉｔ，１６ ｂｉｔ和４ 数逐渐递增，始终与流水线的深度保持２倍的关系， ｂｉｔ，令日为流水线深度，则相邻两个节点间的相距 层数用ｆｌｏｇ 日１ ｂｉｔ表示，令左／右子节点地址宽度 与前文关于ＢＲＡＭ资源占用的分析一致；而不同深 为ｗ ｂｉｔ，左／右子节点数据偏移分别为Ｖ ｂｉｔ，则图 度流水线的对应的时钟频率会随着ＢＲＡＭ及逻辑 ４显示的节点占用的比特位宽ｍ可以表示为 资源的增多而减小，但即使是流水线深度达到８时， ｍ＝２＋１６＋４＋２［１ｏｇ２Ｈ１＋２ｗ＋２ｖ （３） ＰＰＡＦ也仅占用了不到３％的片上逻辑资源，同时 ｍ＝２２＋２（［１ｏｇ２ Ｈ１＋Ｗ＋ ） （４） ＰＰＡＦ的时钟频率仍然可以达到４．８４４ ｎｓ（２０６．４４ ＭＨｚ），由于本结构采用双通道ＢＲＡＭ，可以支持 整个结构占用的存储空间 大小为 两个流水查找过程并行进行，则对于最小的以太网 Ｍ＝ｍ Ｘ Ｈ×２” （５） 包（６４ ｂｙｔｅ１，吞吐量至少可以达到２０６．４４ ＭＨｚ×６４ 由于实验中流水线的最大深度为８，所以左／右 ×８ ｂｉｔ×２＝２１１ Ｇｂｐｓ。 子节点相距层数分别为ｌｏｇ ８＝３。令左／右子节点 地址分别为１０ ｂｉｔ，左／右子节点数据偏移分别为９ 表４不同深度流水线的ＰＰＡＦ结构资源与性能对比表 ｂｉｔ，则每个节点总共占用６２ ｂｉｔ的存储空间，根据 式（４），式（５）可知，整个结构共占用 ６６ｘ ８ｘ ２加 ＝５４０．４７２ ｋｂｉｔ空间。ＸｉｌｉｎｘＶｉｒｔｅｘ一５ ＦＰＧＡ中每块 Ｂｌｏｃｋ ＲＡＭ最多存储３６ ｋｂｉｔ数据，且可以灵活的 配置成两个的１８ ｋｂｉｔ ＲＡＭ或一个３６ ｋｂｉｔ ＲＡＭ（３６×１０００ ｂｉｔ１。考虑到硬件节点的位宽 （３６＜６６＜７２），所以每级别流水线需要２块ＢＲＡＭ 来构建。 为验证节点映射算法的均衡性，对应着虚拟的 图９给出了ＰＰ，Ｋａｎｇａｒｏｏ和ＰＰＡＦ ３种协议解 接口模拟构造产生了３２个ＦＰ—ｔｒｉｅ树，所有ＦＰ—ｔｒｉｅ 析结构在ＮｅｔＦＰＧＡ实验平台下，对协议树Ｅｔｈｅｒｎｅｔ 树的最大深度为８，最小深度为１，共有３９６个节点， —ＶＬＡＮ—ＭＰＬＳ解析时资源和性能上的对比。如 其中实叶子节点８５个，虚叶子节点３２个。采用ＮＴＰ 图９（ａ）所示，相对于Ｋａｎｇａｒｏｏ，ＰＰＡＦ在ｓｌｉｃｅ资源 算法将全部３２个接口的ＦＰ—ｔｒｉｅ树映射到深度为８ 的占用上基本持平，但是节约了１０％左右的ＢＲＡＭ 的流水线上。 资源，但在处理能力上，ＰＰＡＦ的处理能力达到２２８ ４．２结果与分析 Ｇｂｐｓ远高于Ｋａｎｇａｒｏｏ的１０ Ｇｂｐｓ；图９（ｂ１中的 图８给出了两种节点映射算法映射后流水线节 ＰＰＡＦ。代表两个并行处理的ＰＰＡＦ结构，由于硬件 点数目分布图，其中ｓｉｍｐｌｅ方法采用直接对应映射 的方式，将ＦＰ—ｔｒｉｅ树节点按照其深度对应映射到相 并行处理的特性，所以ＰＰＡＦ 在资源的占用上是 同深度的流水线级。通过观察可以发现，ＮＴＰ算法 ＰＰＡＦ一倍的同时，处理能力也为单个ＰＰＡＦ的一 除了第１级节点相对少一些外，其他流水线级的节 倍，达到２２８ Ｇｂｐｓ×２＝４５６ Ｇｂｐｓ，远高于ＰＰ的 点基本按照算法的设计，在流水线上基本均匀分布。 ３４１ Ｇｂｐｓ的处理能力，虽然占用了少量不到４％的 而ＮＴＰ算法第１级的节点明显少于其他级的流水线 ＢＲＡＭ资源，但相对于ＰＰ系统，也节省了２７％的 节点数目是因为根据映射算法的约束条件２，第１ ｓｌｉｃｅ资源。 级流水线能且只能存放每个接口ＦＰ—ｔｒｉｅ树的根节 综上，相对于两种已有的算法，ＰＰＡＦ结构在 点，所以第１级流水线共存放了３２个节点。同时， 资源占用较小的同时具有较强的处理能力，在资源 对比可以发现，ＮＴＰ算法相对于ｓｉｍｐｌｅ方法可以有 占用和处理速率上取得了较好的均衡，并且不同于 效解决节点占用存储资源分布不均的问题，并充分 其他两种解析结构，ＰＰＡＦ结构为每个接口都建立 优化使用存储空间。 专用的ＦＰ—ｔｒｉｅ树，所以ＰＰＡＦ可以为每个接口提 表４给出了基于ＮｅｔＦＰＧＡ平台的不同深度流 供的解析能力，更适合未来网络柔性的需求。 第５期 ∞加∞锄∞∞洳加 《 啦 董永吉等：一种新的高速报文解析结构研究 １０８９ 口８ｎＣｅ ｉ １ Ｇｂｐｓ Ｓｌ６ 婚 碍 ３５ 誉 电 翳 ２５ ＿ＢＲＡＭ 要１２ 篱８ ０ 舞 ＊ 娓 鬟 澍 ４５（ｉ Ｇｂｔ ０ ｌ５ 肇４ 蓍， １ ２ ３ ４ ５ ６ ７ ８ 芝 ＰＰＡＦ Ｋａｎｇａｒｏｏ ５ ｌ厂］ 一 ＰＰＡＦ２ ＰＰ 流水线ＩＤ （ｎ）ＰＰＡＦ与Ｋａｎｇｎｒｏｏ资源似 能对比 ｍ）ＰＰＡＦ。与ＰＰ资源性能对比 图８流水线节点数目对比图 ５结论 针对传统的报文解析结构在功能上无法适应业 务变化、协议处理上无法灵活扩展及资源上不支持 虚拟化等问题，本文提出了一种应用于路由转发的 报文解析结构ＰＰＡＦ，该结构采用流水线配合二叉 ｔｒｉｅ树来实现协议解析功能高效性和灵活性，采用 节点映射算法来均衡各级流水线上的节点数目，以 达到优化存储空间的目的，并基于ＮｅｔＦＰＧＡ实验 平台仿真验证了ＰＰＡＦ的可行性和有效性，为可重 构信息通信基础网络体系研究的实验平台设计提供 了参考依据。 参考文献 ［１］ Ｋａｔｉｅ Ｖ Ｐ ａｎｄ Ｉｎｏｕｅ Ｍ．Ｉｎｔｒｏｄｕｃｉｎｇ ｍｕｌｔｉ—ＩＤ ａｎｄ ｍｕｌｔｉ— ｌｏｃａｔｅｒ ｉｎｔｏ ｎｅｔｗｏｒｋ ａｒｃｈｉｔｅｃｔｕｒｅ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ，２０１２，５０（３）：１０４—１１０． 【２１ Ｋｈａｎ Ａ，Ｚｕｇｅｎｍａｉｅｒ Ａ，Ｊｕｒｃａ Ｄ，ｅ ａ１．．Ｎｅｔｗｏｒｋ ｖｉｒｔｕａｌｉｚａｔｉｏｎ：ａ ｈｙｐｅｒｖｉｓｏｒ ｆｏｒ ｔｈｅ Ｉｎｔｅｒｎｅｔ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ，２０１２，５０（１）：１３６—１４３． ［３】Ｐａｌｋｏｐｏｕｌｏｕ Ｅ，Ｓｃｈｕｐｋｅ Ｄ Ａ，ａｎｄ Ｂａｕｓｃｈｅｒｔ Ｔ．Ｓｈａｒｅｄ ｂａｃｋｕｐ ｒｏｕｔｅｒ ｒｅｓｏｕｒｃｅｓ：ｒｅａｌｉｚｉｎｇ ｖｉｒｔｕａｌｉｚｅｄ ｎｅｔｗｏｒｋ ｒｅｓｉｌｉｅｎｃｅ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ，２０１１，４９（５）： １４０—１４６． ［４】 Ｎａｏｕｓ Ｊ，Ｅｒｉｃｋｓｏ Ｄ，Ｃｏｖｉｎｇｔｏｎ Ａ，ｅｔ ａ１．．Ｉｍｐｌｅｍｅｎｔｉｎｇ ａｎｄ ｄｅｐｌｏｙｉｎｇ ａｎ ｏｐｅｎｆｌｏｗ ｓｗｉｔｃｈ ｏｎ ｔｈｅ ＮｅｔＦＰＧＡ ｐｌａｔｆｏｒｍ［Ｃ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ ＡＣＭ／ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｒｃｈｉｔｅｃｔｕｒｅｓ［ｏｒ Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｙｓｔｅｍｓ， Ｓａｎ Ｊｏｓｅ，ＣＡ，ＵＳＡ，Ｎｏｖ．２００８：卜９． ［５】 Ｍｕｈａｍｍａｄ Ｂｉｌａｌ Ａｎｗｅｒ，Ｍｕｒｔａｚａ Ｍｏｔｉｗａｌａ，Ｍｕｋａｒｒａｍ ｂｉｎ Ｔａｒｉａ， ａ１．．Ｓｗｉｔｃｈｂｌａｄｅ：ａ ｐｌａｔｆｏｒｍ ｆｏｒ ｒａｐｉｄ ｄｅｐｌｏｙｍｅｎｔ ｏｆ 图９ ３种解析结构资源和性能对比 ｎｅｔｗｏｒｋ ｐｒｏｔｏｃｏｌｓ ｏｎ ｐｒｏｇｒａｍｍａｂｌｅ ｈａｒｄｗａｒｅ［Ｃ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＣＯＭＭ Ｃｏｎｆｅｒｅｎｃｅ．Ｎｅｗ Ｄｅｌｈｉ． Ｉｎｄｉａ，Ａｕｇ．２０１０：１８３—１９４． Ｘｉｅ Ｇ Ｇ，Ｈｅ Ｐ，Ｇｕａｎ Ｈ Ｔ，ｅｔ ａ１．．ＰＥＡＲＬ：ａ ｐｒｏｇｒａｍｍａｂｌｅ ｖｉｒｔｕａｌ ｒｏｕｔｅｒ ｐｌａｔｆｏｒｍ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｍａｇａｚｉｎｅ， ２０１１，４９（７）：７１—７７． ［７ Ｋｏｚａｎｉｔｉｓ Ｃ，Ｈｕｂｅｒ Ｊ，Ｓｉｎｇｈ Ｓ，ｅｔ ａ１．．Ｌｅａｐｉｎｇ ｍｕｌｔｉｐｌｅ ｈｅａｄｅｒｓ ｉｎ ａ ｓｉｎｇｌｅ ｂｏｕｎｄ：ｗｉｒｅ—ｓｐｅｅｄ ｐａｒｓｉｎｇ ｕｓｉｎｇ ｔｈｅ Ｋａｎｇａｒｏｏ ｓｙｓｔｅｍｉＣ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２９ｔｈ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｓａｎ Ｄｉｅｇｏ，ＣＡ， ＵＳＡ，Ｍａｒ．２０１０：８３０—８３８． Ｚａｎｅ Ｆ，Ｎａｒｌｉｋａｒ Ｇ，ａｎｄ Ｂａｓｕ Ａ．ＣｏｏｌＣＡＭｓ：ｐｏｗｅｒ—ｅｆｉｆｃｉｅｎｔ ＴＣＡＭｓ ｆｏｒ ｆｏｒｗａｒｄｉｎｇ ｅｎｇｉｎｅｓ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２２ｎｄ ＩＥＥＥ ＩＮＦＯＣＯＭ，Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＵＳＡ，２００３：４２—５２． Ａｔｔｉｇ Ｍ ａｎｄ Ｂｒｅｂｎｅｒ Ｇ．４００ Ｇｂ／ｓ ｐｒｏｇｒａｍｍａｂｌｅ ｐａｃｋｅｔ ｐａｒｓｉｎｇ ｏｎ ａ ｓｉｎｇｌｅ ＦＰＧＡ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ／ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｙｓｔｅｍｓ，Ｂｒｏｏｋｌｙｎ，ＮＹ，ＵＳＡ，Ｏｃｔ．２０１ ｈ １２—２３． 【１Ｏ Ｐａｏ Ｄ，Ｌｕ Ｚ，ａｎｄ Ｐｏｏｎ Ｙ Ｈ．Ｂｉｔ—ｓｈｕｆｌｆｅｄ ｔｒｉｅ：ＩＰ ｌｏｏｋｕｐ ｗｉｔｈ ｍｕｌｔｉ—ｌｅｖｅｌ ｉｎｄｅｘ ｔａｂｌｅｓ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｋｙｏｔｏ，Ｊａｐａｎ， Ｊ１ｉｎｅ ２０】】：】一５． 董永吉： 男，１９８３年生， 博士生，研究方向为宽带信息网络． 郭云飞： 男，１９６３年生， 教授，博士生导师，主要研究领域为宽 带信息网络． 黄万伟 男，１９７９年生， 讲师，研究方向为宽带信息网络 夏军波 男，１９８１年生， 讲师，研究方向为宽带信息网络
