在介紹鏈路狀態算法之前，我們再來回憶一下DV算法，比如說RIP，RIP協議在計算路由的時候首先把自己已知的路由發送給自己的鄰居，當這個鄰居收到路由之后會與自己的路由進行比較，然后取一個***的路由添加到路由表中，同時將下一條指向發給自己路由的路由器。而OSPF鏈路狀態協議采用了一種全新的設計思想，在網絡中運行OSPF的路由器在向外發送的信息中不僅包含了路由信息，還包括了鏈路的狀態信息及網絡的拓撲結構(拓撲結構可以理解為，在網絡中使用的接口，每個接口的網絡狀況是什么樣的，以及在網絡中的互連情況)。

OSPF協議通過LSA描述網絡拓撲

在了解了OSPF協議的算法后，下面我們來看下OSPF協議是如何來描述這種信息的。首先，現存的網絡中的任何形式的組網精選后都不外乎以下四種：

***種：為整個網段中只有路由器本身運行OSPF，與這臺路由器相連的接口的其它設備都不運行OSPF。

第二種：兩臺運行OSPF協議的路由器通過點對點鏈路相連(比如PPP/HDLC)。

第三種：一臺路由器在同一個網段中通過點對多點鏈路與多個路由器相連，而這多個路由器之間不存在互連關系。

第四種：一臺路由器在一個網段中通過點對多點鏈路與多個路由器相連，但這多個路由器之間存在互連關系(也就是說在網絡中的路由器都是兩兩互通，不需要轉發而可以直接相互訪問)。

四種網絡拓撲如下圖所示：

在對網絡拓撲進行抽象描述后，我們具體講述下上圖中RTA是如何描述它身邊的這四種網絡情況。

首先我們來看***種(整個網段中只有路由器本身運行OSPF，與這臺路由器相連的接口的其它設備都不運行OSPF)無論什么路由協議，歸根結底都是為了計算出路由。在***種網絡結構中，首先要描述出自己已知的路由，那么在運行OSPF的路由器中該如何描述呢?

Link Id:192.168.1.0 /本地接口網段/

Data: 255.255.255.0 /掩碼/

Type: StubNet (3) /類型/

Metric: 5 /花費值/

由于有了網段和掩碼我們就可以描述出這條路由，上述例子描述了192.168.1.0/24網段的路由，同時，到達這個網段的花費值為5。并且把***種類型的網絡定義成3這個字符，當其他設備收到字符3時就會明白在整個網段中只有發送3字符的路由器運行OSPF協議。

接下來我們來看第二種網絡拓撲(兩臺運行OSPF協議的路由器通過點對點鏈路相連)該如何描述。第二種網絡拓撲描述的時候分兩步。首先，同***種情況類似的是，路由器需要把本地運行OSPF接口的路由信息描述出來，即：

Link Id:192.168.2.0 /網段/

Data: 255.255.255.0 /掩碼/

Type: StubNet (3) /類型/

Metric: 5 /花費值/

第二步，描述與其相連的RTB路由器。

Link Id:192.168.2.1 /RTB 的Router ID/

Data: 2.2.2.2 /RTB的接口地址/

Type: Router (1) /類型/

Metric: 20 /花費值/

在這里需要說明的是，在對RTB路由器進行描述的時候，Link ID字段必須用一個唯一的數字來表示，既不能是路由器的名稱也不能是路由器的型號，因為在整個網絡中Router ID是唯一的，所以這里用RTB的Router ID來描述RTA與RTB相連。同時，在Type字段中添加的數字為1，就表示是與一臺路由器相連。那么是否通過這些描述就能非常清楚地沒有歧義的描述出網絡拓撲呢?答案是否定的。因為RTA與RTB相連有可能是多個接口互連，比如RTA與RTB互連是通過多條串行線路。所以，當RTA知道了自己與RTB 相連后，還需要知道是與RTB的哪個接口相連，因此在Data字段中我們用RTB的接口地址來描述RTA是與RTB的那個接口相連。***，在計算到RTB 的花費。通過這些描述，RTA就能夠清楚地描述出自己的連接狀況。

