Improved search parameters for tox onion routed queries.

1 files changed, 16 insertions, 6 deletions

diff --git a/src/Network/Kademlia/Search.hs b/src/Network/Kademlia/Search.hs
index 58c8fad8..593470c3 100644
--- a/src/Network/Kademlia/Search.hs
+++ b/src/Network/Kademlia/Search.hs
@@ -60,7 +60,7 @@ data SearchState nid addr tok ni r = SearchState
       searchPendingCount :: TVar Int
       -- | Nodes scheduled to be queried.
     , searchQueued       :: TVar (MinMaxPSQ ni nid)
-      -- | The nearest K nodes that issued a reply.
+      -- | The nearest (K - α) nodes that issued a reply.
     , searchInformant    :: TVar (MinMaxPSQ' ni nid (Maybe tok))
       -- | This tracks already-queried addresses so we avoid bothering them
       -- again. XXX: We could probably keep only the pending queries in this
@@ -121,8 +121,17 @@ reset bkts qsearch target st = do
 searchAlpha :: Int
 searchAlpha = 8
 
+-- | 'searchK' should be larger than 'searchAlpha'.  How much larger depends on
+-- how fast the queries are.  For Tox's much slower onion-routed queries, we
+-- need to ensure that closer non-responding queries don't completely push out
+-- farther away queries.
+--
+-- For BitTorrent, setting them both 8 was not an issue, but that is no longer
+-- supported because now the number of remembered informants is now the
+-- difference between these two numbers.  So, if searchK = 16 and searchAlpha =
+-- 4, then the number of remembered query responses is 12.
 searchK :: Int
-searchK = 8
+searchK = 16
 
 sendQuery :: forall addr nid tok ni r.
             ( Ord addr
@@ -158,9 +167,10 @@ sendQuery Search{..} searchTarget searchResult sch@SearchState{..} (ni :-> d) =
              | otherwise = MM.insertTake k n ( kademliaXor searchSpace searchTarget
                                                $ kademliaLocation searchSpace n )
                                                    q
-        qsize <- MM.size <$> readTVar searchQueued
+        qsize0 <- MM.size <$> readTVar searchQueued
+        let qsize = if qsize0 < searchK then searchK else qsize0
         modifyTVar searchQueued    $ \q -> foldr (insertFoundNode qsize) q ns
-        modifyTVar searchInformant $ MM.insertTake' searchK ni tok d
+        modifyTVar searchInformant $ MM.insertTake' (searchK - searchAlpha) ni tok d
         flip fix rs $ \loop -> \case
             r:rs' -> do
                 wanting <- searchResult r
@@ -178,7 +188,7 @@ searchIsFinished SearchState{ ..} = do
     informants <- readTVar searchInformant
     return $ cnt == 0
              && ( MM.null q
-                  || ( MM.size informants >= searchK
+                  || ( MM.size informants >= (searchK - searchAlpha)
                        && ( PSQ.prio (fromJust $ MM.findMax informants)
                             <= PSQ.prio (fromJust $ MM.findMin q))))
 
@@ -217,7 +227,7 @@ searchLoop sch@Search{..} target result s@SearchState{..} = do
                 Just (ni :-> d, q)
                   | -- If there's fewer than /k/ informants and there's any
                     -- node we haven't yet got a response from.
-                    (MM.size informants < searchK) && (cnt > 0 || not (MM.null q))
+                    (MM.size informants < searchK - searchAlpha) && (cnt > 0 || not (MM.null q))
                     -- Or there's no informants yet at all.
                     || MM.null informants
                     -- Or if the closest scheduled node is nearer than the