臺灣博碩士論文加值系統

架構在單距WDM網路上的群播封包之排程方法可分為三大類，隨意存取(random-access)事先配置(pre-allocation)及預留方式(reservation)。而預留方式的排程方法又可分為一次只排程一個封包的方式及整批封包排程的方式，在本篇論文中，我們研究以預留方式為基礎的群播封包之排程方法，目的在於發展一個可以產生較低平均封包延遲的群播封包排程方法。
首先，我們研究以整批封包排程的方式，而且不允許將一個群播的封包的傳送，分成以多個單一的封包或多個群播的封包的方式來傳送，在這種方式下，產生較低封包延遲的關鍵在於如何排程整批封包使其所需的資料時段為最少， 我們證明這是一個NP-Complete的問題，並提出一個啟發式的方法，模擬研究的結果顯示，在系統負載從中到重的情況下，我們所提出的方法會有較低的平均封包延遲。
再者，我們研究一次只排程一個封包的方式，且允許將一個群播的封包的傳送，分成以多個單一的封包或多個群播的封包的方式來傳送。在這種方式下，我們探討在封包延遲為最短的條件下，如何以最少的次數傳送來完成一個群播封包的傳送，我們證明這是一個NP-Complete的問題。因此，我們提出一個maximum-available-destination 的排程方法，並藉由程式的模擬，與不做分割的排程方法(no-partition)及可做分割的排程方法(greedy scheduling)做效能的比較，模擬研究的結果顯示，我們所提出的方法會有較低的平均封包延遲。
最後，我們深入探究可做分割的排程方法(greedy scheduling)與不分割的排程方法(no-partition)。我們發現，可做分割的排程方法(greedy scheduling)所產生的平均封包延遲不見得一定比不做分割的排程方法(no-partition)所產生的平均封包延遲為低，我們提出一個混合式的排程方法，可依據資料通道(data channel)與接收器(receiver)的平均使用率，動態的選擇使用可做分割的排程方法(greedy scheduling)或不分割的排程方法(no-partition)，模擬研究的結果顯示，我們所提出的混合式的排程方法，在各種不同系統負載範圍、群播大小、單一封包的比例、以及資料通道的個數等情況下，均會較其他兩個方法有較低的平均封包延遲。

Scheduling algorithms for multicast packets in single-hop WDM networks can be classified into three categories, namely, random-access based, pre-allocation based and reservation-based scheduling algorithms. Reservation-based scheduling algorithms can be further classified as one-by-one scheduling or batch scheduling depending on whether reservation requests are processed one at a time or a batch at a time. In this thesis, we focus on the reservation-based multicast scheduling algorithms. Our goal is to develop the multicast scheduling algorithms that produce lower mean packet delay.
We first investigate a batch-scheduling scheme which does not partition a multicast transmission into multiple unicast or multicast transmissions. The key to produce low average packet delay is to minimize the number of data slots used for scheduling a batch of multicast packets. The problem is formulated as a minimization problem and shown to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. The simulation results show that the
proposed scheduling algorithm produces significantly lower mean packet delays when the load of the system is
medium to heavy.
Next, we investigate a one-by-one scheduling scheme in which partitioning a multicast transmission into multiple unicast or multicast transmissions is allowed. The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop WDM networks is studied. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm, namely, maximum-available-destination scheduling algorithm, is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible at
the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that the proposed heuristic algorithm produces lower mean packet delay than the greedy and no-partition scheduling algorithms.
Finally, the performance of the greedy scheduling algorithm and the no-partition scheduling algorithm are further studied. We show that the greedy scheduling algorithm may not always produce lower mean packet delay than the no-partition scheduling algorithm. The reason for this phenomenon is analyzed using several examples. The performance of a multicast scheduling algorithm may depend on the traffic conditions (e.g., the load, the maximum multicast group size, the percentage of unicast traffic, and etc.) and the availability of the channel resource in the network. A hybrid multicast scheduling algorithm that can produce good performance for wide ranges of the traffic conditions and the availability of
the channel resource in the network is proposed. Depending on the average utilizations of the data channels and the receivers, the proposed hybrid multicast scheduling algorithm dynamically chooses to employ a multicast scheduling algorithm which always tries to partition multicast transmissions or a multicast scheduling algorithm which does not partition multicast transmissions. Extensive simulations are performed to study the performance of the proposed hybrid algorithm. Our simulation results show that the proposed hybrid algorithm produces lower mean packet delay for wide ranges of the load, the maximum multicast group size, the percentage of unicast traffic, and the number of data channels in the network compared with a multicast scheduling algorithm which always tries to partition multicast transmissions and a multicast scheduling which does not partition multicast transmissions.

