Rapid dissemination of bulk information to widely dispersed network nodes

• US 7,961,741 B2
• Filed: 10/23/2008
• Issued: 06/14/2011
• Est. Priority Date: 10/23/2008
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: Filippo, William San III, van Greunen, Jana, Hughes, Sterling
• Primary Examiner(s): Phan; Man
• Application Number:
  US12/257,077
• Publication Number:
  US 20100103940A1
• Time in Patent Office: 964 Days
• Field of Search: 370252-255, 370328-352, 370400-503, 455328-441, 709221-227, 709238-245
• US Class Current: 370/400
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1055 involving connection limits involving dynamic management of active down- or uploading connections H04L67/1085
• CPC Class Codes: H04L 67/107 with limitation or expansion of the discovery scope
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network

Abstract

Bulk information is transferred to nodes in a communication network having a plurality of widely dispersed nodes. The information can be an image, content, or configuration information. The information is uni-cast to a selection of nodes by a central node or server, to seed the information at certain nodes in the network. The information is then distributed by these seed nodes to every other node in the network. A first algorithm selects which nodes should be seeded with information by the central node. A second algorithm distributes information in the network on a query basis.

Claims

1. A method of disseminating information from a central location to nodes in a network, comprising:

selecting a node in the network as a seed node and transferring the information to the seed node for storage therein;

sending a notification message from the central location to non-seed nodes in the network, informing them of the availability of said information for download from one or more seed nodes;

from each non-seed node in the network that is to receive the information, sending an information transfer request to an established number of neighbor nodes;

in the event the information is not located at one of said neighbor nodes in response to the transfer request sent to the established number of neighbor nodes after a defined wait interval, sending an information transfer request to a successively increasing number of neighbor nodes, until either the information is located at a neighbor node or a search threshold is reached; and

in the event the information is located, downloading the information from a neighbor node.

2. The method of claim 1, wherein the established number of neighbor nodes is determined on the basis of a metric.

3. The method of claim 2, wherein said metric is related to the quality of a connection to a neighbor node.

4. The method of claim 2, wherein said metric is related to the amount of traffic being handled by the neighbor node.

5. The method of claim 1, wherein the step of increasing the set of neighbor nodes that are sent the transfer request occurs after a plurality of said transfer requests are repeatedly sent a predetermined number of times to said established number of neighbor nodes.

6. The method of claim 1, further including the step of increasing the wait interval in conjunction with increasing the set of neighbor nodes that are sent the transfer request.

7. A method of distributing information to nodes in a network, comprising:

selecting a node in the network as a seed node and storing the information in the seed node;

notifying all non-seed nodes in the network of the availability of said information for download from one or more seed nodes;

from each non-seed node in the network that is to receive the information, sending an information transfer request to an established number of neighbor nodes;

in the event the information is not located at one of said neighbor nodes in response to the transfer request sent to the established number of neighbor nodes after a defined wait interval, sending an information transfer request to a successively increasing number of neighbor nodes, until either the information is located at a neighbor node or a search threshold is reached;

in the event the information is located, determining whether the link quality to the node with the information is above a link quality threshold;

downloading the information if the link quality is above the link quality threshold; and

continuing to transmit requests for the information in the event the link quality is not above the link quality threshold.

8. A method of disseminating information from a central location to nodes in a network, comprising:

selecting a node for seeding by;

selecting a candidate node from a list of nodes in the network;

if the selected candidate node has less than a first preset threshold of other nodes which route through the selected candidate node to an access point of the network, and

if the selected candidate node has more than a second preset threshold of neighbor nodes with a link quality above a preset link quality threshold, designating the selected candidate node as a node for receiving a seed of the information;

transferring the information from the central location to the designated node in the network for storage therein;

sending a message from the central location to other nodes in the network, informing them of the availability of new information;

sending an information transfer request from each of said other nodes to a plurality of neighbor nodes to locate the information; and

in the event the information is located, downloading the information to the requesting node.

9. The method of claim 8, further including the step of determining whether the selected candidate node has a traffic congestion level less than an established value, and designating the selected candidate node as a node for receiving a seed only if the traffic congestion level is less than said established value.

10. The method of claim 8, wherein said steps of selecting a node for seeding are performed for a plurality of candidate nodes, until a predetermined percentage of all nodes that are to receive the information have been designated as nodes for receiving a seed of the information.

11. A method of distributing information in a network, comprising:

selecting a node for seeding by;

selecting a candidate node from a list of nodes in the network;

if the selected candidate node has less than a first preset threshold of other nodes which route through the selected candidate node to an access point of the network, and

if the selected candidate node has more than a second preset threshold of neighbor nodes with a link quality above a present link quality threshold, designating the selected candidate node as a node for receiving a seed of the information;

storing the information at the designated node in the network;

informing other nodes in the network of the availability of new information;

sending an information transfer request from each of said other nodes to a plurality of neighbor nodes to locate the information;

in the event the information is located, downloading the information to the requesting node; and

in the event the information is not located in response to the transfer request sent to said plurality of neighbor nodes after a defined wait interval, sending an information transfer request to a successively increasing set of neighbor nodes, until either the information is located at a neighbor node or a search threshold is reached.

12. A method of disseminating information from a central location to nodes in a network, comprising:

selecting at least one node in the network as a seed node and transferring the information from the central location to the seed node for storage therein;

from each of a plurality of other nodes, sending an information transfer request to a plurality of neighbor nodes to locate the information; and

in the event the information is located, downloading the information by;

sending a request for a portion of the information starting at an established offset value,

downloading the requested information portion,

waiting a predefined period of time after receipt of the requested information portion before sending a request for an additional portion of the information.

13. A method of distributing information in a network, comprising:

selecting at least one node in the network as a seed node and storing the information in the seed node;

from each of a plurality of other nodes, sending an information transfer request to a plurality of neighbor nodes to locate the information;

sending a synchronization message to a plurality of nodes requesting the information, the synchronization message specifying a given channel in a frequency hopping spread spectrum network via which the information is to be transmitted from a given seed node;

receiving, at a plurality of requesting nodes tuned to said given channel, a packet containing the requested information portion; and

downloading the information by;

sending a request for a portion of the information starting at an established offset value,

downloading the requested information portion,

waiting a predefined period of time after receipt of the requested information portion before sending a request for an additional portion of the information.