在軟體定義數據中心中改善群播演算法

A Lightweight Multicast Forwarding Algorithm in Software-Defined Datacenter Networks

黃建勳(Jian-Xun Huang)

指導教授 ： 張貴雲

國立中央大學/資訊電機學院/資訊工程學系/碩士(2015年)

摘要

近幾年雲端網路的運用越來越普遍化，許多雲端服務的技術也有研究在改進中，例如群播（Multicsat）這項技術，但是群播在交換器（Switch）所儲存的資料量非常大，有許多研究在使群播這項技術更加的有效率，其中利用布倫過濾器（Bloom Filter）來降低交換器、路由器中的儲存空間以及提高其運行效率雖然可行，但也造成了誤判（False Postitive）的情況，因此為了能夠達到百分之百的傳送正確性又能同時節省交換器中的儲存空間，在2013 年一個新的演算法SVRF 被提了出來，利用質數與中國餘式定理的特性，讓交換器不用在儲存巨大的群播成員，只需要儲存一組數字（Mcp，Mcrt）即可讓交換器知道每一個封包所要送往的出口埠（Output Port）並且也能達到百分之百的傳送準確率，但是SVRF 在交換器埠的數量增加時，其所生成的數值會有巨大的增長，使得所花消耗空間越來越龐大，並且過大的數值在運算時必須透過大樹運算，一般的交換器並無法支援這種運算。本篇論文目的在與改進SVRF 演算法，使得其在交換器埠的數量龐大時，其儲存空間依然可以有效降低，並且依然達到百分之百的傳送準確率。另外我們提出的演算法中分散了交換器儲存的數值，使得可以在一般的交換器中運算，讓此演算法更加貼近實作。

關鍵字

軟體定義網路 ； 群播 ； 雲端網路 ； OpenFlow

並列摘要

In this thesis, we consider a scalability problem associated with software-defined datecenter, of which the unicast/multicast routing state is proven to be NP-complete. Although there are many algorithm about multiple membership query algorithm in unicast/multicast routing, like Bloom Filter and SVRF, they still have some problem. Bloom Filter has the false positive that makes it can not be 100% delivery accuracy and SVRF with 100% delivery accuracy but cost lots of memory space when the number of switch port is huge. In order to solve these problem, we introduce a lightweight multiple membership query algorithm based on the SVRF with the prime theory Chinese Remainder Theorem (CRT). Our proposed algorithm use two phases to reduce the flow table memory usage. First phase is partitioning the membership to lower the prime value; Second phase is partitioning the Output Port Bitmap (OPB) into two part to lower the scalar-pair (Mcp,Mcrt). With these two phases, our algorithm achieves a better performance in flow table memory space usage when the number of switch port is huge, and also achieves the 100% delivery accuracy (including unicast and multicast). Compared to the original SVRF and the improved SVRF, our algorithm can get better performance in in terms of memory consumption. Our work improve the unicast/multicast routing querying algorithm and make it more easier to implement in software-defined datacenter networks.

並列關鍵字

Software-defined Networks ； Multicast ； OpenFlow ； Data Center ； Chinese Remainder Theorem

參考文獻

[1] IEEE RFC 3376. Internet group management protocol, version 3, 2002.

[2] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13:422–426, 1970.

[3] Li Fan, Pei Cao, J. Almeida, and A.Z. Broder. Summary cache: a scalable widearea web cache sharing protocol. Networking, IEEE/ACM Transactions on, 8(3): 281–293, Jun 2000.

[4] O. Rottenstreich, Y. Kanizo, and I. Keslassy. The variable-increment counting bloom filter. Networking, IEEE/ACM Transactions on, 22(4):1092–1105, Aug 2014.

[5] Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. Beyond bloom filters: From approximate membership checks to approximate state machines, 2006.