Peer-to-peer collaboration system with edge routing

• US 8,656,017 B2
• Filed: 05/16/2007
• Issued: 02/18/2014
• Est. Priority Date: 05/16/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Jim J., Titchener, Thomas B., Sanfilippo, Thomas D.
• Primary Examiner(s): Nguyen, Dustin
• Assistant Examiner(s): Mesa, Joel
• Application Number:
  US11/803,800
• Publication Number:
  US 20080288580A1
• Time in Patent Office: 2,470 Days
• Field of Search: 709/226, 709/223
• US Class Current: 709/226
• CPC Class Codes: H04L 61/2567 for reachability, e.g. inquiring the address of a correspondent behind a NAT server
• CPC Class Codes: H04L 61/2575 using address mapping retrieval, e.g. simple traversal of user datagram protocol through session traversal utilities for NAT [STUN]
• CPC Class Codes: H04L 61/2578 without involvement of the NAT server
• CPC Class Codes: H04L 63/029 Firewall traversal, e.g. tunnelling or, creating pinholes
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers

Abstract

A peer-to-peer collaboration system in which changes to a shared space may be broadcast to all of the peers in a collaboration session using messages sent with a combination of addressing techniques. Messages may be addressed for direct peer-to-peer transmission, indirect transmission through another peer or indirect transmission through a server. The type of addressing used to communicate with each peer is determined through the use of a routing table. The routing table defines interconnected groups of peers and may be used to select one or more peers in each group as the initial recipients of the message. The initial recipients may forward the message to other peers within their groups, such that all peers receive the message. For peers behind a NAT, one or more NAT traversal techniques may be used to obtain information to construct the routing table.

Claims

1. A method of joining a computing device that is behind a Network Address Translation (NAT) device to a peer-to-peer collaboration session which includes a plurality of peers, the method comprising:

communicating, by the computing device, with a home relay server to discover a type of the NAT device;

determining, by the computing device based on the type of the NAT device, an address vector of the computing device that can be used by the peers of the peer-to-peer collaboration session for traversing the NAT device and directly transmitting messages to the computing device without use of the home relay server;

communicating, by the computing device, the address vector of the computing device to the home relay server for sharing the address vector of the computing device with the peers of the peer-to-peer collaboration session;

receiving, by the computing device from the home relay server, address vectors of the peers of the peer-to-peer collaboration session;

receiving, by the computing device from the home relay server, a list of peers that have established direct connections to other peers of the peer-to-peer collaboration session; and

constructing, by the computing device, a routing table based on the address vectors of the peers of the peer-to-peer collaboration session and the list of peers that have established direct connections to other peers of the peer-to-peer collaboration session, the routing table comprising;

a first group representing peers of the peer-to-peer collaboration session to which the computing device can directly transmit messages without the use of the home relay server, the first group including at least one peer designated as a first super peer by the home relay server, wherein the first super peer is configured to;

receive messages comprising collaboration information from the computing device via direct peer-to-peer transmission; and

forward the messages to other peers in the first group with which the first super peer has established a direct connection; and

a second group representing peers of the peer-to-peer collaboration session to which the computing device can indirectly transmit messages through the home relay server, the second group including at least one peer designated as a second super peer by the home relay server, wherein the second super peer is configured to;

receive messages comprising collaboration information from the computing device via indirect transmission through the home relay server; and

forward the messages to other peers in the second group with which the second super peer has established a direct connection.

2. The method of claim 1, further comprising:

sending, by the computing device, a probing packet to the home relay server; and

receiving, by the computing device, a response to the probing packet from the home relay server.

3. The method of claim 1, further comprising:

sending, by the computing device, at least one message comprising collaboration information to the first super peer in the first group.

4. The method of claim 1, further comprising:

broadcasting, by the computing device, a change message to the peers of the peer-to-peer collaboration session based on the routing table.

5. The method of claim 1, further comprising:

updating, by the computing device, the routing table in response to detecting that a connection to a peer of the peer-to-peer collaboration session has been lost.

6. The method of claim 1, further comprising:

sending, by the computing device, at least one message comprising collaboration information to the home relay server for forwarding to the second super peer in the second group.

7. The method of claim 1, wherein:

the peers of the second group are behind a second NAT, and

the computing device is unable to traverse the second NAT.

8. A computer-readable storage device storing computer-executable instructions that, when executed by a computing device that is behind a Network Address Translation (NAT) device, cause the computing device to perform a method of joining a peer-to-peer collaboration session which includes a plurality of peers, the method comprising:

communicating with a home relay server to discover a type of the NAT device;

determining, based on the type of the NAT device, an address vector of the computing device that can be used by the peers of the peer-to-peer collaboration session for traversing the NAT device and directly transmitting messages to the computing device without use of the home relay server;

