路由協(xié)議-路由與交換課件

路由和交換技術(shù)第六章路由和交換技術(shù)第六章第6章路由協(xié)議本章主要內(nèi)容路由項(xiàng)分類；路由協(xié)議基礎(chǔ)；RIP；OSPF；BGP。第6章路由協(xié)議本章主要內(nèi)容26.1路由項(xiàng)分類本講主要內(nèi)容直連路由項(xiàng)靜態(tài)路由項(xiàng)動(dòng)態(tài)路由項(xiàng)靜態(tài)路由項(xiàng)缺陷6.1路由項(xiàng)分類本講主要內(nèi)容3一、直連路由項(xiàng)R1路由表路由器自動(dòng)生成的用于指明通往這些直接連接的網(wǎng)絡(luò)的傳輸路徑的路由項(xiàng)稱為直連路由項(xiàng)。

一、直連路由項(xiàng)R1路由表路由器自動(dòng)生成的用于指明通往這些直接4二、靜態(tài)路由項(xiàng)路由器建立路由表的過(guò)程就是找出通往各個(gè)子網(wǎng)的最短路徑的過(guò)程，在RIP中，最短路徑就是經(jīng)過(guò)跳數(shù)最少的路徑R5路由表二、靜態(tài)路由項(xiàng)路由器建立路由表的過(guò)程就是找出通往各個(gè)子網(wǎng)的最5三、動(dòng)態(tài)路由項(xiàng)路由協(xié)議路由協(xié)議就是一組用于規(guī)范路由消息的格式、路由器之間路由消息交換過(guò)程、路由器對(duì)路由消息的處理流程的規(guī)則路徑距離路徑距離可以是傳輸路徑經(jīng)過(guò)的路由器跳數(shù)，也可以是其他衡量傳輸路徑的參數(shù)，如傳輸路徑的物理距離、傳輸路徑經(jīng)過(guò)的物理鏈路的帶寬等三、動(dòng)態(tài)路由項(xiàng)路由協(xié)議6四、靜態(tài)路由項(xiàng)缺陷一是大型互連網(wǎng)絡(luò)很難做到各個(gè)路由器配置的靜態(tài)路由項(xiàng)一致二是互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)變化的三是為了容錯(cuò)，各個(gè)網(wǎng)絡(luò)之間存在多條傳輸路徑四是實(shí)際網(wǎng)絡(luò)配置靜態(tài)路由項(xiàng)的工作量是無(wú)法想象的四、靜態(tài)路由項(xiàng)缺陷一是大型互連網(wǎng)絡(luò)很難做到各個(gè)路由器配置的靜76.2路由協(xié)議基礎(chǔ)本講主要內(nèi)容路由協(xié)議分類路由協(xié)議要求距離向量路由協(xié)議鏈路狀態(tài)路由協(xié)議6.2路由協(xié)議基礎(chǔ)本講主要內(nèi)容8一、路由協(xié)議分類距離向量路由協(xié)議距離向量路由協(xié)議要求每一個(gè)路由器定期向其相鄰路由器公告全部路由項(xiàng)，由于每一項(xiàng)路由項(xiàng)用于指明通往某個(gè)網(wǎng)絡(luò)或網(wǎng)絡(luò)前綴相同的一組網(wǎng)絡(luò)的傳輸路徑，路由器擁有某項(xiàng)路由項(xiàng)，意味著該路由器已經(jīng)建立通往目的網(wǎng)絡(luò)字段指定的一個(gè)或一組網(wǎng)絡(luò)的傳輸路徑。鏈路狀態(tài)路由協(xié)議互連網(wǎng)絡(luò)中的某個(gè)路由器獲得所有其他路由器的鏈路狀態(tài)信息，就可構(gòu)建互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并在此基礎(chǔ)上計(jì)算出該路由器到達(dá)所有網(wǎng)絡(luò)的最短路徑。

一、路由協(xié)議分類距離向量路由協(xié)議9內(nèi)部網(wǎng)關(guān)協(xié)議用于建立自治系統(tǒng)內(nèi)傳輸路徑的路由協(xié)議稱作內(nèi)部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議用于建立自治系統(tǒng)間傳輸路徑的路由協(xié)議稱作外部網(wǎng)關(guān)協(xié)議一、路由協(xié)議分類內(nèi)部網(wǎng)關(guān)協(xié)議一、路由協(xié)議分類10一、路由協(xié)議分類互連網(wǎng)絡(luò)分成多個(gè)自治系統(tǒng)；用于建立自治系統(tǒng)內(nèi)端到端路徑的路由協(xié)議稱為內(nèi)部網(wǎng)關(guān)協(xié)議；用于建立自治系統(tǒng)間端到端路徑的路由協(xié)議稱為外部網(wǎng)關(guān)協(xié)議。一、路由協(xié)議分類互連網(wǎng)絡(luò)分成多個(gè)自治系統(tǒng)；11二、路由協(xié)議要求建立完整路由表選擇最佳路由簡(jiǎn)單、開(kāi)銷小實(shí)時(shí)反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化具有穩(wěn)定性快速收斂二、路由協(xié)議要求建立完整路由表12三、距離向量路由協(xié)議本講主要內(nèi)容距離向量路由協(xié)議創(chuàng)建路由表過(guò)程距離向量路由協(xié)議特性三、距離向量路由協(xié)議本講主要內(nèi)容131．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程141．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1、R2和R3自動(dòng)生成的直連路由項(xiàng)1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1、R2和R3自動(dòng)15路由器R2發(fā)送給路由器R1的路由消息如下{（192.1.2.0/24,0）（192.1.6.0/30,0）（192.1.4.0/30,0）192.1.4.2}路由器R3向路由器R1發(fā)送路由消息{（192.1.3.0/24,0）（192.1.5.0/30,0）（192.1.6.0/30,0）192.1.5.2}1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R2發(fā)送給路由器R1的路由消息如下{（192.1.2.161．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1完整路由表1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1完整路由表172．距離向量路由協(xié)議特性周期性廣播全部路由項(xiàng)容易發(fā)生路由環(huán)路實(shí)時(shí)性差設(shè)置觸發(fā)機(jī)制設(shè)置無(wú)效定時(shí)器2．距離向量路由協(xié)議特性周期性廣播全部路由項(xiàng)18四、鏈路狀態(tài)路由協(xié)議本講主要內(nèi)容鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程鏈路狀態(tài)路由協(xié)議特性四、鏈路狀態(tài)路由協(xié)議本講主要內(nèi)容191．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程三個(gè)路由器建立的鏈路狀態(tài)1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程三個(gè)路由器建立的鏈路狀態(tài)201．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程泛洪鏈路狀態(tài)建立前圖所示的鏈路狀態(tài)信息庫(kù)1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程泛洪鏈路狀態(tài)211．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程令D(v)為源結(jié)點(diǎn)（路由器R1）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)v所經(jīng)過(guò)的鏈路的代價(jià)之和，L(i,j)為結(jié)點(diǎn)i至結(jié)點(diǎn)j的距離。①以R1為樹(shù)根，求出各個(gè)結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。D(v)=L(R1,v)若結(jié)點(diǎn)v與R1直接相連∞若結(jié)點(diǎn)v與R1不直接相連

