Subject: [manet] RFC7181 (OLSRv2) trouble with ANSN and router restart

From: "Rogge, Henning" <[email-masked]>
Date: Thu, 22 Jul 2021 07:12:22 +0000

Hi,

I think I have potentially identified an issue with OLSRv2 that can lead to a stable desynchronization of the OLSRv2 TC database after a router restart.

The trouble happens because the ANSN (Advertised Neighbor Set Number) can (and should) become stable when the locally reachable neighbors and their metrics don't restart anymore.

The sequence that leads to the issue is:

1) router A restarts
2) router A (randomly?) selects a new Message Sequence Number which is HIGHER (in terms of cyclical comparison) than the last one it used
3) router A selects a new ANSN which is LOWER (or the same) than the last one it used
4) router B sees the new message sequence number/ANSN in TCs from router A
   => router B does not allow the old TC data to timeout (message sequence number is higher!)
   => router B does NOT overwrite the old TC data (ANSN is lower)

this situation will continue as long as the ANSN or router A (which can be stable for an arbitrary time) stays below the ANSN used by the router before its restart

There are two parts to this problem, one of them easy to fix.

a) the ANSN after the restart is lower than the ANSN before. We could just demand that a router does NOT increase the validity time of the TC entry in this case... or that it overwrites the TC entry (the combination of "new message seqno" and "old ANSN" should only happen after a restart)
b) the ANSN after the restart is the SAME as before... this is tricky, I have no idea how to resolve this at the receiver without comparing the TC data with the database, which is not reliable when we deal with incomplete TCs.

What do you think?

Henning Rogge

---

From: Justin Dean <[email-masked]>
Date: Thu, 22 Jul 2021 11:32:26 -0400

Interesting issue.  I think the solution you proposed for new ANSN < old
ANSN and new MSN > old MSN works and wouldn't be hard to provide some
ERRATA on how to deal with this.  I would suggest that when this state
occurs all existing entries with that ANSN be removed as if they were old
and all the entries in the message with the lower ANSN be added and the
ANSN number be reset to the lower value.

As for the lower case it will happen less often but can still happen.  One
way we could solve it is to have a router periodically update it's ANSN
upon restart (even when the state has not changed) and slowly stop updating
it over time.  Any update rate should suffice but an actual specification
need not be created as any progression of the ANSN near the restart time
should suffice.  With more updates providing more/quicker resolution at the
cost of efficiencies throughout the network.  We would still need the first
solution.

A completely different approach would be to use a lollipop numbering system
with restarts occuring say anything greater than 65500 and progressing
regardless of neighbor state for some small number then jumping to 0 and
looping the number system at 65500 instead of 65535.  Any ANSN with a value
on the "stick" would reset the ANSN if the currently stored ANSN was on the
"pop"  otherwise normal operation.  This is a bit more complicated and IMO
unnecessary for fixing this but just wanted to put it out there.

Justin Dean

On Thu, Jul 22, 2021 at 3:12 AM Rogge, Henning <
[email-masked]> wrote:

> Hi,
>
> I think I have potentially identified an issue with OLSRv2 that can lead
> to a stable desynchronization of the OLSRv2 TC database after a router
> restart.
>
> The trouble happens because the ANSN (Advertised Neighbor Set Number) can
> (and should) become stable when the locally reachable neighbors and their
> metrics don't restart anymore.
>
> 2) router A (randomly?) selects a new Message Sequence Number which is
> HIGHER (in terms of cyclical comparison) than the last one it used
> this situation will continue as long as the ANSN or router A (which can be
> stable for an arbitrary time) stays below the ANSN used by the router
> before its restart
>
> a) the ANSN after the restart is lower than the ANSN before. We could just
> demand that a router does NOT increase the validity time of the TC entry in
> this case... or that it overwrites the TC entry (the combination of "new
> message seqno" and "old ANSN" should only happen after a restart)
> b) the ANSN after the restart is the SAME as before... this is tricky, I
> have no idea how to resolve this at the receiver without comparing the TC
> data with the database, which is not reliable when we deal with incomplete
> TCs.
>
> What do you think?
>
> Henning Rogge
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>

---

From: "Rogge, Henning" <[email-masked]>
Date: Fri, 23 Jul 2021 06:11:43 +0000

The problem is easy to solve on the "sender" side, but if we manage I would like to solve it on the receiver side (of TCs).

This way we could prevent an incompatible change to the protocol.

Could the problem be solved if we track (per prefix) when we got the last TC containing it? This way, even when a transmitter only sends "incomplete TCs", we would eventually remove all database entries that have never been repeated despite being part of the (currently unchanging) ANSN.

