第6章路由協(xié)議new

1、 2006工程兵工程學(xué)院 計(jì)算機(jī)教研室第六章本章主要內(nèi)容本章主要內(nèi)容n路由項(xiàng)分類；路由項(xiàng)分類；n路由協(xié)議基礎(chǔ)；路由協(xié)議基礎(chǔ)；nRIPRIP；nOSPFOSPF；nBGPBGP。2本講主要內(nèi)容本講主要內(nèi)容n直連路由項(xiàng)直連路由項(xiàng)n靜態(tài)路由項(xiàng)靜態(tài)路由項(xiàng)n動態(tài)路由項(xiàng)動態(tài)路由項(xiàng)n靜態(tài)路由項(xiàng)缺陷靜態(tài)路由項(xiàng)缺陷3R1R1路由表路由表路由器自動生成、通往這路由器自動生成、通往這些直接連接的網(wǎng)絡(luò)的傳輸些直接連接的網(wǎng)絡(luò)的傳輸路徑的路由項(xiàng)稱為直連路路徑的路由項(xiàng)稱為直連路由項(xiàng)。由項(xiàng)。 4互連網(wǎng)絡(luò)結(jié)構(gòu)互連網(wǎng)絡(luò)結(jié)構(gòu) 192.1.1.0/24 192.1.1.1 192.1.2.0/24 192.1.2.1 192.1.3

2、.0/24 192.1.3.1 192.1.4.0/24 192.1.4.1 193.1.4.1 193.1.7.1 193.1.9.2 RR1 1 RR3 3 RR2 22 2 RR4 4 RR5 5 RR6 6 RR7 7 路由器沒有直接連接的網(wǎng)絡(luò)對路由器沒有直接連接的網(wǎng)絡(luò)對應(yīng)的路由項(xiàng)，若采用手工配置，應(yīng)的路由項(xiàng)，若采用手工配置，即是靜態(tài)路由項(xiàng)。即是靜態(tài)路由項(xiàng)。R5R5路由表路由表5建立靜態(tài)路由項(xiàng)：建立靜態(tài)路由項(xiàng)：1 1、確定本路由器到非直連網(wǎng)絡(luò)、確定本路由器到非直連網(wǎng)絡(luò)的最短路徑的最短路徑( (在在RIPRIP中，最短路中，最短路徑就是經(jīng)過跳數(shù)最少的路徑徑就是經(jīng)過跳數(shù)最少的路徑) )。

3、192.1.1.0/24 192.1.1.1 192.1.2.0/24 192.1.2.1 192.1.3.0/24 192.1.3.1 192.1.4.0/24 192.1.4.1 193.1.4.1 193.1.7.1 193.1.9.2 RR1 1 RR3 3 RR2 22 2 RR4 4 RR5 5 RR6 6 RR7 7 R5R5路由表路由表6建立靜態(tài)路由項(xiàng)：建立靜態(tài)路由項(xiàng)：1 1、找出本路由器到非直連網(wǎng)絡(luò)、找出本路由器到非直連網(wǎng)絡(luò)的最短路徑的最短路徑( (在在RIPRIP中，最短路中，最短路徑就是經(jīng)過跳數(shù)最少的路徑徑就是經(jīng)過跳數(shù)最少的路徑) )。2 2、找出最短路徑的上的、找出最短

4、路徑的上的 下一跳路由器和相關(guān)下一跳路由器和相關(guān) 接口的接口的IPIP地址。地址。3 3、配置路由項(xiàng)。、配置路由項(xiàng)。n路由器沒有直接連接的網(wǎng)絡(luò)對應(yīng)的路由項(xiàng)，若采路由器沒有直接連接的網(wǎng)絡(luò)對應(yīng)的路由項(xiàng)，若采用用路由協(xié)議路由協(xié)議自動生成，即是動態(tài)路由項(xiàng)。自動生成，即是動態(tài)路由項(xiàng)。n路由協(xié)議路由協(xié)議 就是一組用于規(guī)范就是一組用于規(guī)范路由消息的格式路由消息的格式、路由器之間、路由器之間路由消息交換過程路由消息交換過程、路由器對路由消息的、路由器對路由消息的處理流處理流程程的規(guī)則。的規(guī)則。 n路徑距離路徑距離 可以是可以是傳輸路徑傳輸路徑經(jīng)過的經(jīng)過的路由器跳數(shù)路由器跳數(shù)，也可以是其，也可以是其他衡量傳輸路