②找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)w），將該結(jié)點(diǎn)連接到以R1為根的樹(shù)上，并重新對(duì)剩下的結(jié)點(diǎn)計(jì)算到達(dá)根結(jié)點(diǎn)的距離，D(v)=MIN{D(v),D(w)+L(w,v)}。③重復(fù)步驟②，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹(shù)上。1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程令D(v)為源結(jié)點(diǎn)（路由器221．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程路由器R1完整路由表1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程路由器R1完整路由表232．鏈路狀態(tài)路由協(xié)議特性快速收斂消除路由環(huán)路實(shí)時(shí)性好實(shí)現(xiàn)負(fù)載均衡傳輸開(kāi)銷大計(jì)算復(fù)雜度高2．鏈路狀態(tài)路由協(xié)議特性快速收斂246.3RIP本講主要內(nèi)容RIP消息格式RIP工作過(guò)程RIP建立路由表實(shí)例RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化的過(guò)程計(jì)數(shù)到無(wú)窮大和水平分割6.3RIP本講主要內(nèi)容25一、RIP消息格式RIP消息封裝為IP分組過(guò)程一、RIP消息格式RIP消息封裝為IP分組過(guò)程26二、RIP工作過(guò)程RIP(路由信息協(xié)議）是一種路由協(xié)議。相鄰路由器之間通過(guò)交換路由信息動(dòng)態(tài)構(gòu)建路由表。根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)求出的端到端最短傳輸路徑構(gòu)建路由表。二、RIP工作過(guò)程RIP(路由信息協(xié)議）是一種路由協(xié)議。27

RIP的工作思路如下：用D(i,j)表示路由器i到達(dá)網(wǎng)絡(luò)j的距離，如果某個(gè)路由器i直接連接某個(gè)網(wǎng)絡(luò)j，則該路由器到達(dá)該網(wǎng)絡(luò)的距離最短，距離為1，D（i,j）=1。如果某個(gè)路由器i沒(méi)有直接和某個(gè)網(wǎng)絡(luò)j連接，則必須找到一個(gè)中間路由器k，使得D（i,k）+D（k,j）為最短，通常情況下，中間路由器k和路由器i相鄰。二、RIP工作過(guò)程RIP的工作思路如下：用D(i,j)表示路由器i到達(dá)28R2獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。同樣公告相鄰路由器R4和R5。R5獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。R1到達(dá)子網(wǎng)192.1.1.0/24距離最短，R1將此信息公告相鄰路由器R2和R3.三、RIP建立路由表實(shí)例R2獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。同樣公29每一個(gè)路由器建立和其直接相連的子網(wǎng)的路由項(xiàng)。相鄰路由器交換各自的路由項(xiàng)，如果相鄰路由器路由項(xiàng)中存在通往某個(gè)子網(wǎng)的路徑，意味著通過(guò)該相鄰路由器可以找到通往該子網(wǎng)的路徑。經(jīng)過(guò)反復(fù)交換路由項(xiàng)，最終建立到達(dá)網(wǎng)絡(luò)中所有子網(wǎng)的路由項(xiàng)。三、RIP建立路由表實(shí)例每一個(gè)路由器建立和其直接相連的子網(wǎng)的路由項(xiàng)。三、RIP建立路30路由器R1向路由器R2、R3發(fā)送路由消息的過(guò)程三、RIP建立路由表實(shí)例路由器R1向路由器R2、R3發(fā)送路由消息的過(guò)程三、RIP建立31193.1.4.1三、RIP建立路由表實(shí)例193.1.4.1三、RIP建立路由表實(shí)例32四、RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程一旦路由器R2和R5之間的鏈路故障，路由器R5選擇經(jīng)過(guò)R4到達(dá)網(wǎng)絡(luò)192.1.1.0/24的傳輸路徑四、RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程一旦路由器R2和R5之間的鏈路33計(jì)數(shù)無(wú)窮大的問(wèn)題１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由器R1向路由器R2發(fā)送刪除路由項(xiàng)信息。３．路由器R2刪除通往NET1的路由項(xiàng)。路由表收斂。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)無(wú)窮大的問(wèn)題１．路由器R1檢測(cè)到故障，刪除通往NET1的34１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由器R2搶先向路由器R1發(fā)送通往NET1的路由項(xiàng)。３．路由器R1認(rèn)為通過(guò)路由器R2存在通往NET1的傳輸路徑。４．路由器R2通往NET1的傳輸路徑經(jīng)過(guò)R1，因而在R1公告的距離上加1。五、計(jì)數(shù)到無(wú)窮大和水平分割１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由35計(jì)數(shù)到無(wú)窮大是指某個(gè)實(shí)際不存在的路由項(xiàng)只有經(jīng)過(guò)反復(fù)交換，將距離增加到無(wú)窮大值（RIP定為16），才刪除。引發(fā)計(jì)數(shù)到無(wú)窮大問(wèn)題的關(guān)鍵是路由項(xiàng)的公告環(huán)路，即從相鄰路由器學(xué)習(xí)到的路由項(xiàng)又公告該相鄰路由器。因此，RIP規(guī)定：從某個(gè)相鄰路由器學(xué)習(xí)到的路由項(xiàng)不允許出現(xiàn)在公告該路由器的路由消息中。前面的計(jì)數(shù)到無(wú)窮大可以避免，但不是可以避免所有計(jì)數(shù)到無(wú)窮大的問(wèn)題。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)到無(wú)窮大是指某個(gè)實(shí)際不存在的路由項(xiàng)只有經(jīng)過(guò)反復(fù)交換，將距36正常收斂的情況五、計(jì)數(shù)到無(wú)窮大和水平分割正常收斂的情況五、計(jì)數(shù)到無(wú)窮大和水平分割37計(jì)數(shù)無(wú)窮大的問(wèn)題無(wú)窮大問(wèn)題是無(wú)法徹底避免的，這是RIP的缺陷。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)無(wú)窮大的問(wèn)題無(wú)窮大問(wèn)題是無(wú)法徹底避免的，這是RIP的缺陷386.4OSPF本講主要內(nèi)容路由器確定自身鏈路狀態(tài)泛洪鏈路狀態(tài)通告構(gòu)建路由表算法OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程OSPF和RIP的區(qū)別OSPF分區(qū)域建立路由表的過(guò)程6.4OSPF本講主要內(nèi)容39一、路由器確定自身鏈路狀態(tài)HELLO報(bào)文格式和封裝過(guò)程一、路由器確定自身鏈路狀態(tài)HELLO報(bào)文格式和封裝過(guò)程40通過(guò)發(fā)送、接收Hello報(bào)文建立鄰居關(guān)系；自身狀態(tài)信息包括直接連接的LAN信息和已經(jīng)建立鄰居關(guān)系的路由器。一、路由器確定自身鏈路狀態(tài)通過(guò)發(fā)送、接收Hello報(bào)文建立鄰居關(guān)系；一、路由器確定自身41一、路由器確定自身鏈路狀態(tài)數(shù)據(jù)庫(kù)描述報(bào)文用于向?qū)Ψ焦骀溌窢顟B(tài)數(shù)據(jù)庫(kù)中存在的LSA

