Peer-to-peer method of quality of service (QoS) probing and analysis and infrastructure employing same

• US 7,133,368 B2
• Filed: 02/01/2002
• Issued: 11/07/2006
• Est. Priority Date: 02/01/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Qian, Zhu, Wenwu, Zhang, XinYan, Xiong, YongQiang
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Sol, Anthony
• Application Number:
  US10/061,462
• Publication Number:
  US 20030152034A1
• Time in Patent Office: 1,740 Days
• Field of Search: 370/249, 370/252, 370/253
• US Class Current: 370/249
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 61/2567 for reachability, e.g. inquiring the address of a correspondent behind a NAT server

Abstract

A peer-to-peer (P2P) probing/network quality of service (QoS) analysis system utilizes a UDP-based probing tool for determining latency, bandwidth, and packet loss ratio between peers in a network. The probing tool enables network QoS probing between peers that connect through a network address translator. The list of peers to probe is provided by a connection server based on prior probe results and an estimate of the network condition. The list includes those peers which are predicted to have the best QoS with the requesting peer. Once the list is obtained, the requesting peer probes the actual QoS to each peer on the list, and returns these results to the connection server. P2P probing in parallel using a modified packet-pair scheme is utilized. If anomalous results are obtained, a hop-by-hop probing scheme is utilized to determine the QoS of each link. In such a scheme, differential destination measurement is utilized.

Claims

1. A method of probing quality of service parameters in a peer-to-peer network between at least a first peer and a second peer, comprising the steps of:

generating by the first peer a first and a second probing packet, each probing packet including a first timestamp;

sending the first probing packet and the second probing packet to the second peer, the first timestamp of each probing packet indicating a time at which that probing packet is sent;

receiving from the second peer a first acknowledgement packet and a second acknowledgement packet corresponding to the first probing packet and the second probing packet, each of said acknowledgement packets including the first timestamp of the probing packet to which the acknowledgement packet corresponds, a second timestamp indicating a time at which the correspanding probing packet arrived at the second peer, and a third timestamp indicating a time at which the acknowledgement packet was sent by the second peer; and

calculating quality of service parameters for the network as a function of the first timestamp, the second timestamp, and the third timestamp of both the first acknowledgement packet and the second acknowledgement packet;

wherein the step of generating the first probing packet and the second probing packet comprises the steps of generating the first probing packet of a first size, generating the second probing packet of a second size, and wherein the first size and the second size are equal;

wherein the step of calculating quality of service parameters for the network comprises the step of calculating bottleneck bandwidth for a first path from the first peer to the second peer as a function of the first size divided by the difference between the second timestamp of the first acknowledgement packet and the second timestamp of the second acknowledgement packet; and

wherein the steps of generating, sending, receiving, and calculating bottleneck bandwidth are repeated approximately 20 times, further comprising the step of filtering out pairs of acknowledgement packets that are interlaced with other packets.

2. The method of claim 1, further comprising the step of overcoming time compression and extension of the acknowledgement packets by utilizing a kernel density estimator over a whole range of the bottleneck bandwidth results.

3. The method of claim 1, wherein the step of receiving the first acknowledgement packet and the second acknowledgement packet comprises the step of receiving the first acknowledgement packet having a third size and the second acknowledgement packet having a fourth size, and wherein the third size and the fourth size are equal.

4. The method of claim 1, further comprising the step of recording a fourth timestamp indicating a time when the first acknowledgement packet is received and a fifth timestamp indicating a time when the second acknowledgement packet is received, and wherein the step of calculating quality of service parameters for the network comprises the step of calculating bottleneck bandwidth for a second path from the second peer to the first peer as a function of the third size divided by the difference between the fourth timestamp and the fifth timestamp.

5. The method of claim 1, further comprising the step of recording a fourth timestamp indicating a time when the first acknowledgement packet is received and a fifth timestamp indicating a time when the second acknowledgement packet is received, and wherein the step of calculating quality of service parameters for the network comprises the step of calculating a first end-to-end delay between the first peer to the second peer as a function of the first timestamp of the first acknowledgement packet, the second timestamp of the first acknowledgement packet, the third timestamp of the first acknowledgement packet, and the fourth timestamp.

