國立臺灣大學電機工程學系暨研究所黃寶儀2006-07-252018-07-062006-07-252018-07-062004-07-31http://ntur.lib.ntu.edu.tw//handle/246246/7984本研究的主要目的在探討網際網路連結架構(Internet topology)在Autonomous System(AS)層面的各種特徵與模式的建構。我們的做法有別於既存的“統計為主 直覺為輔”(statistics and intuition)方法，以圖學(spectral graph theory)為出發點， 將網際網路的連結予以嚴謹的理論分析。工作主要分三項：1)圖學上與網際網路 相關的量測值(metrics)研究、2)本團隊提出的Normalized Laplacian Spectrum(nls) 用於鑑別網際網路連結架構與其他圖學良測值的比較、及3)網際網路連結架構的 模型建構與產生器的編寫。第一年的研究進度略超過預期、各項工具程式的編寫 已大致底定、並且已經開始分析比較的研究。期間、我們也發現了目前運算設備 上的瓶頸。由於網際網路的成長迅速，節點與節線數量大幅增加。經過最佳化之 後，運算所需的記憶體與CPU cycle 量極高。針對這個問題，我們也藉期中報告 的機會一併提出在電腦設備上小幅增加預算。Our goal is to investigate the various characteristics and to establish a high-fidelity model of the Internet topology at the autonomous system (AS) level. Our approach is distinctive of the existing methods aided by statistics and experts’ intuition. In this project, we propose to analyze the Internet topology using rigorous graph theory. The project execution is constructed in 3 parts: 1) the study of the Internet graphs using graph-theoretical metrics, 2) the effectiveness and comparison of the use of Normalized Laplacian Spectrum (nls) to distinguish the Internet topology, and 3) the modeling of the Internet topology and topology generation. We have accomplished more than we anticipate for the first year. As of the time this mid-term report is fired, we are about to finish all implementation of the graph theoretical analysis tools and have begun the analysis and the modeling of the Internet topology. During the year, we also found a bottleneck in computation. Due to the excessive growth of the Internet, the size of the topology in our analysis has exceeded the capacity of the computing equipment we have. After optimizing our tool implementation, the extensive use of memory and CPU cycles still poses a serious challenge. Therefore, we would like to take advantage of the opportunity to plead for a raise on the computing equipment budget to accommodate the unexpected computation resource problem.application/pdf98067 bytesapplication/pdfzh-TW國立臺灣大學電機工程學系暨研究所網際網路連結結構圖學連結結構產生器Internet TopologyGraph TheoryTopology Generatorreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/7984/1/922213E002055.pdf