臺灣博碩士論文加值系統

由於群播訊務在網際網路中大量的成長，使得群播訊務排程已經成為熱門的
研究議題。為了建構此類的網路，一個能夠快速的將到達輸入連結的封包傳送至
輸出連結的高效能交換器是必要的。在此篇論文中的交換系統，我們將群播封包
的目的位址與資料承載分開處理。演算法將根據目的位址加以排程，並利用共享
記憶體式的儲存策略來處理資料承載以減輕群播封包對交換器的負擔。當目的位
址排入交換器的排程表後，利用跳插演算法預先在排程表中找尋可往前插隊的目
的位址。將目的位址盡量排至排程表的前端以減少封包的延遲時間與交換器發生
阻塞的機率。此交換架構因採用共享記憶體式的儲存策略，因此可以節省群播交
換器的記憶體成本。另外，演算法因針對排程表加以重整，所以可以降低群播衝
突以達到提高交換器產出量的目的。

Due to the rapid growth of multicast traffic on Internet, multicast traffic scheduling
has become one of the most popular issues in researches. In order to construct a
multicast traffic scheduling network, a switch with the capability of quickly transmitting
input packets to their outputs is necessary. In this thesis, we respectively deal with the
destination addresses and data loads of multicast packets. Our algorithm schedules
packets according to their destination addresses, and utilizes shared memory storage in
data management to alleviate the loads of multicast packet switch. After the
destination address enters the scheduling table in switch, the JAQ (Jump a Queue)
algorithm in advance searches for the preemptive destination address in scheduling
tables. If the destination addresses can be scheduled as closely to the forehead of
scheduling table as possible, we can reduce both the packet latency and blocking
probability. In addition, by the shared memory storage, we can also decrease the
memory costs of multicast switch. Consequently, owing to rescheduling the
scheduling tables, multicast conflicts can be substantially decreased while the switch
throughput can also be synchronously enhanced.

目 錄
第一章 緒論 1
1.1 緣起 1
1.2相關研究 1
1.3 研究動機與目的 4
1.4 論文架構 6
第二章 交換器架構與系統模型 7
2.1 交換器基本架構 8
2.1.1 輸入架構 8
2.1.2 交換器內部架構 8
2.1.3 輸出架構 11
2.2 系統模型 12
2.2.1 輸入區塊 12
2.2.1.1 位址細胞 14
2.2.1.2 資料細胞 15
2.2.2交換區塊 15
2.2.2.1 排程表 16
2.2.2.2 跳插排程器 16
2.2.3 資料區塊 18
2.2.4 控制單元 15
第三章 交換機制 22
3.1 跳插演算法 22
3.1.1 符號定義 22
3.1.2 演算法執行流程 23
3.1.3 圖例說明 25
3.2記憶體需求 29
第四章 效能模擬與分析 32
4.1 模擬架構與相關參數 32
4.1.1 模擬架構 32
4.1.2 系統模擬參數 32
4.1.3 取樣名詞定義 35
4.2 模擬結果 35
4.2.1 單點傳輸訊務 35
4.2.1.1 平均排程延遲時間 35
4.2.1.2 平均超額延遲時間 36
4.2.1.3 平均超額頻率 37
4.2.1.4 平均佇列長度 37
4.2.2 群播隨機訊務 39
4.2.2.1 平均排程延遲時間 39
4.2.2.2 平均超額延遲時間 40
4.2.2.3 平均超額頻率 42
4.2.2.4 平均佇列長度 43
4.2.3 群播突發訊務 45
4.2.3.1 平均排程延遲時間 45
4.2.3.2 平均超額延遲時間 46
4.2.3.3 平均超額頻率 48
4.2.3.4 平均佇列長度 49
第五章 結論 51
參考文獻 52























表 目 錄

表3-1 緩衝細胞數量比較表------------------------------------------------------------ 31
表4-1 模擬參數------------------------------------------------------------------------ 33

































圖 目 錄