Henning

________________________________
Von: Justin Dean <[email-masked]>
Gesendet: Donnerstag, 22. Juli 2021 17:32
An: Rogge, Henning
Cc: [email-masked]
Betreff: Re: [manet] RFC7181 (OLSRv2) trouble with ANSN and router restart

Interesting issue.  I think the solution you proposed for new ANSN < old ANSN and new MSN > old MSN works and wouldn't be hard to provide some ERRATA on how to deal with this.  I would suggest that when this state occurs all existing entries with that ANSN be removed as if they were old and all the entries in the message with the lower ANSN be added and the ANSN number be reset to the lower value.

As for the lower case it will happen less often but can still happen.  One way we could solve it is to have a router periodically update it's ANSN upon restart (even when the state has not changed) and slowly stop updating it over time.  Any update rate should suffice but an actual specification need not be created as any progression of the ANSN near the restart time should suffice.  With more updates providing more/quicker resolution at the cost of efficiencies throughout the network.  We would still need the first solution.

A completely different approach would be to use a lollipop numbering system with restarts occuring say anything greater than 65500 and progressing regardless of neighbor state for some small number then jumping to 0 and looping the number system at 65500 instead of 65535.  Any ANSN with a value on the "stick" would reset the ANSN if the currently stored ANSN was on the "pop"  otherwise normal operation.  This is a bit more complicated and IMO unnecessary for fixing this but just wanted to put it out there.

Justin Dean

On Thu, Jul 22, 2021 at 3:12 AM Rogge, Henning <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

1) router A restarts

What do you think?

Henning Rogge
_______________________________________________
manet mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/manet

---

From: Christopher Dearlove <[email-masked]>
Date: Fri, 23 Jul 2021 13:41:33 +0100

Hi to those who remember me, I’m still around, although retired now. (Unless a bit of consultancy pops up.)

Not so interested in DLEP, but keep an eye on OLSRv2 etc.

I’m failing to understand the specific problem here. There are restart issues that we never found the bandwidth to formally address, but they are different to this one.

Comments below.

> On 22 Jul 2021, at 08:12, Rogge, Henning <[email-masked]> wrote:
> 
> Hi,
> 

This is unfortunate, and part of the problem, router A will find it hard to get back into the network. The easiest way is simply to wait out expiry times, but that might not be an issue if those have become long (which is a bandwidth saving approach in a stable network - but nothing unfortunately is free).

But the suggestion here appears to be different.

>   => router B does NOT overwrite the old TC data (ANSN is lower)

Yes, the old data won’t be overwritten. But nothing affects the timeout. It doesn’t happen, but it isn’t extended. 16.3.3.1 point 1, the TC message will be discarded. So Topology Tuples etc. aren’t modified and will in due course timeout. Maybe that’s too slow, but that’s a different issue.

> a) the ANSN after the restart is lower than the ANSN before. We could just demand that a router does NOT increase the validity time of the TC entry in this case... or that it overwrites the TC entr…

(a) already happens, paragraph as quoted. No change needed.

> b) the ANSN after the restart is the SAME as before... this is tricky, I have no idea how to resolve this at the receiver without comparing the TC data with the database, which is not reliable when…

This one might be a problem. Unlucky with 2^16 numbers to pick. But not unlucky enough. But we are into the region of how to restart a router, and advice to give it. Using more than one ANSN is one way to solve that. However the composite of MSN and ANSN is a tricky one. I can see (I think) a horribly inefficient way to make it work, but an efficient way - other than just wait out timeouts - needs more thought.

A restarting router that uses incomplete TCs though is not good behaviour. That would be part of the advice to restarting routers.

(I assume we are considering routers that restart with no memory of their last MSN and ANSN. Those with memory can simply continue.)

---

From: Christopher Dearlove <[email-masked]>
Date: Fri, 23 Jul 2021 14:36:33 +0100

I would start with the principle that we don’t want to change OLSRv2, create incompatibilities etc. unless we actually have to. And I don’t think we need to.

So what we should start with is advice to restarting routers. Can we solve all our problems that way?

Before addressing that, you might say, what about the case of routers that restart but don’t follow advice, can they mess us up? Possibly (though I think it needs a matching ANSN, not just an expired one). But that’s the nature of OLSRv2 and similar protocols, a poorly behaving router can always mess you up. Worse if it is malicious, but that’s a different problem.

And let’s supposed we managed to come up with a set of really good rules for restarting routers. What to do with them.  Could be an informational RFC, advice on restarting a router. Or a standards track RFC, what you should and what you must do on restarting a router. I could see either. Or a non-RFC approach.

