Figure 6 presents the pseudo-code for the listen
algorithm. The algorithm takes a conservative approach towards
determining whether a route is verifiable. Since false positive tests
can impact the performance of a few flows, the algorithm uses the
constant and
to trade off between when to test for false
positives. When the test is not applied, we use the fraction of
complete connections as the only metric to determine whether the route
works. The setting of
depends on the popularity of the
prefixes. Firstly, we apply the false positive tests only for popular
prefixes i.e.,
for non-popular prefixes. For a popular
prefix, we choose a conservative estimate of
(closer to
)
i.e., a large fraction of the connections have to complete in order to
conclude that the route is verifiable. On the other hand, if we
observe that a reasonable fraction of combination of incomplete
connections, we apply the false positive test to
sampled complete
connections. The user has choice in tuning
based on the total
number of false positive tests that need to be performed. For
non-popular prefixes, the statistical sample of connections is
small. For such prefixes, we set the value of
to be small.