學術產出-Theses
Article View/Open
Publication Export
-
題名 基於軟體定義網路下多物流的更新機制
SDN Update for Multi-Commodity Flow作者 藍堯祺
Lan, Yao-Chi貢獻者 郭桐惟
Kuo, Tung-Wei
藍堯祺
Lan, Yao-Chi關鍵詞 軟體定義網路
網路流更新
Software-Defined network
Network flow update日期 2018 上傳時間 1-Oct-2018 12:11:40 (UTC+8) 摘要 為了滿足使用者的即時要求，網路設定需要頻繁地被更新。如今的網管人員可以透過軟體定義網路技術輕鬆地更新網路設定。然而，網路更新期間可能會造成許多不良副作用，如迴圈或是網路壅塞。給定當下的網路設定，本論文考慮使用者的優先權，在避免更新的副作用的情況下，計算出最大化系統效率的網路流設定，與對應的更新順序。我們的方法基於線性規劃。實驗顯示我們的方法在兩個常見的資料中心網路拓樸，Fat-Tree 與 BCube，有良好的表現。
To satisfy users’ real-time demands, network configurations have to be updated frequently. Nowadays, network operators can easily update network configurations through Software-Defined Network technology. However, during the period of network update, several bad side effects may occur, including loops and congestions. Given the current network configuration, this thesis jointly considers user priority and computes a new network configuration that maximizes the efficiency of the system under the constraint that no bad side effects can happen during the period of update. We also give the corresponding update sequence. Our solution is based on linear programming. Simulation results have shown that our solution has good performance in Fat-Tree and BCube, which are common data center topologies.參考文獻 [1] N. McKeown, “Software-defined networking,” INFOCOM keynote talk, vol. 17, no. 2, pp. 30–32, 2009. [2] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69–74, 2008. [3] S. Agarwal, M. Kodialam, and T. Lakshman, “Traffic engineering in software defined networks,” in INFOCOM, 2013 Proceedings IEEE, pp. 2211–2219, IEEE, 2013. [4] F. Giroire, J. Moulierac, and T. K. Phan, “Optimizing rule placement in softwaredefined networks for energy-aware routing,” in Global Communications Conference (GLOBECOM), 2014 IEEE, pp. 2523–2529, IEEE, 2014. [5] X. Jin, H. H. Liu, R. Gandhi, S. Kandula, R. Mahajan, M. Zhang, J. Rexford, and R. Wattenhofer, “Dynamic scheduling of network updates,” in ACM SIGCOMM Computer Communication Review, vol. 44, pp. 539–550, ACM, 2014. [6] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, et al., “B4: Experience with a globally-deployed software defined wan,” in ACM SIGCOMM Computer Communication Review, vol. 43, pp. 3– 14, ACM, 2013. [7] C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer, “Achieving high utilization with software-driven wan,” in ACM SIGCOMM Computer Communication Review, vol. 43, pp. 15–26, ACM, 2013. [8] E. Mannie, “Generalized multi-protocol label switching (gmpls) architecture,” tech. rep., 2004. [9] R. Mahajan and R. Wattenhofer, “On consistent updates in software defined networks,” in Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, p. 20, ACM, 2013. [10] K.-T. Förster, R. Mahajan, and R. Wattenhofer, “Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes,” in IFIP Networking Conference (IFIP Networking) and Workshops, 2016, pp. 1–9, IEEE, 2016. [11] R. McGeer, “A safe, efficient update protocol for openflow networks,” in Proceedings of the first workshop on Hot topics in software defined networks, pp. 61–66, ACM, 2012. [12] R. McGeer, “A correct, zero-overhead protocol for network updates,” in Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking, pp. 161–162, ACM, 2013. [13] M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker, “Abstractions for network update,” ACM SIGCOMM Computer Communication Review, vol. 42, no. 4, pp. 323–334, 2012. [14] C. Wilson, H. Ballani, T. Karagiannis, and A. Rowtron, “Better never than late: Meeting deadlines in datacenter networks,” ACM SIGCOMM Computer Communication Review, vol. 41, no. 4, pp. 50–61, 2011. [15] J. Liddle, “Amazon found every 100ms of latency cost them 1% in sales,” The GigaSpaces, vol. 27, 2008. [16] J. Zheng, H. Xu, G. Chen, and H. Dai, “Minimizing transient congestion during network update in data centers,” in Proceedings of the 2014 CoNEXT on Student Workshop, pp. 4–6, ACM, 2014 [17] S. Paris, A. Destounis, L. Maggi, G. S. Paschos, and J. Leguay, “Controlling flow reconfigurations in sdn,” in Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, pp. 1–9, IEEE, 2016. [18] S. Luo, H. Yu, L. Luo, and L. Li, “Arrange your network updates as you wish,” in IFIP Networking Conference (IFIP Networking) and Workshops, 2016, pp. 10–18, IEEE, 2016. [19] S. Brandt, K.-T. Förster, and R. Wattenhofer, “On consistent migration of flows in sdns,” 2016. [20] W. Wang, W. He, J. Su, and Y. Chen, “Cupid: Congestion-free consistent data plane update in software defined networks,” in Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, pp. 1–9, IEEE, 2016. [21] S. Vissicchio, O. Tilmans, L. Vanbever, and J. Rexford, “Central control over distributed routing,” in ACM SIGCOMM Computer Communication Review, vol. 45, pp. 43–56, ACM, 2015. [22] S. Brandt, K.-T. Foerster, and R. Wattenhofer, “Augmenting flows for the consistent migration of multi-commodity single-destination flows in sdns,” Pervasive and Mobile Computing, vol. 36, pp. 134–150, 2017. [23] C. E. Leiserson, “Fat-trees: universal networks for hardware-efficient supercomputing,” IEEE transactions on Computers, vol. 100, no. 10, pp. 892–901, 1985. [24] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “Bcube: a high performance, server-centric network architecture for modular data centers,” ACM SIGCOMM Computer Communication Review, vol. 39, no. 4, pp. 63–74, 2009. [25] S. Brandt, K.-T. Foerster, and R. Wattenhofer, “Augmenting anycast network flows,” in Proceedings of the 17th International Conference on Distributed Computing and Networking, p. 24, ACM, 2016. [26] B. Dezső, A. Jüttner, and P. Kovács, “Lemon–an open source c++ graph template library,” Electronic Notes in Theoretical Computer Science, vol. 264, no. 5, pp. 23– 45, 2011. [27] I. I. CPLEX, “V12. 1: User’s manual for cplex,” International Business Machines Corporation, vol. 46, no. 53, p. 157, 2009. [28] T.-W. Kuo, B.-H. Liou, K. C.-J. Lin, and M.-J. Tsai, “Deploying chains of virtual network functions: On the relation between link and server usage,” IEEE/ACM Transactions on Networking, no. 99, pp. 1–15, 2018. 描述 碩士
國立政治大學
資訊科學系
105753038資料來源 http://thesis.lib.nccu.edu.tw/record/#G0105753038 資料類型 thesis dc.contributor.advisor 郭桐惟 zh_TW dc.contributor.advisor Kuo, Tung-Wei en_US dc.contributor.author (Authors) 藍堯祺 zh_TW dc.contributor.author (Authors) Lan, Yao-Chi en_US dc.creator (作者) 藍堯祺 zh_TW dc.creator (作者) Lan, Yao-Chi en_US dc.date (日期) 2018 en_US dc.date.accessioned 1-Oct-2018 12:11:40 (UTC+8) - dc.date.available 1-Oct-2018 12:11:40 (UTC+8) - dc.date.issued (上傳時間) 1-Oct-2018 12:11:40 (UTC+8) - dc.identifier (Other Identifiers) G0105753038 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/120263 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 105753038 zh_TW dc.description.abstract (摘要) 為了滿足使用者的即時要求，網路設定需要頻繁地被更新。如今的網管人員可以透過軟體定義網路技術輕鬆地更新網路設定。然而，網路更新期間可能會造成許多不良副作用，如迴圈或是網路壅塞。給定當下的網路設定，本論文考慮使用者的優先權，在避免更新的副作用的情況下，計算出最大化系統效率的網路流設定，與對應的更新順序。我們的方法基於線性規劃。實驗顯示我們的方法在兩個常見的資料中心網路拓樸，Fat-Tree 與 BCube，有良好的表現。 zh_TW dc.description.abstract (摘要) To satisfy users’ real-time demands, network configurations have to be updated frequently. Nowadays, network operators can easily update network configurations through Software-Defined Network technology. However, during the period of network update, several bad side effects may occur, including loops and congestions. Given the current network configuration, this thesis jointly considers user priority and computes a new network configuration that maximizes the efficiency of the system under the constraint that no bad side effects can happen during the period of update. We also give the corresponding update sequence. Our solution is based on linear programming. Simulation results have shown that our solution has good performance in Fat-Tree and BCube, which are common data center topologies. en_US dc.description.tableofcontents 第一章 緒論 1 第二章 系統模型 7 第一節 網路模型與問題輸入 7 第二節 問題定義 7 第三章 研究方法 10 第一節 線性規劃模型 10 第二節 避免網路壅塞的更新限制所造成的負面影響 12 第三節 更新效率 13 第四章 實驗結果 15 第一節 實驗設定 15 第二節 實驗結果 17 第五章 相關研究 34 第六章 結論 35 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0105753038 en_US dc.subject (關鍵詞) 軟體定義網路 zh_TW dc.subject (關鍵詞) 網路流更新 zh_TW dc.subject (關鍵詞) Software-Defined network en_US dc.subject (關鍵詞) Network flow update en_US dc.title (題名) 基於軟體定義網路下多物流的更新機制 zh_TW dc.title (題名) SDN Update for Multi-Commodity Flow en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] N. McKeown, “Software-defined networking,” INFOCOM keynote talk, vol. 17, no. 2, pp. 30–32, 2009. [2] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69–74, 2008. [3] S. Agarwal, M. Kodialam, and T. Lakshman, “Traffic engineering in software defined networks,” in INFOCOM, 2013 Proceedings IEEE, pp. 2211–2219, IEEE, 2013. [4] F. Giroire, J. Moulierac, and T. K. Phan, “Optimizing rule placement in softwaredefined networks for energy-aware routing,” in Global Communications Conference (GLOBECOM), 2014 IEEE, pp. 2523–2529, IEEE, 2014. [5] X. Jin, H. H. Liu, R. Gandhi, S. Kandula, R. Mahajan, M. Zhang, J. Rexford, and R. Wattenhofer, “Dynamic scheduling of network updates,” in ACM SIGCOMM Computer Communication Review, vol. 44, pp. 539–550, ACM, 2014. [6] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, et al., “B4: Experience with a globally-deployed software defined wan,” in ACM SIGCOMM Computer Communication Review, vol. 43, pp. 3– 14, ACM, 2013. [7] C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer, “Achieving high utilization with software-driven wan,” in ACM SIGCOMM Computer Communication Review, vol. 43, pp. 15–26, ACM, 2013. [8] E. Mannie, “Generalized multi-protocol label switching (gmpls) architecture,” tech. rep., 2004. [9] R. Mahajan and R. Wattenhofer, “On consistent updates in software defined networks,” in Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, p. 20, ACM, 2013. [10] K.-T. Förster, R. Mahajan, and R. Wattenhofer, “Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes,” in IFIP Networking Conference (IFIP Networking) and Workshops, 2016, pp. 1–9, IEEE, 2016. [11] R. McGeer, “A safe, efficient update protocol for openflow networks,” in Proceedings of the first workshop on Hot topics in software defined networks, pp. 61–66, ACM, 2012. [12] R. McGeer, “A correct, zero-overhead protocol for network updates,” in Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking, pp. 161–162, ACM, 2013. [13] M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker, “Abstractions for network update,” ACM SIGCOMM Computer Communication Review, vol. 42, no. 4, pp. 323–334, 2012. [14] C. Wilson, H. Ballani, T. Karagiannis, and A. Rowtron, “Better never than late: Meeting deadlines in datacenter networks,” ACM SIGCOMM Computer Communication Review, vol. 41, no. 4, pp. 50–61, 2011. [15] J. Liddle, “Amazon found every 100ms of latency cost them 1% in sales,” The GigaSpaces, vol. 27, 2008. [16] J. Zheng, H. Xu, G. Chen, and H. Dai, “Minimizing transient congestion during network update in data centers,” in Proceedings of the 2014 CoNEXT on Student Workshop, pp. 4–6, ACM, 2014 [17] S. Paris, A. Destounis, L. Maggi, G. S. Paschos, and J. Leguay, “Controlling flow reconfigurations in sdn,” in Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, pp. 1–9, IEEE, 2016. [18] S. Luo, H. Yu, L. Luo, and L. Li, “Arrange your network updates as you wish,” in IFIP Networking Conference (IFIP Networking) and Workshops, 2016, pp. 10–18, IEEE, 2016. [19] S. Brandt, K.-T. Förster, and R. Wattenhofer, “On consistent migration of flows in sdns,” 2016. [20] W. Wang, W. He, J. Su, and Y. Chen, “Cupid: Congestion-free consistent data plane update in software defined networks,” in Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, pp. 1–9, IEEE, 2016. [21] S. Vissicchio, O. Tilmans, L. Vanbever, and J. Rexford, “Central control over distributed routing,” in ACM SIGCOMM Computer Communication Review, vol. 45, pp. 43–56, ACM, 2015. [22] S. Brandt, K.-T. Foerster, and R. Wattenhofer, “Augmenting flows for the consistent migration of multi-commodity single-destination flows in sdns,” Pervasive and Mobile Computing, vol. 36, pp. 134–150, 2017. [23] C. E. Leiserson, “Fat-trees: universal networks for hardware-efficient supercomputing,” IEEE transactions on Computers, vol. 100, no. 10, pp. 892–901, 1985. [24] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “Bcube: a high performance, server-centric network architecture for modular data centers,” ACM SIGCOMM Computer Communication Review, vol. 39, no. 4, pp. 63–74, 2009. [25] S. Brandt, K.-T. Foerster, and R. Wattenhofer, “Augmenting anycast network flows,” in Proceedings of the 17th International Conference on Distributed Computing and Networking, p. 24, ACM, 2016. [26] B. Dezső, A. Jüttner, and P. Kovács, “Lemon–an open source c++ graph template library,” Electronic Notes in Theoretical Computer Science, vol. 264, no. 5, pp. 23– 45, 2011. [27] I. I. CPLEX, “V12. 1: User’s manual for cplex,” International Business Machines Corporation, vol. 46, no. 53, p. 157, 2009. [28] T.-W. Kuo, B.-H. Liou, K. C.-J. Lin, and M.-J. Tsai, “Deploying chains of virtual network functions: On the relation between link and server usage,” IEEE/ACM Transactions on Networking, no. 99, pp. 1–15, 2018. zh_TW dc.identifier.doi (DOI) 10.6814/THE.NCCU.CS.017.2018.B02 en_US