OSPF對第三種網絡拓撲的描述

第三種為一臺路由器在同一個網段中通過點對多點鏈路與多個路由器相連，而這多個路由器之間不存在互連關系。首先，RTA仍然是先描述自己的接口。

Link ID： 1.1.1.1 /本地接口地址/

Data： 255.255.255.255 /掩碼/

Type： StubNet(3) /類型/

Metric： 5 /花費/

在這里需要注意的是，在第三種網絡拓撲中RTA描述自己的接口是采用的是主機地址而不是網段。

第二步描述與RTE相連

Link ID：2.2.2.2 /RTE的Router ID/

Data： 1.1.1.1 /與RTE相連的接口地址/

Type： Router(1) /類型/

Metric： 10 /花費/

第三步描述與RTF相連

Link ID：3.3.3.3 /RTF的Router ID/

Data： 1.1.1.1 /與RTF相連的接口地址/

Type： Router(1) /類型/

Metric： 20 /花費/

第四種為一臺路由器在一個網段中通過點對多點鏈路與多個路由器相連，但這多個路由器之間存在互連關系(full mesh)。

Link ID：4.4.4.4 /網段中DR的接口地址/

Data： 4.4.4.1 /本地接口地址/

Type： TransNet(2) /類型/

Metric： 20 /花費/

在第四種情況中(實際上，第四種情況可以看作是第三種拓撲的特例)，RTA并不描述自己接口的路由而是描述與DR相連的接口地址，以及DR的接口地址。在full mesh結構中，每個路由器都會生成這種LSA，其他的拓撲信息都在DR上描述。

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的產生我們會在下面講到)上的LSA和其他路由器上的LSA就可以描述出這種拓撲。那么這樣做有什么好處呢?如果我們按照第三種拓撲來描述第四種全連通的網絡，我們會發現在網絡中的每臺路由器都會生成一個很龐大的LSA。每臺路由器都要清楚而準確無誤的描述出與自己相連的路由器，如果一個網絡中有50臺路由器那么每臺路由器就需要描述1225條LSA。這會造成無謂的帶寬浪費和設備性能的下降。而通過DR來生成LSA就大大緩解了這種情況的發生。

在現存的網絡拓撲中，OSPF通過LSA都能準確無誤的描述出來。在路由器向其他設備通告LSA的時候還需要加上一個頭(head)。以下是Head的結構。

Type： Router /LSA的類型，可以看出此例是異地中情況的LSA/

Ls ID：1.1.1.1 /LSA的標示/

Adv rtr: 1.1.1.1 /生成LSA的路由器/

Ls Age: 40 /本條LSA的老化時間/

Length: 108 /LSA的長度/

Seq# 70000001 /LSA的序號/

Cksum: 0x3543 /校驗和/

Link Count：7 /本條LSA中包含的連接個數/

至此，LSA加上Head后就完成了對自己周邊拓撲的描述。

對網絡拓撲完成以后，接下來的工作就是進行路由計算了。在學習OSPF路由計算之前，我們先回憶一下使用DV算法計算路由的RIP協議。使用RIP協議的路由器在收到鄰居發送過來的路由信息后，將收到的路由信息添加到自己的路由表中。這個路由信息是誰發給我的，我便將自己的下一條指向這個路由器。OSPF 協議算法相對來說比較復雜，它采用了SPF算法，SPF算法是OSPF路由協議的基礎。SPF算法有時也被稱為Dijkstra算法，這是因為最短路徑優先算法SPF是Dijkstra發明的。SPF算法將每一個路由器作為根(ROOT)來計算其到每一個目的地路由器的距離，每一個路由器根據一個統一的數據庫會計算出路由域的拓撲結構圖，該結構圖類似于一棵樹，在SPF算法中，被稱為最短路徑樹。在OSPF路由協議中，最短路徑樹的樹干長度，即OSPF路由器至每一個目的地路由器的距離，稱為OSPF的Cost，其算法為：Cost = 100×106/鏈路帶寬

