Heterogeneous Flow Table Distribution in Software-defined Networks

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：56

、訪客IP：18.223.125.236

姓名

王竣鋒(Chun-Feng Wang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Heterogeneous Flow Table Distribution in Software-defined Networks)

相關論文

★ 基於OP-TEE的可信應用程式軟體生態系統	★ SeFence: 基於安全感測的可信任周邊存取控制
★ 高解析度二維地理影像的三維建模：旋轉變換投影與傳統方法的比較研究	★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略	★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案	★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 衛星地面整合網路之隨機接入前導訊號設計與偵測	★ SatPolicy: 基於Trustzone的衛星政策執行系統
★ TruzMalloc: 基於TrustZone 的隱私資料保護系統	★ 衛星地面網路中基於物理層安全的CSI保護方法
★ 低軌道衛星地面整合網路之安全非正交多重存取傳輸	★ 低軌道衛星地面網路中的DRX機制設計
★ 衛星地面整合網路之基於集合系統的前導訊號設計	★ 基於省電的低軌衛星網路路由演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近幾年來，軟體定義網路(SDN)已經變成了一個重要而且受歡迎的技術，這個技術提供了真實網路中開發新協議與政策的更好的彈性。而在軟體定義網路中的控制器轉換網路政策成網路規則，這些規則大多都儲存於交換器中的封包路徑表格中，而封包路徑表格通常都是用三態內容尋址儲存器(TCAM)來實作。而三態內容尋址儲存器有著一些限制，這種儲存器價格較為昂貴、耗電量高、以及高廢熱的產生使得在交換器中的三態內容尋址儲存器並不會太大，因此，若交換器需要儲存上百甚至上千條的規則的話，可能會不夠用。而其中一個解決的方案是若交換器有這樣規則的需求時，才向控制器尋問並快取這些規則，但這樣會使得封包延遲與佔用龐大的緩衝區。在此篇論文中，我們提出了一個規則分散與放置的演算法來提高效能，這個演算法會分散規則到各個交換器上，我們的演算法不僅適合用於容量小三態內容尋址儲存器的交換器上，更可保證語意上的正確性(即網路全域的行為不會受到改變)，我們在現有的系統上實作了我們的演算法並且展示一些結果來說明我們的演算法可以增進整個網路效能。

摘要(英)

Recently, Software-defined Network (SDN) has become an important and popular technology which provides for the flexibility of developing new protocols and the policies of real networks. The controller in SDN translates network policies into rules which are installed in the flow tables (Flow tables are usually stored in ternary content addressable memory (TCAM)) of switches in the networks. Hence, TCAM usually has some critical disadvantages (e.g., high costs, power consumption and high heat generation). Flow tables cannot scale beyond a few hundred entries. Therefore, switches may need to cache rules reactively (i.e., installing rules on demand). However, when cache misses happen, switches will send the packet-in message to the controller and reactively cache the rules, which causes packet delay and large buffers. In this thesis, we propose a rule partition and allocation algorithm that distributes rules across network switches to improve the performance. Our algorithm not only is applicable to small TCAM switch scenario, but also guarantees semantically-invariant (i.e., the global action of the network is unchanged). We implement our algorithm into the real world SDN scenario and the experiment result shows that our algorithm have obviously reduced TCAM usage.

關鍵字(中)

★ 軟體定義網路
★ 三態內容尋址儲存器
★ OpenFlow
★ 規模可伸縮性

關鍵字(英)

★ Software-defined Networks
★ TCAM
★ OpenFlow
★ Scalability

論文目次

中文摘要 i
Abstract ii
Contents iii
List of Figures vi
List of Tables ix
1 INTRODUCTION 1
2 RELATED WORK 6
2.1 Table compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Rule partition and allocation . . . . . . . . . . . . . . . . . . . . . . . . 8
3 THE PROPOSED ALGORITHM 10
3.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Heterogeneous Flow Table Distribution . . . . . . . . . . . . . . . . . . 11
3.2.1 Rule Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Rule Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 SIMULATION 20
4.1 Rule partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1.1 Rule replications . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Rule allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Impact of shortest flow path length . . . . . . . . . . . . . . . . 22
4.2.2 Impact of the available amount of TCAM in a single switch . . . 23
4.2.3 Impact of the number of the flow . . . . . . . . . . . . . . . . . 23
4.2.4 Impact of the number of switch . . . . . . . . . . . . . . . . . . 23
5 IMPLEMENTATION 30
6 IMPLEMENTATION RESULT 34
6.1 Implementation in bus topology . . . . . . . . . . . . . . . . . . . . . . 34
6.2 Implementation in star topology . . . . . . . . . . . . . . . . . . . . . . 34
6.3 Implementation in simple fat-tree topology . . . . . . . . . . . . . . . . 35
7 CONCLUSION 40
A MAIN FUNCTION 41
A.1 rule_app.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
B RULE INITIATION 51
B.1 rule_generate.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
C PATH 61
C.1 Path.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
C.2 PathHasGenerate.py . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
D Enhance CBD 64
D.1 CBD.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
E COLORING 89
E.1 TheLast.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
E.2 mSwitch.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
E.3 Clique.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
E.4 V ertex.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
E.5 WelshPowell.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
F RULE NORMALIZATION 100
F.1 RuleNormalize.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

