Instrumentation system and methods for estimation of decentralized network characteristics

• US 20050108378A1
• Filed: 04/06/2004
• Published: 05/19/2005
• Est. Priority Date: 10/25/2003
• Status: Abandoned Application

• Current Assignee: Macrovision Corporation (Adeia Inc.)
• Original Assignee: Macrovision Corporation (Adeia Inc.)
• Inventors: Ward, Bruce, Patterson, James
• Application Number:
  US10/818,674
• Publication Number:
  US 20050108378A1
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 41/042 comprising distributed management centres cooperatively managing the network
• CPC Class Codes: H04L 41/048 mobile agents

Abstract

An instrumentation system estimates characteristics of a decentralized network, such as: the size, growth rate, and growth acceleration of the network; the number of instances, the rate of propagation, and the acceleration of propagation of a file in the network; and the search and download activities, in the aggregate and for particular files, in the network. A data center in the instrumentation system performs a set of interrelated methods for inferring these and other characteristics of the network. For estimating some characteristics, it identifies and uses a subset of the network, and uses information from the subset to infer or obtain information of the entire network. For estimating other characteristics, it deploys software agents to masquerade as nodes in the network.

Claims

1. An instrumentation system for estimating decentralized network characteristics, comprising a computer configured to estimate the number of instances of a file in a decentralized network by identifying a representative sample of nodes in the decentralized network, determining the density of the file in the representative sample, and estimating the number of instances of the file in the decentralized network by multiplying the size of the network by the density of the file in the representative sample.

2. The instrumentation system according to claim 1, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by indexing a sample of nodes in the decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute; and

generating the representative sample of nodes by including at least a subset of nodes in the search results.

3. The instrumentation system according to claim 2, wherein the one searchable attribute is independent of network topology.

4. The instrumentation system according to claim 3, wherein the computer is further configured to index the sample of nodes in the decentralized network by identifying a node in the decentralized network, and identifying other nodes connected directly or indirectly to the identified node.

5. The instrumentation system according to claim 1, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by associating nodes in the decentralized network to cells of an attribute matrix having matching attribute values until maximum numbers of nodes are associated to all cells of the attribute matrix so that the representative sample of nodes is generated from at least a subset of the nodes associated to the cells of the attribute matrix.

6. The instrumentation system according to claim 5, wherein the attributes of the attribute matrix are key attributes for which the representative sample of nodes is to be representative.

7. The instrumentation system according to claim 5, wherein the maximum number of nodes associated to each cell is based upon an estimated percentage of nodes in the decentralized network having the attribute value of the cell.

8. The instrumentation system according to claim 5, wherein nodes selected for associating with the cells of the attribute matrix are selected by crawling the network topology starting from an initially selected node.

9. The instrumentation system according to claim 1, wherein the computer is further configured to estimate the rate of propagation of the file in the decentralized network by estimating the number of instances of the file at two points in time, and dividing a difference between the two estimates by a time period between the two points in time.

10. The instrumentation system according to claim 1, wherein the computer is further configured to estimate acceleration of propagation of the file in the decentralized network by estimating the number of instances of the file at three points in time.

11. An instrumentation system for estimating decentralized network characteristics, comprising a computer configured to estimate a total number of search queries for a file in a decentralized network over a specified period of time by multiplying the total number of search queries for the file recorded over the specified period of time by software agents uniformly distributed in the decentralized network by the number of nodes in the decentralized network, and dividing the product by the number of software agents.

12. The instrumentation system according to claim 11, wherein the computer is further configured to uniformly distribute the software agents in the decentralized network by identifying a representative sample of nodes in the decentralized network, and attaching a corresponding software agent to each of the nodes in the representative sample of nodes.

13. The instrumentation system according to claim 12, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by indexing a sample of nodes in the decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute; and

generating the representative sample of nodes by including at least a subset of nodes in the search results.

14. The instrumentation system according to claim 13, wherein the one searchable attribute is independent of network topology.

15. The instrumentation system according to claim 14, wherein the computer is further configured to index the sample of nodes in the decentralized network by identifying a node in the decentralized network, and identifying other nodes connected directly or indirectly to the identified node.

