×

Group sampling method for connectionless networks

  • US 6,253,242 B1
  • Filed: 08/31/1998
  • Issued: 06/26/2001
  • Est. Priority Date: 08/07/1998
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for estimating the number of entities in a group whereby said entities each have a unique key and send data to one another over a connectionless network using a multicast mechanism, the method comprising the steps of:

  • receiving, by a receiving entity, a key unique to one of the other entities;

    sampling the received key by comparing the received key with a mask, wherein said mask is constructed by assigning m bits in a binary word to 0 and the remaining bits to 1 and the comparison includes;

    performing a logical AND of the mask with the received key thereby producing a first resulting test word;

    performing a logical AND of the mask with a unique key associated with the entity performing the comparison thereby producing a second resulting test word; and

    accepting the received key when the first resulting test word is equal to the second resulting test word;

    storing the received key in a bin of a group of bins corresponding to a sampling factor when the received key is acceptable according to the sampling operation such that the storing operation places the received key in bin m if said mask has m bits and wherein said storing operation moves a received key from bin z to bin m if there are m bits in said mask and said key is currently in bin z where z>

    m;

    selectively moving received keys from one bin to another when the sampling factor changes, wherein said moving operation places those keys in bin m which are still accepted when the mask increases to m+1 bits into bin m+1 when said mask changes from m to m+1; and

    ;

    generating the estimate of the number of entities in the group from the number of received keys in stored each bin, wherein said estimate is generated according to the following relationship;

    L=

    i=031


    B

    (i)


    2i
    ;

    where B(i) is the number of keys contained in the ith bin.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×