But that’s getting ahead. What advice could we give?

First, if the router remembers its old MSN and ANSN (and if necessary, PSN) there’s no problem. (Obviously you’d include this in an RFC/whatever but it’s a trivial case.)

The second trivial case is that you just wait longer than your data will take to timeout. Often the easiest solution. But if you might have been using long timeouts, might be a problem. Or if you want rapid readmission. But that needs other routers to also act rapidly, and might not be an option.

So let’s assume you want back in, have no idea of your old MSN/ANSN, and there might be data out there that needs replacing, and you can’t just wait.

Handling two sequence numbers (MSN/ANSN) together would be tricky. But fortunately we can do these one at a time. Because to get back in, first we need HELLO exchange (NHDP). That only uses MSN. So first we fix MSN, then we move on to ANSN. (Until we’ve exchanged HELLOs, no one will forward our TC messages.)

So pick a random MSN. If we pick badly, we will be ignored. We could wait, see if we are ignored, if we are, move on. (We might be ignored because messages are lost. I’ll ignore that for now. You might want to send messages more than once before moving on to handle that.)

But maybe we would rather not wait that long. So here’s an approach I think works. Haven’t been able to test it - my former employer has my OLSRv2 code unfortunately and won’t let me have it - but that’s the point of discussion.

So we pick three or four equispaced (or roughly so) numbers. Two won’t work, the case of separation by exactly N/2 is unreliable, where N is 2^16. (The version in OLSRv1 is specified but has strange consequences, so we left it unspecified in OLSRv2.). Four is easiest (0, N/4, N/2, 3N/4).

So we send a HELLO (or more than one) with one of those MSNs. Then, without needing to wait, do the same for the rest of the numbers in order. At first we might be ignored, but at some point we will get past the last one we used. Then we will start overriding ourselves. And the last one we send will be accepted. (We can stop early if we get a response, that tells us we have an MSN we can use.)

Is that ugly? Yes. But we are trying to solve the problem of having no information and not being prepared to wait. There are more efficient solutions if we modify OLSRv2 (e.g. reserve 0 or N-1 as a “forced reset” number) but I don’t want to do that as noted.

Now we have established an MSN, once we have data to send in TC messages we could do the same with the ANSN. Or actually we don’t need to wait, we can do that with empty TC messages. Complete ones. (Note that, unlike OLSRv1, empty messages are recorded.)

Why might this not work? (Apart of course from something I’ve overlooked.) I think there is implicit permission for a router to ignore messages with a big gap of sequence number from last seen as a security measure. We need that not to be done. (That would be firming up behaviour.) But - and as even there will be a security implications section - we really want to be running with authenticated messages anyway.

Is this fast enough? That depends on how long your data would take to expire anyway. This is really for cases where long duration data can be assumed.

If anyone does want to take this further, I’m around.

Christopher

---

From: Christopher Dearlove <[email-masked]>
Date: Fri, 23 Jul 2021 15:04:41 +0100

I didn’t addresss this.

> On 23 Jul 2021, at 07:11, Rogge, Henning <[email-masked]> wrote:
> 

First, I don’t think you have the receiver side issue you note. The information will eventually timeout unless the sender sends incomplete messages with valid MSN and latest ANSN. But that’s something it could do anyway.

There are heuristics you might add to say “ignore this message as it fails a smell test”. You can’t stop a router doing that, nor should you. There are various heuristics you could try. Some relevant to this situation, others not. One such is that if you see a message where MSN and ANSN show opposite behaviour, that’s a sign that router is misbehaving. If you interpret misbehaving as “probably reset, I should wipe all its data” that’s drastic but possible. But doing so on the basis of one message is a bit much. And I don’t think you’ll ever get a set of rules applicable to all situations. Which is why I used the term heuristics.

Either in an informational RFC on router reset behaviour, or in a non-normative annex to a standards track RFC, you could include advice on behaviour to look out for that suggests a misbehaving/reset router and that you MAY (no stronger) discard messages or even wipe the database if you see that, probably more than once.

In short, I don’t think this is a soluble, here are rules that always work, problem. But if you find a real problem in a real network you could include code that makes a tradeoff of handling that case while possibly making other cases behave less well. (For example the multiple MSNs/ANSNs I suggest in my last email might trigger some heuristics.) Information might help a network operator. If you are supplying an OLSRv2 implementation and have a heuristic you think is often useful, you could include it as an option. But it would be very easy to think up heuristics that in reality aren’t much use.