一、路由器確定自身鏈路狀態(tài)數(shù)據(jù)庫(kù)描述報(bào)文用于向?qū)Ψ焦骀溌窢?2一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)請(qǐng)求報(bào)文用于請(qǐng)求對(duì)方向其傳輸特定的LSA一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)請(qǐng)求報(bào)文用于請(qǐng)求對(duì)方向其傳43一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)更新報(bào)文的作用有二，一是用于向LSR發(fā)送者傳輸一組完整的LSA。二是在路由器自身鏈路狀態(tài)發(fā)生改變，或是路由器用于指定泛洪鏈路狀態(tài)通告周期的定時(shí)器溢出時(shí)，用于向互連網(wǎng)絡(luò)中的所有其他路由器泛洪用于表示自身鏈路狀態(tài)的LSA。

一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)更新報(bào)文的作用有二，一是用44一、路由器確定自身鏈路狀態(tài)鄰接關(guān)系建立過(guò)程就是兩個(gè)路由器的鏈路狀態(tài)數(shù)據(jù)庫(kù)同步過(guò)程。一、路由器確定自身鏈路狀態(tài)鄰接關(guān)系建立過(guò)程就是兩個(gè)路由器的鏈45路由器泛洪自身鏈路狀態(tài)信息；其他路由器通過(guò)始發(fā)路由器和序號(hào)確定是否是重復(fù)接收的鏈路狀態(tài)信息，對(duì)新接收到的鏈路狀態(tài)信息發(fā)送確認(rèn)報(bào)文；其他路由器從其他端口轉(zhuǎn)發(fā)新接收到的鏈路狀態(tài)信息。二、泛洪鏈路狀態(tài)通告路由器泛洪自身鏈路狀態(tài)信息；二、泛洪鏈路狀態(tài)通告46鏈路狀態(tài)信息泛洪過(guò)程；依靠始發(fā)路由器和序號(hào)確定是否重復(fù)接收的鏈路狀態(tài)信息；每一個(gè)路由器轉(zhuǎn)發(fā)時(shí)，用轉(zhuǎn)發(fā)接口的IP地址作為IP分組的源IP地址。二、泛洪鏈路狀態(tài)通告鏈路狀態(tài)信息泛洪過(guò)程；二、泛洪鏈路狀態(tài)通告47三、構(gòu)建路由表算法把互連網(wǎng)看作一個(gè)無(wú)向圖，以路由器和LAN為結(jié)點(diǎn)，以互連路由器的傳輸網(wǎng)絡(luò)為邊；每一個(gè)路由器計(jì)算以自己為根，到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)。三、構(gòu)建路由表算法把互連網(wǎng)看作一個(gè)無(wú)向圖，以路由器和LAN為48令D(v)為源結(jié)點(diǎn)（路由器R5）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)v所經(jīng)過(guò)的鏈路的代價(jià)之和，L(i,j)為結(jié)點(diǎn)i至結(jié)點(diǎn)j的距離。以源結(jié)點(diǎn)為樹(shù)根，求出各個(gè)結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)w），將該結(jié)點(diǎn)連接到以源結(jié)點(diǎn)為根的樹(shù)上，并重新對(duì)剩下的結(jié)點(diǎn)計(jì)算到達(dá)根結(jié)點(diǎn)的距離，D(v)=MIN{D(v),D(w)+L(w,v)}。重復(fù)步驟(2)，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹(shù)上。三、構(gòu)建路由表算法令D(v)為源結(jié)點(diǎn)（路由器R5）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)49以路由器R5為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；根據(jù)最短路徑樹(shù)可以得出通往其他結(jié)點(diǎn)的最短路徑樹(shù)上的下一跳結(jié)點(diǎn)。三、構(gòu)建路由表算法以路由器R5為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；三、構(gòu)建路由表算法50

