\section{Performance}
\label{timing}

\begin{table*}
\begin{center}
\begin{tabular}{|r|c||c|c||c|c||c|c||c|c||c|c|}
\hline 
& thr. & \multicolumn{2}{c||}{no sharing} & \multicolumn{2}{c||}{2-out-of-3} & 
	       \multicolumn{2}{c||}{2-out-of-4} & 
		\multicolumn{2}{c||}{3-out-of-4} &
		\multicolumn{2}{c|}{3-out-of-5}  \\
\hline 
%512 & 0.006s &  165/s & 0.274s & 6.96/s &        &         &        &         &        &         \\
1024 & 2  & 0.067s & 29.2/s & 0.411s & 4.86/s & 0.403s & 4.95/s & 0.639s & 3.08/s & 0.638s & 3.13/s \\
1024 & 10 & 0.070s & 28.9/s & 1.343s & 7.14/s & 1.180s & 7.90/s & 1.790s & 4.83/s & 1.755s & 4.90/s  \\
2048 & 2  & 0.370s & 5.38/s & 1.434s & 1.38/s & 1.268s & 1.55/s & 1.978s & 1.01/s & 1.975s & 1.00/s \\
\hline
\end{tabular}
\end{center}
\mbox{} \vspace{-0.5cm}
\caption{Latency and throughput as a function of key size} \label{tbl:perf1}
\end{table*}

\begin{table*}
\mbox{} 
\begin{center}
\begin{tabular}{|r||c|c||c|c||c|c||c|c|}
\hline
 & \multicolumn{2}{c||}{2-out-of-3} & 
   \multicolumn{2}{c||}{2-out-of-4} & 
   \multicolumn{2}{c||}{3-out-of-4} & 
   \multicolumn{2}{c|}{3-out-of-5} \\
\hline
0--offline & 0.411s & 4.86/s & 0.403s & 4.95/s & 0.639s & 3.08/s & 0.638s & 3.13/s  \\
1--offline & 0.604s & 3.26/s & 0.532s & 3.72/s & 0.979s & 2.01/s & 0.887s & 2.19/s  \\
2--offline &        &        & 0.763s & 2.60/s &        &        & 0.967s & 2.03/s  \\
\hline
\end{tabular}
\end{center}
\mbox{} \vspace{-0.5cm}
\caption{The effect of offline servers (1024-bit key)} \label{tbl:perf2}
\end{table*}

The following timing measurements were taken on six Intel-based PC's.  Two
were running Solaris 2.6 at 333Mhz and four were running Windows NT at
450Mhz.  The machines were connected via a 10base-T Ethernet.  Clearly, a
faster local network would improve our performance numbers.

Table~\ref{tbl:perf1} shows the latency and throughput for several
key-sizes and sharings.  Latency is the time that a client has to wait for
a request to be serviced.  Throughput is the number of requests that can
be serviced per second.  The table also lists the number of concurrent
threads running on the {\em client}.  The more threads run on the client
the higher the load on the servers.  Load balancing causes each share
server to see some fraction of the requests.  For example, when 10 threads
are used the client makes 10 concurrent requests.  If a 3-out-of-5 sharing
is in use, each share server will service an average of $\frac{3}{5}$ of
the total requests, or an average of 6 concurrent requests.

If the requests are processed serially, throughput depends only on
latency, but when multiple clients connect to the servers at once
load-balancing increases throughput.  Increasing the number of
simultaneous connections slows down each individual request but increases
the throughput.  Unless stated otherwise, the number of simultaneous
connections was set to two.

A larger key corresponds to more communication and longer computations, so
as the number of bits in the key increases, the latency increases and the
throughput decreases.  In every configuration, the 1024-bit key was
significantly faster than the 2048-bit key.

Latency is affected by both the number of servers involved in a request
and the total number of servers.  For a fixed threshold, a larger total
number of servers makes load-balancing more effective by distributing
concurrent requests over more servers.  This keeps the servers from being
inundated by requests.  When the total number of server is fixed, a higher
threshold is likely to increase latency.  To see this recall that a
request completes only once all the servers in the coalition respond. With
a larger coalition it is more likely that a busy server is included in the
coalition.  Hence, the time until the request completes is likely to
increase.

The ratio of servers used to the total number of servers is the dominating
factor in throughput.  For example, with the 3-out-of-5 sharing, this
ratio would be 0.6.  As this ratio shrinks, a smaller portion of the
servers is required per request, and more simultaneous requests can be
processed with the same performance.

Table~\ref{tbl:perf1} also compares shared keys versus standard
non-shared RSA keys.  As expected, latency is larger when
using a shared key than when using a non-shared key.  The use of the
shared key requires communication with share servers which is not
required when using a non-shared key.  Likewise, throughput is lower
when using a shared key, but throughput doesn't degrade as much as
latency because of load-balancing and multi-threading of the share
servers.

As the number of simultaneous requests (threads) grows, latency also
grows, because of the higher load on the servers.  However, throughput
improves because of load balancing and because the servers can service
some threads while other threads are idle.


Table~\ref{tbl:perf2} shows what happens when some servers are taken
offline.  This is implemented by putting the share-servers in ``suspended''
mode.  In this mode, a server can accept connections, but immediately
closes them.  Performance is identical when a server is simply shut down.

