Instant messaging using distributed indexes

• US 7,657,597 B2
• Filed: 09/26/2002
• Issued: 02/02/2010
• Est. Priority Date: 09/26/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Pabla, Kuldipsingh A., Arora, Akhil K.
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): SHAW, PELING ANDY
• Application Number:
  US10/255,203
• Publication Number:
  US 20040064512A1
• Time in Patent Office: 2,686 Days
• Field of Search: 709/206, 709/204, 707/104.1
• US Class Current: 709/206
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 51/04 Real-time or near real-time messaging, e.g. instant messaging [IM]
• CPC Class Codes: H04L 51/043 using or handling presence information
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Embodiments of a distributed instant messaging system that uses a distributed index in peer-to-peer networks. A distributed index may be used to implement an instant messaging system in a group of participating peers. The distributed index may be used, for example, to route messages between participating peers, in identifying and authenticating peers wishing to participate, in notifying peers of newly joined peers, and in notifying joining peers of participating peers. In one embodiment, zones of the distributed index may be moved to joining peers. In one embodiment, zones of the distributed index stored on departing peers may be moved to participating peers. One embodiment may be implemented in peer-to-peer networks implemented according to a peer-to-peer platform including one or more peer-to-peer platform protocols for enabling peer nodes to discover each other, communicate with each other, and cooperate with each other to form peer groups and share network resources.

Claims

1. A system, comprising:

a network; and

a plurality of peer nodes coupled to the network and configured to;

participate with each other in instant messaging;

store instant messaging information in a distributed index, wherein one or more of the plurality of peer nodes each stores a zone of the distributed index configured to store instant messaging information for a subset of participating peer nodes at locations in the zone indicated by hashes of identifiers of the participating peer nodes;

one of the plurality of peer nodes configured to;

receive a message comprising an identifier;

access routing information comprised in the instant messaging information for a participating peer node corresponding to the identifier from a location in the distributed index indicated by a hash of the identifier comprised in the message; and

route the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

2. The system as recited in claim 1, wherein, to route the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information, the one of the plurality of peer nodes is further configured to send the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

3. The system as recited in claim 1, wherein, to route the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information, the one of the plurality of peer nodes is further configured to:

send the routing information to a peer node that originated the message;

wherein the peer node that originated the message is configured to send the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

4. The system as recited in claim 1, wherein the message is from another one of the plurality of peer nodes.

5. The system as recited in claim 1, wherein the message is from a node on the network.

6. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

add a peer node to the plurality of peer nodes as a participant in the instant messaging; and

store instant messaging information for the added peer node at a location in the distributed index indicated by a hash of an identifier of the added peer node.

7. The system as recited in claim 6, wherein the added peer node is configured to store a zone of the distributed index.

8. The system as recited in claim 6, wherein the plurality of peer nodes is further configured to move a part of one or more of the zones of the distributed index from the one or more of the plurality of peer nodes to the added peer node to form a new zone of the distributed index stored on the added peer node.

9. The system as recited in claim 6, wherein, to add a peer node to the plurality of peer nodes, the plurality of peer nodes is further configured to:

receive a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging; and

add the node to the plurality of peer nodes as the added peer node in response to said request.

10. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

add a peer node to the plurality of peer nodes as a participant in the instant messaging;

provide presence information corresponding to each of one or more of the plurality of peer nodes and stored in the distributed index at locations indicated by hashes of identifiers of the one or more peer nodes to the added peer node; and

wherein the presence information identifies the one or more peer nodes as participants in the instant messaging.

11. The system as recited in claim 10, wherein the presence information comprises contact information for the one or more peer nodes.

12. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

add a peer node to the plurality of peer nodes as a participant in the instant messaging; and

notify one or more of the plurality of peer nodes that the peer node has been added.

13. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

add a peer node with the particular identifier to the plurality of peer nodes as a participant in the instant messaging;

access a request for notification from the distributed index stored at a location indicated by a hash of the particular identifier; and