求出以某個(gè)結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)的先決條件是該結(jié)點(diǎn)擁有描述無(wú)向圖的全部信息，這些信息稱為鏈路狀態(tài)信息。由此可以得出OSPF建立路由表過(guò)程。發(fā)現(xiàn)鄰居，確定到達(dá)鄰居的代價(jià)。泛洪鏈路狀態(tài)信息。建立鏈路狀態(tài)數(shù)據(jù)庫(kù)并計(jì)算路由表。三、構(gòu)建路由表算法求出以某個(gè)結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)的先決條件是該結(jié)51路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開(kāi)始路由器為下一跳路由器；以到達(dá)根結(jié)點(diǎn)的距離為路由項(xiàng)距離。三、構(gòu)建路由表算法路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開(kāi)始路由器為下一跳路由器；三、構(gòu)建52路由器R2與R5之間鏈路發(fā)生故障；路由器R2和R5通過(guò)鏈路狀態(tài)更新報(bào)文泛洪這一變化。四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程路由器R2與R5之間鏈路發(fā)生故障；四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變53重新根據(jù)修改后鏈路狀態(tài)庫(kù)構(gòu)建路由器R2到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；根據(jù)最短路徑樹(shù)得出路由器R5到達(dá)所有結(jié)點(diǎn)的路由項(xiàng)。四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程重新根據(jù)修改后鏈路狀態(tài)庫(kù)構(gòu)建路由器R2到達(dá)其他結(jié)點(diǎn)的最短路徑54五、OSPF和RIP的區(qū)別OSPF是將部分信息泛洪給互連網(wǎng)絡(luò)中所有其他路由器，而RIP是將所有信息傳輸給相鄰路由器OSPF中，每一個(gè)路由器可以根據(jù)不同的應(yīng)用要求設(shè)定鏈路代價(jià)，也可根據(jù)鏈路狀態(tài)數(shù)據(jù)庫(kù)計(jì)算出多條到達(dá)指定網(wǎng)絡(luò)的傳輸路徑，以此實(shí)現(xiàn)負(fù)載均衡。而RIP只能得出最小跳數(shù)傳輸路徑OSPF由于可以及時(shí)更新每一個(gè)路由器的鏈路狀態(tài)數(shù)據(jù)庫(kù)，路由表能夠及時(shí)反映最新的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，而RIP存在好消息傳得快，壞消息傳得慢的問(wèn)題

五、OSPF和RIP的區(qū)別OSPF是將部分信息泛洪給互連網(wǎng)絡(luò)55將網(wǎng)絡(luò)分成一個(gè)主干區(qū)和若干個(gè)區(qū)；其他區(qū)通過(guò)區(qū)域邊界路由器和主干區(qū)相連。六、OSPF分區(qū)域建立路由表過(guò)程將網(wǎng)絡(luò)分成一個(gè)主干區(qū)和若干個(gè)區(qū)；六、OSPF分區(qū)域建立路由表56

路由器R11建立至網(wǎng)絡(luò)NET6傳輸路徑的過(guò)程：通過(guò)區(qū)域3OSPF建立路由表過(guò)程建立區(qū)域邊界路由器R05、R06至NET6傳輸路徑；通過(guò)主干區(qū)域OSPF建立路由表過(guò)程建立R01、R02至NET6傳輸路徑；通過(guò)區(qū)域1OSFP建立路由表過(guò)程建立R11至NET6傳輸路徑。六、OSPF分區(qū)域建立路由表過(guò)程路由器R11建立至網(wǎng)絡(luò)NET6傳輸路徑的過(guò)程：六、OSPF57六、OSPF分區(qū)域建立路由表過(guò)程區(qū)域3建立R06至NET6傳輸路徑區(qū)域0建立R01至NET6傳輸路徑區(qū)域1建立R11至NET6傳輸路徑六、OSPF分區(qū)域建立路由表過(guò)程區(qū)域3建立R06至NET6傳586.5BGP本講主要內(nèi)容分層路由的原因BGP報(bào)文類型BGP工作機(jī)制6.5BGP本講主要內(nèi)容59一、分層路由的原因自治系統(tǒng)結(jié)構(gòu)一、分層路由的原因自治系統(tǒng)結(jié)構(gòu)60BGP是一種可以在不了解各個(gè)自治系統(tǒng)內(nèi)部結(jié)構(gòu)、不需要統(tǒng)一各個(gè)自治系統(tǒng)的代價(jià)取值標(biāo)準(zhǔn)的情況下，在滿足政策和安全的前提下建立自治系統(tǒng)之間的傳輸路徑，的路由協(xié)議。BGP是路徑向量路由協(xié)議，選擇經(jīng)過(guò)自治系統(tǒng)最少的傳輸路徑作為通往該外部網(wǎng)絡(luò)的傳輸路徑。一、分層路由的原因BGP是一種可以在不了解各個(gè)自治系統(tǒng)內(nèi)部結(jié)構(gòu)、不需要統(tǒng)一各個(gè)61二、BGP報(bào)文類型打開(kāi)（OPEN）報(bào)文?；睿↘EEPALIVE）報(bào)文更新（UPDATE）報(bào)文通知（NOTIFICATION）報(bào)文