5、徑的參數(shù)，如傳輸路徑的物理距離、他衡量傳輸路徑的參數(shù)，如傳輸路徑的物理距離、傳輸路徑經(jīng)過的物理鏈路的帶寬等。傳輸路徑經(jīng)過的物理鏈路的帶寬等。 7n中、大型互連網(wǎng)絡(luò)的最短路徑難以找出中、大型互連網(wǎng)絡(luò)的最短路徑難以找出n靜態(tài)路由項(xiàng)的配置工作量網(wǎng)管難以承受靜態(tài)路由項(xiàng)的配置工作量網(wǎng)管難以承受 n互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動態(tài)變化的，手工更互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動態(tài)變化的，手工更新難以做到及時(shí)、準(zhǔn)確新難以做到及時(shí)、準(zhǔn)確n大型互連網(wǎng)絡(luò)中各個路由器配置的靜態(tài)路由大型互連網(wǎng)絡(luò)中各個路由器配置的靜態(tài)路由項(xiàng)很難做到一致項(xiàng)很難做到一致 n為了容錯，各個網(wǎng)絡(luò)之間存在多條傳輸路徑，為了容錯，各個網(wǎng)絡(luò)之間存在多條傳輸路徑，導(dǎo)致出

6、現(xiàn)環(huán)路導(dǎo)致出現(xiàn)環(huán)路 8本講主要內(nèi)容本講主要內(nèi)容n路由協(xié)議分類路由協(xié)議分類n對路由協(xié)議的要求對路由協(xié)議的要求n距離向量路由協(xié)議距離向量路由協(xié)議n鏈路狀態(tài)路由協(xié)議鏈路狀態(tài)路由協(xié)議9n距離向量路由協(xié)議距離向量路由協(xié)議 距離向量路由協(xié)議要求每一個路由器距離向量路由協(xié)議要求每一個路由器定期定期向其向其相鄰路由相鄰路由器器公告公告全部路由項(xiàng)全部路由項(xiàng)，由于每一項(xiàng)路，由于每一項(xiàng)路網(wǎng)絡(luò)前綴相同的一組網(wǎng)絡(luò)前綴相同的一組網(wǎng)絡(luò)網(wǎng)絡(luò)由項(xiàng)用于指明通往由項(xiàng)用于指明通往某個網(wǎng)絡(luò)某個網(wǎng)絡(luò)或的傳輸路徑?；虻膫鬏斅窂?。n鏈路狀態(tài)路由協(xié)議鏈路狀態(tài)路由協(xié)議 互連網(wǎng)絡(luò)中的某個路由器獲得互連網(wǎng)絡(luò)中的某個路由器獲得所有其他路由器所有其他路

7、由器的的鏈路狀鏈路狀態(tài)信息態(tài)信息，就可構(gòu)建互連網(wǎng)絡(luò)的，就可構(gòu)建互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)，并在此基礎(chǔ)上，并在此基礎(chǔ)上計(jì)算出該路由器到達(dá)所有網(wǎng)絡(luò)的計(jì)算出該路由器到達(dá)所有網(wǎng)絡(luò)的最短路徑最短路徑。 10n互連網(wǎng)絡(luò)分成多個互連網(wǎng)絡(luò)分成多個自治系統(tǒng)自治系統(tǒng)(AS)；n用于建立自治系統(tǒng)用于建立自治系統(tǒng)內(nèi)內(nèi)端到端傳輸路徑的路由協(xié)議稱為端到端傳輸路徑的路由協(xié)議稱為內(nèi)部網(wǎng)關(guān)協(xié)議內(nèi)部網(wǎng)關(guān)協(xié)議；n用于建立自治系統(tǒng)用于建立自治系統(tǒng)間間端到端傳輸路徑的路由協(xié)議稱為端到端傳輸路徑的路由協(xié)議稱為外部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議。11n建立完整路由表建立完整路由表n選擇最佳路由選擇最佳路由n簡單、開銷小簡單、開銷小n實(shí)時(shí)反映網(wǎng)絡(luò)拓?fù)?/p>

