跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/22 22:59
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉力瑋
研究生(外文):Liu, Lee Wei
論文名稱:基於Multipath TCP在軟體定義網路下之多路徑路由演算法
論文名稱(外文):An Efficient Multipath Routing Algorithm for Multipath TCP in Software-Defined Networks
指導教授:許健平許健平引用關係
指導教授(外文):Sheu, Jang Ping
學位類別:碩士
校院名稱:國立清華大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:35
中文關鍵詞:k條最大化最小之不相交路徑多路徑路由演算法多路徑傳輸控制協定軟體定義網路
外文關鍵詞:k Max-min disjoint pathsmultipath routing algorithmmultipath TCPsoftware-defined networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:417
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:1
隨著軟體定義網路的快速發展,我們比過去更容易操縱網路流量。多路徑繞徑協定一直都是一個重要的研究主題,在本文中,我們著重在設計多路徑演算法結合Multipath TCP(MPTCP)。MPTCP 是 TCP 的延伸,此協定透過多條路徑來傳送,而不是用一條路徑來傳送,此協定明顯提高了點對點傳輸的吞吐量。換言之,一個MPTCP的流量可以分成多個子流量來進行點對點的傳輸。我們將此繞逕問題制定成k條不相交路徑之最大化最小頻寬的路徑。k條不相交路徑之最大化最小頻寬的路徑是要找k條不相交的路徑,且在這k條不相交的路徑中頻寬最小的路徑要被最大化。由於此問題屬於NP-complete的問題,所以我們提出了一個啟發式演算法能在多項式時間內解決此問題。我們將來自同一組點對點傳輸的多個MPTCP子流量分散到不同的路徑上來避免子流量互相競爭網路資源,且縮小了每條路徑的頻寬差距。我們的模擬結果顯示我們提出的演算法之於其他演算法能針對一個MPTCP流量提供較好得吞吐量,較小的路徑頻寬差距以及較短的平均路徑長度。
Due to the rapid growth of Software-Defined Networks, we can manipulate network traffic easier than before. One of the major issues on SDN is the multipath routing protocols. In this paper, we focus multipath routing algorithm on Multipath TCP (MPTCP). MPTCP is an extension of TCP that increases the throughput of TCP communication significantly by utilizing multiple paths transmission rather than single path. In other words, an MPTCP flow generates multiple sub-flows for end-to-end communications. We consider the multipath routing problem as a k Max-Min bandwidth disjoint paths one. The problem is to find k disjoint paths with relative higher throughput and the smallest bottleneck bandwidth of the k paths is the maximum. Since this problem is NP-complete, we propose a heuristic algorithm to solve this problem in polynomial time. The simulation results show that our proposed algorithm perform better than previous works in terms of average throughput and average hop count.
Chapter 1 Introduction 1
Chapter 2 Related Works 5
Chapter 3 k Max-Min Disjoint Paths Algorithm 8
Chapter 3.1 Find a set of Candidate Paths 9
Chapter 3.2 Select k Max-Min Bandwidth Disjoint Paths 16
Chapter 3.3 Time Complexity Analysis 20
Chapter 4 Performance Evaluation 22
Chapter 5 Conclusion 32
References 33

