Using signals extracted from a VOIP data stream to distinguish between network congestion and link losses

• US 10,462,078 B2
• Filed: 11/17/2017
• Issued: 10/29/2019
• Est. Priority Date: 11/17/2017
• Status: Active Grant

• Current Assignee: WhatsApp LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Original Assignee: WhatsApp LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Gong, Jun, Singh, Manpreet
• Primary Examiner(s): Rutkowski, Jeffrey M
• Assistant Examiner(s): Tacdiran, Andre
• Application Number:
  US15/817,048
• Publication Number:
  US 20190158437A1
• Time in Patent Office: 711 Days
• Field of Search: None
• CPC Class Codes: H04L 12/1813 for computer conferences, e.g. chat rooms instant messaging H04L51/04; protocols for multimedia communication H04L65/1101; arrangements for multi-party communication H04L65/403; telephonic conference arrangements H04M3/56; television conference systems H04N7/15
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 51/04 Real-time or near real-time messaging, e.g. instant messaging [IM]
• CPC Class Codes: H04W 28/0242 Determining whether packet losses are due to overload or to deterioration of radio communication conditions
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

Two (or more) client devices engage in a chat session. Packets associated with the chat session are numbered using a predetermined pattern. When the packets are received, the receiving client device extracts signals from the packet metadata to determine whether the primary cause of packet loss during transit is network congestion or link losses. Based on the extracted signals, the receiving device sends a control message back to the other client device indicating how one or more chat parameters should be updated. On receiving the control message, the other client device updates the chat parameters accordingly.

Claims

1. A method comprising:

receiving packets from a sending client device via a network, wherein each of the received packets includes chat content data and metadata for a chat session, the metadata including a timestamp indicating when the received packet was sent;

determining one or more network performance signals from the metadata of the received packets, the one or more network performance signals distinguishing between a scenario where a network problem arises from congestion and a scenario where the network problem arises from link loss, wherein the one or more network performance signals include a moving average signal, determining the moving average signal comprising;

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

calculating a long-term ROTT average, the long-term ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer greater than one;

calculating a short-term ROTT average, the short-term ROTT average being an average of the ROTT for the last m packets received, where m is a positive integer less than n; and

calculating a difference between the long-term ROTT average and the short-term ROTT average, wherein the difference exceeding a threshold indicates the network problem arose from network congestion;

selecting, based on the moving average signal, between attributing the network problem to network congestion and attributing the network problem to link loss;

determining a control message to send based on whether the network problem is attributed to network congestion or link loss, the control message indicating how a parameter of the chat session should be updated to address the network problem, wherein, responsive to attributing the network problem to network congestion, the control message indicates that a bitrate of the chat session should be reduced; and

sending the control message to the sending client device.

2. The method of claim 1, wherein, responsive to attributing the network problem to link loss, the control message indicates packet redundancy should be increased.

3. The method of claim 1, wherein determining the one or more network performance signals includes determining a packet loss gap signal, determining the packet loss gap signal comprising:

determining one or more groups of missing packets; and

calculating a moving average of the number of packets in the one or more groups, the moving average being below a threshold indicating the network problem arose due to link loss,

wherein the moving average being below the threshold indicates that the network problem is due to link loss.

4. The method of claim 1, further comprising detecting the network problem, detecting the network problem including:

determining a number of packets lost in a given time period; and

determining the network problem is present responsive to the number of packets lost exceeding a packet loss threshold,

wherein the control message is sent responsive to determining the network problem is present.

5. The method of claim 1, further comprising:

receiving additional packets, wherein each of the additional received packets includes a corresponding timestamp indicating when the additional received packet was sent;

calculating a relative one-way trip time (ROTT) for each additional received packet by comparing the corresponding timestamp to a time at which the additional received packet was received;

calculating an updated long-term ROTT average, the updated long-term ROTT average being an average of the ROTT for the last n packets received, the last n packets received including the additional packets;

calculating an updated short-term ROTT average, the updated short-term ROTT average being an average of the ROTT for the last m packets received, the last m packets received including the additional packets; and

