博碩士論文 102522030 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:18 、訪客IP:34.239.150.57
姓名 王竣鋒(Chun-Feng Wang)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱
(Heterogeneous Flow Table Distribution in Software-defined Networks)
相關論文
★ 基於OP-TEE的可信應用程式軟體生態系統★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 在無線感測網路中連續型物體的偵測與追蹤協定之設計★ 在車用無線網路中利用虛擬地標的封包繞徑協定
★ 在無線感測網路下處理不同重要性區域的覆蓋問題★ 在車用網路環境下分散式計程車呼叫協定
★ 車用無線網路車輛密度偵測方法★ 在車用無線網路中利用適應道路分割法提供區域性階層式定位服務
★ 在無線感測網路中以延長網路生命週期為目的之避洞繞徑協定★ 利用車用無線網路尋找空停車位之協定
★ 在車載無線網路中以區域性為基礎的資源分享協定★ 設計於城市環境之分散式車載隨意行動網路位置服務
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 近幾年來,軟體定義網路(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
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明