Internet-網(wǎng)絡(luò)解析課件

Internet網(wǎng)絡(luò)

6/4/2023結(jié)構(gòu)安排1因特網(wǎng)介紹

1.1因特網(wǎng)概述;1.2因特網(wǎng)發(fā)展的三個階段

1.3因特網(wǎng)的組成;1.4計算機網(wǎng)絡(luò)中的路由選擇算法

1.5因特網(wǎng)的路由選擇協(xié)議2Internet的拓?fù)涮匦?.1增長特性;2.2富人俱樂部特性和優(yōu)先連接特性2.3冪律分布;2.4層次性;2.5異配性;2.6核數(shù);2.7介數(shù)3Internet拓?fù)洚a(chǎn)生器6/4/20231.1因特網(wǎng)(Internet)概述internet（互聯(lián)網(wǎng)）是泛指由多個計算機網(wǎng)絡(luò)互連而成的計算機網(wǎng)絡(luò)；Internet（因特網(wǎng)）是指當(dāng)前全球最大的、開放的、由眾多網(wǎng)絡(luò)相互連接而成的特定計算機網(wǎng)絡(luò)，它采用TCP/IP協(xié)議族，且其前身是美國的ARPANET。進入20世紀(jì)90年代以后，以因特網(wǎng)為代表的計算機網(wǎng)絡(luò)得到了飛速的發(fā)展。已從最初的教育科研網(wǎng)絡(luò)逐步發(fā)展成為商業(yè)網(wǎng)絡(luò)。6/4/2023(a)(b)網(wǎng)絡(luò)互聯(lián)網(wǎng)（網(wǎng)絡(luò)的網(wǎng)絡(luò)）結(jié)點鏈路6/4/2023主機因特網(wǎng)6/4/20231.2因特網(wǎng)發(fā)展的三個階段第一階段是從單個網(wǎng)絡(luò)ARPANET向互聯(lián)網(wǎng)發(fā)展的過程。1983年TCP/IP協(xié)議成為ARPANET上的標(biāo)準(zhǔn)協(xié)議。人們把1983年作為因特網(wǎng)的誕生時間。6/4/2023三級結(jié)構(gòu)的因特網(wǎng)第二階段的特點是建成了三級結(jié)構(gòu)的因特網(wǎng)。三級計算機網(wǎng)絡(luò)，分為主干網(wǎng)、地區(qū)網(wǎng)和校園網(wǎng)（或企業(yè)網(wǎng)）。6/4/2023多層次ISP結(jié)構(gòu)的因特網(wǎng)第三階段的特點是逐漸形成了多層次ISP結(jié)構(gòu)的因特網(wǎng)。出現(xiàn)了因特網(wǎng)服務(wù)提供者ISP(InternetServiceProvider)。6/4/2023用戶因特網(wǎng)ISP1ISP2因特網(wǎng)服務(wù)提供者用戶通過ISP上網(wǎng)根據(jù)提供服務(wù)的覆蓋面積大小以及所擁有的IP地址數(shù)目的不同，ISP也分成為不同的層次。6/4/2023一級ISP一級ISP第一層

ISP大公司本地

ISP大公司大公司公司本地

ISP本地

ISP校園網(wǎng)校園網(wǎng)校園網(wǎng)校園網(wǎng)第二層

ISP第二層

ISPNAPNAPAB主機A→本地ISP→第二層ISP→NAP→第一層ISP→NAP→第二層ISP→本地ISP→主機B第一層

ISP第二層

ISP本地

ISP本地

ISP本地

ISP本地

ISP第一層

ISP第一層第二層第三層本地

ISP第二層

ISP本地

ISP本地

ISP本地

ISP本地

ISP第二層

ISP本地

ISP本地

ISP第二層

ISP6/4/2023因特網(wǎng)的發(fā)展情況概況網(wǎng)絡(luò)數(shù)主機數(shù)用戶數(shù)管理機構(gòu)數(shù)198010102

1021001990103105106101

2000105107108102

