跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/03 03:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林淑君
研究生(外文):Shu-Chun Lin
論文名稱:利用拓撲特性分析與演算法設計之網際網路效能改善研究
論文名稱(外文):Internet Performance Improvement via Topological Properties Analysis and Algorithm Design
指導教授:盧能彬盧能彬引用關係
指導教授(外文):Neng-Pin Lu
學位類別:碩士
校院名稱:長庚大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:94
中文關鍵詞:網路拓撲分析網際網路小世界網路無尺度網路
外文關鍵詞:topology analysisInternetsmall-world networksscale-free networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:139
  • 評分評分:
  • 下載下載:14
  • 收藏至我的研究室書目清單書目收藏:4
本論文目的主要在探討網際網路 (Internet) 的拓撲結構 (Topology)。本研究藉由研究流程的建構,著手收集網際網路路由資訊,進行網路拓撲的資料分析與相關理論驗證,透過模擬演算法的設計,以及實驗模擬後提出改善網際網路效率之建議。本研究觀察了目前網際網路的現況,並建立了網際網路相關後續應用、研究的基本資料庫。本論文以網際網路位址 (IP address) 為研究基礎,從網路管理、政治、經濟角度擷取抽樣樣本,分別是全球191個國家與地區的網路資訊中心 (Network Information Center)網站、227個政府入口網站,與2004年Fortune Global 500大企業網站網址,並另以隨機方式產生抽樣對象作為樣本對映。本研究以 tracert 為基礎的路由偵測程式,由長庚大學出發對所有的抽樣網際網路位址,進行網路拓撲搜尋 (Network Probing),並將收集之路由資訊建置於資料庫eLinkage中。之後輔以網路拓撲特性之統計分析,以小世界網路 (small-world property)與無尺度網路 (scale-free property)進行理論驗證,同時應用圖形理論於網際網路拓撲的表示,並且實作 iGeoMap,產生與實際地理資訊對映之網路拓撲圖形,使整體網際網路拓撲能夠清楚與具結構性的被呈現,以利於後續研究者判讀辨識與研究探討。最後本研究輔以演算法設計與模擬實驗,提出網際網路建置與發展的相關建議。
This thesis is to analyze the Internet topology. The research goal is to collect statistics data of the Internet structure and to compare the results with related theories, such as small-world networks and scale-free networks. In this research, we sampled from network management, political, and economic aspects. In the three sets of samples, there are 191 web sites of Network Information Centers (NIC), 227 government portal sites, and 2004 Fortune Global 500 corporations’ web sites. To make sure the validities of the three sample set, an extra set of 10 thousand randomly sampled IP addresses were traced. The IP routing information from Chang Gung University to the sampled IP addresses were collected by traceroute-based utility: tracert and was stored into the database: eLinkage. Through statistical analysis of topological properties, small-world property and scale-free property were verified. After theory verification, we also applied graph theory to visualize the Internet topology map. As a result, we developed a tool: iGeoMap to generate the Internet topology with geographical mapping. Furthermore, we implemented our filtering algorithm, Kf, to figure out the rough backbone of the Internet. Finally, we designed two algorithms, Longest-path-first (LPF) and Random-link-added (RLA) methods to suggest improving performance of the Internet.
指導教授推薦書………………………………………………………
口試委員會審定書……………………………………………………
授權書………………………………………………………………… iii
誌謝…………………………………………………………………… iv
摘要…………………………………………………………………… v
Abstract……………………………………………………………… vi
Table of Contents………………………………………………… vii
List of Figures……………………………………………………… x
List of Tables ……………………………………………………… xiii
List of Abbreviations……………………………………………… xv