communicating the address vector of the computing device to the home relay server for sharing the address vector of the computing device with the peers of the peer-to-peer collaboration session;

receiving, from the home relay server, address vectors of the peers of the peer-to-peer collaboration session;

receiving, from the home relay server, a list of peers that have established direct connections to other peers of the peer-to-peer collaboration session; and

constructing a routing table based on the address vectors of the peers of the peer-to-peer collaboration session and the list of peers that have established direct connections to other peers of the peer-to-peer collaboration session, the routing table comprising;

a first group representing peers of the peer-to-peer collaboration session to which the computing device can directly transmit messages without the use of the home relay server, the first group including at least one peer designated as a first super peer by the home relay server, wherein the first super peer is configured to;

receive messages comprising collaboration information from the computing device via direct peer-to-peer transmission; and

forward the messages to other peers in the first group with which the first super peer has established a direct connection; and

a second group representing peers of the peer-to-peer collaboration session to which the computing device can indirectly transmit messages through the home relay server, the second group including at least one peer designated as a second super peer by the home relay server, wherein the second super peer is configured to;

receive messages comprising collaboration information from the computing device via indirect transmission through the home relay server; and

forward the messages to other peers in the second group with which the second super peer has established a direct connection.

9. The computer-readable storage device of claim 8, wherein the method further comprises:

sending a probing packet to the home relay server; and

receiving a response to the probing packet from the home relay server.

10. The computer-readable storage device of claim 8, wherein the method further comprises:

sending at least one message comprising collaboration information to the first super peer in the first group.

11. The computer-readable storage device of claim 8, wherein the method further comprises:

broadcasting a change message to the peers of the peer-to-peer collaboration session based on the routing table.

12. The computer-readable storage device of claim 8, wherein the method further comprises:

updating the routing table in response to detecting that a connection to a peer of the peer-to-peer collaboration session has been lost.

13. The computer-readable storage device of claim 8, wherein the method further comprises:

sending at least one message comprising collaboration information to the home relay server for forwarding to the second super peer in the second group.

14. The computer-readable storage device of claim 8, wherein:

the peers of the second group are behind a second NAT, and

the computing device is unable to traverse the second NAT.

15. A computing device comprising:

a processor for executing computer-executable instructions; and

memory storing computer-executable instructions for joining the computing device to a peer-to-peer collaboration session that includes a plurality of peers when the computing device is behind a Network Address Translation (NAT) device, the computer-executable instructions comprising instructions for;

communicating with a home relay server to discover a type of the NAT device;

determining, based on the type of the NAT device, an address vector of the computing device that can be used by the peers of the peer-to-peer collaboration session for traversing the NAT device and directly transmitting messages to the computing device without use of the home relay server;

communicating the address vector of the computing device to the home relay server for sharing the address vector of the computing device with the peers of the peer-to-peer collaboration session;

receiving, from the home relay server, address vectors of the peers of the peer-to-peer collaboration session;

receiving, from the home relay server, a list of peers that have established direct connections to other peers of the peer-to-peer collaboration session; and

constructing a routing table based on the address vectors of the peers of the peer-to-peer collaboration session and the list of peers that have established direct connections to other peers of the peer-to-peer collaboration session, the routing table comprising;

a first group representing peers of the peer-to-peer collaboration session to which the computing device can directly transmit messages without the use of the home relay server, the first group including at least one peer designated as a first super peer by the home relay server, wherein the first super peer is configured to;

receive messages comprising collaboration information from the computing device via direct peer-to-peer transmission; and

forward the messages to other peers in the first group with which the first super peer has established a direct connection; and

a second group representing peers of the peer-to-peer collaboration session to which the computing device can indirectly transmit messages through the home relay server, the second group including at least one peer designated as a second super peer by the home relay server, wherein the second super peer is configured to;

receive messages comprising collaboration information from the computing device via indirect transmission through the home relay server; and

forward the messages to other peers in the second group with which the second super peer has established a direct connection.

16. The computing device of claim 15, the computer-executable instructions further comprising instructions for:

sending a probing packet to the home relay server; and

receiving a response to the probing packet from the home relay server.

17. The computing device of claim 15, the computer-executable instructions further comprising instructions for:

sending at least one message comprising collaboration information to the first super peer in the first group.

18. The computing device of claim 15, the computer-executable instructions further comprising instructions for:

broadcasting a change message to the peers of the peer-to-peer collaboration session based on the routing table.

19. The computing device of claim 15, the computer-executable instructions further comprising instructions for:

sending at least one message comprising collaboration information to the home relay server for forwarding to the second super peer in the second group.

20. The computing device of claim 15, wherein:

the peers of the second group are behind a second NAT, and

the computing device is unable to traverse the second NAT.