notify a peer node that originated the request for notification that the peer node with the particular identifier has been added to the plurality of peer nodes in response to the request for notification.

14. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to combine a zone stored on a departing peer node with a zone stored on another peer node of the plurality of peer nodes to form a new zone of the distributed index on the other peer node.

15. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

receive a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determine if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node;

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node, perform authentication of the identifier of the node to determine if the node is to be added to the plurality of peer nodes as a participant in the instant messaging; and

if instant messaging information is not stored at the location in the distributed index indicated by the hash of the identifier of the node, add instant messaging information corresponding to the identifier at the location in the distributed index indicated by the hash of the identifier.

16. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to:

receive a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determine if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node; and

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node;

receive additional identity information from the node;

compare the additional identity information received from the node to identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node; and

if the additional identity information received from the node matches the identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node, add the node as a peer node to the plurality of peer nodes as a participant in the instant messaging.

17. The system as recited in claim 1, wherein the distributed index is a distributed hash table.

18. The system as recited in claim 1, wherein the plurality of peer nodes is further configured to participate in a peer-to-peer environment on the network in accordance with one or more peer-to-peer platform protocols for enabling the plurality of peer nodes to discover each other, communicate with each other, and cooperate with each other to form peer groups and share network resources in the peer-to-peer environment.

19. A method, comprising:

a plurality of peer nodes coupled to a network participating with each other in instant messaging;

the plurality of peer nodes storing instant messaging information in a distributed index, wherein one or more of the plurality of peer nodes each stores a zone of the distributed index configured to store instant messaging information for a subset of participating peer nodes at locations in the zone indicated by hashes of identifiers of the participating peer nodes;

one of the plurality of peer nodes receiving a message comprising an identifier;

the one of the plurality of peer nodes accessing routing information comprised in the instant messaging information for a participating peer node corresponding to the identifier from a location in the distributed index indicated by a hash of the identifier comprised in the message; and

routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

20. The method as recited in claim 19, wherein said routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information comprises the one of the plurality of peer nodes sending the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

21. The method as recited in claim 19, wherein said routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information comprises:

the one of the plurality of peer nodes sending the routing information to a peer node that originated the message;

the peer node that originated the message sending the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

22. The method as recited in claim 19, wherein the message is from another one of the plurality of peer nodes.

23. The method as recited in claim 19, wherein the message is from a node on the network.

24. The method as recited in claim 19, further comprising:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging; and

storing instant messaging information for the added peer node at a location in the distributed index indicated by a hash of an identifier of the added peer node.

25. The method as recited in claim 24, further comprising storing a zone of the distributed index on the added peer node.

26. The method as recited in claim 24, further comprising moving a part of one or more of the zones of the distributed index from the one or more of the plurality of peer nodes to the added peer node to form a new zone of the distributed index stored on the added peer node.

27. The method as recited in claim 24, wherein said adding a peer node to the plurality of peer nodes comprises:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging; and

adding the node to the plurality of peer nodes as the added peer node in response to said request.

28. The method as recited in claim 19, further comprising:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging;

providing presence information corresponding to each of one or more of the plurality of peer nodes and stored in the distributed index at locations indicated by hashes of identifiers of the one or more peer nodes to the added peer node; and

wherein the presence information identifies the one or more peer nodes as participants in the instant messaging.

29. The method as recited in claim 28, wherein the presence information comprises contact information for the one or more peer nodes.

30. The method as recited in claim 19, further comprising:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging; and

notifying one or more of the plurality of peer nodes that the peer node has been added.

31. The method as recited in claim 19, further comprising:

adding a peer node with the particular identifier to the plurality of peer nodes as a participant in the instant messaging;

accessing a request for notification from the distributed index stored at a location indicated by a hash of the particular identifier; and

notifying a peer node that originated the request for notification that the peer node with the particular identifier has been added to the plurality of peer nodes in response to the request for notification.

32. The method as recited in claim 19, further comprising combining a zone stored on a departing peer node with a zone stored on another peer node of the plurality of peer nodes to form a new zone of the distributed index on the other peer node.