圖1-1 4×4交換器發生最前端阻塞現象情形-------------------------------------------- 2
圖1-2 三個輸入輸出埠搭配四路(4-Way)縱橫式交換架構的Cisco 12000 GSR 交換器示意圖--------------------------------------------------------------------------- 5
圖2-1 基本交換器架構----------------------------------------------------------------- 7
圖2-2 交換器內部架構----------------------------------------------------------------- 7
圖2-3 固定長度緩衝策略--------------------------------------------------------------- 8
圖2-4 匯流排式傳輸架構--------------------------------------------------------------- 9
圖2-5 共享記憶體式傳輸架構---------------------------------------------------------- 10
圖2-6 縱橫式傳輸架構----------------------------------------------------------------- 11
圖2-7 系統模型------------------------------------------------------------------------- 13
圖2-8 2×2 VOQ Switch利用複製機制處理群播封包情形------------------------------ 13
圖2-9 輸入區塊------------------------------------------------------------------------- 14
圖2-10 位址細胞儲存情形--------------------------------------------------------------- 14
圖2-11 資料細胞儲存情形--------------------------------------------------------------- 15
圖2-12 3×3 Switch的排程表傳輸情形--------------------------------------------------- 16
圖2-13 3×3 Switch的位置矩陣----------------------------------------------------------- 17
圖2-14 3×3 Switch的佔用矩陣與閒置矩陣---------------------------------------------- 18
圖2-15 系統執行流程-------------------------------------------------------------------- 20
圖2-16 傳統系統執行流程--------------------------------------------------------------- 20
圖2-17 管線技術比較圖----------------------------------------------------------------- 20
圖2-18 管線技術效能-------------------------------------------------------------------- 21
圖3-1 跳插演算法執行流程------------------------------------------------------------ 23
圖3-2 初始狀態------------------------------------------------------------------------- 26
圖3-3 讀取與搜尋步驟執行過程------------------------------------------------------- 26
圖3-4 讀取與搜尋步驟執行結果------------------------------------------------------- 27
圖3-5 基本演算法執行過程------------------------------------------------------------ 27
圖3-6 基本演算法執行結果------------------------------------------------------------ 28
圖3-7 跳插步驟初始狀態--------------------------------------------------------------- 23
圖3-8 跳插步驟執行結果--------------------------------------------------------------- 29
圖4-1 模擬架構------------------------------------------------------------------------- 33
圖4-2 單點傳輸訊務平均排程延遲時間------------------------------------------------ 36
圖4-3 單點傳輸訊務平均超額延遲時間------------------------------------------------ 37
圖4-4 單點傳輸訊務平均超額頻率----------------------------------------------------- 38
圖4-5 單點傳輸訊務平均佇列長度----------------------------------------------------- 38
圖4-6 群播隨機訊務平均排程延遲時間(NC=2)---------------------------------------- 39
圖4-7 群播隨機訊務平均排程延遲時間(NC=4)---------------------------------------- 39
圖4-8 群播隨機訊務平均排程延遲時間(NC=8)---------------------------------------- 40
圖4-9 群播隨機訊務平均超額延遲時間(NC=2)---------------------------------------- 40
圖4-10 群播隨機訊務平均超額延遲時間(NC=4)---------------------------------------- 41
圖4-11 群播隨機訊務平均超額延遲時間(NC=8)---------------------------------------- 41
圖4-12 群播隨機訊務平均超額頻率 (NC=2)-------------------------------------------- 42
圖4-13 群播隨機訊務平均超額頻率 (NC=4)-------------------------------------------- 42
圖4-14 群播隨機訊務平均超額頻率 (NC=8)-------------------------------------------- 43
圖4-15 群播隨機訊務平均佇列長度 (NC=2)-------------------------------------------- 43
圖4-16 群播隨機訊務平均佇列長度 (NC=4)-------------------------------------------- 44
圖4-17 群播隨機訊務平均佇列長度 (NC=8)-------------------------------------------- 44
圖4-18 群播突發訊務平均排程延遲時間 (NC=2)--------------------------------------- 45
圖4-19 群播突發訊務平均排程延遲時間 (NC=4)--------------------------------------- 45
圖4-20 群播突發訊務平均排程延遲時間 (NC=8)--------------------------------------- 46
圖4-21 群播突發訊務平均超額延遲時間 (NC=2)--------------------------------------- 46
圖4-22 群播突發訊務平均超額延遲時間 (NC=4)------------------ -------------------- 47
圖4-23 群播突發訊務平均超額延遲時間 (NC=8)--------------------------------------- 47
圖4-24 群播突發訊務平均超額頻率 (NC=2)-------------------------------------------- 48
圖4-25 群播突發訊務平均超額頻率 (NC=4)-------------------------------------------- 48
圖4-26 群播突發訊務平均超額頻率 (NC=8)-------------------------------------------- 49
圖4-27 群播突發訊務平均佇列長度 (NC=2)-------------------------------------------- 49
圖4-28 群播突發訊務平均佇列長度 (NC=4)-------------------------------------------- 50
圖4-29 群播突發訊務平均佇列長度 (NC=8)-------------------------------------------- 50

參考文獻