16. The instrumentation system according to claim 13, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by associating nodes in the decentralized network to cells of an attribute matrix having matching attribute values until maximum numbers of nodes are associated to all cells of the attribute matrix so that the representative sample of nodes is generated from at least a subset of the nodes associated to the cells of the attribute matrix.

17. The instrumentation system according to claim 16, wherein the attributes of the attribute matrix are key attributes for which the representative sample of nodes is to be representative.

18. The instrumentation system according to claim 16, wherein the maximum number of nodes associated to each cell is based upon an estimated percentage of nodes in the decentralized network having the attribute value of the cell.

19. The instrumentation system according to claim 16, wherein nodes selected for associating with the cells of the attribute matrix are selected by crawling the network topology starting from an initially selected node.

20. An instrumentation system for estimating decentralized network characteristics, comprising a computer configured to estimate a total number of downloads of a file in a decentralized network over a specified period of time by multiplying the total number of downloads of the file recorded over the specified period of time by software agents uniformly distributed in the decentralized network by the number of nodes in the decentralized network, and dividing the product by the number of software agents.

21. The instrumentation system according to claim 20, wherein the computer is further configured to uniformly distribute the software agents in the decentralized network by identifying a representative sample of nodes in the decentralized network, and attaching a corresponding software agent to each of the nodes in the representative sample of nodes.

22. The instrumentation system according to claim 21, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by indexing a sample of nodes in the decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute; and

generating the representative sample of nodes by including at least a subset of nodes in the search results.

23. The instrumentation system according to claim 22, wherein the one searchable attribute is independent of network topology.

24. The instrumentation system according to claim 23, wherein the computer is further configured to index the sample of nodes in the decentralized network by identifying a node in the decentralized network, and identifying other nodes connected directly and indirectly to the identified node until a statistically representative sample of nodes is included in the sample of nodes being indexed.

25. The instrumentation system according to claim 22, wherein the computer is configured to identify the representative sample of nodes in the decentralized network by associating nodes in the decentralized network to cells of an attribute matrix having matching attribute values until maximum numbers of nodes are associated to all cells of the attribute matrix so that the representative sample of nodes is generated from at least a subset of the nodes associated to the cells of the attribute matrix.

26. The instrumentation system according to claim 25, wherein the attributes of the attribute matrix are key attributes for which the representative sample of nodes is to be representative.

27. The instrumentation system according to claim 25, wherein the maximum number of nodes associated to each cell is based upon an estimated percentage of nodes in the decentralized network having the attribute value of the cell.

28. The instrumentation system according to claim 25, wherein nodes selected for associating with the cells of the attribute matrix are selected by crawling the network topology starting from an initially selected node.

29. A method for identifying a representative sample of nodes in a decentralized network, comprising:

indexing a sample of nodes in a decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute as in the drawn sample; and

generating a representative sample of nodes in the decentralized network by including at least a subset of nodes in the search results.

30. The method according to claim 29, wherein the indexing of the sample of nodes comprises:

indexing a sample of connected nodes in the decentralized network.

31. The method according to claim 30, further comprising:

generating the sample of connected nodes by identifying a node in the decentralized network, and identifying other nodes connected directly or indirectly to the identified node.

32. The method according to claim 31, wherein the identifying a node in the decentralized network comprises:

connecting a node to the decentralized network and using that node as the identified node.

33. The method according to claim 29, wherein the one searchable attribute is independent of network topology.

34. The method according to claim 29, further comprising:

using the representative sample of nodes to obtain an unbiased estimate of the distribution of other node attributes.

35. A method for identifying a representative sample of nodes in a decentralized network, comprising:

(a) identify a node in a decentralized network;

(b) determining if the node has an attribute value matching an attribute value of a cell of an attribute matrix;

(c) if the answer in (b) is NO, then jumping back to (a) to identify another node in the decentralized network, and if the answer to (b) is YES, then determining if the cell has reached its maximum number of associated nodes;

