Internet拓?fù)浣Ｅc演化綜述?

關(guān)曉惠，錢亞冠，周志敏

（1.浙江水利水電專科學(xué)校計(jì)算機(jī)與信息工程系，杭州310018；2.浙江科技學(xué)院理學(xué)院，杭州310023）

Internet拓?fù)浣Ｅc演化綜述?

關(guān)曉惠1，錢亞冠2，周志敏1

（1.浙江水利水電?？茖W(xué)校計(jì)算機(jī)與信息工程系，杭州310018；2.浙江科技學(xué)院理學(xué)院，杭州310023）

認(rèn)識Internet拓?fù)浣Y(jié)構(gòu)及其演化趨勢對下一代網(wǎng)絡(luò)技術(shù)的研究至關(guān)重要?？偨Y(jié)了Internet拓?fù)溲芯砍晒?，綜述了Internet靜態(tài)拓?fù)淠Ｐ秃蛣討B(tài)演化模型，著重考察了拓?fù)湓诠?jié)點(diǎn)度和結(jié)構(gòu)兩方面的演化特征，據(jù)此提出了今后的研究方向，即運(yùn)用統(tǒng)計(jì)物理的非廣延Tsallis熵理論來研究拓?fù)涮卣饕约坝梅謱拥姆绞窖芯縄nternet拓?fù)浣Y(jié)構(gòu)，以期取得有效的成果。

下一代網(wǎng)絡(luò)；Internet拓?fù)淠Ｐ?；冪律；演化；?jié)點(diǎn)度；Tsallis熵

1 引言

Internet是復(fù)雜網(wǎng)絡(luò)的一個典型例子，也可以說是一個龐大的人工生態(tài)系統(tǒng)。Internet發(fā)展時間盡管不長，但隨著用戶數(shù)的不斷增多，其規(guī)模變得極其龐大；政治、經(jīng)濟(jì)和技術(shù)的變化也影響著拓?fù)浣Y(jié)構(gòu)的演變。Internet發(fā)展到現(xiàn)在，幾乎沒有人能清楚地描述它的真實(shí)拓?fù)浣Y(jié)構(gòu)。研究Internet拓?fù)溲莼Ｐ陀兄匾囊饬x：深入理解現(xiàn)存路由協(xié)議的局限性，正確評估新的協(xié)議、體系的設(shè)計(jì)，預(yù)測將來互聯(lián)網(wǎng)的發(fā)展需求；深入理解網(wǎng)絡(luò)技術(shù)、拓?fù)浣Y(jié)構(gòu)和背后的經(jīng)濟(jì)因素之間的相互作用關(guān)系；路由協(xié)議的模擬與仿真、網(wǎng)絡(luò)病毒的傳播等均需要網(wǎng)絡(luò)拓?fù)淠Ｐ?；發(fā)現(xiàn)拓?fù)溲葑儽澈蟮膭右颉⒈举|(zhì)規(guī)律，對于指導(dǎo)和預(yù)測將來Internet上部署各種新技術(shù)、新協(xié)議和新應(yīng)用將具有重要指導(dǎo)意義。

對Internet拓?fù)涞难芯恳话阕裱@樣的過程：從真實(shí)的Internet環(huán)境中提取拓?fù)鋽?shù)據(jù)，通過各種數(shù)學(xué)方法分析拓?fù)涮卣?，根?jù)分析得到的拓?fù)涮卣鹘⑾鄳?yīng)的拓?fù)淠Ｐ秃蜕伤惴?，通過數(shù)學(xué)分析的方法或?qū)嶒?yàn)的方法來驗(yàn)證所建立模型的正確性。

對Internet的拓?fù)溲芯浚叭艘呀?jīng)做了很多工作，從最初的隨機(jī)圖模型到結(jié)構(gòu)模型，到Faloutsos提出的節(jié)點(diǎn)度的分布冪律特征［1］，再到Barabasi等提出的無標(biāo)度網(wǎng)絡(luò)［2］，以及后來Zhou S等提出的rich -club現(xiàn)象［3］、Mahadevan等關(guān)于節(jié)點(diǎn)度的相關(guān)性研究［4］，這些都是基于靜態(tài)模型基礎(chǔ)的。目前，動態(tài)演化模型的研究越來越受到關(guān)注［5-7］。

由于Internet是通過BGP協(xié)議將全球AS（自治系統(tǒng)）互聯(lián)起來的網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)主要由AS之間的互連關(guān)系表現(xiàn)出來，因此本文也主要闡述AS級的拓?fù)淠Ｐ停磳⒚總€AS看作圖的節(jié)點(diǎn)，將AS之間的連接抽象成圖中節(jié)點(diǎn)的鄰接關(guān)系。

2 拓?fù)浣４嬖诘睦щy

2.1 拓?fù)鋽?shù)據(jù)測量的困難

不管是建立還是驗(yàn)證分析Internet的拓?fù)淠Ｐ?，都需要可靠和真?shí)的數(shù)據(jù)。目前獲得Internet拓?fù)鋽?shù)據(jù)的方法主要有：

（1）通過測量技術(shù)獲得，常用工具是traceroute，由于Internet的拓?fù)鋾r刻處于動態(tài)變化，因此測量得到的數(shù)據(jù)具有滯后性；

（2）通過路由器上的BGP表、IRR、RIR獲得，由于測量節(jié)點(diǎn)的數(shù)量有限，探測的目的節(jié)點(diǎn)數(shù)量也有限；AS之間存在的路由策略，BGP路由表不一定對外宣告；拓?fù)浣Y(jié)構(gòu)的高度動態(tài)變化等因素；尤其是很難發(fā)現(xiàn)冗余鏈接。