二、BGP報(bào)文類型打開(kāi)（OPEN）報(bào)文62BGP工作過(guò)程自治系統(tǒng)之間通過(guò)BGP發(fā)言人交換路由消息，需要配置相鄰自治系統(tǒng)的BGP發(fā)言人；BGP發(fā)言人建立到達(dá)自治系統(tǒng)內(nèi)部網(wǎng)絡(luò)的傳輸路徑；BGP發(fā)言人之間交換路由消息，給出通過(guò)BGP發(fā)言人可以到達(dá)的網(wǎng)絡(luò)；建立經(jīng)過(guò)自治系統(tǒng)最少的傳輸路徑。三、BGP工作機(jī)制BGP工作過(guò)程三、BGP工作機(jī)制63三、BGP工作機(jī)制BGP發(fā)言人之間交換路由消息過(guò)程，目的是使AS1中BGP發(fā)言人具有通往其他自治系統(tǒng)中網(wǎng)絡(luò)的傳輸路徑，由于R21發(fā)送給AS1中BGP發(fā)言人的下一跳地址是R21連接NET7接口的IP地址，而NET7是AS1的內(nèi)部網(wǎng)絡(luò)，因此，AS1中路由器可以通過(guò)內(nèi)部網(wǎng)關(guān)路由協(xié)議建立通往R21的傳輸路徑。三、BGP工作機(jī)制BGP發(fā)言人之間交換路由消息過(guò)程，目的是使64R11通往所有網(wǎng)絡(luò)的路由項(xiàng)；通往其他自治系統(tǒng)的路由項(xiàng)中給出的下一跳地址是通往下一個(gè)自治系統(tǒng)的BGP發(fā)言人的傳輸路徑的下一跳，如NET3是通往R21連接NET7接口的傳輸路徑的下一跳R13，NET5是通往R31連接NET8接口的傳輸路徑的下一跳R12。三、BGP工作機(jī)制R11通往所有網(wǎng)絡(luò)的路由項(xiàng)；三、BGP工作機(jī)制65路由和交換技術(shù)第六章路由和交換技術(shù)第六章第6章路由協(xié)議本章主要內(nèi)容路由項(xiàng)分類；路由協(xié)議基礎(chǔ)；RIP；OSPF；BGP。第6章路由協(xié)議本章主要內(nèi)容676.1路由項(xiàng)分類本講主要內(nèi)容直連路由項(xiàng)靜態(tài)路由項(xiàng)動(dòng)態(tài)路由項(xiàng)靜態(tài)路由項(xiàng)缺陷6.1路由項(xiàng)分類本講主要內(nèi)容68一、直連路由項(xiàng)R1路由表路由器自動(dòng)生成的用于指明通往這些直接連接的網(wǎng)絡(luò)的傳輸路徑的路由項(xiàng)稱為直連路由項(xiàng)。

一、直連路由項(xiàng)R1路由表路由器自動(dòng)生成的用于指明通往這些直接69二、靜態(tài)路由項(xiàng)路由器建立路由表的過(guò)程就是找出通往各個(gè)子網(wǎng)的最短路徑的過(guò)程，在RIP中，最短路徑就是經(jīng)過(guò)跳數(shù)最少的路徑R5路由表二、靜態(tài)路由項(xiàng)路由器建立路由表的過(guò)程就是找出通往各個(gè)子網(wǎng)的最70三、動(dòng)態(tài)路由項(xiàng)路由協(xié)議路由協(xié)議就是一組用于規(guī)范路由消息的格式、路由器之間路由消息交換過(guò)程、路由器對(duì)路由消息的處理流程的規(guī)則路徑距離路徑距離可以是傳輸路徑經(jīng)過(guò)的路由器跳數(shù)，也可以是其他衡量傳輸路徑的參數(shù)，如傳輸路徑的物理距離、傳輸路徑經(jīng)過(guò)的物理鏈路的帶寬等三、動(dòng)態(tài)路由項(xiàng)路由協(xié)議71四、靜態(tài)路由項(xiàng)缺陷一是大型互連網(wǎng)絡(luò)很難做到各個(gè)路由器配置的靜態(tài)路由項(xiàng)一致二是互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)變化的三是為了容錯(cuò)，各個(gè)網(wǎng)絡(luò)之間存在多條傳輸路徑四是實(shí)際網(wǎng)絡(luò)配置靜態(tài)路由項(xiàng)的工作量是無(wú)法想象的四、靜態(tài)路由項(xiàng)缺陷一是大型互連網(wǎng)絡(luò)很難做到各個(gè)路由器配置的靜726.2路由協(xié)議基礎(chǔ)本講主要內(nèi)容路由協(xié)議分類路由協(xié)議要求距離向量路由協(xié)議鏈路狀態(tài)路由協(xié)議6.2路由協(xié)議基礎(chǔ)本講主要內(nèi)容73一、路由協(xié)議分類距離向量路由協(xié)議距離向量路由協(xié)議要求每一個(gè)路由器定期向其相鄰路由器公告全部路由項(xiàng)，由于每一項(xiàng)路由項(xiàng)用于指明通往某個(gè)網(wǎng)絡(luò)或網(wǎng)絡(luò)前綴相同的一組網(wǎng)絡(luò)的傳輸路徑，路由器擁有某項(xiàng)路由項(xiàng)，意味著該路由器已經(jīng)建立通往目的網(wǎng)絡(luò)字段指定的一個(gè)或一組網(wǎng)絡(luò)的傳輸路徑。鏈路狀態(tài)路由協(xié)議互連網(wǎng)絡(luò)中的某個(gè)路由器獲得所有其他路由器的鏈路狀態(tài)信息，就可構(gòu)建互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并在此基礎(chǔ)上計(jì)算出該路由器到達(dá)所有網(wǎng)絡(luò)的最短路徑。