(d) if the answer in (c) is NO, then associating the node to the cell and jumping back to (b) to determine if the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (c) is YES, then determining if all cells in the attribute matrix have reached their maximum numbers of associated nodes; and

(e) if the answer in (d) is NO, then jumping back to (b) to determine whether the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (d) is YES, then generating a representative sample of nodes in the decentralized network from the nodes associated to the cells of the attribute matrix.

36. The method according to claim 35, wherein the attributes of the attribute matrix are key attributes for which the representative sample of nodes is to be representative.

37. The method according to claim 35, wherein the representative sample of nodes in the decentralized network is generated so as to include all of the nodes associated with the attribute matrix.

38. The method according to claim 35, wherein the maximum number of associated nodes for each cell in the attribute matrix is based upon an estimated percentage of nodes in the decentralized network having the attribute value of the cell.

39. The method according to claim 35, wherein each successively identified node in performing (a) is determined by crawling the network topology of the decentralized network starting with a first identified node.

40. The method according to claim 35, further comprising:

using the representative sample of nodes to obtain an unbiased estimate of the distribution of other node attributes.

41. A method for estimating the number of nodes in a decentralized network, comprising:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

42. The method according to claim 41, wherein the reference network is a peer-to-peer file sharing network that keeps track of and provides information of the number of nodes currently connected to the network to each node currently connected to the network.

43. The method according to claim 41, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

performing a low-level port scan for each of the addresses in the random sample, and inferring nodes associated with the decentralized network from the responses.

44. The method according to claim 41, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

performing a high-level application scan for each port known to be used by a client software application associated with the decentralized network on each of the addresses in the random sample, and inferring nodes associated with the decentralized network from the responses.

45. The method according to claim 41, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

hosting a client node connected to the decentralized network with at least one highly demanded file residing on the client node;

recording IP addresses of other nodes in the decentralized network that attempt to communicate with the client node during a fixed period of time to download one or more of the at least one highly demanded file; and

comparing the recorded IP addresses to the addresses in the random sample to identify nodes associated with the decentralized network.

46. A method for estimating the number of nodes in a decentralized network, comprising:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of nodes in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

47. The method according to claim 46, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

performing a low-level port scan for each of the addresses in the random sample, and inferring nodes associated with the decentralized network from the responses.

48. The method according to claim 46, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

performing a high-level application scan for each port known to be used by a client software application associated with the decentralized network on each of the addresses in the random sample, and inferring nodes associated with the decentralized network from the responses.

49. The method according to claim 46, wherein the counting of the number of nodes associated with the decentralized network that reside at addresses in the random sample, comprises:

hosting a client node connected to the decentralized network with at least one highly demanded file residing on the client node;

recording IP addresses of other nodes in the decentralized network that attempt to communicate with the client node during a fixed period of time to download one or more of the at least one highly demanded file; and

comparing the recorded IP addresses to the addresses in the random sample to identify nodes associated with the decentralized network.

50. A method for estimating the growth rate of a decentralized network, comprising:

estimating the number of nodes in the decentralized network at a point in time;

estimating the number of nodes in the decentralized network at a fixed period of time after the point in time; and

estimating the growth rate of the decentralized network by subtracting the estimated number of nodes in the decentralized network at the point in time by the estimated number of nodes in the decentralized network at the fixed period of time after the point in time, and dividing the difference by the fixed period of time.

51. The method according to claim 50, wherein the estimating the number of nodes in the decentralized network at a point in time comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

52. The method according to claim 50, wherein the estimating the number of nodes in the decentralized network at a point in time comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

53. A method for estimating acceleration in a growth of the number of nodes in a decentralized network, comprising:

generating a first estimate of the number of nodes in the decentralized network at a time t0;

generating a second estimate of the number of nodes in the decentralized network at a time (t0+Δ

t), where Δ

t is a time period;

generating a third estimate of the number of nodes in the decentralized network at a time (t0+2·

Δ

t), where 2·

Δ

t is twice the time period; and

estimating acceleration in the growth of the number of nodes in the decentralized network by generating a product by doubling the second estimate, generating a difference by subtracting the first and the third estimates from the product, and dividing the difference by the time period Δ

