Re: OSPF LSA type 3 filtering

Brian,
I don't follow. Sorry. Can we do it step by step ?

Brian McGahan @ 04/01/2013 19:45 -0300 dixit:
>The router isn't trying to solve SPF for R1 -> DR though, it's trying to solve SPF
>for R1 -> R2 and R1 -> R3. This is the topology information that LSA
2 maintains.

The router is doing SPF from itself to everywhere.
For so doing, it needs a representation of the graph (of the area).
The "DR" in this graph is an added node to represent the LAN. It has
some info on the LSA 2 and it is referenced by LSAs 1. Right ?

So in my example, you would have 4 nodes and 4 arcs.
What the real issue is, AFAIK, is that OSPF uses directional links, and
all LSA 1 links go *to* the DR, and the LSA 2 links go to the routers.
You need both, because if not there is no path. But given that you know
that this is a transit LAN, that could be inferred.

>The DR/BDR information in LSA 2 isn't used just to minimize flooding
of n*(n-1)/2,
>it's also used to cut down the discovery of candidates in the tree on a
>broadcast/non-broadcast segment from n*(n-1)/2 to 2.

This I don't follow at all. Cut to 2 ? SPF works on edges, so even if is
is represented as one LSA 2, it still is 3 edges...

>In other words if you have 100 routers on a LAN and in one case you run the link as
>network type point-to-multipoint, and in the other case you run it as
network broadcast,
> network broadcast will have a shorter SPF completion time because
there are less operations
>of discovering candidates. The time might be negligible nowadays but
it's still measurable.

100 edges vs 1 + 100 edges. I don't follow it to be a performance gain.
May be a space gain.

>
> Think of it this way, with 100 routers on the LAN running network type broadcast,
>R1 says "I have an adjacency to DR with cost X via LSA 1. DR has adjacency with R2, R3, R4
>... R100 via LSA 2. Therefore I have adjacency with R2, R3, R4... R100 with cost X".

Right, so ?

>
> In network type point-to-multipoint this would read as "I have an adjacency to R2 with
>cost X via LSA 1. I have an adjacency to R3 with cost X via LSA 1. I
have an adjacency to
>R4 with cost X via LSA 1... I have an adjacency to R100 with cost X via LSA 1."

Also right.

>The resulting Shortest Path Trees will be the same, but programmatically the amount of
>operations needed to reach the end result are not the same between the
two. When LSA 1
>points at a transit link (broadcast/non-broadcast) the recursive
lookup to LSA 2
>immediately returns *all* candidates on that portion of the tree,
whereas with
>point-to-multipoint there is a separate LSA 1 that represents each
candidate.
>Therefore with broadcast/non-broadcast you need two lookups (one for
LSA 1 and the
>second recursive lookup to LSA 2) vs. n*(n-1)/2 LSA 1 lookups for
point-to-multipoint.

Immediatelly returns is not very orthodox nor formal complexity
language. Dijstra runs in O(n^2). Trading some edges for an added node
does not sound as an efficiency decision to me.
In any case, this has gone way beyond the initial point, and we digress.

You said LSA 2 was *only* topology, and I keep that that is not the
case. It contains reachability info for the LAN segment.

-Carlos

>
> Of course if your Ethernet links are physically point-to-point then you would want
>to run them as OSPF network point-to-point, which means one LSA 1
lookup instead of
>one LSA 1 lookup and a second recursive LSA 2 lookup.
>
>
>
> Brian McGahan, CCIE #8593 (R&S/SP/Security)
> bmcgahan_at_INE.com
>
> Internetwork Expert, Inc.
> http://www.INE.com
>
>
> -----Original Message-----
> From: Carlos G Mendioroz [mailto:tron_at_huapi.ba.ar]
> Sent: Friday, January 04, 2013 4:03 AM
> To: Marko Milivojevic
> Cc: Brian McGahan; Narbik Kocharians; Cisco certification
> Subject: Re: OSPF LSA type 3 filtering
>
> Marko,
> say we have an area with 3 routers, R1, R2, R3, connected by a LAN.
> Then OSPF would choose one as DR. Say that lan is X.
>
> Would you agree that the database representation would be:
>
> Router links:
> R1: R1 -> DR (transit)
> R2: R2 -> DR (transit)
> R3: R3 -> DR (transit)
>
> Net link:
> DR: X (R1,R2,R3)
>
> You can draw the topology just by looking at the router links.
> What is missing ?
>
> -Carlos
>
>
> Marko Milivojevic @ 04/01/2013 01:11 -0300 dixit:
>> Writing on a phone. Pardon the brevity
>>
>>>
>>> I would argue that you can make the topology of an area only with
>>> type 1 LSAs, and that type 2 LSAs are just for "condensing" the multiaccess link reachability information in one place.
>>
>> Not quite. You would know which routers exist in the area, but not how they are interconnected.
>>
>> To calculate the SPF tree, routers need two pieces of information for all non-leaf links: the link state, and relationship with other routers.
>>
>> OSPF recognizes three link types in Type 1: stub, transit, and point to point.
>>
>> For point to point links, link state is carried in two link state entries. Link itself is described as a "stub link", and the relationship with other router is described as a point-to-point link. These are both in Type 1 LSA.
>>
>> However, for transit link the actual link is described as a link entry in Type 1 LSA, with a reference to a Type 2 LSA (in a form of a DR address). The Type 2 carries the topological information about the relationships between touters in the segment. Both are crucial for the topological calculation.
>>
>> Note - this was all about the topological information and not the reachability.
>>
>> -Marko
>>
>>
>> Blogs and organic groups at http://www.ccie.net
>>
>> ______________________________________________________________________
>> _ Subscription information may be found at:
>> http://www.groupstudy.com/list/CCIELab.html
>>
>>
>>
>>
>>
>>
>>
>
> --
> Carlos G Mendioroz <tron_at_huapi.ba.ar> LW7 EQI Argentina
>

-- 
Carlos G Mendioroz  <tron_at_huapi.ba.ar>  LW7 EQI  Argentina
Blogs and organic groups at http://www.ccie.net