20051061081091036/4/20231.3因特網(wǎng)的組成從因特網(wǎng)的工作方式上看，可以劃分為以下的兩大塊：(1)邊緣部分由所有連接在因特網(wǎng)上的主機組成。這部分是用戶直接使用的，用來進行通信（傳送數(shù)據(jù)、音頻或視頻）和資源共享。(2)核心部分由大量網(wǎng)絡(luò)和連接這些網(wǎng)絡(luò)的路由器組成。這部分是為邊緣部分提供服務(wù)的（提供連通性和交換）。6/4/2023因特網(wǎng)的核心部分因特網(wǎng)的邊緣部分主機網(wǎng)絡(luò)路由器因特網(wǎng)的邊緣部分與核心部分6/4/2023因特網(wǎng)的核心部分因特網(wǎng)的核心部分是由許多網(wǎng)絡(luò)和把它們互連起來的路由器組成，而主機處在因特網(wǎng)的邊緣部分。在因特網(wǎng)核心部分的路由器之間一般都用高速鏈路相連接，而在網(wǎng)絡(luò)邊緣的主機接入到核心部分則通常以相對較低速率的鏈路相連接。主機的用途是為用戶進行信息處理的，并且可以和其他主機通過網(wǎng)絡(luò)交換信息。路由器的用途則是用來轉(zhuǎn)發(fā)分組的，即進行分組交換的。6/4/2023路由器在路由器中的輸入和輸出端口之間沒有直接連線。路由器處理分組的過程是：把收到的分組先放入緩存（暫時存儲）；查找轉(zhuǎn)發(fā)表，找出到某個目的地址應(yīng)從哪個端口轉(zhuǎn)發(fā)；把分組送到適當(dāng)?shù)亩丝谵D(zhuǎn)發(fā)出去。

6/4/20231.4計算機網(wǎng)絡(luò)中的路由選擇算法根據(jù)路由算法是否能隨網(wǎng)絡(luò)的通信量和拓?fù)渥赃m應(yīng)地進行調(diào)整，路由算法分為：自適應(yīng)路由算法（靜態(tài)路由算法）非自適應(yīng)路由算法（動態(tài)路由算法）

a自適應(yīng)可從時間和空間兩方面進行調(diào)整。

b自適應(yīng)路由選擇策略是每個結(jié)點周期性地從相鄰的結(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息，同時也將本結(jié)點做出的決定周期性地通知周圍的各個結(jié)點。以使這些結(jié)點不斷地根據(jù)網(wǎng)絡(luò)新的狀態(tài)更新其路由選擇決定。6/4/20231.5因特網(wǎng)的路由選擇協(xié)議因特網(wǎng)采用自適應(yīng)路由選擇協(xié)議。并且由于下述兩個原因，因特網(wǎng)采用分層次的路由選擇協(xié)議：（1）因特網(wǎng)的規(guī)模特別大。如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)該怎樣到達，則這種路由表將非常大，處理起來也太花時間。而所有這些路由器之間交換路由信息所需的帶寬就會使通信鏈路飽和。（2）許多單位不愿意外界了解自己單位網(wǎng)絡(luò)的布局細(xì)節(jié)和本部分所采用的路由選擇協(xié)議，但同時還希望連接在因特網(wǎng)上。6/4/2023自治系統(tǒng)AS

(AutonomousSystem)自治系統(tǒng)AS的定義：在單一的技術(shù)管理下的一組路由器，而這些路由器使用一種AS內(nèi)部的路由選擇協(xié)議和共同的度量以確定分組在該AS內(nèi)的路由，同時還使用一種AS之間的路由選擇協(xié)議用以確定分組在AS之間的路由?，F(xiàn)在對自治系統(tǒng)AS的定義是強調(diào)下面的事實：盡管一個AS使用了多種內(nèi)部路由選擇協(xié)議和度量，但重要的是一個AS對其他AS表現(xiàn)出的是一個單一的和一致的路由選擇策略。6/4/2023自治系統(tǒng)AS間采用BGP協(xié)議BGP發(fā)言人BGP發(fā)言人BGP發(fā)言人BGP發(fā)言人BGP發(fā)言人AS1AS3AS2AS5AS46/4/20232Internet的拓?fù)涮匦?/p>

