Broadcast tiers in decentralized networks

• US 7,143,139 B2
• Filed: 03/27/2002
• Issued: 11/28/2006
• Est. Priority Date: 03/27/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wesley, Ajamu A., Burbeck, Stephen L.
• Primary Examiner(s): Dinh, Khanh
• Assistant Examiner(s): MADAMBA, GLENFORD J
• Application Number:
  US10/108,014
• Publication Number:
  US 20030187974A1
• Time in Patent Office: 1,707 Days
• Field of Search: 709/206
• US Class Current: 709/206
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Methods, systems, and computer program products are disclosed for classifying nodes into broadcast tiers to reduce traffic in decentralized networks. Persistent identifiers are defined for nodes, allowing nodes to be identified across sessions and invocations, even though they re-enter the network with a different network address. Paths taken by content resources as they traverse the network (e.g. which nodes forwarded the content) are persisted, along with reputation information about nodes (e.g. indicating how successful they are at answering queries from peers). Trust relationships can be derived using the persisted information. Preferred embodiments leverage a web services implementation model.

Claims

1. A computer-implemented method of classifying nodes into broadcast tiers to reduce traffic in a decentralized network, comprising steps of:

associating, using a mapping, a unique persistent node identifier for each of a plurality of nodes in the decentralized network with a current network address assigned to the node, wherein a different network address may be assigned to each node upon entering the network multiple times and wherein the mapping is revised to reflect the current network address assigned to each of the nodes upon each entry of the node into the network, and wherein the persistent node identifier for each of the nodes in the network comprises;

(i) an original network address assigned to the node upon an initial entry of the node into the network;

(ii) a date of the initial entry;

(iii) a time of the initial entry; and

(iv) an identifier of a network domain in which the initial entry occurred;

upon determining that a particular request is to be sent from a first of the nodes in the network, classifying, by the first node, others of the nodes into a plurality of tiers by consulting stored reputation information for each of the other nodes to determine the other node'"'"'s reputation for responding to the particular request, wherein the persistent node identifier for each of the other nodes is usable for locating its stored reputation information and wherein the other nodes are classified into tiers based on the consulted reputation information;

using the mapping to determine the current network address for each of the one or more nodes in a highest one of the tiers;

sending the particular request from the first node to each of the one or more nodes in the highest one of the tiers, using the determined current network addresses; and

subsequently using the mapping to determine the current network address assigned to each of the one or more nodes in a next-highest one of the tiers and sending the particular request from the first node to each of the one of more nodes in the next-highest one of the tiers, using the subsequently-determined current network addresses, only if a satisfactory response is not received from any of the nodes in the highest one of the tiers.

2. The method according to claim 1, wherein a time interval is used to limit a period for which the first node waits for responses to determine whether the satisfactory response was received.

3. The method according to claim 2, wherein the time interval is configurable.

4. A computer-implemented method of using broadcast tiers to reduce traffic in a decentralized network, comprising steps of:

selecting, by a first of a plurality of nodes in the decentralized network, one or more others of the nodes which are perceived to be best suited for responding to a particular request from the first node, as compared to nodes not selected, using stored reputation information for each of the other nodes that indicates requests that can be responded to by the node and the node'"'"'s reputation for responding thereto;

determining, by the first node, a current network address of each of the selected nodes by consulting a mapping that associates a unique persistent node identifier for each of the nodes in the network which are known to the first node with a current network address assigned to the known node, wherein a different network address may be assigned to each of the known nodes upon entering the network multiple times and wherein the mapping is revised to reflect the current network address assigned to each of the known nodes upon each entry of the known node into the network and upon learning by the first node, of any change in the current network address assigned to any of the known nodes, and wherein the persistent node identifier for each of the nodes in the network comprises;

(i) an original network address assigned to the node upon an initial entry of the node into the network;

(ii) a date of the initial entry;

(iii) a time of the initial entry; and

(iv) an identifier of a network domain in which the initial entry occurred;

sending the request from the first node to each of the selected nodes, using the determined current network addresses; and

subsequently determining, by the first node, the current network address assigned to each of one or more next-selected ones of the nodes not yet selected by consulting the mapping and sending the request from the first node to each of the next-selected ones of the nodes, using the subsequently-determined current network addresses, only if a satisfactory response is not received from any of the selected nodes within a configurable time interval.

24. The method according to claim 4, wherein the network is a peer-to-peer network.

5. A computer-implemented method of using broadcast tiers to reduce traffic in a decentralized network, comprising steps of:

