臺灣博碩士論文加值系統

因為電子看板有著多彩多姿的多媒體影音表現，且具有多元性、地理性、即時性、分眾性及存在性等等的優點，使其在各項調查中，被預告為未來廣告的主要趨勢。而針對多媒體電子廣告經由網路傳播的特性，將會有傳送大量資料、依地區派送不同的電子廣告等等的特性，針對這些需求，我們提出一種以多重路徑，多種子的傳送方法來適用於多媒體電子廣告的傳送。

在多媒體播放端點所構成的網路拓樸中，首先依據區域性形成網路叢集，這樣就可以依據各叢集的地區特性，決定要分送到該叢集內的電子廣告；我們再利用BitTorrent 生成種子的觀念，將整體多媒體電子廣告分割成眾多的種子。

同時，本論文採用Guoliang Xue 所提出的最佳多重路徑選擇演算法(Optimal multi-path routing)，設計一個具有多個多重路徑的peer-to-peer-like 架構；再把眾多的種子分散到叢集內的各個端點上，以期利用各端點的頻寬，來完成種子的再次傳送，以達成各個端點上都有整體的多媒體電子廣告之目的。

本論文所建構的方法實作於一個商用系統的子系統中，以實際的環境來驗證可行性；並且利用國立交通大學的網路與系統實驗室所開發出來的NCTUns(網路模擬器)來模擬不同端點數目、資料量時的傳輸情況，以期驗證本論文所提出方法之可使用於不同建構參數和傳送情況。

With the fact that digital signage are characterized for the variable and abundant multimedia visual and audio expressions and exhibit advantages of multiplicity, locality, real-time, segmentation, and existence, they have been predicted to emerge as the major trend in the future advertising in various surveys. Focused on the characteristics of disseminating the multimedia electronic advertisements through the network, there will be an enormous amount of data transmitted and various electronic advertising distributed in accordance with the regions. To specifically address these needs, we will propose a multi-path, multi-seed dissemination approach suitable for the delivery of the multimedia electronic advertisements.

Within a peer-to-peer network structure, the network cluster will be first formed in accordance with the locality. Based on each cluster’s locality, the electronic advertisements designated for dissemination into a specific cluster can then be determined. We then apply the seed concept formed by BitTorrent to segment the entire multimedia electronic advertisement into myriad seeds. At the same time, this thesis adopts the Optimal Multi-Path Routing proposed by Guoliang Xue to design a peer-to-peer-like multiple multi-path framework, followed by the distribution of myriad seeds into each node within the cluster. Each node’s bandwidth will also be utilized to complete the re-transmission of the multimedia electronic advertisement for achieving the objective of establishing multimedia electronic advertisement on each node.

The approach established in this thesis will be factually applied in the sub-system of a commercial system for verifying the feasibility under the real environment. Further, the NCTUns developed by National Chiao Tung University’s network and system laboratory will then be utilized to simulate the transmission status for variable number of node , in the hope of verifying that the approach proposed by this thesis can be applied to different set-up parameters and data volume.

中文提要 ………………………………………………………………… i
英文提要 ………………………………………………………………… ii
誌謝 ………………………………………………………………… vi
目錄 ………………………………………………………………… vii
表目錄 ………………………………………………………………… ix
圖目錄 ………………………………………………………………… x
一、 緒論…………………………………………………………… 1
1.1 電子看板已成為未來趨勢…………………………………… 1
1.1.1 統計資料…………………………………………………… 1
1.2 電子看板的特性及優勢……………………………………… 2
1.3 研究動機和目的…………………………………………… 4
1.4 論文架構……………………………………………………… 6
二、 背景知識……………………………………………………… 7
2.1 網路圖形定義………………………………………………… 7
2.2 網路傳送的相關因素………………………………………… 8
2.3 相關的研究…………………………………………………… 9
2.3.1 單一路徑法…………………………………………………… 10
2.3.2 多重路徑法…………………………………………………… 11
2.4 簡單的範例.…………………………………………………… 12
2.4.1 單路徑傳送…………………………………………………… 13
2.4.2 多重路徑傳送………………………………………………… 16
2.4.3 單一路徑法和多重路徑法的比較…………………………… 18
2.5 點對點應用(Peer to Peer Application)…………………… 19
2.5.1 主從式傳輸（Client and Server）架構………………… 19
2.5.2 第一代點對點傳輸架構……………………………………… 20
2.5.3 第二代點對點傳輸架構……………………………………… 21
2.5.4 第三代點對點傳輸架構……………………………………… 23
2.5.5 Bittorrent點對點網路傳輸架構…………………………… 25
2.6 小結…………………………………………………………… 28
三、 利用多重路徑、多種子傳送大量多媒體電子廣告的方法…… 29
3.1 系統概觀……………………………………………………… 29
3.2 邏輯拓樸……………………………………………………… 30
3.3.1 多重路徑的拓樸設計………………………………………… 31
3.3 系統架構……………………………………………………… 32
3.3.1 分享檔案管理元件( Share Data Manager) ……………… 32
3.3.2 資料傳輸管理元件(Transmission Manager) ……………… 34
3.3.3 訊息管理元件(Message Manager) ………………………… 34
3.3.4 一個範例……………………………………………………… 35
3.4 分割種子……………………………………………………… 40
3.4.1 資料內容大小………………………………………………… 40
3.4.2 單一路徑派送………………………………………………… 40
3.4.3 多重路徑派送………………………………………………… 40
四、 實驗…………………………………………………………… 42
4.1 模擬計劃……………………………………………………… 43
4.1.2 使用NCTUns 建立拓樸……………………………………… 43
4.2 模擬結果……………………………………………………… 44
4.2.1 單一路徑傳送模擬結果……………………………………… 44
4.2.2 多重路徑、多種子方法傳送的模擬結果…………………… 46
4.2.3 結果分析……………………………………………………… 48
五、 結論及未來研究方向………………………………………… 50
5.1 結論…………………………………………………………… 50
5.2 未來研究方向………………………………………………… 51
六、 參考文獻……………………………………………………… 52

