臺灣博碩士論文加值系統

軟體定義網路(Software defined networking, SDN)將控制層 (control plane)與資料層(data plane)分離，網路管理者能藉由控制器，以集中化的方式管理網路上的交換器，並根據網路策略規劃路由路徑。在SDN，為了能有效提升轉發封包的效率，交換器通常會使用TCAM來加快路由表搜尋的時間。然而，當重新路由的次數太頻繁時，TCAM就必須不斷的更新路由表以確保路由表的規則正確排序。而轉發封包的動作必須被停止直到TCAM更新結束，才能正常的轉發封包。因此，為了要減少重新路由的情況，本論文提出以最小瓶頸生成樹為基礎的路由演算法，在決定路由時，會以best-effort的方式盡可能地平均使用所有link做為傳輸路徑。我們亦提出了動態門檻值演算法，動態門檻值會隨著當下的頻寬調整當前的門檻值，避免過去SDN的路由演算法設定固定門檻值所造成的問題。實驗結果證明，本論文提出的路由算法相較於過去的方法，不僅能有效降低控制器重新路由次數與交換器端的TCAM更新次數，也能降低遺失的封包數及達到較佳的網路負載平衡。

Software-defined networking (SDN) decouples the control plane and data plane of network devices. The decoupling allows network administrators to manage network services and determine forwarding paths in a centralized manner. In order to increase the performance of packet forwarding in SDN networks, the switches are usually equipped with ternary content addressable memory (TCAM) to shorten the look up time. When the events of path rerouting frequently occur, switches must perform TCAM updates for the correctness of packet forwarding. While the TCAM updates, packet forwarding could be halted to avoid race condition. In order to reduce the occurrence of path rerouting, we propose a routing scheme which can evenly distribute routing paths to different links. We also develop a floating-threshold algorithm to adjust the threshold value based on the average traffic load. With the proposed routing scheme and floating-threshold algorithm, redundant path rerouting can be avoided. The experimental results demonstrate that the proposed scheme can reduce the number of path-rerouting occurrences. As a result, the average and total number of installed rules can be lowered to minimize TCAM updates. The proposed scheme also achieves a better balance of link loads.

摘要 i
Abstract ii
Table of Contents iii
List of Figures iv
List of Tables v
Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 Static Routing Schemes 4
2.2 Dynamic Routing Schemes 5
2.3 TCAM Update Schemes 6
Chapter 3 The Proposed Scheme 8
3.1 Controller Modules 8
3.2 Minimum Bottleneck Spanning Tree 11
3.3 Default Path Algorithm 14
3.4 Alternative Path Algorithm 16
3.5 Link Load Monitor Algorithm 19
3.6 Rerouting Algorithm 21
Chapter 4 Performance Evaluation 25
4.1 Experimental Environment 25
4.2 The Comparison of Different Threshold Values 27
4.3 The Comparison of Routing Schemes 29
4.4 The Comparison of Fixed and Floating Thresholds 33
Chapter 5 Conclusion and Future Work 36
References 37

[1]McKeown, Nick. "Software-defined networking." INFOCOM keynote talk 17.2 (2009): 30-32.
[2]Jiang, Jehn-Ruey, et al. "Extending Dijkstra's shortest path algorithm or software defined networking." Network Operations and Management Symposium (APNOMS), 2014 16th Asia-Pacific. IEEE, 2014.
[3]Dijkstra, Edsger W. "A note on two problems in connexion with graphs." Numerische mathematik 1.1 (1959): 269-271.
[4]Nguyen, Trong-Tien, and Dong-Seong Kim. "Accumulative-load aware routing in software-defined networks." Industrial Informatics (INDIN), 2015 IEEE 13th International Conference on. IEEE, 2015.
[5]Cheocherngngarn, Tosmate, et al. "Depth-First Worst-Fit Search based multipath routing for data center networks." Global Communications Conference (GLOBECOM), 2012 IEEE. IEEE, 2012.
[6]Di Stefano, Antonella, et al. "A4sdn-adaptive alienated ant algorithm for software-defined networking." P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2015 10th International Conference on. IEEE, 2015.
[7]Dorigo, Marco, Mauro Birattari, and Thomas Stutzle. "Ant colony optimization." IEEE computational intelligence magazine 1.4 (2006): 28-39.
[8]Kim, Seonhyeok, et al. "Congestion prevention mechanism based on Q-leaning for efficient routing in SDN." Information Networking (ICOIN), 2016 International Conference on. IEEE, 2016.
[9]Watkins, Christopher JCH, and Peter Dayan. "Q-learning." Machine learning 8.3 (1992): 279-292.
[10]Kanagavelu, Renuga, et al. "Openflow based control for re-routing with differentiated flows in data center networks." Networks (ICON), 2012 18th IEEE International Conference on. IEEE, 2012.
[11]Kanagevlu, Renuga, and Khin Mi Mi Aung. "SDN controlled local re-routing to reduce congestion in cloud data center." Cloud Computing Research and Innovation (ICCCRI), 2015 International Conference on. IEEE, 2015.
[12]Chang, Yeim-Kuan, and Kai-Yang Liu. "An Efficient TCAM Update Scheme for Packet Classification." Advanced Information Networking and Applications (AINA), 2013 IEEE 27th International Conference on. IEEE, 2013.
[13]Kuo, Fang-Chen, Yeim-Kuan Chang, and Cheng-Chien Su. "A memory-efficient TCAM coprocessor for IPv4/IPv6 routing table update." IEEE Transactions on Computers 63.9 (2014): 2110-2121.
[14]Luo, Layong, et al. "A hybrid hardware architecture for high-speed IP lookups and fast route updates." IEEE/ACM Transactions on Networking (TON) 22.3 (2014): 957-969.
[15]Dharmapurikar, Sarang, et al. "Fast packet classification using bloom filters." Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems. ACM, 2006.
[16]Wen, Xitao, et al. "Ruletris: Minimizing rule update latency for tcam-based sdn switches." Distributed Computing Systems (ICDCS), 2016 IEEE 36th International Conference on. IEEE, 2016.
[17]GENI, "OpenFlow Discovery Protocol and Link Layer Discovery Protocol," 2000 [Online]. Available: http://groups.geni.net/geni/wiki/OpenFlowDiscoveryProtocol
[18]McKeown, Nick, et al. "OpenFlow: enabling innovation in campus networks." ACM SIGCOMM Computer Communication Review 38.2 (2008): 69-74.
[19]Camerini, Paolo M. "The min-max spanning tree problem and some extensions." Information Processing Letters 7.1 (1978): 10-14.
[20]Ryu official website, "Ryu SDN Framework," 2017 [Online]. Available: http://osrg.github.io/ryu/
[21]Lantz, Bob, Brandon Heller, and Nick McKeown. "A network in a laptop: rapid prototyping for software-defined networks." Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. ACM, 2010.
[22]Srivats, P. "OSTINATO: An open, scalable packet/traffic generator." FOSS. IN (2010): 80.
[23]Mirjalily, Ghasem, et al. "An approach to select the best spanning tree in Metro Ethernet networks." Computer and Information Technology, 2008. CIT 2008. 8th IEEE International Conference on. IEEE, 2008.