Selectively ordered protocol for unreliable channels

• US 20070086343A1
• Filed: 10/14/2005
• Published: 04/19/2007
• Est. Priority Date: 10/14/2005
• Status: Active Grant

• Current Assignee: Turbine Incorporated (Warner Bros. Discovery, Inc.)
• Original Assignee: Turbine Incorporated (Warner Bros. Discovery, Inc.)
• Inventors: Berkebile, Todd, Kujawa, Michael
• Granted Patent: US 8,284,663 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 67/131 Protocols for games, networked simulations or virtual reality
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol

Abstract

A communication protocol provides a selective ordering of packets such that some sequences of packets on the channel are guaranteed not to be delivered out of order, while other packets on the same channel may be delivered before earlier sent packets are received, thereby preempting their delivery. The communication protocol can be implemented using UDP over IP. The protocol may be used for exchange of information in a distributed multi-player game.

Claims

1. A method for communication over a data network comprising:

receiving a plurality of messages over the data network, each message being associated with sequencing data, the sequencing data for a message including a first index and a second index;

enforcing delivery order for at least some of the received messages according to the first index of the received messages; and

discarding without delivery at least some of the received messages according to the second index of the received messages.

2. The method of claim 1 further comprising:

accepting the plurality of messages at a source on the data network for transmission over the data network;

transmitting the messages over the data network from the source to a destination; and

for at least some messages not successfully received at the destination, discarding at least a portion of the messages at the source according to the sequencing data of the messages and sequencing data of other messages transmitted to the destination.

3. The method of claim 1 wherein each received message includes the sequencing data associated with that messages.

4. The method of claim 1 wherein the sequencing data for a message further includes a channel identifier.

5. The method of claim 4 wherein enforcing the delivery order of messages and discarding messages is performed separately for messages with different channel identifiers.

6. The method of claim 1 wherein receiving the messages over the data network includes receiving said messages using a reliable datagram service.

7. The method of claim 6 wherein the reliable datagram service make use of a User Datagram Protocol (UDP).

8. The method of claim 6 wherein receiving the messages using the reliable datagram service includes receiving at least some retransmissions of datagrams.

9. The method of claim 8 wherein receiving retransmission of datagrams includes receiving retransmitted datagram header information without retransmission of corresponding payload data.

10. Software stored on computer-readable media comprising instructions for causing a computing system to:

receive a plurality of messages over a data network, each message being associated with sequencing data, the sequencing data for a message including a first index and a second index;

enforce delivery order for at least some of the received messages according to the first index of the received messages; and

discard without delivery at least some of the received messages according to the second index of the received messages.

11. A communication system comprising:

a plurality of packet communication services; and

a protocol service;

wherein each packet communication service is configured to receive data packets from a source over a data network, the data packets carrying a plurality of messages, each message being associated with sequencing data, the sequencing data for a message including a first index and a second index; and

wherein the protocol engine is configured to accept the messages from the datagram services and enforce delivery order for at least some of the received messages according to the first index of the received messages, and discard without delivery at least some of the received messages according to the second index of the received messages.

12. A method for communication over a data network comprising:

accepting a plurality of messages at a source on a data network, each message being associated with sequencing data, the sequencing data for a message including a first index and a second index;

transmitting the messages over the data network from the source to a destination, the first index of the transmitted message being for ordering the messages at the destination; and

for at least some messages not successfully received at the destination, discarding at least a portion of the not successfully received messages at the source according to the second index of the sequencing data of the not successfully received messages and of other messages transmitted to the destination.

13. The method of claim 12 wherein each of the accepted messages includes a channel identifier and the sequencing data.

14. The method of claim 13 further comprising determining the destination according to the channel identifier.

15. A method for communicating in a distributed game system comprising:

at a server system, maintaining information associated with a plurality of entities in an environment; and

maintaining communication sessions between the server system and a plurality of client system for exchanging information associated with the entities between the server system and a plurality of client systems, wherein each communication session uses a communication protocol that supports both reliable transmission of ordered messages and transmission and selective discarding of ephemeral messages.

16. The method of claim 15 wherein the server system is hosted on a plurality of server computers, and each of the communication session is associated with a channel identifier that is independent of which of the server computers is handling the communication session.

17. The method of claim 16 further comprising migrating at least some of the communication sessions among the server computers.

18. The method of claim 15 further comprising:

for each of the entities in the environment, maintaining a data structure that include data identifying client systems to which information associated with the entity is to be sent.

19. The method of claim 18 wherein the data structure for each of the entities includes communication sequencing data associated with each of the client systems to which the information is to be sent.

20. The method of claim 18 further comprising:

receiving information associated with one of the entities from a client system; and

forwarding the received information to the client systems identified in the data structure for that entity.

21. The method of claim 18 wherein the server system is hosted on a plurality of server computers, and each of the entities is hosted on one of the server computer, and wherein maintaining the data structure for an entity includes maintaining the data structure on the server computer hosting the entity.

22. The method of claim 21 further comprising migrating an entity from being hosted on one of the server computers to an other of the server computers, including passing the data structure for the entity from the one of the server computers to the other of the other of the server computers.