由於網路的蓬勃發展，加上多媒体(multimedia)技術的應用，使得現有的頻寬己逐漸不敷使用，透過光纖網路可以提供較多的頻寬，故得在固定的頻寬中，使用良好的排程演算法，來增進頻道的重覆使用率，和網路的整體效率。就目前波長分割多工(WDM) 的排程演算法而言，大略可分成三種主要方式:Random access-based protocol 、Pre-allocation-based protocol 以及Reservation-based protocol，本文裡，首先概述個別的工作原理。接著描述所摘錄下來，以Reservation-based protocol為主的六個排程演算法工作原理。而本文所提出的無碰撞(collisionless)排程演算法是以廣播式被動星形隅合器(Passive Star Coupler (PSC))連結的光纖網路架構為主，不但能夠解決之前六個演算法在單一對資料頻道的傳收器中，單次跳躍傳輸可能發生封包碰撞與傳收器困擾的問題，同時我們也考慮收發器的轉換延遲(tuning latency)對整個系統的影響，甚至可適用於Multi-transmission behavior之機制。我們利用模擬程式來評估演算法對於三種不同傳收端(transceiver)架構；評估演算法於multi-transceiver model的效能，包括以節點數、封包數與頻道數為操縱變因的頻道使用率(channel utilization)、平均封包延遲(average packet delay)與輸出率(throughput)。以提供此演算法對不同網路架構彈性運用當參考。

Due to the booming development of network and technical applications of multimedia, the provided bandwidth of the current technology are gradually not enough. The fiber-optic network is a perspective emerging broadband high-speed network could provide much more bandwidth. Furthermore, one important issue is that how we use well-scheduling algorithm in fixed bandwidth to increase the repeat usage of channel and the whole efficiency of network. The scheduling algorithms of current passive star coupler (PSC) WDM networks can be mainly divided into three categories: Random access-based protocol, Pre-allocation-based protocol and Reservation-based protocol. In this thesis, we describe and compare the work principle of six scheduling algorithms that are based on reservation-based protocol. Unfortunately, two important issues are not discussed in the previous papers that are transceiver conflict and tuning latency. In this thesis, the collisionless scheduling algorithm with arbitrary transceiver tuning latencies is proposed based on the fiber-optic network topology using broadcast PSC connection. It can’t only solve the packet collision and transceiver conflict problem during point-to-point transmission, but also we consider the impact of tuning latency on system performance. The proposed scheduling algorithm can also be applied to multicast and broadcast mechanisms. Three different transceiver frameworks (TT-TR, FT-TR, and TT-FR) are investigated and compared in detail by computer simulations. The performance of multi-transceiver models are evaluated in terms of the average packet delay, throughput and channel utilization varied with different number of nodes, packets and channels.

目錄……………………………………………………………………Ⅰ
表目錄…………………………………………………………………Ⅲ
圖目錄…………………………………………………………………Ⅳ
一、緒論………………………………………………………………1
二、相關工作…………………………………………………………4
2.1 Scheduling Strategies……………………………………….4
2.2熟悉的排程演算法………………………………………….……5
2.2.1 Earliest available time scheduling……………………5
2.2.2 Frame scheduling……………………….………………….6
2.2.3 Frame and queue scheduling………….………………….7
2.2.4 Scheduling with receiver-grouping……..…………….7
2.2.5 Balance scheduling with cut-off concept…………….8
2.2.6 Multiple message per node scheduling…………………9
2.2.6.1 深入Multiple message per node scheduling….…...9
2.2.6.2相同平均延遲時間之相異演算法……………….……....10
2.2.6.3 MMPNs之Total packet delay的數學通式…….........12
2.3己存在排程演算法的優缺點……………………………….……13
三、新的排程演算法…………………………………………………15
3.1網路架構………………………………………………………….15
3.2封包基本配置…………………………………………………….16
3.3封包碰撞定義…………………………………………………….18
3.4 基本原理…………………………………………………………18
3.5封包無碰撞演算法……………………………………………….20
3.5.1 Fixed transmitter — tunable receiver model……….22
3.5.2 Tunable transmitter — fixed receiver model……….23
3.5.3 Tunable transmitter — tunable receiver model…….24
3.6 演算法之優缺點…………………………………………………26
四、模擬………………………………………………………………27
4.1模擬環境之定義………………………………………………….27
4.2 Simulation I……………………………………………………29
4.3 Simulation II………………………………………………….31
4.3 Simulation III…………………………………………………33
五、結論與未來工作…………………………………………………36
參考文獻………………………………………………………………37