CHAPTER 1 Introduction 1
1.1 Motivation 1
1.2 Research Objective 3
1.3 Research Scope 3
1.4 Thesis Organization 4
CHAPTER 2 Background and Related Work 5
2.1 Internet 5
2.1.1 Internet Structure 5
2.1.2 Internet Addressing 7
2.1.3 The Domain Name System 11
2.1.4 Internet Topology 12
2.2 Graph Terminology and Notation 13
2.3 Classical Graph Models 17
2.4 Small-world Networks 18
2.5 Scale-free Networks 20
2.6 Summary 22
CHAPTER 3 Methodology 23
3.1 Research Flow 23
3.1.1 Selecting Experimental Samples 24
3.1.2 Probing the Internet 24
3.1.3 Building “eLinkage” Database 29
3.1.4 Making Statistical Analysis 30
3.1.5 Mapping Internet Topology 30
3.1.6 Doing Simulations 30
3.1.7 Making Discussion and Conclusion 30
3.2 Data Structures and Algorithms 31
3.2.1 Assumption 31
3.2.2 Data Structures 31
3.2.3 Problem of Private IP Addresses 32
3.2.4 All-pairs Shortest Paths Algorithm 33
3.3 Metrics 34
3.4 Statistical Methods 35
3.5 Developing Environment 38
3.6 Database 38
CHAPTER 4 Analytical Results 46
4.1 Sample Testing 46
4.2 Analytical Results of Metrics 48
4.2.1 Degree, k 49
4.2.2 Path Lengths, l 53
4.2.3 Clustering Coefficient, c 57
4.3 Geographical Visualization 58
4.4 Filtering Algorithm, Kf 64
4.5 Summary 68
CHAPTER 5 Performance Simulations 70
5.1 Introduction 70
5.2 First m Longest-Path First Method (LPF) 73
5.3 Random-Link-Added Method (RLA) 77
5.4 Random-Link-Added Method Combined with Kf Algorithm (RLA plus Kf) 81
5.5 Suggestion 86
CHAPTER 6 Conclusions and Future Work 87
References 90
1.W. Aiello, F. R. K. Chung, and L. Lu., “A random graph model for massive graphs,” in Proc. ACM Symposium on Theory of Computing (STOC), pp. 171-180, 2000.
2.R. Albert, A.-L. Barabási, H. Jeong, and G. Bianconi, “Power-law distribution of the World Wide Web,” Science, vol. 287, pp. 2115a, 2000.
3.R. Albert, H. Jeong, and A.-L. Barabási, “Diameter of the World-Wide Web,” Nature, vol. 401, pp. 130-131, 1999.
4.R. Albert, H. Jeong, and A.-L. Barabasi, “Error and Attack Tolerance of Complex Networks,” Nature, vol. 406, pp. 378, 2000.
5.P. Albitz and C. Liu, DNS and BIND, 4th ed. California: O'Reilly & Associates, 2001.
6.L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, “Classes of Small-World Networks,” in Proc. of the National Academy of Sciences, vol. 97, no. 21, October 2000.
7.S. M. Ballew, Managing IP Networks with Cisco Routers, 1st ed., California: O'Reilly & Associates, 1997.
8.A.-L. Barabási, Linked: How Everything Is Connected to Everything Else and What It Means, 2nd ed. New York: Pub.Plume Books, 2003.
9.A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509-512, 1999.
10.S. Branigan, H. Burch, B. Cheswick, and F. Wojcik, “What Can You Do with Traceroute?” IEEE Internet Computing, vol. 5, no. 5, 2001.
11.D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Network Robustness and Fragility: Percolation on Random Graphs,” Physical Review Letters, vol. 85, no. 25, pp. 5468, 2002.
12.R. F. i Cancho, C. Janssen and R. V. Sole, “Topology of technology graphs: small world patterns in electronic circuits,” Physical Review E, vol. 64, 046119, 2001.
13.Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker and W. Willinger, “The Origin of Power Laws in Internet Topologies (Revisited),” in Proc. IEEE INFOCOM 2002, June 2002.
14.D. E. Comer, and D. L. Stevens, Internetworking with TCP/IP Volume II: Design, Implementation, and Internals, 2nd ed. New Jersey: Prentice-Hall, 1994.
15.Defense Advanced Research Projects Agency Information Processing Techniques Office, “Internet Protocol,” IETF, RFC 791, 1981.
16.S. Dorogovtsev and J. Mendes, Evolution of networks: from biological nets to the Internet and WWW, 1st ed. New York: Oxford University Press, 2003.
17.P. Erdös and A. Rényi, “On Random Graph,” Publications Mathematicae, vol. 6, pp. 290-297, 1959.
18.P. Erdös and A. Rényi, “On the EVolution of Random Graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Science, vol. 5, pp. 17-61, 1960.
19.P. Erdös and A. Rényi, “On the Strength and Connectedness of a Random Graph,” Acta Mathematica Scientia Hungarian, vol. 12, pp. 261-267, 1961.
20.C. Faloutsos, M. Faloutsos, and P. Faloutsos, “On Power-Law Relationships of the Internet Topology,” in Proc. of ACM SIGCOMM, 1999.
21.P. P. Frasconi and P. Smyth, Modeling the Internet and the Web: Probabilistic Methods and Algorithms, 1st ed. New Jersey: John Wiley & Sons, 2003.
22.M. Hollander and D. A. Wolfe, Nonparametric Statistical Methods, 2nd ed. New York: Wiley-Interscience, 1999.
23.T. Hong, “Performance,” Peer-to-Peer: Harnessing the Power of Disruptive Technology, 1st ed. A. Oram, ed., California: O'Reilly & Associates, 2001.
24.B. Huffaker, M. Fomenkov, D. Plummer, D. Moore, and K. Claffy, “Distance Metrics in the Internet,” in Proc. IEEE International Telecommunications Symposium (ITS), Brazil, September 2002.
25.G. Huston, “Interconnection, Peering, and Settlements,” Internet Protocol Journal, vol. 2, no. 1, pp. 210-217, 1999.
26.S. Jin, Scalability of Multicast-based Streaming Delivery Mechanisms on the Internet, PhD Dissertation, Boston Univ., United States, 2003.
27.G. Malkin, “Traceroute Using an IP Option,” IETF, RFC 1393, 1993.
28.S. Milgram, “The Small World Problem,” Psychology Today, vol. 22, pp. 61-67, 1967.
29.P. Mockapetris, “Domain Names-Concepts and Facilities,” IETF, RFC 1034, 1987.
30.R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet, 1st ed. Cambridge, UK.: Cambridge University Press, 2004.
31.J. Postel, “Internet Control Message Protocol,” IETF, RFC 777, 1981.
32.Y. Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot, and E. Lear, “Address Allocation for Private Internets,” IETF, RFC 1918, 1996.
33.S. Sahni, Data Structures, Algorithms, and Applications in Java, 1st ed. New York: McGraw-Hill, 2001.
34.R. Siamwalla, R. Sharma, and S. Keshav, “Discovering Internet Topology,” in Proc. IEEE Infocom'99, pp. 21-25, 1999.
35.H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, “Network Topology Generators: Degree based vs. Structural,” in Proc. ACM SIGCOMM 2002, 2002.
36.A. Vazquez, “Statistics of citation networks,” cond-mat/0105031, May 2001.
37.X. F. Wang and G. Chen, “Complex Networks: Small-world, Scale-free and Beyond,” IEEE Control & System Magazine, vol. 3, no. 1, pp. 6-20, 2003.
38.D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, vol. 393, pp. 440, 1998.
39.S. Zhou and R. J. Mondragon, “The ‘rich-club' phenomenon in the Internet topology,” IEEE Communication Letters, November 2002.
40.S. Zhou and R. J. Mondragon, “The missing links in the BGP-based AS connectivity maps,” in Proc. Passive and Active Measurement Workshop (PAM03), San Diego, USA., April 2003.

Online Resources:
1.aiSee. [Online]. Available: http://www.aisee.com
2.CIA, “The World Factbook 2005," 2005. [Online]. Available: http://www.cia.gov/cia/publications/factbook
3.Fortune, “The 2004 Global 500: The World Largest Corporations,” 2004. [Online]. Available: http://www.fortune.com/fortune/global500
4.Name Intelligence, “IP Counts by Country,” 2005. [Online]. Available: http://www.whois.sc/internet-statistics/country-ip-counts.html
5.National Laboratory for Applied Network Research (NLANR), “Route Views archive.” [Online]. Available: http://moat.nlanr.net/Routing/rawdata.
6.Root-Zone Whois Information, IANA ccTLD Database, 2004. [Online]. Available: http://www.iana.org/cctld/cctld-whois.htm
7.Routeviews, “Route Views archive.” [Online]. Available: http://archive.routeviews.org
8.The RIPE routing information service. [Online]. Available: http://www.ripe.net/ris
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top