8、結(jié)構(gòu)的變化實(shí)時(shí)反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化n具有穩(wěn)定性具有穩(wěn)定性n快速快速收斂收斂收斂收斂在拓?fù)浣Y(jié)構(gòu)不變的情況下，各路由器建立了所有非直連網(wǎng)絡(luò)的路在拓?fù)浣Y(jié)構(gòu)不變的情況下，各路由器建立了所有非直連網(wǎng)絡(luò)的路 由項(xiàng)，且這些路由項(xiàng)是一致的。由項(xiàng)，且這些路由項(xiàng)是一致的。12本講主要內(nèi)容本講主要內(nèi)容n距離向量路由協(xié)議創(chuàng)建路由表過程距離向量路由協(xié)議創(chuàng)建路由表過程n距離向量路由協(xié)議特性距離向量路由協(xié)議特性1314互連網(wǎng)絡(luò)結(jié)構(gòu)互連網(wǎng)絡(luò)結(jié)構(gòu)路由器路由器R1R1、R2R2和和R3R3自動生成的直自動生成的直連路由項(xiàng)連路由項(xiàng)151)1)建立直連路由項(xiàng)建立直連路由項(xiàng)路由器路由器R1R1完整的完整的路由表：路由表：163)3)

9、發(fā)現(xiàn)拓?fù)渥兓穆酚善?，及時(shí)向相鄰路由器發(fā)送新的路由發(fā)現(xiàn)拓?fù)渥兓穆酚善鳎皶r(shí)向相鄰路由器發(fā)送新的路由信息，更新其路由項(xiàng)信息，更新其路由項(xiàng)2)2)定期交換路由消息，自動建立非直連網(wǎng)絡(luò)的路由項(xiàng)，完善定期交換路由消息，自動建立非直連網(wǎng)絡(luò)的路由項(xiàng)，完善 路由表路由表n周期性廣播全部路由項(xiàng)周期性廣播全部路由項(xiàng)n容易發(fā)生路由環(huán)路容易發(fā)生路由環(huán)路n實(shí)時(shí)性差實(shí)時(shí)性差：拓?fù)浣Y(jié)構(gòu)變化時(shí)，收斂時(shí)間長：拓?fù)浣Y(jié)構(gòu)變化時(shí)，收斂時(shí)間長n設(shè)置觸發(fā)機(jī)制設(shè)置觸發(fā)機(jī)制：發(fā)現(xiàn)拓?fù)浣Y(jié)構(gòu)變化時(shí)，及：發(fā)現(xiàn)拓?fù)浣Y(jié)構(gòu)變化時(shí)，及時(shí)更新相鄰路由器的路由表，加快收斂時(shí)更新相鄰路由器的路由表，加快收斂n設(shè)置無效定時(shí)器設(shè)置無效定時(shí)器：路由項(xiàng)更新超時(shí)后，

10、認(rèn)：路由項(xiàng)更新超時(shí)后，認(rèn)為路由項(xiàng)相應(yīng)的鏈路或路由器出現(xiàn)故障，為路由項(xiàng)相應(yīng)的鏈路或路由器出現(xiàn)故障，判定該路由項(xiàng)失效，刪除此路由項(xiàng)判定該路由項(xiàng)失效，刪除此路由項(xiàng)17本講主要內(nèi)容本講主要內(nèi)容n鏈路狀態(tài)路由協(xié)議建立路由表過程鏈路狀態(tài)路由協(xié)議建立路由表過程n鏈路狀態(tài)路由協(xié)議特性鏈路狀態(tài)路由協(xié)議特性181）建立三個路由器的直連鏈路狀態(tài)）建立三個路由器的直連鏈路狀態(tài)19108數(shù)據(jù)傳輸速率=2）泛洪鏈路狀態(tài)）泛洪鏈路狀態(tài)3）建立鏈路狀態(tài)數(shù)據(jù)庫）建立鏈路狀態(tài)數(shù)據(jù)庫4）根據(jù)鏈路狀態(tài)數(shù)據(jù)庫，建立路由表中各個路由項(xiàng)）根據(jù)鏈路狀態(tài)數(shù)據(jù)庫，建立路由表中各個路由項(xiàng)20路由器R1路由表完整？21以路由器以路由器R1R1為根的