出于商業(yè)競爭、網(wǎng)絡(luò)安全等因素的考慮，對于ISP來說，網(wǎng)絡(luò)拓?fù)?、路由策略、對等關(guān)系、容錯能力和容量規(guī)劃等信息對外界都是不公開的。AS級的營運(yùn)商會經(jīng)常變更他們之間的連接和流量交換策略；AS內(nèi)部也因?yàn)榻?jīng)常發(fā)生路由設(shè)備的失敗、維護(hù)和升級等事件，使得路由器級的拓?fù)浣Y(jié)構(gòu)同樣也是不穩(wěn)定的。因此，獲取Internet真實(shí)的拓?fù)鋽?shù)據(jù)非常困難。

正是由于無法精確了解Internet的真實(shí)拓?fù)浣Y(jié)構(gòu)，也就為正確建立和驗(yàn)證拓?fù)淠Ｐ蛶砹撕艽蟮睦щy。CAIDA（The Cooperative Association for Internet Data Analysis）認(rèn)為目前需要解決的問題有［8］：

（1）所有的測量都受到實(shí)驗(yàn)條件和觀測條件的限制，如觀測點(diǎn)的地理分布范圍、數(shù)量，被探測節(jié)點(diǎn)的數(shù)量等，使得數(shù)據(jù)不可避免的帶有局限性；

（2）數(shù)據(jù)的不完整導(dǎo)致我們將一些合成的拓?fù)淠Ｐ彤?dāng)作真實(shí)的Internet拓?fù)?，已?jīng)證明像E-R隨機(jī)圖這樣一類特殊的圖不能代表真實(shí)的Internet拓?fù)洌?/p>

（3）應(yīng)該將測量的目標(biāo)放到具體的地理區(qū)域，通過比較不同的地理區(qū)域和社會經(jīng)濟(jì)環(huán)境下的數(shù)據(jù)去區(qū)分Internet在全局核心和局部區(qū)域的不同特征。

在CAIDA發(fā)起的WIT（the Workshop on Internet Topology）上，所有與會的網(wǎng)絡(luò)研究組織一致認(rèn)為高質(zhì)量的測量數(shù)據(jù)對于拓?fù)浣Ｑ芯糠浅Ｖ匾?。目前可供給研究者使用的拓?fù)鋽?shù)據(jù)源有RouteViews、RIPE、Skitter、DIMES、iPlane等。

2.2 生成機(jī)理與演化規(guī)律

目前，我們只是對Internet的靜態(tài)拓?fù)浣y(tǒng)計(jì)特性有所了解，如節(jié)點(diǎn)度分布的冪律特征、rich-club特征等，但I(xiàn)nternet拓?fù)淙绾窝葑?，以及模擬演變過程，即找到合適的拓?fù)渖伤惴?，使之在演變過程中始終保持這些特征是一個困難的問題。我們發(fā)現(xiàn)的這些統(tǒng)計(jì)特征只是一個靜態(tài)的、表層的、描述性的（de

scriptive），要解決這個難題必須找到形成這些統(tǒng)計(jì)特征背后的生長機(jī)理和各種促進(jìn)因素，包括技術(shù)的、經(jīng)濟(jì)的和社會的，必須是解析性的（explanatory）。文獻(xiàn)［9］指出，即使兩個拓?fù)渚哂邢嗤慕y(tǒng)計(jì)度量，它們之間也可能具有不同的拓?fù)浣Y(jié)構(gòu)，如二維格子和三叉樹，均具有相同的節(jié)點(diǎn)度分布。Internet拓?fù)涞男纬蓻]有事先設(shè)計(jì)規(guī)劃，各個ISP只在自己的AS域內(nèi)進(jìn)行優(yōu)化規(guī)劃，但I(xiàn)nternet拓?fù)鋮s很好地表現(xiàn)出“小世界”特征，使得路由非常高效，是什么原因使得局部最優(yōu)同時也能全局最優(yōu)，尋找這些背后的生成機(jī)理對于下一代網(wǎng)絡(luò)的研究具有重要意義。

2.3 模型驗(yàn)證的困難

由于缺乏對真實(shí)Internet拓?fù)涞牧私?，以及測量方法的局限和拓?fù)涞膭討B(tài)變化，使得拓?fù)淠Ｐ偷尿?yàn)證也存在極大的困難。文獻(xiàn)［10］指出了目前拓?fù)淠Ｐ万?yàn)證的困難在于以下幾方面。

（1）拓?fù)渖善髦荚诋a(chǎn)生一類拓?fù)鋱D，它們反映Internet某些拓?fù)涮卣?。區(qū)分這些拓?fù)鋱D的類型依賴于哪些拓?fù)涮卣餍枰磉_(dá)，以及這些特征如何表達(dá)。如何確定這些分類在真實(shí)性和典型性之間的界限是目前還無法解決的問題。

（2）目前對Internet的拓?fù)涮卣鬟€沒有被充分的研究。由于路由選擇的復(fù)雜性，通過traceroute工具和BGP數(shù)據(jù)進(jìn)行逆向工程方式分析，得出的拓?fù)涮卣鞔嬖诓缓侠淼牡胤健?/p>

（3）目前已經(jīng)存在很多拓?fù)涠攘?，但并不是每個都與Internet的拓?fù)湎嚓P(guān)，選擇哪些拓?fù)涠攘咳ヲ?yàn)證模型是一個目前還沒解決的問題。

3 拓?fù)溲莼?/h2>

拓?fù)淠Ｐ涂煞譃殪o態(tài)模型和動態(tài)模型［11］。靜態(tài)模型是指從可獲得的實(shí)際拓?fù)鋽?shù)據(jù)中生成能夠反映實(shí)際網(wǎng)絡(luò)拓?fù)涮匦缘撵o態(tài)網(wǎng)絡(luò)拓?fù)鋱D，可以稱為是一個拓?fù)淇煺眨═opology Snapshot）；動態(tài)模型是指根據(jù)某種或某幾種拓?fù)涮匦远芯烤W(wǎng)絡(luò)的生長／演化過程，反映拓?fù)涮匦陨蓹C(jī)理，因此也把動態(tài)模型稱為演化模型。動態(tài)演化的不僅包括節(jié)點(diǎn)和邊在數(shù)量上的增長，也包含數(shù)量的減少和節(jié)點(diǎn)之間連接的改變等。

