MINIMIZING NETWORK LATENCY IN INTERACTIVE INTERNET APPLICATIONS

• US 20120128010A1
• Filed: 11/22/2010
• Published: 05/24/2012
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huang, Cheng, Li, Jin, Mehrotra, Sanjeev, Chou, Philip A., Livni, Felix, Chen, Hao, Thaler, Jay, Ross, Keith W., Zhang, Chao
• Granted Patent: US 9,059,817 B2
• Time in Patent Office: Days
• US Class Current: 370/468
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/1812 Hybrid protocols; Hybrid automatic repeat request [HARQ]
• CPC Class Codes: H04L 1/188 Time-out mechanisms

Abstract

A method and system that enhances a user'"'"'s performance while interacting with an interactive internet application such as a Massively Multiplayer Online (MMO) game is provided. The network latency experienced by users participating in the MMO game is minimized by dynamically determining an optimal transmission action for a message generated by the MMO game. In one embodiment, determining the optimal transmission action for a message includes dynamically determining the optimal number of redundant Forward Error Correction (FEC) packets to add to a message prior to transmitting a message to a receiving device. The optimal number of FEC packets is determined based on a wide range of varying network conditions.

Claims

1. A method comprising:

receiving an input message to be transmitted to a receiving device, wherein the input message includes one or more information packets;

dynamically and automatically determining an optimal transmission action for the input message based on monitoring one or more network performance parameters in real-time and based on the one or more information packets in the input message, wherein determining the optimal transmission action comprises;

determining an optimal number of forward error correction packets to add to the input message prior to and during transmission of the input message to the receiving device;

generating the forward error correction packets;

creating an output message for transmission to the receiving device, wherein the output message includes the one or more information packets and the optimal number of forward error correction packets;

transmitting the output message to the receiving device; and

receiving a reply message from the receiving device.

2. The method of claim 1, wherein the one or more network performance parameters comprise one or more of a round trip time (RTT), a network latency, and a packet loss probability of a message transmitted between one or more client devices and a centralized data server.

3. The method of claim 1, wherein determining the optimal transmission action for the input message further comprises:

identifying one or more states associated with the input message and determining one or more possibilities of loss patterns for the one or more states of the input message, wherein each state identifies the number of information packets to be transmitted in the input message during a particular transmission stage associated with the input message; and

representing the one or more states and the one or more possibilities of loss patterns of the input message in a Markov Decision Process (MDP) framework.

4. The method of claim 1, wherein the steps of determining the optimal transmission action for the input message, generating the one or more forward error correction packets, creating the output message and receiving a reply message is performed iteratively for different states of the input message until the input message is delivered at the receiving device or until a network threshold latency has been reached.

5. The method of claim 4, wherein determining the optimal transmission action further comprises:

determining an optimal transmission action for each state of the input message, comprising;

determining the packet loss probability of each path leaving each state of the input message, wherein the packet loss probability of each path is calculated as a compound probability of the loss patterns along each path;

determining the transmission cost of delivery of the input message along each path;

determining an aggregated cost of transmission along each path; and

comparing the aggregated cost of transmission across each path to determine the optimal transmission action for a state of the input message, wherein the optimal transmission action minimizes the transmission cost and network latency associated with transmitting the input message, subject to the constraint that a probability of non-arrival of the input message along a path is below a threshold value.

6. The method of claim 5, wherein determining the optimal transmission action further comprises:

defining a combined objective function for the input message as a weighted sum of a failure probability and a transmission cost associated with transmitting the input message, utilizing a Lagrangian multiplier λ

.

7. The method of claim 6, wherein determining the optimal transmission action further comprises:

varying the Lagrangian multiplier λ

using bi-section search to determine the optimal transmission action for the input message.

8. The method of claim 1, wherein dynamically and automatically determining the optimal transmission action for the input message further comprises:

creating one or more look-up tables to store the optimal transmission action determined for the input message in real-time, wherein each look-up table stores the optimal transmission action for the input message for a given state of the input message, a packet loss probability of the input message, a transmission stage of the input message and the number of remaining transmission stages of the input message; and

dynamically choosing the optimal transmission action for the input message during online execution utilizing the one or more look-up tables.

9. The method of claim 1, wherein dynamically and automatically determining the optimal transmission action for the input message further comprises:

