Subject: OSPF LSID with vary length masks

From: Zhao-Yang Dong <[email-masked]>
Date: Thu, 14 Apr 2005 19:31:47 -0400

In an OSPF link state database, each LSA is supposed to have a unique Link
State ID (LSID). Sometimes this is not true, especially in multiple vendor
devices environment. 

When originating summary and/or AS-external LSAs, how to assign unique LSID
for a network number who has multiple (different length of) masks is
described in RFC 2328 appendix E. However, I did not see any discussion in
RFC 2328 nor this archive how to handle/process summary and/or AS-external
LSAs received from other routers with the same LSID but different length of
masks. 

According RFC 2328, a LSA is identified by LS type, LSID and advertising
router. To determine which LSA of two LSA instances is newer, LS sequence
number, checksum and age are compared. Network mask does not seem play any
role while processing the received LSAs. 

My question is, for example, if I received a LSA with LSID=A.B.C.D and 24
bits mask and installed in my database, and later I received the same LSA
(i.e. same LS type, LSID and advertising router) but with 28 bits mask. If
the second LSA has the larger sequence number, should I replace my database
copy with the second LSA?

Thanks,

Zhaoyang

---

From: Dave Katz <[email-masked]>
Date: Thu, 14 Apr 2005 22:26:19 -0700

On Apr 14, 2005, at 4:31 PM, Zhao-Yang Dong wrote:

> In an OSPF link state database, each LSA is supposed to have a unique 
> Link State ID (LSID). Sometimes this is not true, especially in 
> multiple vendor devices environment.

The LSA ID is qualified by the originating system, so it is entirely 
reasonable to have multiple LSAs with the same LSA ID but different 
router IDs.

What is *not* allowed is to have multiple LSAs with the same LSA ID 
originated by the same system.  This cannot happen according to the 
rules, and they will not be propagated if they were, also according to 
the rules.  Whether there are multiple vendors has no impact on this.

> When originating summary and/or AS-external LSAs, how to assign unique 
> LSID for a network number who has multiple (different length of) masks 
> is described in RFC 2328 appendix E. However, I did not see any 
> discussion in RFC 2328 nor this archive how to handle/process summary 
> and/or AS-external LSAs received from other routers with the same LSID 
> but different length of masks.

A router can do anything it wants to guarantee LSA ID uniqueness on the 
LSAs it generates; appendix E is one way (though there are ways that 
will go further before they fail than the one outlined there.)  Note 
that RFC2328 also refers to appendix E for Summary LSAs as well;  see 
appendix A.4.5.

It is not the job of a receiving router to deal with this case, because 
it cannot happen (according to the rules) and it is indistinguishable 
from the case where somebody changes the netmask on a redistributed 
static route.

>
>   
>
> According RFC 2328, a LSA is identified by LS type, LSID and 
> advertising router. To determine which LSA of two LSA instances is 
> newer, LS sequence number, checksum and age are compared. Network mask 
> does not seem play any role while processing the received LSAs.

It does not, nor should it.  An LSA is identified by originating router 
ID, LSA type, and LSA ID.  Period.  Any router that attempts to 
generate two different LSAs with the same ID is broken.

>
>   
>
> My question is, for example, if I received a LSA with LSID=A.B.C.D and 
> 24 bits mask and installed in my database, and later I received the 
> same LSA (i.e. same LS type, LSID and advertising router) but with 28 
> bits mask. If the second LSA has the larger sequence number, should I 
> replace my database copy with the second LSA?

That's what the rules say.  This is why a broken system generating 
multiple LSAs with the same ID will not get far;  only one of them 
(with the higher sequence number) will get acknowledged, and the other 
will be retransmitted ad infinitum.

The problem is that the Founding Fathers that spec'ed OSPF screwed up 
and overloaded the LSA ID with routing information because they were 
afraid of spending another four bytes per LSA.  One could blame it on 
classful networking, but in a purely classful environment you wouldn't 
even need masks.  Basically it was yet another mistaken optimization.

It's impossible to guarantee uniqueness;  if you try hard enough you 
can generate a situation that no algorithm can work around (because the 
LSA ID space is by definition sparse due to the masking requirement, 
but the space of possible external routes is dense.)  As a practical 
matter, however, it's very unlikely that there will be an LSA ID 
collision if a reasonably good algorithm is chosen.

BTW, the cisco IOS implementation appears to attempt to detect this 
case, though it's not clear why.  I assume it complains if it sees the 
same LSA ID and a different netmask, but that's a perfectly legal 
situation.  If anybody from cisco can explain this, I'm quite curious.

--Dave

---

From: Tom Petch <[email-masked]>
Date: Fri, 15 Apr 2005 11:22:57 +0200

Agree with everything Dave saids but would stress that OSPF by design does not
cater for overlapping prefix (from the same router) so a router MUST NOT
originate two LSA, one a /24 and the other a /28 for the same prefix.  Other
routing protocols are different which is an issue when redistributing from them
into OSPF.

Tom Petch

----- Original Message -----
From: "Dave Katz" <[email-masked]>
To: <[email-masked]>
Sent: Friday, April 15, 2005 7:26 AM

--Dave

---