對于動態(tài)模型，我們又將它們分為基與節(jié)點(diǎn)度的演化和基于結(jié)構(gòu)的演化兩類。

3.1 基于節(jié)點(diǎn)度的演化模型

3.1.1 BA模型

BA模型是Barabasi和Albert于1999年提出，大型網(wǎng)絡(luò)能自組織成無標(biāo)度（Scale-free）狀態(tài)，主要是因?yàn)椋涸鲩L（Growth）特性，即網(wǎng)絡(luò)的規(guī)模是不斷擴(kuò)大的；優(yōu)先連接（preferential-attachment）特性，即新的節(jié)點(diǎn)加入網(wǎng)絡(luò)，總是傾向于與較高連接度的“大”節(jié)點(diǎn)連接。

BA模型就是基于上述兩個特征構(gòu)造的具有度分布呈冪律特征的無標(biāo)度網(wǎng)絡(luò)。構(gòu)造算法如下：

（1）增長：從一個具有m0個節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次加入一個新的節(jié)點(diǎn)，并連接到m個已存在的節(jié)點(diǎn)上，m≤m0；

（2）優(yōu)先連接：新加入的節(jié)點(diǎn)以概率∏（ki）=與節(jié)點(diǎn)i連接，ki是節(jié)點(diǎn)i的度。

3.1.2 AB模型

AB模型是Albert和Barabasi于2000年提出的［12］，是對BA模型的擴(kuò)展。AB模型的拓?fù)溲莼瘉碜杂谛鹿?jié)點(diǎn)的加入、新邊的加入和邊的重新連接。具體算法是從m0個孤立的節(jié)點(diǎn)開始，每一步執(zhí)行下面3個步驟中的一個：

（1）以概率p加入m（m≤m0）條新邊，這些邊連接已存在的節(jié)點(diǎn)：隨機(jī)選擇一個節(jié)點(diǎn)作為新邊的起始點(diǎn)，再以概率

選擇另一端的節(jié)點(diǎn)；此過程重復(fù)m次；

（2）以概率q重連m條邊：隨機(jī)取節(jié)點(diǎn)i和它的一條邊lij，刪除這條邊并重新以概率∏ab（kj）選擇一個節(jié)點(diǎn)j作新的連接；此過程重復(fù)m次；

（3）以概率1-p-q增加一個新節(jié)點(diǎn)，以概率∏ab（kj）與網(wǎng)絡(luò)中已存在的m個節(jié)點(diǎn)連接。

上述概率p、q滿足0≤p＜1，0≤q＜1-p。

3.1.3 GLP模型

GLP模型［13］稱廣義線性優(yōu)先（Generalized Linear Preference）模型，由Tian Bu和Don Towsley于2002年提出。該模型不僅體現(xiàn)了度分布的冪律特征，還表達(dá)了兩個“小世界”模型的聚簇特性和特征路徑長度。經(jīng)過觀察，發(fā)現(xiàn)Internet節(jié)點(diǎn)比BA模型線性優(yōu)先連接更傾向于連接到連接度高的節(jié)點(diǎn)上，因此提出了廣義線性優(yōu)先的方法。另外，文獻(xiàn)［14］的研究表明，Internet在AS級很少發(fā)生重連（rewiring）操作。GLP模型去除了AB模型的重連操作，算法與AB模型相似，是從一個有m0個節(jié)點(diǎn)、m0-1條邊連接的網(wǎng)絡(luò)開始，首先以概率p增加m≤m0條新邊，新邊兩端的每個節(jié)點(diǎn)以概率

在網(wǎng)絡(luò)中已存在的節(jié)點(diǎn)中選擇。β∈（-∞，1）是一個可調(diào)節(jié)參數(shù)，β值越小，表明對高連接度節(jié)點(diǎn)的偏好性越小。其次，以概率1-p增加一個新節(jié)點(diǎn)，新節(jié)點(diǎn)以概率∏（di）連接m個節(jié)點(diǎn)。Tian Bu從數(shù)學(xué)上證明了廣義線性優(yōu)先模型具有冪律特征的度分布。

3.1.4 GNG模型

GNG（Generalized Network Growth）模型［15］與GLP模型相似，由Caldarelli于2003年提出?；舅悸肥浅嗽试S同時以概率p加入節(jié)點(diǎn)和以概率（1-p）加入連接，還采用了一種新的偏好方案：即要么加入一個新節(jié)點(diǎn)，以概率

與節(jié)點(diǎn)i連接；要么以概率

在節(jié)點(diǎn)i、j之間加入一條新邊。GNG模型生成的網(wǎng)絡(luò)具有無標(biāo)度特征，在節(jié)點(diǎn)度的分布、介數(shù)的分布和聚簇系數(shù)等方面與Internet拓?fù)錅y量吻合，但動態(tài)增長特征與測量結(jié)果不符合。

3.1.5 IG模型

IG（Interactive Growth）模型［16］由S.Zhou于2003年提出。IG模型仍然采用BA模型的兩個基本操作：新節(jié)點(diǎn)和新邊的加入，連接概率也采用BA模型的線性偏好連接∏（ki），但BA、AB、GLP模型的新節(jié)點(diǎn)和新邊的加入是相互獨(dú)立的，IG模型提出新節(jié)點(diǎn)和新邊聯(lián)合增長模式。聯(lián)合增長模型基于如下發(fā)現(xiàn)：新加入的節(jié)點(diǎn)連接到它的宿主節(jié)點(diǎn)（host），會給宿主節(jié)點(diǎn)增加流量，同時也帶來宿主節(jié)點(diǎn)周圍節(jié)點(diǎn)的流量模式變化，從而需要增加從宿主節(jié)點(diǎn)到它對等方（peer）的新連接，以便均衡流量和優(yōu)化網(wǎng)絡(luò)性能。實(shí)驗(yàn)表明，與AB、GLP模型相比，IG模型在節(jié)點(diǎn)度的分布和rich-club特性上更接近于真實(shí)的Internet拓?fù)洹?/p>

