Electrical computers and digital processing systems: multicomput – Computer network managing
Reexamination Certificate
1999-04-30
2003-07-01
El-Hady, Nabil (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer network managing
C709S224000, C709S232000
Reexamination Certificate
active
06587875
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains to computer network protocols and computer programs that implement such protocols.
BACKGROUND OF THE INVENTION
There are many instances in which it would be advantageous to be able to advance and retard data transfer rates during network data transmissions to make full use of the available bandwidth based on the current network traffic. One such instance occurs when multi-player games are played over a network, such as the Internet. The executable code for these games are often located on network servers that are accessible through various networks, such as the Internet. Alternately, some or all of the executable code for the games may be located on each of computers the players are using. One or more players can log on to the game and play against the game itself (a computer) or each other. These games typically comprise an ever-changing graphical environment that is primarily controlled by the control inputs of the various game players. For example, a game may involve several warriors facing off against one another, with one or more of the warriors being controlled by each player (or a computer). In such a game, the movements of each warrior relative to the graphical environment and the other warriors will depend on the control inputs of the players (or automated movements by the computer). For this reason, it is highly desired to transfer the user-input information to the game as rapidly as possible so that the inputs for the various players can be immediately reflected by updating the graphics displayed on each player's screen.
To understand why rapid data transfer is so desirable, consider a situation in which the data transfer carries a substantial delay. Player A activates her controls to cause one of her warriors to throw a spear at an enemy warrior. Player A aims the spear based on her perception of the current state of the game, i.e., what she sees on her screen. If the data transfer rate is rapid, the display each player sees accurately reflects (is synchronous with) the current state of the game. Conversely, if the data transfer carries a delay, the display each player sees does not accurately reflect the present game state—that is, the displays observed by the various players will not be synchronized. Under such circumstances, the players may miss their targets due to the program's inaccurate display of the positions of the other participants. This delay may also cause players to be unaware of an attack in progress from another player. Transfer delays of this type are frequently encountered when networked games are played, creating unsatisfactory game performance. A principle reason for this is conventional program development tools do not provide a built-in interface that allows the data transfer rate to be adjusted to optimize bandwidth use under varying link conditions.
Developers of multi-player networked game applications typically design games to support presumed worst-case bandwidth situations. As a result, the bandwidth usage between machines is limited to a fraction of the bandwidth available over the network link, which results in non-optimal game performance. Under such worst-case-scenario design practices, the game developer assumes a minimum available link bandwidth, such as 14.4 or 28.8 kilobaud (kilobits per second), and a maximum number of players the game will support or likely encounter. The developer may also determine the average (or maximum) size of each message that the game will transfer over the network (which she typically will seek to minimize). The developer will then calculate a maximum message sending rate based on this predetermined criteria, and the game application will send messages at this calculated transfer rate. For example, in a peer-to-peer game, where messages are distributed to all players from each machine, the following equation can be used to determine the maximum sending rate:
R
=
bw
cb
*
(
n
-
1
)
(
1
)
wherein R is the maximum message sending rate in messages per second, n is the number of players in the game, cb is the number of bytes in a message, and bw is the assumed bandwidth.
Unfortunately, the use of static calculations of this sort leads to a number of problems, including: (1) the application can't compensate for variation in headers due to the underlying transport; (2) the application will under-utilize the link in situations where more bandwidth is available than originally presumed; and (3) the application will not be able to adjust the message sending rate to compensate for other traffic on the link. In addition, when the conditions on the link are actually worse than the initial assumptions,sending messages at the statically-deterrnined rate will lead to the link being backlogged. That is, the rate at which the application sends messages may exceed the link's capabilities, causing messages to build up in the sending computer or on a router in the network, resulting in: increased apparent latency that can grow without bound, eventually making the game unplayable and ultimately causing the link to timeout.
A solution to all of the above problems is for the application to be able to make on-the-fly changes to the message send rate based on continuous measurements of the varying link conditions. In order to provide a platform (i.e. programming interface) for this solution, the platform must be able to determine the actual available bandwidth between two computers on a continuous basis. It is also preferable that the platform be able to detect link saturation and clear out backlogged messages. The platform must then be able to inform the application of the available bandwidth and link conditions so that the transmission code in the application can adapt to the prevailing network conditions.
SUMMARY OF THE INVENTION
The invention addresses the foregoing problems by providing a network communication protocol and associated methods for implementing the protocol that enable application programs to tune message send rates to optimize use of the available network bandwidth under varying network conditions. The network protocol is preferably implemented in an application program interface (API) that allows programmers to use features of the invention through a set of API calls. The network protocol resides at the application layer, providing a tool for application programs to use a variety of network protocol suites, including TCP/IP and IPX/SPX.
According to a first aspect of the invention, the network protocol allows application programs to determine the available bandwidth between two computers that are linked in communication across a network. Outbound messages are sent from a first local computer to a second remote computer, with the remote computer returning an acknowledge message for each outbound message. The local computer records the send time for each outbound message and includes a message identifier in the message. Each acknowledge message is timestamped with the time it is sent from the remote computer, and includes a count of the bytes received from the local computer and an identifier that matches the message identifier of the corresponding outbound message. The message identifier is used to ensure that the acknowledgement messages are correctly matched with outbound messages. A clock bias between the computers is calculated based on the local time the outbound messages are sent and the remote time they are received by comparing the send times with the acknowledge message timestamps. The rate the outbound messages are sent is increased until the link becomes saturated, which is detected by observing an increase in outbound latency based on changes in clock bias and roundtrip latency. The outbound bandwidth is calculated by calculating a difference in bytes received based on the byte counts in acknowledgement messages, and dividing the result by a difference in the time stamps of the acknowledgement messages.
According to another aspect of the invention, the network protocol facilitates a method for maintaining a clock offset between t
El-Hady Nabil
Microsoft Corporation
LandOfFree
Network protocol and associated methods for optimizing use... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network protocol and associated methods for optimizing use..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network protocol and associated methods for optimizing use... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3058398