臺灣博碩士論文加值系統

現今電腦網路的發展日新月異，電腦網路多播路徑選擇法的應用日益增加，利用電腦網路多播路徑選擇法的傳輸應用也趨多元性。針對不同的電腦網路應用，應該考慮到的電腦網路多播路徑選擇法的特性也應該有所不同，目前有關多播路徑選擇問題之研究，大部份的焦點都放在使電腦網路頻寬使用效率最佳化，即使用最少的頻寬來傳送資料。在如此的考慮下，多播群組目的節點之間資料接收時間差異常常無法預期，這對很多的電腦網路應用是相當要命的，例如，在一些分散式的資料庫系統中，各資料庫間的資料版本將產生不一致性。
因此本篇論文我們所要研究的主題是放在傳輸延遲上，如何在點對點延遲限制條件下，使目的節點之間的傳輸延遲差異降到最低。在這篇論文中，分析了延遲差異限制之多播路徑選擇問題和單一延遲網路之延遲差異限制之多播路徑選擇問題，提供另外一個延遲差異限制之多播路徑選擇問題是NP-完全性問題的證明，並且證明了單一延遲網路之延遲差異限制之多播路徑選擇問題是NP-完全性問題，以及為延遲差異限制之多播路徑選擇問題和單一延遲網路之延遲差異限制之多播路徑選擇問題找出一個誤差在最佳解  倍之內的近似解的問題都是NP-完全性問題，接著我們提出了一個啟發式演算法，並以電腦模擬結果證明它具有不錯的延遲效能和時間效率。
本論文之主要架構如下：在第一章，我們先初步介紹多播和延遲種類，並提出我們的研究題目和主要成果。在第二章，我們回顧目前關於多播延遲相關之文獻，並討論這些研究的優缺點。在第三章，我們將討論在一般電腦網路架構下之延遲差異限制之多播路徑選擇問題，包括電腦網路模型、問題描述、問題複雜度等。在第四章，我們將討論在單一延遲網路之延遲差異限制之多播路徑選擇問題，包括電腦網路模型、問題描述、問題複雜度等。在第五章，我們將針對延遲差異限制之多播路徑選擇問題提出一個啟發式的演算法DVCA，並且分析它的時間複雜度。在第六章，我們將使用電腦實驗模擬的方式，比較最短路徑樹、最小擴張樹、Steiner Tree、DVMA和DVCA在延遲、延遲差異和執行時間之優缺點。最後，在第七章，我們把所有的研究和討論做了一個結論，指出我們主要貢獻，並且建議一些和本論文相關的未來研究方向。

Today's computer networks are changing day by day. Many computer network applications use multicast routing to send messages. As a result, numerous computer network routing protocols have continuously been presented and update. With different computer network applications, we should consider different qualities of computer network routing protocols. One of the most frequently considered optimization objectives is to minimize the total cost of the multicast tree, which is taken as the sum of the costs on the links of the multicast tree. Under such a situation, the multicast tree is usually found to fail to guarantee the delay variations among the delays along the individual source-destination paths. This is a fatal problem in many computer network applications. In a distributed database system, for example, minimizing the delay variation will minimize the length of time during which the database is in an inconsistent state. Therefore, our purpose in this thesis is to study the effect of transmission delay of multicast routing. We study on the issue of minimum delay variation with end-to-end delay constrained multicast routing problem, to find a multicast tree with minimum delay variation under an end-to-end delay constraint.
In this thesis, we discuss the problem of multicast routing with delay variation constraints for both normal computer networks and unit delay computer networks. We provide another proof to show that the problem of multicast routing with delay variation constraints for normal computer networks is NP-complete. We prove the problem of multicast routing with delay variation constraints for unit delay computer networks to be NP-complete. Furthermore, we discover that finding approximation algorithms on multicast routing with delay variation constraints for normal computer networks and for unit delay computer networks are both NP-complete. A heuristic algorithm with low time complexity is presented to solve the problem of multicast routing with delay variation constraints. Experimental results demonstrate that our heuristic algorithm has good performance in terms of delay, delay variance and running time in most cases.
The thesis is arranged as follows. In Section 1, we introduce several kinds of multicasting and delay and demonstrate our subjects and achievements. In Section 2, we review the relevant documents and discuss their advantages and disadvantages. In Section 3, we address the problem of multicast routing with delay variation constraints for normal computer networks, including the computer network model, problem description, and complexity of the problem. In Section 4, we discuss that the problem of multicast routing with delay variation constraints for unit delay computer networks, including the computer network model, problem description, and complexity of the problem. In Section 5, we present a heuristic which is named Delay Variation Constraints Algorithm (DVCA) to solve the problem of multicast routing with delay variation constrains, and analyze the time complexity of DVCA. In Section 6, computer simulations foe evaluating the algorithm are preformed. We also compare with Shortest Path Tree, Minimum Spanning Tree, Steiner Tree, DVMA and DVCA in terms of delay, delay variations and running time. Finally, we summarize our discussions and highlight our main contributions. Several related research topics will also be suggested.

