Estimating the Number of Hosts Corresponding to an Address while Preserving Anonymity

Estimating the number of hosts that have been assigned to an Internet address is a challenging problem due to confounding factors such as the dynamic allocation of addresses and the prohibition of access to privacy sensitive data that can reveal user identities and remove anonymity. We propose a probabilistic method that strikes a desired balance between protection of anonymity and accuracy of estimation. By utilising the phenomenon of preferential attachment, we show that the number of hosts corresponding to an address is accurately predicted by the number of times that an address appears in a series of alternating ON and OFF intervals. We validate our method using a four month trace of dynamic address allocations at a campus wireless network. In so doing, we demonstrate the practical significance and utility of such an anonymity preserving method for estimating the number of hosts corresponding to a dynamic address.