creating one or more look-up tables to store the optimal transmission action determined for the input message offline, wherein each look-up table stores the optimal transmission action for the input message for a given state of the input message, a packet loss probability of the input message, a transmission stage of the input message and the remaining transmission stages of the input message; and

dynamically choosing the optimal transmission action for the input message during online execution utilizing the one or more look-up tables.

10. The method of claim 1, wherein the optimal transmission action minimizes transmission cost and network latency associated with transmitting the input message between one or more client devices and a centralized data server.

11. The method of claim 1, wherein determining the optimal transmission action for the input message further comprises:

determining the packet loss probability of each path leaving each state of the input message, utilizing an MDP framework, wherein the packet loss probability of each path is calculated as a compound probability of the loss patterns along each path; and

determining the transmission cost of delivery of the input message along each path;

determining an aggregated cost of transmission along each path;

comparing the aggregated cost of transmission across each path to determine the optimal transmission action for a state of the input message;

defining a combined objective function for the input message as a weighted sum of a failure probability and the transmission cost associated with transmitting the input message, utilizing a Lagrangian multiplier λ

; and

varying the Lagrangian multiplier λ

using bi-section search to determine the optimal transmission action for the input message, wherein the optimal transmission action minimizes the transmission cost and network latency associated with transmitting the input message, subject to the constraint that a probability of non-arrival of the input message along a path is below a threshold value.

12. One or more processor readable storage devices having processor readable code embodied on said one or more processor readable storage devices, the processor readable code for programming one or more processors to perform a method comprising:

sending a group of input messages generated by an interactive internet application to a receiving device;

obtaining one or more network performance parameters associated with the group of input messages;

determining a transmission budget for the group of input messages during a transmission stage associated with the group of input messages;

identifying one or more states associated with each message in the group of input messages;

determining one or more possibilities of loss patterns for the one or more states associated with each message in the group of input messages;

determining an optimal transmission action for each message in the group of input messages based on the one or more network performance parameters, the one or more states and the one or more possibilities of loss patterns, wherein the optimal transmission action minimizes a transmission cost and network latency associated with transmitting each of the messages in the group of input messages to a receiving device;

creating a group of output messages for transmission to the receiving device based on the optimal transmission action determined for each message in the group of input messages;

transmitting the group of output messages to the receiving device; and

receiving one or more reply messages from the receiving device.

13. One or more processor readable storage devices according to claim 12, wherein determining the optimal transmission action for each message in the group of input messages further comprises:

allocating the transmission budget among the group of input messages such that the total transmission cost of delivering each message in the group of input messages is minimized.

14. One or more processor readable storage devices according to claim 12, wherein the one or more network performance parameters comprise one or more of a round trip time (RTT), a network latency, and a packet loss probability of a message transmitted to a receiving device.

15. One or more processor readable storage devices according to claim 12, wherein determining the optimal transmission action further comprises:

representing the one or more states and the one or more possibilities of loss patterns of each message in the group of input messages in a Markov Decision Process (MDP) framework.

16. One or more processor readable storage devices according to claim 12, wherein determining the optimal transmission action further comprises:

dynamically determining the optimal number of redundant Forward Error Correction (FEC) packets to add to each message in the group of input messages prior to and during transmission of the group of messages, based on the one or more network performance parameters.

17. One or more processor readable storage devices according to claim 12, further comprising storing the optimal transmission action for the group of input messages in one or more look-up tables, wherein each look-up table stores an optimal transmission action for the group of input messages, for a given state of each message in the group of input messages, a packet loss probability of the group of input messages and a transmission stage of the group of input messages.

18. A system comprising:

one or more client devices in communication with a centralized data server via a communications network;

one or more applications hosted on the one or more client devices and the centralized data server, wherein the one or more applications generate one or more messages that include a sequence of one or more information packets; and

an intelligent adaptive decision making engine hosted on the one or more client devices and the centralized data server that determines an optimal transmission action for the one or more messages generated by the one or more applications, wherein the optimal transmission action includes the optimal number of forward error correction (FEC) packets to add to the one or more messages prior to and during transmission of the one or more messages between the one or more client devices and the centralized data server.

19. The system of claim 18, wherein the optimal transmission action minimizes a transmission cost and network latency associated with transmitting the one or more messages between the one or more client devices and the centralized data server.

20. The system of claim 18, wherein the one or more applications comprise one or more interactive internet applications, wherein the one or more interactive internet applications include a Massively Multiplayer Online (MMO) game.