6. The method of claim 5, wherein the step of calculating quality of service parameters for the network comprises the step of calculating a second end-to-end delay between the first peer to the second peer as a function of the first timestamp of the second acknowledgement packet, the second timestamp of the second acknowledgement packet, the third timestamp of the second acknowledgement packet, and the fifth timestamp.

7. The method of claim 1, further comprising the step of recording a fourth timestamp indicating a time when the first acknowledgement packet is received, and wherein the step of calculating quality of service parameters for the network comprises the step of calculating a first round trip time between the first peer and the second peer as a difference between the first timestamp and the fourth timestamp, less a difference between the third timestamp and the second timestamp, all of the first acknowledgement packet.

8. The method of claim 7, wherein the steps of generating, sending, receiving, and calculating a first round trip time are repeated approximately 20 times, further comprising the step of determining a median of the 20 first round trip times to represent a first measured round trip time.

9. The method of claim 7, further comprising the step of recording a fifth timestamp indicating a time when the second acknowledge packet is received, and wherein the step of calculating quality of service parameters for the network comprises the step of calculating a second round trip time between the first peer and the second peer as a difference between the first timestamp and the fifth timestamp, less a difference between the third timestamp and the second timestamp, all of the second acknowledgement packet.

10. The method of claim 9, wherein the steps of generating, sending, receiving, and calculating a second round trip time are repeated approximately 20 times, further comprising the step of determining a median of the 20 second round trip times to represent a second measured round trip time.

11. The method of claim 1, wherein the step of sending the first probing packet and the second probing packet to the second peer comprises the step of sending the first probing packet and the second probing packet back to back.

12. The method of claim 1, wherein the step of sending the first probing packet and the second probing packet to the second peer comprises the step of sending the first probing packet and the second probing packet as a probing packet pair.

13. The method of claim 1, wherein the step of generating the first probing packet and the second probing packet comprises the step of generating the first probing packet and the second probing packet of a size approximately equal to 200 bytes.

14. The method of claim 1, wherein the step of sending probing packet pairs comprises the step of determining the interval between the probing packet pairs when the access bandwidth is large enough.

15. The method of claim 1 wherein the second peer connects to the network through a network address translator, and wherein the step of generating comprises generating a first UDP-based probing packet and a second UDP-based probing packet.

16. The method of claim 1, wherein the network includes at least one connection server, the connection server having contact information for at least the second peer, the method further comprising the steps of:

establishing a connection to the connection server;

requesting peer contact list information from the connection server;

receiving the peer contact list information; and

maintaining the connection open to the connection server.

17. The method of claim 16, further comprising the steps of measuring a first latency between the first peer and the connection server, and transmitting information of the first latency to the connection server.

18. The method of claim 17, wherein the first peer connects to the network through a network address translator, the method further comprising the steps of measuring a second latency between the first peer and the network address translator, and transmitting information of the second latency to the connection server.

19. The method of claim 16, further comprising the step of registering a port for quality of service probing with the connection server.

20. The method of claim 16, further comprising the step of transmitting the quality of service parameters to the connection server.

21. The method of claim 1, further comprising the step of receiving a probing packet from a peer, and immediately responding to the probing packet.

22. The method of claim 21, wherein the step of immediately responding to the probing packet comprises the steps of recording a sixth timestamp corresponding to a time of receipt of the probing packet, forming an acknowledgement packet including the sixth timestamp and a seventh timestamp therein, sending the acknowledgement packet to the peer, the seventh timestamp corresponding to a time the acknowledgement packet is sent.

23. The method of claim 21 wherein the network contains at least one connection server, further comprising the step of registering receipt of the probing packet from the peer with the connection server.

24. The method of claim 1, wherein at least one of the step of receiving fails and the step of calculating provides anomaly results, the method further comprising the step of generating a packet train having four packets therein, the four packets including a first large packet having a time to live set to (1, . . . , n−

1) followed by a first small packet followed by a first delay followed by a second large packet having a time to live set to (2, . . . , n) followed by a second small packet, transmitting the packet train to the second peer, receiving ICMP time-exceeded error messages from intermediate nodes in a path to the second peer, and inferring link characteristics based on differential destination measurements (DDM).

25. The method of claim 24, wherein the first and second large packets are sized to be as large as possible without fragmenting, and wherein the first and second small packets are set to be as small as possible.