t.

54. The method according to claim 53, wherein the generating of the first estimate comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

55. The method according to claim 53, wherein the generating of the first estimate comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

56. The method according to claim 53, wherein the generating of the second estimate comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

57. The method according to claim 53, wherein the generating of the second estimate comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

58. The method according to claim 53, wherein the generating of the third estimate comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

59. The method according to claim 53, wherein the generating of the third estimate comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

60. A method for estimating the number of instances of a file in a decentralized network, comprising:

identifying a representative sample of nodes in a decentralized network;

determining a density of instances of a file in the representative sample of nodes; and

estimating the number of instances of the file in the decentralized network by multiplying the density of instances of the file by the number of nodes in the decentralized network.

61. The method according to claim 60, wherein the identifying of a representative sample of nodes comprises:

indexing a sample of nodes in a decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute as in the drawn sample; and

generating a representative sample of nodes in the decentralized network by including at least a subset of nodes in the search results.

62. The method according to claim 60, wherein the identifying of a representative sample of nodes comprises:

(a) identify a node in a decentralized network;

(b) determining if the node has an attribute value matching an attribute value of a cell of an attribute matrix;

(c) if the answer in (b) is NO, then jumping back to (a) to identify another node in the decentralized network, and if the answer to (b) is YES, then determining if the cell has reached its maximum number of associated nodes;

(d) if the answer in (c) is NO, then associating the node to the cell and jumping back to (b) to determine if the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (c) is YES, then determining if all cells in the attribute matrix have reached their maximum numbers of associated nodes; and

(e) if the answer in (d) is NO, then jumping back to (b) to determine whether the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (d) is YES, then generating a representative sample of nodes in the decentralized network from the nodes associated to the cells of the attribute matrix.

63. The method according to claim 60, wherein the determining of the density of instances of a file comprises:

generating a count by counting the number of copies of the file residing on the representative sample of nodes; and

calculating the density of instances of the file by dividing the count by the number of nodes in the representative sample of nodes.

64. The method according to claim 60, wherein the determining of the density of instances of a file comprises:

determining a globally unique identifier for the file by querying the decentralized network for the file;

generating a count by counting the number of occurrences of the globally unique identifier among all nodes in the representative sample of nodes; and

calculating the density of instances of the file by dividing the count by the number of nodes in the representative sample of nodes.

65. The method according to claim 60, wherein the determining of the density of instances of a file comprises:

computing one-way hash values for all files residing on the representative sample of nodes;

generating a count by counting the number of times that a one-way hash value for the file occurs among the computed one-way hash values for all files residing on the representative sample of nodes; and

calculating the density of instances of the file by dividing the count by the number of nodes in the representative sample of nodes.

66. The method according to claim 60, further comprising:

estimating the number of nodes in the decentralized network if the actual number of nodes in the decentralized network is not known.

67. The method according to claim 66, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

68. The method according to claim 66, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

69. A method for estimating the rate of propagation of a file in a decentralized file network, comprising:

estimating the number of instances of a file in a decentralized network at a point in time;

estimating the number of instances of the file in the decentralized network at a fixed period of time after the point in time; and

estimating the rate of propagation of the file in the decentralized network by generating a difference by subtracting the estimated number of instances of the file in the decentralized network at the point in time from the estimated number of instances of the file in the decentralized network at the fixed period of time after the point in time, and dividing the difference by the fixed period of time.

70. The method according to claim 69, wherein the estimating of the number of instances of a file in a decentralized network at a point in time comprises:

identifying a representative sample of nodes in a decentralized network;

determining a density of instances of a file in the representative sample of nodes; and

estimating the number of instances of the file in the decentralized network by multiplying the density of instances of the file by the number of nodes in the decentralized network.

71. The method according to claim 69, wherein the estimating of the number of instances of a file in a decentralized network at the fixed period of time after the point in time comprises:

identifying a representative sample of nodes in a decentralized network;

determining a density of instances of a file in the representative sample of nodes; and

