Re: [tsvwg] Adoption call: draft-fairhurst-tsvwg-datagram-plpmtud-02 to end 10th January 2018

[Mikkel Fahnøe Jørgensen <[e-mail]>]

Here is a Fibonacci variant the grows slower.
Not sure it is any better, but the intention is to avoid probing very large
packets too early.
It could probably be applied recursively to avoid bin search altogether.
The same idea might be applicable to reducing the congestion window as
opposed to doubling or halving.

/* Fibonacci variant */
/* roughly like this - untestet */
unit = 10 /* min probe increment */
a = minPMTU / unit
b = maxPMTU / unit
k1 = initDelta /* 1 or larger, e.g. a / 4 */
k0 = 0
while a + k0 <= b
  k2 = k0 + k1
  n = binsearch(a + k0, min(a + k1 - 1, b), unit)
  if n return n
  k0 = k1
  k1 = k2
end
/* binsearch probes multiples of unit and calls
   updatePMTUEstimate(n) whenever n is a larger
   valid probe than previously reported */

Kind Regards,
Mikkel Fahnøe Jørgensen


On 21 January 2018 at 09.28.32, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:


Since you mentioned it, I implemented "application level" PMTUD in my
implementation of QUIC (https://github.com/private-octopus/picoquic). Basic
"probe" strategy. Start with the min value (from IPv6), then learn the
peer-supported value during the handshake (standard QUIC), then send probes
to perform a binary search between min and max. Stop the binary search if
the range of search is less than 10 bytes. No ICMP dependency. Some
overhead, but that is amortized by sending a dozen packets or so at the
maximum size instead of the default size.

-- Christian Huitema



How you considered exponential search where you start with a conservative
limit for the upper bound, then exponentially increase that limit until
maxPMTU. It is not faster than binary search if each size is equally
likely, but that is probably not true.
I assume it would use less bandwidth if the max is much larger than the
typical PMTU, and allow the application to start using larger MTU’s earlier
since early guesses are more likely to succeed.

/* roughly like this - untestet */
a = minPMTU
b = maxPMTU
k = initDelta /* 1 or larger, e.g. minPMTU / 4 */
while a <= b
  k = min(a + k, b) - a
  n = binsearch(a, a + k - 1)
  if n return n
  a = a + k /* this doubles the search range */
end
return not found

https://en.wikipedia.org/wiki/Exponential_search