最近翻了一下網(wǎng)上關(guān)于DR以及BDR選舉的文章,發(fā)現(xiàn)很多文章的描述都存在問題,而且很多東西都沒有描述清楚,所以,我自己打算寫一篇文章,將事情徹底講清楚.
參考
最權(quán)威的參考資料還是RFC文檔,網(wǎng)上大部分文章都不靠譜,甚至TCP/IP路由卷一,都沒有講清楚.有興趣的同學(xué)可以翻一下RFC2328,我這里干脆引用一下得了.
This section describes the algorithm used for calculating a network’s Designated Router and Backup Designated Router. This algorithm is invoked by the Interface state machine. The initial time a router runs the election algorithm for a network,
the network’s Designated Router and Backup Designated Router are initialized to 0.0.0.0. This indicates the lack of both a Designated Router and a Backup Designated Router.
The Designated Router election algorithm proceeds as follows:
Call the router doing the calculation Router X. The list of neighbors attached to the network and having established bidirectional communication with Router X is examined. This list is precisely the collection of Router X’s neighbors (on this network) whose state is greater than or equal to 2-Way . Router X itself is also considered to be on the list. Discard all routers from the list that are ineligible to
become Designated Router. (Routers having Router Priority of 0 are ineligible to become Designated Router.) The following steps are then executed, considering only those routers that remain on the list:
(1) Note the current values for the network’s Designated Router
and Backup Designated Router. This is used later for comparison purposes.
(2) Calculate the new Backup Designated Router for the network as follows. Only those routers on the list that have not declared themselves to be Designated Router are eligible to become Backup Designated Router. If one or more of these routers have declared themselves Backup Designated Router (i.e., they are currently listing themselves as Backup Designated Router, but not as Designated Router, in their
Hello Packets) the one having highest Router Priority is declared to be Backup Designated Router. In case of a tie, the one having the highest Router ID is chosen. If no routers have declared themselves Backup Designated Router, Moy Standards Track [Page 75]RFC 2328 OSPF Version 2 April 1998 choose the router having highest Router Priority, (again excluding those routers who have declared themselves Designated Router), and again use the Router ID to break ties.
(3) Calculate the new Designated Router for the network as follows. If one or more of the routers have declared themselves Designated Router (i.e., they are currently
listing themselves as Designated Router in their Hello Packets) the one having highest Router Priority is declared to be Designated Router. In case of a tie, the one having the highest Router ID is chosen. If no routers have declared themselves Designated Router, assign the Designated Router to be the same as the newly elected Backup Designated Router.
(4) If Router X is now newly the Designated Router or newly the Backup Designated Router, or is now no longer the Designated Router or no longer the Backup Designated Router, repeat steps 2 and 3, and then proceed to step 5. For example, if Router X is now the Designated Router, when step 2 is repeated X will no longer be eligible for Backup Designated Router election. Among other things, this will ensure that no router will declare itself both Backup Designated Router
and Designated Router.
(5) As a result of these calculations, the router itself may now be Designated Router or Backup Designated Router. See Sections 7.3 and 7.4 for the additional duties this would entail. The router’s interface state should be set accordingly. If the router itself is now Designated Router, the new interface state is DR. If the router itself is now Backup Designated Router, the new interface state is Backup.
Otherwise, the new interface state is DR Other.
(6) If the attached network is an NBMA network, and the router itself has just become either Designated Router or Backup Designated Router, it must start sending Hello Packets to those neighbors that are not eligible to become Designated Router (see Section 9.5.1). This is done by invoking the neighbor event Start for each neighbor having a Router Priority of 0.
(7) If the above calculations have caused the identity of either the Designated Router or Backup Designated Router to change,the set of adjacencies associated with this interface will need to be modified. Some adjacencies may need to be
formed, and others may need to be broken. To accomplish this, invoke the event AdjOK? on all neighbors whose state is at least 2-Way. This will cause their eligibility for adjacency to be reexamined (see Sections 10.3 and 10.4).
The reason behind the election algorithm’s complexity is the desire for an orderly transition from Backup Designated Router to Designated Router, when the current Designated Router fails.
This orderly transition is ensured through the introduction of hysteresis: no new Backup Designated Router can be chosen until the old Backup accepts its new Designated Router responsibilities.
The above procedure may elect the same router to be both Designated Router and Backup Designated Router, although that router will never be the calculating router (Router X) itself.
The elected Designated Router may not be the router having the highest Router Priority, nor will the Backup Designated Router necessarily have the second highest Router Priority. If Router X is not itself eligible to become Designated Router, it is
possible that neither a Backup Designated Router nor a Designated Router will be selected in the above procedure. Note also that if Router X is the only attached router that is eligible to become Designated Router, it will select itself as Designated Router and there will be no Backup Designated Router for the network.
算法
以下算法基本是上面內(nèi)容的翻譯.
一臺(tái)ospf接口起來的時(shí)候,它默認(rèn)的dr以及bdr都是0.0.0.0,這意味著,這個(gè)時(shí)候,此接口認(rèn)為還網(wǎng)絡(luò)中不存在DR以及BDR.
接下來開始DR的選舉算法,假定我們有一臺(tái)路由器X,它正在運(yùn)行DR選舉算法,它首先會(huì)開始檢查同一網(wǎng)段上,和X建立了雙向連接關(guān)系的鄰居(鄰居狀態(tài)大于等于two-way),當(dāng)然,X自己也在這些鄰居之中,去掉那些優(yōu)先級(jí)為0的鄰居(優(yōu)先級(jí)為0,表示其并不想?yún)⑴c選舉),去掉那些Router ID為0的鄰居,將其余的鄰居加入候選列表.
(1) 先將當(dāng)前路由器認(rèn)為的DR以及BDR的值記錄下來,這個(gè)將由于后面的比較;
(2) 首先選舉新的BDR,首先選擇BDR的候選者,那些宣稱自己為DR的鄰居不能作為BDR,如果有1個(gè)或者多個(gè)候選候選鄰居宣稱自己為BDR(沒有宣稱自己為DR),那么它們之中,優(yōu)先級(jí)最高的鄰居作為BDR,如果優(yōu)先級(jí)一致,Router ID大的將成為BDR.如果沒有鄰居宣稱自己為BDR, 那就挑選一個(gè)擁有最高優(yōu)先級(jí)的作為BDR,優(yōu)先級(jí)一致的話,router-id大的成為BDR(同樣的,要排除那些宣稱自己為DR的鄰居);
(3) 接下來選舉DR,流程如下,如果有一個(gè)或多個(gè)候選鄰居宣稱自己為DR(也就是說,Hello包中,它們將自己的Router ID填入了DR字段),擁有最高優(yōu)先級(jí)的鄰居成為DR,如果優(yōu)先級(jí)一致,則比較Router ID,Router ID大的鄰居成為DR,如果沒有鄰居宣稱自己為DR,那么前面選舉的BDR成為DR;
(4) 使用(1)中保存的值,如果X成為了新的DR/BDR(之前不是),或者現(xiàn)在已經(jīng)不是DR/BDR(原來是),重復(fù)算法(2),(3)步,然后執(zhí)行第(5)步.為什么要這么做呢?很簡單,經(jīng)歷(2),(3)之后,X現(xiàn)在可能即是DR也是BDR,重新執(zhí)行之后,我們可以保證,X只有一個(gè)角色;
(5) ... (接下來就不是選舉算法部分了,省略)
問題
為什么DR以及BDR一般只要不掛,就不會(huì)改變?
假定一個(gè)局域網(wǎng),已經(jīng)存在了一個(gè)DR以及一個(gè)BDR,現(xiàn)在另外一臺(tái)優(yōu)先級(jí)更高的路由器R3加入:
R1[DR]-------R2[BDR]
|
R3
需要說明一下,真實(shí)環(huán)境收包發(fā)包時(shí)序可能并非如此,這里僅僅只是為了演示而已.
- 首先,R3剛起來,認(rèn)為DR以及BDR為0,開始發(fā)送Hello包,DR為0,BDR為0;
- 接下來R2接收到了R1的Hello包,里面DR為R1, BDR為R2, 以及受到了R2發(fā)來的Hello包,里面DR為R1, BDR為R2;
- R2開始運(yùn)行選舉算法,先選舉BDR, BDR只有R2一個(gè)候選者,R2成為BDR;
- 開始選舉DR,DR只有R1這一個(gè)候選者,因此,R1為DR.
繼續(xù)上面的拓?fù)?如果R1掛掉了呢?
R1[DR]-X------R2[BDR]
|
R3
等待一段時(shí)間,R2和R3沒有收到R1的Hello報(bào)文,就會(huì)將R1從鄰居列表中移除.然后重新開始選舉.假定這個(gè)時(shí)候R3將R1移除,但是還沒有收到R2的Hello報(bào)文.
- 首先選舉BDR,因?yàn)镽2宣稱自己為BDR,選舉R2為BDR;
- 開始選舉DR,因?yàn)闆]有鄰居宣稱自己為DR,那么R2成為DR;
- 因?yàn)镽3一直都是DROther,因此就不執(zhí)行算法步驟(2)和(3);
R2同樣也會(huì)執(zhí)行選舉:
- 首先選舉BDR,因?yàn)镽2宣稱自己為BDR,選舉R2為BDR;
- 開始選舉DR,因?yàn)闆]有鄰居宣稱自己為DR,那么R2成為DR;
- R2成為了DR,重新執(zhí)行算法步驟(2)和(3);
- 首先,因?yàn)镽2成為了DR,它不會(huì)再成為BDR,因此BDR為R3;
- R2經(jīng)過DR選舉仍然是DR.
接著R2和R3會(huì)互相洪泛Hello報(bào)文,R3收到R2的Hello報(bào)文后,會(huì)再次進(jìn)行選舉:
- 首先選舉BDR,因?yàn)镽2為DR,因此R3成為了BDR;
- R2仍然是DR;
- 因?yàn)镽3新成為了BDR,重新執(zhí)行算法步驟(2)和(3);
- 選舉BDR,R3為BDR;
- 選舉DR,R2為DR;
最終R2和R3會(huì)達(dá)成一致.
什么時(shí)候會(huì)進(jìn)行選舉過程?
1.新增two-way及以上的鄰居;
2.two-way及以上的鄰居減少;
3.two-way及以上的鄰居宣稱自己為DR/BDR (原來不是);
4.two-way及以上的鄰居不再宣稱自己為DR/BDR (原來是);
5.two-way及以上的鄰居的優(yōu)先級(jí)發(fā)生變化.
