reliability-metric

/* 1 step process

type route       = { destination, neighbor, metric: number }
type destination = { pastUsage: number }
type neighbor    = { pastAccuracy: number }

for each route
  probabilities[route] = destination.pastUsage * metric * neighbor.pastAccuracy

selectedRoute = selectRoute(probabilities)
actualMetric  = testRoute(selectedRoute)
accuracy      = inverse(selectedRoute.metric - actualMetric)
updatePastAccuracy(selectedRoute.neighbor, accuracy)

*/


/* 2 step process

// Get average of all past trials of neighbor
let getAvgAccuracy = (neighbor) => sum(neighbor.tests) / neighbor.tests.length

// Create destination probability distribution from past usage of destination
let pd = normalize(destinations.map(dest => dest.pastUsage))

// Select destination to test
let d  = weightedRandomSample(pd)

// Create neighbor probability distribution by multiplying all neighbors metric per destination by
// average past accuracy
let pn = normalize(neighbors.map(neighbor => neighbor.metrics[d] * getAvgAccuracy(neighbor)))

// Select neighbor to test
let n  = weightedRandomSample(pn)

// Push result of test into fixed size list of test results (sliding window)
neighbors[n].tests.pushWindow(testNeighbor(d, n))

*/

Makes sense.
However, its not clear to me why you can't test all of the neighbors given a single destination, or all dest given a single neighbor. Are some of the destinations bad, or at least not useful?
I'm not sure how big the neighbor/dest space is in a 'realistic' network application, but it may very well be the case that no data exists for the specific combination. However, from our conversation, it seems like the network properties are convergent, so it will probably be okay.
Also, for the second test, your pushing results parameterized over (d,n), while the average accuracy is on (n) only. The algorithm would be subject to bias shifts resulting from the limited choice of destinations, each with high temporal variance.

If the first algorithm works, use it, it will probably be 10x -> 100x less work in implement in a production system from a complexity standpoint, and I can't see benefit without looking at the results applied to real network data. However, the obvious benefit is leveraging the random weighting to minimize the cost of network sampling. I recall you saying something about a sliding scale in the sampling that can generalize the 2 step into the 1 step by increasing the sampling to include all possible combinations. Is it also possible to use an adjustable sampling technique for measurement of net accuracy as well?

There are a couple of things this reminds me of: the first is Online Learning, which is generalized MAB. The next, is probabilistic graphical models, (see Daphne Kohler's book), which go into great detail modeling the how probability works for complex factorized distributions.

So, the starting point here is that we have a table of of routes. A route is a tuple of {destination, neighbor, metric}. The size of this table is n neighbors * n nodes in network (destinations). This table is populated by the routing protocol, outside of what's shown here. In the 1 step process above, we weight by the destination's past usage, the route metric (how good the neighbor claims it is for that destination), and the neighbor's past accuracy. This is a pretty simple way to express what we need, but as written it requires iteration over all routes.

The 2 step process is actually more of an optimization (even though I came up with it first). By selecting a specific destination first, we greatly reduce the amount of iteration.