具體算法是從一個小的隨機(jī)網(wǎng)絡(luò)開始，反復(fù)執(zhí)行如下操作：

（1）以概率p∈（0，1），加入一個新節(jié)點(diǎn)，并以概率∏（ki）與網(wǎng)絡(luò)中已有節(jié)點(diǎn)（稱宿主節(jié)點(diǎn)）連接，如圖1中新節(jié)點(diǎn)A-接入節(jié)點(diǎn)連接，再在宿主節(jié)點(diǎn)與其它網(wǎng)內(nèi)節(jié)點(diǎn)之間添加兩條內(nèi)部連接，如圖中的伙伴節(jié)點(diǎn)-接入節(jié)點(diǎn)-伴節(jié)點(diǎn)連接；

（2）以概率1-p，加入一個新節(jié)點(diǎn)，并以概率∏（ki）與網(wǎng)絡(luò)中已有的兩個宿主節(jié)點(diǎn)連接，再在其中一個宿主節(jié)點(diǎn)和網(wǎng)內(nèi)其它節(jié)點(diǎn)之間添加一條內(nèi)部連接。

3.1.6 PFP模型

PFP模型［17］是由S.Zhou于2008年在IG模型的基礎(chǔ)上提出，稱為正向反饋優(yōu)先模型。Internet在AS級拓?fù)渲械墓?jié)點(diǎn)最大度kmax約等于節(jié)點(diǎn)總數(shù)的1／4，而IG和BA模型在節(jié)點(diǎn)最大度這個指標(biāo)上遠(yuǎn)遠(yuǎn)超過了這個值。根據(jù)Internet歷史數(shù)據(jù)，Pastor-

Satorras［18］和V′azquez［19］發(fā)現(xiàn)新節(jié)點(diǎn)與低連接度節(jié)點(diǎn)的連接傾向遵循線性優(yōu)先概率∏（i）=ki／∑jkj，

而Chen［20］發(fā)現(xiàn)高連接度節(jié)點(diǎn)的“吸引力”遠(yuǎn)高于低連接度節(jié)點(diǎn)。PFP模型在偏好連接概率上進(jìn)行了改進(jìn)：由原來的線性優(yōu)先改為非線性優(yōu)先，

∏（i）=k1+δlgki／∑jk1+δlgkj，δ∈0，[] 1以提高連接度高的節(jié)點(diǎn)的“吸引力”。

算法與IG模型相似，是從一個小的隨機(jī)網(wǎng)絡(luò)開始，反復(fù)執(zhí)行如下操作：

（1）以概率p∈（0，1），加入一個新節(jié)點(diǎn)，并以概率∏（i）與網(wǎng)絡(luò)中已有節(jié)點(diǎn)（稱宿主節(jié)點(diǎn)）連接，再在宿主節(jié)點(diǎn)與其它網(wǎng)內(nèi)節(jié)點(diǎn)之間添加一條內(nèi)部連接；

（2）以概率q∈（0，1-p），加入一個新節(jié)點(diǎn)，并以概率∏（i）與網(wǎng)絡(luò)中已有節(jié)點(diǎn)（稱宿主節(jié)點(diǎn)）連接，再在宿主節(jié)點(diǎn)與其它網(wǎng)內(nèi)節(jié)點(diǎn)之間添加兩條內(nèi)部連接；

（3）以概率1-p-q，加入一個新節(jié)點(diǎn)，并以概率∏（i）與網(wǎng)絡(luò)中已有的兩個宿主節(jié)點(diǎn)連接，再在其中一個宿主節(jié)點(diǎn)和網(wǎng)內(nèi)其它節(jié)點(diǎn)之間添加一條內(nèi)部連接。當(dāng)p=0.3、q=0.1時，PFP模型生成的拓?fù)浣咏鎸?shí)的AS拓?fù)洹?/p>

3.1.7 MPA模型

MPA（Multiclass Preferential Attachment）模型［21］是由加州大學(xué)的Srinivas Shakkottai等在2010年提出。MPA模型仍然基于連接偏好的原理，其所有參數(shù)都可從測量數(shù)據(jù)中獲取，這一點(diǎn)為模型的客觀性和驗(yàn)證上帶來了優(yōu)勢。與以往模型的不同，該模型的一個顯著改進(jìn)是注意區(qū)分節(jié)點(diǎn)的類型，分為ISP和非ISP節(jié)點(diǎn)，因此稱為多類偏好連接。但這種區(qū)分仍然顯得過于粗略，與我們在結(jié)構(gòu)演化中的討論存在差距。最后，作者基于對實(shí)際測量數(shù)據(jù)的分析，進(jìn)一步肯定連接偏好性是Internet演變的驅(qū)動力。

3.1.8 HOT模型

前面介紹的各種演化模型，其生長機(jī)理都是基于偏好連接，而且只有新節(jié)點(diǎn)和新連接的加入，沒有節(jié)點(diǎn)和邊的減少、連接的重新調(diào)整，這是不符合In

ternet的實(shí)際運(yùn)行情況的。基于節(jié)點(diǎn)度的模型都可以很好地吻合冪律分布這個特性，但它們的缺陷是，除MPA模型外，都忽視了AS之間連接建立的內(nèi)在因素，即商業(yè)關(guān)系?；诙鹊哪Ｐ捅M管也有演化能力，但這種演化方式很大程度上是帶主觀的假設(shè)，其目的就是符合冪律，因此缺乏充分的解析能力。

