OSPF協(xié)議通過LSA描述網(wǎng)絡(luò)拓?fù)?/h1>
在介紹鏈路狀態(tài)算法之前，我們再來回憶一下DV算法，比如說RIP，RIP協(xié)議在計(jì)算路由的時候首先把自己已知的路由發(fā)送給自己的鄰居，當(dāng)這個鄰居收到路由之后會與自己的路由進(jìn)行比較，然后取一個***的路由添加到路由表中，同時將下一條指向發(fā)給自己路由的路由器。而OSPF鏈路狀態(tài)協(xié)議采用了一種全新的設(shè)計(jì)思想，在網(wǎng)絡(luò)中運(yùn)行OSPF的路由器在向外發(fā)送的信息中不僅包含了路由信息，還包括了鏈路的狀態(tài)信息及網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)(拓?fù)浣Y(jié)構(gòu)可以理解為，在網(wǎng)絡(luò)中使用的接口，每個接口的網(wǎng)絡(luò)狀況是什么樣的，以及在網(wǎng)絡(luò)中的互連情況)。
OSPF協(xié)議通過LSA描述網(wǎng)絡(luò)拓?fù)?/strong>
在了解了OSPF協(xié)議的算法后，下面我們來看下OSPF協(xié)議是如何來描述這種信息的。首先，現(xiàn)存的網(wǎng)絡(luò)中的任何形式的組網(wǎng)精選后都不外乎以下四種：
***種：為整個網(wǎng)段中只有路由器本身運(yùn)行OSPF，與這臺路由器相連的接口的其它設(shè)備都不運(yùn)行OSPF。
第二種：兩臺運(yùn)行OSPF協(xié)議的路由器通過點(diǎn)對點(diǎn)鏈路相連(比如PPP/HDLC)。
第三種：一臺路由器在同一個網(wǎng)段中通過點(diǎn)對多點(diǎn)鏈路與多個路由器相連，而這多個路由器之間不存在互連關(guān)系。
第四種：一臺路由器在一個網(wǎng)段中通過點(diǎn)對多點(diǎn)鏈路與多個路由器相連，但這多個路由器之間存在互連關(guān)系(也就是說在網(wǎng)絡(luò)中的路由器都是兩兩互通，不需要轉(zhuǎn)發(fā)而可以直接相互訪問)。
四種網(wǎng)絡(luò)拓?fù)淙缦聢D所示：
在對網(wǎng)絡(luò)拓?fù)溥M(jìn)行抽象描述后，我們具體講述下上圖中RTA是如何描述它身邊的這四種網(wǎng)絡(luò)情況。
首先我們來看***種(整個網(wǎng)段中只有路由器本身運(yùn)行OSPF，與這臺路由器相連的接口的其它設(shè)備都不運(yùn)行OSPF)無論什么路由協(xié)議，歸根結(jié)底都是為了計(jì)算出路由。在***種網(wǎng)絡(luò)結(jié)構(gòu)中，首先要描述出自己已知的路由，那么在運(yùn)行OSPF的路由器中該如何描述呢?
Link Id:192.168.1.0 /本地接口網(wǎng)段/
Data: 255.255.255.0 /掩碼/
Type: StubNet (3) /類型/
Metric: 5 /花費(fèi)值/
由于有了網(wǎng)段和掩碼我們就可以描述出這條路由，上述例子描述了192.168.1.0/24網(wǎng)段的路由，同時，到達(dá)這個網(wǎng)段的花費(fèi)值為5。并且把***種類型的網(wǎng)絡(luò)定義成3這個字符，當(dāng)其他設(shè)備收到字符3時就會明白在整個網(wǎng)段中只有發(fā)送3字符的路由器運(yùn)行OSPF協(xié)議。
接下來我們來看第二種網(wǎng)絡(luò)拓?fù)?兩臺運(yùn)行OSPF協(xié)議的路由器通過點(diǎn)對點(diǎn)鏈路相連)該如何描述。第二種網(wǎng)絡(luò)拓?fù)涿枋龅臅r候分兩步。首先，同***種情況類似的是，路由器需要把本地運(yùn)行OSPF接口的路由信息描述出來，即：
Link Id:192.168.2.0 /網(wǎng)段/
Data: 255.255.255.0 /掩碼/
Type: StubNet (3) /類型/
Metric: 5 /花費(fèi)值/
第二步，描述與其相連的RTB路由器。
Link Id:192.168.2.1 /RTB 的Router ID/
Data: 2.2.2.2 /RTB的接口地址/
Type: Router (1) /類型/
Metric: 20 /花費(fèi)值/
在這里需要說明的是，在對RTB路由器進(jìn)行描述的時候，Link ID字段必須用一個唯一的數(shù)字來表示，既不能是路由器的名稱也不能是路由器的型號，因?yàn)樵谡麄€網(wǎng)絡(luò)中Router ID是唯一的，所以這里用RTB的Router ID來描述RTA與RTB相連。同時，在Type字段中添加的數(shù)字為1，就表示是與一臺路由器相連。那么是否通過這些描述就能非常清楚地沒有歧義的描述出網(wǎng)絡(luò)拓?fù)淠?答案是否定的。因?yàn)镽TA與RTB相連有可能是多個接口互連，比如RTA與RTB互連是通過多條串行線路。所以，當(dāng)RTA知道了自己與RTB 相連后，還需要知道是與RTB的哪個接口相連，因此在Data字段中我們用RTB的接口地址來描述RTA是與RTB的那個接口相連。***，在計(jì)算到RTB 的花費(fèi)。通過這些描述，RTA就能夠清楚地描述出自己的連接狀況。
OSPF對第三種網(wǎng)絡(luò)拓?fù)涞拿枋?/strong>
第三種為一臺路由器在同一個網(wǎng)段中通過點(diǎn)對多點(diǎn)鏈路與多個路由器相連，而這多個路由器之間不存在互連關(guān)系。首先，RTA仍然是先描述自己的接口。
Link ID： 1.1.1.1 /本地接口地址/
Data： 255.255.255.255 /掩碼/
Type： StubNet(3) /類型/
Metric： 5 /花費(fèi)/
在這里需要注意的是，在第三種網(wǎng)絡(luò)拓?fù)渲蠷TA描述自己的接口是采用的是主機(jī)地址而不是網(wǎng)段。
第二步描述與RTE相連
Link ID：2.2.2.2 /RTE的Router ID/
Data： 1.1.1.1 /與RTE相連的接口地址/
Type： Router(1) /類型/
Metric： 10 /花費(fèi)/
第三步描述與RTF相連
Link ID：3.3.3.3 /RTF的Router ID/
Data： 1.1.1.1 /與RTF相連的接口地址/
Type： Router(1) /類型/
Metric： 20 /花費(fèi)/
第四種為一臺路由器在一個網(wǎng)段中通過點(diǎn)對多點(diǎn)鏈路與多個路由器相連，但這多個路由器之間存在互連關(guān)系(full mesh)。
Link ID：4.4.4.4 /網(wǎng)段中DR的接口地址/
Data： 4.4.4.1 /本地接口地址/
Type： TransNet(2) /類型/
Metric： 20 /花費(fèi)/
在第四種情況中(實(shí)際上，第四種情況可以看作是第三種拓?fù)涞奶乩?，RTA并不描述自己接口的路由而是描述與DR相連的接口地址，以及DR的接口地址。在full mesh結(jié)構(gòu)中，每個路由器都會生成這種LSA，其他的拓?fù)湫畔⒍荚贒R上描述。
DR生成的LSA
Net Mask：255.255.255.0
Attached： 4.4.4.1
Attached： 4.4.4.2
Attached： 4.4.4.3
通過DR(DR的產(chǎn)生我們會在下面講到)上的LSA和其他路由器上的LSA就可以描述出這種拓?fù)?。那么這樣做有什么好處呢?如果我們按照第三種拓?fù)鋪砻枋龅谒姆N全連通的網(wǎng)絡(luò)，我們會發(fā)現(xiàn)在網(wǎng)絡(luò)中的每臺路由器都會生成一個很龐大的LSA。每臺路由器都要清楚而準(zhǔn)確無誤的描述出與自己相連的路由器，如果一個網(wǎng)絡(luò)中有50臺路由器那么每臺路由器就需要描述1225條LSA。這會造成無謂的帶寬浪費(fèi)和設(shè)備性能的下降。而通過DR來生成LSA就大大緩解了這種情況的發(fā)生。
在現(xiàn)存的網(wǎng)絡(luò)拓?fù)渲?，OSPF通過LSA都能準(zhǔn)確無誤的描述出來。在路由器向其他設(shè)備通告LSA的時候還需要加上一個頭(head)。以下是Head的結(jié)構(gòu)。
Type： Router /LSA的類型，可以看出此例是異地中情況的LSA/
Ls ID：1.1.1.1 /LSA的標(biāo)示/
Adv rtr: 1.1.1.1 /生成LSA的路由器/
Ls Age: 40 /本條LSA的老化時間/
Length: 108 /LSA的長度/
Seq# 70000001 /LSA的序號/
Cksum: 0x3543 /校驗(yàn)和/
Link Count：7 /本條LSA中包含的連接個數(shù)/
至此，LSA加上Head后就完成了對自己周邊拓?fù)涞拿枋觥?/p>
對網(wǎng)絡(luò)拓?fù)渫瓿梢院?，接下來的工作就是進(jìn)行路由計(jì)算了。在學(xué)習(xí)OSPF路由計(jì)算之前，我們先回憶一下使用DV算法計(jì)算路由的RIP協(xié)議。使用RIP協(xié)議的路由器在收到鄰居發(fā)送過來的路由信息后，將收到的路由信息添加到自己的路由表中。這個路由信息是誰發(fā)給我的，我便將自己的下一條指向這個路由器。OSPF 協(xié)議算法相對來說比較復(fù)雜，它采用了SPF算法，SPF算法是OSPF路由協(xié)議的基礎(chǔ)。SPF算法有時也被稱為Dijkstra算法，這是因?yàn)樽疃搪窂絻?yōu)先算法SPF是Dijkstra發(fā)明的。SPF算法將每一個路由器作為根(ROOT)來計(jì)算其到每一個目的地路由器的距離，每一個路由器根據(jù)一個統(tǒng)一的數(shù)據(jù)庫會計(jì)算出路由域的拓?fù)浣Y(jié)構(gòu)圖，該結(jié)構(gòu)圖類似于一棵樹，在SPF算法中，被稱為最短路徑樹。在OSPF路由協(xié)議中，最短路徑樹的樹干長度，即OSPF路由器至每一個目的地路由器的距離，稱為OSPF的Cost，其算法為：Cost = 100×106/鏈路帶寬
在這里，鏈路帶寬以bps來表示。也就是說，OSPF的Cost 與鏈路的帶寬成反比，帶寬越高，Cost越小，表示OSPF到目的地的距離越近。舉例來說，F(xiàn)DDI或快速以太網(wǎng)的Cost為1，2M串行鏈路的Cost 為48，10M以太網(wǎng)的Cost為10等。作為一種典型的鏈路狀態(tài)的路由協(xié)議，OSPF還得遵循鏈路狀態(tài)路由協(xié)議的統(tǒng)一算法。鏈路狀態(tài)的算法非常簡單，在這里將鏈路狀態(tài)算法概括為以下四個步驟：
1、當(dāng)路由器初始化或當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化(例如增減路由器，鏈路狀態(tài)發(fā)生變化等)時，路由器會產(chǎn)生鏈路狀態(tài)廣播數(shù)據(jù)包LSA(Link-State Advertisement)，該數(shù)據(jù)包里包含路由器上所有相連鏈路，也即為所有端口的狀態(tài)信息。
2、所有路由器會通過一種被稱為刷新(Flooding)的方法來交換鏈路狀態(tài)數(shù)據(jù)。Flooding是指路由器將其LSA數(shù)據(jù)包傳送給所有與其相鄰的OSPF路由器，相鄰路由器根據(jù)其接收到的鏈路狀態(tài)信息更新自己的數(shù)據(jù)庫，并將該鏈路狀態(tài)信息轉(zhuǎn)送給與其相鄰的路由器，直至穩(wěn)定的一個過程。
3、 當(dāng)網(wǎng)絡(luò)重新穩(wěn)定下來，也可以說OSPF路由協(xié)議收斂下來時，所有的路由器會根據(jù)其各自的鏈路狀態(tài)信息數(shù)據(jù)庫計(jì)算出各自的路由表。該路由表中包含路由器到每一個可到達(dá)目的地的Cost以及到達(dá)該目的地所要轉(zhuǎn)發(fā)的下一個路由器(next-hop)。
4、 第4個步驟實(shí)際上是指OSPF路由協(xié)議的一個特性。當(dāng)網(wǎng)絡(luò)狀態(tài)比較穩(wěn)定時，網(wǎng)絡(luò)中傳遞的鏈路狀態(tài)信息是比較少的，或者可以說，當(dāng)網(wǎng)絡(luò)穩(wěn)定時，網(wǎng)絡(luò)中是比較安靜的。這也正是鏈路狀態(tài)路由協(xié)議區(qū)別與距離矢量路由協(xié)議的一大特點(diǎn)。
下面我們舉例來看OSPF是如何計(jì)算路由的。首先，每個路由器都向自己的鄰居發(fā)送自己的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，生成一個LSA的數(shù)據(jù)結(jié)構(gòu)，并且將這個數(shù)據(jù)結(jié)構(gòu)發(fā)送給網(wǎng)絡(luò)中每一臺運(yùn)行OSPF的路由器，從而每一臺運(yùn)行OSPF協(xié)議的路由器將LSA組合起來形成一個LSDB。在每個路由器都得到相同的 LSDB后路由器會依據(jù)LSA進(jìn)行路由計(jì)算，在進(jìn)行路由計(jì)算的時候路由器會把LSDB打開，進(jìn)行每一段的搜尋。詳細(xì)過程可以參考下圖：
每一臺路由器都已自己為根節(jié)點(diǎn)來使用SPF算來計(jì)算路由。拿上圖來舉例說明：RTA收到每臺路由器傳來的LSA后形成LSDB，然后打開LSDB進(jìn)行每一段的搜尋。當(dāng)檢索到Type字段為StubNet的時候，RTA知道描述的是一條路由，于是將這條路由添加到自己的路由表中(實(shí)際上，這些路由是RTA的本地接口路由)。當(dāng)檢索的LSA中Type字段為Router的時候，RTA知道它是與一臺路由器相連(從這條LSA中可以獲知相連路由器的接口地址和 Router ID以及到達(dá)相連路由器的花費(fèi))。這個時候，路由計(jì)算會停止，RTA會根據(jù)Link ID尋找與其相連路由器生成的LSA。因?yàn)樵贚SA的Head中有Router ID，所以，RTA會以Router ID為關(guān)鍵字進(jìn)行檢索從而計(jì)算出到RTB的路由，并添加到路由表中。假設(shè)RTB還與RTC相連，那么RTA在查找由RTB生成的LSA時，會發(fā)現(xiàn)RTB生成的LSA中Type字段也為Router，這個時候RTA停止計(jì)算，重新以RTC的Router ID為關(guān)鍵字在LSDB中檢索，然后將RTC的路由添加到自己的路由表中，同時RTA得知通過RTB可以到達(dá)RTC，在添加路由Metric值時就將 RTC到RTB，RTB到RTA的Metric值相加，得到RTA到達(dá)RTC的Metric。
OSPF協(xié)議路由計(jì)算過程
***步，網(wǎng)絡(luò)中所有運(yùn)行OSPF協(xié)議的路由器都清楚地描述自己鄰居的拓?fù)浣Y(jié)構(gòu)，并生成LSA。
第二步，將LSA傳給給自己相鄰的路由器，保證網(wǎng)絡(luò)中所有路由器都收到其他路由器的LSA，最終形成LSDB。
第三步，通過LSDB計(jì)算出一張帶權(quán)的有向圖，最終形成統(tǒng)一的路由表。
