4.4 Reduction of elapsed time

**Figure 5:** Elapsed time for value shipping and operation shipping.
$\begin{figure} \begin{center} \begin{tabular}{\vert l\vert l\vert r\vert\vert r... ...ntheses are standard deviations from three runs.} \end{center} \par\end{figure}$

We also measured the elapsed time for propagating an update by value shipping and by operation shipping. The elapsed time is the time to complete the respective remote procedure calls: ViceReintegrate for value shipping, and UserOpPropagate for operation shipping. For the latter, the elapsed time comprises the time for shipping the operation log, re-executing the operation, and other overhead, such as checking the fingerprints. Since the elapsed time depends heavily on the network bandwidth, we measured it under three different network bandwidths: 9.6, 28.8, and 64.0 kilobits per second. The measurements are shown in Figure 5.

We summarize the speedups for the tests in Figure 6. The speedup is defined to be the ratio T_v/T_op, where T_v and T_op are the elapsed time for value shipping and operation shipping respectively.

We found that the speedups were substantial. They were the most substantial in the 9.6-Kbps network. Eight out of the 16 tests were accelerated by a factor exceeding 10. The maximum speedup was 26.3 (T9); the minimum speedup was 3.4 (T1). In the other two networks, the speedups ranged from a factor of 1.4 to 10.2. (There was one exception: test T1 slowed down when using operation shipping at 64 Kbps.)

However, we also found that the speedups were smaller than the numbers that we got from the previous version of our system, where forward error correction was not used. We performed some initial profiling of the time spent for operation shipping and found that the overhead of FEC was not small, sometimes as high as 80% of the total elapsed time. Although FEC is useful in handling the side effects of timestamps, it does not justify such a large overhead. We plan to use two optimizations to reduce the overhead: (1) we could use FEC on only those applications that need it, using hints from the users, and (2) we could choose to use a smaller number of parity symbols (says, 16) and substantially reduce the amount of computation needed.

Even without the planned optimizations, our current result has already shown that operation shipping is useful. Our result also indicates another advantage of operation shipping. That is, the speed of update propagation is much less sensitive to the network condition. This can be seen from the elapsed-time-bandwidth curves for test T9, plotted in Figure 7, in which the curves for value shipping is steep and that for operation shipping is flat. (Curves for other tests show similar trends.)

Combining the results of these two subsections, we conclude that operation shipping can reduce network traffic very substantially, can accelerate update propagation substantially, and can make the elapsed time of update propagation much less dependent on the network condition.

**Figure 6:** Speedups for update propagation
$\begin{figure} \begin{center} \begin{small} \begin{tabular}{\vert l\vert l\vert ... ...9.6), 28.8-Kbps (28.8), and 64-Kbps (64).}}\end{small}\end{center}\end{figure}$

**Figure 7:** Elapsed time vs. bandwidth
$\begin{figure} \centerline{ \psfig{figure=T9_elapse.eps,width=4in} }\end{figure}$