26. The method of claim 24, wherein the first and second large packets are sized to be approximately 1500 bytes, and wherein the first and second small packets are sized to be approximately 40 bytes.

27. The method of claim 24, wherein the steps of generating and transmitting the packet train are repeated for each link in a path from the first peer to the second peer, and wherein the step of inferring link characteristics comprises the step of inferring link bandwidth for each link along the path from the first peer to the second peer.

28. A method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers; and

further comprising the step of receiving a probing request from a peer, and immediately responding to the probing request; and

further comprising the step of registering receipt of the probing request from the peer with the connection server;

wherein the step of probing the plurality of peers comprises the steps of;

generating a probing packet pair;

transmitting the probing packet pair to each of the peers in parallel; and

recording a first and a second timestamp corresponding to a time when each packet in the probing packet pair were transmitted.

29. A method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers;

wherein the step of probing the plurality of peers comprises the steps of;

generating a probing packet pair;

transmitting the probing packet pair to each of the peers in parallel; and

recording a first and a second timestamp corresponding to a time when each packet in the probing packet pair were transmitted.

30. The method of claim 29, further comprising the step of transmitting the quality of service parameters for each of the plurality of peer to the connection server.

31. The method of claim 29, further comprising the steps of measuring a first latency to the connection server, and transmitting the first latency to the connection server.

32. The method of claim 31, wherein the step of establishing a connection to the connection server comprises the step of establishing a connection to the connection server through a network address translator, further comprising the steps of measuring a second latency to the network address translator, and transmitting the second latency to the connection server.

33. The method of claim 29, further comprising the step of registering a port for quality of service probing with the connection server.

34. The method of claim 29, further comprising the step of communicating to the connection server a desire to be a game server.

35. The method of claim 29, further comprising the step of receiving a probing request from a peer, and immediately responding to the probing request.

36. The method of claim 35, wherein the step of immediately responding to the probing request comprises the steps of recording a first timestamp corresponding to a time of receipt of the probing request, forming an acknowledgement packet including the first timestamp and a second timestamp therein, sending the acknowledgement packet to the peer, the second timestamp corresponding to a time the acknowledgement packet is sent to the peer.

37. The method of claim 29, wherein the step of determining the quality of service parameters comprises the steps of:

receiving a probing acknowledgement pair from at least one of the peers, the probing acknowledgement pair including a third and a fourth timestamp corresponding to a time of receipt of each of the packets in the probing packet pair, and a fifth and a sixth timestamp corresponding to a time of transmission of each of the packets in the probing acknowledgement pair;

recording a seventh and an eighth timestamp corresponding to a time of receipt of each of the packets in the probing acknowledgement pair; and

calculating the quality of service parameters as a function of a size of the packets in the probing packet pair and in the probing acknowledgement pair and of the first, second, third, fourth, fifth, sixth, seventh, and eighth timestamps.

38. The method of claim 37, wherein the step of calculating the quality of service parameters as a function of the size of the packets in the probing packet pair and in the probing acknowledgement pair and of the first, second, third, fourth, fifth, sixth, seventh, and eighth timestamps comprises the steps of calculating a forward bottleneck bandwidth as a function of the size of the packets in the probing pair divided by the difference between the third and fourth timestamps, and calculating a reverse bottleneck bandwidth as a function of the size of the packets in the probing acknowledge pair divided by the difference between the seventh and eighth timestamps.

39. The method of claim 38, wherein the step of probing, and calculating the forward bottleneck bandwidth, and calculating the reverse bottleneck bandwidth are repeated a plurality of times, further comprising the step of filtering out probing acknowledgement pairs that are interlaced with other packets.

40. The method of claim 39, further comprising the step of overcoming time compression and extension of the packets in the probing acknowledgement pairs by utilizing a kernel density estimator over a whole range of the bottleneck bandwidth results.

41. The method of claim 37, wherein the step of calculating the quality of service parameters as a function of the size of the packets in the probing packet pair and in the probing acknowledgement pair and of the first, second, third, fourth, fifth, sixth, seventh, and eighth timestamps comprises the steps of calculating a first round trip time (RTT) as a function of a difference between the second and the eighth timestamps less a difference between the fourth and the sixth timestamps.

