黃寶儀臺灣大學：電機工程學研究所徐榮德Shyu, Lung-deLung-deShyu2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53217There has been a significant amount of work analyzing the Internet AS (Autonomous System)-level topology which gives rise to a number of topology models. Although each of these models is being refined to fit better a particular set of graph properties over time, there is a more fundamental need in knowing the topology invariants. To address this need, we examine how the Internet AS-level topology evolves, using a variety of graph metrics—a super set of what has been used in recent works. We discover that the AS-level topology shows a clear converging trend only in the normalized Laplacian spectrum (nls). From the theory of nls, we discover further that the converging trend indicates a stabilizing ratio of leaf to core ASes (or customer to provider ASes) on the Internet.abstract i 1 Introduction 1 1.1 Thesis Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 RelatedWork 4 3 Data Sets 6 3.1 Consistency Analysis . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Metrics and Normalizations 12 4.1 Single value metrics . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Distribution-based metrics . . . . . . . . . . . . . . . . . . . . . 13 5 Search of Invariants 16 5.1 Evolving Trends . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 Identifying Invariants . . . . . . . . . . . . . . . . . . . . . . . . 23 5.3 Sensitivity Test of MG(1) . . . . . . . . . . . . . . . . . . . . . . 24 6 Understanding the Invariant 25 6.1 nls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.2 Significance of MG(1) . . . . . . . . . . . . . . . . . . . . . . . 26 7 Conclusion 29 8 Future Work and Discussion 301264843 bytesapplication/pdfen-US網際網路自治系統層級不變性InternetAutonomous Systeminvariantsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53217/1/ntu-95-R93921029-1.pdf