11、最短路徑樹為根的最短路徑樹n快速收斂快速收斂n不易產(chǎn)生路由環(huán)路路由環(huán)路n實(shí)時(shí)性好實(shí)時(shí)性好n實(shí)現(xiàn)負(fù)載均衡實(shí)現(xiàn)負(fù)載均衡n傳輸開銷大傳輸開銷大n計(jì)算復(fù)雜度高計(jì)算復(fù)雜度高22本講主要內(nèi)容本講主要內(nèi)容nRIPRIP消息格式消息格式nRIPRIP動態(tài)適應(yīng)網(wǎng)絡(luò)變化的過程動態(tài)適應(yīng)網(wǎng)絡(luò)變化的過程n計(jì)數(shù)到無窮大和水平分割計(jì)數(shù)到無窮大和水平分割23RIPRIP消息格式消息格式封裝為封裝為IPIP分組的過程分組的過程24nRIP(RIP(路由信息協(xié)議）是一種路由協(xié)議。路由信息協(xié)議）是一種路由協(xié)議。n相鄰路由器相鄰路由器之間通過交換路由信息動態(tài)構(gòu)之間通過交換路由信息動態(tài)構(gòu)建路由表。建路由表。n根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)求出的端到

12、端最短傳輸根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)求出的端到端最短傳輸路徑，路徑，構(gòu)建路由表。構(gòu)建路由表。25一旦路由器一旦路由器R2R2和和R5R5之間的鏈之間的鏈路故障，路由路故障，路由器器R5R5選擇經(jīng)過選擇經(jīng)過R4R4到達(dá)網(wǎng)絡(luò)到達(dá)網(wǎng)絡(luò)192.1.1.0/24192.1.1.0/24的傳輸路徑的傳輸路徑26RIPRIP動態(tài)調(diào)整路由器動態(tài)調(diào)整路由器R5R5路由表的過程路由表的過程 NET1 NET2 NET1 1 直接直接 NET2 2 R2 NET1 2 R1 NET2 1 直接直接 R1 R2 路由器路由器R1檢測到故檢測到故障，刪除通障，刪除通往往NET1的路的路由項(xiàng)。由項(xiàng)。路由器路由器R1向路由器向路由器

13、R2發(fā)送刪除發(fā)送刪除路由項(xiàng)信息。路由項(xiàng)信息。路由器路由器R2刪除通往刪除通往NET1的路由的路由項(xiàng)。路由表項(xiàng)。路由表收斂。收斂。 NET1 16 NET1 2 R1 NET2 1 直接直接 27路由器路由器R1R1先公告路由消息的情況先公告路由消息的情況 NET1 NET2 NET1 1 直接直接 NET2 2 R2 NET1 2 R1 NET2 1 直接直接 R1 R2 NET1 2 NET1 3 R2 NET2 2 R2 NET1 3 NET1 4 R1 NET2 1 直接直接 NET1 4 NET1 5 R2 NET2 2 R2 路由器路由器R1檢測到故檢測到故障，刪除通障，刪除通往往N

14、ET1的路的路由項(xiàng)。由項(xiàng)。路由器路由器R2搶先向路搶先向路由器由器R1發(fā)送發(fā)送通往通往NET1的的路由項(xiàng)。路由項(xiàng)。路由器路由器R1認(rèn)為通過認(rèn)為通過路由器路由器R2存存在通往在通往NET1的傳輸路徑。的傳輸路徑。路由器路由器R2通往通往NET1的傳的傳輸路徑經(jīng)過輸路徑經(jīng)過R1，因而在因而在R1公告公告的距離上加的距離上加1。28路由器路由器R2R2先公告路由消息的情況先公告路由消息的情況n計(jì)數(shù)到無窮大是指某個實(shí)際不存在的路由項(xiàng)只有計(jì)數(shù)到無窮大是指某個實(shí)際不存在的路由項(xiàng)只有經(jīng)過反復(fù)交換，將距離增加到無窮大值（經(jīng)過反復(fù)交換，將距離增加到無窮大值（RIPRIP定定為為1616），才刪除。），才刪除。n

