[prev in list] [next in list] [prev in thread] [next in thread] 

List:       ms-ospf
Subject:    Re: determining the newer LSA
From:       Alex Zinin <zinin () AMT ! RU>
Date:       1999-12-02 10:50:06
[Download RAW message or body]


Wenhui:

I'll group the two of your replies into one message:

At 22:30 01.12.99 +0800, you wrote:
>Alex,John and Radia
>Thanks for your explanation!
>
>First, I know the probability to meet the same SeqNum
>is small.
[snip]

The probability of this event if much higher than
one could think, because it happens when:

1. routers even don't restart and an LSA is being
flooded throughout the domain. In this case the received
LSA is just the same LSA as in the LSDB and the router
stops flooding it further. The router actually received
it because of the redundant nature of the flooding
mechanism.

2. routers restart within a short period of time after
initial start (one can see it pretty often when debugging
an OSPF implementation :)

>Radia:
>I know what's your meaning. In your opinion,in fact,
>the "simple meathod" is complex because it needs to
>match the long string.
>First,I just think that when two LSAs have the same LS SeqNum,
>LS checksum and LS age field, maybe these two LSAs are
>not identical completely,so the probability that router A chooses
>one and router B chooses other one exists.

Yes there is a chance if, for example, A's clock is faster than B's one,
or when the age of the old LSA is somewhere about MaxAgeDiff.

In any case, it must be understood that though probability
of being wrong when determining whether LSAs are euqal
or not based on the age is 0.5, the overall probability of
*real problem* is very low, because it's tied to many factors,
including the probability of having the same checksum
value for different data patterns.

>Second,when two LSAs
>have the same LS SeqNum and LS checksum,we need to turn to
>the age field, at this situation, the "simple meathod" is simple.
>Now, I know I have made a big mistake: the probability for two
>LSAs have the same LS SeqNum and LS checksum is small.In fact,
>it is close to impossible.

Yes, it is very small when the bodies are different.

>
>When we choose the LSA which has greater age value,
>The probability we choose the wrong one is 50 percent,right?
>I think so.

We should talk about the probability of *a mistake* here,
because we first decide whether LSAs are equal and
if they are not we see which one is newer. We can make
a mistake while doing the first step, but once LSAs
are reported to be different, I can hardly imagine how
a wrong LSA can be chosen in reality.

Regards,

Alex.