Chang等［22］將HOT（Highly Optimized Tolerance）模型應(yīng)用到AS級的拓?fù)浣ㄉ稀＜兇獾腍OT模型是一種多目標(biāo)的優(yōu)化方式：當(dāng)一個新節(jié)點(diǎn)加入網(wǎng)絡(luò)，它基于兩種目標(biāo)來選擇它要連接的節(jié)點(diǎn)（稱父節(jié)點(diǎn)），分別是最后距離（Last Mile）的連接成本和父節(jié)點(diǎn)核心度（node centrality）成本。前者以新節(jié)點(diǎn)和父節(jié)點(diǎn)之間的歐氏距離來計(jì)算，后者以父節(jié)點(diǎn)到其它節(jié)點(diǎn)的平均距離來計(jì)算。文中指出，provider-customer關(guān)系在拓?fù)涞墓?jié)點(diǎn)度分布特征中占主導(dǎo)地位，peer -peer關(guān)系可以忽略。另外，多穴（Multi-Homing）連接對于節(jié)點(diǎn)度分布也沒有影響?；谶@個分析，文中的建模主要針對provider-customer連接的。Internet的發(fā)展不是隨意的，而是在收益、資源成本和對風(fēng)險的承受這三者之間的一種平衡，是一種高度優(yōu)化設(shè)計(jì)的結(jié)果。

3.2 基于結(jié)構(gòu)的演化模型

自從1999年Faloutsos提出Internet節(jié)點(diǎn)度的分布也服從冪律后，基于節(jié)點(diǎn)度的拓?fù)淠Ｐ偷难芯垦杆侔l(fā)展起來。Internet拓?fù)浣Y(jié)構(gòu)主要由自治系統(tǒng)（AS）之間的連接關(guān)系來體現(xiàn)，這里AS被看成是節(jié)點(diǎn)。因此拓?fù)浣Y(jié)構(gòu)的演化要反映AS數(shù)量的增減、AS之間的連接關(guān)系的增減（或重連），以及不同類型的AS分布情況。圖2為Internet典型的傳統(tǒng)分層拓?fù)浣Y(jié)構(gòu)。

3.2.1 AS之間的關(guān)系分類

AS之間的關(guān)系可分為c2p（customer-provider）、p2p（peer-peer）、s2s（sibling-sibling）3類。在c2p關(guān)系中，customer AS需要向provider AS繳納它們之間發(fā)生的流量費(fèi)用；在p2p關(guān)系中，兩個AS自身或它們的customer之間的流量可以在它們之間免費(fèi)傳輸，但不能傳輸它們的provider及peer之間的流量；屬于s2s關(guān)系的AS往往屬于同一個管理組織，它們之間或它們的provider、customer之間的流量都可以在這些AS之間免費(fèi)傳輸。s2s這種關(guān)系是隨著Internet規(guī)模的擴(kuò)大，一個大公司可以同時擁有多個AS時出現(xiàn)，它們之間的關(guān)系一般并不體現(xiàn)商業(yè)利益關(guān)系。正是由于提供商之間這種復(fù)雜的利益關(guān)系，最終體現(xiàn)在Internet拓?fù)涞母叨葎討B(tài)變化中。

3.2.2 AS的類型

在基于節(jié)點(diǎn)度的拓?fù)淠Ｐ椭?，并不區(qū)分節(jié)點(diǎn)的類型，而實(shí)際的AS節(jié)點(diǎn)并不是等同的。AS節(jié)點(diǎn)的類型也決定了它在整個拓?fù)浣Y(jié)構(gòu)中的位置，如核心層、邊緣層等。根據(jù)業(yè)務(wù)類型可分為5類。

（1）企業(yè)客戶（EC）：處于網(wǎng)絡(luò)邊緣的組織、大學(xué)和公司，它們代表了大多數(shù)的用戶，不會再有自己的客戶AS。

（2）小型傳輸業(yè)務(wù)提供商（STP）：通常是區(qū)域ISP（包括國家傳輸網(wǎng)、科研網(wǎng)），提供Internet的接入服務(wù)和傳輸業(yè)務(wù)，目的是建立本地區(qū)域的客戶群。這些ISP之間通過優(yōu)化的對等連接，可以減少客戶的上行鏈路的傳輸成本。

（3）大型傳輸服務(wù)提供商（LTP）：具有極大的地域分布的國際級ISP。它們與其它ISP的對等連接僅為了可達(dá)性的需要，因此對等連接采取限制性策略。

（4）接入／托管服務(wù)提供商（AHP）：提供Internet接入（如DSL、撥號連接、租用線路等）、服務(wù)器托管業(yè)務(wù)的ISP。它們的客戶主要是沒有AS號的本地用戶和企業(yè)。

（5）內(nèi)容提供商（CP）：以提供付費(fèi)內(nèi)容為業(yè)務(wù)的供應(yīng)商，它們的目的是為了降低傳輸成本，所以采用開放的對等連接策略。

k-核的分解［23］是一種提取大規(guī)模網(wǎng)絡(luò)核心區(qū)域的新方法。Guo-Qing Zhang等利用k-核分解的方法研究了Internet的演化趨勢，發(fā)現(xiàn)：AS級的Internet規(guī)模增長很快，遵循摩爾定律，即N（t）～100.0283t～e0.0652t；與整個Internet拓?fù)湟?guī)模的指數(shù)級增大相比，k值越大的k-核，其規(guī)模隨時間變化得更穩(wěn)定；2003年后，與配置模型的預(yù)測相比，最大核數(shù)kmax非常穩(wěn)定；與主流Internet模型的預(yù)測相比，最大節(jié)點(diǎn)連接度相對穩(wěn)定；與隨機(jī)模型相比，Internet仍然屬于松散連接結(jié)構(gòu)；與隨機(jī)網(wǎng)絡(luò)相比，不管Internet整體上還是它的核心都呈現(xiàn)異配性。

最近由Hamed Haddadi等提出用帶權(quán)譜分布（Weighted Spectral Distribution，WSD）這個度量來分析Internet拓?fù)浣Y(jié)構(gòu)。研究表明：WSD可以很好地區(qū)分Internet的核心層和邊緣層；核心層與邊緣層的界限隨著Internet進(jìn)化，開始變得模糊；從圖3中可以看出，隨著核數(shù)的增加，高連接度的節(jié)點(diǎn)數(shù)2008年比2004增加，這意味著Internet中的對等連接增加，也反映出Internet的層次結(jié)構(gòu)的模糊化。

