Abstract
Adaptive tuning techniques are provided for data communications in an Object Management Group (OMG) Real-Time Publish Subscribe (RTPS) Protocol operable over a communication network to provide good throughput/latency tradeoff as well as efficient bandwidth utilization. With this invention, latency under high throughput conditions can be reduced several times compared with the latency obtained with traditional non-adaptive approaches.
Claims
1. A method for adaptively auto-tuning data communications over a communication network in a Real-Time Publish-Subscribe Protocol (RTPS), comprising: an auto-tuning method for the RTPS Protocol, wherein the RTPS Protocol sends samples from an RTPS-Writer to an RTPS-Reader, wherein each of the samples is identified by a writer global source identifier (GUID) and a sequence number, wherein the auto-tuning method is implemented as a computer software executable by a computer for dynamically and automatically adjusting a size of an RTPS-BATCH based on a publication rate, wherein the RTPS-BATCH is defined as an RTPS-DATA message aggregating together in a single RTPS-DATA message multiple samples, wherein that RTPS-BATCH message is sent as a single RTPS-DATA message by the RTPS-Writer, and wherein the publication rate is defined as the number of samples that are written by the RTPS-Writer per second to the RTPS-Reader.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1) FIG. 1 shows a Basic reliable RTPS Message Exchange according to the current state of the art. HB=HEARTBEAT, ACK=Positive acknowledgment and NACK=Negative acknowledgment.
(2) FIG. 2 shows a Send Window Update Algorithm according to an exemplary embodiment of the invention.
(3) FIGS. 3-4 combined show the Send Rate Adjustment Algorithm according to an exemplary embodiment of the invention
(4) FIG. 5 shows a Writer Without Batching according to an exemplary embodiment of the invention.
(5) FIG. 6 shows a Writer With Batching according to an exemplary embodiment of the invention.
(6) FIG. 7 shows a Batch Size Adjustment Algorithm according to an exemplary embodiment of the invention.
(7) FIG. 8 shows a Writer with Dynamic Batching according to an exemplary embodiment of the invention. In this example only during higher publication frequency will data be batched to trade away low latency in favor of better throughput. In our specific implementation we used a linear interpolation to calculate the batch size. This is described infra in detail: (WriteFrequency—MinFrequency)/(MaxFrequency—MinFrequency))*MaxBatchSize. In this exemplary implementation, we set MinFrequency to 10 samples per second, MaxFrequency to 10000 samples per second and MaxBatchSize to 32 KB (it is noted that these are all configuration parameters). The higher the frequency the more data we batch up to a maximum of 32 KB. Writing more than 10000 samples per second will always result in 32 KB batches.
(8) FIGS. 9-10 shows according to an exemplary embodiment of the invention the performance improvements to latency average (FIG. 9) and latency jitter (FIG. 10) by using (i) the system/method of this invention for dynamic adjustment of the send window size, (ii) the system/method of this invention for dynamic adjustment of the writing rate.
(9) FIG. 11 shows a according to an exemplary embodiment of the invention performance improvements to latency average by using dynamic sample batching versus direct batching.
DETAILED DESCRIPTION
(10) Dynamic Adjustment of the Send Window Size
(11) The first auto-tuning mechanism includes maintaining a send window of variable size on the Writer to provide a flow control mechanism. If the network is congested, for example, the Writer will stop writing samples.
(12) A Writer blocks when it tries to send a sample and the send window is full. Samples are removed from the send window as soon as they are acknowledged by all the Readers to which the Writer must send the samples.
(13) The size of the send window is updated periodically based on the number of RTPS NACK messages received by the Writer since the last update. FIG. 2 describes the window size update algorithm. In the algorithm: The window size is updated within the interval [MinSendWindowSize,MaxSendWindowSize] The window size is increased by a factor IncreaseWindowFactor where IncreaseWindowFactor>1 The window size is decreased by a factor DecreaseWindowFactor where
(14) DecreaseWindowFactor is strictly between 0 and 1, that is 0<DecreaseWindowFactor<1. UpdatePeriod is the update period RecvNACKs is the number of NACK messages received by the Writer in the current UpdatePeriod PrevRecvNACKs is the value of RecvNACKs in the previous UpdatePeriod.
(15) Dynamic Adjustment of the Sending Rate
(16) By introducing a variable send window size we provide a method to do flow control between the Writer and Reader(s) based on the number of NACKs received. This method optimizes the bandwidth usage and improves the average sample latency by reducing the number of repairs. However, samples that block the Writer will add a high latency component and they will increase jitter.
(17) To reduce the latency jitter we introduce a method that dynamically adjusts the sending rate by doing busy-waiting between writes. This way the send window does not fill up and the Writer never blocks and yields CPU. FIGS. 3 and 4 describe the rate adjustment algorithm. In the algorithm: CurrentSpinMicrosecondCount indicates the number of microseconds of busy-wait MaxSpinMicrosecondCount indicates the maximum number of microseconds of busy-wait SpinMicrosecondIncrement indicates by how many microseconds the busy-wait can increase between consecutive writes SpinMicrosecondDecrement indicates by how many microseconds the busy-wait can decrease between consecutive writes CurrentSampleCount is the number of samples sent since the Writer started. The CurrentSpinMicrosecondCount used to do busy-wait is recalculated every SpinUpdateSampleCount LowSendWindowSizeThreshold and HighSendWindowSizeThreshold are used to determine when to update CurrentSpinMicrosecondCount. The idea is to keep the number of unacknowledged samples in the send window between these two thresholds. ElapsedTime is the time elapsed in microseconds since the previous write operation (LastWriteTime). The amount of busy-wait is only adjusted every certain number of samples in order to allow the algorithm to stabilize. Because of this, if the speed at which the application writes samples decreases to a level in which spin is not necessary, the algorithm would be introducing an unnecessary component of latency until the spin becomes 0. To accomplish this the algorithm will not do busy-wait if the ElapsedTime is already greater than the CurrentSpinMicrosecondCount required.
(18) Dynamic Sample Batching
(19) The exchange of multiple RTPS messages, including DATA, HEARTBEAT and ACKNACK, to provide reliable communications between a Writer and one or multiple Readers introduces an overhead in bandwidth and CPU usage that affects the effective sample throughput in terms of samples per second.
(20) The number of DATA, HEARTBEAT and ACKNACK messages can be reduced by grouping multiple application changes (samples) into a single RTPS DATA message. This practice is commonly known as message batching or message aggregation. When this is done the effective throughput can be increased dramatically, especially for small data samples (size<2048 bytes). Batching many smaller samples to be sent in a single RTPS DATA message optimizes bandwidth usage, reduces CPU utilization, and thus improves throughput.
(21) FIG. 5 shows the Writer behavior without batching. FIG. 6 shows the Writer behavior with batching. In this case, multiple samples up to a number of samples or number of bytes are grouped and sent together into a single DATA RTPS message. There is also a configurable flush delay after which the current batch (independently of the number of samples sent on the network) is sent.
(22) The problem with a direct batching implementation is that although the throughput is dramatically increased at high publication rates, there is a significant penalty in latency at low publication rates as shown in FIG. 6.
(23) To mitigate this problem embodiments of this invention provide a technique for dynamically adjusting the size of a batch based on the current publication rate. This provides a good throughput/latency tradeoff. FIG. 7 describes the algorithm that adjusts the batch size. In the algorithm: The batch size (in bytes) is adjusted every SamplesPerReevaluation The batch size is adjusted between [1, MaxBatchSize] based on the write rate WriteFrequency The WriteFrequency is calculated without accounting for the blocking time (TotalBlokcingTimeSinceFirstWrite) generated because the Send Window is full GetBatchSize calculates the size of the batch based on the WriteFrequency. This function must be monotonic between 1 (for WriteFrequency=MinFrequency) and MaxBatchSize (for WriteFrequency=MaxFrequency). A possible implementation is to use a linear interpolation: (WriteFrequency—MinFrequency)/(MaxFrequency—MinFrequency))*MaxBatchSize;
(24) Adjusting the batch size dynamically provides a good throughput/latency tradeoff under scenarios in which the publication rate changes over time as shown in FIG. 8. Current approaches using fix size batches provide poor latency for low publication rates (a few samples per second). This latency can be several orders of magnitude higher than the latency provided with the auto-tuning protocol of the present invention.
(25) Performance
(26) The system/method for auto-tune reliable communications in RTPS Publish-Subscribe systems have been incorporated into the latest RTI Connext DDS 5.1.0.
(27) FIGS. 9-10 show the performance improvements to latency average and jitter by using: The system/method of this invention for dynamic adjustment of the send window size. The system/method of this invention for dynamic adjustment of the writing rate.
(28) FIG. 11 shows the performance improvements to latency average by using dynamic sample batching versus direct batching. In FIG. 11, every three rows represent a single run, so the publication rate (the demand) fluctuates during the same run. The first three rows represent no batching. The next three rows represent vanilla batching. The last three rows represent dynamic batching. The results are consistent with FIGS. 5, 6, and 8.
(29) Embodiments of the invention can be envisioned as a system and/or computer-implemented methods executed by a computer either standalone or part of a system in a communication network e.g. over the Internet.