中文摘要 i
英文摘要 iii
目錄 v
圖表目錄 viii
誌謝 x
第一章 導論 1
1.1 多點通訊 1
1.1.1 單一傳輸之多點通訊 1
1.1.2 廣播傳輸之多點通訊 2
1.1.3 多播傳輸之多點通訊 2
1.2 多播路徑選擇通訊協定 3
1.3 多播樹 3
1.4 延遲問題 4
1.4.1 點對點延遲限制 4
1.4.2 延遲差異限制 6
1.5 研究之問題與主要成果 7
1.6 文章之組織 9
第二章 相關文獻回顧 10
2.1 最小成本之多播樹 10
2.2 Core Based Tree 之多播樹 10
2.3 點對點延遲限制之多播樹 10
2.4 延遲差異限制之多播樹 11
2.5 點對點延遲限制並延遲差異限制之多播樹 12
第三章 延遲差異限制之多播路徑選擇問題 13
3.1 一些相關之符號與定義 13
3.2 延遲差異限制之多播路徑選擇問題之描述 14
3.3 延遲差異限制之多播路徑選擇問題之複雜度 15
3.4 延遲差異限制之多播路徑選擇問題之近似解之複雜度 19
第四章 單一延遲網路之延遲差異限制之多播路徑選擇 23
4.1 單一延遲網路之延遲差異限制之多播路徑選擇問題之定義 23
4.2 單一延遲網路之延遲差異限制之多播路徑選擇問題之複雜度 24
4.3 單一延遲網路之延遲差異限制之多播路徑選擇問題近似解之複雜度27
第五章 一個快速且有效的啟發式演算法：DVCA 31
5.1 DVCA的基本想法 31
5.2 DVCA的正式描述 32
5.3 DVCA的時間複雜度 36
5.4 DVCA之討論 36
5.4.1 封包傳送路徑之選擇與延遲之計算 36
5.4.2 多播樹的存在與否 38
5.5 DVCA和DVMA之時間複雜度比較 38
第六章 電腦模擬 40
6.1 電腦網路模型 40
6.2 延遲差異 40
6.3 點對點延遲 43
6.4 平均延遲 46
6.5 程式執行時間 49
第七章 結論與未來研究方向 53
7.1 結論與主要貢獻 53
7.2 未來研究方向 53
附錄A：啟發式演算法DVMA 55
附錄B：參考文獻 57