一、路由協(xié)議分類距離向量路由協(xié)議74內(nèi)部網(wǎng)關(guān)協(xié)議用于建立自治系統(tǒng)內(nèi)傳輸路徑的路由協(xié)議稱作內(nèi)部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議用于建立自治系統(tǒng)間傳輸路徑的路由協(xié)議稱作外部網(wǎng)關(guān)協(xié)議一、路由協(xié)議分類內(nèi)部網(wǎng)關(guān)協(xié)議一、路由協(xié)議分類75一、路由協(xié)議分類互連網(wǎng)絡(luò)分成多個(gè)自治系統(tǒng)；用于建立自治系統(tǒng)內(nèi)端到端路徑的路由協(xié)議稱為內(nèi)部網(wǎng)關(guān)協(xié)議；用于建立自治系統(tǒng)間端到端路徑的路由協(xié)議稱為外部網(wǎng)關(guān)協(xié)議。一、路由協(xié)議分類互連網(wǎng)絡(luò)分成多個(gè)自治系統(tǒng)；76二、路由協(xié)議要求建立完整路由表選擇最佳路由簡(jiǎn)單、開(kāi)銷小實(shí)時(shí)反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化具有穩(wěn)定性快速收斂二、路由協(xié)議要求建立完整路由表77三、距離向量路由協(xié)議本講主要內(nèi)容距離向量路由協(xié)議創(chuàng)建路由表過(guò)程距離向量路由協(xié)議特性三、距離向量路由協(xié)議本講主要內(nèi)容781．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程791．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1、R2和R3自動(dòng)生成的直連路由項(xiàng)1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1、R2和R3自動(dòng)80路由器R2發(fā)送給路由器R1的路由消息如下{（192.1.2.0/24,0）（192.1.6.0/30,0）（192.1.4.0/30,0）192.1.4.2}路由器R3向路由器R1發(fā)送路由消息{（192.1.3.0/24,0）（192.1.5.0/30,0）（192.1.6.0/30,0）192.1.5.2}1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R2發(fā)送給路由器R1的路由消息如下{（192.1.2.811．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1完整路由表1．距離向量路由協(xié)議創(chuàng)建路由表過(guò)程路由器R1完整路由表822．距離向量路由協(xié)議特性周期性廣播全部路由項(xiàng)容易發(fā)生路由環(huán)路實(shí)時(shí)性差設(shè)置觸發(fā)機(jī)制設(shè)置無(wú)效定時(shí)器2．距離向量路由協(xié)議特性周期性廣播全部路由項(xiàng)83四、鏈路狀態(tài)路由協(xié)議本講主要內(nèi)容鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程鏈路狀態(tài)路由協(xié)議特性四、鏈路狀態(tài)路由協(xié)議本講主要內(nèi)容841．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程三個(gè)路由器建立的鏈路狀態(tài)1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程三個(gè)路由器建立的鏈路狀態(tài)851．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程泛洪鏈路狀態(tài)建立前圖所示的鏈路狀態(tài)信息庫(kù)1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程泛洪鏈路狀態(tài)861．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程令D(v)為源結(jié)點(diǎn)（路由器R1）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)v所經(jīng)過(guò)的鏈路的代價(jià)之和，L(i,j)為結(jié)點(diǎn)i至結(jié)點(diǎn)j的距離。①以R1為樹(shù)根，求出各個(gè)結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。D(v)=L(R1,v)若結(jié)點(diǎn)v與R1直接相連∞若結(jié)點(diǎn)v與R1不直接相連