33. The method as recited in claim 19, further comprising:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determining if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node;

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node, performing authentication of the identifier of the node to determine if the node is to be added to the plurality of peer nodes as a participant in the instant messaging; and

if instant messaging information is not stored at the location in the distributed index indicated by the hash of the identifier of the node, adding instant messaging information corresponding to the identifier at the location in the distributed index indicated by the hash of the identifier.

34. The method as recited in claim 19, further comprising:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determining if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node; and

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node;

receiving additional identity information from the node;

comparing the additional identity information received from the node to identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node; and

if the additional identity information received from the node matches the identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node, adding the node as a peer node to the plurality of peer nodes as a participant in the instant messaging.

35. The method as recited in claim 19, wherein the distributed index is a distributed hash table.

36. The method as recited in claim 35, wherein the plurality of peer nodes is configured to participate in a peer-to-peer networking environment implemented in accordance with one or more peer-to-peer platform protocol for enabling peer nodes to discover each other, communicate with each other, and cooperate with each other to form peer groups and share network resources in the peer-to-peer environment.

37. A computer-accessible medium comprising program instructions, wherein the program instructions are configured to implement:

a plurality of peer nodes coupled to a network participating with each other in instant messaging;

the plurality of peer nodes storing instant messaging information in a distributed index, wherein one or more of the plurality of peer nodes each stores a zone of the distributed index configured to store instant messaging information for a subset of participating peer nodes at locations in the zone indicated by hashes of identifiers of the participating peer nodes;

one of the plurality of peer nodes receiving a message comprising an identifier;

the one of the plurality of peer nodes accessing routing information comprised in the instant messaging information for a participating peer node corresponding to the identifier from a location in the distributed index indicated by a hash of the identifier comprised in the message; and

routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

38. The computer-accessible medium as recited in claim 37, wherein, in said routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information, the program instructions are further configured to implement the one of the plurality of peer nodes sending the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

39. The computer-accessible medium as recited in claim 37, wherein, in said routing the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information, the program instructions are further configured to implement:

the one of the plurality of peer nodes sending the routing information to a peer node that originated the message;

the peer node that originated the message sending the message to the participating peer node corresponding to the identifier comprised in the message according to the routing information.

40. The computer-accessible medium as recited in claim 37, wherein the message is from another one of the plurality of peer nodes.

41. The computer-accessible medium as recited in claim 37, wherein the message is from a node on the network.

42. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging; and

storing instant messaging information for the added peer node at a location in the distributed index indicated by a hash of an identifier of the added peer node.

43. The computer-accessible medium as recited in claim 42, wherein the program instructions are further configured to implement storing a zone of the distributed index on the added peer node.

44. The computer-accessible medium as recited in claim 42, wherein the program instructions are further configured to implement moving a part of one or more of the zones of the distributed index from the one or more of the plurality of peer nodes to the added peer node to form a new zone of the distributed index stored on the added peer node.

45. The computer-accessible medium as recited in claim 42, wherein, in said adding a peer node to the plurality of peer nodes, the program instructions are further configured to implement:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging; and

adding the node to the plurality of peer nodes as the added peer node in response to said request.

46. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging;

providing presence information corresponding to each of one or more of the plurality of peer nodes and stored in the distributed index at locations indicated by hashes of identifiers of the one or more peer nodes to the added peer node; and

wherein the presence information identifies the one or more peer nodes as participants in the instant messaging.

47. The computer-accessible medium as recited in claim 46, wherein the presence information comprises contact information for the one or more peer nodes.

48. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

adding a peer node to the plurality of peer nodes as a participant in the instant messaging; and

notifying one or more of the plurality of peer nodes that the peer node has been added.

49. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

adding a peer node with the particular identifier to the plurality of peer nodes as a participant in the instant messaging;

accessing a request for notification from the distributed index stored at a location indicated by a hash of the particular identifier; and

