| 姓名 |
黃建勳(Jian-Xun Huang)
查詢紙本館藏 |
畢業系所 |
資訊工程學系 |
| 論文名稱 |
在軟體定義數據中心中改善群播演算法
(A Lightweight Multicast Forwarding Algorithm in Software-Defined Datacenter Networks)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
近幾年雲端網路的運用越來越普遍化，許多雲端服務的技術也有研究在改進中，例如群播（Multicsat）這項技術，但是群播在交換器（Switch）所儲存的資料量非常大，有許多研究在使群播這項技術更加的有效率，其中利用布倫過濾器（Bloom Filter）來降低交換器、路由器中的儲存空間以及提高其運行效率雖然可行，但也造成了誤判（False Postitive）的情況，因此為了能夠達到百分之百的傳送正確性又能同時節省交換器中的儲存空間，在2013 年一個新的演算法SVRF 被提了出來，利用質數與中國餘式定理的特性，讓交換器不用在儲存巨大的群播成員，只需要儲存一組數字（Mcp，Mcrt）即可讓交換器知道每一個封包所要送往的出口埠（Output Port）並且也能達到百分之百的傳送準確率，但是SVRF 在交換器埠的數量增加時，其所生成的數值會有巨大的增長，使得所花消耗空間越來越龐大，並且過大的數值在運算時必須透過大樹運算，一般的交換器並無法支援這種運算。本篇論文目的在與改進SVRF 演算法，使得其在交換器埠的數量龐大時，其儲存空間依然可以有效降低，並且依然達到百分之百的傳送準確率。另外我們提出的演算法中分散了交換器儲存的數值，使得可以在一般的交換器中運算，讓此演算法更加貼近實作。 |
| 摘要(英) |
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. |
| 關鍵字(中) |
★ 軟體定義網路
★ 群播
★ 雲端網路
★ OpenFlow |
關鍵字(英) |
★ Software-defined Networks
★ Multicast
★ OpenFlow
★ Data Center
★ Chinese Remainder Theorem |
| 論文目次 |
中文摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vi
1 Introduction 1
2 Related Work 5
2.1 Internet Group Management Protocol 5
2.2 Bloom Filter 6
2.3 The Counting Bloom Filters 6
2.4 The Variable-Increment Counting Bloom Filter 7
2.5 Stateful Bloom Filter 7
2.6 Counter Braids: A Novel Counter Architecture for Per-Flow Measurement 8
2.7 Scalar-Pair and Vectors Routing and Forwarding 8
2.8 ALEX: An Arithmetic-based Unified Unicast and Multicast Routing for MANETs 9
3 The Proposed Algorithm 11
3.1 Preliminaries 11
3.2 Proposed Algorithm 14
3.2.1 Proposed System Frame 15
3.2.2 Membership Partition Phase 16
3.2.3 OPB Partition Phase 16
3.2.4 Use TACM to Store Scalar-Pair 18
3.2.5 Querying Group Membership 19
3.2.6 An Example 21
3.2.7 Number of Row 21
3.2.8 Discussion for Implementation 23
4 Simulation Analysis 24
4.1 Scenario 24
4.2 Total Memory Usage 24
4.3 Single pair (Mcp, Mcrt) Memory Usage 25
4.4 Number of Prime Keys 26
5 Conclusion 30
Reference 32 |
| 參考文獻 |
[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.
[6] Yi Lu, Andrea Montanari, Sarang Dharmapurikar, Abdul Kabbani, and Balaji Prabhakar. Counter braids: A novel counter architecture for per-flow measurement. In In ACM SIGMETRICS¡¦08, 2008.
[7] Wen-Kang Jia and Li-Chun Wang. A unified unicast and multicast routing and forwarding algorithm for software-defined datacenter networks. Selected Areas in Communications, IEEE Journal on, 31(12):2646–2657, December 2013.
[8] Lusheng Ji and M. Scott Corson. Explicit multicasting for mobile ad hoc networks. Mob. Netw. Appl., 8(5):535–549, October 2003.
[9] Wen-Kang Jia, Chia-Yao Chen, and Yaw-Chung Chen. Alex: An arithmetic-based unified unicast and multicast routing for manets. In Wireless Communications and Networking Conference (WCNC), 2014 IEEE, pages 2114–2119, April 2014.
[10] IEEE 802.1AB. Link layer discovery protocol. |
| 指導教授 |
張貴雲(Guey-Yun Chang)
|
審核日期 |
2015-8-13 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
