臺灣博碩士論文加值系統

在一個任意來源端互動式多媒體服務應用中，例如：視訊會議，都需要多播網路的服務及較短的傳輸延遲。在目前既有的網際網路中，支援跨越廣域網路的網路層多播是不可能的。最近的焦點多集中在應用層多播。在過去，只有少數的學者探討具有Δ限制(Δconstrained)的應用層多播。本論文提出一個具有延遲限制及分支容量限制的多播擴張樹(Delay and Degree constrained Multicasting Spanning Tree(D2MST))演算法，以建立一個共用樹，使得大多數點對點的延遲都能符合延遲限制。D2MST使用網路中心及重心的概念，依據選擇適當的根節點價格函數”merit”，來開始多播樹的建置。並使用價格函數”power”選擇節點加入多播樹的優先順序。此外，一個具有最短路徑及分支容量限制的演算法(Shortest Path with Degree Constrained (SPDC))，使加入節點可透過已知節點連接到擴張樹，使得點對點之間的延遲能夠符合Δ限制的要求。由模擬結果顯示出D2MST能有效建立一個符合Δ限制的覆疊多播樹。

Any to any source interactive multimedia services, such as video conference, demand multicasting network services and short communicate delay among end points. As for present Internet, the support of network layer multicasting across WAN is impossible. Recent focus is thus mostly on the application layer multicasting. In the past, very few researchers probe into the field of application layer multicasting on Δ-constrained. This thesis proposes an algorithm called Delay and Degree constrained Multicast Spanning Tree (D2MST) to establish a shared tree that makes end to end delay among high percentage of nodes within Δ-constrained. D2MST uses a novel concept of network center and gravity, based on which a cost function “merit” is defined to choose an appropriate root to start the construction of multicasting tree. The other cost function “power” is used therefore to choose which node can enter the multicasting tree first. An algorithm called Shortest Path with Degree Constrained (SPDC) is also proposed to connect a given node to the spanning tree so that the delay between node and node can conform to the need of Δ-constrained. The simulation results show that D2MST performs well and can establish a Δ-constrained overlay multicasting tree effectively.

圖目錄....................................................... 2
表目錄....................................................... 3
1. 導論...................................................... 4
1.1. 研究動機與目的.......................................... 6
1.2. 研究範圍................................................ 8
1.3. 研究貢獻................................................ 8
1.4. 章節概要................................................ 8
2. 相關研究.................................................. 9
2.1. 代理器多播(Proxy Based Multicasting(PBM))............... 9
2.2. 端系統多播(End System Multicasting(ESM))................ 9
3. D2MST演算法....................................... 12
3.1. D2MST的架構.....................................12
3.2. D2MST拓樸形成................................... 13
3.2.1. 根節點的選擇.................................. 13
3.2.2. SPDC演算法.................................... 17
3.2.3. D2MST範例..................................... 20
4. 模擬與分析........................................ 21
4.1. 模擬環境........................................ 21
4.2. 模擬方法........................................ 22
4.3. 結果分析........................................ 22
4.3.1. 不同網路範圍的影響............................ 22
4.3.2. 參數組合的比較................................ 23
4.3.3. α、β、γ、Θ數值的分佈...................... 25
4.3.4. 個案研究...................................... 28
5. 結論與未來工作.................................... 33
參考論文............................................. 34

