State diagram excludes potential algorithms

[msvoelker]

Our state diagram excludes algorithms that would proceed upon an unsuccessful probe.

When we first arrive in SEARCHING state, PLPMTU equals BASE_PMTU. For instance, a binary search algorithm would start probing with PROBED_SIZE = BASE_PMTU + (MAX_PMTU - BASE_PMTU)/2. If unsuccessful the algorithm would proceed searching with PROBED_SIZE = BASE_PMTU + (MAX_PMTU - BASE_PMTU)/4. However, our state diagram tells us to switch to SEARCH_COMPLETE upon the first unsuccessful probe.

@tuexen suggested to add syntax in order to express a previous or next probe value. Then, we could use (for the arrow form SEARCHING to SEARCH_COMPLETE) a condition like

PROBE_COUNT = MAX_PROBES and prev(PROBED_SIZE) = PLPMTU

@adventureloop @gorryfair OK for you?

[gorryfair]

I don't think it says how you choose probe values or how to progress to the next probe size - that is the search algorithm. It says if you do probe_count successive attempts to find a PLPMTU value without success you should give up.

[msvoelker]

I don't think it says how you choose probe values or how to progress to the next probe size - that is the search algorithm.

Agree.

It says if you do probe_count successive attempts to find a PLPMTU value without success you should give up.

Agree. But, what if your algorithm don't want to give up then but rather try another probe value x, with PLPMTU < x < PROBED_SIZE? Our current state diagram does not allow that.

[adventureloop]

The text has been changed. We think it now allows probing with a new probe size (reseting probe count to 0) which can be either smaller or larger than the first.

[msvoelker]

I couldn't find the text that says we could stay in SEARCHING then. Is it in the State section?

Here is an example to clarify the issue.

MAX_PMTU = local interface MTU = 1500 bytes
BASE_PMTU = 1200 bytes
PMTU = the one we try to find = 1300 bytes
Algorithm: binary search

When entering SEARCHING state, we know BASE_PMTU = 1200 bytes works (PLPMTU = 1200 bytes).
Next PROBED_SIZE = BASE_PMTU + (MAX_PMTU - BASE_PMTU)/2 = 1350 bytes.
PROBE fails repeatedly, PROBE_COUNT will reach MAX_PROBES.
binary search would proceed with PROBED_SIZE = 1275 bytes. --/-- Our state diagram says, we switch to SEARCH_COMPLETE (PLPMTU = 1200 bytes).

[tuexen]

Problem seems to be on my side.

[msvoelker]

I still see a problem here.

@tuexen
We talked about it in the train. Were I able to convince you that there is a problem?

[gorryfair]

On 10/09/2019, 14:52, msvoelker wrote: I still see a problem here. @tuexen <https://github.com/tuexen> We talked about it in the train. Were I able to convince you that there is a problem? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#7?email_source=notifications&email_token=ABYLLESDAULIQQGTRKYQAHLQI6RARA5CNFSM4HM2I46KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD6LFFIA#issuecomment-529945248>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABYLLEQNK3IVW7VU7H2RMSTQI6RARANCNFSM4HM2I46A>.

What is the anticipated problem? Gorry

[tuexen]

@gorryfair OK, after talking to Timo, here is the issue:

The condition we are talking about is the condition PROBE_TIMER expiry: PROBE_COUNT = MAX_PROBES for the state transition SEARCHING to SEARCH_COMPLETE.

Assume we are NOT doing a linear upwards search. Then, it can happen that we probe successfully a value which is less than the PMTU. If the searching algorithm now selects as a next candidate a value which is higher than the PMTU and the path is black-holing these probe packets, we would try MAX_PROBES times and the above condition would force the search algorithm to leave the SEARCHING state instead of trying smaller candidates.