>
>
>
>
>
>
>>Wenhui:
>>
>>a small addition to already said by John and Radia.
>>
>>1. The age field does reflect the true age of an LSA,
>>but not only it. It's generally inaccurate because
>>flooding uses it in a manner similar to hop count
>>in DV RPs to prevent endless flooding (which is
>>the main reason) and because of other reasons
>>mentioned before.
>>
>>2. Use of MaxAgeDiff during Age comparision is an
>>heuristic attempt to take the above described
>>inaccuracy into consideration.
>>
>>3. We cannot check the Age field first because
>>it changes while an LSA is being flooded, so
>>there's a chance that some routers choose one
>>LSA as newer, while other ones choose the other,
>>which is not what we want, because, as John
>>highlighted, we need all routers to agree on which
>>LSA is newer. So we use the checksum, since
>>(like Radia was saying) it is stable for a given LSA.
>>
>>Best,
>>Alex.
>>
>>At 23:26 30.11.99 +0800, you wrote:
>>>Alex,
>>>First,thanks for your explanation.I think
>>>I have known what is your meaning.
>>>
>>>In your opinion, though we choose the LSA which has greater
>>>checksum value, maybe we choose the wrong one. The probability
>>>is 50 percent. Following is come from RFC 2328 (page 146)
>>>"Else, if only one of the instances has its LS age field
>>>set to MaxAge, the instance of age MaxAge is considered
>>>to be more recent.Else, if the LS age fields of the two
>>>instances differ by more than MaxAgeDiff, the instance having
>>>the smaller (younger) LS age is considered to be more recent."
>>>Now, the Age field doesn't reflect the true age
>>>of an LSA(two LSAs have the same SeqNum and checksum),
>>>so the words included in quotation marks are meanless.
>>>If we choose the LSA which has greater age fields,Also
>>>maybe we choose the wrong one, the probability is 50 percent.
>>>If the probability we choose the correct one is large than
>>>50 percent,we should first dertermine the age field,then
>>>the checksum field.
>>>
>>>
>>>Now,suppose we install the wrong LSA,the routing
>>>table is recalculated,some data packets may routed incorrectly
>>>before the router receive the Next correct LSA.
>>>
>>>
>>>
>>>
>>>>Wenhui:
>>>>
>>>>At 20:38 30.11.99 +0800, you wrote:
>>>>>    Hello,friends:
>>>>>
>>>>>    I have a doubt on determining the newer LSA.
>>>>>    In RFC2328,an LSA is identified by its LS type,
>>>>>    link state ID and advertising number.If two instance
>>>>
>>>>"advertising number" = "advertising router ID";
>>>>
>>>>>    LSAs have the same LS type,link state ID and advertising
>>>>>    number,we think the two LSAs of the same LSA.
>>>>>    For two instances of the same LSA,the LS sequence number
>>>>>    LS age,and LS checksum fields are used to determine which
>>>>>    instance is more recent.Now the question is coming:
>>>>>    why first the LS sequence number,then LS checksum field
>>>>>    considered,and finally,the LS age field?  Is there some
>>>>>    theory behind it?
>>>>
>>>>First, let's not talk about the situations when routers
>>>>restart, i.e., everything is stable.
>>>>
>>>>Whenever a router reoriginates an LSA, it increments
>>>>the SeqNum field, so if we have two instances with different
>>>>SeqNums, the one with larger value is newer.
>>>>
>>>>Now, if the routers do not restart, neither the LSA checksum, nor
>>>>the age will actually play any role here, because when we have
>>>>two instances of an LSA with the same SeqNum, their checksums
>>>>will be the same and the age field will not differ much (they, of course,
>>>>will, because we increment the age while flooding, but the difference
>>>>is not likely to be greater than MaxAgeDiff). So in the perferct world
>>>>it's enough to have SeqNums.
>>>>
>>>>Now getting closer to the reality. Routers do reload and when they
>>>>reload they originate new LSA instances and during the transition
>>>>periods the old and the new LSAs may have the same SeqNum,
>>>>so we must be really careful when deciding whether LSAs are
>>>>the same and if not which one is newer. We cannot reliably use
>>>>the Age field for this, because it doesn't only reflect the true age
>>>>of an LSA, but also the path it took while being flooded, also
>>>>different implementations age LSAs differently, some may have
>>>>clock instability, etc.
>>>>So, we first decide whether LSAs are the same or not by comparing
>>>>the checksums. If the checksums are not the same (but they are
>>>>correct), then the LSA bodies are different and we must pick up
>>>>one to call newer. It doesn't really matter which one is chosen
>>>>(the RFC specifies---take the one with greater checksum value),
>>>>because if we're wrong (and we can be wrong no matter how
>>>>we choose) the originating router will insist on its view by originating
>>>>a new instance of the LSA with greater SeqNum. If checksums
>>>>are equal we still cannot be sure bodies are the same, since
>>>>we can have two equal CRC values for two different data patterns
>>>>(though probability is really low), so we check the Age field.
>>>>
>>>>I'd like to put it again---if for whatever reason a wrong LSA is chosen
>>>>as the newer one, the originating router will increment the SeqNum
>>>>and will flood the new instance of the LSA, even if it contains
>>>>the same info.
>>>>
>>>>Hope this helps
>>>>------------------------------------------------------------------
>>>>Alex D. Zinin, Consultant
>>>>CCSI #98966
>>>>CCIE #4015
>>>
>>>
>>------------------------------------------------------------------
>>Alex D. Zinin, Consultant
>>CCSI #98966
>>CCIE #4015
>>
>
>
------------------------------------------------------------------
Alex D. Zinin, Consultant
CCSI #98966
CCIE #4015

[prev in list] [next in list] [prev in thread] [next in thread]