Heuristics-based peer to peer message routing

• US 7,376,749 B2
• Filed: 08/12/2002
• Issued: 05/20/2008
• Est. Priority Date: 08/12/2002
• Status: Active Grant

• Current Assignee: PNI Canada Acquireco Corp. (Francisco Partners Management LLC)
• Original Assignee: Sandvine Incorporated ULC (Sandvine Corp.)
• Inventors: Loach, Scot, Bowman, Don
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US10/216,676
• Publication Number:
  US 20040044790A1
• Time in Patent Office: 2,108 Days
• Field of Search: 709205-206, 709/221, 709/224, 709/227, 709/238, 709241-242, 709/202, 709/204, 709/244, 370/219, 370355-356, 370/360, 710/316
• US Class Current: 709/238
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/107 with limitation or expansion of the discovery scope
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention is directed to a system and method for administering Peer to Peer (P2P) query messages within a P2P network. The present invention collects a plurality of metrics for each host that it is aware of in a P2P network, most often by a host information or query hit message. The metrics collected aid in determining a set of P2P hosts best able to fulfill a query message, without having knowledge of specific content. The metrics collected also aid in managing query messages in that they determine when to drop query messages or when to resend query messages.

Claims

1. A system for routing messages in a peer to peer network, said system comprising:

a memory;

a processor;

a) a network cache module configured to inspect messages passing through the system and store information relating to hosts in the peer to peer network;

b) a connection metrics module operatively connected to said network cache module;

said connections metric module configured to aggregate connection metrics based on the information relating to hosts received from the network cache module, said connection metrics based on an aggregate of values for all hosts reachable through a particular host as a connection, said connection metrics comprising;

an amount of content available from said connection;

a percentage of hosts firewalled in the connection;

a count of queries sent to the connection and query hits received from the connection,

c) a scheduler module operatively connected to said connection metrics module said scheduler module configured to analyze said connection metrics and rank bests connections based on said connection metrics; and

;

d) a query cache module operatively connected to said scheduler module said query cache module configured to store and forward query messages to a subset of all connections based on said rank of connections.

2. The system of claim 1 further comprising:

a host table database, a connection table database, a query table database and a forwarded table database.

3. The system of claim 1 further comprising means for determining a type of message received by said system and forwarding said type of message to an appropriate module.

4. A method of routing messages in a peer to peer network said method comprising the step of:

inspecting said messages passing through said peer to peer network and storing information relating to hosts in said peer to peer network;

aggregating connection metrics based on the information relating to hosts, said connection metrics based on values for all hosts reachable through a particular host as a connection, said connection metrics comprising;

an amount of content available from said connection;

a percentage of hosts firewalled in the connection;

a count of queries sent to the connection and query hits received from the connection;

analyzing said connection metrics and ranking connections based on said connection metrics; and

storing and forwarding query messages to a subset of connections based on said ranking of connections.

5. The method of claim 4 further comprising the step of upon receiving a host information message, using contents in said host information message to update a network cache.

6. The method of claim 4 further comprising the step of upon receiving a query message using the contents of said query message to update a query cache.

7. The method of claim 4 further comprising the step of upon receiving a query hit message using the contents of said query hit message to update a query cache.

8. The method of claim 4 further comprising the steps of:

issuing a timer event to track time to connect to a host; and

if said timer event has expired, discarding the connection metrics for said host.

9. The method of claim 4 further comprising the steps of:

initiating a timer event for a query message sent to a host;

if said timer event expires, deleting said query message from a query cache.

10. The method of claim 4 further comprising the step of:

if a query that has been forwarded to a host has not met a threshold of hits, reissuing said query.

11. The method of claim 4 further comprising the step of:

when a request is made to connect to a host providing a host from a set of hosts.

12. The method of claim 11 wherein the providing of a host from said set of hosts is done randomly.

13. The method of claim 11 wherein a weight is established for each host, said weight being decremented each time a host is provided, and if said weight reaches zero, removing said host from said set of hosts.

14. The method of claim 11 wherein when all hosts in said set of hosts have been connected to, reinitializing said set of hosts.

15. A computer readable storage medium comprising instructions when executed by a computer causes the instruction to implement a method of:

inspecting said messages passing through said peer to peer network and storing information relating to hosts in said peer to peer network;

aggregating connection metrics based on the information relating to hosts, said connection metrics based on values for all hosts reachable through a particular host as a connection, said connection metrics comprising;

an amount of content available from said connection;

a percentage of hosts firewalled in the connection;

a count of queries sent to the connection and query hits received from the connection;

analyzing said connection metrics and ranking connections based on said connection metrics; and

storing and forwarding query messages to a subset of connections based on said ranking of connections.