Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1998-08-31
2001-06-26
Burgess, Glenton B. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
C709S219000, C709S223000, C709S226000, C709S235000, C709S243000, C370S390000, C370S392000, C370S395430, C370S399000, C370S256000, C370S409000, C707S793000
Reexamination Certificate
active
06253242
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of telecommunications and in particular to a group sampling method for connectionless networks.
BACKGROUND OF THE INVENTION
There exist a number of emerging applications that make use of large scale multicast groups on the Internet. Such emerging applications include database replication, service discovery, distributed interactive simulations, and large scale voice and video conferencing. In many cases, these applications require each participant in the multicast group to keep a count of the other members in the multicast group. Such counts are often necessary for scaling feedback in order to perform congestion control or reliable multicast. Additionally, the number of participants in a multicast group is often dynamic, increasing and decreasing sharply at times. For example, in a multimedia conference, there will be a sharp increase in the number of participants when the session begins, and a sharp decrease in the number of participants when the session ends.
In order to effectively count the number of other participants, each participant may maintain a participant list that contains every other member of the multicast group heard from. For truly large scale applications, however, low power devices such as a telephone or TV set top boxes cannot adequately support sufficient memory to maintain a listing of each participant or group member.
The prior art has generally addressed this problem by employing various sampling mechanisms. These prior art sampling mechanisms store only a subset of the group members, yet allow a participant to keep a relatively accurate group size estimate. Specifically, the prior art has employed statistical sampling mechanisms in which group members maintain keys that are random and unique. Each participant in the group maintains a mask, with some number of bits, m, set. If the key of a participant matches the key of the local participant under the masking operation, the participant identifier is kept in the table of the local participant, otherwise its identifier is discarded. Additionally, the prior art has shown how the number of bits in the mask can be increased as group sizes grow, thereby minimizing the variance in the group size estimate for a given memory size. Despite such developments however, the prior art has not demonstrated an effective way to decrease the number of bits in the mask—an essential characteristic when the group membership decreases. Instead, the prior art has relied upon “corrective fudge factors” to compensate for the sampling errors. Unfortunately, however, these factors are inaccurate for those situations where group size decreases rapidly and oftentimes these factors may require a potentially unbounded number of mathematical operations if the group size oscillates rapidly.
Consequently, alternative methods of tracking group members of connectionless network activities are required.
SUMMARY OF THE INVENTION
I have developed a method for determining a group size estimate for applications utilizing connectionless networks. In contrast to prior art methods that simply track all participants who match a key in some kind of flat table, my method tracks participants who match the key under the mask by placing a participant identifier into bins, with each bin corresponding to the number of bits in the mask that match the key. According to my method, when the number of bits in the mask is increased from m to m+1, all of the participant identifiers in bin m are moved into bin m+1. When the number of bits in the mask decreases from m+1 to m, however, no participant identifiers are moved. Additionally, when a refresh packet is received from a particular participant whose participant identifier is in bin k, but the current mask is m bits, for k>m, the participant identifier for that particular participant is moved from bin k to bin m. The group size estimate is then be obtained as
∑
i
=
0
31
B
(
i
)
2
i
where B(I) is the number of participants in the ith bin.
My approach has a number of advantages over prior art methods. Specifically, computation is always bounded for any given group size and estimates remain accurate even over highly dynamic groups with rapid oscillations. Additionally, my method provides a simple way to “favor” certain participants, so that they can be stored in the table even when their key doesn't match the key of the local participant under the masking operation.
Further features and advantages of the present invention will become apparent to those skilled in the art.
REFERENCES:
patent: 4853843 (1989-08-01), Echland
patent: 5511168 (1996-04-01), Perlman et al.
patent: 5742772 (1998-04-01), Sreenan
patent: 5799145 (1998-08-01), Kuriyan
patent: 5799154 (1998-08-01), Kuriyan
patent: 5831975 (1998-11-01), Chen et al.
patent: 6085238 (2000-07-01), Yuasa et al.
patent: 6088344 (2000-07-01), Wales et al.
patent: 6108493 (2000-08-01), Miller
patent: 6115749 (2000-09-01), Golestani et al.
patent: 6141347 (2000-09-01), Shaughnessy
patent: 6181697 (2001-01-01), Nuren berg et al.
patent: WO 98/15133 (1998-04-01), None
patent: WO-15133 (1998-09-01), None
patent: WO-9849856 (1998-11-01), None
Khalili K.M. “A system approach for planning, tuning and upgrading local area network” Colbal Telecommunications conference Dec. 2-5, 1991, pp. 658-663, vol. 1.*
Khalidi M. Yousef “Using multicast communication to locate resources in a LAN-based distributed system” IEEE Oct. 10, 1998, pp. 193-202.
Brosemer Jeffery J.
Burgess Glenton B.
Lucent Technologies - Inc.
Safavian Seyed M.
LandOfFree
Group sampling method for connectionless networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Group sampling method for connectionless networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Group sampling method for connectionless networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455624