②找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)w），將該結(jié)點(diǎn)連接到以R1為根的樹(shù)上，并重新對(duì)剩下的結(jié)點(diǎn)計(jì)算到達(dá)根結(jié)點(diǎn)的距離，D(v)=MIN{D(v),D(w)+L(w,v)}。③重復(fù)步驟②，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹(shù)上。1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程令D(v)為源結(jié)點(diǎn)（路由器871．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程路由器R1完整路由表1．鏈路狀態(tài)路由協(xié)議建立路由表過(guò)程路由器R1完整路由表882．鏈路狀態(tài)路由協(xié)議特性快速收斂消除路由環(huán)路實(shí)時(shí)性好實(shí)現(xiàn)負(fù)載均衡傳輸開(kāi)銷大計(jì)算復(fù)雜度高2．鏈路狀態(tài)路由協(xié)議特性快速收斂896.3RIP本講主要內(nèi)容RIP消息格式RIP工作過(guò)程RIP建立路由表實(shí)例RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化的過(guò)程計(jì)數(shù)到無(wú)窮大和水平分割6.3RIP本講主要內(nèi)容90一、RIP消息格式RIP消息封裝為IP分組過(guò)程一、RIP消息格式RIP消息封裝為IP分組過(guò)程91二、RIP工作過(guò)程RIP(路由信息協(xié)議）是一種路由協(xié)議。相鄰路由器之間通過(guò)交換路由信息動(dòng)態(tài)構(gòu)建路由表。根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)求出的端到端最短傳輸路徑構(gòu)建路由表。二、RIP工作過(guò)程RIP(路由信息協(xié)議）是一種路由協(xié)議。92

RIP的工作思路如下：用D(i,j)表示路由器i到達(dá)網(wǎng)絡(luò)j的距離，如果某個(gè)路由器i直接連接某個(gè)網(wǎng)絡(luò)j，則該路由器到達(dá)該網(wǎng)絡(luò)的距離最短，距離為1，D（i,j）=1。如果某個(gè)路由器i沒(méi)有直接和某個(gè)網(wǎng)絡(luò)j連接，則必須找到一個(gè)中間路由器k，使得D（i,k）+D（k,j）為最短，通常情況下，中間路由器k和路由器i相鄰。二、RIP工作過(guò)程RIP的工作思路如下：用D(i,j)表示路由器i到達(dá)93R2獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。同樣公告相鄰路由器R4和R5。R5獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。R1到達(dá)子網(wǎng)192.1.1.0/24距離最短，R1將此信息公告相鄰路由器R2和R3.三、RIP建立路由表實(shí)例R2獲悉到達(dá)子網(wǎng)192.1.1.0/24的路徑和距離。同樣公94每一個(gè)路由器建立和其直接相連的子網(wǎng)的路由項(xiàng)。相鄰路由器交換各自的路由項(xiàng)，如果相鄰路由器路由項(xiàng)中存在通往某個(gè)子網(wǎng)的路徑，意味著通過(guò)該相鄰路由器可以找到通往該子網(wǎng)的路徑。經(jīng)過(guò)反復(fù)交換路由項(xiàng)，最終建立到達(dá)網(wǎng)絡(luò)中所有子網(wǎng)的路由項(xiàng)。三、RIP建立路由表實(shí)例每一個(gè)路由器建立和其直接相連的子網(wǎng)的路由項(xiàng)。三、RIP建立路95路由器R1向路由器R2、R3發(fā)送路由消息的過(guò)程三、RIP建立路由表實(shí)例路由器R1向路由器R2、R3發(fā)送路由消息的過(guò)程三、RIP建立96193.1.4.1三、RIP建立路由表實(shí)例193.1.4.1三、RIP建立路由表實(shí)例97四、RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程一旦路由器R2和R5之間的鏈路故障，路由器R5選擇經(jīng)過(guò)R4到達(dá)網(wǎng)絡(luò)192.1.1.0/24的傳輸路徑四、RIP動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程一旦路由器R2和R5之間的鏈路98計(jì)數(shù)無(wú)窮大的問(wèn)題１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由器R1向路由器R2發(fā)送刪除路由項(xiàng)信息。３．路由器R2刪除通往NET1的路由項(xiàng)。路由表收斂。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)無(wú)窮大的問(wèn)題１．路由器R1檢測(cè)到故障，刪除通往NET1的99１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由器R2搶先向路由器R1發(fā)送通往NET1的路由項(xiàng)。３．路由器R1認(rèn)為通過(guò)路由器R2存在通往NET1的傳輸路徑。４．路由器R2通往NET1的傳輸路徑經(jīng)過(guò)R1，因而在R1公告的距離上加1。五、計(jì)數(shù)到無(wú)窮大和水平分割１．路由器R1檢測(cè)到故障，刪除通往NET1的路由項(xiàng)。２．路由100計(jì)數(shù)到無(wú)窮大是指某個(gè)實(shí)際不存在的路由項(xiàng)只有經(jīng)過(guò)反復(fù)交換，將距離增加到無(wú)窮大值（RIP定為16），才刪除。引發(fā)計(jì)數(shù)到無(wú)窮大問(wèn)題的關(guān)鍵是路由項(xiàng)的公告環(huán)路，即從相鄰路由器學(xué)習(xí)到的路由項(xiàng)又公告該相鄰路由器。因此，RIP規(guī)定：從某個(gè)相鄰路由器學(xué)習(xí)到的路由項(xiàng)不允許出現(xiàn)在公告該路由器的路由消息中。前面的計(jì)數(shù)到無(wú)窮大可以避免，但不是可以避免所有計(jì)數(shù)到無(wú)窮大的問(wèn)題。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)到無(wú)窮大是指某個(gè)實(shí)際不存在的路由項(xiàng)只有經(jīng)過(guò)反復(fù)交換，將距101正常收斂的情況五、計(jì)數(shù)到無(wú)窮大和水平分割正常收斂的情況五、計(jì)數(shù)到無(wú)窮大和水平分割102計(jì)數(shù)無(wú)窮大的問(wèn)題無(wú)窮大問(wèn)題是無(wú)法徹底避免的，這是RIP的缺陷。五、計(jì)數(shù)到無(wú)窮大和水平分割計(jì)數(shù)無(wú)窮大的問(wèn)題無(wú)窮大問(wèn)題是無(wú)法徹底避免的，這是RIP的缺陷1036.4OSPF本講主要內(nèi)容路由器確定自身鏈路狀態(tài)泛洪鏈路狀態(tài)通告構(gòu)建路由表算法OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程OSPF和RIP的區(qū)別OSPF分區(qū)域建立路由表的過(guò)程6.4OSPF本講主要內(nèi)容104一、路由器確定自身鏈路狀態(tài)HELLO報(bào)文格式和封裝過(guò)程一、路由器確定自身鏈路狀態(tài)HELLO報(bào)文格式和封裝過(guò)程105通過(guò)發(fā)送、接收Hello報(bào)文建立鄰居關(guān)系；自身狀態(tài)信息包括直接連接的LAN信息和已經(jīng)建立鄰居關(guān)系的路由器。一、路由器確定自身鏈路狀態(tài)通過(guò)發(fā)送、接收Hello報(bào)文建立鄰居關(guān)系；一、路由器確定自身106一、路由器確定自身鏈路狀態(tài)數(shù)據(jù)庫(kù)描述報(bào)文用于向?qū)Ψ焦骀溌窢顟B(tài)數(shù)據(jù)庫(kù)中存在的LSA

