Approximating the Number of Active Nodes Behind a NAT Device

Network Address Translation (NAT) is used for various reasons on the Internet and hides the IP address and number of nodes behind the NAT device. Although many applications benefit from the knowledge of number of active nodes behind a NAT device, existing schemes are limited. In this paper, we use TCP timestamp option to count the number of active nodes. Timestamp option includes current timestamp of the machine in the TCP packet. We propose an efficient scheme that counts the number of machines approximately using clustering of timestamps. We use least-squares line fit of timestamp values and convex hulls to efficiently maintain the crucial information about existing clusters. Proposed scheme is online and requires minimal resources. We have investigated various aspects of the scheme to improve its performance. Using a developed tool to send packets, we have observed that the proposed scheme approximates the number of machines that send more than threshold number of packets well. Real experiments validate the proposed scheme.