1. Bezjian-Avery, A., B. Calder and D. Iacobucci, New media interactive advertising vs. traditional advertising, Journal of Advertising Research, Vol. 38, No. 4 (July), pp. 23-32,1998.
2. Jeff Sauer. Picture This: Digital Signage, Sound & Video Contractor, P20-22, 2004.
3. Sanju Khatri, Digital-signage market generates new opportunities, iSuppli/Stanford Resources, 2004.
4. Sanju Khatri, Dynamic Digital Signage Captures InfoComm’s Attention: Market Expected to Grow to US$1.2 Billion in 2007, iSuppli/Stanford Resources, 2003.
5. Matthew Tullman, Ready For Take Off -Getting Beyond The Pilot In Dynamic Digital Signage, Systems Contractor News New York, P 62. , 2004.
6. Robert W Rycroft, Don E Kash.. Managing complex networks--key to 21st century innovation success, Research Technology Management, Washington: May/Jun 1999. Vol. 42, Iss. 3; p. 13, 1999.
7. Marianne Wilson, Signage Goes Digital, Chain Store Age, P75-76, 2004.
8. Y.L. Chen and Y.H Chin, The quickest path problem, Comput. Oper. Res. 17,153-161,1990.
9. J.B. Rosen, S.-Z. Sun and G. -L. Xue, ALGORITHMS FOR THE QUICKEST PATH PROBLEM AND THE ENUMERATION OF QUICKEST PATHS, Computers Ops Res. Vol. 18, No.6, pp.579-584,1991.
10. Y.L. Chen, Finding the k quickest simple paths in a network, Information Processing Letters 50, 89-92, 1994.
11. Y.L. Chen, AN ALGORITHM FOR FINDING THE k QUICKEST PATHS IN A NETWORK, Computer Ops Res. Vol. 20, No. 1, pp. 59-65, 1993.
12. Guoliang Xue, Optimal Multi-Path End-to-End Data Transmission in Networks, IEEE, 2000.
13. M.L. Fredman and R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J.ACM., Vol.34, pp. 596-615, 1987.
14. N Doe and C-Y Pang, Shortest-path algorithms : taxonomy and annotation. Networks, Vol.14, pp.275-323, 1984.
15. R.K. Ahuja, Minimum cost-reliability ratio problem, Computers and Operations Research, Vol. 16, pp.83-89, 1988.
16. T. C. Hu, The Maximum Capacity Route Problem, Operations Research, Vol. 9, No. 6, pp. 898-900, 1961
17. Ernesto de Queiros Vieira Martins, Jose Luis Esteves dos Santos, An algorithm for the quickest path problem. Operations Research Letters 20, pp. 195-198, 1997.
18. Guo-Liang Xue, Shang-Zhi Sun, J.Ben Rosen, Minimum Time Message Transmission in Networks, IEEE, 1992.
19. Guoliang Xue, Hsangzhi Sun, J.Ben Rosen, Fast data transmission and maximal dynamic flow, Information Processing Letters 66, pp. 127-132, 1998.
20. G. White, E. Fisch, U. Pooch, Computer System and Network Security, CRC Press, Inc., 1996.
21. Kalogeraki, V., Chen, F., Managing distributed objects in peer-to-peer systems, Network, Vol. 18, pp. 22-29, 2004.
22. A. Crespo and H. Garcia-Molina, Routing Indices For Peer-to -Peer Systems, In Proceedings of the 22nd International Conference on Distributed Systems, pages 23--32, Vienna, Austria, 2002.
23. I. Ivkovic, Improving Gnutella Protocol: Protocol Analysis and Research Proposals, Computer Networking Group Seminar Series, University of Waterloo, November 2001.
24. M. Ripeanu, I. Foster, and A. Iamnitchi, Mapping the Gnutella Network: Properties of Large-Scale Peer-To-Peer Systems and Implications for System Design, IEEE Internet Computing, Vol. 6, No. 1, pp.50-57, January-February 2002.
25. Choi Y, Park D, Associativity based clustering and query stride for on-demand routing protocols in ad hoc networks, JOURNAL OF COMMUNICATIONS AND NETWORKS 4 (1): 4-13 MAR 2002
26. Liang J, Kumar R, Ross KW, The FastTrack overlay: A measurement study, COMPUTER NETWORKS 50 (6): 842-858 APR 13 2006.
27. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, ACM SIGCOMM 2001, San Deigo, CA, pp. 149-160, August 2001.
28. Pastry : A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001
29. Izal M, Urvoy-Keller G, Biersack EW, Felber PA, Al Hamra A, Garces-Erice L, Dissecting BitTorrent: Five months in a torrent's lifetime, PASSIVE AND ACTIVE NETWORK MEASUREMENT LECTURE NOTES IN COMPUTER SCIENCE 3015: 1-11 2004
30. Ziqian Liu, Student Member, IEEE, and Changjia Chen, Senior Member, IEEE, Modeling BitTorrent-like Peer-to-Peer Systems, IEEE COMMUNICATIONS LETTERS, VOL. 10, NO. 7, JULY 2006
31. 鄭宏揚，點對點多重路徑網路之最佳化分析，義守大學資訊工程研究所，2003。
32. 陳積弘，DLC：可擴展式點對點查詢與資料分享架構，交通大學資訊工程研究所，2005。