成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	鄭翰濰 Zheng, Han-Wei
論文名稱：	最小記憶體頻寬及分散式的分享記憶體交換器 Design of Least Memory-Bandwidth Shared Memory Switch with Decentralized Control
指導教授：	卿文龍 Chin, Wen-Long
學位類別：	碩士 Master
系所名稱：	工學院 - 工程科學系 Department of Engineering Science
論文出版年：	2011
畢業學年度：	99
語文別：	中文
論文頁數：	65
中文關鍵詞：	分享式交換器、分散式控制
外文關鍵詞：	shared memory switch, decentralized control
相關次數：	點閱：97 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著日漸發達的網際網路，網路已融入日常生活中，成為生活上的一部分，然而網路傳輸速度不斷的進步，網路流量由平坦趨近暴衝(burst)，目前傳輸速度可達到Gigabit/s，未來甚至將達到Terabit/s，網路封包交換器如不發展出新架構，勢必將成為網路系統中的瓶頸。

分享式記憶體封包交換器(shared-memory packet switch)在暴衝流量下，可提供最佳的傳輸量和極低封包遺失率，但分享式記憶體封包交換器需擴充成大規格的交換器時，到記憶體存取速度及中央式排程控制使擴充難度提升。滑動視窗封包交換器(sliding-window packet switch)是一種分享式記憶體架構的交換器，各個記憶體模組實際是分開的，但邏輯上是可共享的，且利用虛擬的3-D平面，封包依序被讀出記憶體，當讀出之封包所在平面與指標所在平面相同，即傳送到輸出埠，反之，則不會將封包讀出，藉此達到分散式控制，克服分享式記憶體封包交換器記憶體存取速度及中央式排程控制兩大限制。不過滑動視窗封包交換器需大量的記憶體模組才可達到全部記憶體共享，衍生出記憶體使用率低及記憶體頻寬浪費兩大問題。

本篇論文將結合分享式記憶體封包交換器和滑動視窗封包交換器記憶體共享和擴充性高兩大特點，提出嶄新的交換器，設計的觀念在保留滑動視窗封包交換器將記憶體模組分開但邏輯上卻是共享的觀念，並提出一套特殊的封包排程演算法，使交換器傳輸量達到最佳、封包遺失率低和記憶體使用率高。

我們使用暴衝流量模型(bursty traffic model)模擬真實的網路流量，證明了最小記憶體頻寬及分散式控制的分享記憶體封包交換器的傳輸量、封包遺失率和記憶體使用率，都比滑動視窗封包交換器來的更佳，並利用暴力法及基因演算法找出交換器理想的傳輸量，以和設計出之封包排程器的傳輸量比較，以做為改進封包排程演算法之依據。

With the advances of Internet, the Internet has been integrated into our daily life and become a part of our life. The network traffic becomes bursty because of the increasing transmission rate. The present transmission rate can reach Gigabit/s and even up to Terabits/s. If we do not design a new architecture for the packet switch, it will be the bottleneck in the network system.

The shared-memory packet switch can provide the best throughput and the lowest packet loss rate under the condition of bursty traffic. However, its scalability problem becomes difficult because of the memory-access speed in centralized control. The Sliding-Window(SW) is a switch based on the shared-memory packet switch architecture, where physically separated multiple memory modules are logically shared among all the ports of the switch. It is fantastic owing to its decentralized control that with the self-routing parameter, the packet will transmit from a memory module to an output port by itself. So that the SW switch can overcome the problems of memory access rate and centralized control. The SW switch provides a complete sharing of all the memory modules among all input and output ports, but requires amount of memory modules. The problem causes of the lower memory utilization and the waste of memory bandwidth.

In the paper, a new packet switch architecture for the shared-memory packet switch and the SW packet switch, called the Least Memory-Bandwidth Shared Memory Switch with Decentralized Control, is proposed a new packet scheduling algorithm, which provides the best throughput, the lowest packet loss rate and higher memory utilization.

We do the simulation by the bursty traffic model, which proves that the throughput, packet loss rate and memory utilization of our proposed switch are better than the SW. We compare the throughput of our proposed switch with the ideal throughput by the way of Brute force method and Genetic algorithm.