[1] Yang-hua Chu; S.G.Rao; S.Seshan and Zhang. Hui，”A Case for End System Multicast ，”IEEE JSAC on Volume 20，Issue 8，pp.1456—1471，2002.
[2] N.M.Malouch; Zhen Liu; D.Rubenstein and S.Sahu，”A Graph Theoretic Approach to Bounding Delay in Proxy-Assisted， End-System Multicast，”in proceedings of Quality of Service，Tenth IEEE International Workshop，pp.106-115，2002.
[3] J.Jannotti; D.Gifford; K.Johnson; F.Kaashoek and J.O’Toole，”Overcast:Reliable Multicasting with An Overlay Network，”in proceedings of USENIX OSDI，San Diego，CA，pp.197-212，2000.
[4] Y.Chawathe; S.McCanne and E.A.Brewer，”RMX: Reliable Multicast for Heterogeneous Networks，”in proceedings of IEEE INFOCOM，Volume 2，pp.795—804，2000.
[5] Suman Banerjee; Bobby Bhattacharjee; Christopher Kommareddy，”Scalable Application Layer Multicast，”in proceedings of conference on Applications， technologies， architectures， and protocols for computer communications，pp.205-217，2002.
[6] S.Banerjee; C.Kommareddy; K.Kar; B.Bhattacharjee and S.Khuller，”Construction of An Efficient Overlay Multicast Infrastructure for Real-Time Applications，”IEEE INFOCOM ，Volume 2， pp.1521-1531，2003.
[7] RenJie Pi; JunDe Song and Li Jiong Hong，”Application Level Multicast In hierarchical Topology，”in proceedings of IEEE CCECE ，Volume 2，pp.805—808，2003.
[8] Wenjie Wang; David Helder; Sugih Jamin and Lixia Zhang， "Overlay Optimizations for End-Host Multicast，"in proceedings of Fourth International Workshop on Networked Group Communication (NGC)，pp.154-161.2002.
[9] Xiaohua Jia ，”A Distributed Algorithm of Delay-Bounded Multicast Routing for Multimedia Applications in Wide Area Networks，”IEEE/ACM Transactions Networking on ，Volume 6，Issue 6，pp.828—837，1998.
[10] D.Pendarakis; S.Shi; D.Verma and M.Waldvogel，“ALMI: An Application Level Multicast Infrastructure，”in proceedings of 3rd Usenix Symposium on Internet Technologies & Systems ，pp.49-60，2001.
[11] J.Saltzer; D.Reed and D.Clark，“End-to-end Arguments in System Design，”ACM Trans on，Comput.System，Volume 2，pp.195—206，1984.
[12] R.S.Cahn，Wide Area Network Design Concepts and Tools for Optimization，Morgan Kaufmann Publishers.
[13] T.S.Eugene Ng and Hui Zhang，”Towards Global Network Positioning，”in proceedings of the First ACM SIGCOMM Workshop on Internet Measurement citation， San Francisco， California， USA ，pp.25-29，2001.
[14] M.Draoli; M Lancia and A.Laureti-Palma，”Video Conference on a LAN/MAN Interconnected System: QoS Evaluation，”Computer Communications and Networks，in proceedings of Fourth International Conference pp.170—177，1995.
[15] L.Pierucci and Enrico Del Re，”An Interactive Multimedia Satellite Telemedicine Service，”IEEE Multimedia，Volume 7，Issue 2，pp.76—83，2000.
[16] M.Parsa;Qing Zhu and J.J.Garcia-Luna-Aceves，”An Interative Algorithm for Delay- Constrained Minimum-Cost Multicasting，”IEEE/ACM Transactions on Networking， Volume 6，Issue 4，pp.461- 474，1998.
[17] Guozhen Tan; Xiaojun Han and Yilin Zhao;”Approximate Shortest Path Algorithms for Network-Tree Model，”in proceedings of Intelligent Transportation Systems， IEEE ，Volume 2，pp.1263-1268， 2003.
[18] H.Zhou，”Efficient Steiner Tree Construction Based on Spanning Graphs，”IEEE Transactions on Computer -Aided Design of Integrated Circuits and Systems，Volume 23，Issue 5，pp.704—710，2004.
[19] Li Yi Lin; Yi Yu Liu and Ting Ting Hwang，”Construction of Minimal Delay Steiner Tree Using Two-Pole Delay Model，”in proceedings of ASP-DAC 2001，Asia and South Pacific，pp.126-131，2001.
[20] G.Grewal; T.Wilson; M.Xu and D.Banerji，”Shrubbery: A New Algorithm for Quickly Growing High-Quality Steiner Trees，”in proceedings of VLSI Design，17th International Conference on，pp.855—862，2004.
[21] J.Knowles; D.Corne，”A New Evolutionary Approach to The Degree-Constrained Minimum Spanning Tree Problem，”IEEE Transactions on Evolutionary Computation，Volume 4，Issue 2，pp.125-134，2000.
[22] Raidl， G.R，”An Efficient Evolutionary Algorithm for The Degree-Constrained Minimum Spanning Tree Problem，” in proceedings of Congress on Evolutionary Computation，Volume 1，pp.104-111，2000.