comparing the updated long-term ROTT average and the updated short-term ROTT average, wherein the updated short-term ROTT average being below the updated long-term ROTT average indicates the network has transitioned to an uncongested state.

6. The method of claim 1, wherein determining the one or more network performance signals includes determining an overall latency signal, determining the overall latency signal comprising:

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

identifying a global minimum ROTT as a lowest ROTT of any of the received packets;

identifying a global maximum ROTT as a highest ROTT of any of the received packets;

calculating a current ROTT average, the current ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer; and

comparing the current ROTT average to a danger threshold between the global minimum and global maximum, wherein the current ROTT average exceeding the danger threshold indicates network congestion.

7. The method of claim 6, further comprising setting the danger threshold at a given percentage of a range between the global minimum and the global maximum, and wherein, responsive to the current ROTT average being above the danger threshold, the control message includes an indication that the bitrate of the chat session should be decreased.

8. The method of claim 6, wherein comparing the current ROTT average to the global minimum and global maximum comprises comparing the current ROTT average to a caution threshold between the danger threshold and the global minimum, and wherein, responsive to the current ROTT average being below the caution threshold, the control message includes an indication that the bitrate of the chat session can be increased.

9. A non-transitory computer-readable medium storing computer program instructions executable by a processor to perform operations comprising:

receiving packets from a sending client device via a network, wherein each of the received packets includes chat content data and metadata for a chat session, the metadata including a timestamp indicating when the received packet was sent;

determining one or more network performance signals from the metadata of the received packets, the one or more network performance signals distinguishing between a scenario where a network problem arises from congestion and a scenario where the network problem arises from link loss, wherein the one or more network performance signals include a moving average signal, determining the moving average signal comprising;

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

calculating a long-term ROTT average, the long-term ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer greater than one;

calculating a short-term ROTT average, the short-term ROTT average being an average of the ROTT for the last m packets received, where m is a positive integer less than n; and

calculating a difference between the long-term ROTT average and the short-term ROTT average, wherein the difference exceeding a threshold indicates the network problem arose from network congestion;

selecting, based on the moving average signal, between attributing the network problem to network congestion and attributing the network problem to link loss;

determining a control message to send based on whether the network problem is attributed to network congestion or link loss, the control message indicating how a parameter of the chat session should be updated to address the network problem, wherein, responsive to attributing the network problem to network congestion, the control message indicates that a bitrate of the chat session should be reduced; and

sending the control message to the sending client device.

10. The non-transitory computer-readable medium of claim 9, further comprising receiving additional packets from the sending client device, the additional packets including additional chat content data and additional metadata for the chat session, wherein the sending client device sent the additional packets after updating the parameter of the chat session based on the control message.

11. The non-transitory computer-readable medium of claim 9, wherein determining the one or more network performance signals includes determining a packet loss gap signal, determining the packet loss gap signal comprising:

determining one or more groups of missing packets; and

calculating a moving average of the number of packets in the one or more groups, the moving average being below a threshold indicating the network problem arose due to link loss,

wherein the moving average being below the threshold indicates that the network problem is due to link loss.

12. The non-transitory computer-readable medium of claim 9, wherein the operations further comprise detecting the network problem, detecting the network problem including:

determining a number of packets lost in a given time period; and

determining the network problem is present responsive to the number of packets lost exceeding a packet loss threshold,

wherein the control message is sent responsive to determining the network problem is present.

13. The non-transitory computer-readable medium of claim 12, wherein the computer-readable storage medium further contains computer program instructions for:

receiving additional packets, each of the additional received packets including a corresponding timestamp indicating when the additional received packet was sent;

calculating a relative one-way trip time (ROTT) for each additional received packet by comparing the corresponding timestamp to a time at which the additional received packet was received;

calculating an updated long-term ROTT average, the updated long-term ROTT average being an average of the ROTT for the last n packets received, the last n packets received including the additional packets;

calculating an updated short-term ROTT average, the updated short-term ROTT average being an average of the ROTT for the last m packets received, the last m packets received including the additional packets; and

comparing the updated long-term ROTT average and the updated short-term ROTT average, wherein the updated short-term ROTT average being below the updated long-term ROTT average indicates the network has transitioned to an uncongested state.

