適用於低功耗開源流封包處理之可動態更新布隆過濾器設計

Dynamically Updatable Ternary Segmented Aging Bloom Filter for OpenFlow-Compliant Low-Power Packet Processing

高聖鈞(Sheng-Chun Kao)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701157

摘要

OpenFlow為軟體定義網路中最主流的協定，大型路由表以及頻繁更新為OpenFlow交換器的主要特色。為了達到快速平行化的路由查找，大多採用TCAM作為儲存以及搜尋單元，然而其能耗問題造成OpenFlow交換器的效能瓶頸。傳統路由器中已有許多相關研究採用Bloom Filter作為過濾搜尋的機制以達到節能效果。但對於OpenFlow的網路封包特性而言，過去的Bloom Filter由於不能動態更新、面對三態路由消耗大量面積等問題，使其無法直接適用在OpenFlow交換器。
因此，我們提出適用於未來OpenFlow交換器的Ternary Segmented Aging Bloom Filter (TSA-BF)。其由兩部分組成，首先為Segmented Aging Bloom Filter (SA-BF)，其使用內容自主老化以及分時切分儲存空間的演算法，達到內容自動更新的功能，節省了在更新上需要的大量控制以及溝通成本，且可以隨著新進的路由，即時汰換老舊的路由。另一部分為Ternary Prefix-tagging Encoder (TPE)，其將三態路由編碼成不衝突的二元路由，使得Bloom Filter可以有效處理三態路由，而避免過去三態路由平行展開所造成的儲存空間壅擠現象。
我們的模擬結果顯示，SA-BF比起最佳的相關研究結果，可以進一步節省37%的儲存空間。而在三態路由的環境下，TSA-BF比起最佳的相關研究結果，可以再節省93%的儲存空間。在軟體定義網路中的下世代路由器需要快速動態更新以及低能耗要求且支援多變的三態路由，我們提出的適用於OpenFlow的路由過濾演算法TSA-BF，是目前可以最有效的利用有限空間而達到良好過濾效果的演算法。

關鍵字

軟體定義網路 ； Bloom Filter ； TCAM ； 封包分類演算法

並列摘要

OpenFlow, the main protocol for Software-Defined Networking (SDN), requires large-sized rule tables and frequent updating. For fast packet processing, rule tables are often implemented with Ternary Content-Addressable Memory (TCAM) in OpenFlow. To deal with TCAM power problems, many network applications employ Bloom Filters (BFs) to reduce redundant operations of table-lookup and for low power consumption. However, applying traditional BFs to an OpenFlow switch leads to problems such as unsupported dynamic update, large space overhead, and rule-set expansion of ternary data. In this paper, we propose a dynamically updatable Ternary Segmented Aging Bloom Filter (TSA-BF). The TSA-BF consists of two parts: a Segmented Aging BF algorithm (SA-BF) and a Ternary Prefix-tagging Encoder (TPE). First, in the SA-BF, we develop an automatic update scheme using the mechanisms of content-aging and buffer-segmenting. The SA-BF ages and deletes its contents automatically, thus eliminating the costly communication overhead and enabling dynamic updating. It also achieves space efficiency by the developed partial-deletion mechanism. Second, in the TPE, we encode ternary prefix-rules into uniquely decodable binary codewords. The TPE prevents the rule-set expansion of ternary-data in the OpenFlow environment. Simulation results show that the SA-BF alone can save 37% of space overhead, compared with state-of-the-art techniques. In an environment with ternary prefix-rules, the TSA-BF can save another 93% of space overhead, compared with the best-performance scheme. Hence, the TSA-BF is highly suited to the requirements of emerging high-performance TCAM-based packet processing in OpenFlow, which considers dynamic update and power efficiency.

並列關鍵字

Bloom filter ； packet classification ； dynamically updatable ； OpenFlow ； Software-Defined Networking(SDN) ； Ternary Content Addressable Memory(TCAM)

參考文獻

[1] A Survey on Software-Defined Network and OpenFlow: From Concept to Implementation

[2] Software-Defined Networking: A Comprehensive Survey

[3] ITRS, International Technology Roadmap for Semiconductors, http://public.itrs.net.

[4] J. A. Davis et al., “Interconnect Limits on Gigascale Integration (GSI) in the 21st Century,” Proc. IEEE, vol. 89, pp. 305-324, Mar. 2001.

[5] R. Ho, K. W. Mai, and M. A. Horowitz, “The Future of Wires,” Proc. IEEE, vol. 89, pp. 490-504, Apr. 2001.