一種避免冗餘Flood的方法
2023-06-03 00:51:06 1
專利名稱：一種避免冗餘Flood的方法
技術領域：
本發明涉及網絡通信技術領域，尤其涉及一種避免冗餘Flood的方法。
背景技術：
OSPF(開放最短路徑優先協議)是運行於IP(網際協議)之上的協議，它沒有利用TCP(傳輸控制協議)進行報文的傳輸，因此保證報文的可靠傳輸就成為OSPF協議的一部分。目前OSPF協議可以充分保證報文的可靠傳輸，但是在兩臺路由器之間存在多條並行鏈路的情況下卻會出現傳輸冗餘的情況。並行鏈路的數量越多，冗餘傳輸的情況也就越嚴重。如果能夠避免冗餘的傳輸，那就能很大地提高路由器的處理效率。
OSPF的網絡類型P2P，NBMA，Broadcast。P2P就是點到點類型，意思是一條鏈路只能使兩臺路由器通信。NBMA和Broadcast(廣播網)的行為是一致的，這種網絡中的路由器分為三種角色(以一個廣播網為例)DR(一定會有且僅一個)，BDR(是DR的備份路由器，DR壞了BDR就自動成為DR了，不一定有，但最多只能一個)，DRother(數量沒有限制，可以有，可以沒有)。DR、BDR、DRother的概念僅存在於NBMA和Broadcase網絡中，P2P中不存在也沒有對應的角色。DR、BDR是路由器自動選舉產生的，DRother就是除去DR和BDR的路由器了。
顯式ACK在任何類型的網絡上，如果路由器A給B發送一個LSA，然後B回給A一個ACK報文的話，這種確認的方式叫做顯式ACK。
隱式ACK在NBMA和Broadcast類型的網絡上，如果DRother給DR發送一個LSA，協議規定DR只能給DRother回那個收到的LSA，這種類型叫做隱式ACK。
根據OSPF標準(RFC2328)，一臺路由器收到一條LSA(鏈路狀態通告)後應該向所有其它鄰居Flood。接收端在收到LSA後會發送一個ACK給發送端。如果發送端在一定時間內沒有收到確認，它會把LSA再Flood一次，直到收到ACK為止。這樣一個Flood周期就完成了。
圖1中的拓撲結構，Flood LSA的過程如圖2所示，RTA和RTB都運行OSPF協議，它們之間有三條並行鏈路，對應的接口分別為s0、s1和s2。假設RTB向RTA Flood一條LSA，根據OSPF標準，LSA會分別從RTB的接口s0、s1、s2向RTA Flood；RTA會分別從三個接口收到三份相同的LSA，再假設s0接口的LSA先到達RTA，RTA會把該LSA從其接口s1、s2給Flood回RTB，然後再從接口s0發一個ACK給RTB，通知RTB在接口s0上發送的LSA已經收到了；接下來RTB從s1、s2 Flood出來的LSA也陸續到達RTA，RTA會認為這兩個LSA是重複的LSA，它會分別在s1、s2發送一個ACK告訴RTB從上述兩個接口Flood的LSA已經收到了。
發明內容
從圖2可以看到，三個並行鏈路的情況下，兩臺路由器報文發送總的次數共六次。事實上，在圖1中的兩臺路由器之間冗餘Flood的發送有兩次分別是RTA收到RTB Flood過來的LSA後又分別從接口s1和s2把該LSA Flood回去，在圖2中用虛線顯示。如果RTA不Flood這兩條LSA，那麼RTA和RTB都能提高2/6(33％)的效率。而且並行鏈路越多，冗餘Flood的LSA越多。四條鏈路會冗餘Flood 3條LSA，浪費的效率是3/8(37％)。隨著鏈路的增加，冗餘Flood的LSA就越多，浪費的效率會越來越趨近於50％。
本發明的發明目的是提供一種避免冗餘Flood的方法，通過本發明，通過本發明，可以消除冗餘Flood的LSA，利用本發明可以有效減少報文的Flood，同時減少報文的接收處理，降低了帶寬的佔用。
本發明的目的是通過以下技術方案實現的一種避免冗餘Flood的方法，適用於開放最短優先路徑OSPF多鏈路情況，該方法包括A.路由器的一個接口收到一個鏈路狀態廣播LSA，查詢所述LSA的發送方，記錄所述發送方的標識Router-id；B.遍歷所述路由器所有的接口下的所有的鄰居，每一次遍歷過程中，如果當前的鄰居滿足特定條件，則不向該鄰居Flood LSA。
所述的一種避免冗餘Flood的方法，步驟A中所述的LSA，是所述路由器接口收到的比自己資料庫中更新的、非所述路由器接口生成的鏈路狀態廣播LSA。
所述的一種避免冗餘Flood的方法，步驟A中所述的發送方的標識Router-id，置於所述LSA的域中；或者，通過函數的參數來傳遞。
所述的一種避免冗餘Flood的方法，所述步驟B中遍歷所有的接口下的所有的鄰居之前，確定每一個接口、每一個鄰居存在。
所述的一種避免冗餘Flood的方法，所述步驟B中鄰居滿足的條件包括當前的鄰居的標識Router-id和所述記錄的標識Router-id相同，並且不需要Flood隱式ACK。
所述的一種避免冗餘Flood的方法，所述步驟B中判斷不需要Flood隱式ACK的情況包括所述路由器不是指定路由器DR，或者發送所述LSA的鄰居不是非指定路由器DRother。
所述的一種避免冗餘Flood的方法，所述步驟B還包括每一次遍歷過程中，如果當前的鄰居不滿足所述的條件，則向該鄰居Flood LSA。
所述的一種避免冗餘Flood的方法，有多條並行鏈路時，如果存在一條可靠鏈路，則只在該條鏈路上Flood LSA。
圖1為拓撲結構示意圖。
圖2為已有技術中發送LSA的示意圖。
圖3a為本發明中發送LSA的示意圖。
圖3b為本發明中發送LSA的示意圖。
圖4為本發明中發送LSA的流程圖。
具體實施例方式
貫穿說明書，示出的該優選實施例和示例應被看作本發明的範例而不受限制。
路由器Router每次收到一條LSA查詢該條LSA是由哪一個鄰居Flood的，記錄該路由器的標識Router-id；遍歷所有接口下的所有的鄰居路由器，與已經記錄的標識Router-id比較；如果標識Router-id相同並且不需要Flood隱式ACK，則跳過該鄰居取下一個鄰居，否則，向該鄰居Flood LSA。
本發明提供的一種避免冗餘Flood的方法，具體實施流程如圖4所示，其中，
步驟410路由器的一個接口收到一個比自己資料庫中更新的，且非自己產生的鏈路狀態廣播LSA；步驟420在所述接口下的鄰居表中根據源IP位址查找到發送所述LSA的鄰居，記錄下該路由器的標識Router-id，取第一個接口；步驟430如果所述接口不存在，則跳轉到步驟540；步驟440所述接口存在，如果所述路由器自己是指定路由器DR，並且鄰居是非指定路由器DRother，則所述接口發送隱式ACK，否則，跳轉到步驟460；步驟450取所述路由器的下一接口，跳轉到步驟430；步驟460發送顯式ACK，取第一個鄰居；步驟470如果鄰居不存在，跳轉到步驟450；步驟480如果鄰居關係沒有建立，跳轉到步驟520；步驟490如果路由器自己是非指定路由器DRother，且LSA是指定路由器DR或備份指定路由器BDR發送過來的，跳轉到步驟450；步驟500假如路由器自己是備份指定路由器BDR，則跳轉到步驟450；步驟510
路由器自己不是是備份指定路由器BDR，假如當前鄰居的標識Router-id和發送這個LSA的鄰居的標識Router-id相同，則跳轉到步驟530；步驟520給這個鄰居發送LSA；步驟530取下一個鄰居，跳轉到步驟470。
步驟540結束。
此時，Flood LSA的示意圖如圖3a所示，如果RTA不Flood圖2中虛線表示的兩條冗餘LSA，那麼RTA和RTB都能提高2÷6＝33％的效率，而且並行鏈路越多，冗餘Flood的LSA越多。隨著鏈路的增加，冗餘Flood的LSA就越多，浪費的效率會越來越趨近於50％，因此，本發明最大可減少50％的總報文Flood量。
如圖3b所示，如果在多條並行鏈路的情況下能夠確保其中某一條鏈路一定可靠，則可以指定LSA只在該條鏈路上Flood，這樣就能夠更進一步地降低冗餘的LSA Flood和接收。以圖1中的拓撲為例，如果指定RTB在s0接口上FloodLSA，那麼當RTB要向RTA Flood一條LSA時，它只會從s0接口Flood給RTA，而不會再從s1或s2 Flood LSA。這樣在多條並行鏈路的情況下，Flood LSA時就可以把多條鏈路看成一條鏈路，使得報文Flood、接收的效率達到最高。也就是說一條LSA僅僅兩個報文就夠了，比改進前減少了四個報文，效率提高了66％。
通過本發明可以判斷鄰居上是否已經存在該LSA，如果該鄰居上存在該LSA，則不再向其Flood該LSA，如果該鄰居上不存在該LSA，且存在一條可靠鏈路，則只在該條鏈路上Flood，否則，正常處理。本發明可以消除冗餘Flood的LSA，利用本發明可以有效減少報文的Flood，同時減少報文的接收處理，降低了帶寬的佔用。接口數量越多，效果越好。隨著接口數量的增加，最大可減少50％的總報文Flood量。
權利要求
1.一種避免冗餘Flood的方法，適用於開放最短優先路徑OSPF多鏈路情況，其特徵在於，該方法包括A.路由器的一個接口收到一個鏈路狀態廣播LSA，查詢所述LSA的發送方，記錄所述發送方的標識Router-id；B.遍歷所述路由器所有的接口下的所有的鄰居，每一次遍歷過程中，如果當前的鄰居滿足特定條件，則不向該鄰居Flood LSA。
2.根據權利要求1所述的一種避免冗餘Flood的方法，其特徵在於，步驟A中所述的LSA，是所述路由器接口收到的比自己資料庫中更新的、非所述路由器接口生成的鏈路狀態廣播LSA。
3.根據權利要求1所述的一種避免冗餘Flood的方法，其特徵在於，步驟A中所述的發送方的標識Router-id，置於所述LSA的域中；或者，通過函數的參數來傳遞。
4.根據權利要求1所述的一種避免冗餘Flood的方法，其特徵在於，所述步驟B中遍歷所有的接口下的所有的鄰居之前，確定每一個接口、每一個鄰居存在。
5.根據權利要求1、2、3或4所述的一種避免冗餘Flood的方法，其特徵在於，所述步驟B中鄰居滿足的條件包括當前的鄰居的標識Router-id和所述記錄的標識Router-id相同，並且不需要Flood隱式ACK。
6.根據權利要求5所述的一種避免冗餘Flood的方法，其特徵在於，所述步驟B中判斷不需要Flood隱式ACK的情況包括所述路由器不是指定路由器DR，或者發送所述LSA的鄰居不是非指定路由器DRother。
7.根據權利要求1或6所述的一種避免冗餘Flood的方法，其特徵在於，所述步驟B還包括每一次遍歷過程中，如果當前的鄰居不滿足所述的條件，向該鄰居Flood LSA。
8.根據權利要求7所述的一種避免冗餘Flood的方法，其特徵在於，有多條並行鏈路時，如果存在一條可靠鏈路，則只在所述可靠鏈路上Flood LSA。
全文摘要
本發明公開了一種避免冗餘Flood的方法，根據開放最短路徑優先協議OSPF的Flood原則在Flood一條鏈路狀態公告(LSA)的時候，如果不確定鄰居是否已經有該條LSA那就需要把它Flood給對方，如果已經確定該鄰居已經有該LSA，則不必再向其Flood該LSA，關鍵是如何判斷在這個鄰居上已經存在該LSA，本發明的判斷方法是如果路由器A從路由器B收到一條LSA，那麼B一定有該條LSA。通過本發明，可以消除冗餘Flood的LSA，減少報文的接收、處理工作量，避免帶寬的無效佔用。
文檔編號H04L29/06GK1859375SQ20051010141
公開日2006年11月8日 申請日期2005年11月12日 優先權日2005年11月12日
發明者楊鋒 申請人:華為技術有限公司