[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #7571 [Tor]: Make AutomapHostsOnResolve work with IPv6
#7571: Make AutomapHostsOnResolve work with IPv6
-------------------------+--------------------------------------------------
Reporter: nickm | Owner:
Type: enhancement | Status: needs_review
Priority: normal | Milestone: Tor: 0.2.4.x-final
Component: Tor | Version:
Keywords: | Parent:
Points: | Actualpoints:
-------------------------+--------------------------------------------------
Comment(by andrea):
Further thought on the random numbers issue: there's a deterministic
O(log(n)) way to do this that doesn't depend strongly on the properties of
the PRNG. We keep track of all the addresses we've already assigned
already (we have to, to be able to test whether one we've picked is
available), and for that to be an acceptably efficient algorithm the test
better take O(log(n)), so we already have some data structure complexity
there. Why not just select some data structure that lets us efficiently
skip over the already assigned addresses? Then pick uniformly distributed
random numbers x in the range 0 <= x < max_address - assigned_addresses,
and, at a conceptual level, we want to (efficiently) compute the
following:
1.) Let S_i for i from 0 to max_address - assigned_addresses - 1 be the
set of all unassigned addresses in numerical order.
2.) Pick S_x
Then this is clearly a uniformly distributed random selection of an
unallocated address, which we can always choose with only one attempt. It
remains only to show that we can efficiently compute S_x.
--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/7571#comment:4>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs