基于社團劃分的Internet路由器自治系統(tǒng)映射方法研究.pdf

1、現(xiàn)實世界中，許多大型系統(tǒng)都可以抽象為復雜網(wǎng)絡系統(tǒng)，很多的網(wǎng)絡系統(tǒng)內(nèi)部都具有社團結構。宏觀上，社團結構有助于深入理解網(wǎng)絡的內(nèi)部結構和拓撲特征；微觀上，社團結構有助于理解網(wǎng)絡中節(jié)點之間的關系和相互作用。Internet也可以看作是一個巨大的復雜網(wǎng)絡。Internet由大量的路由器、主機以及之間的相互連接構成，同時Internet也可以劃分為不同的管理域，每個管理域管理著一個或者多個自治系統(tǒng)。從復雜網(wǎng)絡中的社團結構來看，某種程度上可以將自治系

2、統(tǒng)看作社團，雖然自治系統(tǒng)和復雜網(wǎng)絡中的社團有著不同的特點，但是現(xiàn)有的社團發(fā)現(xiàn)方法可以為Internet的自治系統(tǒng)劃分工作提供一些啟發(fā)。
　　過去十多年中，針對Internet的路由器級和自治系統(tǒng)級的拓撲結構，已經(jīng)有了比較系統(tǒng)和完整的方法。但是，這兩個級別的拓撲結構是獨立的和分離的，仍然缺少有效的方法來綜合展示 Internet在這兩個級別的結構。CAIDA在這方面做了一些初步的工作，即通過由路由追蹤和別名解析技術得到的路由器級拓撲

3、以及拓撲中路由器的端口歸屬的自治系統(tǒng)來推斷路由器歸屬的自治系統(tǒng)，該過程稱為Internet路由器自治系統(tǒng)映射。在此基礎上，結合現(xiàn)有的社團發(fā)現(xiàn)算法，本文提出新的路由器自治系統(tǒng)映射方法，并在實際數(shù)據(jù)上做出驗證。實際數(shù)據(jù)驗證表明，本文提出的兩種方法的正確率相對CAIDA提出的基本方法有所提升，同時本文的兩種方法從不同的思路出發(fā)，具有不同的算法復雜性和準確率。
　　主要工作介紹如下，（1）提出一種基于節(jié)點相似性且利用網(wǎng)絡節(jié)點局部信息的路由

4、器自治系統(tǒng)映射方法。該方法中，路由器自治系統(tǒng)映射過程分為兩步，第一步將路由器端口信息和拓撲結構信息轉換為網(wǎng)絡的邊的權重，第二步采用復雜網(wǎng)絡社團劃分的思想依據(jù)第一步得到的帶權重的網(wǎng)絡拓撲推斷路由器之間的關系，完成路由器自治系統(tǒng)的映射過程；（2）實現(xiàn)CAIDA提出的方法，對比本文的方法與CAIDA所提出的方法在相同的數(shù)據(jù)上的不同表現(xiàn)；（3）對比不同節(jié)點相似性以及不同邊的權重計算方法的映射結果的準確性；（4）提出一種采用鏈路預測思想以及全局網(wǎng)