面向转发的双向高速报文解析结构

发布时间：2019-10-08 05:54

【摘要】：为进一步提升未来互联网体系结构的实验平台对转发报文高速灵活解析的能力,提出了一种面向转发的双向报文解析结构(BiPPAF)。该结构由以下2个方面构成:在协议的解析表达上,利用二叉trie树动态灵活的字符串组织方式,实现协议解析表达的可扩展;在协议解析的处理上,采用硬件流水线通过高速流水的查表方式,实现协议解析的高性能。BiPPAF结构通过为每个网络接口建立协议二叉trie树实现接口独立的协议解析能力,并利用节点映射算法来完成流水线和二叉trie树之间的关联,能够均衡各级流水线上二叉trie树的节点数目优化存储空间的使用。仿真实验表明,与Packet Parsing方法相比,BiPPAF结构的协议处理速率提升了31%,而资源占用降低了64%。
【图文】：

结构组成

活并快速地实现新协议的解析，本文提出了由转发协议二叉ｔｒｉｅ树（ｆｏｒｗａｒｄｉｎｇｐｒｏｔｏｃｏｌｔｒｉｅ，ＦＰ－ｔｒｉｅ）和双向流水线２部分组成的ＢｉＰＰＡＦ结构，通过结合两者的优势实现快速灵活的协议解析功能。ＢｉＰＰＡＦ结构如图１所示。在ＢｉＰＰＡＦ结构中，转发协议二叉ｔｒｉｅ树将传统的报文解析过程转换为二叉ｔｒｉｅ树，实现报文解析的灵活表示；双向流水结构则充分利用硬件并行处理的特性，采用线性流水的查找ＦＰ－ｔｒｉｅ树实现图１ＢｉＰＰＡＦ结构组成图协议解析，达到高速的处理能力。１．１转发协议二叉ｔｒｉｅ树定义１节点深度是该节点到根节点的最大距离，根节点的深度为１，其余节点的深度为双亲深度的最大值加１；ＦＰ－ｔｒｉｅ树中最大的节点深度称为ＦＰ－ｔｒｉｅ树的深度。定义２叶子节点只能包含解析的结果，其中包含正常解析内容的称为实叶子节点，反之包含无法解析的称为虚叶子节点。定义３若二叉ｔｒｉｅ树被称为ＦＰ－ｔｒｉｅ树，则应满足如下条件：条件１每个协议的识别判定可能需要多个定位规则，但每个非叶子节点内只存储一个定位规则和２个跳转的指针，其中定位规则包含该协议相关字段的判定取值及判定方法；条件２任一个非叶子节点必须有２个子节点，但不能同时以２个实叶子节点作子节点；条件３一个ＦＰ－ｔｒｉｅ树最多只能有一个虚叶子节点；条件４从根到叶子节点的路径上的所有节点（不包括叶子节点）包含的定位规则顺序连接表示报文解析的过程。由上述的定义可知，协议二叉ｔｒｉｅ树具有如下的性质

协议树,树结构

个节点的父节点的深度为Ｌ－１，故Ｌ－１＋１＝Ｌ≤ＳＬ。综上可知，当ｋ＝Ｌ的时候，满足Ｌ≤ＳＬ≤２Ｌ－１，故命题成立。推论１对于节点数ＳＬ一定的ＦＰ－ｔｒｉｅ树，深度满足ｌｂ（ＳＬ＋１）≤Ｌ≤ＳＬ。证明由性质２可知，Ｌ≤ＳＬ且ＳＬ≤２Ｌ－１，故ＳＬ＋１≤２Ｌ，进而ｌｂ（ＳＬ＋１）≤Ｌ，所以得到结论：ｌｂ（ＳＬ＋１）≤Ｌ≤ＳＬ。（ａ）协议树Ａ（ｂ）协议树Ｂ图２ＦＰ－ｔｒｉｅ树结构综上可知，，ＦＰ－ｔｒｉｅ树的节点数和深度都存在上下限，即实现ＦＰ－ｔｒｉｅ树节点占用的存储空间有限，表明ＦＰ－ｔｒｉｅ树物理可实现。目前，网络设备在多数情况下需要根据多协议标签交换协议（ｍｕｌｔｉ－ｐｒｏｔｏｃｏｌｌａｂｅｌｓｗｉｔｃｈｉｎｇ，ＭＰＬＳ）和ＩＰ协议（ＩｎｔｅｒｎｅｔＰｒｏｔｏｃｏｌ）进行数据的转发，本文根据网络实际情况，构造了２个协议树Ａ与Ｂ，其中协议树Ａ描述了以太网协议内嵌虚拟局域网协议（ｖｉｒｔｕａｌｌｏｃａｌａｒｅａｎｅｔｗｏｒｋ，ＶＬＡＮ）及ＭＰＬＳ、ＩＰｖ６的协议嵌套关系，而协议树Ｂ描述了８０２．３ＳＮＡＰ协议内嵌ＩＰｖ４的协议嵌套关系，图２中分别对协议树Ａ和协议树Ｂ进行了图形化表示。图２中的２个ＦＰ－ｔｒｉｅ树的节点类型共分为３种情况：①Ｐ１和Ｐ１１代表协议无法识别的叶子节点，用于指示报文无法解析；②Ｐ４、Ｐ６和Ｐ１０分别代表了识别ＭＰＬＳ、
【作者单位】：国家数字交换系统工程技术研究中心;解放军理工大学指挥信息系统学院;
【基金】：国家“973计划”资助项目(2012CB315901,2012CB315905) 国家“863计划”资助项目(2011AA01A103) 国家科技支撑计划资助项目(2011BAH19B01)
【分类号】：TP393.02

【参考文献】