[1]Mark J, Karol et al., 1987, “Input Versus Output Queueing on a Space-Division Packet Switch”, IEEE Transactions on communications, Vol.35, No.12,pp.1347-1356, December.
[2]Nicholas William McKeown, 1995, Scheduling Algorithms for Input-Queued Cell Switch, University of California at Berkeley, Doctoral Dissertation.
[3]Nick McKeown and Thomas E. Anderson, 1998, “A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches”, Computer Networks and ISDN Systems, Vol.30, No.24, pp.2309-2326, December.
[4]Nick McKeown, 1997, Fast Switched Backplane for a Gigabit Switched Router, Business Communications Review, Vol.27, No.12, December.
[5]Wen-Tsuen Chen et al., 2000, “An Efficient Cell-Scheduling Algorithm for Multicast ATM Switching System”, IEEE/ACM Transactions on Networking, Vol.8, No.8, pp.517-525, August.
[6]H. Jonathan Chao, 2000, “Saturn: A Terabit Packet Switch Using Dual Round-Robin”, IEEE Communications Magazine, Vol.38, No.12, pp.78-84, December.
[7]H. Jonathan Chao, 2000, “Saturn: A Terabit Packet Switch Using Dual Round-Robin”, IEEE Global Telecommunications Conference, No.1, pp.487-495, November.
[8]Yihan Li, Shivendra Panwar, and H. Jonathan Chao, 2001, “On the Performance of a Dual Round-Robin Switch”, IEEE INFOCOM, Vol.3, pp.1688-1697, April.
[9]Yihan Li, Shivendra Panwar, and H. Jonathan Chao, 2002, “The Dual Round-Robin Matching Switch with Exhaustive Service”, IEEE Workshop on High Performance Switching and Routing, pp.58-62, May.
[10]Yihan Li, Shivendra Panwar, and H. Jonathan Chao, 2002, “Performance Analysis of a Dual Round Robin Matching Switch with Exhaustive Service”, IEEE Globecom, Vol.3, pp.2292-2295, November.
[11]R. Manivasakan, Mounir Hamdi, and Danny H. K. Tsang, 2002, “The Dual Round Robin Pseudo-grant Matching for high-speed packet Switches”, IEEE Workshop on High Performance Switching and Routing, pp.64-68, May.
[12]Heyung Sub Lee et al., 2002, “A Multicast Switching Algorithm Based on iSLIP”, International Technical Conference On Circuits/Systems Computers and Communications, pp.1011-1014, July.
[13]Meina Song, Junde Song, and Renjie Pi, 2003, “An Improved Multicast Traffic Scheduling Scheme in the Packet-Switching Systems”, Australian Telecommunications Networks and Applications Conference, December.
[14]Lotfi Mhamdi, and Mounir Hamdi, 2004, “Scheduling Multicast Traffic in Internally Buffered Crossbar Switches”, IEEE International Conference on Communications, Vol.2, pp.1103-1107, June.
[15]Deng Pan, and Yuanyuan Yang, 2004, “FIFO Based Multicast Scheduling Algorithm for VOQ Packet Switches”, IEEE International Conference on Parallel Processing, Vol.1, pp.318-325, August.
[16]Balaji Prabhakar, Nick McKeown, and Ritesh Ahuja, 1997, “Multicast Scheduling for Input-Queued Switches”, IEEE Journal of Selected Areas in Communications, Vol.15, No.5, pp.855–866, June.
[17]Chuang S.-T et al., 1999, “Matching Output Queueing with a Combined Input Output Queued Switch”, IEEE Journal of Selected Areas in Communications, pp.1030-1039, June.
[18]Roberto Rojas-Cessa, Eiji Oki, Zhigang Jing, and H. Jonathan Chao, 2001, “CIXB-1: Combined Input-One-Cell-Crosspoint Buffered Switch”, IEEE Workshop on High Performance Switching and Routing, pp.324-329, May.
[19]Roberto Rojas-Cessa, Eiji Oki, and H. Jonathan. Chao, 2001, “CIXOB-k: Combined Input-Crosspoint-Output Buffered Packet Switch”, IEEE Globecom, Vol. 4, pp.2654-2660, November.
[20]Cyriel Minkenberg, 2000, “Integrating Unicast and Multicast traffic Scheduling in a Combined Input- and Output-Queued Packet-Switching System”, IEEE Computer Communications and Networks, pp. 127-134, October.
[21]Grzegorz Danilewicz et al., 2004, “Packet Switch Architecture with Multiple Output Queueing”, IEEE Global Telecommunications Conference, Vol.2, pp.1192-1196, November.
[22]Tarjan R. E., 1983, Data Structures and Network Algorithms, Bell Labs.
[23]K. J. Schultz and P. G. Gulak, 1994, “Distributed Multicast Contention Resolution using Content Addressable FIFOs”, Proceedings of International Conference Communications, pp.1495-1500.
[24]Andrea Bianco et al., 2003, “On the Number of Input Queues to Efficiently Support Multicast Traffic in Input Queued Switches”, IEEE Workshop on High Performance Switching and Routing, pp.111-116, June.
[25]Meina Song, Xiaosu Zhan, and Junde Song, 2004, “An Efficient Queueing Scheme for Multicast Packet Switching Routers”, IEEE International Conference on Computer Supported Cooperative Work, Vol.1, pp.572-577, May.
[26]Pankaj Gupta, 1996, “Scheduling in Input Queued Switches: A Survey”, [Online]. Available: http://klamath.stanford.edu/~pankaj/research.html, June.
[27]M. Ajmone Marsan et al., 2001, “Optimal Multicast Scheduling in Input-Queued Switches”, IEEE International Conference on Communications, Vol.7, pp.2021-2027, June.
[28]Timothy X Brown, 2001, “Switch Packet Arbitration via Queue-Learning”, Advances in Neural Information Processing Systems 14, pp.1337-1344, December
[29]Shashank Gupta, Adnan Aziz, 2001, “Multicast scheduling for switches with multiple input-queues”, IEEE High Performance Interconnects, pp.28-33, August.
[30]Jong Arm Jun et al., 2003, “A Two-Dimensional Scalable Crossbar Matrix Switch Architecture”, IEEE International Conference on Communications, Vol.26, No.1, pp.1892-1896, May.