notifying a peer node that originated the request for notification that the peer node with the particular identifier has been added to the plurality of peer nodes in response to the request for notification.

50. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement combining a zone stored on a departing peer node with a zone stored on another peer node of the plurality of peer nodes to form a new zone of the distributed index on the other peer node.

51. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determining if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node;

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node, performing authentication of the identifier of the node to determine if the node is to be added to the plurality of peer nodes as a participant in the instant messaging; and

if instant messaging information is not stored at the location in the distributed index indicated by the hash of the identifier of the node, adding instant messaging information corresponding to the identifier at the location in the distributed index indicated by the hash of the identifier.

52. The computer-accessible medium as recited in claim 37, wherein the program instructions are further configured to implement:

receiving a request from a node on the network to be added to the plurality of peer nodes as a participant in the instant messaging, wherein the request comprises an identifier of the node;

determining if instant messaging information corresponding to the identifier of the node is stored at a location in the distributed index indicated by a hash of the identifier of the node; and

if instant messaging information is stored at the location in the distributed index indicated by the hash of the identifier of the node;

receiving additional identity information from the node;

comparing the additional identity information received from the node to identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node; and

if the additional identity information received from the node matches the identity information comprised in the instant messaging information stored at the location in the distributed index indicated by the hash of the identifier of the node, adding the node as a peer node to the plurality of peer nodes as a participant in the instant messaging.

53. The computer-accessible medium as recited in claim 37, wherein the distributed index is a distributed hash table.

54. The computer-accessible medium as recited in claim 37, wherein the plurality of peer nodes is configured to participate in a peer-to-peer networking environment implemented in accordance with one or more peer-to-peer platform protocol for enabling peer nodes to discover each other, communicate with each other, and cooperate with each other to form peer groups and share network resources in the peer-to-peer environment.

55. A system, comprising:

a network; and

a plurality of peer nodes coupled to the network and configured to;

participate with each other in instant messaging;

store instant messaging information in a distributed index, wherein one or more of the plurality of peer nodes each stores a zone of the distributed index configured to store instant messaging information for a subset of participating peer nodes at locations in the zone indicated by hashes of identifiers of the participating peer nodes; and

route messages to the participating peer nodes in accordance with routing information comprised in instant messaging information corresponding to the participating peer nodes and accessed from locations in the distributed index indicated by hashes of identifiers of the participating peer nodes comprised in the messages.

56. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to authenticate nodes on the network in accordance with identity information comprised in instant messaging information corresponding to the nodes and accessed from locations in the distributed index indicated by hashes of identifiers of the nodes in response to requests to participate with the plurality of peer nodes in the instant messaging received from the nodes.

57. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to notify one or more of the plurality of peer nodes of a peer node added to the plurality of peer nodes to participate with the plurality of peer nodes in the instant messaging in accordance with requests for notification received from the one or more of the peer nodes and stored at a location in the distributed index indicated by a hash of an identifier of the peer node added to the plurality of peer nodes.

58. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to:

add a peer node to the plurality of peer nodes as a participant in the instant messaging;

notify the peer node added to the plurality of peer nodes of one or more of the plurality of peer nodes participating in the instant messaging in response to the peer node being added to the plurality of peer nodes.

59. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to:

add a peer node to the plurality of peer nodes as a participant in the instant messaging; and

move a part of one or more of the zones of the distributed index from the one or more of the plurality of peer nodes to the added peer node to form a new zone of the distributed index stored on the added peer node.

60. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to combine a zone stored on a departing peer node with a zone stored on another peer node of the plurality of peer nodes to form a new zone of the distributed index on the other peer node.

61. The system as recited in claim 55, wherein the distributed index is a distributed hash table.

62. The system as recited in claim 55, wherein the plurality of peer nodes is further configured to participate in a peer-to-peer environment on the network in accordance with one or more peer-to-peer platform protocols for enabling the plurality of peer nodes to discover each other, communicate with each other, and cooperate with each other to form peer groups and share network resources in the peer-to-peer environment.