文獻(xiàn)［5］在對BGP數(shù)據(jù)的測量分析基礎(chǔ)上，對Internet拓?fù)涞难莼?guī)律進(jìn)行了有益的探索。作者提出兩個概念，通過測量發(fā)現(xiàn)的拓?fù)洌∣bservedTopology，OT）和真實(shí)的網(wǎng)絡(luò)拓?fù)洌≧eal Topology，RT）。發(fā)現(xiàn)了一個重要的演化規(guī)律：臨時性的路由動態(tài)變化對OT的影響隨著時間的推移呈指數(shù)遞減，而RT中的拓?fù)渥兓撕闼俪錾秃闼傧鰞煞N過程。同時又發(fā)現(xiàn)Internet規(guī)模的擴(kuò)大主要由處于AS拓?fù)溥吘壍挠脩艟W(wǎng)絡(luò)節(jié)點(diǎn)的出生和消亡引起，邊緣網(wǎng)絡(luò)和核心網(wǎng)絡(luò)存在不同的增長模式。核心網(wǎng)絡(luò)節(jié)點(diǎn)的增長速度緩慢，但相互間的連接變化卻非常頻繁，這種變化主要來自AS之間的peer-to-peer鏈路連接的重新調(diào)整。因此，研究AS的出生率、死亡率和增長率以及路由器和鏈路的失效模型，有利于建立真實(shí)的拓?fù)浒l(fā)生器，用于有效地模擬Internet的端到端行為。

隨著網(wǎng)絡(luò)新應(yīng)用的不斷涌現(xiàn)，文獻(xiàn)［24，25］通過對BGP路由和流量的測量，發(fā)現(xiàn)Internet結(jié)構(gòu)出現(xiàn)新的變化趨勢。文獻(xiàn)［24］發(fā)現(xiàn)40%～80%的BGP路徑經(jīng)過tier-2 ISP，從而認(rèn)為tier-2 ISP在拓?fù)溥B接性上開始扮演重要角色，區(qū)別于以往傳統(tǒng)上認(rèn)為樹型分層拓?fù)浣Y(jié)構(gòu)（見圖4）。文獻(xiàn)［25］對域間流量的分析也得出相似的結(jié)論，流量從核心層向外層轉(zhuǎn)移，也反映出拓?fù)浣Y(jié)構(gòu)的非樹形變化。

從傳統(tǒng)意義上的樹型分層拓?fù)浣Y(jié)構(gòu)向非樹型結(jié)構(gòu)的演變，主要原因來自新應(yīng)用、新的互聯(lián)網(wǎng)盈利模式的出現(xiàn)。繼web應(yīng)用之后，最近社會網(wǎng)絡(luò)和視頻內(nèi)容逐漸在Internet流量中居主導(dǎo)地位。經(jīng)濟(jì)因素的變化，包括IP地址租用費(fèi)用的連續(xù)下降，以廣告為支撐的信息量的增長，極大地改變了許多提供商的互連策略。新互聯(lián)網(wǎng)經(jīng)濟(jì)的出現(xiàn)，大的內(nèi)容提供商開始構(gòu)建自己的全球骨干網(wǎng)，并直接與自己的客戶網(wǎng)絡(luò)連接，轉(zhuǎn)移了超過5%的域間流量。由此可見，Internet的拓?fù)浣Y(jié)構(gòu)的演變，新應(yīng)用和經(jīng)濟(jì)因素起到非常重要的作用。

4 拓?fù)淠Ｐ偷尿?yàn)證

在本文的第2節(jié)中提到了驗(yàn)證模型的正確性是其中的一大困難。通過比較不同模型生成的拓?fù)涞慕y(tǒng)計(jì)特性，不一定能反映出模型的正確性。已有研究表明，相同的統(tǒng)計(jì)度量下，也可能存在不同的拓?fù)浣Y(jié)構(gòu)。同時，測量取得拓?fù)鋽?shù)據(jù)存在很多虛假信息，如節(jié)點(diǎn)和邊的消失與出現(xiàn)不一定與實(shí)際拓?fù)浣Y(jié)構(gòu)變化相符合。Ricardo Oliveira提出了一種與真實(shí)Inter

net比較節(jié)點(diǎn)／邊的生滅過程來驗(yàn)證模型的思路。理論模型的節(jié)點(diǎn)／邊的加入是由連接偏好來決定的，那么真實(shí)Internet是怎么樣呢？Ricardo Oliveira提出拓?fù)浠钚裕╨iveness）的概念來說明該問題。我們將真實(shí)的Internet拓?fù)溆肎real來表示，通過測量等手段提取出來的拓?fù)浞Q為Gobsv。Gobsv對于我們是可見的，而Greal則是不可見的。如圖5所示，箭頭表示BGP路徑或trace route探測方向。

由圖5發(fā)現(xiàn)，Greal和Gobsv是不一致的，即使在同一個Gobsv中，t0到t1和t2到t3也是不一致的。其中t0到t1的不一致是由動態(tài)路由引起的，而t2到t3的不一致是由Greal拓?fù)浣Y(jié)構(gòu)發(fā)生變化引起的。同時又可觀察到B-C這條邊在Gobsv中，從t0到t3的過程中經(jīng)歷了消失-出現(xiàn)-消失的過程，而實(shí)際上它一直存在。因此我們希望能區(qū)分出這些邊或接點(diǎn)在Gobsv的出現(xiàn)／消失是由于動態(tài)路由還是真實(shí)的拓?fù)涓淖円鸬?，這個問題就是拓?fù)浠钚詥栴}。為了區(qū)分這兩種不同，將Greal中的拓?fù)湓兀ü?jié)點(diǎn)／邊）的加入／移除稱為出生（birth）／死亡（death），而將Gobsv中的元素加入／移除稱為出現(xiàn)（appearance）／消失（disappearance）。研究發(fā)現(xiàn)，Greal拓?fù)湓氐某錾劳龊虶obsv中的元素出現(xiàn)／消失并不對應(yīng)。因此我們要去發(fā)現(xiàn)真正由于元素“死亡”而“消失”、“出生”而“出現(xiàn)”的情況，篩除因動態(tài)路由等原因造成的同一個元素在不同時刻反復(fù)消失又出現(xiàn)的干擾情況（實(shí)際在Greal中一直存在）。通過觀察Gobsv發(fā)現(xiàn)Greal中的節(jié)點(diǎn)／邊的“死亡”和“出生”規(guī)律來驗(yàn)證理論上的拓?fù)淠Ｐ偷纳L過程，才能取得合理的結(jié)論。