針對不同的預(yù)測和改善Internet性能的目的，建立合適的Internet拓?fù)淠Ｐ褪欠浅Ｖ匾摹，F(xiàn)在，對Internet的研究主要在AS層面和路由器層面。

Internet是一個典型的復(fù)雜網(wǎng)絡(luò)。下面針對AS層面的拓?fù)浣Y(jié)構(gòu)展開一些討論。6/4/20232.1增長特性網(wǎng)絡(luò)的規(guī)模在不斷的擴大。即網(wǎng)絡(luò)中隨著時間的前進，不斷地有新的結(jié)點和新的邊加入進來。見圖1：Internet增長性6/4/20232.2富人俱樂部特性和優(yōu)先連接特性Internet中少量的結(jié)點具有大量的邊，這些結(jié)點也稱為‘富結(jié)點’；它們傾向于彼此之間相互連接，構(gòu)成‘富人俱樂部’

富人俱樂部連通性它表示的是網(wǎng)絡(luò)中前r個度最大的結(jié)點之間，實際存在的邊數(shù)L與這r個結(jié)點之間總的可能存在的邊數(shù)的比值。如圖2：富人俱樂部所示

6/4/2023優(yōu)先連接特性：即新的結(jié)點更傾向于與那些具有較高連接度和很好適應(yīng)度的‘大’結(jié)點相連接。6/4/20232.3冪律分布通過研究AS層面Internet的統(tǒng)計數(shù)據(jù),Faloutsos三兄弟指出AS層面Internet拓?fù)錆M足以下四種冪律分布:冪律分布1:∝其中是節(jié)點v的度,是將網(wǎng)絡(luò)中節(jié)點按度降序排列節(jié)點V的秩,R是秩指數(shù)常數(shù)冪律分布2:∝其中表明度大于d的節(jié)點在整個網(wǎng)絡(luò)中所占的百分比,D是度指數(shù)常數(shù).可以推得R=1/D

6/4/2023冪律分布3:∝其中為網(wǎng)絡(luò)對應(yīng)的連接矩陣的特征值,i為將特征值按降序排列時的序列號.特征值指數(shù)和連接度指數(shù)D間存在近似關(guān)系冪律分布4:P(h)∝

其中P(h)為距離不超過h的節(jié)點對的數(shù)目,其中包括自節(jié)點對,并對其他節(jié)點對計數(shù)兩次,H是hop指數(shù)常數(shù),可以推得其中c=N+2M,N,M和分別為網(wǎng)絡(luò)節(jié)點數(shù),邊數(shù)和直徑.6/4/20232.4層次性Internet由大量的相互連接的AS系統(tǒng)組成,其中每個AS系統(tǒng)可以被看作Stub域或Transit域.Stub域僅承載那些起源于或終止于域內(nèi)的通信量;stub域通常是LANTransit域沒有這種限制,它的目的是有效地相互連接Stub域.Transit域一般是WAN,MAN,被看作是服務(wù)供應(yīng)商.Stub節(jié)點連接一個或多個Transit節(jié)點,起源于一個stub節(jié)點的路徑必須橫貫?zāi)切┳鳛楣?yīng)商的transit節(jié)點.圖P533-86/4/20232.5異配性結(jié)論:在Internet網(wǎng)中:Internet網(wǎng)上度數(shù)高的節(jié)點之間連接比較緊密,即存在富人俱樂部現(xiàn)象,但其絕大多數(shù)鄰居節(jié)點的度數(shù)很低.見圖3：鄰居節(jié)點的平均度分布研究表明,通過計算前面所講過的同配性系數(shù)r,發(fā)現(xiàn)Internet網(wǎng)的r<0,即Internet網(wǎng)是異配網(wǎng)絡(luò).6/4/20232.6核數(shù)一個圖的K-核是指反復(fù)去掉度小于或等于K的節(jié)點后,所剩余的子圖.若一個節(jié)點存在于K-核,而在K+1核中被移去,那么此節(jié)點的核數(shù)為K.例如:包含N個節(jié)點的星形網(wǎng)絡(luò)的中心節(jié)點的度數(shù)為N-1,核數(shù)為0.節(jié)點核數(shù)的最大值稱為圖的核數(shù).節(jié)點的核數(shù)可以表明節(jié)點在核中的深度.圖4：Internet的節(jié)點核數(shù)與度數(shù)之間的關(guān)系：顯示了Internet拓?fù)鋽?shù)據(jù)的節(jié)點的核數(shù)與度數(shù)之間的關(guān)系.