42. The method of claim 41, wherein the step of probing, calculating the first RTT, and calculating the second RTT are repeated a plurality of times, further comprising the step of determining a median of the plurality of first and second RTTs to represent a measured RTT of the network.

43. The method of claim 29, wherein the step of generating the probing packet pair comprises the step of generating a first UDP-based packet and a second UDP-based packet to form the probing packet pair.

44. The method of claim 29, wherein the step of transmitting probing packet pairs comprises the step of determining the interval between the probing packet pairs utilizing a Poisson distribution to describe the interval between each packet-pair of a certain peer, recognizing that different peers may have different arrival rates.

45. A method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers;

wherein the step of probing the plurality of peers is unsuccessful for at least one peer, further comprising the step of analyzing hop-by-hop characteristics for a path to the at least one peer for which the step of probing is unsuccessful.

46. The method of claim 45, wherein the step of analyzing hop-by-hop characteristics comprises the steps of generating a UDP-based probing packet train for each link in the path, each probing packet train having a first largest possible non-fragmented packet followed by a first smallest possible packet followed by a first delay followed by a second largest possible non-fragmented packet followed by a second smallest possible packet, transmitting each probing packet train to the at least one peer, and inferring link characteristics for each hop in the path by differential destination measurement (DDM).

47. A computer-readable medium having computer-executable instructions for performing steps comprising:

generating a first and a second probing packet, each probing packet including a first timestamp;

sending the first probing packet and the second probing packet to a peer, the first timestamp of each probing packet indicating a time at which that probing packet is sent;

receiving from the peer a first acknowledgement packet and a second acknowledgement packet corresponding to the first probing packet and the second probing packet, each of said acknowledgement packets including the first timestamp of the probing packet to which the acknowledgement packet corresponds, a second timestamp indicating a time at which the corresponding probing packet arrived at the peer, and a third timestamp indicating a time at which the acknowledgement packet was sent by the peer; and

calculating quality of service parameters for the network as a function of the first timestamp, the second timestamp, and the third timestamp of both the first acknowledgement packet and the second acknowledgement packet;

wherein the step of generating the first probing packet and the second probing packet comprises the steps of generating the first probing packet of a first size, generating the second probing packet of a second size, and wherein the first size and the second size are equal;

wherein the step of calculating quality of service parameters for the network comprises the step of calculating bottleneck bandwidth for a first path to the peer as a function of the first size divided by the difference between the second timestamp of the first acknowledgement packet and the second timestamp of the second acknowledgement packet; and

wherein the steps of generating, sending, receiving, and calculating bottleneck bandwidth are repeated approximately 20 times, further comprising the step of filtering out pairs of acknowledgement packets that are interlaced with other packets.

48. A computer-readable medium having computer-executable instructions for performing a method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, the method comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers; and

further comprising the step of receiving a probing request from a peer, and immediately responding to the probing request; and

further comprising the step of registering receipt of the probing request from the peer with the connection server;

wherein the step of probing the plurality of peers comprises the steps of;

generating a probing packet pair;

transmitting the probing packet pair to each of the peers in parallel; and

recording a first and a second timestamp corresponding to a time when each packet in the probing packet pair were transmitted.

49. A computer-readable medium having computer-executable instructions for performing a method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, the method comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers;

wherein the step of probing the plurality of peers comprises the steps of;

generating a probing packet pair;

transmitting the probing packet pair to each of the peers in parallel; and

recording a first and a second timestamp corresponding to a time when each packet in the probing packet pair were transmitted.

50. A computer-readable medium having computer-executable instructions for performing a method of establishing a network session with one of a plurality of peers which provides the best quality of service, the network including at least one connection server, the method comprising the steps of:

establishing a connection to the connection server;

requesting peer contact information from the connection server;

receiving the peer contact information from the connection server, the peer contact information containing contact information for a plurality of peers;

probing the plurality of peers;

determining quality of service parameters for each of the plurality of peers;

selecting one of the peers which has the best quality of service; and

establishing a peering session with the one of the peers;

wherein the step of probing the plurality of peers is unsuccessful for at least one peer, further comprising the step of analyzing hop-by-hop characteristics for a path to the at least one peer for which the step of probing is unsuccessful.