請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65894完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林永松(Frank Yeong-Sung Lin) | |
| dc.contributor.author | Yang-Che Su | en |
| dc.contributor.author | 蘇揚哲 | zh_TW |
| dc.date.accessioned | 2021-06-17T00:14:45Z | - |
| dc.date.available | 2023-02-19 | |
| dc.date.copyright | 2020-02-19 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-02-13 | |
| dc.identifier.citation | M. Castro, M. B. Jones, A. M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman, 'An Evaluation of Scalable Application-Level Multicast Built Using Peer-To-Peer Overlays,' in Proc. IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, March 2003, pp. 1510-1520.
M. F. M. Firdhous, 'Multicasting over Overlay Networks - A Critical Review,' International Journal of Advanced Computer Science and Applications, vol. 2, no. 3, March 2011, pp. 54-61. Z. Li and A. J. Yu, 'A Hybrid Routing Algorithm based on Overlay Network for Wireless Ad Hoc Network,' in Proc. 2012 International Conference on Industrial Control and Electronics Engineering (ICICEE), Xi'an, China, August 2012, pp. 1138-1141. Y. Qin, X. Zhou, and H. Tang, 'A Cross-Transmission Protocol Architecture Concept for Resource Discovery in P2P Overlay Networks,' in Proc. 2009 WRI World Congress on Software Engineering (WCSE), Xiamen, China, May 2009, pp. 134- 137. R. K. Sitaraman, M. Kasbekar, W. Lichtenstein, and M. Jain, 'Overlay Networks: An Akamai Perspective,' Advanced Content Delivery, Streaming, and Cloud Services, pp.305-328, September 2014. M. Curado and E. Monteiro, 'A Survey of QoS Routing Algorithms,' in Proc. 2004 International Conference on Information Technology (ICIT), Istanbul, Turkey, December 2004, pp. 43-46. Y. S. Yen, H. C. Chao, R. S. Chang, and A. Vasilakos, 'Flooding-limited and Multi- constrained QoS Multicast Routing Based on The Genetic Algorithm for MANETs,' Mathematical and Computer Modelling, vol. 53, no. 11, pp. 2238-2250, June 2011. F. Y. S. Lin, C. H. Hsiao, H. H. Yen, and Y. J. Hsieh, 'A Near-Optimal Distributed QoS Constrained Routing Algorithm for Multichannel Wireless Sensor Networks,' Sensors, vol. 13, no. 12, pp. 16424–16450, December 2013. X. Gu, K. Nahrstedt, R. N. Chang and Z. Y. Shae, 'An overlay based QoS-aware voice-over-IP conferencing system,' in Proc. 2004 IEEE International Conference on Multimedia and Expo (ICME), Taipei, Taiwan, June 2004, pp. 2111-2114. C. Decker and R. Wattenhofer, 'Information Propagation in the Bitcoin Network,' in Proc. 2013 IEEE International Conference on Peer-to-Peer Computing (IEEE P2P), Trento, Italy, September 2013, pp. 1-10. D. Kim, E. Kim and C. Lee, 'Efficient peer-to-peer overlay networks for mobile IPTV services,' IEEE Transactions on Consumer Electronics, vol. 56, no. 4, pp. 2303-2309, November 2010. S. El-Ansary, L. O. Alima, P. Brand, and S. Haridi. 'Efficient Broadcast in Structured P2P Networks,' in Proc. 2003 International Workshop on Peer-to-Peer Systems (IPTPS), Berkeley, USA, February 2003, pp. 304-314. B. Sun, S. Pi, C. Gui, Y. Zeng, B. Yan, W. Wang, and Q. Qin, 'Multiple Constraints QoS Multicast Routing Optimization Algorithm in MANET Based on GA,' Progress in Natural Science, vol. 18, no. 3, pp. 331-336, March 2008. D. Li, N. Xiao, and X. Lu, “Topology and resource discovery in Peer-to-Peer overlay networks,” in Proc. 2004 International Conference on Grid and Cooperative Computing (GCC), Wuhan, China, October 2004, pp. 221-228. R. C. Chalmers and K. C. Almeroth, “On the Topology of Multicast Trees,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 153-165, February 2003. H. H. Yen and F. Y. S. Lin, “Near-optimal Tree-based Access Network Design,” Computer Communications, vol. 28, no. 2, pp. 236–245, February 2005. A. K. Das and M. El-Sharkawi, “Minimum Hop Multicasting in Broadcast Wireless Networks with Omni-directional Antennas,” in Proc. 2004 IEEE Military Communications Conference (MILCOM), Monterey, CA, USA, October 2004, pp. 603-608. R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks,” IEEE/ACM Transactions on Networking (TON), vol.16, no. 4, pp. 840-851, February 2008. K. T. Cheng and F. Y. S. Lin, “Minimax End-to-end Delay Routing and Capacity Assignment for Virtual Circuit Networks,” in Proc. 1995 IEEE Global Communications Conference (GLOBECOM), Singapore, Singapore, November 1995, pp. 2134-2138. T. Murase, H. Shimonishi, and M. Murata, “Overlay Network Technologies for QoS Control,” IEICE Transactions on Communication, vol. E89-B, no. 9, pp. 2280-2291, September 2006. A. M. Geoffrion, “Lagrangean Relaxation and its Uses in Integer Programming,” Mathematical Programming Studies, vol. 2, pp. 82-114, January 1974. M. L. Fisher, “An Application Oriented Guide to Lagrangean Relaxation,” Interfaces, vol. 15, no. 2, pp. 10-21, April 1985. M. L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” Management Science, vol. 27, no. 1, pp. 1-18, January 1981. P. Humblet, “A Distributed Algorithm for Minimum Weight Directed Spanning Trees,” IEEE Transactions on Communications, vol. 31, no. 6, pp. 756-762, June 1983. Y. J. Chu and T. H. Liu, 'On the Shortest Arborescences of a Directed Graph,' Scientia Sinica, vol. 14, pp. 1396-1400, January 1965. J. Edmonds, 'Optimum branchings,' Journal of Research of the National Bureau of Standards B, vol. 71, no. 4, pp. 233-240, October 1967. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65894 | - |
| dc.description.abstract | 應用層覆蓋網路是建立於傳統的網路系統之上，相較於底層網路架構，其具有更彈性與可調整性之特性。在覆蓋網路中最引人注目的議題之一即是訊息廣播，而許多網路應用也都會使用到訊息廣播技術。透過廣播技術，一個訊息或是網路狀態，可以從起始節點被傳遞給網路上所有的其他節點。而對於分散式系統來說，廣播更因為可以讓整個系統維持共識而在許多分散式應用中更顯重要。
不同應用會根據其網路環境與使用情境而對其網路有不同的目標。在本論文中，我們建立一個最佳化問題並考量一個更普遍性的目標，也就是讓廣播到整個網路所產生的傳輸成本最小化，而這個傳輸成本的定則因為網路所關注的面向不同而有所差異。另外，本論文也考量對服務品質的需求，我們將這些服務品質需求轉化為最佳化問題中的限制式，以將其納入最後決策考量。 本論文所要解決的問題是一個NP-完全的問題，我們提出一個透過建立廣播樹致力於有效率路由規劃的數學規劃模型，我們並使用拉格朗日鬆弛法來解決此一最佳化問題。另外，我們提出一個能夠考量服務品質之分散式廣播演算法來讓其能夠被實際應用在分散式網路的環境之中。最後，我們透過模擬實驗來評估所提出之演算法的效能，同時亦提出數種情境設定並觀察變化，並針對實驗結果予以分析與解釋。 | zh_TW |
| dc.description.abstract | Application-level overlay network is built on top of the traditional Internet system, and it is more flexible and adjustable than existing underlay network. One of the most attractive issue in overlay networks is broadcasting, which could be applied by a number of applications. With broadcasting, a message or network status could be transmitted to the whole network from the source node. In the case of distributed system, broadcasting can help keeping a consensus for the whole system.
Different application would set their own objective for their transmission, depends on the network environment and scenario. In this thesis, we formulate an optimization problem and consider a more general objective, which is the minimization of transmission cost in the whole network. The transmission cost mentioned here varies depending on the concern of the network. Furthermore, some QoS (Quality of Service) requirements are also considered, they are transformed into constraints in the proposed optimization problem. The problem that this thesis is going to solve is actually a NP-complete problem. We propose a mathematical programming model which attempts to schedule an efficient routing strategy by constructing a broadcast tree. The Lagrangean relaxation method is then applied to solve the optimization problem. Besides, a distributed broadcast algorithm that considers QoS requirements is proposed to make it possible to implement this algorithm in a distributed environment. Finally, some computing experiments are done to evaluate the performance and variation of the proposed algorithm, and the analyses and interpretations are given. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T00:14:45Z (GMT). No. of bitstreams: 1 ntu-109-R06725052-1.pdf: 2670483 bytes, checksum: ded7084e501f5f471c54d0f610179f5c (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 中文摘要 i
ABSTRACT ii CONTENTS iii LIST OF FIGURES vi LIST OF TABLES vii Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 3 1.3 Literature Review 5 1.3.1 Broadcasting strategies 5 1.3.2 Peer-to-peer topology 7 1.3.3 The topology of broadcast tree 8 1.3.4 QoS control in overlay networks 9 1.4 Proposed Approach 10 1.5 Thesis Organization 11 Chapter 2 Problem Formulation 12 2.1 Problem Description 12 2.1.1 Broadcasting strategy 12 2.1.2 Quality of Service assurance 14 2.1.3 Network topology 15 2.1.4 Table of problem description 16 2.2 Problem Notation 18 2.3 Model Formulation 20 Chapter 3 Solution Approach 23 3.1 Introduction to Lagrangean Relaxation Method 23 3.2 Lagrangean Relaxation 25 3.2.1 Subproblem 1 26 3.2.2 Subproblem 2 28 3.2.3 Subproblem 3 30 3.2.4 Subproblem 4 31 3.3 A Restricted Model Formulation 33 3.3.1 Model Formulation 33 3.4 Lagrangean Relaxation for Restricted Model 36 3.4.1 Subproblem A 37 3.4.2 Subproblem B 38 3.4.3 Subproblem C 40 3.5 The Dual Problem and the Subgradient Method 41 Chapter 4 Distributed Routing Algorithm 42 4.1 Distributed Shortest Path Algorithm 42 4.2 Distributed Broadcasting Tree Algorithm 43 4.3 Getting Primal Feasible Solution 46 4.3.1 Heuristic to consider QoS constraints 47 4.3.2 Heuristic to handle constraint violation 48 4.4 Lagrangean Relaxation Based Algorithm 48 4.5 System Parameters Update Mechanism 50 Chapter 5 Computational Experiments 51 5.1 Experiment Environment and Settings 51 5.2 Performance Evaluation of Proposed Method 52 5.2.1 The primal model 52 5.2.2 The restricted model 54 5.3 Scenario Based Experiments 55 5.3.1 The effect of network scale 55 5.3.2 The effect of weighting factor 57 5.3.3 Hop constraint and fan-out constraint 59 5.3.4 Summaries for scenario based experiments 62 Chapter 6 Conclusions and Future Work 63 6.1 Summary 63 6.2 Future Work 65 ACKNOWLEDGMENT 66 REFERENCES 67 | |
| dc.language.iso | en | |
| dc.subject | 覆蓋網路 | zh_TW |
| dc.subject | 網路廣播 | zh_TW |
| dc.subject | 分散式路由演算法 | zh_TW |
| dc.subject | 服務品質限制路由演算法 | zh_TW |
| dc.subject | 拉格朗日鬆弛法 | zh_TW |
| dc.subject | Distributed Routing Algorithm | en |
| dc.subject | Overlay Network | en |
| dc.subject | Lagrangean Relaxation Method | en |
| dc.subject | Broadcast | en |
| dc.subject | QoS Constrained Routing Algorithm | en |
| dc.title | 考量服務品質之分散式廣播演算法 | zh_TW |
| dc.title | A Distributed QoS Constrained Broadcast Algorithm | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 溫演福(Yean-Fu Wen),黃彥男(Yennun Huang),莊東穎(Tong-Ying Juang),李漢銘(Hahn-Ming Lee) | |
| dc.subject.keyword | 覆蓋網路,網路廣播,分散式路由演算法,服務品質限制路由演算法,拉格朗日鬆弛法, | zh_TW |
| dc.subject.keyword | Overlay Network,Broadcast,Distributed Routing Algorithm,QoS Constrained Routing Algorithm,Lagrangean Relaxation Method, | en |
| dc.relation.page | 70 | |
| dc.identifier.doi | 10.6342/NTU201902663 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-02-14 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-109-1.pdf 未授權公開取用 | 2.61 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。