效率三元位址規則切割和分布利用覆蓋集合概念演算法在軟體定義網路

Efficient TCAM Rule Distribution on Cover-Set Graph Partition in Software-Defined Networking

李建霖(Chien-Lin Lee)

指導教授 ： 許健平

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2015年)

https://doi.org/10.6843/NTHU.2015.00542

摘要

在軟體定義網路中三位元可定址內容記憶體(Ternary Content Access Memory, TCAM) 是一個重要的有限資源，現今的交換機安置的TCAM大小，大約只有幾千行規則位址，成了軟體定義網路(Software Define Network, SDN) 在提供多功能的網路應用和更多的網路需求時的主要阻礙。在這篇論文中我們提出一個在規則位址分配架構(Rule Distribution)下的演算法，使網路上的交換機TCAM資源更有效率的共享。規則位址分配架構將網路上所有的規則收集後、分割，然後分到網路上不同的交換機上。我們所提出的演算法探討如何平均分割規則位址同時達到最少量的額外規則位址產出。這樣的問題是一個NP-hard的問題，因此我們提出異質(heuristic)演算法，並且運用規則覆蓋方法和Fiduccia-Matheyses圖形分割演算法。然後使用Classbench 規則位址模擬器來模擬實際網路規則位址狀況。我們所提出的演算法能有效的減少額外規則位址，同時也使分割後的規則位址群更加平均。

關鍵字

軟體定義網路 ； 三元可定址內容記憶體 ； 規則重疊問題 ； 規則切割問題

並列摘要

In Software-Defined Networking (SDN), Ternary Content Access Memory (TCAM) is a scarce and expensive resource, providing only a few thousands of rule entries on a network switch. In this paper, we propose an algorithm under rule distribution scheme which allows switches in the network to share their TCAM resources in order to achieve better TCAM space utilization. Rule distribution scheme collects rules from network switches and redistributes the rule sets to network switches after partition the overall rules to rule sets. Our proposed algorithm mainly deals with the balanced rule partition problem, which is an NP-hard problem. We design a heuristic algorithm utilizing cover-set graph dependency and Fiduccia-Matheyses graph partition concept. We evaluate our algorithm by real world synthetic routing policy provided by ClassBench packet classification simulator. The result shows that our algorithm efficiently reduces the overall rule space overhead and balances the decomposed rule sets.

並列關鍵字

Software-defined networking ； ternary content access memory ； rule dependency ； rule partition ； open flow

參考文獻

[2] K. Nanxi, L. Zhenming, R. Jennifer, and D.Walker, “Optimizing the“ One Big Switch” Abstraction in Software Defined Networks,” Proceedings of the Ninth ACM Conference on

[3] Z. Ying, N. Sriram, H. Xin, B. Neda, and M. Ravi, “A Compressive Method for Maintaining Forwarding States in SDN Controller,” HotSDN, pp. 139-144, Chicago, IL, USA, August 2014.

[8] K. Yossi, H. David, and K. Isaac, “Palette: Distributing Tables in Software-Defined Networks,” Proceedings of IEEE INFOCOM, pp 545-549, April 2013.

[9] C. M. Fiduccia and R. M. Matheyses, “A Linear-Time Heuristic for Improving Network Partitions,” Proceedings of the 19th IEEE Design Automation Conference, pp 175-181, 1982.

[10] A. X. Liu, C. R. Meiners, and E. Torng, “TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMs,” IEEE Transactions on Networking, vol. 18, no. 2, pp. 490-500, April 2010.