[1] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker, “Ethane: Taking Control of the Enterprise,” Proceedings of ACM SIGCOMM, pp. 1-12, New York, USA, August 2007.
[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, April 2008
[3] “Openflow Switch Specification v1.3.4,” 2014. https://www.opennetworking.org/sdn-resources/onf-specifications
[4] M. Koerner, and O. Kao, "Evaluating SDN based Rack-to-Rack Multi-Path Switching for Data-Center Networks," Procedia Computer Science, Vol. 34, pp. 118-125, 2014
[5] R. van der Pol, M. Bredel, and A. Barczyk, “Experiences with MPTCP in an Intercontinental Multipathed OpenFlow Network,” Proceedings of the 29th Trans European Research and Education Networking Conference, Maastricht, Netherland, June 2013.
[6] A. Ford, C. Raiciu, M. Handley, S. Barre, and J. Iyengar, RFC 6182, “Architectural Guidelines for Multipath TCP Development,” 2011.
[7] A. Ford, C. Raiciu, M. Handley, and O. Bonaventure, RFC 6824, "TCP Extensions for Multipath Operation with Multiple Addresses," 2013.
[8] I. F. Akyildiz, A. Lee, P. Wang, M. Luo, and W. Chou, "A Roadmap for Traffic Engineering in SDN-OpenFlow Networks," Computer Networks, Vol. 71, No. 4, pp. 1-30, October 2014.
[9] C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley, "Improving Datacenter Performance and Robustness with Multipath TCP," Proceedings of ACM SIGCOMM, pp. 266-277, New York, USA, August 2011.
[10] C. Paasch, S. Ferlin, O. Alay, and O. Bonaventure, "Experimental Evaluation of Multipath TCP Schedulers," Proceedings of ACM SIGCOMM Workshop on Capacity Sharing, New York, USA, August 2014.
[11] R.M. Karp, “On the Computational Complexity of Combinatorial Problems,” Networks, Vol. 5, No. 1, pp. 45-68, USA, January 1975.
[12] B. Ulrik, G. Neyer, and D. Wagner, "Edge-Disjoint Paths in Planar Graphs with Short Total Length," 1996.
[13] C-L Li, S. T. McCormic, and D. Simchi-Levi, "The Complexity of Finding Two Disjoint Paths with Min-Max Objective Function," Discrete Applied Mathematics, Vol. 26, No. 1, pp. 105-115, January 1990.
[14] J. M. Kleinberg, “Approximation Algorithms for Disjoint Paths Problems,” Dissertation, Massachusetts Institute of Technology, 1996.
[15] R. Banner, and A. Orda, "Multipath Routing Algorithms for Congestion Minimization," IEEE/ACM Transactions on Networking, Vol. 15, No. 2, pp. 413-424, Piscataway, NJ, USA, April 2007.
[16] P. Zhang, and W. Zhao, "On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems," Proceedings of Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pp. 70-81, Hangzhou, China, 2007.
[17] R. C. Loh, S. Soh, M. Lazarescu, and S. Rai, "A Greedy Technique for Finding the Most Reliable Edge-Disjoint-Path-Set in a Network," Proceedings of 14th IEEE Pacific Rim International Symposium on Dependable Computing, pp. 216-223, Taipei, December 2008.
[18] Ryu. Available: http://osrg.github.com/ryu/
[19] B. Lantz, B. Heller, and N. McKeown, "A Network in a Laptop: Rapid Prototyping for Software-Defined Networks," Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, Monterey, CA, USA, October 2010.
[20] B. M. Waxman, "Routing of Multipoint Connections," IEEE Journal on Selected Areas in Communications, Vol. 6, No. 9, pp. 1617-1622, December 1988.
[21] Internet2. Available: http://www.internet2.edu
[22] Cernet. Available: http://www.edu.cn/HomePage/english/cernet/index.shtml
[23] J. He and J. Rexford, "Toward Internet-Wide Multipath Routing," IEEE Network, Vol. 22, No. 2, pp. 16-21, March-April 2008.
[24] D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley, "Design, Implementation and Evaluation of Congestion Control for Multipath TCP," USENIX Symposium on Networked Systems Design & Implementation, Vol. 11, pp. 8-8, March 2011.
[25] F. Németh, B. Sonkoly, L. Csikor, and A. Gulyás, "A Large-scale Multipath Playground for Experimenters and Early Adopters," Proceedings of the ACM SIGCOMM, pp. 481-482, New York, USA, August 2013.
[26] R. Fleischer, Q. Ge, J. Li, and H. Zhu, "Efficient Algorithms for K-Disjoint Paths Problems on DAGs," Proceedings of Algorithmic Aspects in Information and Management, pp. 134-143, Portland, OR, USA, June 2007.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top