15、引發(fā)計(jì)數(shù)到無窮大問題的關(guān)鍵是路由項(xiàng)的公告環(huán)引發(fā)計(jì)數(shù)到無窮大問題的關(guān)鍵是路由項(xiàng)的公告環(huán)路，即從相鄰路由器學(xué)習(xí)到的路由項(xiàng)又公告該相路，即從相鄰路由器學(xué)習(xí)到的路由項(xiàng)又公告該相鄰路由器。鄰路由器。n因此，因此，RIPRIP規(guī)定：從某個相鄰路由器學(xué)習(xí)到的路規(guī)定：從某個相鄰路由器學(xué)習(xí)到的路由項(xiàng)不允許出現(xiàn)在公告該路由器的路由消息中。由項(xiàng)不允許出現(xiàn)在公告該路由器的路由消息中。n前面的計(jì)數(shù)到無窮大可以避免，但不是可以避免前面的計(jì)數(shù)到無窮大可以避免，但不是可以避免所有計(jì)數(shù)到無窮大的問題。所有計(jì)數(shù)到無窮大的問題。29水平分水平分割規(guī)則割規(guī)則 NET1 R2 R3 NET1 1 直接直接 NET1 2 R3 NET1

16、 2 R3 R1 正常收斂的情況正常收斂的情況30 NET1 R2 R3 NET1 1 直接直接 NET1 2 R3 NET1 2 R3 R1 無窮大問題是無法徹底避無窮大問題是無法徹底避免的，這是免的，這是RIPRIP的缺陷。的缺陷。 NET1 3 R2 NET1 4 R1 NET1 5 R3 31本講主要內(nèi)容本講主要內(nèi)容n路由器確定自身鏈路狀態(tài)路由器確定自身鏈路狀態(tài)n泛洪鏈路狀態(tài)通告泛洪鏈路狀態(tài)通告n構(gòu)建路由表算法構(gòu)建路由表算法nOSPFOSPF動態(tài)適應(yīng)網(wǎng)絡(luò)變化過程動態(tài)適應(yīng)網(wǎng)絡(luò)變化過程nOSPFOSPF和和RIPRIP的區(qū)別的區(qū)別nOSPFOSPF分區(qū)域建立路由表的過程分區(qū)域建立路由表的過

17、程321 1、Router IDRouter ID33HELLOHELLO報(bào)文格式和封裝過程報(bào)文格式和封裝過程用于在互連網(wǎng)絡(luò)中唯一標(biāo)識某個路由器的路由器標(biāo)識符。n通過發(fā)送、接收通過發(fā)送、接收HelloHello報(bào)文建立鄰報(bào)文建立鄰居關(guān)系；居關(guān)系；n自身狀態(tài)信息包括自身狀態(tài)信息包括直接連接的直接連接的LANLAN信信息和已經(jīng)建立鄰居息和已經(jīng)建立鄰居關(guān)系的路由器。關(guān)系的路由器。34發(fā)現(xiàn)鄰居過程發(fā)現(xiàn)鄰居過程2 2、發(fā)現(xiàn)鄰居、發(fā)現(xiàn)鄰居數(shù)據(jù)庫描述報(bào)文用于數(shù)據(jù)庫描述報(bào)文用于向?qū)Ψ焦骀溌窢顟B(tài)向?qū)Ψ焦骀溌窢顟B(tài)數(shù)據(jù)庫中存在的數(shù)據(jù)庫中存在的LSALSA 35數(shù)據(jù)庫描述報(bào)文格式數(shù)據(jù)庫描述報(bào)文格式3 3、建立鄰接

18、關(guān)系、建立鄰接關(guān)系2 2）OSPFOSPF報(bào)文格式報(bào)文格式（1 1）DDDD報(bào)文格式報(bào)文格式鏈路狀態(tài)請求報(bào)文鏈路狀態(tài)請求報(bào)文用于請求對方向其用于請求對方向其傳輸特定的傳輸特定的LSA LSA 36鏈路狀態(tài)請求報(bào)文格式鏈路狀態(tài)請求報(bào)文格式（2 2）LSRLSR報(bào)文格式報(bào)文格式鏈路狀態(tài)更新報(bào)文的作用有二，一是用于向鏈路狀態(tài)更新報(bào)文的作用有二，一是用于向LSRLSR發(fā)送者傳輸一組發(fā)送者傳輸一組完整的完整的LSALSA。二是在路由器自身鏈路狀態(tài)發(fā)生改變，或是路由器。二是在路由器自身鏈路狀態(tài)發(fā)生改變，或是路由器用于指定泛洪鏈路狀態(tài)通告周期的定時(shí)器溢出時(shí)，用于向互連用于指定泛洪鏈路狀態(tài)通告周期的定時(shí)器溢出