[1].Babak Hamidzadeh, Ma Maode, and Mounir Hamdi, “Efficient Sequencing Techniques for Variable-Length Messages in WDM Networks”, IEEE Journal, pp, 1309-1319, August 1999.
[2].Shiann-Tsong Sheu, Yue-Ru Chuang, and Hsuen-Wen Tseng, “Balanced scheduling Mechanism for supporting variable-length packets in WDM Networks”, TANET 2000, pp, 895-902, December 2000.
[3].I-Shyan Hwang and Ling-Feng Ku,”Performance Impacts of tuning latency in passive star-coupled DWDM network”, IPC 2000, December 2000. and submitted to IEEE/OSA Journal of Lightwave Technology.
[4].Hashimoto, K., Shibata, Y., and Shiratori, N, ”Agent-oriented flexible multimedia system considering organization and QoS functions”, Database and Expert Systems Applications, 1999. Proceedings. Tenth International Workshop on, Page(s): 662—666, 1999.
[5].Guillemot, C., Clerot, F., Henry, M, Le Corre, A, Kervarec, J, Dupas, A., Billes, L., ”Optical packet switching for WDM high speed backbones”, Optical Communication, 1998. 24th European Conference on Volume: 2, , Page(s): 81-85, 1998.
[6].Kiniry, J.R, ”Wavelength division multiplexing: ultra high speed fiber optics”, IEEE Internet Computing Volume: 2, Page(s): 13-15, March-April 1998.
[7].Hwa-Chun Lin and Chun-Hsin Wang, ”Minimizing the number of multicast transmissions in single-hop WDM networks”, 2000 IEEE International Conference on Volume: 3, Page(s): 1645 -1649, 2000.
[8].Jin Seek Choi and Hyeong Ho Lee, ”A dynamic wavelength allocation scheme with status information for fixed- and variable-length messages”, The Bridge to Global Integration. IEEE Volume: 4, Page(s): 2358-2362, 1998.
[9].Modiano, E., ”Unscheduled multicasts in WDM broadcast-and-select networks”, INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE Volume: 1, Page(s): 86 -93, 1998.
[10].A. Ganz and Y. Gao, “A Time-wavelength Assignment Algorithm for A WDM Star Network”, IEEE Transactions on Communications, Vol. 42, No. 2, pp.1827-1836, Feb. 1994.
[11].K. Bogineni, K. M. Sivalingham, and P. W. Dowd, “Low-complexity Multiple Access Protocols for Wavelength-division Multiplexed Photonic Networks”, IEEE Journal on Selected Areas in Communications, Vol.11, pp. 590-604, May 1993.
[12].T. Weller and B. Majek, “Scheduling Non-uniform Traffic in Packet Switching System with Small Propagation Delay”, IEEE/ACM Transactions on Networking, Vol. 56, pp. 813-823, Dec. 1997.
[13].George N. Rouskas and V. Sivaraman, “Packet Scheduling in Broadcast WDM Networks with Arbitrary Transceiver Tuning Latencies”, IEEE/ACM transactions on networking, Vol. 5, No. 3, pp. 359-370, June 1997.
[14].I-Shyan Hwang and Patrick W. Dowd, "Media Access Protocol Impacts on A WDMA Star Photonic Network with Distributed Shared Memory System", Journal of Information Science and Engineering, Vol. 11, No. 3, pp.345-369, Sep. 1995.
[15].Patrick W. Dowd and I-Shyan Hwang, "Memory and Network Architecture Interaction in An Optically Interconnected Distributed Shared-Memory System", Journal of Parallel and Distributed Computing, Vol. 25, No. 2, pp. 144-161, Mar. 1995.
[16].Leonid G. Kazovsky, Charles Barry, Michael Hickey, Ciro A. Noronha Jr., and Pierluigi Poggiolini, “WDM Local Area Networks”, IEEE LTS, pp. 8-15, May 1992.