using a mapping that associates, for each of a plurality of nodes in the decentralized network a unique persistent node identifier for the node with a current network address assigned to the node, wherein a different network address may be assigned to each node upon entering the network multiple times and wherein the mapping is revised to reflect the current network address assigned to each of the nodes upon each entry of the node into the network, and wherein the persistent node identifier for each of the nodes in the network comprises;

(i) an original network address assigned to the node upon an initial entry of the node into the network;

(ii) a date of the initial entry;

(iii) a time of the initial entry; and

(iv) an identifier of a network domain in which the initial entry occurred;

upon determining that a particular request is to be sent from a first of the nodes in the network, selecting, by the first node, one or more other ones of the nodes which are perceived to be best suited for responding to the particular request from the first node, as compared to nodes not selected, using stored reputation information for each of the nodes that is locatable using the persistent node identifier for the node and that indicates requests that can be responded to by the node and the node'"'"'s reputation for responding thereto;

determining, by the first node, the current network address assigned to each of the selected nodes by consulting the mapping;

sending the particular request from the first node to each of the selected nodes, using the determined current network addresses; and

if none of the selected nodes provides a satisfactory response, repeating the selecting, determining, and sending steps for nodes perceived to be next-best suited, among the nodes not yet selected, for responding to the particular request.

6. The method according to claim 5, wherein the repeating step is performed until either the satisfactory response is received or there are no more nodes suited for responding to the particular request.

7. The method according to claim 5, wherein a configurable time interval is used to limit how long the first node waits for the responses from the selected nodes before concluding that no satisfactory response was received.

8. The method according to claim 5, wherein the stored reputation information of the other nodes is stored by the first node and persists even if the other nodes leave the network and re-enter the network with the different network address.

9. The method according to claim 8, wherein the stored reputation information for a particular one of the other nodes indicates how well suited the particular node is for responding to this particular request.

10. The method according to claim 8, wherein the stored reputation information for a particular one of the other nodes indicates how well suited the particular node is for responding to a plurality of requests.

11. The method according to claim 5, wherein the stored reputation information is maintained, by the first node, for each of the other nodes.

12. The method according to claim 5, wherein the stored reputation information is obtained, by the first node, using capabilities advertised by the other nodes.

13. The method according to claim 12, wherein the capabilities are initially advertised upon each node'"'"'s entry into the network.

14. The method according to claim 11, wherein the stored reputation information for each of the nodes further comprises a success measure indicating how successful the node has been when previously responding to the particular request.

15. The method according to claim 11, wherein the stored reputation information for each of the nodes further comprises an efficiency measure indicating how efficient the node has been when previously responding to the particular request.

16. The method according to claim 5, wherein the stored reputation information for each of the nodes further comprises a set of capabilities, and a success measure for the set, which was advertised by each of the other nodes upon its entry into the network.

17. The method according to claim 5, wherein the stored reputation information for each of the nodes further comprises a set of capabilities, and an efficiency measure for the set, which was advertised by each of the other nodes upon its entry into the network.

18. The method according to claim 5, wherein the stored reputation information for each of the nodes further comprises a set of capabilities, and a success measure for each of the capabilities in the set, which was advertised by each of the other nodes upon its entry into the network.

19. The method according to claim 5, wherein the stored reputation information for each of the nodes further comprises a set of capabilities, and an efficiency measure for each of the capabilities in the set, which was advertised by each of the other nodes upon its entry into the network.

20. The method according to claim 11, wherein the reputation information is periodically refreshed using information gathered from the other nodes and sent to the first node.

21. The method according to claim 11, further comprising the step of revising the stored reputation information, by the first node, as it interacts with selected ones of the other nodes and wherein the selecting step uses the revised information.

22. The method according to claim 5, wherein the stored reputation information for each of the other nodes further comprises a set of capabilities initially advertised by the other node upon its entry into the network, along with the first node'"'"'s local view of at least one of the other nodes'"'"' success in performing its advertised capabilities.

23. The method according to claim 5, wherein the stored reputation information for each of the other nodes further comprises a set of capabilities initially advertised by the other node upon its entry into the network, along with the first node'"'"'s local view of at least one of the other nodes'"'"' efficiency at performing its advertised capabilities.

31. The method according to claim 5, wherein the stored reputation information is obtained, by the first node, from a query set advertised by each of the other nodes when sending one or more messages to the first node, wherein the query set advertised by each of the nodes indicates queries to which that node can respond.

32. The method according to claim 31, wherein the query set advertised by each of the nodes uses regular expression syntax to indicate the queries to which that node can respond.

