PATENT DOCUMENT

Publication Number: US-8065418-B1
Application Number: US-76984104-A
Country: US
Kind Code: B1

Title: NAT traversal for media conferencing

Abstract:
Methods for establishing a direct peer-to-peer (“P2P”) connection between two computers are disclosed. In particular, the methods are designed to work in cases where one or both of the computers are connected to a private network, such private networks being interconnected via a public network, such as the Internet. The connections between the private network and the public network are facilitated by network address translation (NAT).

Claims:
1. A method for initiating a peer-to-peer network connection from a first computer to a second computer across a public network, wherein at least one of the first and second computers is on a private network and is connected to the public network through a network address translator, the first and second computers having each established a connection to a common Relay server, the method comprising the steps of:
 sending a connection request message from the first computer to the Relay server for re-transmitting to the second computer; 
 receiving at the first computer from the Relay server a message originating at the second computer, said message comprising one or more addresses corresponding to the second computer; 
 attempting to initiate a connection from the first computer directly to the second computer using one or more of the addresses received in the message; and 
 sending a message from the first computer to the Relay server, for re-transmitting to the second computer, requesting that the second computer initiate a connection with the first computer in response to a failure to establish a connection between the first computer and each of the addresses corresponding to the second computer. 
 
     
     
       2. The method of  claim 1  wherein the one or more addresses corresponding to the second computer comprise one or more IP addresses and one or more port numbers. 
     
     
       3. The method of  claim 2  wherein the message originating at the second computer comprising one or more addresses corresponding to the second computer further comprises a specified transformation of the one or more addresses. 
     
     
       4. The method of  claim 3 , wherein the specified transformation comprises a binary complement transformation. 
     
     
       5. The method of  claim 1  wherein the one or more addresses corresponding to the second computer comprise one or more IP addresses and one or more port numbers. 
     
     
       6. The method of  claim 5  wherein the message originating at the second computer comprising one or more addresses corresponding to the second computer further comprises a predetermined transformation of the one or more addresses. 
     
     
       7. The method of  claim 6 , wherein the specified transformation comprises a binary complement transformation. 
     
     
       8. A program storage device having instructions stored therein for causing a programmable control device to initiate a peer-to-peer network connection from a first computer to a second computer across a public network, wherein at least one of the first and second computers is on a private network and is connected to the public network through a network address translator, the first and second computers having each established a connection to a common Relay server, said instructions comprising instructions to:
 send a connection request message from the first computer to the Relay server for re-transmitting to the second computer; 
 receive at the first computer from the Relay server a message originating at the second computer, said message comprising one or more addresses corresponding to the second computer; 
 attempt to initiate a connection from the first computer directly to the second computer using one or more of the addresses received in the message; and 
 means for sending a message from the first computer to the Relay server, for re-transmitting to the second computer, requesting that the second computer initiate a connection with the first computer in response to a failure to establish a connection between the first computer and each of the addresses corresponding to the second computer.

