BR and BDR

[fbarreras]

Came across this formula in CCNP studies for determining number of adjacencies required when using BR and BDR in a full mesh environment. The formula is 2 x (n-1) where n = number of nodes. Taking a 4 node situation, the number of adjacencies would be 6, according to the formula. Ok, the DR formed adjancencies with the BDR and routers A and B. Now the BDR forms adjacencies with routers A and B and the DR. My question is, why does the BDR have to form another adjacency with the DR if it already has one formed? Does it really require two adjancencies between the DR and BDR? That seems to be the only way the formula makes sense to me. What am I missing here?

[donewald]

I believe in that 2N-1 formula you are missing the one between A and B. If you draw it out with all routers having an adajcency with one another (including A and B (DROTHER)) you come up with 6.

Hope this helps,

Don

[fbarreras]

Thanks for your response. I thought the reason that they have DR and BDR is so that the other devices would not thave to have adjancencies with each other, just with the designated routers, to cut down on the traffic. So therefore there would not be an adjancency required between routers A and B. Lets try it this way. If you had five routers with full mesh the prescribed formula is n x(n-1) / 2 and the answer would be 10. If you had five routers using DR and BDR and the prescribed formula 2 x (N-1) the answers is 8. If you draw it out, you will see that the only way this will work is if there is two adjacencies between the DR and the BDR. HELP!!

[fbarreras]

Any CCNP'S out there that know the theory behind this that can help? Thanks in advance.

[donewald]

This is how the OSPF adjacencies work, as stated in my 1st reply. All routers do form adjacencies although nonDR routers adjacencies are not full but are there. Hope this helps you understand.

All routers connected via a serial connection should become fully adjacent.

On a shared broadcast media, i.e.: ethernet, a router will

become fully adjacent with both the DR and BDR. Of course if the router

is a DR or BDR then it will become adjacent with all routers

on that ethernet. Two routers that are not DR or BDR will only reach

the two way adjacency state with each other. In a point-to-multipoint

network, a router will form a full adjacency with all routers that it

is directly connected to.

Regards,

Don

[fbarreras]

Thanks for your response. I believe I have the adjacencies down pat. The problem I am having is directly figuring out the formula 2x(n-1) when used in a DR -BDR environment in a broadcast multiaccess network. If you could explain that it would be very helpful. Thanks again.

[mck]

I think you are right in the first place.

I do not see a reason for 2 adjacencies between the DR and BDR.

The adjacency relationship is symmetrical.

If X is adjacent to Y, then Y is adjacent to X and vise versa.

No double-counting should be performed when counting the number of

adjacencies.

In RFC 2328, it is stated that the collection of adjacencies in a network

can be pictured as an undirected graph.(Notice the word "undirected".)

The vertices consist of routers with edges joining them if they are

adjacent.

Notice also, that 2 routers can be neighbors,

but that does not necessarily mean that they will become adjacent.

Let's suppose that we have n routers on a broadcast multi-access segment,

configured appropriately for OSPF.

They will all become neighbors.

Each router will see n-1 neighbors (all the others except itself).

A DR and a BDR will be elected.

n-1 routers (BDR included) will become adjacent with the DR,

and will reach FULL neighbor state with the DR.

n-1 routers (DR included) will become adjacent with the BDR,

and will reach FULL neighbor state with the BDR.

Two routers that are neither DR nor BDR, will not become adjacent.

This can be easily confirmed with the command

"show ip ospf interface "

in any live broadcast segment with OSPF.

The concept of adjacency is different from the neighbor concept.

Instead of having each router trying to synchronize databases with all others,

we have each router trying to synchronize only with the DR and BDR.

One way to count the adjacencies is to look only

from the DR and BDR point of view.

The DR sees n-1 adjacencies (one of them is with BDR).

The BDR sees n-1 adjacencies (one of them is with the DR, already counted above).

The number of adjacencies is (n-1) + (n-1) -1 = 2n-3

All other routers see only 2 adjacencies (with DR and BDR),

but these are already included in the above sum.

Another way is to exclude DR and BDR in the beginning

(remembering to add the 1 adjacency between them)

and look from the others point of view.

Then we have : 2 (n-2) + 1 = 2n-3, because

each of the n-2 routers has 2 adjacencies.

If no DR/BDR existed and each router became adjacent with all the rest,

then the number of adjacencies would be [n(n-1)]/2.

Each of the n nodes would form (n-1) adjacencies and we divide by 2

to compensate for the double-counting.

In my opinion, what really matters in all those calculations

is not the exact result, as long as the order of complexity is maintained.

With no DR/BDR, the number of adjacencies grows with the square of n.

With DR/BDR, the number of adjacencies grows linearly with n.

I hope this helps.

[fbarreras]

Thanks for taking the time to response. So the formula 2 (n-1) is bogus.

[mck]

I have come across in various books the following formulas :

1) N(N-1) for the no DR/BDR scheme,

no mentioning about the DR/BDR scheme.

2) n(n-1) for the no DR/BDR scheme

and (n-2)*2 + 1 = 2n-3 for the DR/BDR scheme

3) [n(n-1)]/2 for the no DR/BDR scheme

and 2n-1 for the DR/BDR scheme.

This paricular one is from John T. Moy (OSPF RFC author).

When he introduces the DR concept (no BDR yet), he says

that the result is n adjacencies.

This sounds strange to me, because it can only hold if the

DR establishes an adjacency with itself.

With DR and BDR he says we have n + (n-1) =2n-1.

He does not double-count the DR-BDR adjacency,

but he bases his thought on the assumption that there are

n adjacencies in the DR-only case.

I have to say however, that when he depicts the adjacencies

in a graph ,for n=5 the result is 7 and not 9.

You asked about the 2(n-1) formula.

I guess we have a 4th one.

And the one I wrote about is the 5th.

Notice that the one I wrote about holds for n>=2 ,

when we have at least a DR and a BDR.

In Moy's formula we have 3 adjacencies for n=2 !

I am afraid you will have to choose a formula ,

since there is obvious confusion.

If the question pops up in an exam you know what to do :

" Choose the best one " ;-)))

If all above appear as potential answers,

I wouldn't like to be in your place...;-)))

[fbarreras]

Thanks for all the help. The one that I would go for is (n-2)x2+1 = 2n-3. That seems to make the most sense to me.