System for the reliable, fast, low-latency communication of object state updates over a computer network by combining lossy and lossless communications

• US 6,006,254 A
• Filed: 08/29/1997
• Issued: 12/21/1999
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Information Technology Center America, Inc. (Mitsubishi Electric Corporation)
• Inventors: Anderson, David, Waters, Richard C.
• Primary Examiner(s): Dinh, Dung C.
• Assistant Examiner(s): LE, QUOC KHANH
• Application Number:
  US08/920,585
• Time in Patent Office: 844 Days
• Field of Search: 709/205, 709/232, 709/206, 709/230, 709/236, 709/200, 709/204
• US Class Current: 709/205
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• 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 system for fast, efficient and reliable communication of object state irmation among a group of processes combines the use of a fast, but lossy and thus unreliable communications channel to the group of processes and a server coupled to the group for providing data which has been lost in the multicasting. In one embodiment, a central server supports reliability and rapid joining while using UDP multicast messaging to achieve rapid interaction and low bandwidth. Differential messages are sent over the lossy channel to compactly describe how to compute the new state of an object from any of several previous states. Such a description can be interpreted even if some number of prior descriptions were not received, greatly reducing the need for explicit, round-trip message repairs while also conserving bandwidth. In one embodiment, the central server communicates with each member of the group over a reliable channel to robustly detect and repair objects affected by lost messages.

Claims

1. A system for fast, efficient and reliable communication of object state information among a group of users, comprising:

a network and a number of users at nodes of said network, each of said users having a computer coupled to said network;

a world model, containing objects stored at each of said users and coupled to respective computers;

means at a user for altering said world model thereat by altering objects of said world model such that objects of said world model are changed;

means including messages for communicating the current state of objects that have changed to other users over a lossy direct link to said other users for rapidly communicating the current state of said objects to said other users;

means at a user for detecting when messages describing object state are lost; and

,

a server coupled to said lossy direct link for storing said object states and for transmitting up-to-date object states over a lossless link to a user when requested by that user, whereby information transmitted over said lossy link which is lost can be recovered with information from said server.

2. The system of claim 1 wherein said server includes means for sending object state summary messages to said users over said lossless link and wherein said means for detecting when messages describing object state are lost includes means for comparing said summary messages with object states currently at the user such that retransmission of information is done on the basis of obtaining the most up-to-date information about objects rather than retransmitting every lost message.

3. The system of claim 2 wherein said summary message specifies for each object a counter value identifying the latest version of the state known to said server.

4. The system of claim 2 wherein said summary messages are differential messages specifying the state only of objects that have changed since the last summary message.

5. The system of claim 1 wherein said object state messages are differential messages indicating only the part of the state that is different from the prior state.

6. The system of claim 1 wherein said object state messages are differential messages indicating only the part of the state that is different from any of the previous N states, where N is greater than one, thereby allowing a differential message to be interpreted even if the prior message was lost so that it is not necessary to retransmit every lost message.

7. The system of claim 6 wherein said server includes means for transmitting a summary of changes in said object state to said users and further including means at each user for comparing a summary from said server to a like summary stored at said user as a result of said lossy direct link, thus to detect a lost message and for causing said server to transmit an updated message responsive to the detection of said lost message.

8. The system of claim 6 wherein said objects are identified by GUIDs, and wherein the assignment of GUIDs to objects includes means for causing the GUIDs for all the objects modified by a given user to have many bits in common, thereby allowing messages describing object state to be represented more completed.

9. The systems of claim 6 wherein a means for creating said differential messages describing object state includes bitmasks for representing which components of an object have change in the transmissions between each of said N previous states, thereby allowing the rapid and compact determination of what information needs to be included in said differential messages describing object state by combining said bitmasks with a logical OR operation.

10. The system of claim 1 wherein said objects are graphical objects.

11. The system of claim 1 and further including means at a user for rejecting messages describing object states that arrive out of order with a delay greater than a predetermined amount of time, thereby placing a bound on how long said user must maintain a record that an object has been removed, so as to be able to reject out of order messages about said objects.

12. The system of claim 1 wherein said group of users can be dynamically changed, and wherein said server includes means for downloading the current state of every object in the world model to a user when requested by said user.

13. The system of claim 1 wherein said lossy direct communication link utilizes multicast.

14. The system of claim 1 wherein said server includes means for simulating multicast communication to those of said users who are incapable of direct multicast communication.

15. A system for fast, efficient and reliable communication of object state information among a group of users, comprising:

a network and a number of users at nodes of the network;

a world model, containing objects stored at each of said users and coupled to respective computers;

means at a user for altering said world model thereat by altering objects of said world model such that objects of said world model are changed;

means including messages for communicating a current state of said objects that have changed to other users over a lossy direct link to said other users for rapidly communicating the current state of said objects to said other users;

means at a user for detecting when messages describing object states are lost;

a server coupled to said lossy direct link for storing said object states and for transmitting up-to-date object states over a lossless link to a user when requested by that user, whereby information transmitted over said lossy link which is lost can be recovered with information from said server, and

means for rejecting messages that arrive late by a predetermined amount, thus to create lost messages, said server providing recovery of the information lost thereby, whereby the amount of information that must be stored by each user is bounded.