Srinivas Shakkottai等提出一個可以驗(yàn)證的模型應(yīng)該符合如下的條件：模型盡可能簡單，參數(shù)盡可能少；所有的參數(shù)必須是可測量的，排除主觀假設(shè)；易用分析手段來處理。因此，作為拓?fù)浣Ｕ?，在建模過程中始終能考慮這些最優(yōu)階段的驗(yàn)證要求，無疑對模型的有效性、真實(shí)性、合理性是有積極意義的。

5 存在的問題和發(fā)展趨勢

Internet拓?fù)浣淖畛醯碾S機(jī)模型到結(jié)構(gòu)模型，隨著復(fù)雜網(wǎng)絡(luò)的無標(biāo)度性質(zhì)的發(fā)現(xiàn)，基于度的模型應(yīng)運(yùn)而生。研究表明，基于度的模型不但很好地反映出了局部特征，同時也符合Internet的結(jié)構(gòu)特征，但反之不成立。盡管有研究表明，網(wǎng)絡(luò)的核心層與邊緣層在結(jié)構(gòu)上有模糊的傾向，但仍然不能忽視Internet整體上仍然是一個等級網(wǎng)絡(luò)的事實(shí)。因此，一個好的拓?fù)渖善?，不僅要考慮局部特征，也要兼顧整體的結(jié)構(gòu)特征。

Internet拓?fù)湓诮Y(jié)構(gòu)上的演變對我們以往的一些靜態(tài)統(tǒng)計(jì)度量，如聚簇系數(shù)、平均距離等，也提出了挑戰(zhàn)：這些統(tǒng)計(jì)度量是否還存在？在數(shù)值上又有哪些變化？這些都要求我們不斷地去更新拓?fù)錅y量方法，獲取更新的認(rèn)識。對Internet拓?fù)溲芯康淖罱K目的是能夠預(yù)測未來，但這恰恰也是最難的。Internet拓?fù)鋵τ诰W(wǎng)絡(luò)領(lǐng)域的其它研究起著關(guān)鍵性的基礎(chǔ)作用，可應(yīng)用于網(wǎng)絡(luò)模擬、研究網(wǎng)絡(luò)病毒傳播機(jī)理、網(wǎng)絡(luò)協(xié)議性能等。

將統(tǒng)計(jì)物理的熵概念引入對Internet拓?fù)浣Y(jié)構(gòu)的統(tǒng)計(jì)特性研究，將是我們下階段需要研究的方向。尤其是非廣延量Tsallis熵［26］對于研究Internet這樣具有明顯異配性、冪律特征的系統(tǒng)，是一個非常合適的統(tǒng)計(jì)量。

最后，我們發(fā)現(xiàn)目前大量的工作集中在對物理拓?fù)浣Y(jié)構(gòu)的研究，這樣的工作吸引了大量的數(shù)學(xué)、物理等學(xué)科的學(xué)者參與。從計(jì)算機(jī)網(wǎng)絡(luò)學(xué)科看，Internet是由多層協(xié)議構(gòu)成的異質(zhì)網(wǎng)絡(luò)，僅對物理連接性的研究是不夠的，在不同的協(xié)議層需要的拓?fù)湫畔⑵鋵?shí)是不一致的。因此我們提出分層拓?fù)浣５乃悸?，分別在物理層（物理介質(zhì)連接性）、網(wǎng)絡(luò)層（路由路徑構(gòu)成）、應(yīng)用層（P2P、覆蓋網(wǎng)、虛擬網(wǎng)路由路徑構(gòu)成）測量、分析和研究構(gòu)建各種邏輯拓?fù)涞姆椒ǎ@樣的研究成果會對網(wǎng)絡(luò)研究界更具實(shí)用意義。我們希望這些研究成果可應(yīng)用于下階段關(guān)于大規(guī)模虛擬網(wǎng)模擬的研究。

6 結(jié)論

本文詳細(xì)介紹了Internet的靜態(tài)拓?fù)淠Ｐ秃蛣討B(tài)拓?fù)淠Ｐ?，并對拓?fù)淠Ｐ驮诠?jié)點(diǎn)度和結(jié)構(gòu)方面的演化進(jìn)行了詳細(xì)的討論，最后分析了存在的問題并提出了以后的發(fā)展方向，希望為Internet拓?fù)浣Ｌ峁┮欢ǖ膮⒖肌?/p>

［1］FaloutsosM，F(xiàn)aloutsos P，F(xiàn)aloutsos C.On power-law relationships of the internet topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，1999：251-262.

［2］Barab′asi A，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［3］Zhou S，Mondragon R J.The rich-club phenomenon in the Internet topology［J］.IEEECommunication Letters，2004，8（3）：180-182.

［4］Mahadevan P，Krioukov D，F(xiàn)all K，etal.Systematic topology analysis and generation using degree correlations［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication. New York：ACM，2006：135-146.

［5］Oliveira R，Zhang B，Zhang L.Observing the evolution of Internet AS topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，2007：313-324.

［6］Shakkottai S，F(xiàn)omenkov M，Koga R，et al.Evolution of the Internet AS-Level Ecosystem［J］.European Physical JournalB，2010，74（2）：271-278.

［7］Zhang GQ，Yang Q F，Cheng SQ，et al.Evolution of the Internet and its cores［J］.New Journal of Physics，2008，10（12）：123027.

［8］Krioukov D，Chung F，Claffy K，et al.2007 The workshop on Internet topology（WIT）report［J］.ACM SIGCOMM Computer Communication Review，2007，37（1）：69-73.