中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i
英文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..ii
誌謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..iv
目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .v
表目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..ix
圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .x
符號說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...xiv
第一章、背景知識. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1封包交換器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
2三種不同封包傳遞方式. . . . . . . . . . . . . . . . . . . . . . . . . . . .2
2.1單點傳播(unicast)....... . . . . . . . . . . . . . . . . . . . . . . . . . . .2
2.2 廣播傳播(broadcast)......... . . . . . . . . . . . . . . . . . . . . . . . . .2
2.3 多點傳播(multicast)......... . . . . . . . . . . . . . . . . . . . . . . . . .3
3 三種依佇列不同封包交換器. . . . . . . . . . . . . . . . . . . . . . . . .3
3.1 輸入埠佇列交換器(input queue switch)................ . . . . . . . . . . . . . . .3
3.2 輸出埠佇列交換器(output queue switch)................. . . . . . . . . . . . . . .5
3.3結合輸入和輸出埠佇列交換器(combined input and output queue switch)......................
............ . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
4 交換器結構(switch fabric)............ . . . . . . . . . . . . . . . . . . . . . . . . . .7
4.1 分時交換(time-division switching)...................... . . . . . . . . . . . . . . . . . .7
4.2分空間交換(space-division switching)....................... . . . . . . . . . . . . . . . .8
4.3多級互連網路封包交換器(multistage interconnection networks packet switch).................................
............. . . . . . . . . . . . . . . . . . . . . . . . . . . .9
4.4滑動視窗封包交換器(sliding-window packet switch).......................... . . . . . . . 10
4.5滑動視窗封包交換器記憶體分享策略. . . . . . . . . . . . . . . ..13
5 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..15
6論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..15
第二章、最小記憶體頻寬及分散式的分享記憶體封包交換器. . . . . . . . . . . ..16
1 交換器架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..16
2操作流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..19
2.1接收端. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..19
2.2傳送端. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
2.3記憶體分享策略. . . . . . . . . . . . . . . . . . . . . . . . . . . ..23
第三章、封包排程演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..24
1演算法目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..24
2 演算法流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..24
2.1 優先選擇封包. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..25
2.2 分配記憶體模組. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..28
3圖解最小記憶體頻寬及分散式控制的分享式記憶體交換器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..29
第四章、實現最小記憶體頻寬及分散式的分享記憶體封包交換器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..34
1演算法實現其困難度. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..34
2 硬體演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..34
3 各個模組說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..38
3.1同步訊號. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..39
3.2 交換器記憶體. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..39
3.3交換器埠端. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..40
3.4 記憶體模組排程器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..43
3.5 空佇列管理者. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..44
4 FPGA實現. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..46
5硬體效能及模擬驗證. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..48
第五章、模擬驗證. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..49
1 模擬環境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..49
2 滑動視窗封包交換器與最小記憶體頻寬及分散式的分享式記憶體封包交換器比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.1 傳輸量與封包遺失率. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..51
2.2 記憶體使用率. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..53
2.3 時間延遲. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..54
3暴力法與基因演算法驗證. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..55
3.1暴力法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..55
3.2 基因演算法(genetic algorithm,GA). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..56
3.3模擬比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..60
3.4 演算法總結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..62
第六章、結論與未來展望. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..63
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..64


                                    

[1]J. Karol, G. Hluchyj, P. Morgan, "Input versus Output Queueing on a Space-Division Switch", IEEE Transactions on Communications, vol. 35, NO. 12, pp. 1347-1356, Dec. 1987.

[2]S. Chuang, A. Goel, N. McKeown, "Matching Output Queueing with a Combined Input/Output Queued Switch", IEEE Journal on Selected Ares in Communication, VOL. 17, NO. 6, Jun. 1999.

[3]C. Kolias, I. Tomkos, "Switch Fabrics", IEEE Circuits and Devices Magazine, September/October 2005.

[4]H. Jonathan Chao, B. Liu, "High Performance Switches and Rounters", JohnWiley and Sons, New Jersey, pp. 181-183, 2007.

[5]L. Mhamdi, "PBC：A Partially Buffered Crossbar Packet Switch", IEEE Transactions on Computers, vol. 58, No. 11, pp. 1568-1581, Nov. 2009.

[6]S. Kumar, "The Sliding-window Packet Switch: A New Class of Packet Switch Architecture with Plural Memory Modules and Decentralized Control", IEEE J. Select, Areas Communications, vol. 21, pp. 656-673, May 2003.

[7]S. Kumar, T. Doganer, A. Munoz, "The Effect of Traffic Burstiness on Memory-Bandwidth of the Sliding-Window Switch", International Conference on Networking, March 2004.

[8]S. Kumar, T. Doganer, "Memory-Bandwidth Performance of the Sliding-Window Based Routers/Switches", IEEE Worldtop on Local&Metropolitan Area Networks, San Francisco, CA, Apr. 2004.

[9]S. Kumar, T. Doganer, "Impact of Scan-Planes on Memory-Bandwidth of the Sliding-Window Switch", IEEE 2005.

[10]S. Venkatraman, G. Yen, "A Generic Framework for Constrained Optimization Using Genetic Algorithms", IEEE Transactions on Evolutionary Computation, VOL. 9, NO. 4, Aug. 2005.

[11]林豐澤, "演化式計算下篇：基因演算法以及三種應用實例",智慧科技與應用統計學報, pp. 29-56.

校內：2016-08-30公開
校外：不公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文