estimating the number of instances of the file in the decentralized network by multiplying the density of instances of the file by the number of nodes in the decentralized network.

72. A method for estimating acceleration of the propagation of a file in a decentralized network, comprising:

generating a first estimate of the rate of propagation of a file in a decentralized file network at a time t0;

generating a second estimate of the rate of propagation of the file in the decentralized file network at a time (t0+Δ

t), where Δ

t is a time period;

generating a third estimate of the rate of propagation of the file in the decentralized file network at a time (t0+2·

Δ

t), where 2·

Δ

t is twice the time period; and

estimating acceleration of the propagation of the file in the decentralized network by generating a product by doubling the second estimate, generating a difference by subtracting the first and the third estimates from the second estimate, and dividing the difference by the time period Δ

t.

73. The method according to claim 72, wherein the generating of the first estimate comprises:

estimating the number of instances of a file in a decentralized network at a point in time;

estimating the number of instances of the file in the decentralized network at a fixed period of time after the point in time; and

estimating the rate of propagation of the file in the decentralized network by generating a difference by subtracting the estimated number of instances of the file in the decentralized network at the point in time from the estimated number of instances of the file in the decentralized network at the fixed period of time after the point in time, and dividing the difference by the fixed period of time.

74. The method according to claim 72, wherein the generating of the second estimate comprises:

estimating the number of instances of a file in a decentralized network at a point in time;

estimating the number of instances of the file in the decentralized network at a fixed period of time after the point in time; and

estimating the rate of propagation of the file in the decentralized network by generating a difference by subtracting the estimated number of instances of the file in the decentralized network at the point in time from the estimated number of instances of the file in the decentralized network at the fixed period of time after the point in time, and dividing the difference by the fixed period of time.

75. The method according to claim 72, wherein the generation of the third estimate comprises:

estimating the number of instances of a file in a decentralized network at a point in time;

estimating the number of instances of the file in the decentralized network at a fixed period of time after the point in time; and

estimating the rate of propagation of the file in the decentralized network by generating a difference by subtracting the estimated number of instances of the file in the decentralized network at the point in time from the estimated number of instances of the file in the decentralized network at the fixed period of time after the point in time, and dividing the difference by the fixed period of time.

76. A method for uniformly infiltrating a decentralized network with software agents masquerading as nodes of the decentralized network, comprising:

identifying a representative sample of nodes in a decentralized network; and

attaching a corresponding software agent masquerading as a node to each of the nodes in the representative sample of nodes.

77. The method according to claim 76, wherein the identifying of a representative sample of nodes comprises:

indexing a sample of nodes in a decentralized network;

building a set of observed values for one searchable attribute found in all nodes in the sample;

drawing a sample of observed values for the one searchable attribute from the set;

performing a search in the decentralized network for nodes having at least one of the observed values for the one searchable attribute as in the drawn sample; and

generating a representative sample of nodes in the decentralized network by including at least a subset of nodes in the search results.

78. The method according to claim 76, wherein the identifying of a representative sample of nodes comprises:

(a) identify a node in a decentralized network;

(b) determining if the node has an attribute value matching an attribute value of a cell of an attribute matrix;

(c) if the answer in (b) is NO, then jumping back to (a) to identify another node in the decentralized network, and if the answer to (b) is YES, then determining if the cell has reached its maximum number of associated nodes;

(d) if the answer in (c) is NO, then associating the node to the cell and jumping back to (b) to determine if the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (c) is YES, then determining if all cells in the attribute matrix have reached their maximum numbers of associated nodes; and

(e) if the answer in (d) is NO, then jumping back to (b) to determine whether the node has another attribute value matching that of another cell of the attribute matrix, and if the answer in (d) is YES, then generating a representative sample of nodes in the decentralized network from the nodes associated to the cells of the attribute matrix.

79. A method for uniformly distributing files in a decentralized network, comprising:

uniformly infiltrating a decentralized network with software agents masquerading as nodes of the decentralized network; and

uploading a file to each of the software agents.

80. The method according to claim 79, wherein the uniformly infiltrating of the decentralized network with software agents comprises:

