A Trie-based Approach to Fast Flow Recognition for OpenFlow Laboratory of Dependable Systems and Network - Group of Network Security A Trie-based Approach to Fast Flow Recognition for OpenFlow 今天我报告的题目是《基于特里树的OpenFlow流快速匹配方法》 Reporter : Tong SHEN Advisor : Prof. Dafang ZHANG May 21st, 2014

Contents Background Related works Our approach Evaluation Conclusion 今天的报告主要分为五大部分： 背景与动机(点目录) 相关工作(点目录) 我们优化的快速匹配方法(点目录) 然后是实验部分(点目录) 最后是总结(点目录) Laboratory of Dependable Systems and Network - Group of Network Security

Traditional Internet and SDN Challenges to traditional internet architecture Complicated network application Ever-growing data traffic Business requirements Features of SDN (Software Defined Networks) Separate controlling panel from forwarding panel Opening programmable interface Centralized controlling 大家知道，随着越来越复杂的网络应用，日益增长的数据量，以及越来越丰富的业务需求，给传统的网络架构带来了极大的压力。为了解决这个问题，SDN(Software Defined Networks)孕育而生，这是少数几个由使用者提出来的架构，大多数都是由运营商或者厂商提出来的。IPV6等。 SDN的特点有： 控制面与（数据面）转发面分离 开放的可编程接口 以及集中控制 我们来看一下原理图 Laboratory of Dependable Systems and Network - Group of Network Security

SDN Architecture APPLICATION LAYER BUSINESS APP API API API CONTROL LAYER SDN Control Software NETWORK SERV 首先看到的是SDN将网络分为3层，基础设施、控制、应用层 基础设施层，是一些硬件设备，处理一些简单的操作，如交换机等 控制层即是一些提供服务的软件，用于控制基础设备中的硬件设备，比如修改流表等 最上层则是一些应用 应用通过api指示控制器做相应的修改 控制器通过数据面的接口改写数据，满足应用需求。 这一层的协议有很多，但其中最著名的也是应用最多的就是openflow Control Data Plane Interface ( e.g., OpenFlow ) INFRASTRUCTURE LAYER NETWORK DEV NETWORK DEV NETWORK DEV NETWORK DEV Laboratory of Dependable Systems and Network - Group of Network Security

OpenFlow OF (OpenFlow) is a part of SDN, presented by ONF (Open Networking Foundation) OF runs both on Controller and Switch OF is not mature Of是sdn的一部分，由onf提出，最早是斯坦福研究的一个实验室项目 Of同时运行在交换机和控制器上 目前为止，of还很不成熟 来看一下原理图 Laboratory of Dependable Systems and Network - Group of Network Security

Issues Issues of OF This is what we solve Communication Too flexible to compatibility Efficiency of forwarding Forwarding on large scale tables This is what we solve Of存在的一些问题 不同版本的控制器与交换机 以及 不同厂商生产的控制器和交换机 相互通信都存在问题，兼容性存在很大问题 转发的效率不高 尤其是在大规模的用户下，转发的时间复杂度程线性增长 我们方法所解决的问题主要是最后两个，尤其是在规模上，我们的方法在流表大小上的时间复杂度为O(1) 返回返回返回返回返回 Laboratory of Dependable Systems and Network - Group of Network Security

Specification Specification says that Two matching mechanisms OF entries have multi matching fields Entries in flow table can have wildcards Matched entry with highest priority will be apply Two matching mechanisms Exact match based on hash Fuzzy match with wildcards Of的协议说of存在多个匹配字段 每个流表项允许使用通配符 所有匹配的项中，选择优先权最高的应用他的action 现有的匹配机制有两种： 1、基于哈希表的精确匹配 2、基于通配符的模糊匹配 Laboratory of Dependable Systems and Network - Group of Network Security

Exact Match Based on Hash Mathing fields & a action field A hash value field & a outdate flag Hash Value OpenFlow match fields Discard flag Action Ingress port … Port src Port dst 0xAAAA I L U 1 X 0xBBBB J M V Y 0xCCCC K N W Z 如果只用精确匹配表，那么在空间和成本上将会是一种巨大的浪费 Hash Value = Hash( Ingress port, …, Port src, Port dst ) Laboratory of Dependable Systems and Network - Group of Network Security

Fuzzy Match with Wildcards Mathing fields & a action field A priority field & a wildcards mask field Priority OpenFlow match fields Wildcard flag Action Ingress port … Port src Port dst 0xAAAA * L 1…01 X 0xBBBB J 0…11 Y 0xCCCC N W 1…00 Z 匹配效率低，时间随着表的增大而线性增长 Laboratory of Dependable Systems and Network - Group of Network Security

Compromised Solution A compromised solution is to use both exact-match table and wildcard-aware table at the meantime and regard the exact- match table as a cache for wildcard-aware table The same problem, the performance cannot be guaranteed under the circumstance of many users 一种较为理想的方法是同时使用两种表。 哈希匹配表作为 通配符表的缓存(dian) 但是这种算法还是存在大规模用户下效率低下的问题。我们来看下原因 Laboratory of Dependable Systems and Network - Group of Network Security