The TLB detects all offline servers in the coalition in one pass.
When too many servers are offline, TLB returns an error code.  For
example, the 2-out-of-3 sharing will return an error code if two servers
are offline, since the remaining server cannot service a request by itself.

Taking servers offline increases latency because some requests have to be
issued multiple times, with different coalitions.  Also, as servers are
taken offline, load-balancing forces the remaining servers to service more
requests, further increasing latency.  Throughput also suffers when
servers are taken offline, for the same reasons as latency.

Performance drops more when going from 0--offline to 1--offline than it
does when going from 1--offline to 2--offline.  2--offline is worse than
1--offline since in the worst case requests may need to be issued three
times until a valid coalition is found.  As servers are taken offline, the
sharings that use a larger fraction of the total servers degrade the most.
For example, taking one server offline affects the 2-out-of-3 and
3-out-of-4 sharings more than the 2-out-of-4 sharing.  This is because
load balancing is more effective when the number of servers per request is
small compared to the total number of servers.

Table~\ref{tbl:perf3} shows the effects of corrupt servers.  Corrupt
servers act just like normal servers, but they return invalid responses.
In the tests used to find this data, corrupt servers compute the correct
response, then return twice that value.  When an invalid response is
detected all servers in the coalition are checked for corruption. Hence, all
corrupt servers in the coalition are detected in one pass.

Latency grows dramatically when corrupt servers are detected.  There
are two causes for this growth.  First, just as with offline servers,
requests may need to be issued multiple times.  Second, when a
corruption is found, each server in the corrupt coalition must be
checked to see if it is corrupt (see Section~\ref{corrupt}).
Comparing this chart to the previous chart, it becomes apparent that a
corrupt server adds approximately 2.7 times latency penalty as an
offline server in the same configuration.  As with offline servers,
throughput suffers as servers are corrupted, for the same reasons as
latency.

\begin{table*}
\begin{center}
\begin{tabular}{|r||c|c||c|c||c|c||c|c|}
\hline
 & \multicolumn{2}{c||}{2-out-of-3} & 
   \multicolumn{2}{c||}{2-out-of-4} & 
   \multicolumn{2}{c||}{3-out-of-4} & 
   \multicolumn{2}{c|}{3-out-of-5} \\
\hline
0--corrupt & 0.411s & 4.86/s & 0.403s & 4.95/s & 0.639s & 3.08/s & 0.638s & 3.13/s  \\
1--corrupt & 0.955s & 2.06/s & 0.823s & 2.40/s & 1.478s & 1.31/s & 1.334s & 1.50/s  \\
2--corrupt &        &        & 1.536s & 1.28/s &        &        & 2.084s & 0.95/s  \\
\hline
\end{tabular}
\end{center}
\mbox{} \vspace{-0.5cm}
\caption{The effect of corrupt servers (1024-bit key)} \label{tbl:perf3}
\end{table*}

\begin{table*}
\mbox{}
\begin{center}
\begin{tabular}{|c|c|c||c|c||c|c||c|c||c|c|}
\hline
 & key-size  & thr. & \multicolumn{2}{c||}{no sharing} & \multicolumn{2}{c||}{2-out-of-3} &
	      \multicolumn{2}{c||}{2-out-of-4} & \multicolumn{2}{c|}{2-out-of-4} \\
 &      &   & \multicolumn{2}{c||}{}           & \multicolumn{2}{c||}{}           & 
	      \multicolumn{2}{c||}{}           & \multicolumn{2}{c|}{1--offline} \\
\hline
web-server & 1024 & 2  & 0.209s & 9.50/s &  0.644s & 3.10/s & 0.515s & 3.84/s & 0.535s & 3.73/s \\
web-server & 1024 & 10 & 1.097s & 8.25/s &  1.362s & 6.85/s & 1.503s & 6.03/s & 1.543s & 5.66/s \\
web-server & 2048 & 2  & 0.389s & 5.05/s &  1.527s & 1.31/s & 1.484s & 1.34/s & 1.509s & 1.32/s \\
\hline
CA         & 1024 & 2  & 0.067s & 29.2/s &  0.411s & 4.86/s & 0.403s & 4.95/s & 0.532s & 3.72/s \\
CA         & 2048 & 2  & 0.370s & 5.38/s &  1.434s & 1.38/s & 1.268s & 1.55/s & 1.749s & 1.12/s \\
\hline
\end{tabular}
\end{center}
\mbox{} \vspace{-0.5cm}
\caption{Usage of ITTC in a CA and web server} \label{tbl:perf4}
\end{table*}

Table~\ref{tbl:perf4} shows the performance of a web-server and
certification authority, both using shared and non-shared private keys
of size 1024-bits and 2048-bits.  The web-server was tested by
repeatedly establishing an SSL connection and issuing a {\tt HEAD}
request to a URL on the web-server.  The number of threads listed in
the table reflects the number of concurrent threads used by the test
program when establishing connections to the web server.

In the web-server, both latency and throughput are worse with a shared-key
than with a non-shared key, but not by much.  With 10 simultaneous
connections, latency is only 24\% higher for a shared key and throughput
is only 17\% worse.  For most applications, this slowdown is insignificant
considering that SSL session establishment is only a small part of the
interaction with the web server.