identifying a representative sample of nodes in a decentralized network; and

attaching a corresponding software agent masquerading as a node to each of the nodes in the representative sample of nodes.

81. A method for estimating a total number of search queries in a decentralized network over a specified period of time, comprising:

uniformly infiltrating a decentralized network with software agents masquerading as nodes in the decentralized network;

causing the software agents to record all received search queries for a specified period of time; and

estimating a total number of search queries in the decentralized network for the specified period of time by generating a sum by adding the received search queries recorded by the software agents during the specified period of time, generating a product by multiplying the sum by the number of nodes in the decentralized network, and dividing the product by the number of the software agents.

82. The method according to claim 81, wherein the uniformly infiltrating of the decentralized network with software agents comprises:

identifying a representative sample of nodes in a decentralized network; and

attaching a corresponding software agent masquerading as a node to each of the nodes in the representative sample of nodes.

83. The method according to claim 81, further comprising:

estimating the number of nodes in the decentralized network if the actual number of nodes in the decentralized network is unknown.

84. The method according to claim 83, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

85. The method according to claim 83, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

86. A method for estimating a total number of search queries for a file in a decentralized network over a specified period of time, comprising:

uniformly infiltrating a decentralized network with software agents masquerading as nodes in the decentralized network;

causing the software agents to record all received search queries for a file during a specified period of time; and

estimating a total number of search queries for the file in the decentralized network for the specified period of time by generating a sum by adding the received search queries for the file recorded by the software agents during the specified period of time, generating a product by multiplying the sum by the number of nodes in the decentralized network, and dividing the product by the number of the software agents.

87. The method according to claim 86, wherein the uniformly infiltrating of the decentralized network with software agents comprises:

identifying a representative sample of nodes in a decentralized network; and

attaching a corresponding software agent masquerading as a node to each of the nodes in the representative sample of nodes.

88. The method according to claim 86, further comprising:

estimating the number of nodes in the decentralized network if the actual number of nodes in the decentralized network is unknown.

89. The method according to claim 88, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

90. The method according to claim 88, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

91. A method for estimating a total number of downloads of a file in a decentralized network over a specified period of time, comprising:

uniformly infiltrating a decentralized network with software agents masquerading as nodes in the decentralized network;

uploading copies of a file to each of the software agents;

causing the software agents to respond to each request to download a copy of the file over a specified period of time, and keep a record of each download;

determining the aggregate number of downloads of copies of the file over the specified period of time by all the software agents; and

estimating a total number of downloads of the file in the decentralized network over the specified period of time by generating a product by multiplying the aggregate number of downloads of copies of the file over the specified period of time by all the software agents by the number of nodes in the decentralized network, and dividing the product by the number of software agents.

92. The method according to claim 91, further comprising:

estimating the number of nodes in the decentralized network if the actual number of nodes in the decentralized network is not known.

93. The method according to claim 92, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space common to a decentralized network and a reference network;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample;

counting the number of nodes associated with a reference network that reside at addresses in the random sample;

calculating a density of the reference network nodes by dividing the count of nodes associated with the reference network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes with a known number of nodes in the reference network, and dividing the product by the density of the reference network nodes.

94. The method according to claim 92, wherein the estimating of the number of nodes in the decentralized network comprises:

drawing a random sample of all potential addresses in an underlying address space;

counting the number of nodes associated with the decentralized network that reside at addresses in the random sample;

calculating a density of the decentralized network nodes by dividing the count of nodes associated with the decentralized network by the number of addresses in the random sample; and

estimating the number of nodes in the decentralized network by multiplying the density of the decentralized network nodes by the size of the address space.

95. The method according to claim 91, wherein the uniformly infiltrating of the decentralized network with software agents comprises:

identifying a representative sample of nodes in a decentralized network; and

attaching a corresponding software agent masquerading as a node to each of the nodes in the representative sample of nodes.

96. The method according to claim 91, wherein the file is a decoy file spoofing another file that is the target of the download requests, and the method estimates the number of downloads of the target file during the specified period of time in the decentralized network.