19、時(shí)，用于向互連網(wǎng)絡(luò)中的所有其他路由器泛洪用于表示自身鏈路狀態(tài)的網(wǎng)絡(luò)中的所有其他路由器泛洪用于表示自身鏈路狀態(tài)的LSALSA。 37鏈路狀態(tài)更新報(bào)文格式鏈路狀態(tài)更新報(bào)文格式（3 3）LSRLSR報(bào)文格式報(bào)文格式鄰接關(guān)系建立過程就鄰接關(guān)系建立過程就是兩個路由器的鏈路是兩個路由器的鏈路狀態(tài)數(shù)據(jù)庫同步過程。狀態(tài)數(shù)據(jù)庫同步過程。 38鄰接關(guān)系建立過程鄰接關(guān)系建立過程2 2）鄰接關(guān)系建立過程）鄰接關(guān)系建立過程n路由器泛洪自身鏈路狀態(tài)信息；路由器泛洪自身鏈路狀態(tài)信息；n其他路由器通過始發(fā)路由器和序號確定是否是重復(fù)接收的其他路由器通過始發(fā)路由器和序號確定是否是重復(fù)接收的鏈路狀態(tài)信息，對新接收到的鏈路狀態(tài)信息發(fā)

20、送確認(rèn)報(bào)文；鏈路狀態(tài)信息，對新接收到的鏈路狀態(tài)信息發(fā)送確認(rèn)報(bào)文；n其他路由器從他端口轉(zhuǎn)發(fā)新接收到的鏈路狀態(tài)信息。其他路由器從他端口轉(zhuǎn)發(fā)新接收到的鏈路狀態(tài)信息。39路由器路由器R1R1用泛洪方式傳輸用泛洪方式傳輸LSALSA的過程的過程n鏈路狀態(tài)信息泛洪過程；鏈路狀態(tài)信息泛洪過程；n依靠始發(fā)路由器和序號確定是否重復(fù)接收的鏈路狀態(tài)信息；依靠始發(fā)路由器和序號確定是否重復(fù)接收的鏈路狀態(tài)信息；n每一個路由器轉(zhuǎn)發(fā)時(shí)，用轉(zhuǎn)發(fā)接口的每一個路由器轉(zhuǎn)發(fā)時(shí)，用轉(zhuǎn)發(fā)接口的IPIP地址作為地址作為IPIP分組的源分組的源IPIP地址。地址。40鏈路狀態(tài)更新報(bào)文內(nèi)容和封裝格式鏈路狀態(tài)更新報(bào)文內(nèi)容和封裝格式n把互連網(wǎng)看作一

21、個無向圖，以路由器和把互連網(wǎng)看作一個無向圖，以路由器和LANLAN為結(jié)為結(jié)點(diǎn)，以互連路由器的傳輸網(wǎng)絡(luò)為邊；點(diǎn)，以互連路由器的傳輸網(wǎng)絡(luò)為邊；n每一個路由器計(jì)算以自己為根，到達(dá)其他結(jié)點(diǎn)的每一個路由器計(jì)算以自己為根，到達(dá)其他結(jié)點(diǎn)的最短路徑樹。最短路徑樹。41n令令D(v)D(v)為源結(jié)點(diǎn)（路由器為源結(jié)點(diǎn)（路由器R5R5）到達(dá)結(jié)點(diǎn)）到達(dá)結(jié)點(diǎn)v v的距離，它是從源的距離，它是從源結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)結(jié)點(diǎn)沿著某一路徑到達(dá)結(jié)點(diǎn)v v所經(jīng)過的鏈路的代價(jià)之和，所經(jīng)過的鏈路的代價(jià)之和，L(i,j)L(i,j)為結(jié)點(diǎn)為結(jié)點(diǎn)i i至結(jié)點(diǎn)至結(jié)點(diǎn)j j的距離。的距離。 n以源結(jié)點(diǎn)為樹根，求出各個結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。