參考文獻

[1] Software-defined networking from wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/Software-defined_networking.
[2] Software-defined networking (sdn) definition. https://www.opennetworking.org/sdn-resources/sdn-definition.
[3] Openflow. https://www.opennetworking.org/sdn-resources/openflow.
[4] V. C. Ravikumar and R.N. Mahapatra. Tcam architecture for ip lookup using prefix properties. IEEE Micro, 24(2):60–69, 2004.
[5] Y. Kanizo, D. Hay, and I Keslassy. Palette: Distributing tables in software-defined networks. In The IEEE INFOCOM, 2013.
[6] Chad R. Meiners, Alex X. Liu, and Eric Torng. Bit weaving: A non-prefix approach to compressing packet classifiers in tcams. IEEE/ACM Transactions on Networking, 20(2):488–500, 2012.
[7] Minlan Yu, Jennifer Rexford, Michael J. Freedman, and Jia Wang. Scalable flowbased networking with difane. In the ACM SIGCOMM, 2010.
[8] OpenFlow cisco connect. http://www.cisco.com/web/CZ/ciscoconnect/2014/assets/tech_sdn2_sp_api_openflow_
ungerman.pdf.
[9] Amin Tootoonchian, Sergey Gorbunov, Yashar Ganjali, Martin Casado, and Rob Sherwood. On controller performance in software-defined networks. In Presented as part of the 2nd USENIX Workshop on Hot Topics in Management of Internet, Cloud, and Enterprise Networks and Services, Berkeley, CA, 2012. USENIX.
[10] David A. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, and Jia Wang. Compressing rectilinear pictures and minimizing access control lists. In the ACM/SIAM SODA, 2007.
[11] Qunfeng Dong, Suman Banerjee, Jia Wang, Dheeraj Agrawal, and Ashutosh Shukla. Packet classifiers in ternary cams can be smaller. In SIGMETRICS, 2006.
[12] AX. Liu and M.G. Gouda. Complete redundancy removal for packet classifiers in tcams. IEEE Transactions on Parallel and Distributed Systems, 21(4):424–437, 2010.
[13] AX. Liu, C.R. Meiners, and E. Torng. Tcam razor: A systematic approach towards minimizing packet classifiers in tcams. IEEE/ACM Transactions on Networking, 18(2):490–500, 2010.
[14] Subhash Suri, Tuomas Sandholm, and Priyank Warkhede. Compressing twodimensional routing tables. Algorithmica, 35(4):287–300, 2003.
[15] R.P. Draves, C. King, S. Venkatachary, and B.D. Zill. Constructing optimal ip routing tables. In The IEEE INFOCOM, 1999.
[16] Nanxi Kang, Zhenming Liu, Jennifer Rexford, and David Walker. Optimizing the ”one big switch” abstraction in software-defined networks. In the Ninth ACM CoNEXT, 2013.
[17] Masoud Moshref, Minlan Yu, Abhishek Sharma, and Ramesh Govindan. vcrib: Virtualized rule management in the cloud. In HotCloud, 2012.
[18] Bo Yan, Yang Xu, Hongya Xing, Kang Xi, and H. Jonathan Chao. Cab: A reactive wildcard rule caching system for software-defined networks. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, HotSDN ’14, pages 163–168, New York, NY, USA, 2014. ACM.
[19] D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1): 85–86, 1967.
[20] Ryu. http://osrg.github.io/ryu/.
[21] Nox, pox. http://www.noxrepo.org/.
[22] Floodlight. http://www.projectfloodlight.org/floodlight/.
[23] Open vswitch. http://openvswitch.org/.
[24] AX. Liu, C.R. Meiners, and Yun Zhou. All-match based complete redundancy removal for packet classifiers in tcams. In IEEE INFOCOM, pages –, 2008.
[25] Alex X. Liu and Mohamed G. Gouda. Complete redundancy detection in firewalls. In DBSec, 2005.
[26] F. d’Amore, V.H. Nguyen, T. Roos, and P. Widmayer. On optimal cuts of hyperrectangles. Springer Computing, 55(3):191–206, 1995.
[27] RFC2722. https://tools.ietf.org/html/rfc2722.
[28] Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A scalable, commodity data center network architecture. In Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication, SIGCOMM ’08, pages 63–74, New York, NY, USA, 2008. ACM.

指導教授

張貴雲(Guey-Yun Chang)

審核日期

2015-7-7

推文