Numerousity and latency driven dynamic computer grouping

• US 20050193099A1
• Filed: 02/27/2004
• Published: 09/01/2005
• Est. Priority Date: 02/27/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alan Zoran, Michael David, Reus, Edward F.
• Granted Patent: US 7,702,756 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1059 Inter-group management mechanisms, e.g. splitting, merging or interconnection of groups
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

In a domain containing one of many computing devices, the computing device transmits a query and receives back a response from one or more neighbor-casting groups in the domain each including one or more of the computing devices. Predetermined criteria are applied by the computing device to select one of the groups to which it is joined as a group member. The predetermined criteria can be the number of computing devices in the selected group, a length of time between the query and the response from the selected group, or a combination of thereof. When the selected group has few computing devices, the computing device can send a query and receive back a response from one or more groups. By applying criteria similar to the predetermined criteria, the computing device can select one other group, remove itself from its current group, and join the other selected group.

Claims

1. A method comprising:

transmitting a query with a computing device in a domain;

receiving, with the computing device, a response to the query from one or more neighbor-casting (NC) groups in the domain each including one or more said computing devices;

applying, with the computing device, a predetermined criteria to select one said NC group; and

joining the computing device to the selected NC group.

2. The method as defined in claim 1, wherein the predetermined criteria is selected from the group consisting of:

the number of said computing devices in the selected NC group;

a length of time between the query and the response from the selected NC group; and

a combination of the foregoing.

3. The method as defined in claim 1, wherein each said NC group has an identifier that is unique to other said NC groups in the domain.

4. The method as defined in claim 1, wherein each said computing device is selected from among a video game console, a set top box, an automatic teller machine, a Personal Digital Assistance (PDA), a Personal Computer (PC), a cellular telephone, a printer, a facsimile machine, a copier, a multifunction peripheral device, and a server.

5. The method as defined in claim 1, wherein each said response to the query is transmitted by one said computing device in a respective said NC group.

6. The method as defined in claim 1, wherein the query is transmitted over a TCP network with a broadcast or multicast.

7. The method as defined in claim 1, wherein the predetermined criteria to select one said NC group ignores each said response from any said NC group for which the length of time between the query and the response exceeds a predetermined maximum.

8. The method as defined in claim 1, wherein:

each said response includes the number of computing devices in the responding said NC group; and

the predetermined criteria to select one said NC group ignores any said NC group for which the response includes the number of computing devices in the responding said NC group that exceeds a predetermined maximum.

9. The method as defined in claim 8, wherein each said response includes an identifier that is unique to the responding said NC group in the domain.

10. The method as defined in claim 1, wherein one or more of the transmitting, the receiving, the applying, and the joining are executed by a component of an operating system of the computing device that is joined to the selected NC group.

11. The method as defined in claim 10, wherein each of the transmitting, the receiving, the applying, and the joining are executed by the operating system of the computing device joined to the selected NC group.

12. The method as defined in claim 1, wherein one or more of the transmitting, the receiving, the applying, and the joining are executed by an application that is running on the computing device joined to the selected NC group.

13. The method as defined in claim 1, wherein the applying further comprises determining at least one of:

a closest said NC group for which the corresponding response was first to be received; and

a smallest said NC group that has the least number of the computing devices from among those said NC groups for which the response was received.

14. The method as defined in claim 13, wherein the applying further comprises selecting the one said NC group to be the smallest said NC group when the closest said NC group is more than one said NC group.

15. The method as defined in claim 1, wherein the applying further comprises ordering said NC groups for which a corresponding said response was received according to:

the length of time between the query and the corresponding response; and

a number that quantifies the computing devices in the corresponding NC group as is contained in the corresponding response.

16. The method as defined in claim 15, wherein:

the predetermined criteria to select one said NC group ignores each said response from any said NC group for which the length of time between the query and the response exceeds a predetermined maximum; and

the selected NC group is selected by a condition that is selected from the group consisting of;

the length of time between the query and the corresponding response is least;

the number of said computing devices contained in the corresponding response is least; and

the number of members contained in the corresponding response is least when more than one said NC group had the least length of time between the query and the corresponding response.

17. A computer-readable medium comprising instructions that, when executed by a computer, performs the method of claim 1.

18. A method comprising:

transmitting a query with an initial computing device in a domain, wherein the computing device is in an initial NC group that contains a number of said computing devices that are also in the domain, and wherein the number is less than a predetermined threshold;

receiving, with the initial computing device, a response to the query from one or more said NC groups in the domain each including one or more said computing devices;

applying, with the computing device, predetermined criteria to select one said NC group;

removing the initial computing device from the initial NC group; and

joining the initial computing device to the selected NC group.

19. The method as defined in claim 18, wherein the predetermined criteria to select the one said NC group is selected from the group consisting of:

