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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

（1）所有的測(cè)量都受到實(shí)驗(yàn)條件和觀測(cè)條件的限制，如觀測(cè)點(diǎn)的地理分布范圍、數(shù)量，被探測(cè)節(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)該將測(cè)量的目標(biāo)放到具體的地理區(qū)域，通過(guò)比較不同的地理區(qū)域和社會(huì)經(jīng)濟(jì)環(huán)境下的數(shù)據(jù)去區(qū)分Internet在全局核心和局部區(qū)域的不同特征。

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

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

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

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

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

由于缺乏對(duì)真實(shí)Internet拓?fù)涞牧私?，以及測(cè)量方法的局限和拓?fù)涞膭?dòng)態(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í)性和典型性之間的界限是目前還無(wú)法解決的問(wèn)題。

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

（3）目前已經(jīng)存在很多拓?fù)涠攘浚⒉皇敲總€(gè)都與Internet的拓?fù)湎嚓P(guān)，選擇哪些拓?fù)涠攘咳ヲ?yàn)證模型是一個(gè)目前還沒(méi)解決的問(wèn)題。

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

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

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

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

3.1.1 BA模型

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

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

（1）增長(zhǎng)：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始，每次加入一個(gè)新的節(jié)點(diǎn)，并連接到m個(gè)已存在的節(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］，是對(duì)BA模型的擴(kuò)展。AB模型的拓?fù)溲莼瘉?lái)自于新節(jié)點(diǎn)的加入、新邊的加入和邊的重新連接。具體算法是從m0個(gè)孤立的節(jié)點(diǎn)開(kāi)始，每一步執(zhí)行下面3個(gè)步驟中的一個(gè)：

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

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

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

（3）以概率1-p-q增加一個(gè)新節(jié)點(diǎn)，以概率∏ab（kj）與網(wǎng)絡(luò)中已存在的m個(gè)節(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á)了兩個(gè)“小世界”模型的聚簇特性和特征路徑長(zhǎng)度。經(jīng)過(guò)觀察，發(fā)現(xiàn)Internet節(jié)點(diǎn)比BA模型線性優(yōu)先連接更傾向于連接到連接度高的節(jié)點(diǎn)上，因此提出了廣義線性優(yōu)先的方法。另外，文獻(xiàn)［14］的研究表明，Internet在AS級(jí)很少發(fā)生重連（rewiring）操作。GLP模型去除了AB模型的重連操作，算法與AB模型相似，是從一個(gè)有m0個(gè)節(jié)點(diǎn)、m0-1條邊連接的網(wǎng)絡(luò)開(kāi)始，首先以概率p增加m≤m0條新邊，新邊兩端的每個(gè)節(jié)點(diǎn)以概率

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

3.1.4 GNG模型

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

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

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

3.1.5 IG模型

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

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

（1）以概率p∈（0，1），加入一個(gè)新節(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，加入一個(gè)新節(jié)點(diǎn)，并以概率∏（ki）與網(wǎng)絡(luò)中已有的兩個(gè)宿主節(jié)點(diǎn)連接，再在其中一個(gè)宿主節(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級(jí)拓?fù)渲械墓?jié)點(diǎn)最大度kmax約等于節(jié)點(diǎn)總數(shù)的1／4，而IG和BA模型在節(jié)點(diǎn)最大度這個(gè)指標(biāo)上遠(yuǎn)遠(yuǎn)超過(guò)了這個(gè)值。根據(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)：由原來(lái)的線性優(yōu)先改為非線性優(yōu)先，

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

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

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

3.1.7 MPA模型

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

3.1.8 HOT模型

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

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

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

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

自從1999年Faloutsos提出Internet節(jié)點(diǎn)度的分布也服從冪律后，基于節(jié)點(diǎn)度的拓?fù)淠Ｐ偷难芯垦杆侔l(fā)展起來(lái)。Internet拓?fù)浣Y(jié)構(gòu)主要由自治系統(tǒng)（AS）之間的連接關(guān)系來(lái)體現(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)系中，兩個(gè)AS自身或它們的customer之間的流量可以在它們之間免費(fèi)傳輸，但不能傳輸它們的provider及peer之間的流量；屬于s2s關(guān)系的AS往往屬于同一個(gè)管理組織，它們之間或它們的provider、customer之間的流量都可以在這些AS之間免費(fèi)傳輸。s2s這種關(guān)系是隨著Internet規(guī)模的擴(kuò)大，一個(gè)大公司可以同時(shí)擁有多個(gè)AS時(shí)出現(xiàn)，它們之間的關(guān)系一般并不體現(xiàn)商業(yè)利益關(guān)系。正是由于提供商之間這種復(fù)雜的利益關(guān)系，最終體現(xiàn)在Internet拓?fù)涞母叨葎?dòng)態(tài)變化中。

3.2.2 AS的類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 存在的問(wèn)題和發(fā)展趨勢(shì)

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

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

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

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

6 結(jié)論

本文詳細(xì)介紹了Internet的靜態(tài)拓?fù)淠Ｐ秃蛣?dòng)態(tài)拓?fù)淠Ｐ停?duì)拓?fù)淠Ｐ驮诠?jié)點(diǎn)度和結(jié)構(gòu)方面的演化進(jìn)行了詳細(xì)的討論，最后分析了存在的問(wèn)題并提出了以后的發(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

錢(qián)亞冠（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ī)硬件的研究和開(kāi)發(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）