Forwarding Pseudo-code Forwarding Algorithms Pseudo-code 0: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: if matched in Exact-match Table { ----apply Action; } else { ----if matched in Wildcard-aware Table { --------update Exact-match Table; --------apply Action; ----} else { --------send to controller; --------update Wildcard-aware Table; ----} } This is the core issue, and its time Complexity is O(n) 这是转发算法的伪代码 Laboratory of Dependable Systems and Network - Group of Network Security

Others Some hardware has been proposed for handling the flow forwarding GPU FPGA netFPGA multi-core CPU However, the forwarding efficiency is still restricted to the size of the flow table 另外的工作主要是运用了不同硬件来加速匹配，并没有从结构上来解决问题 Laboratory of Dependable Systems and Network - Group of Network Security

Use GPU Problem Scan twice ( O(2n) ) Small scale （dian）还存在一个问题，最后在选择优先级最高项的时候又扫描了一遍表，使时间复杂度为O（2n），虽然系数在理论上可以忽略，但在实际应用中很重要。时间差一辈呢。 返回返回返回返回返回 Laboratory of Dependable Systems and Network - Group of Network Security

Approach and Contribution Our approach We used Trie to achieve wildcard-aware table, avoiding the linear search Our contribution The time complexity matching in wildcard- aware table have been upgraded from O(n) to O(1) Make OF suitable in huge networks 我们的方法是利用特里树实现通配符表 我们的贡献是将通配符表的匹配时间复杂度提高到了O（1） 使of能够适用于大型网络 Laboratory of Dependable Systems and Network - Group of Network Security

Structure OF has multiple matching fields, and the bits of each matching field varies, which requires a corresponding Trie to every matching field Leaf node collects normal entry’s index Root node of Trie collects all the index of entries inlcuding wildcards A small table keeps every entry’s priority and action 把每个匹配字段分开来建立特里树 跟节点存储通配符的索引，叶子结点存储普通索引，另外一个small table 根据索引存储优先级和action 下面用一个简单的例子来讲一下我们的结构。 Laboratory of Dependable Systems and Network - Group of Network Security

Structure (Cont.) e.g. Priority OpenFlow match fields Action VLAN id IP src IP dst Port src Port dst 2 0100 1011 1001 * FW 1 1101 1000 Drop 1111 101 001 3 1110 000 Mod e.g. No. Priority Action 1 2 3 4 2 FW Just keep, not use to be matched 1 Drop 1 FW 3 Mod Laboratory of Dependable Systems and Network - Group of Network Security

Structure (Cont.) e.g. 3 1 Priority OpenFlow match fields Action 1 Priority OpenFlow match fields Action VLAN id IP src IP dst Port src Port dst 2 0100 1011 1001 * FW 1 1101 1000 Drop 1111 101 001 3 1110 000 Mod No. Pri 1 2 3 4 1 1 1 1 2 ,4 Laboratory of Dependable Systems and Network - Group of Network Security

Structure (Cont.) e.g. Priority OpenFlow match fields Action VLAN id IP src IP dst Port src Port dst 2 0100 1011 1001 * FW 1 1101 1000 Drop 1111 101 001 3 1110 000 Mod Laboratory of Dependable Systems and Network - Group of Network Security

Structure (Cont.) e.g. 这就是最终的结构 我们的思想是利用gpu并行计算，但目前还只是基于cpu的， 最后还有一个问题就是对所有集合求交，这个过程理论上是n平方的复杂度，但是我在实验中测试出来，求交这个过程只占总时间53分之1 当然我也为此做了优化 一种方式是开辟一段空间，用bit来存储每个集合中的数，最后只要做与运算，但是最终要获取结果，还要对这段空间的每一个位做遍历，所以时间复杂度还是线性级，而且空间开销会很大。 第二种方法是对所有的集合排序，然后取元素最少的集合遍历，看这些元素是否在其他集合中存在，这个改进的时间复杂度是nlogn。 这个改进最后的求交过程占总时间的55分之1 返回返回返回返回返回 Laboratory of Dependable Systems and Network - Group of Network Security

Evaluation The result shows that the performance of wildcard-aware table with Trie has been increased to nearly 24 times (table size: 5k) Laboratory of Dependable Systems and Network - Group of Network Security

Evaluation (Cont.) 返回返回返回返回返回 Obviously, our update algorithm’s time complexity is also O(1) and spent far less time than the classical algorithm Laboratory of Dependable Systems and Network - Group of Network Security

Future Works Deploy our approach on to GPU Deploy our approach on to netFPGA Control panel 1、这里要详细一点，要说明那个取交集的问题，以及我们拟采用哪些方案来解决，以及数据的特点是什么样子 2、用GPU来做，就是数据并行，要说明我们的方案适合数据并行的特点是什么 3、用FPGA来做，就是任务并行，主要是进行多个流表查找的流水线部署。 Laboratory of Dependable Systems and Network - Group of Network Security

Conclusion A structure of wildcard-aware table based on Trie Matching algorithm Update algorithm Laboratory of Dependable Systems and Network - Group of Network Security

Thanks Q & A Reporter: Tong Shen Email: tshen@hnu.edu.cn Site: shentong.xoom.it Thanks Q & A Laboratory of Dependable Systems and Network - Group of Network Security