［9］Li L，Alderson D，WillingerW，etal.A first-principlesapproach to understanding the Internet′s router-level topology［J］.ACM SIGCOMM Computer Communication Review，2004，34（4）：3-14.

［10］Haddadi H，Uhlig S，Moore A，et al.Modeling internet topology dynamics［J］.Computer Communication Review，2008，38（2）：65-68.

［11］MahadeVan P，Krioukov D，F(xiàn)all K.Systematic topology analysisand generation using degree correlations［J］.SIGCOMM，2006，36（4）：135-146.

［12］Réka Albert，Albert-LászlóBarabási.Topology of Evolving Networks：Local Events and Universality［J］.Physical Review Letters，2000，85（24）：5234-5237.

［13］Tian Bu，Don Towsley.On Distinguishing between Internet Power Law Topology Generators［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEEComputer and Communications Societies.New York：IEEE，2002：638-647.

［14］Chen Q，Chang H，Govindan R，etal.The Origin of Power Laws in Internet Topologies Revisited［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEE Computer and Communications Societies.New York：IEEE，2002：608-617.

［15］BianconiG，CaldarelliG，Capocci A.Number of h-cycles in the Internet at the autonomous system level［EB／OL］. 2003-10-15［2003-10-16］.http：arxiv.org／condmat／0310339.

［16］Zhou S，Mondragon R J.Towards modeling the Internet topology：the interactive growth model［J］.Teletraffic Science and Engineering，2003（5）：121-130.

［17］Zhou S，Mondragon R J.Accurately modeling the Internet topology［J］.Physical Review E，2004，70（6）：106-108.

［18］Pastor-Satorras R，V′azquez A，Vespignani A.Dynamical and Correlation Properties of the Internet［J］.Physical Review Letters，2001，87（25）：1-4.

［19］V′azquez A，Pastor-Satorras R，Vespignani A.Largescale topological and dynamical properties of Internet［J］. Physical Review E，2001，65（6）：1-13.

［20］Chen Q，Chang H，Govindan R，etal.The origin of power laws in internet topologies revisited［C］／／Proceedings of the Twenty-First Annual JointConference of the IEEEComputer and Communications.［S.l.］：IEEE，2002：608-617.

［21］Shakkottai S，F(xiàn)omenkov M，Koga R，etal.Evolution of the Internet AS-Level Ecosystem［J］.European Physical Journal B，2010，74（2）：271-278.

［22］Chang H，Jamin S，WillingerW.Internet connectivity at the AS-level：An optimization-driven modeling approach［C］／／Proceedings of the ACM SIGCOMM 2003Workshops. Karlsruhe，Germany：ACM，2003：33-46.

［23］Pittel B，Spencer J，Wormald N.Sudden emergence of a giant k-core in a random graph［J］.Journal of Combinatorial Theory B，1996，67（1）：111-151.

［24］Hiroshi Fujinoki，Andrew Hauck.Analysis on the Trend of Recent Changes in the Internet Structure：Departing from the Long-Assumed Tree-Structure Model［C］／／Proceedings of the 8th International Conference on Computing，Communication and Control Technology.Orland，F(xiàn)lorida，USA：［s.n.］，2010.

［25］Craig Labovitz，Scott Iekel-Johnson，Danny McPherson，et al.Internet Inter-Domain Traffic［C］／／Proceedings of the ACM SIGCOMM 2010 Conference on SIGCOMM.New York：ACM，2010：75-86.

［26］Tsallis C.Introduction to nonextensive statisticalmechanics—approaching a complex world［M］.New York：Springer，2009.

GUANXiao-huiwas born in Luohe，Henan Province，in 1977. She received the M.S.degree from Zhejiang University in 2005.She is now a lecturer.Her research direction is networkmultimedia.

Email：guanxh＠zjwchc.com

錢亞冠（1976—），男，浙江嵊州人，2005年于浙江大學(xué)計(jì)算機(jī)學(xué)院獲碩士學(xué)位，現(xiàn)為講師，主要從事計(jì)算機(jī)網(wǎng)絡(luò)建模方面的研究；

QIAN Ya-guan was born in Shengzhou，Zhejiang Province，in 1976.He received the M.S.degree from Zhejiang University in 2005.He is now a lecturer.His research concerns computer networkmodeling.

周志敏（1966—），女，河北保定人，碩士，副教授，主要從事計(jì)算機(jī)硬件的研究和開發(fā)。

ZHOU Zhi-min was born in Baoding，Hebei Province，in 1966.She is now an associate professor with the M.S.degree.Her research concerns R＆D of computer hardware.

A Survey of Internet Topology Modeling and Evolution

GUAN Xiao-hui1，QIAN Ya-guan2，ZHOU Zhi-min1
（1.Department of Computer and Information Enginering，ZhejiangWater Conservancy and Hydropower College，Hangzhou 310018，China；2.Science College，Zhejiang University of Science and Technology，Hangzhou 310023，China）

It iswell known that clearly learning the realistic Internet topology and its evolution trend will play an important role in the research of next generation network and the operatingmanagement.This papermakes a comprehensive survey of the topology evolution based on node degree and structure，and reviews static topology models and dynamic topology models.Finally，it proposes the future research directions，that are using Tsallis entropy to explore the topology statistics and using layered fashion to study the topology structure.

next generation network；Internet topologymodel；power-law；evolution；node degree；Tsallis entropy

Scientific Research Foundation of Zhejiang Educational Committee（Y201017457）

TP393.02

A

10.3969／j.issn.1001-893x.2011.11.025

關(guān)曉惠（1977—），女，河南漯河人，2005年于浙江大學(xué)計(jì)算機(jī)學(xué)院獲碩士學(xué)位，現(xiàn)為講師，主要研究方向?yàn)榫W(wǎng)絡(luò)多媒體；

1001-893X（2011）11-0121-08

2011-07-11；

2011-08-15

浙江省教育廳科研項(xiàng)目資助（Y201017457）