Subject: [Lsvr] Comment on LSVR sequence number handling

From: Eric Rosen <[email-masked]>
Date: Mon, 3 Dec 2018 16:02:59 +0000

I have a few comments on the sequence number handling.

Consider the following topology:

A--B--C--D
|        |
|--...---Z (The ellipsis represents a long path.)

Suppose A originates its link state update with sequence number k, and 
thisupdate is received and installed by all the other routers.

At some time, A originates a new update with sequence number k+1.  A 
sendsthis to B, who installs it, and B sends it to C, who installs it.  
UpdateA(k+1) is also making its way to Z, via the longer path, but 
hasn't reachedit yet.  D still has the old update A(k) (from Z), and has 
forwarded it onto C. Of course, C prefers A(k+1) that it received from B 
to A(k) that itreceived from D.  So C will forward A(k+1) to D.

Now suppose the BGP session between B and C fails.

Won't this cause C to replace A(k+1) (received from B) with A(k) 
(receivedfrom D)?  That is, won't it cause C to revert from A's most 
recent update toa less recent update from A?  And if C has already 
forwarded A(k+1) to D,won't C now send A(k) on its session to D, thereby 
implicitly  withdrawing the more recent A(k+1)?

This doesn't seem good.

Eventually there will be convergence to A(k+1) as it makes its way along 
thepath via Z to D.  In the meantime, we have an unfortunate period of 
churnand instability as C and D (and possibly other nodes) change from 
A(k+1) tothe earlier A(k) and then eventually back again.

It would be better if, once the C's LSDB has update A(k+1), C does 
notreplace it with a less recent update from A, no matter what BGP 
says.A(k+1) can be removed if and when BGP either has a more recent 
update fromA or when it no longer has any updates from A at all.  Of 
course, this wouldrequire that there be a way for a node that comes up 
to purge old updatesand reinitialize its sequence number space.  IGPs 
generally have sequencenumber purge, timeout, reinitialization, and 
resynchronization mechanisms,but the LSVR proposal seems to lack them.

There is also some lack of clarity about sequence number 
wraparound.Section 4.4 says that the sequence number is "strictly 
increasing", butSection 5.1 talks about "the unlikely possibility that a 
sequence numberwraps".  Perhaps what is meant is that the sequence 
number is allowed towrap, but if that happens, the less recent update 
will be preferred to themore recent.  That seems a bit strange, even if 
the less recent update will,eventually, get withdrawn.

Also from Section 4.4: "If the lower-order 32-bit value wraps, 
thehigher-order 32-bit value should be incremented and saved in 
non-volatilestorage." You might mention that saving the value in 
non-volatile storageis best done before transmitting any update whose 
sequence number containsthe incremented higher-order 32 bits.  Actually, 
the number saved innon-volatile storage should always be one higher than 
the one that isactually being used.  That ensures that a system 
returning after a crashdoesn't reuse sequence numbers that it already used.

Of course, the draft doesn't actually say that the first update after 
bootupshould have a sequence number whose high-order part is from the 
non-volatilestorage, and whose low-order part is zero, though I suspect 
that that is theintention. It also doesn't say that the "factory 
default" for the high-orderpart as stored in non-volatile storage is 
zero.  An implementation thatdecided to use, e.g.,  a random number as 
its first sequence number after bootupwould be compliant to the draft.  
A "clever" implementation like that couldstart with a sequence number 
that is close to the maximum value, in whichcase wraparound and 
subsequent slow convergence would not be at allunlikely.

So even if it is deemed acceptable to prefer older updates to newer 
ones,the sequence number initialization is certainly underspecified.

BTW, isn't it true that the various graceful restart schemes can cause 
oldsequence numbers to remain extant for extended periods of time?  Has 
anyconsideration been given to the issue of whether there are 
circumstances inwhich this may cause slow convergence to result?

Of course, one may expect slow convergence with BGP ;-), but isn't the 
point ofthis proposal to have the BGP-SPF stuff converge at IGP speeds?

---

From: Randy Bush <[email-masked]>
Date: Mon, 03 Dec 2018 13:13:17 -0800

> There is also some lack of clarity about sequence number wraparound.

i tend to use the DNS sequence number arithmetic rfc 1982 to clarify
this one

randy, still thinking about your update serial issue