Sampling Rules for Information Dissemination

• US 20090190599A1
• Filed: 01/30/2008
• Published: 07/30/2009
• Est. Priority Date: 01/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation), Rockwell Collins, Inc. (Rtx Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gkantsidis, Christos, Vojnovic, Milan, Gupta, Varun, Karagiannis, Thomas
• Granted Patent: US 8,081,581 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 67/1074 for supporting data block transmission mechanisms file transfer H04L67/06
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Sampling rules for information dissemination are described which may be applied in a system containing a number of nodes arranged into groups. A target address is selected using one of two methods: selection of an address from the entire address space of the system and selection of an address from a part of the address space which corresponds to set of groups of nodes. The set of groups of nodes is updated when information is successfully disseminated to a node at a target address selected using the first of the two methods. Rules to determine which of the two methods are used for any particular selection operation are also described.

Claims

1. A method of selecting addresses to which to disseminate information in a system, the system comprising a plurality of nodes arranged into groups, and the method comprising:

selecting addresses from an address space associated with the system using one of a first and a second selection mode, wherein the first selection mode comprises selecting an address from the entire address space and wherein the second selection mode comprises selecting an address from a portion of the address space; and

updating the portion of the address space on selection of an address using the first mode that corresponds to a node requiring the information.

2. A method according to claim 1, wherein the first selection mode comprises randomly selecting an address from the entire address space and wherein the second selection mode comprises randomly selecting an address from a portion of the address space.

3. A method according to claim 1, wherein each group is associated with a subset of the address space and wherein the portion comprises at least one subset.

4. A method according to claim 3, further comprising:

switching from the first selection mode to the second selection mode on selection of an address using the first mode that corresponds to a node requiring the information.

5. A method according to claim 4, further comprising:

incrementing a failure counter on selection of an address using the second mode that does not correspond to a node requiring the information.

6. A method according to claim 5, further comprising:

switching from the second selection mode to the first selection mode when the failure counter equals a threshold value.

7. A method according to claim 3, wherein selecting addresses from an address space associated with the system using one of a first and a second selection mode comprises:

using the second selection mode with a probability defined by a probability parameter; and

using the first selection mode when the second selection mode is not used.

8. A method according to claim 3, wherein updating the portion of the address space on selection of an address using the first mode that corresponds to a node requiring the information comprises:

identifying a group corresponding to said node; and

updating the portion of the address space to include the subset associated with said group.

9. A method according to claim 8, wherein updating the portion of the address space further comprises:

removing a subset associated with another group from the portion of the address space.

10. A node in a system comprising:

a sampling component arranged to select a target address for information dissemination using one of a first and a second selection mode, wherein the first selection mode comprises selecting an address from an address space associated with the system and wherein the second selection mode comprises selecting an address from a portion of the address space corresponding to a candidate set of at least one group of nodes in the system;

a dissemination component arranged to attempt to transmit an item of information to the target address; and

a sampling state controller arranged to update the candidate set upon successful transmission of the item of information to a target address selected using the first selection mode.

11. A node according to claim 10, wherein the first selection mode comprises randomly selecting an address from an address space associated with the system and wherein the second selection mode comprises randomly selecting an address from a portion of the address space corresponding to a candidate set of at least one group of nodes in the system.

12. A node according to claim 10, wherein the dissemination component is further arranged to determine if an attempt to transmit an item of information to the target address is successful.

13. A node according to claim 10, further comprising:

a mapping component arranged to identify a group of nodes comprising the target address.

14. A node according to claim 13, wherein the sampling state controller is arranged to update the candidate set to include the identified group of nodes.

15. A node according to claim 10, wherein the sampling component is arranged to:

switch from the first selection mode to the second selection mode on successful transmission of the item of information to a target address selected using the first selection mode.

16. A node according to claim 10, wherein the sampling component is arranged to:

use the second selection mode with a defined probability; and

use the first selection mode when the second selection mode is not used.

17. A method of selecting addresses to which to disseminate information in a system, the system comprising a plurality of nodes arranged into groups, and the method comprising:

accessing node distribution data; and

using the node distribution data to select a target address.

18. A method according to claim 17, wherein using the node distribution data to select a target address comprises:

selecting a group using a probability function; and

selecting a target address at random from a range of addresses associated with the group,

wherein the probability function comprises;

$p_j=\{\begin{array}{cc}\mathrm{\alpha <br><br>}<br><br><br><br>{\mathrm{\omega <br><br>}}_j<br><br>\log <br><br><br><br>\left(\frac{\frac{s_j^A<br><br>\left(0\right)}{{\mathrm{\omega <br><br>}}_j^A}}{1-\frac{i^0-i<br><br>\left(0\right)}{\underset{k\in <br><br>A}{\sum <br><br>}<br><br><br><br>s_k<br><br>\left(0\right)}}\right)& j\in <br><br>A\\ 0& j\notin <br><br>A\end{array}$

where;

α

is a normalization constant,

i⁰ is a target fraction of infected nodes,

i(0) is an initial fraction of infected nodes,

A is the set of most dense groups,

$s_j^A<br><br>\left(0\right)=\frac{s_j<br><br>\left(0\right)}{\underset{k\in <br><br>A}{\sum <br><br>}<br><br><br><br>s_k<br><br>\left(0\right)},<br><br>{\mathrm{\omega <br><br>}}_j^A<br><br>\left(0\right)=\frac{{\mathrm{\omega <br><br>}}_j}{\underset{k\in <br><br>A}{\sum <br><br>}<br><br><br><br>{\mathrm{\omega <br><br>}}_k},$

ω

_j is the range of address associated by group j divided by a sum of the ranges for all groups, and

s_j(t) is a normalized number of susceptible nodes at time t.