33. The method according to claim 5, wherein the stored reputation information is obtained, by the first node, from a query set advertised by each of the other nodes when sending one or more messages to the first node, wherein the query set advertised by each of the nodes indicates queries to which that can respond and a stature indicating how successful the node is in responding to the queries in its query set.

25. A system for using broadcast tiers to reduce traffic in an ad hoc network, comprising:

a stored mapping that associates, for each of a plurality of nodes in the ad hoc network, a unique persistent node identifier for the node with a current network address assigned to the node, even though a different network address may be assigned to the node upon entering the network multiple times, wherein the stored mapping is revised to reflect the current network address assigned to each node upon each entry of the node into the ad hoc network, and wherein the persistent node identifier for each of the nodes in the network comprises;

(i) an original network address assigned to the node upon an initial entry of the node into the network;

(ii) a date of the initial entry;

(iii) a time of the initial entry; and

(iv) an identifier of a network domain in which the initial entry occurred;

means for recording reputation information, by each of the nodes in the network, the reputation information for each of the nodes comprising results of the node'"'"'s behavior as it interacts with other nodes in the network, wherein the mapping allows persistently associating the behavior with the node even though the node'"'"'s current network address may change;

means for communicating, by each of the nodes, its recorded reputation information to others of the nodes when sending messages thereto;

means for selecting, by a particular one of the nodes in the network upon determining that a particular request is to be sent by the particular node, one or more other ones of the nodes perceived by the particular node to be best suited for responding to the particular request from the particular node, as compared to nodes not selected, using the recorded reputation information that was communicated to the particular node by the other ones and that is locatable, via the mapping, using the persistent node identifier for the communicating node;

means for determining, by the particular node, the current network address of each of the selected nodes by consulting the stored mapping;

means for sending the particular request from the particular node to each of the selected nodes, using the determined current network addresses; and

if none of the selected nodes provides a satisfactory response, means for repeating operation of the means for selecting, means for determining, and means for sending, thereby selecting and sending to nodes perceived to be next-best suited, among the nodes not yet selected, for responding to the particular request.

26. The system according to claim 25, wherein the recorded reputation information for each node indicates how successful the node is at responding to requests from other nodes.

27. The system according to claim 25, wherein the recorded reputation information for each node indicates the node'"'"'s efficiency at responding to requests from other nodes.

28. A computer program product for using broadcast tiers to reduce traffic in an ad hoc network, where a collection of nodes making up the network may change over time, the computer program product embodied on one or more computer-readable media and comprising:

computer-readable program code for associating, for each of the nodes in the network a unique persistent node identifier with a current network address assigned to the node, even though a different network address may be assigned to the node upon entering the network multiple times, wherein the persistent node identifier for each of the nodes in the network comprises;

(i) an original network address assigned to the node upon an initial entry of the node into the network;

(ii) a date of the initial entry;

(iii) a time of the initial entry; and

(iv) an identifier of a network domain in which the initial entry occurred;

computer-readable program code for recording reputation information, by each of the nodes in the network, the reputation information for each of the nodes comprising results of the node'"'"'s behavior as it interacts with other nodes in the network, wherein the mapping allows persistently associating the behavior with the node even though the node'"'"'s current network address may change;

computer-readable program code for communicating, by each of the nodes, its recorded reputation information to others of the nodes when sending messages thereto;

computer-readable program code for selecting, by a particular one of the nodes in the network upon determining that a particular request is to be sent by the particular node, one or more other ones of the nodes perceived by the particular node to be best suited for responding to the request from the particular node, as compared to nodes not selected, using the recorded reputation information that was communicated to the particular node by the other ones and that is locatable, via the mapping, using the persistent node identifier for the communicating node;

computer-readable program code for determining, by the particular node, the current network address of each of the selected nodes by consulting the stored mapping;

computer-readable program code for sending the particular request from the particular node to each of the selected nodes, using the determined current network addresses; and

if none of the selected nodes provides a satisfactory response, computer-readable program code for repeating operation of the computer-readable program code for selecting, the computer-readable program code for determining, and the computer-readable program code for sending, thereby selecting and sending to nodes perceived to be next-best suited, among the nodes not yet selected, for responding to the particular request.

29. The computer program product according to claim 28, wherein the recorded reputation information for each node indicates how successful the node is at responding to this particular request.

30. The computer program product according to claim 28, wherein the recorded reputation information for each node indicates the node'"'"'s efficiency at responding to this particular request.