路由表的建立算法

1、路由表

1）什么是路由表

路由表是指路由器或者其他互聯(lián)網(wǎng)網(wǎng)絡(luò)設(shè)備上存儲(chǔ)的一張路由信息表，該表中存有到達(dá)特定網(wǎng)絡(luò)終端的路徑，在某些情況下，還有一些與這些路徑相關(guān)的度量。

2）路由表分類

（1）靜態(tài)路由表

由系統(tǒng)管理員事先設(shè)置好固定的路由表稱之為靜態(tài)路由表，一般是在系統(tǒng)安裝時(shí)就根據(jù)網(wǎng)絡(luò)的配置情況預(yù)先設(shè)定的，它不會(huì)隨未來(lái)網(wǎng)絡(luò)結(jié)構(gòu)的改變而改變。

（2）動(dòng)態(tài)路由表

動(dòng)態(tài)路由表是路由器根據(jù)網(wǎng)絡(luò)系統(tǒng)的運(yùn)行情況而自動(dòng)調(diào)整的路由表。路由器根據(jù)路由選擇協(xié)議（Routing Protocol）提供的功能，自動(dòng)學(xué)習(xí)和記憶網(wǎng)絡(luò)運(yùn)行情況，在需要時(shí)自動(dòng)計(jì)算數(shù)據(jù)傳輸?shù)淖罴崖窂健?/p>

2、路由表項(xiàng)

• 目的地址：用來(lái)標(biāo)識(shí)IP包的目的地址或者目的網(wǎng)絡(luò)。

• 網(wǎng)絡(luò)掩碼：與目的地址一起標(biāo)識(shí)目的主機(jī)或者路由器所在的網(wǎng)段的地址。

pre：標(biāo)識(shí)路由加入IP路由表的優(yōu)先級(jí)。可能到達(dá)一個(gè)目的地有多條路由，但是優(yōu)先級(jí)的存在讓他們先選擇優(yōu)先級(jí)高的路由進(jìn)行利用。

cost：路由開銷，當(dāng)?shù)竭_(dá)一個(gè)目的地的多個(gè)路由優(yōu)先級(jí)相同時(shí)，路由開銷最小的將成為最優(yōu)路由。

interface：輸出接口，說(shuō)明IP包將從該路由器哪個(gè)接口轉(zhuǎn)發(fā)。

nexthop：下一跳IP地址，說(shuō)明IP包所經(jīng)過(guò)的下一個(gè)路由器。

3、路由表的相關(guān)算法

1）總體式路由算法。

采用總體式路由算法時(shí)，每個(gè)路由器都擁有網(wǎng)絡(luò)中所有其他路由器的全部信息以及網(wǎng)絡(luò)的流量狀態(tài)。這些算法也被稱為L(zhǎng)S（鏈路狀態(tài)）算法。

2）分散式路由算法

采用分散式路由算法時(shí)，每個(gè)路由器只有與它直接相連的路由器的信息——而沒(méi)有網(wǎng)絡(luò)中的每個(gè)路由器的信息。這些算法也被稱為DV（距離向量）算法。

距離向量路由算法，也叫做最大流量演算法，其被距離向量協(xié)議作為一個(gè)算法，如RIP就是一種分布式的基于距離向量的路由選擇協(xié)議。使用這個(gè)算法的路由器必須掌握這個(gè)距離表，它告訴在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最遠(yuǎn)和距離。在距離表中的這個(gè)信息是根據(jù)臨近接點(diǎn)信息的改變而時(shí)時(shí)更新的。表中數(shù)據(jù)的量和在網(wǎng)絡(luò)中的所有的接點(diǎn)(除了它自己本身)是等同的。這個(gè)表中的列代表直接和它相連的鄰居，行代表在網(wǎng)絡(luò)中的所有目的地。每個(gè)數(shù)據(jù)包括傳送數(shù)據(jù)包到每個(gè)在網(wǎng)上的目的地的路徑和距離/或時(shí)間在那個(gè)路徑上來(lái)傳輸(我們叫這個(gè)為“成本”)。這個(gè)在那個(gè)算法中的度量公式是跳躍的次數(shù)， 等待時(shí)間，流出數(shù)據(jù)包的數(shù)量，等等。

在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，路由器之間也將及時(shí)地相互通知有關(guān)變更信息。

鏈路狀態(tài)算法的思想是要求網(wǎng)絡(luò)中所有參與鏈路狀態(tài)路由協(xié)議的路由器都掌握網(wǎng)絡(luò)的全部拓?fù)浣Y(jié)構(gòu)信息，并記錄在路由數(shù)據(jù)庫(kù)中。鏈路狀態(tài)算法中路由數(shù)據(jù)庫(kù)實(shí)質(zhì)上是一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)鋱D，該拓?fù)鋱D由一個(gè)節(jié)點(diǎn)的集合和一個(gè)邊的集合構(gòu)成。在網(wǎng)絡(luò)拓?fù)鋱D中，結(jié)點(diǎn)代表網(wǎng)絡(luò)中路由器，邊代表路由器之間的物理鏈路。在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態(tài)、距離或費(fèi)用等。如果沒(méi)一個(gè)路由器所保存的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖都是一致的，那么個(gè)路由器生成的路由表也是最佳的，不存在錯(cuò)誤路由或循環(huán)路由。

特征一：向本自治系統(tǒng)中的所有路由器發(fā)送信息。這里使用的方法是洪泛法（Flooding），即路由器通過(guò)所有的輸出端口向所有的相鄰路由器發(fā)送信息。而每一個(gè)路由器又將此信息發(fā)往其所有的相鄰的路由器（但不包括剛剛發(fā)來(lái)信息的那個(gè)路由器）。

特征二：發(fā)送的信息就是本路由器相鄰的所有路由器的鏈路狀態(tài)，但這只是路由器所知道的部分信息。所謂“鏈路狀態(tài)”就是說(shuō)明本路由器和那些路由器相鄰，以及該鏈路的“度量”。對(duì)于OSPF，鏈路狀態(tài)的“度量”主要用來(lái)表示費(fèi)用、距離、時(shí)延、帶寬等。

特征三：只有當(dāng)鏈路狀態(tài)發(fā)生改變時(shí)，路由器才用洪泛法向所有路由器發(fā)送此信息。

OSPF就是使用分布式的鏈路狀態(tài)協(xié)議。