由圖可以看出,當(dāng)度數(shù)較小時,兩者之間呈現(xiàn)冪律關(guān)系;當(dāng)節(jié)點度數(shù)大于100時,核數(shù)基本保持不變.6/4/20232.7介數(shù)介數(shù)衡量了通過網(wǎng)絡(luò)中該節(jié)點的最短路徑的數(shù)目.圖5：Internet的節(jié)點的標(biāo)準(zhǔn)化介數(shù)與度數(shù)之間的關(guān)系：顯示了三類Internet拓?fù)鋽?shù)據(jù)的節(jié)點的介數(shù)與度數(shù)之間的關(guān)系.6/4/2023Internet拓?fù)洚a(chǎn)生器隨機圖產(chǎn)生器結(jié)構(gòu)產(chǎn)生器基于連接度的產(chǎn)生器6/4/2023Inet

拓?fù)洚a(chǎn)生器Inet采用PLGR算法與優(yōu)先附著實現(xiàn)冪律,重視連通性(最小節(jié)點覆蓋),并根據(jù)最大團尺寸和聚類系數(shù)做了優(yōu)化.先后有Inet1,Inet2,Inet3版本.Inet3建模過程:(1)從用戶那里獲得節(jié)點個數(shù)N和N個節(jié)點中度為1的節(jié)點所占的比例k.(2)根據(jù)下式計算Internet從1997年11月份的節(jié)點個數(shù)增長到N所需的月份數(shù)t:N=exp(0.0298t+7.9842)(3)定義和:是度為1的節(jié)點的集合,為前三個最大度的節(jié)點的集合,為除去中節(jié)點以外的其他節(jié)點.(4)代入t,根據(jù)來計算中節(jié)點的度分布,其中a,b,c為已知常數(shù).Internet上度為1的節(jié)點所占比例基本是在30%左右.根據(jù)度-秩指數(shù)增長律來計算中節(jié)點的度分布,其中p,q為已知常數(shù).6/4/2023(5)在度大于1的節(jié)點間構(gòu)建一個生成樹:令G為所要產(chǎn)生的圖,初始為空集;不在G中的度大于1的節(jié)點i與G中的一個節(jié)點j相連的概率為其中為節(jié)點i的度,為度的頻率.(6)按照步驟(5)中的概率式,將中的kN個節(jié)點連接到G中的節(jié)點上.(7)從具有最大度的節(jié)點開始,連接G中仍剩余的自由度;在進行這些連接時,以步驟(5)中的概率式隨機地選取有著自由度的節(jié)點.6/4/2023Brite產(chǎn)生器BRITE期望能構(gòu)建一個具有代表性,包容性和交互性的拓?fù)洚a(chǎn)生器.其中,代表性指期望反映Internet實際拓?fù)涞亩鄠€方面,如層次性、連接度分布等；包容性指將多個已經(jīng)存在的產(chǎn)生器的功能融合在一個拓?fù)洚a(chǎn)生器當(dāng)中;交互性指為廣泛使用的仿真應(yīng)用提供更好的接口界面.Brite生成器主要有4步:在平面上放置節(jié)點;在節(jié)點間建立內(nèi)部邊;為每個拓?fù)湓卦O(shè)置屬性;以一定的形式輸出此拓?fù)浣Y(jié)構(gòu).具體過程如下:(1)首先將平面分成HS×HS個正方形，每個正方形被進一步分成LS×LS個小的正方形，每個小