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

　　在介紹鏈路狀態算法之前，我們再來回憶一下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協議的路由器