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

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

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

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

4、器自治系統(tǒng)映射方法。該方法中，路由器自治系統(tǒng)映射過程分為兩步，第一步將路由器端口信息和拓?fù)浣Y(jié)構(gòu)信息轉(zhuǎn)換為網(wǎng)絡(luò)的邊的權(quán)重，第二步采用復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的思想依據(jù)第一步得到的帶權(quán)重的網(wǎng)絡(luò)拓?fù)渫茢嗦酚善髦g的關(guān)系，完成路由器自治系統(tǒng)的映射過程；（2）實(shí)現(xiàn)CAIDA提出的方法，對比本文的方法與CAIDA所提出的方法在相同的數(shù)據(jù)上的不同表現(xiàn)；（3）對比不同節(jié)點(diǎn)相似性以及不同邊的權(quán)重計(jì)算方法的映射結(jié)果的準(zhǔn)確性；（4）提出一種采用鏈路預(yù)測思想以及全局網(wǎng)