---

From: "Rogge, Henning" <[email-masked]>
Date: Tue, 27 Jul 2021 12:09:42 +0000

> This is unfortunate, and part of the problem, router A will find it hard to get back into the network. The easiest way is simply to wait out expiry times, but that might not be an issue if those ha…

Yes, waiting for the configured VTIME before you restart the routing is a valid option with a lot of time-cost involved.

> Yes, the old data won’t be overwritten. But nothing affects the timeout. It doesn’t happen, but it isn’t extended. 16.3.3.1 point 1, the TC message will be discarded. So Topology Tuples etc. aren’t…

I think Ronald and me overlooked this detail... I have to check my implementation, but I think I do this correctly.

> This one might be a problem. Unlucky with 2^16 numbers to pick. But not unlucky enough. But we are into the region of how to restart a router, and advice to give it. Using more than one ANSN is one…

Yes. waiting for the Validity time is often a bad option.

> A restarting router that uses incomplete TCs though is not good behaviour. That would be part of the advice to restarting routers.

Sometimes the router has no choice, e.g. if the list of attached prefixes is just LONG. Long ago I wrote a hack for OLSRv1 that allowed to add the "range" of a partial update... so the receiver could clear every prefix within the range that is not in the TC.

But the most likely way to go for me is to define an OLSRv2 extension so I don't have to send the (mostly static) Attached Networks with every TC. Or finally look into my ideas about RFC 5444 compression.

> (I assume we are considering routers that restart with no memory of their last MSN and ANSN. Those with memory can simply continue.)

Yes, storing all relevant sequence numbers would also help.

> Either in an informational RFC on router reset behaviour, or in a non-normative annex to a standards track RFC, you could include advice on behaviour to look out for that suggests a misbehaving/res…

I think an informational document that points out the issue and offer a few suggestions what you could do would be a good way.

> In short, I don’t think this is a soluble, here are rules that always work, problem. But if you find a real problem in a real network you could include code that makes a tradeoff of handling that c…

I think my confusion was mostly triggered by the fact that the same router coming only again can give me a validity-time long interval of bad network behavior...

Henning Rogge

---

From: "Rogge, Henning" <[email-masked]>
Date: Tue, 27 Jul 2021 12:22:58 +0000

> I would start with the principle that we don’t want to change OLSRv2, create incompatibilities etc. unless we actually have to. And I don’t think we need to.
Yes, breaking the protocol would be bad.

> Before addressing that, you might say, what about the case of routers that restart but don’t follow advice, can they mess us up? Possibly (though I think it needs a matching ANSN, not just an expir…

Every advice should hopefully fall back onto a "solve with timeout".

> First, if the router remembers its old MSN and ANSN (and if necessary, PSN) there’s no problem. (Obviously you’d include this in an RFC/whatever but it’s a trivial case.)

There is also the issue that you might not want to constantly write to flash memory.

> The second trivial case is that you just wait longer than your data will take to timeout. Often the easiest solution. But if you might have been using long timeouts, might be a problem. Or if you w…

Yes.

> Handling two sequence numbers (MSN/ANSN) together would be tricky. But fortunately we can do these one at a time. Because to get back in, first we need HELLO exchange (NHDP). That only uses MSN. So…

I already have a mechanism in place to fix the problem for MSN... because they always increase, I just "restart" the old/new decision as soon as I get 8 consecutive "too old but increasing" MSNs without a single valid one. With this kind of strategy you can reduce the waiting time from TC-VTIME to TC-ITIME*factor

> So we send a HELLO (or more than one) with one of those MSNs. Then, without needing to wait, do the same for the rest of the numbers in order. At first we might be ignored, but at some point we wil…

Hmm... interesting idea...

> Is that ugly? Yes. But we are trying to solve the problem of having no information and not being prepared to wait. There are more efficient solutions if we modify OLSRv2 (e.g. reserve 0 or N-1 as a…

and having a single "reset" number would just fail if we hit a single packet loss.

> Now we have established an MSN, once we have data to send in TC messages we could do the same with the ANSN. Or actually we don’t need to wait, we can do that with empty TC messages. Complete ones.…

If we don't worry about packet loss, we could send all 4 empty TCs in a single OLSR packet.

> Why might this not work? (Apart of course from something I’ve overlooked.) I think there is implicit permission for a router to ignore messages with a big gap of sequence number from last seen as a…

Lets not worry about security, just point to "sign messages" if someone asks.

> If anyone does want to take this further, I’m around.

This is definitely a nice set of ideas, I have to think about them a bit.

Christopher