適用於開源流交換器封包處理之效率型布穀過濾器設計

Efficient Cuckoo Filter-based Packet Processing for OpenFlow-Compliant Switches

汪敬哲(Ching-Che Wang)

指導教授 ： 吳安宇

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

https://doi.org/10.6342/NTU201802093

摘要

軟體定義網路(Software-Defined Networking, SDN)是一種新型態的網路架構，將網路設備中之控制層與資料傳輸層分割並透過單一控制層操作所有資料傳輸層。開源流，一種主要SDN之標準，負責制定控制單位與所有網路設備之通訊協定。隨著開源流之快速演進與發展，現今符合開源流之交換器須滿足支援多個欄位之比對以因應快速網路之創新與發展。欄位之增加在儲存需求上造成龐大之負擔；而為了支援多個欄位之三態路由比對，更破壞了整體網絡封包傳輸之速率。
為了解決欄位增加所造成之儲存負擔，我們提出一個機率基底過濾器作為儲存單位之標準。機率過濾器擁有空間效率之特性因此視為可被依賴用於SDN之設備。機率過濾器之主要疑慮為假陽性，假陽性(False Positive)會進一步導致錯誤之封包傳輸。因此，我們提出一個新型之機率過濾器，multi-pair segmented cuckoo filter (MP-SCF)。相較相關研究成果，MP-SCF可以將假陽率進一步降低兩個層級；透過將過濾器分割至多個記憶體，MP-SCF可以維持單一週期傳輸每個封包。MP-SCF支援三種典型之網路功能、支援動態規則更新以及自動更新，並在開源流之限制下，在過濾器重組前皆維持零假陽性之特性。
針對多個欄位之三態路由比對，傳統上主要透過針對單一欄位進行比對，爾後將各個欄位之比對結果鏈結起來進行最終確認。我們透過先前提出之MP-SCF建構一封包處理引擎，dynamic multi-field stitching (DMFS)，DMFS為一過濾器基底之封包處理引擎，由兩層之MP-SCF所組成。不同於以往單一欄位之比對方式，第一層之MP-SCF透過針對相鄰欄位進行同時比對，有效解決聯結問題並大幅降低比對後之可能結果組合。而受惠於MP-SCF之零假陽性特性，DMFS僅需於第二層放置一具有全局視野之MP-SCF進行最後確認，不需儲存大量之完整規則。因此，相較於相關封包處理引擎，DMFS被視為更高速且更空間效率，因此更適合用於新興之高效能開源流協定之封包處理設計。

關鍵字

軟體定義網路 ； 開源流 ； 布隆過濾器 ； 布穀過濾器 ； 封包處理

並列摘要

Software-Defined Networking (SDN) is an emerging network infrastructure that decouples the network device’s control plane and data plane and gathers all control units in one. OpenFlow, a prominent standard of SDN, defines the communication protocol between the controller and the network devices. With the evolution of the OpenFlow protocol, nowadays an OpenFlow switch is required to support multi-field matching for fast network innovation. The increasing field number poses a great burden on storage demand and ruins the processing speed because of the multi-field ternary matching.
To deal with the storage burden from the increasing filed number, we aim to propose a probability-based filter to be the standard storage unit. The probabilistic filter has the property of space efficiency thereby seen as a reliable solution for the SDN devices. The main concern of the probabilistic filter is the false positive since it may result in false routing. As a result, we propose a novel filter called multi-pair segmented cuckoo filter (MP-SCF). The MP-SCF achieves 2-order reduction of the false positive rate compared to the prior arts. Meanwhile, by segmenting a filter into several banked memory, the MP-SCF maintains the single-cycle access time per packet query. The MP-SCF supports 3 typical network operations, dynamic rule-updatable and auto-updating. Under the OpenFlow constraint, the MP-SCF achieves no false positive occurred before reconstructing the filter.
For the multi-field ternary matching, traditionally the multi-field matching is decomposed of the single-field search and then concatenating the searched results. We construct a packet-processing engine by proposed MP-SCF. Dynamic multi-field stitching (DMFS) structure is an unprecedented filter-based processing engine that is composed of the 2-layer MP-SCFs. Unlike the single-field search, the neighboring-field search in the 1st layer efficiently solves the concatenating issue and reduces the possible combinations tremendously. Due to the no false positive from the MP-SCF, the DMFS only needs a global-view MP-SCF in the 2nd layer for the final verification rather than a complete rule table. Compared to the prior packet-processing engines, the DMFS is proven to be high speed and space-efficient, thereby being suitable for emerging high-performance packet processing in OpenFlow protocol.

並列關鍵字

Software-Defined Networking (SDN) ； OpenFlow ； Bloom filter (BF) ； Cuckoo filter (CF) ； Packet processing

參考文獻

[1] F. Hu, Q. Hao, and K. Bao, “A Survey on Software-Defined Network and OpenFlow: From Concept to Implementation,” IEEE Communication Survey & Tutorials, vol.16, no. 4, pp. 2181–2206, 2014.

[2] N. Feamster, J. Rexford, and E. Zegura, “The Road to SDN: An Intellectual History of Programmable Networks,” ACM SIGCOMM Computer Communication Review, vol. 44, Issue. 2, pp. 87-98, 2014.

[3] ONF: OpenFlow Switch Specification Version 1.5.0, available on https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.5.0.noipr.pdf

[4] P. Goransson, C. Black, and T. Culver, Software Defined Networks A Comprehensive Approach, 2nd Edition, 2014.

[5] B. Pfaff, J. Pettit, T. Koponen, E. J. Jackson, A. Zhou, J. Rajahalme, J. Gross, A. Wang, J. Stringer, P. Shelar, K. Amidon, and M. Casado, “The Design and Implementation of Open vSwitch” in Proc. 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pp. 117-130, May. 2015.