Selectively ordered protocol for unreliable channels

• US 8,284,663 B2
• Filed: 10/14/2005
• Issued: 10/09/2012
• 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: Kujawa, Michael, Berkebile, Todd
• Primary Examiner(s): Divecha, Nishant B
• Assistant Examiner(s): PHAM, TITO Q
• Application Number:
  US11/251,301
• Publication Number:
  US 20070086343A1
• Time in Patent Office: 2,552 Days
• Field of Search: None
• 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 of discarding a message that is intended to be delivered to a computer over a data communication network, said method comprising:

(a) receiving a first message intended for said computer, said first message having a first sequence index and a first ephemerality index;

(b) receiving a second message intended for said computer, said second message having a second sequence index and a second ephemerality index;

(c) determining that said first ephemerality index and said second ephemerality index are the same;

(d) comparing the first sequence index and the second sequence index;

(e) on the basis of the comparison, delivering said second message before said first message;

(f) receiving a third message intended for said computer, said third message having a third sequencing index and a third ephemerality index;

(g) receiving a fourth message intended for said computer, said fourth message having a fourth sequencing index and a fourth ephemerality index;

(h) determining that said third ephemerality index and said fourth ephemerality index are different; and

(i) discarding said third message;

wherein said ephemerality indices are not priority indices;

whereby the third message, which was intended for said computer, never reaches said computer.

2. The method of claim 1, wherein said first message has a first channel identifier, said second message has a second channel identifier, said third message has a third channel identifier, and said fourth message has a fourth channel identifier.

3. The method of claim 2, wherein said first channel identifier and said second channel identifier identify a first channel, wherein said third channel identifier and said fourth channel identifier identify a second channel that is different from said first channel, and wherein said steps of receiving a third message intended for said computer, said third message having a third sequencing index and a third ephemerality index, receiving a fourth message intended for said computer, said fourth message having a fourth sequencing index and a fourth ephemerality index, determining that said third ephemerality index and said fourth ephemerality index are different, and discarding said third message are performed independently of said steps of receiving a first message intended for said computer, said first message having a first sequence index and a first ephemerality index, receiving a second message intended for said computer, said second message having a second sequence index and a second ephemerality index, determining that said first ephemerality index and said second ephemerality index are the same, comparing said first sequence index and said second sequence index, and on the basis of said comparison, delivering said second message before said first message.

4. The method of claim 1, wherein receiving said first message comprises receiving said first message using a reliable datagram service, receiving said second message comprises receiving said second message using said reliable datagram service, receiving said third message comprises receiving said third message using said reliable datagram service, and receiving said fourth message comprises receiving said fourth message using said reliable datagram service.

5. The method of claim 4, wherein said reliable datagram service makes use of a User Datagram Protocol (UDP).

6. The method of claim 4, wherein at least one of receiving said first message, receiving said second message, receiving said third message, and receiving said fourth message comprises receiving a retransmission of a datagram.

7. The method of claim 6, wherein receiving a retransmission of a datagram includes receiving retransmitted datagram header information without receiving retransmitted payload data corresponding to said datagram header information.

8. A manufacture comprising a non-transitory computer-readable medium having encoded thereof software for discarding a message that is intended to be delivered to a computer over a data communication network, said software including instructions for causing a computer system (a) to receive a first message intended for said computer, said first message having a first sequence index and a first ephemerality index, (b) to receive a second message intended for said computer, said second message having a second sequence index and a second ephemerality index, (c) to determine that said first ephemerality index and said second ephemerality index are the same, (d) to compare said first sequence index and said second sequence index, (e) on the basis of said comparison, to deliver said second message before said first message, (f) to receive a third message intended for said computer, said third message having a third sequencing index and a third ephemerality index, (g) to receive a fourth message intended for said computer, said fourth message having a fourth sequencing index and a fourth ephemerality index, (h) to determine that said third ephemerality index and said fourth ephemerality index are different, and (i) to discard said third message, wherein said ephemerality indices are not priority indices, whereby said third message, which was intended for said computer, never reaches said computer.

9. The manufacture of claim 8, wherein said instructions comprise instructions for causing said computer system to determine that said first message has a first channel identifier, that said second message has a second channel identifier, that said third message has a third channel identifier, and that said fourth message has a fourth channel identifier.

10. The manufacture of claim 9, wherein said instructions comprise instructions for causing a computer system to determine that said first channel identifier and said second channel identifier identify a first channel, and that said third channel identifier and said fourth channel identifier identify a second channel that is different from said first channel, and wherein said instructions for causing a computer system to receive a third message intended for said computer, said third message having a third sequencing index and a third ephemerality index, to receive a fourth message intended for said computer, said fourth message having a fourth sequencing index and a fourth ephemerality index, to determine that said third ephemerality index and said fourth ephemerality index are different, and to discard said third message are performed independently of said instructions for causing said computer system to receive a first message intended for said computer, said first message having a first sequence index and a first ephemerality index, to receive a second message intended for said computer, said second message having a second sequence index and a second ephemerality index, to determine that said first ephemerality index and said second ephemerality index are the same, to compare said first sequence index and said second sequence index, and on the basis of said comparison, to deliver said second message before said first message.

11. The manufacture of claim 8, wherein said instructions for causing a computer system to receive said first, second, third, and fourth messages comprise instructions for causing said computer system to receive messages via a reliable datagram service.

12. The manufacture of claim 11, wherein said instructions for causing said computer system to receive messages via a reliable datagram service comprise instructions for causing said computer system to receive messages via a User Datagram Protocol (UDP).

13. The manufacture of claim 11, wherein said instructions for causing said computer system to receive messages via said reliable datagram service comprise instructions for causing said computer system to receive retransmitted datagrams.

14. The manufacture of claim 13, wherein said instructions for causing said computer system to receive retransmitted datagrams comprise instructions for causing said computer system to receive retransmitted datagram header information without receiving retransmitted payload data corresponding to said header information.