臺灣博碩士論文加值系統

在本論文中，我們討論排程問題在使用管線傳輸的分時分波多工圓形網路上。其中，任意兩個節點都必須建立連線。我們假設每個節點上只有一個可調式的傳送端與一個固定式的接收端，並且考慮波長調整時間與傳送延遲時間。每個節點都要傳送一個唯一的封包給其他所有節點。我們的目標是用最少的時間單位來完成所成工作。在這篇論文中，我們說明如何將排程問題用0與1整數規劃的公式來表示。另外，我們也提出三種近似演算來解這個問題。

In this thesis, we focus on the scheduling problem for All-to-All Personalized Communication(AAPC) pipeline transmissions in unidirectional TWDM TT-FR rings. We assume that each node has only one TT-FR(fully tunable transmitter and fixed receiver) pair, and tuning latency and propagation delay are considered. Each node has to send a unique packet to each of the other nodes. The objective is to minimize the number of time slots required to accomplish all tasks. In this thesis, we show how to formulate the scheduling problem as a 0/1 integer linear programming(ILP). Three heuristic algorithms are also proposed to solve this problem.

1 Introduction…………………………………………………………1
1.1 Overview…………………………………………………………1
1.2 AAPC………………………………………………………………1
1.3 Goals ……………………………………………………………2
1.4 Outline of this thesis………………………………………2
2 System Description ………………………………………………4
2.1 System Model …………………………………………………4
2.2 Pipeline Transmission ………………………………………6
2.3 Schedule Period ………………………………………………7
3 Formulation …………………………………………………………8
3.1 Notations ………………………………………………………8
3.2 Integer Linear Programming…………………………………8
3.3 Obtaining an Optimal Solution ………………………13
4 Collisions and Virtual Topology ……………………………16
4.1 Overview ………………………………………………………16
4.2 Avoiding collisions…………………………………………16
4.3 Virtual Topology ……………………………………………19
5 The Heuristic Algorithms ………………………………………20
5.1 Longest First ………………………………………………21
5.2 Same Group First …………………………………………23
5.3 Double Sort …………………………………………………25
5.4 Simulation Result……………………………………………27
6 Conclusion …………………………………………………………29

[1] K. H. Liu, B. J. Wilson, and J. Y. Wei ``A scheduling
application for WDM optical networks," IEEE J. Select.
Area Commun., vol. 18, no. 10, pp. 2041-2050, 2000
[2] R. Ramaswami, ``Multi-wavelength lightwave networks
for computer communication,"IEEE Communications
Magazine, vol.31, pp.78-88, 1993
[3] H. S Choi, H.-A Choi,and M. Azizoglu, ``Optimum
transmission scheduling in optical broadcast
networks," In Proc.Int'l Conference on Communication,
pp.266-270, 1995
[4] G. Pieris and G. Sasaki, ``Scheduling transmissions in WDM
broadcast-and-select networks,"IEEE/ACM Transaction on
Networking, 2(2):105-110, 1994
[5] X. J Zhang, C. M. Qiao, ``Pipelined transmission
scheduling in all-optical TDM/WDM rings Computer
Communications and Networks," 1997. Proceedings.,
Sixth International Conference on, pp: 144 -149, 1997
[6] X. J. Zhang ,C. M. Qiao, ``On scheduling all-to-all
personalized connection and cost-effective designs in
WDM rings Networking," IEEE/ACM Transactions on,
pp.435-445, 1999
[7] A. Elrefaie, ``Multiwavelength survivable ring network
architectures," In Proc.Int'l Conference on
Communication, pp. 1245-1251, 1993
[8] S. Hinrichs, C. Kosak, D. R. O'Hallaron, T.M. Stricker,and
R.Take, ``An architecture for optimal all-to-all
personalized communication," In proc.Sixth Annual ACM
Symposium on Parallel Algorithms and Architecture
(SPAA), pp. 310-319, 1994
[9] L. Tassiulas and J. Joung, ``Performance measures and
scheduling policies in ring networks," IEEE/ACM
Transaction on Networking, pp.576-584, 1995
[10] G. N. Rouskas and V. Sivaraman, ``Packet scheduling in
broadcast WDM networks with arbitrary tuning
latencies," IEEE/ACM Trans. Networking, vol. 5,
pp. 359-370, 1997
[11] T. H. Lee, Lee,K., ``Optimal routing and wavelength
assignment in WDM ring networks," Sungsoo Park
Selected Areas in Communications, IEEE Journal
on, pp. 2146 -2154, 2000
[12] C. Law, and K.Y. Siu,``Online routing and wavelength
assignment in single-hub WDM rings Selected Areas in
Communications," IEEE Journal on, pp.
2111 -2122, 2000
[13] A. Sneh, K.M. Johnson,``High-Speed Tunable Liquid
Crystal Optical Filter for WDM Systems," IEEE/
LEOS, $pp. 3_59-3_60$, 1994
[14] D. A. Smith et al., ``Evolution of Acousto-Optic
Wavelength Routing Switch," IEEE/OSA Journal of
Lightwave Technology,v.14,n.6 pp.1005-1119,1996