22、以源結(jié)點(diǎn)為樹根，求出各個結(jié)點(diǎn)和根結(jié)點(diǎn)之間距離。n找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)找出與根結(jié)點(diǎn)距離最短的結(jié)點(diǎn)（假定為結(jié)點(diǎn)w w），將該結(jié)點(diǎn)），將該結(jié)點(diǎn)連接到以源結(jié)點(diǎn)為根的樹上，并重新對剩下的結(jié)點(diǎn)計(jì)算到連接到以源結(jié)點(diǎn)為根的樹上，并重新對剩下的結(jié)點(diǎn)計(jì)算到達(dá)根結(jié)點(diǎn)的距離，達(dá)根結(jié)點(diǎn)的距離，D (v)=MIND(v),D(w)+L(w,v)D (v)=MIND(v),D(w)+L(w,v)。n重復(fù)步驟重復(fù)步驟(2)(2)，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹上。，直到所有結(jié)點(diǎn)都連接到以源結(jié)點(diǎn)為根的樹上。 42n以路由器以路由器R5R5為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹；為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹；n根據(jù)

23、最短路徑樹可以得出通往其他結(jié)點(diǎn)的最短路根據(jù)最短路徑樹可以得出通往其他結(jié)點(diǎn)的最短路徑樹上的下一跳結(jié)點(diǎn)。徑樹上的下一跳結(jié)點(diǎn)。43最短路徑樹最短路徑樹求出以某個結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短求出以某個結(jié)點(diǎn)為根到達(dá)其他結(jié)點(diǎn)的最短路徑樹的先決條件是該結(jié)點(diǎn)擁有描述無向路徑樹的先決條件是該結(jié)點(diǎn)擁有描述無向圖的全部信息，這些信息稱為鏈路狀態(tài)信圖的全部信息，這些信息稱為鏈路狀態(tài)信息。由此可以得出息。由此可以得出OSPFOSPF建立路由表過程。建立路由表過程。n發(fā)現(xiàn)鄰居，確定到達(dá)鄰居的代價(jià)。發(fā)現(xiàn)鄰居，確定到達(dá)鄰居的代價(jià)。n泛洪鏈路狀態(tài)信息。泛洪鏈路狀態(tài)信息。n建立鏈路狀態(tài)數(shù)據(jù)庫并計(jì)算路由表。建立鏈路狀態(tài)數(shù)據(jù)庫并計(jì)算路

24、由表。44n路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開始路由器為下一跳路由器；路由項(xiàng)以到達(dá)該結(jié)點(diǎn)的分枝的開始路由器為下一跳路由器；n以到達(dá)根結(jié)點(diǎn)的距離為路由項(xiàng)距離。以到達(dá)根結(jié)點(diǎn)的距離為路由項(xiàng)距離。45最短路徑樹最短路徑樹R5R5創(chuàng)建路由表過程創(chuàng)建路由表過程n路由器路由器R2R2與與R5R5之間鏈路發(fā)生故障；之間鏈路發(fā)生故障；n路由器路由器R2R2和和R5R5通過鏈路狀態(tài)更新報(bào)文泛洪通過鏈路狀態(tài)更新報(bào)文泛洪這一變化。這一變化。46發(fā)生故障后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生故障后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)n重新根據(jù)修改后鏈路狀態(tài)庫構(gòu)建路由器重新根據(jù)修改后鏈路狀態(tài)庫構(gòu)建路由器R2R2到達(dá)其他結(jié)點(diǎn)到達(dá)其他結(jié)點(diǎn)的最短路徑樹；的最短路徑樹；n根

25、據(jù)最短路徑樹得出路由器根據(jù)最短路徑樹得出路由器R5R5到達(dá)所有結(jié)點(diǎn)的路由項(xiàng)。到達(dá)所有結(jié)點(diǎn)的路由項(xiàng)。47最短路徑樹最短路徑樹最終確認(rèn)列表內(nèi)容最終確認(rèn)列表內(nèi)容nOSPF是將部分信息泛洪給互連網(wǎng)絡(luò)中所有其他是將部分信息泛洪給互連網(wǎng)絡(luò)中所有其他路由器，而路由器，而RIP是將所有信息傳輸給相鄰路由器是將所有信息傳輸給相鄰路由器 nOSPF中，每一個路由器可以根據(jù)不同的應(yīng)用要中，每一個路由器可以根據(jù)不同的應(yīng)用要求設(shè)定鏈路代價(jià)，也可根據(jù)鏈路狀態(tài)數(shù)據(jù)庫計(jì)算求設(shè)定鏈路代價(jià)，也可根據(jù)鏈路狀態(tài)數(shù)據(jù)庫計(jì)算出多條到達(dá)指定網(wǎng)絡(luò)的傳輸路徑，以此實(shí)現(xiàn)負(fù)載出多條到達(dá)指定網(wǎng)絡(luò)的傳輸路徑，以此實(shí)現(xiàn)負(fù)載均衡。而均衡。而RIP只能得出

