Network Size Estimation In A Peer-to-Peer Network
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Network Size Estimation In A Peer-to-Peer Network
Published Date
2005-09-15
Publisher
Type
Report
Abstract
The emergence of peer-to-peer networks over the last decade has changed user's perspective about information available on the Web. But, with thousand of nodes joining and leaving a peer-to-peer network within a short span of time, it has become practically impossible for a node (or peer) to keep track of complete network. Often times, however, a node needs to at least have an estimate of number of nodes in such a network. For example, in determining time-to-live for a search query packet, a node must have a good estimate of network size. Previous deterministic approaches require a complete walk on the network, since such networks usually lack a central authority. Such approaches hence do not scale well to large networks. A few approaches, which collect partial information about the network, have been proposed as an alternative to address the scalability issues. This paper presents a novel approach for size estimation of a peer-to-peer network. The basic idea is to sample nodes in the network and then using this partial information about the network, an estimate of the network size is obtained using capture-recapture method. The capture-recapture method is a statistical method, which has been widely used for estimation of size of a closed population in oceanography and epidemiology. For a better estimate, the capture-recapture method requires two or more random (independent) samplings (sets of detected nodes) of the network. In our case, for independent sampling, we use random walks on the peer-to-peer network, since a random walk can achieve same statistical properties as independent samplings for a peer-to-peer network (see Gkantsidis et al [1]). Experimental results show that the proposed random walk based capture-recapture approach gives a good estimate of network size. In addition, results of using proposed method as well as three other size estimation methods on scale-free and random networks shows that the former algorithm gives a better estimate (lesser error) with a slight overhead on computation. This research motivates further study of estimation techniques for open networks (i.e. networks whose size changes during the estimation process).
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Mane, Sandeep; Mopuru, Sandeep; Mehra, Kriti; Srivastava, Jaideep. (2005). Network Size Estimation In A Peer-to-Peer Network. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215671.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.