From: Acee Lindem <[email-masked]>
Date: Fri, 15 Apr 2005 08:20:03 -0400

Hi Zhao-Yang,
Added subject. See inline.

>copy with the second LSA?
Yes. As you noted above the LSA payload is not used to determine which 
LSA is newer  (other
than it's contribution to the LSA checksum). Of course, you will need to 
run an incremental (or partial
depending on your terminology) for both the new LSA and the prefix 
corresponding to the old
LSA with the different mask.

Hope this helps,
Acee

---

From: Acee Lindem <[email-masked]>
Date: Fri, 15 Apr 2005 09:03:25 -0400

Hi Dave,

Thanks for the detailed response. I've added my hastily typed
and grammatically incorrect subject for the archives.

See one response inline.

Dave Katz wrote:

>> When originating summary and/or AS-external LSAs, how to assign 
>> unique LSID for a network number who has multiple (different length 
>> of) masks is described in RFC 2328 appendix E. However, I did not see 
>> any discussion in RFC 2328 nor this archive how to handle/process 
>> summary and/or AS-external LSAs received from other routers with the 
>> same LSID but different length of masks.
>
>
> A router can do anything it wants to guarantee LSA ID uniqueness on 
> the LSAs it generates; appendix E is one way (though there are ways 
> that will go further before they fail than the one outlined there.)  
> Note that RFC2328 also refers to appendix E for Summary LSAs as well;  
> see appendix A.4.5.
>
> It is not the job of a receiving router to deal with this case, 
> because it cannot happen (according to the rules) and it is 
> indistinguishable from the case where somebody changes the netmask on 
> a redistributed static route.
>
>>
>>   
>>
>> newer, LS sequence number, checksum and age are compared. Network 
>> mask does not seem play any role while processing the received LSAs.
>
>
> It does not, nor should it.  An LSA is identified by originating 
> router ID, LSA type, and LSA ID.  Period.  Any router that attempts to 
>> My question is, for example, if I received a LSA with LSID=A.B.C.D 
>> and 24 bits mask and installed in my database, and later I received 
>> the same LSA (i.e. same LS type, LSID and advertising router) but 
>> with 28 bits mask. If the second LSA has the larger sequence number, 
>> should I replace my database copy with the second LSA?
>
>
> can generate a situation that no algorithm can work around (because 
> the LSA ID space is by definition sparse due to the masking 
> requirement, but the space of possible external routes is dense.)  As 
> a practical matter, however, it's very unlikely that there will be an 
> LSA ID collision if a reasonably good algorithm is chosen.
>
>

A warning message will only be generated when the originating router 
encounters
an LSA advertisement conflict that cannot be resolved using the 
algorithm in
RFC 2328 Appendix E. This is to let the network administrator know that the
conflict exists and not all prefixes are advertised.

Thanks,
Acee

---

From: Acee Lindem <[email-masked]>
Date: Fri, 15 Apr 2005 09:33:14 -0400

>routing protocols are different which is an issue when redistributing from them
Hi Tom,
Actually the algorithm in RFC 2328 appendix E handles the situation 
aboved quite nicely.
For example,  if you want to advertise 10.1.1.0/24 and 10.1.1.0/28 the LSIDs
10.1.1.0 and 10.1.1.15 will be used. The cases it doesn't handle are the 
more pathological
ones. For example, say you now also want to advertise 10.1.1.8/28 and 
10.1.1.8/29.
You'll get a conflict since you'll try and use the LSID 10.1.1.15 for 
both 10.1.1.0/28
and 10.1.1.8/28. A more common conflict would be if you happen to also 
want to
advertise the host route 10.1.1.15.

Thanks,
Acee

---

From: Acee Lindem <[email-masked]>
Date: Fri, 15 Apr 2005 11:42:03 -0400

Corrected prefix lengths in example.

Hi Tom,
Actually the algorithm in RFC 2328 appendix E handles the situation
above quite nicely. For example, if you want to advertise 10.1.1.0/24
and 10.1.1.0/28 the LSIDs 10.1.1.0 and 10.1.1.15 will be used. The cases
it doesn't handle are the more pathological ones. For example, say
you now also want to advertise 10.1.1.8/29 and 10.1.1.8/30. You'll get
a conflict since you'll try and use the LSID 10.1.1.15 for both
10.1.1.0/28 and 10.1.1.8/30. A more common conflict would be if you
happen to also want to advertise the host route 10.1.1.15/32.

Thanks,
Acee

---

From: Acee Lindem <[email-masked]>
Date: Fri, 15 Apr 2005 12:35:16 -0400

Sigh - I guess I choose a bad example. The conflict with the host
route 10.1.1.15 would be the most common conflict. I've seen
this in environments with subscriber routes.

---

From: Dave Katz <[email-masked]>
Date: Fri, 15 Apr 2005 12:19:05 -0700

> routing protocols are different which is an issue when redistributing 

Do not confuse the encoding of the LSA IDs with the concept of 
advertising overlapping routes.  It is perfectly reasonable to 
advertise overlapping routes, if not necessarily too useful.  In fact, 
all the gorp in appendix E is to specifically support overlapping 
routes (because of the screwed up LSA ID encoding.)

--Dave