Basic Search / Detailed Display

Back to Search Result
Author: 林彥丞
Yen-Cheng Lin
Thesis Title: 軟體定義網路中因外卡規則所產生溢出之縮減：基於重要性之相依性規則安裝
Overflow Reduction Caused by Wildcard Rules in SDN: Importance-Based Installation of Dependency Rules
Advisor: 馮輝文
Huei-­Wen Ferng
Committee: 林嘉慶
Jia-Chin Lin
沈上翔
Shan-Hsiang Shen
謝宏昀
Hung-Yun Hsieh
Degree: 碩士
Master
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2021
Graduation Academic Year: 109
Language: 中文
Pages: 40
Keywords (in Chinese): 軟體定義網路 、三元內容定址記憶體 、相依性問題 、轉送表 、外卡規則
Keywords (in other languages): SDN, TCAM, Rule Dependency Problem, Flow Table, Wildcard Rule
Reference times: Clicks: 441  Downloads: 2 
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  •  Last one

    • 軟體定義網路 (Software­Defined Networking, SDN) 是目前受到各界關注的網路架構，它透過分離資料層 (Data Plane) 以及控制層 (Control Plane)，使得管理者可以透過控制器 (Controller) 來對整個網路架構進行有彈性且集中化的管理， 增加網路的使用效率，其目前應用於許多的大型網路架構。然而軟體定義網路專用交換器使用的三元內容定址記憶體 (Ternary Content Addressable Memory, TCAM) 造價昂貴，易產生容量不足的問題，導致轉送表 (Flow Table) 的規則溢出(Overflow)。目前已經有研究顯示：規則溢出會造成網路傳輸效率降低。這般問題在外卡規則 (Wildcard Rule) 的加入後變得更加嚴重，因為外卡規則之間存在著相依性問題 (Dependency Problem)，導致安裝一個外卡規則時會需要連帶安裝大量的相依性規則來避免發生錯誤路由。因此，本論文提出基於重要性之相依性規則安裝方法，其透過追蹤相依性規則在交換器的資訊來評估規則的重要性，做為是否安裝該規則的依據，經控制器處理後，再判斷是否為值得安裝的規則，藉此減少非重要規則的安裝以降低轉送表發生規則溢出的數量。透過模擬檢驗，本論文所提出的方法能較文獻上相關的方法在轉送表規則溢出數量以及規則總安裝次數有更佳的表現，並且在不產生溢出的情境下，能承受更高的資料流速率。

    The software­defined networking (SDN) is a popular network structure which seper­ ates the control plane from the data plane and introduces a central controller to control the whole network flexibly. With proper management, SDN helps improve the network performance and has been employed in many large­scale networks. However, the ternary content addressable memory (TCAM) used by the modern SDN switches is size­limited, expensive, and power hungry. Moreover, the small size of TCAM increases the risk of flow table overflow, causing network perfor­ mance degradation as illustrated by some research papers. In the meanwhile, wildcard rules in SDN makes such things even worse because dependency prob­ lems between wildcard rules trigger numerous dependency rules to be install to avoid false forwarding. Targeting at this, the importance­based installation for dependency rules will be proposed in this thesis. By tracking the status of depen­ dency rules in switches, the controller can determine whether some dependency rules are worthy to be installed or not. Avoiding installing less importance rules can reduce the amount of overflows in the network. Via simulations, we success­ fully show that our proposed mechanism can decrease the amount of overflows and the total times of rule installation greatly, enhancing the endurance of the flow rate to reach the overflow.

    中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 英文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 目錄 iv 表目錄 vii 圖目錄 viii 第一章、緒論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 軟體定義網路介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 技術簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 控制器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 轉送表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.4 轉送表規則 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.5 轉送表溢出 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.6 外卡規則 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 論文章節安排 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 第 二 章 、 相 關 文 獻 回 顧 文 獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 轉送表溢出相關文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 外卡規則相關文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 相依性問題硬超時機制 . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 相依性問題空閒超時機制 . . . . . . . . . . . . . . . . . . . 9 2.3 混和式基於 Q 學習超時機制 10 2.3.1 相依性問題混和式機制 10 2.3.2 基於 Q 學習適應邏輯 11 第三章、基於重要性之相依性規則安裝 13 3.1 問題描述 13 3.2 基於重要性之相依性規則安裝設計 14 3.2.1 取得規則相依性關係 (演算法 1) 14 3.2.2 控制器規則安裝 (演算法 2) 19 3.2.3 評估規則重要性 (演算法 3) 21 3.2.4 轉送表溢出時的相依性問題 (演算法 4) 23 第四章、數值結果與討論 27 4.1 模擬環境參數設定 27 4.2 模擬情境–不同超時種類設定機制 28 4.2.1 轉送表溢出 28 4.2.2 規則總安裝數量 30 4.2.3 轉送表觸及率 30 4.2.4 壓力測式 31 4.3 模擬情境–不同超時時間適應邏輯 32 4.3.1 轉送表溢出 32 4.3.2 規則總安裝次數 33 4.3.3 轉送表觸及率 33 4.3.4 壓力測式 34 4.4 控制器處理時間 34 第五章、結論 36 參考文獻 37

    [1] L. Yang, T. Anderson, R. Dantu, and R. Gopal, “Forwarding and control ele­ ment separation (ForCES) framework,” IETF RFC 3746, May 2004.
    [2] S. H. Ahmed, S. H. Bouk, D. Kim, D. B. Rawat, and H. Song, “Named data networking for software defined vehicular networks,” IEEE Commun. Mag., vol. 55, no. 8, pp. 60–66, Aug. 2017.
    [3] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata,
    J. Wanderer, J. Zhou, M. Zhu, J. Zolla, U. Hölzle, S. Stuart, and A. Vah­ dat, “B4: Experience with a globally­deployed software defined WAN,” ACM SIGCOMM Comput. Commun. Rev., vol. 43, no. 4, pp. 3–14, Aug. 2013.
    [4] C. Chen, C. Liu, P. Liu, B. T. Loo, and L. Ding, “A scalable multi­datacenter layer­2 network architecture,” in Proc. ACM Symp. SDN Res. (SOSR), Jun. 2015, pp. 1–12.
    [5] “Ryu SDN framework,” https://github.com/faucetsdn/ryu, accessed: 2020­ 11­30.
    [6] “OpenDaylight project a series of LF projects,” https://www.opendaylight. org/, accessed: 2020­11­30.
    [7] “Open network operating system,” https://opennetworking.org/onos/, ac­ cessed: 2020­11­30.
    [8] C. Hsieh, N. Weng, and W. Wei, “Scalable many­field packet classification for traffic steering in SDN switches,” IEEE Trans. Netw. Service Manag., vol. 16, no. 1, pp. 348–361, Mar. 2019.
    [9] Z. Guo, R. Liu, Y. Xu, A. Gushchin, A. Walid, and H. J. Chao, “STAR: Pre­ venting flow­table overflow in software­defined networks,” Comput. Netw., vol. 125, no. 2, pp. 15–25, Oct. 2017.
    [10] S. Shirali­Shahreza and Y. Ganjali, “ReWiFlow: Restricted wildcard Open­ Flow rules,” ACM SIGCOMM Comput. Commun. Rev., vol. 45, no. 5, pp. 29–35, Sep. 2015.
    [11] N. Kang, Z. Liu, J. Rexford, and D. Walker, “Optimizing the“one big switch＂ abstraction in software­defined networks,” in Proc. ACM Int. Conf. Emerg. Netw. Exp. Technol. (CoNEXT), Dec. 2013, pp. 13–24.
    [12] A. Mimidis­Kentis, A. Pilimon, J. Soler, M. Berger, and S. Ruepp, “A novel algorithm for flow­rule placement in SDN switches,” in Proc. IEEE Conf. Netw. Softwarization Workshops (NetSoft), Jun. 2018, pp. 1–9.
    [13] N. Katta, O. Alipourfard, J. Rexford, and D. Walker, “CacheFlow: Dependency­aware rule­caching for software­defined networks,” in Proc. ACM Symp. SDN Res. (SOSR), Mar. 2016, pp. 1–12.
    [14] D. Wang, Q. Li, L. Wang, R. O. Sinnott, and Y. Jiang, “A hybrid­timeout mechanism to handle rule dependencies in software defined networks,” in Proc. IEEE Conf. Comput. Commun. Workshops (INFOCOM WKSHPS), May 2017, pp. 241–246.
    [15] H. Zhu, H. Fan, X. Luo, and Y. Jin, “Intelligent timeout master: Dynamic timeout for SDN­based data centers,” in Proc. IFIP/IEEE Int. Symp. Integr. Netw. Manag. (IM), May 2015, pp. 734–737.
    [16] B. Sooden and M. R. Abbasi, “A dynamic hybrid timeout method to secure flow tables against DDoS attacks in SDN,” in Proc. Int. Conf. Secure Cyber Comput. Commun. (ICSCCC), Dec. 2018, pp. 29–34.
    [17] X. Li and Y. Huang, “A flow table with two­stage timeout mechanism for SDN switches,” in Proc. IEEE Int. Conf. High Perform. Comput. Commun.; IEEE Int. Conf. Smart City; IEEE Int. Conf. Data Sci. Syst. (HPCC/SmartCity/DSS), Aug. 2019, pp. 1804–1809.
    [18] A. Panda, S. S. Samal, A. K. Turuk, A. Panda, and V. C. Venkatesh, “Dynamic hard timeout based flow table management in OpenFlow enabled SDN,” in Proc. IEEE Int. Conf. Vis. Towards Emerg. Trends Commun. Netw. (ViTE­ CoN), Mar. 2019, pp. 1–6.
    [19] X. Xu, L. Hu, H. Lin, and Z. Fan, “An adaptive flow table adjustment algorithm for SDN,” in Proc. IEEE Int. Conf. High Perform. Comput. Commun.; IEEE Int. Conf. Smart City; IEEE Int. Conf. Data Sci. Syst. (HPCC/SmartCity/DSS), Aug. 2019, pp. 1779–1784.
    [20] B. Isyaku, M. B. Kamat, K. b. Abu Bakar, M. S. Mohd Zahid, and F. A. Ghaleb, “IHTA: Dynamic idle­hard timeout allocation algorithm based Open­ Flow switch,” in Proc. IEEE Symp. Comput. Appl. Ind. Electron. (ISCAIE), Apr. 2020, pp. 170–175.
    [21] J. Sheu and Y. Chuo, “Wildcard rules caching and cache replacement algo­ rithms in software­defined networking,” IEEE Trans. Netw. Service Manag., vol. 13, no. 1, pp. 19–29, Feb. 2016.
    [22] Y. Kanizo, D. Hay, and I. Keslassy, “Palette: Distributing tables in software­ defined networks,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), Apr. 2013, pp. 545–549.
    [23] A. Marsico, R. Doriguzzi­Corin, and D. Siracusa, “An effective swapping mechanism to overcome the memory limitation of SDN devices,” in Proc. IFIP/IEEE Int. Symp. Integr. Netw. Manag. (IM), May 2017, pp. 247–254.
    [24] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rex­ ford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 69–74, Mar. 2008.
    [25] B. Yan, Y. Xu, H. Xing, K. Xi, and H. J. Chao, “CAB: A reactive wildcard rule caching system for software­defined networks,” in Proc. ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking (HotSDN), Aug. 2014, pp. 163–168.
    [26] Q. Li, N. Huang, D. Wang, X. Li, Y. Jiang, and Z. Song, “HQTimer: A hybrid Q ­learning­based timeout mechanism in software­defined networks,” IEEE Trans. Netw. Service Manag., vol. 16, no. 1, pp. 153–166, Mar. 2019.
    [27] D. Y. Huang, K. Yocum, and A. C. Snoeren, “High­fidelity switch models for software­defined network emulation,” in Proc. ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking (HotSDN), Aug. 2013, pp. 43–48.
    [28] M. Kharbutli and R. Sheikh, “LACS: A locality­aware cost­sensitive cache replacement algorithm,” IEEE Trans. Comput., vol. 63, no. 8, pp. 1975–1987, Mar. 2014.
    [29] A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and
    S. Banerjee, “DevoFlow: Scaling flow management for high­performance networks,” ACM SIGCOMM Comput. Commun. Rev., vol. 41, no. 4, pp. 254– 265, Aug. 2011.
    [30] “MAWI working group traffic archive,” http://mawi.wide.ad.jp/mawi/, ac­ cessed: 2020­11­30.
    [31] ITU­T Rec. G.1010, “End­user multimedia QoS categories,” Nov. 2001.

    QR CODE