Description:
BACKGROUND 
     The invention relates generally to computer systems and more particularly, but not by way of limitation, to a technique for establishing a peer-to-peer (“P2P”) connection between two computers in the presence of network address translation (“NAT”). Establishing a P2P connection between two computers is useful for the implementation of various applications, including, for example, gaming, file sharing, and media (audio, video, etc.) conferencing. Although the system herein is described with reference to Internet Protocol (“IP”) networks, the invention is not so limited and could be used with other network types. 
     Large public networks, such as the Internet, frequently have connections to smaller private networks, such as those maintained by a corporation, Internet service provider, or even individual households. By their very nature, public networks must have a commonly agreed upon allocation of network addresses, i.e., public addresses. For a variety of reasons, some of which are discussed in more detail below, maintainers of private networks often choose to use private network addresses for the private networks that are not part of the commonly agreed upon allocation. Thus, for network traffic from the private network to be able to traverse the public network, some form of NAT is required. 
     As is known to those skilled in the art, the basic principle of NAT is that a private network, having a private addressing scheme, may be connected to a public network, having a standardized addressing scheme, e.g., the Internet through a network address translator. A network address translator (details of which are known to those skilled in the art) alters the data packets being sent out of the private network to comply with the addressing scheme of the public network. Particularly, the network address translator replaces the originating private address and port number of a packet with its own public address and an assigned port number. A network address translator also alters the data packets being received for computers on the private network to replace the destination public address and port number with the correct private address and port number of the intended recipient. As used herein, the term address should be construed to include both an address and a port number if appropriate in the context, as would be understood by one of ordinary skill in the art. 
     NAT has become increasingly common in modern network computing. One advantage of NAT is that it slows the depletion of public network address space. For example, TCP/IP addressing, which is used on the Internet, comprises four strings of three digits each, thus providing a finite address space. Additionally, certain portions of this address space are reserved for particular uses or users, further depleting the actual number of addresses available. However, if NAT is used, a private network or subnet may use an arbitrary number of addresses, and still present only a single, standardized public address to the outside world. This makes the number of available addresses practically limitless, because each private network could, theoretically, use exactly the same private addresses. 
     Another advantage provided by NAT is increased security. The increased security arises in part from the fact that those on the public network cannot determine the actual (i.e., private) network address of a computer on a private network. This is because only the public address is provided on the public network by the network address translator. Additionally, this public address may correspond to any number of computers on the private network. This feature also facilitates network address translators acting as firewalls, because data received by the network address translator that does not correspond to a request from a computer on the private network may be discarded. 
     While this security works well in conventional client-server computing, where connections to a “server” on the public network are initiated by a “client” on the private network, it poses problems for P2P connections. In many P2P applications, it is desirable to establish a connection directly between two computers (i.e., peers) that would be considered clients in a traditional sense, but that may act both as clients and as servers in the context of the P2P connection. Establishing a direct connection becomes increasingly difficult if one or both of the peers is located behind one or more levels of NAT. 
     Historically, there have been various techniques for establishing a P2P connection in the presence of NAT. These techniques include Relaying, Connection Reversal, UDP Hole Punching, UDP Port Number Prediction, and Simultaneous TCP Connection Initiation. Each of these techniques suffers from various deficiencies that render them undesirable for various applications. For example, Relaying increases network overhead and latency, which is undesirable for timing critical applications such as video conferencing or gaming. Connection Reversal will only work if only one of the peers is located behind a network address translator. UDP Hole Punching, as the name implies, works well only with UDP connections and is less successful using other transport layer protocols, such as TCP. UDP Port Number Prediction requires predictable behavior by the various components, and is also geared toward UDP connections. Simultaneous TCP Connection Initiation requires a degree of luck, both with regard to addressing and port assignment and connection timing, resulting in a fragility that renders it unsuitable for general application. 
     Thus, it would be beneficial to provide a means to permit computers each located behind one or more NAT layers to establish a direct, P2P connection in a way that is efficient, reliable, and requires minimal redesign of existing network infrastructure. 
     SUMMARY 
     The present invention relates to establishing a direct P2P connection between computers wherein one or both of the computers are located behind one or more layers of NAT. In one embodiment, an initiating computer sends a message to the receiving computer by way of a Relay server. The Relay server retransmits this request to the receiving computer, which has already established a connection with the Relay server. Upon receiving this request, the receiving computer determines a list of addresses on which it believes it can be contacted and transmits this information to the Relay server, which then re-transmits the information to the initiating computer. Upon receiving this information, the receiving computer sends direct initiation messages to the addresses provided by the receiving computer until a direct P2P connection is established. If a connection cannot be established, the initiating computer sends a message so indicating to the Relay server, which re-transmits this information to the receiving computer. The receiving computer then starts the process over, this time acting as the initiating computer. 
     In another embodiment, both the initiating computer and the receiving computer have logged into a Relay server. An initiating computer determines its public address by querying an address-determination server. It then generates a list of addresses on which it believes it can be contacted and transmits this information to the Relay server, which re-transmits this information to the receiving computer. On receiving the initiating computer&#39;s address information, the receiving computer also determines its public address and generates a list of addresses on which it believes it can be contacted. The receiving computer also sends a sequence of messages to the initiating computer, which are discarded by a network address translator behind which the initiating computer is located, but which set up the receiving computer&#39;s network address translator to later accept a connection. The receiving computer then transmits the addresses on which it believes it can be contacted to the Relay server, which re-transmits this information to the initiating computer. The initiating computer, having received this information, sends a sequence of initiation messages directly to the addresses provided by the receiving computer, and these messages are able to pass through the receiving computer&#39;s network address translator because of the earlier sequence of messages sent by the receiving computer. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a network topology in which the teachings of the present invention may be used. 
         FIG. 2  illustrates the address header information in connection with various types of network address translation. 
         FIG. 3  illustrates an operational matrix for selecting which technique in accordance with the present invention is necessary to establish a connection between two peers. 
         FIG. 4  illustrates the sequence of messages in one technique of establishing a peer-to-peer connection in accordance with the present invention. 
         FIG. 5  illustrates the sequence of messages in another technique of establishing a peer-to-peer connection in accordance with the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Techniques (methods and devices) to establish a peer-to-peer (“P2P”) connection between computers each located behind one or more levels of network address translation (“NAT”) are described herein. The following embodiments of the invention, described in terms applications compatible with computer systems manufactured by Apple Computer, Inc. of Cupertino, Calif., are illustrative only and should not be considered limiting in any respect. 
     Turning now to  FIG. 1 , a general network topology in which the present invention may be used is illustrated. A plurality of “client” or “peer” computers  110   a  through  110   f  are interconnected by public network  150 , which could be, for example, the Internet. Peer computers  110   c  and  110   e  are directly connected to public network  150 . Peer computers  110   d  and  110   f  are connected behind network address translators  123  and  124 . Still other peer computers  110   a  and  110   b  are connected behind two layers or levels of network address translators,  121  and  122 . Relay server  130 , which is used in the relaying technique of the prior art is also connected to public network  150 . Finally, Address Determination server  140 , used to provide a peer&#39;s public address in accordance with the teachings of the present invention, is also connected to public network  150 . Address Determination server  140  provides the means for a peer to determine its public address and port number as assigned by a network address translator behind which the peer resides. 
     With reference now to  FIG. 2 , the address headers used in connection with three common types of NAT are illustrated. A first type of NAT is a full cone NAT, which means that all requests from the same internal (private) IP address and port are mapped to the same external (public) IP address and port. In this type of NAT, any external host can send a packet to the internal host by sending the packet to the mapped external address and host. Address header information  210  for a full cone NAT thus includes internal IP address  211 , internal port assignment  212 , and external port assignment  213 . (The external address will be the public address of the network address translator.) 
     A second type of NAT is a restricted cone NAT, which means that all requests from the same internal IP address and port are mapped to the same external IP address and port. However, unlike a full cone NAT, an external host can send a packet to the internal host only if the internal host had previously sent a packet to the IP address of the external host. Thus data header  220  includes the same information as with a full cone NAT (internal IP address  221 , internal port assignment  222 , and external port assignment  223 ) and also includes additional field  224  that identifies the remote address to which a packet has previously been sent. 
     A third type of NAT is a port-restricted cone NAT, which is a restricted cone NAT further restricted to port numbers. Specifically, an external host can send a packet to an internal host only if the internal host had previously sent a packet to the specific IP address and port from which the “return” packet originated. Thus, to successfully traverse a port restricted cone NAT, address header  230  must include all the information in a restricted cone header (i.e., internal IP address  231 , internal port assignment  232 , external port assignment  233 , remote IP address  234 ) and the additional information of the remote port to which a packet has previously been sent. 
     Additionally, a network address translator may also use port address translation (“PAT”). When PAT is used, the network address translator will use a different port for each outbound address/port combination. If PAT is not implemented, a single port number is used for each client. 
       FIG. 3  illustrates an operational matrix for determining which process in accordance with the present invention may be used for establish a P2P connection between two peers. For purposes of the following discussion, it is assumed that PEER- 0  is initiating the connection with PEER- 1 . As can be seen from  FIG. 3 , if both PEER- 0  and PEER- 1  are located on the public network, as with peers  110   c  and  110   e  of  FIG. 1 , then no special technique is needed as each computer&#39;s packets indicate its true address and port number. If PEER- 0 , located on the public network, attempts to initiate a connection with PEER- 1  located on a private network, as with peer  110   c  attempting to initiate a connection with peer  110   d , then a first technique ALPHA, discussed below in connection with  FIG. 4  may be used. In the situation where both PEER- 0  and PEER- 1  are both located on private networks, as with peer  110   a  attempting to initiate a connection with peer  110   d , the technique ALPHA will work if one of the peers is behind a full-cone network address translator (described above with reference to  FIG. 2 ). Otherwise, a second technique BETA, discussed below in connection with  FIG. 5  must be used. Technique BETA will work for establishing a connection between two peers each located on a private network, even if both peers are located behind multiple NAT layers, as with peers  110   a  and  110   b  of  FIG. 1 . 
     Turning now to  FIG. 4 , first process ALPHA for establishing a connection between initiating peer  110   c  located on public network  150  and receiving peer  110   d  located behind network address translator  123  is illustrated. A P2P connection can only be established with peer  110   d  if this peer has previously logged in to some third party server, for example, Relay server  130 . Thus peer  110   d  transmits login message  431  to Relay server  130 . Initiating peer  110   c  must also login to Relay server  130 , by transmitting login message  421 . Provided that both peers  110   c  and  110   d  have logged into Relay server  130 , initiating peer  110   c  may then request a connection with peer  110   d  by sending connection request message  422  to Relay server  130 , which acts as an intermediary. Relay server  130  then transmits this information to peer  110   d  as notification message  441 . 
     Upon receiving notification message  441  from Relay server  130  that a connection is requested, peer  110   d  transmits address-determination message  432  to Address Determination server  140 . The purpose of this message is solely for allowing peer  110   d  to determine its public IP address and port number assignment, which are assigned by network address translator  123 . Address Determination server  140  returns reply message  411  to peer  110   d , from which peer  110   d  can determine its public IP address and port assignment. 
     Peer  110   d , having determined its port assignment generates IP-List  433 , which is a list of private IP addresses and corresponding ports on which peer  110   d  can receive a connection. IP-List  433  also includes Flipped List, which is the binary complement of the listing of IP address and port combinations. It will be recognized that a Flipped-List may be generated in accordance with any user-specified transformation of the IP-List&#39;s contents (a binary complement is but one transformation). The flipped list is used because some network address translators interrogate outgoing packets and, if they find a local (private) IP address, convert it to the network address translator&#39;s external (public) IP address. This action would destroy IP-List  433 , which is used by peer  110   c  for initiating the connection. Once generated, IP-List  433  is transmitted to Relay server  130 , which re-transmits the IP-List  442  to peer  110   c.    
     Taking the information from IP-list  442 , peer  110   c  then begins initiating a direct P2P connection with peer  110   d . Specifically, peer  110   c  steps through the addresses and ports contained in IP-list  442  issuing connection requests  423  to peer  110   d  until it is able to establish a connection with peer  110   d  (using the “flipped” aspect of IP List  442  if necessary). In one embodiment, session initiation protocol (“SIP”) invitation messages comprise connection requests  423 . Generally, connection request messages  423  after issued one after another, with a specified time delay between each transmission. For example, three (3) seconds. If peer  110   c  is unable to establish a connection with peer  110   d , peer  110   c  can ascertain that peer  110   d  is behind a network address translator and/or firewall and that network address translator and/or firewall is restricted. Peer  110   c  would then contact Relay server  130  and ask the Relay server to have peer  110   d  contact peer  110   c . At that time, the process of  FIG. 4  is repeated, but with peer  110   d  trying to initiate communication. 
     Turning now to  FIG. 5 , process BETA is illustrated which works regardless of which peer initiates communication and regardless of how many network address translators or firewalls either or both peers are behind. For purposes of explanation of  FIG. 5 , it is assumed that peer  110   f  is initiating a P2P connection with peer  110   d . The beginning of the process requires both peers to have logged onto Relay server  130 , which is done by the transmission of logon message  521  by peer  110   f  and logon message  531  by peer  110   d . To initiate a P2P session, peer  110   f  transmits address detection message  522  to Address Detection server  140 . 
     As with method ALPHA described above, address determination message  522  allows peer  110   f  to determine its public IP address and port number. Address Determination server  140  returns message  511  to peer  110   f , from which peer  110   f  can determine its public IP address and port assignment. Having determined its IP address and port assignment, peer  110   f  then generates IP-List  523 , which is a list of local IP addresses and corresponding ports. As with method ALPHA described above, IP-List  523  also includes a flipped List, i.e., the binary complement of the listing of IP address and port combinations. Once generated, IP-List  523  is transmitted to peer  110   d  by way of Relay server  130  as part of call message  524 . 
     Peer  110   d , upon receiving peer  110   f &#39;s IP-list  523  as part of relayed call message  541  from Relay server  130 , then sends its own address determination message  531  to Address Determination server  140  so that peer it may determine its public IP address and port number. Address Determination server  140  returns message  512  to peer  110   d  in which its public IP address and port assignments are identified. Peer  110   d  then begins sending a series of I-Ping messages  532  to peer  110   f . In one embodiment, each I-Ping message  532  is a junk UDP packet, and one is sent to each of peer  110   f &#39;s IP-List entries. While each I-Ping packet is dropped by peer  110   f &#39;s network address translator, these packets set up peer  110   d &#39;s network address translator to later receive and accept an incoming connection request message (e.g., a SIP invitation message). 
     Having determined its IP address and port assignment, peer  110   d  then generates its own IP-List  533 , which also includes a flipped list. Once generated, IP-List  533  is transmitted to peer  110   f  by way of Relay server  130  as message  534 . Relay server  130  re-transmits this information via message  542  to peer  110   f , which determines the IP address/port pairs in unflip operation  525 . Peer  110   f  then sends a connection request message  526  (e.g., a SIP invitation message) to each IP/port pair in peer  110   d &#39;s IP-List until a connection is received and accepted. Once one of the connection request messages is accepted, a P2P connection is established directly between peer  110   f  and peer  110   d . As described above, individual connection request messages may be staggered in time such as, by three (3) seconds. As previously noted, process BETA described above may be used with all types of connections because neither peer knows or cares if its targeted system is public or private or how many layers of NAT are present. 
     As would be recognized by one of ordinary skill in the art, methods in accordance with the invention may be embodied in computer executable instructions and stored on a program storage device. While the invention has been disclosed with respect to a limited number of embodiments, numerous modifications and variations will be appreciated by those skilled in the art. It is intended that all such variations and modifications fall with in the scope of the following claims.

Metadata:
Filing Date: 20040202
Publication Date: 20111122
Grant Date: 20111122
Priority Date: 20040202
Inventors: ABUAN JOE
GRAESSLEY JOSHUA
JEONG HYEONKUK
TUNG BERKAT
Assignee: APPLE INC
CPC Classifications: [{"code": "H04L65/1069", "inventive": true, "first": true, "tree": "[]"}, {"code": "H04L67/104", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04L61/2589", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04L61/2564", "inventive": true, "first": true, "tree": "[]"}, {"code": "H04L61/2589", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04L61/2564", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04L67/104", "inventive": true, "first": false, "tree": "[]"}]
Family ID: 44936899