用頻繁樣式探勘實現軟體定義網路上的可擴展性群播

隨著軟體定義網路變得流行，搭配OpenFlow protocol 的路由器以廣泛的使用在網路研究上。在過去的許多研究中，已有不少研究是針對可擴展性的軟體定義網路，多半是透過壓縮forwarding table來達成，例如ternary content-addressable memory (TCAM)、Bloom filter (BF)、或者是透過負載均衡的方式實現，但是沒有任何一個研究是使用頻繁樣式探勘的技巧來降低路由器中群的狀態數量。而在我們得這份研究中，我們研究了軟體定義網路上的可擴展性群播，並使用頻繁樣式探勘的技巧來解決可擴展性群播。在這份研究中，我們針對三種種類的相關研究做了整理：繁樣式探勘、傳統網路下的可擴展性群播、以及可擴展性軟體定義網路。我們使用繁樣式探勘來找出所有可能被當作共同群狀態的sub tree。傳統網路下的可擴展性群播的相關研究當做可擴展性群播的歷史演進，並從中尋找可供參考的方法。而最近關於可擴展性軟體定義網路的研究則是我們參考在新的網路架構下，已有的研究都使用什麼方式解決網路可擴展性的問題。我們使用頻繁樣式探勘的術語描述了軟體定義網路上的可擴展性群播問題，提出了一個可解決的方式，並提出不同的效能測度來衡量結果的好壞。最後我們做出了實驗並證實我們的演算法確實可以解決軟體定義網路上的可擴展性群播問題，提升網路的可擴展性。

關鍵字

群播；軟體定義網路；頻繁樣式探勘；可擴展性； OpenFlow

並列摘要

As the concept of software defined networking (SDN) is popular, routers with OpenFlow are widely used in network research. In this work, we focus on scalable multicast on SDN, about which many works have shown that an increase in scalability of SDN can be achieved by compressing the forwarding table (like ternary content-addressable memory (TCAM) or Bloom filter (BF)), while some works increase scalability by load-balance. None of these approaches, however, use subgraph mining techniques to reduce group states in the routers, without having to compress the forwarding table. In this work, we explore three kinds of related works: subgraph mining, traditional scalable multicast, and the scalable SDN. Subgraph mining is used in this work because with the possible selections of reduced groups, the scalability dramatically increases by a proper support. Traditional multicast works are referenced as historical views of scalable multicast in a traditional network framework, with some of their strategies still being workable in an SDN framework. And finally, the recent works on scalable SDN provide many possible solutions to improve the network scalability, and many possible techniques for utilizing SDN. We describe the Multicast Scalability Problem for SDN in view of subgraph mining, and we provide performance measures and a heuristic algorithm to solve it, by choosing frequent group entries based on the position of the pattern in each multicast group and its support. Finally, we show that our method successfully increased the scalability of the multicast in SDN.