26、最小跳數(shù)傳輸路徑只能得出最小跳數(shù)傳輸路徑 nOSPF由于可以及時(shí)更新每一個路由器的鏈路狀由于可以及時(shí)更新每一個路由器的鏈路狀態(tài)數(shù)據(jù)庫，路由表能夠及時(shí)反映最新的互連網(wǎng)絡(luò)態(tài)數(shù)據(jù)庫，路由表能夠及時(shí)反映最新的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，而拓?fù)浣Y(jié)構(gòu)，而RIP存在好消息傳得快，壞消息傳存在好消息傳得快，壞消息傳得慢的問題得慢的問題 48n將網(wǎng)絡(luò)分將網(wǎng)絡(luò)分成一個主成一個主干區(qū)和若干區(qū)和若干個區(qū)；干個區(qū)；n其他區(qū)通其他區(qū)通過區(qū)域邊過區(qū)域邊界路由器界路由器和主干區(qū)和主干區(qū)相連。相連。49OSPFOSPF劃分區(qū)域示意圖劃分區(qū)域示意圖路由器路由器R11R11建立至網(wǎng)絡(luò)建立至網(wǎng)絡(luò)NET6NET6傳輸路徑的過傳輸路徑的過程：程：

27、n通過區(qū)域通過區(qū)域3OSPF3OSPF建立路由表過程建立區(qū)域建立路由表過程建立區(qū)域邊界路由器邊界路由器R05R05、R06R06至至NET6NET6傳輸路徑；傳輸路徑；n通過主干區(qū)域通過主干區(qū)域OSPFOSPF建立路由表過程建立建立路由表過程建立R01R01、R02R02至至NET6NET6傳輸路徑；傳輸路徑；n通過區(qū)域通過區(qū)域1OSFP1OSFP建立路由表過程建立建立路由表過程建立R11R11至至NET6NET6傳輸路徑。傳輸路徑。50區(qū)域區(qū)域3 3建立建立R06R06至至NET6NET6傳輸路傳輸路徑徑區(qū)域區(qū)域0 0建立建立R01R01至至NET6NET6傳輸路傳輸路徑徑區(qū)域區(qū)域1 1建立

28、建立R11R11至至NET6NET6傳輸路傳輸路徑徑51本講主要內(nèi)容本講主要內(nèi)容n分層路由的原因分層路由的原因nBGP報(bào)文類型報(bào)文類型nBGP工作機(jī)制工作機(jī)制52自治系統(tǒng)結(jié)構(gòu)自治系統(tǒng)結(jié)構(gòu)53nBGPBGP是一種可以在不了解各個自治系統(tǒng)內(nèi)是一種可以在不了解各個自治系統(tǒng)內(nèi)部結(jié)構(gòu)、不需要統(tǒng)一各個自治系統(tǒng)的代價(jià)部結(jié)構(gòu)、不需要統(tǒng)一各個自治系統(tǒng)的代價(jià)取值標(biāo)準(zhǔn)的情況下，在滿足政策和安全的取值標(biāo)準(zhǔn)的情況下，在滿足政策和安全的前提下建立自治系統(tǒng)之間的傳輸路徑，的前提下建立自治系統(tǒng)之間的傳輸路徑，的路由協(xié)議。路由協(xié)議。 nBGPBGP是路徑向量路由協(xié)議，選擇經(jīng)過自治是路徑向量路由協(xié)議，選擇經(jīng)過自治系統(tǒng)最少的傳輸路徑作為通往該外部網(wǎng)絡(luò)系統(tǒng)最少的傳輸路徑作為通往該外部網(wǎng)絡(luò)的傳輸路徑。的傳輸路徑。54n打開（打開（OPEN）報(bào)文）報(bào)文 n保活（?；睿↘EEPALIVE）報(bào)文）報(bào)文 n更新（更新（UPDATE）報(bào)文）報(bào)文 n通知（通知（NOTIFICATION）報(bào)文）報(bào)文 5