利用內容定址記憶體與最佳樹覆蓋的 綠能軟體定義網路封包分類器

Abstract

在本篇論文中，我們提出了一個演算法來把在路由表中的規則切 成一塊塊的區塊。當交換機收到一個封包時，它會利用路由表去決定 要如何處理這個封包。如果我們把路由表都儲存在三態内容尋址存儲 器，那就會消耗太多的能量，所以我們使用我們的演算法來切割規 則。交換機會先搜尋三態内容尋址存儲器的索引來決定要開哪個區 塊，那些沒有被打開的區塊可以被關掉來節省能量。在軟體定義網路 的標準中，每一條規則後面都有計算器，所以我們可以利用它得知每 一條規則目前有多少封包符合它，我們可以利用這個資訊來計算每一 條規則被符合的機率有多少，並利用這個資訊來設計我們的演算法。 我們會建一棵樹來代表規則，並利用動態規劃演算法來切割規則。模 擬顯示我們的演算法可以省下大量的能量。

In this thesis, we proposed an algorithm to divide rules to buckets. When a switch receives a packet, it needs to use flow table to decide how to process the packet. If we put flow table to TCAM, it will consume too much power, so we use our algorithm to divide rules. A switch will match index TCAM to decide to open which bucket, the buckets which are not opened can be closed to save power. There are counters in each rule in openflow standard, so we can know there is how many packets match each rule. We use the knowledge to calculate the probability of each rule matched and use it to design our algorithm. The object of our algorithm is to open entries in each search as less as possible. We will build a tree to represent rules and use dynamic programming algorithm to divide rules to buckets. Simulation result shows that our algorithm can reduce power consumed by TCAM very much.