search

DNSCrypt / dnscrypt-proxy

dnscrypt-proxy 2 - A flexible DNS proxy, with support for encrypted DNS protocols.
https://dnscrypt.info
ISC License
11.28k stars 1k forks source link

EWMA warmup phase issue #2046

Closed ghost closed 2 years ago

ghost commented 2 years ago

The EWMA implementation used has a warmup phase making it return 0 for the first 10 queries.

Unless I've overseen something and this is compensated somewhere, this means that the LBEstimator is initially only seeing 0 RTTs, which is very counterproductive. Currently it needs 18 queries on average to get a meaningful answer for one server. However as only the first 2 servers are queried, one of the fastest ones now becomes the slowest, because the rest is still 0. So the intial good order would be scrambled and (if it was roughly correct) be brought back only after e.g. 180 queries on average assuming 10 live servers.

So in short it's all screwed up.

Any thoughts on how to solve this? Forking EWMA and set WARMUP_SAMPLES=1?

jedisct1 commented 2 years ago

Good catch.

Maybe we can send a pull request to ewma in order to make the number of warmup samples tunable?

ghost commented 2 years ago

Pull requests for new features will be rejected, so we recommend forking the repository and making changes in your fork for your use case.

jedisct1 commented 2 years ago

Ah :( Ok...

jedisct1 commented 2 years ago

Alternatively, we may want to try SimpleEWMA.

lifenjoiner commented 2 years ago

Maybe it is not that bad for LBEstimator:

  1. Rank the servers ASAP by getting the initialRtt. https://github.com/DNSCrypt/dnscrypt-proxy/blob/9373cc71625456f9012d0186b8393d208bca4666/dnscrypt-proxy/proxy.go#L235-L236
  2. Assuming it's already warmed up. https://github.com/DNSCrypt/dnscrypt-proxy/blob/9373cc71625456f9012d0186b8393d208bca4666/dnscrypt-proxy/serversInfo.go#L198

And assuming it's already warmed up, would not too bad. You can simulate and watch it using EWMA_cmp.xlsx. I created it while creating my own EWMA variant, which has a adjusting decay during the warmup. It works by Excel formulas. N stands for warmup sample size. Calculate Now (F9) or entering the value of cell A2 can refresh the sample values in column D and other results. EWMA-cmp

ghost commented 2 years ago

@lifenjoiner

  1. Aren't we doing that already?
  2. This issue is about that it isn't warmupped yet, making the estimator go haywire and taking to long to go back to the roughly ok order we already started with.

Your variant works well.

lifenjoiner commented 2 years ago

@livingentity Yes. I mean as we did those 2 things, the EWMA quality shouldn't go too bad, I guess. You can see the simulation from my previous screenshot. It is the column G comparing to the real average in column I. On the other hand, even we get the exact real average, it would not 100% predict a server's quality in a next query. :p If we can improve it, it'd be better!

Logging the real rtt related changes, if possible, may give a more detailed proof.

ghost commented 2 years ago

Clipping or trimming extreme values should be an improvement, as well as lowering α.