List of Figures
Introduction ............................1
1.1 Single-Hop WDM Networks . . . . 1
1.2 Motivation . . . . . . . . . . . . 3
1.3 Contributions . . . . . . . . . . 5
1.4 Thesis Organization . . . . . . . 7
2 Related Researches ..................8
2.1 Random-access based Multicast Scheduling Algorithms . . . . . .................8
2.2 Pre-allocation based Multicast Scheduling Algorithms . . . . . . 9
2.3 Reservation-based Multicast Scheduling Algorithms . . . . .. . . 10
3 System Models ....................12
4 Minimizing the Schedule Length .......15
4.1 System Operation . . . . . . . . 15
4.2 The Problem . . . . . . . . . .. 17
4.3 A Heuristic Scheduling Algorithm . . . . 19
4.4 Simulation and Results . . . . . . . . . .22
4.5 Summary . . . . . . . . . . . . . . . ..24
5 Minimizing the Number of Multicast Transmissions .......27
5.1 System Operation . . . . . . . .. 28
5.2 The Problem . . . . . . . . . . .. 28
5.3 A Heuristic Scheduling Algorithm . . . . 31
5.3.1 The Status Information . . . . . . .. . 32
5.3.2 The Maximum-Available-Destination Scheduling Algorithm . .33
5.3.3 The Greedy Scheduling Algorithm . . .35
5.3.4 The No-Partition Scheduling Algorithm . . .36
5.4 Simulation and Results . . . . . . . . . . 36
5.4.1 Simulation Model . . . . . . . . . . . . 36
5.4.2 Simulation Results . . . . . . . . . . 37
5.5 Summary . . . . . . . . . . . . .. . . . 40
6 A Hybrid Multicast Scheduling Algorithm .......43
6.1 System Operation . . . . . . 44
6.2 Partition versus No Partition of Multicast Transmissions . . 44
6.2.1 The Status Information . . . . 45
6.2.2 The Greedy Algorithm . . . . . .46
6.2.3 The No-Partition Algorithm. . . . . 48
6.2.4 Examples . . . . . . . . . . . .. . 49
6.3 Performance Comparison of the Greedy and No-Partition Algorithms . 52
6.4 The Proposed Hybrid Algorithm . . . . 58
6.5 Performance of the Proposed Hybrid Scheduling Algorithm . . . 62
6.6 Summary . . . . . 65
7 Conclusions and Future Works 70
Bibliography 73