14. The non-transitory computer-readable medium of claim 9, wherein determining the one or more network performance signals includes determining an overall latency signal, determining the overall latency signal comprising:

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

identifying a global minimum ROTT as a lowest ROTT of any of the received packets;

identifying a global maximum ROTT as a highest ROTT of any of the received packets;

calculating a current ROTT average, the current ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer; and

comparing the current ROTT average to a danger threshold between the global minimum and global maximum, wherein the current ROTT average exceeding the danger threshold indicates network congestion.

15. The non-transitory computer-readable medium of claim 14, wherein the operations further comprise setting the danger threshold at a given percentage of a range between the global minimum and the global maximum, and wherein, responsive to the current ROTT average being above the danger threshold, the control message includes an indication that the bitrate of the chat session should be decreased.

16. The non-transitory computer-readable medium of claim 14, wherein comparing the current ROTT average to the global minimum and global maximum comprises comparing the current ROTT average to a caution threshold between the danger threshold and the global minimum, and wherein, responsive to the current ROTT average being below the caution threshold, the control message includes an indication that the bitrate of the chat session can be increased.

17. A computer system comprising:

one or more processors; and

one or more computer readable media storing computer program instructions that, when executed, cause the one or more processors to perform operations including;

receiving packets from a sending client device via a network, wherein each of the received packets includes chat content data and metadata for a chat session, the metadata including a timestamp indicating when the received packet was sent;

determining one or more network performance signals from the metadata of the received packets, the one or more network performance signals distinguishing between a scenario where a network problem arises from congestion and a scenario where the network problem arises from link loss, wherein the one or more network performance signals include a moving average signal, determining the moving average signal comprising;

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

calculating a long-term ROTT average, the long-term ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer greater than one;

calculating a short-term ROTT average, the short-term ROTT average being an average of the ROTT for the last m packets received, where m is a positive integer less than n; and

calculating a difference between the long-term ROTT average and the short-term ROTT average, wherein the difference exceeding a threshold indicates the network problem arose from network congestion;

selecting, based on the moving average signal, between attributing the network problem to network congestion and attributing the network problem to link loss;

determining a control message to send based on whether the network problem is attributed to network congestion or link loss, the control message indicating how a parameter of the chat session should be updated to address the network problem, wherein, responsive to attributing the network problem to network congestion, the control message indicates that a bitrate of the chat session should be reduced; and

sending the control message to the sending client device.

18. The computer system of claim 17, wherein determining the one or more network performance signals includes determining a packet loss gap signal, determining the packet loss gap signal comprising:

determining one or more groups of missing packets; and

calculating a moving average of the number of packets in the one or more groups, the moving average being below a threshold indicating the network problem arose due to link loss,

wherein, the moving average being below the threshold indicates that the network problem is due to link loss.

19. The computer system of claim 17, wherein the operations further include detecting the network problem, detecting the network problem including:

determining a number of packets lost in a given time period; and

determining the network problem is present responsive to the number of packets lost exceeding a packet loss threshold,

wherein the control message is sent responsive to determining the network problem is present.

20. The computer system of claim 17, wherein determining the one or more network performance signals includes determining an overall latency signal, determining the overall latency signal comprising:

calculating a relative one-way trip time (ROTT) for each received packet by comparing the timestamp to a time at which the received packet was received;

identifying a global minimum ROTT as a lowest ROTT of any of the received packets;

identifying a global maximum ROTT as a highest ROTT of any of the received packets;

calculating a current ROTT average, the current ROTT average being an average of the ROTT for the last n packets received, where n is a positive integer; and

comparing the current ROTT average to the global minimum and global maximum, the comparing comprising;

comparing the current ROTT average to a caution threshold between the global minimum and the global maximum, wherein the control message includes an indication that the bitrate of the chat session should be increased responsive to the current ROTT average being below the caution threshold; and

comparing the current ROTT average to a warning threshold between the caution threshold and the global maximum, and wherein, responsive to the current ROTT average being above the warning threshold, the control message includes an indication that the bitrate of the chat session should be decreased.