一、路由器確定自身鏈路狀態(tài)數(shù)據(jù)庫(kù)描述報(bào)文用于向?qū)Ψ焦骀溌窢?07一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)請(qǐng)求報(bào)文用于請(qǐng)求對(duì)方向其傳輸特定的LSA一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)請(qǐng)求報(bào)文用于請(qǐng)求對(duì)方向其傳108一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)更新報(bào)文的作用有二，一是用于向LSR發(fā)送者傳輸一組完整的LSA。二是在路由器自身鏈路狀態(tài)發(fā)生改變，或是路由器用于指定泛洪鏈路狀態(tài)通告周期的定時(shí)器溢出時(shí)，用于向互連網(wǎng)絡(luò)中的所有其他路由器泛洪用于表示自身鏈路狀態(tài)的LSA。

一、路由器確定自身鏈路狀態(tài)鏈路狀態(tài)更新報(bào)文的作用有二，一是用109一、路由器確定自身鏈路狀態(tài)鄰接關(guān)系建立過(guò)程就是兩個(gè)路由器的鏈路狀態(tài)數(shù)據(jù)庫(kù)同步過(guò)程。一、路由器確定自身鏈路狀態(tài)鄰接關(guān)系建立過(guò)程就是兩個(gè)路由器的鏈110路由器泛洪自身鏈路狀態(tài)信息；其他路由器通過(guò)始發(fā)路由器和序號(hào)確定是否是重復(fù)接收的鏈路狀態(tài)信息，對(duì)新接收到的鏈路狀態(tài)信息發(fā)送確認(rèn)報(bào)文；其他路由器從其他端口轉(zhuǎn)發(fā)新接收到的鏈路狀態(tài)信息。二、泛洪鏈路狀態(tài)通告路由器泛洪自身鏈路狀態(tài)信息；二、泛洪鏈路狀態(tài)通告111鏈路狀態(tài)信息泛洪過(guò)程；依靠始發(fā)路由器和序號(hào)確定是否重復(fù)接收的鏈路狀態(tài)信息；每一個(gè)路由器轉(zhuǎn)發(fā)時(shí)，用轉(zhuǎn)發(fā)接口的IP地址作為IP分組的源IP地址。二、泛洪鏈路狀態(tài)通告鏈路狀態(tài)信息泛洪過(guò)程；二、泛洪鏈路狀態(tài)通告112三、構(gòu)建路由表算法把互連網(wǎng)看作一個(gè)無(wú)向圖，以路由器和LAN為結(jié)點(diǎn)，以互連路由器的傳輸網(wǎng)絡(luò)為邊；每一個(gè)路由器計(jì)算以自己為根，到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)。三、構(gòu)建路由表算法把互連網(wǎng)看作一個(gè)無(wú)向圖，以路由器和LAN為113令D(v)為源結(jié)點(diǎn)（路由器R5）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)v所經(jīng)過(guò)的鏈路的代價(jià)之和，L(i,j)為結(jié)點(diǎn)i至結(jié)點(diǎn)j的距離。以源結(jié)點(diǎn)為樹(shù)根，求出各個(gè)結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)w），將該結(jié)點(diǎn)連接到以源結(jié)點(diǎn)為根的樹(shù)上，并重新對(duì)剩下的結(jié)點(diǎn)計(jì)算到達(dá)根結(jié)點(diǎn)的距離，D(v)=MIN{D(v),D(w)+L(w,v)}。重復(fù)步驟(2)，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹(shù)上。三、構(gòu)建路由表算法令D(v)為源結(jié)點(diǎn)（路由器R5）到達(dá)結(jié)點(diǎn)v的距離，它是從源結(jié)114以路由器R5為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；根據(jù)最短路徑樹(shù)可以得出通往其他結(jié)點(diǎn)的最短路徑樹(shù)上的下一跳結(jié)點(diǎn)。三、構(gòu)建路由表算法以路由器R5為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；三、構(gòu)建路由表算法115

求出以某個(gè)結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)的先決條件是該結(jié)點(diǎn)擁有描述無(wú)向圖的全部信息，這些信息稱為鏈路狀態(tài)信息。由此可以得出OSPF建立路由表過(guò)程。發(fā)現(xiàn)鄰居，確定到達(dá)鄰居的代價(jià)。泛洪鏈路狀態(tài)信息。建立鏈路狀態(tài)數(shù)據(jù)庫(kù)并計(jì)算路由表。三、構(gòu)建路由表算法求出以某個(gè)結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)的先決條件是該結(jié)116路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開(kāi)始路由器為下一跳路由器；以到達(dá)根結(jié)點(diǎn)的距離為路由項(xiàng)距離。三、構(gòu)建路由表算法路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開(kāi)始路由器為下一跳路由器；三、構(gòu)建117路由器R2與R5之間鏈路發(fā)生故障；路由器R2和R5通過(guò)鏈路狀態(tài)更新報(bào)文泛洪這一變化。四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程路由器R2與R5之間鏈路發(fā)生故障；四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變118重新根據(jù)修改后鏈路狀態(tài)庫(kù)構(gòu)建路由器R2到達(dá)其他結(jié)點(diǎn)的最短路徑樹(shù)；根據(jù)最短路徑樹(shù)得出路由器R5到達(dá)所有結(jié)點(diǎn)的路由項(xiàng)。四、OSPF動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化過(guò)程重新根據(jù)修改后鏈路狀態(tài)庫(kù)構(gòu)建路由器R2到達(dá)其他結(jié)點(diǎn)的最短路徑119五、OSPF和RIP的區(qū)別OSPF是將部分信息