the number of said computing devices in the selected NC group;

a length of time between the query and the response from the selected NC group; and

a combination of the foregoing.

20. The method as defined in claim 18, wherein each said NC group has an identifier that is unique to other said NC groups in the domain.

21. The method as defined in claim 18, wherein each said computing device is selected from among a video game console, a set top box, an automatic teller machine, a PDA, a PC, a cellular telephone, a printer, a facsimile machine, a copier, a multifunction peripheral device, and a server.

22. The method as defined in claim 18, wherein each said response to the query is transmitted by one said computing device in a respective said NC group.

23. The method as defined in claim 18, wherein the query is transmitted over a TCP network with a broadcast or multicast.

24. The method as defined in claim 18, wherein the predetermined criteria to select one said NC group ignores each said response from any said NC group for which the length of time between the query and the response exceeds a predetermined maximum.

25. The method as defined in claim 18, wherein:

each said response includes the number of computing devices in the responding said NC group; and

the predetermined criteria to select one said NC group ignores any said NC group for which the response includes the number of computing devices in the responding said NC group that exceeds a predetermined maximum.

26. The method as defined in claim 25, wherein each said response includes an identifier that is unique to the responding said NC group in the domain.

27. The method as defined in claim 18, wherein one or more of the transmitting, the receiving, the applying, and the joining are executed by a component of an operating system of the initial computing device.

28. The method as defined in claim 27, wherein each of the transmitting, the receiving, the applying, and the joining are executed by the operating system of the initial computing device.

29. The method as defined in claim 18, wherein one or more of the transmitting, the receiving, the applying, and the joining are executed by an application that is running on the initial computing device.

30. The method as defined in claim 18, wherein the applying further comprises determining at least one of:

a closest said NC group for which the corresponding response was first to be received; and

a smallest said NC group that has the least number of the computing devices from among those said NC groups for which the response was received.

31. The method as defined in claim 30, wherein the applying further comprises selecting the one said NC group to be the smallest said NC group when the closest said NC group is more than one said NC group.

32. The method as defined in claim 18, wherein the applying further comprises ordering said NC groups for which a corresponding said response was received according to:

the length of time between the query and the corresponding response; and

a number quantifying the computing devices in the corresponding NC group as is contained in the corresponding response.

33. The method as defined in claim 32, wherein:

the predetermined criteria to select one said NC group ignores each said response from any said NC group for which the length of time between the query and the response exceeds a predetermined maximum; and

the selected NC group is selected by a condition that is selected from the group consisting of;

the length of time between the query and the corresponding response is least;

a number of said computing devices in the corresponding NC group as contained in the corresponding response is least; and

the number of members contained in the corresponding response is least when more than one said NC group had the least length of time between the query and the corresponding response.

34. A computer-readable medium comprising instructions that, when executed by a computer, performs the method of claim 18.

35. A method comprising:

transmitting a query with an initial computing device in a domain, wherein the computing device is in an initial NC group that contains a number of said computing devices in the domain;

receiving with the initial computing device a group response to the query from one or more related said computing device that are in the initial NC group; and

;

when a length of time between the query and each said group response exceeds a predetermined threshold, removing the initial computing device from the initial NC group.

36. The method as defined in claim 35, wherein the predetermined criteria is a length of time between the query and the group response.

37. A computer-readable medium comprising instructions that, when executed by a computer, performs the method of claim 35.

38. A method comprising:

transmitting a query with an initial computing device in a domain, wherein the computing device is in an initial NC group that contains a number of said computing devices in the domain;

receiving with the initial computing device;

a group response to the query from one or more related said computing device that are in the initial NC group; and

an other group response to the query from one or more NC groups in the domain each including one or more said computing devices;

*

when a length of time between the query and each said group response exceeds a predetermined threshold;

applying, with the computing device, a predetermined criteria to select one said NC group other than the initial NC group, wherein the predetermined criteria is selected from the group consisting of;

the number of said computing devices in the selected NC group;

a length of time between the query and the other group response from the selected NC group; and

a combination of the foregoing;

removing the initial computing device from the initial NC group; and

joining the initial computing device to the selected NC group.

39. The method as defined in claim 38, wherein:

the predetermined criteria to select one said NC group ignores each said other group response from any said NC group for which the length of time between the query and the other group response exceeds a predetermined maximum; and

the selected NC group is selected by a condition that is selected from the group consisting of;

the length of time between the query and the corresponding other group response is least;

or

a number of said computing devices in the corresponding NC group as in contained in the corresponding other group response is least; and

the number of members as contained in the corresponding other group response is least when more than one said NC group had the least length of time between the query and the corresponding other group response.

40. A computer-readable medium comprising instructions that, when executed by a computer, performs the method of claim 38.