[1] M. N. Ransom and D. R. Spears, ''''Applications of public gigabit networks," IEEE Network, pp.30-40, Mar. 1992.
[2] B. E. Carpenter, L. H. Landweber, and R. Tirler,"Where are we with gigabits ?" IEEE Network, pp.10-13, Mar. 1992, Guest Editorial.
[3] C. A. Brackett,"Dense wavelength division multiplexing networks: Principles and applications," IEEE J. Select Areas Commun., vol. 8, pp. 948-946 , Aug. 1990.
[4] P. R. Trischitta and W. C. Marra,"Applying WDM technology to undersea cable networks," IEEE Communication Magazine, pp. 62-66, Feb. 1998.
[5] M. S. Goodman, H. Kobrinski, M. P. Vecchi, R. M. Bulley, and J. L. Gimlett, The LAMBDANET multiwavelength networks: Architecture, applications, and demonstrations," IEEE J. Select Areas Commun., vol. 8, no. 6, pp. 995-1004, Aug. 1990.
[6] Microelectronic Center of North Carolina, Helios: Regional testbed optical access network for IP multicast and differentiated services, a DARPA NGI project, http://projects.anr.mcnc.org/Helios/
[7] E. Modiano,"Unscheduled multicasts in WDM broadcast-and-select networks," Proceedings of IEEE INFOCOM''98, San Francisco, U.S.A., , 1998, pp. 86-93.
[8] G. N. Rouskas and M. H. Ammar,"Analysis and optimization of transmission schedules for single-hop WDM networks," in Proc. IEEE INFOCOM''93, San Francisco, U.S.A., 1993, pp. 1342-1349.
[9] M. S. Borella and B. Mukherjee, Efficent scheduling of nonuniform packet traffic in a WDM/TDM local lightwave network with arbitrary transceiver tuning latencies, " IEEE Journal on Selected Areas in Communications, Vol. 14, No. 5, pp. 923-934, June 1996.
[10] G. N. Rouskas and M. H. Ammar,"Multidestination communication over tunable-receiver single-hop WDM networks," IEEE J. Select Areas Commun., vol. 15, no. 3, pp. 501-511, April 1997.
[11] W. Y. Tseng and S. Y. Kuo,"A Combinational media access protocol for multicast traffic in single-hop WDM LANs," in Proc. IEEE GLOBECOM''98, Sydney, Australia, 1998, pp. 1671-1676.
[12] F. Jia and B. Mukherjee, Variable-length message scheduling algorithms for a WDM based local lightwave network," in Proc. IEEE INFOCOM''94, Toronto, Canada, 1994, pp. 1362-1369.
[13] M. S. Borella and B. Mukherjee,"A reservation-based multicasting protocol for WDM local lightwave networks," in Proc. IEEE ICC''95, Seattle, U.S.A., 1995, pp. 1277-1281.
[14] F. Jia, B. Mukherjee, and J. Iness,"Scheduling variable-length message in a single-hop multichannel local lightwave network," IEEE/ACM Transactions on Networking, Vol.3, No. 4, pp. 477-487, Aug. 1995.
[15] K. M. Sivaraman and J. Wang,"Media access protocols for WDM with on-line scheduling, " IEEE Journal of Lightwave of Technology, Vol. 14, No. 6, pp. 1278-1286, June 1996.
[16] J. P. Jue and B. Mukherjee,"The advantages of partitioning multicast transmissions in a single-hop optical WDM network," in Proc. IEEE ICC''97, Montreal, Canada, 1997, pp. 427-431.
[17] J. S. Choi and H. H. Lee,"A dynamic wavelength allocation scheme with status information for fixed- and variable-length messages," in Proc. IEEE GLOBECOM''98, Sydney, Australia, 1998, pp.1593-1597.
[18] D. Guo, Y. Temini, and Z. Zhang,"Scalable high-speed protocols for WDM optical-star networks," in Proc. IEEE INFOCOM''94, Toronto, Canada, 1994, pp. 1544-1551.
[19] D. A. Levine, I. F. Akyildiz,"A reservation and collision-free media access protocol for optical star local area network," in Proc. IEEE GLOBECOM''94, San Francisco, U.S.A., 1994, pp. 567-571.
[20] R. Chipalkatti, and Z. Zhang,"A hybrid dynamic reservation protocol for an optical star network," in Proc. IEEE GLOBECOM''95, Singapore, 1995, pp. 998-1006.
[21] H. B. Jeon and C. K. Un,"Contention-based reservation protocols in multiwavelength optical networks with a passive star topology," IEEE Trans. On Commun., Vol. 43, pp. 2794-2802, Nov. 1995.
[22] K. M. Sivalingam and P. W. Dowd,"A lightweight media access protocol for WDM-based distributed shared memory system," in Proc. IEEE INFOCOM''96, San Francisco, 1996, pp.946-953.
[23] B. Hamidzadeh, M. Maode, and M. Hamdi,"Message sequencing techniques for on-line scheduling in WDM networks," in Proc. IEEE GLOBECOM''97, Phoenix, U.S.A., 1997, pp. 868-872.
[24] Z. Ortiz, G. N. Rouskas, and H. G. Perros,"Scheduling of multicast traffic in tunable-receiver WDM networks with non-negligible tuning latencies, " in Proc. ACM SIGCOMM''97, Cannes, France, 1997, pp. 301-310.
[25] G. N. Rouskas and V. Sivaraman,"Packet scheduling in broadcast WDM networks with arbitrary transceiver tuning latencies," IEEE/ACM Trans. On Networking, Vol. 5, No. 3, pp. 359-370, June 1997.
[26] V. Sivaraman and G. N. Rouskas,"HiPeR-l: A high performance reservation protocol with look-ahead for broadcast WDM networks," in Proc. IEEE INFCOM''97, Kobe, Japan, 1997, pp. 1272-1279.
[27] A. Smiljanic,"An Efficient channel access protocol for an optical star network," in Proc. IEEE ICC''98, Atlanta, U.S.A., 1998, pp. 514-519.
[28] M. Azizoglu, R. A. Barry, and A. Mokhtar,"Impact of tuning delay on the performance of bandwidth-limited optical broadcast networks with unicast traffic," IEEE Journal on Selected Areas in Communications, Vol. 14, No. 5, pp. 935-944, June 1996.
[29] X. Chen and J. F. Hayes,"Call scheduling in multicasting packet switching, "in Proc. IEEE ICC''92, Chicago, U.S.A., 1992, pp. 895-899.
[30] K. J. Schultz and P. G. Gulak,"Distributed multicast contention resolution using content addressable FIFOs, " in Proc. IEEE ICC''94, New Orleans, U.S.A., 1994, pp.1495-1500.
[31] B. Prabhakar, N. Mckeown, and R. Ahuja,"Multicast scheduling for input-queued switches, " IEEE Journal on Selected Areas in Communications, Vol. 15, No. 5, pp. 855-866, June 1997.
[32] W. T. Chen, C. F. Huang, Y. L. Chang, and W. Y. Hwang,"An efficient cell-scheduling algorithm for multicast ATM switching Systems, "IEEE/ACM Trans. on Netwoeking, vol. 8, No. 4, pp. 517-525, August 2000.
[33] M. R. Garey and D. S. Johnson, Computers and Intractability, San Francisco, CA: Freeman, 1979.
[34] B. Mukherjee,"WDM-Based Local Lightwave Networks { Part 1: Single-Hop Systems," IEEE Net. Mag., vol. 6, pp. 12-27, May 1992.
[35] G. N. M. Shdhakar, M. Kavehrad, and N. D. Georganas,"Access Protocols for Passive Optical Star Networks," Computer Networks and ISDN Systems, pp. 913-930, 1994.
[36] J. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, 1990 (Section 10.8)
[37] A. Burnetas, D. Solow, and R. Agrawal,"An Analysis and Implementation of an Efficient in-place Bucket Sort," Acta Informatica, 34, pp.687-700, 1997