[1] A. Ballardie, "Core Based Tree (CBT) Multicast Routing Architecture," Internet RFC 2201, Sept. 1996.
[2] A. I. Erzin and S. H. Kim, "Polynomial Algorithm for Min-Cost Delay-Constrained Multicasting Routing Problem in Networks," ICICS'97 Sept. 1997.
[3] A. Shaikh, K. Shin, "Destination-Driven Routing for Low-Cost Multicast," IEEE Journal on Selected Areas in Communications, Apr. 1997.
[4] B. K. Kadaba and J. M. Jaffe, "Routing to Multiple Destinations in Computer Networks," IEEE Trans. Commun., vol. COM-31, no. 3, pp. 343-351, Mar. 1983.
[5] B. W. Waxman, "Routing of Multipoint Connections," IEEE J. Select. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.
[6] C. H. Chow, "On Multicast Path Finding Algorithms," in Proc. IEEE INFOCOM '91, pp. 1274-1283, 1991.
[7] Dave Kosiur, IP Multicasting: The Complete Guide to Interactive Corporate Networks. Wiley Computer Publishing, 1998.
[8] E. Lawler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1776.
[9] E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, vol. 1, pp. 269-271, 1959.
[10] F. K. Hwang and D. S. Richards, "Steiner Tree Problems," Networks, vol. 22, pp.55-89, 1992.
[11] F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem., Elsevier Science Publishers B. V., 1992.
[12] G. H. Lin and G. Xue, "Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-length," Information Processing Letters, vol.69, pp. 53-57, 1999.
[13] G. Kumar, N. Narang and C. P. Ravikumar, "Efficient Algorithms for Delay-bounded Minimum Cost Path Problem in Communication Networks," IEEE High Performance Computing, pp. 141-146, Dec. 1998.
[14] G. N. Rouskas and I. Baldine, "Multicast Routing with End-to-end Delay and Delay Variation Constraints," IEEE Journal on Selection Areas in Communications, vol. 15, no. 3, pp. 346-356, Apr. 1997.
[15] H. C. Lin and S. C. Lai, "Core Placement for Core Based Tree Multicast Routing Architecture," GLOBECOM '98, pp. 1999-2003, 1998.
[16] H. Schulzrinne, A. Rao and R. Lanphier, "Real Time Streaming Protocol (RTSP)," RFC 2326, Apr. 1998.
[17] H. Schulzrinne, S. Casner, R. Frederick and V. Jacobson, "RTP: A Transport Protocol for Real-time Applications," RFC 1889, Audio-Video Transport Working Group, Jan. 1996.
[18] L. Kou, G. Markowsky and L. Berman, "A Fast Algorithm for Steiner Trees," Acta Informatica, vol. 15, pp. 141-145, 1981.
[19] M. Parsa and J. J. Garcia-Luna-Aceves, "A Protocol for Scalable Loop-free Multicast Routing," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 316-331, Apr. 1997.
[20] M. R. Garey and D. S. Johson, Computers and Intractability: A Guide to the Theory of NP-completeness, New York, NY: Freeman, 1979.
[21] P. Winter, "Steiner Problem in networks: A Survey," Networks, vol. 17, pp. 129-167, 1987.
[22] P. Winter and J. M. Simth, "Path-Distance Heuristics for the Steiner Problem in Undirected Networks," Algorithmica, pp. 309-327, 1992.
[23] Q. Sun and H. Langendorfer, "An Efficient Delay-constrained Multicast Routing Algorithm," Journal of High Speed Networks, vol. 7, pp. 43-55, 1998.
[24] Q. Zhu, M. Parsa and J. J. Garcia-Luna-Aceves, "A Source-based Algorithm for Delay-constrained Minimum-cost Multicasting," in Proc. IEEE Infocom '95, pp. 377-385, Mar. 1995.
[25] R. M. Karp, "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York, NY: Plenum, pp. 85-103, 1972.
[26] R. Prim, "Shortest Connection Networks and Some Generalizations," Bell Systems Tech. J., vol. 36, pp. 1389-1401, 1957.
[27] S. L. Hakimi, "Steiner's Problem in Graphs and Its Implications," Networks, vol. 1, pp. 113-133, 1971.
[28] S. Paul, K. K. Sabnani, J. C. Lin and S. Bhattacharyya, "Reliable Multicast Transport Protocol," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 407-421, Apr. 1997.
[29] V. P. Kompella, J. C. Pasquale and G. C. Polyzos, "Multicast Routing for Multimedia Communication," IEEE/ACM Trans. Networking, vol. 1, no.3, pp. 286-292, Jun. 1993.
[30] W. Fenner, "Internet Group Management Protocol (IGMP)," RFC 2236, Version 2, Nov. 1997.
[31] X. Jia, N. Pissinou and K. Makki, "A Distributed Algorithm of Delay Bounded Multicast Routing for Multimedia Applications," IEEE Computer Communications and Networks, pp. 208-213, Sept. 1997.