在這里，鏈路帶寬以bps來表示。也就是說，OSPF的Cost 與鏈路的帶寬成反比，帶寬越高，Cost越小，表示OSPF到目的地的距離越近。舉例來說，FDDI或快速以太網的Cost為1，2M串行鏈路的Cost 為48，10M以太網的Cost為10等。作為一種典型的鏈路狀態的路由協議，OSPF還得遵循鏈路狀態路由協議的統一算法。鏈路狀態的算法非常簡單，在這里將鏈路狀態算法概括為以下四個步驟：

1、當路由器初始化或當網絡結構發生變化(例如增減路由器，鏈路狀態發生變化等)時，路由器會產生鏈路狀態廣播數據包LSA(Link-State Advertisement)，該數據包里包含路由器上所有相連鏈路，也即為所有端口的狀態信息。

2、所有路由器會通過一種被稱為刷新(Flooding)的方法來交換鏈路狀態數據。Flooding是指路由器將其LSA數據包傳送給所有與其相鄰的OSPF路由器，相鄰路由器根據其接收到的鏈路狀態信息更新自己的數據庫，并將該鏈路狀態信息轉送給與其相鄰的路由器，直至穩定的一個過程。

3、 當網絡重新穩定下來，也可以說OSPF路由協議收斂下來時，所有的路由器會根據其各自的鏈路狀態信息數據庫計算出各自的路由表。該路由表中包含路由器到每一個可到達目的地的Cost以及到達該目的地所要轉發的下一個路由器(next-hop)。

4、 第4個步驟實際上是指OSPF路由協議的一個特性。當網絡狀態比較穩定時，網絡中傳遞的鏈路狀態信息是比較少的，或者可以說，當網絡穩定時，網絡中是比較安靜的。這也正是鏈路狀態路由協議區別與距離矢量路由協議的一大特點。

下面我們舉例來看OSPF是如何計算路由的。首先，每個路由器都向自己的鄰居發送自己的網絡拓撲結構，生成一個LSA的數據結構，并且將這個數據結構發送給網絡中每一臺運行OSPF的路由器，從而每一臺運行OSPF協議的路由器將LSA組合起來形成一個LSDB。在每個路由器都得到相同的 LSDB后路由器會依據LSA進行路由計算，在進行路由計算的時候路由器會把LSDB打開，進行每一段的搜尋。詳細過程可以參考下圖：

每一臺路由器都已自己為根節點來使用SPF算來計算路由。拿上圖來舉例說明：RTA收到每臺路由器傳來的LSA后形成LSDB，然后打開LSDB進行每一段的搜尋。當檢索到Type字段為StubNet的時候，RTA知道描述的是一條路由，于是將這條路由添加到自己的路由表中(實際上，這些路由是RTA的本地接口路由)。當檢索的LSA中Type字段為Router的時候，RTA知道它是與一臺路由器相連(從這條LSA中可以獲知相連路由器的接口地址和 Router ID以及到達相連路由器的花費)。這個時候，路由計算會停止，RTA會根據Link ID尋找與其相連路由器生成的LSA。因為在LSA的Head中有Router ID，所以，RTA會以Router ID為關鍵字進行檢索從而計算出到RTB的路由，并添加到路由表中。假設RTB還與RTC相連，那么RTA在查找由RTB生成的LSA時，會發現RTB生成的LSA中Type字段也為Router，這個時候RTA停止計算，重新以RTC的Router ID為關鍵字在LSDB中檢索，然后將RTC的路由添加到自己的路由表中，同時RTA得知通過RTB可以到達RTC，在添加路由Metric值時就將 RTC到RTB，RTB到RTA的Metric值相加，得到RTA到達RTC的Metric。

OSPF協議路由計算過程

***步，網絡中所有運行OSPF協議的路由器都清楚地描述自己鄰居的拓撲結構，并生成LSA。

第二步，將LSA傳給給自己相鄰的路由器，保證網絡中所有路由器都收到其他路由器的LSA，最終形成LSDB。

第三步，通過LSDB計算出一張帶權的有向圖，最終形成統一的路由表。