\chapter{Methodology}
The measurement of performance parameters for the proposed five test cases is
listed in Table \ref{table:approach_overview}. These cases are classified into
three categories: Mirror-in-processing, Masked entry, and Calculated traffic.
And each case has a corresponding named method to its spirit.

\begin{center}
    \begin{table}[htb]
        \centering
        \begin{tabular}{| l | l | p{5cm}| l |}
            \hline
            Category & Test Case & Method & Output \\ \hline
            \multirow{2}{*}{Mirror-in-processing}
                & Action set time & Mirror-first-then-action & $T_{\var{action-set}}$ \\ \cline{2-4}
                & Pipeline Time & Mirror-first-then-pipeline &
                    $T_{\var{table-pipeline}}$ \\ \hline

            \multirow{2}{*}{Calculated traffic}
                & Buffer size & Burst-until-loss & $buf, PIR, POR$ \\ \cline{2-4}
                & Pipeline performance & Back-to-back-traffic & $P$ \\
            \hline

            Masked entry & Timeout accuracy & Idle-timeout-derived-by-hard-timeout
                & $Acc_{timeout}$ \\ \hline

        \end{tabular}
        \caption{Approach overview}
        \label{table:approach_overview}
    \end{table}
\end{center}

\section{Mirror-in-processing}
In the OpenFlow performance testing, it is difficult to get the test values and
results directly. However, by leveraging on the mirror operation with
Apply-Actions instruction within the processing, we can duplicate the packets
before some OpenFlow operations for measurement and comparison.

\subsection*{Mirror-first-then-action}
The purpose of this test case is to measure the execution time of action set in
OpenFlow switch. In OpenFlow protocol, there are many kinds of actions which
include forwarding, packet modification, and tagging operation. The packet
modification may cause longer operation time in some switches. Therefore, the
processing latency of action is used for major performance benchmark.


In the normal case, the time of action denoted by $T_{\var{action-set}}$ can be
calculated by measuring the end-to-end latency. Since there are many variables
affecting the testing result, we propose the mirroring concept to get the start
time of action set for better measurement accuracy. As shown in
\ref{fig:action_set}, the $pkt_z$ is denoted as the mirrored packet. The value
of $\alpha$ denotes the arrival time of $pkt_z$ and $\beta$ be the arrival time
of $pkt_z`$. We derive the action set execution time as

\begin{equation} \label{eq:action_set}
T_{\var{action-set}} = \beta - \alpha .
\end{equation}

\subsection*{Mirror-first-then-pipeline}
The purpose of this case is to measure the time of table pipeline in OpenFlow
switch. The mirroring methodology can be applied to this test case as well.
This is because the instructions of table pipeline are executed after
Apply-Actions.

As illustrated in Figure \ref{fig:pipeline_time}, we assume the pipeline stage
consists of two tables: $table_0$ and $table_1$. And the flow entries are almost
the same except the flow entry in $table_0$ has GoTo instruction. The time of
$T_1$ includes the time of table lookup and Apply-Actions operations in
$table_0$. The time of $T_2$ includes the time of $T_{table-pipeline}$, table
lookup, and Apply-Actions operations in $table_1$. Due to the same match fields
and actions of flow entry in $table_0$ and $table_1$, the processing latencies,
denoted by $T_{table\_lookup}$ and $T_{apply\_action}$ respectively, are the
same in $table_0$ and $table_1$. By considering the Round-Trip Time (RTT), that
we can derive the time of table pipeline as follows.

\begin{equation} \label{eq:table_pipeline}
T_{\var{table-pipeline}} = T_2 - T_1 + RTT / 2
\end{equation}

Where the $T_1$ is

\begin{equation} \label{eq:table_pipeline_t1}
T_1 = T_{table\_lookup} + T_{apply\_action} + RTT .
\end{equation}

And the $T_2$ is

\begin{equation} \label{eq:table_pipeline_t2}
T_2 = T_{\var{table-pipelien}} + T_{table\_lookup} + T_{apply\_action} + RTT /
2 .
\end{equation}

The $RTT$ can be derived by $RTT = (pkt_z / cap_n) * 2$.

\begin{figure}[htb]
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\columnwidth]{ActionSet.png}
        \caption{Mirror-first-then-action}
        \label{fig:action_set}
    \end{minipage}
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\columnwidth]{PipelineTime.png}
        \caption{Mirror-first-then-pipeline}
        \label{fig:pipeline_time}
    \end{minipage}
\end{figure}


\section{Calculated traffic}

\subsection*{Burst-until-loss}
The purpose of this test case is to measure the buffer size, the throughputs of
Packet-in and Packet-out. The main reason why we combine the measurement of
these three parameters into one case is that the Packet-in and Packet-out
messages may depend on the size of the buffer in dut.

As shown in Figure \ref{fig:buffer_size}, the $dut$ has the flow entry that
matches the $TFC$ and sends the Packet-in message to the controller $c$. The
controller $c$ will keep all Packet-in messages and generate the expected
Packet-out messages after the traffic generating from host $H$ is done. We
assume there is no packet loss occurred at $c$ and all Packet-in messages
consume the entire buffer space in the dut. When the condition $m < n$ occur,
there exists packet loss at the dut. Therefore, we can derive the buffer size,
denoted as $buf$ in the following formula.

\begin{equation} \label{eq:buffer_size}
buf = m * pkt
\end{equation}

The throughput of Packet-in can be derived by the following formula.

\begin{equation} \label{eq:packet_in}
    PIR = the\, number\, of\, Packet\textnormal{-}in / T_1
\end{equation}

And the throughput of Packet-out can be derived by the following formula.

\begin{equation} \label{eq:packet_out}
    POR = m / T_2
\end{equation}

\subsection*{Back-to-back-traffic}
The purpose of this test case is to measure the gain of table pipeline in $dut$.
As illustrated in Figure \ref{fig:pipeline_performance}, the latency of $TFC$
covers total processing time for $n + 1$ tables. In each table, packets are matched
with the flow entry and sent to the next table in a pipeline fashion.
%TODO: assuming the same processing time, this can reflect the system performance for a certain degree
The pipeline gain of $pkt$ processing time at each table
can be derived by the packet processing time and idle times.
We denote the processing time of $pkt$ and the idle time as $T_{pkt}$, $T_{bubble}$ respectively.
And we derive the pipeline gain from the following
formula.

\begin{equation} \label{eq:pipeline_performance}
    P = T_{pkt} / (T_{bubble} + T_{pkt})
\end{equation}

Where the $T_{pkt}$ is the processing time of the packet at each table.
Due to the difficulty of measuring the $T_{pkt}$ in black-box testing, we assume an uniform processing times of $pkt$ at each table for the performance evaluation.
Therefore, we approximate the $T_{pkt}$ by using the processing time of the first packet $T_{init}$ based on the following formula.

\begin{equation} \label{eq:pipeline_performance_t_pkt}
    T_{pkt} \approx T_{init} / (n + 1)
\end{equation}

In equation \ref{eq:pipeline_performance}, the time of $T_{bubble} + T_{pkt}$
reflect the total time of $pkt$ processing time and the idle time for a single table.
In our measurement, we known the total number of packets $n + 1$ and the
total duration $T$. Thus, asuuming there are $n$ packets sent after the first packet,
the average time of $T_{bubble} + T_{pkt}$ can be derived by the following formula.

\begin{equation} \label{eq:pipeline_performance_t_pkt_t_bubble}
    T_{bubble} + T_{pkt} \approx (T - T_{init}) / n
\end{equation}

The $T_{init}$ and $T$ are the processing time for the first packet, and the total processing
time for $n + 1$ packets respectively.
We denote the $\alpha_z$ as the time of sending $pkt_z$ and the $\beta_z$ as the arrival
time of $pkt_z$. And the $T_{init}$ and the $T$ be derived by the
$T_{init} = \beta_1 - \alpha_1$ and $T = \beta_{n+1} - \alpha_1$ respectively.

%In without pipeline, the $dut$ process the $pkt_{n+1}$ after
%the $pkt_n$ finished that increase the $T$ then the $P_{pipeline}$ approaches
%zero. On the other hand, if the $dut$ pipeline implement is well, the $T$
%should be lower.

\begin{figure}[htb]
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\columnwidth]{BufferSize.png}
        \caption{Burst-until-loss}
        \label{fig:buffer_size}
    \end{minipage}
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\columnwidth]{PipelinePerformance.png}
        \caption{Back-to-back-traffic}
        \label{fig:pipeline_performance}
    \end{minipage}
\end{figure}

%\begin{figure}[htb]
%    \begin{minipage}[b]{0.5\linewidth}
%        \centering
%        \subfloat[Burst-until-loss\label{fig:buffer_size}]{
%            \includegraphics[height=0.4\textheight]{BufferSize.png}
%        }
%    \end{minipage}
%    \begin{minipage}[b]{0.5\linewidth}
%        \centering
%        \subfloat[Back-to-back-traffic\label{sfig:pipeline_performance}]{
%            \includegraphics[height=0.4\textheight]{PipelinePerformance.png}
%        }
%    \end{minipage}
%\end{figure}

\section{Masked entry}
Base on the definition of OpenFlow specification, the flow table can have
multiple entries with the same match fields of different priority.

\subsection*{Idle-timeout-derived-by-hard-timeout}
The purpose of this case is to measure the accuracy of timeout for a given flow
entry. The timeout measurement includes hard-timeout and idle-timeout. For the
measurement of hard-timeout, we can evaluate the accuracy simply based on the
packet injected into the DUT. But for the measurement of idle-timeout, the
deviation of the accuracy could be larger due to the inter-arrival time of the
traffic as the flow entry being matched.

To evaluate the accuracy of idle-timeout, we propose to use the masked entry to
avoid the reset of the timer for idle-timeout at the wrong time by the arriving
packet. In Figure \ref{fig:timeout_accuracy}, there are two flow entries added
into the $dut$. The first one is the idle-timeout flow entry and the second is
the hard-timeout flow entry which is the masked entry with higher priority.
Both of the flow entries are matched with the $TFC$ and the time of
idle-timeout ($T_{\var{idle-timeout}}$) equals the time of hard-timeout
($T_{\var{hard-timeout}}$). When the idle-timeout flow entry is added to the
$dut$, the timer for idle-timeout stays zero as the packets are forwarded based
on the matched entry. After the setting of the idle-timeout flow entry, the
hard-timeout flow entry is added to the $dut$. At this moment, the hard-timeout
flow entry will take over the idle-timeout flow entry because of its higher
priority. And the timers for both of the flow entries will start counting from
zero as they are synchronized. Finally, there are 2 situations
illustrated in Figure \ref{sfig:timeout_accuracy_failed} and Figure
\ref{sfig:timeout_accuracy_success}. In Figure \ref{sfig:timeout_accuracy_failed},
the hard-timeout flow entry is expired early than idle-timeout flow entry. It
means that there exists the skewness for the timer of idle-timeout. In order to evaluate skewness
, we increase the $T_{\var{hard-timeout}}$ and set the hard-timeout
flow entry again. The process stated above is repeated until the idle-timeout flow entry is
expired early as illustrated Figure \ref{sfig:timeout_accuracy_success}.
According to the testing processes, we can derive the accuracy of idle-timeout
based on the following formula.

\begin{equation} \label{eq:timeout_accuracy}
    Acc_{\var{idle-timeout}} = T_{\var{idle-duration}} - T_{\var{idle-expired}} - T_{\var{idle-timeout}}
\end{equation}

The $T_{\var{idle-duration}}$, and $T_{\var{idle-forward}}$ are alive and active
times for idle-timeout flow respectively. We denote the $\alpha_z$ as the
arrival time of $pkt_z$. The $T_{\var{idle-forward}}$ can be derived from the
following formula.

\begin{equation} \label{eq:timeout_accuracy_forward}
    T_{\var{idle-forward}} = \alpha_n - \alpha_1
\end{equation}

%TODO: Please re-draw the figure to include all the parameters discussed in the equations in your paragraph

\begin{figure}[htb]
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \subfloat[Idle-timeout over hard-timeout\label{sfig:timeout_accuracy_failed}]{
            \includegraphics[height=0.3\textheight]{TimeoutAccuracyFail.png}
        }
    \end{minipage}
    \begin{minipage}[b]{0.5\linewidth}
        \centering
        \subfloat[Hard-timeout over idle-timeout\label{sfig:timeout_accuracy_success}]{
            \includegraphics[height=0.3\textheight]{TimeoutAccuracySuccess.png}
        }
    \end{minipage}
    \caption{Idle-timeout-derived-by-hard-timeout}
    \label{fig:timeout_accuracy}
\end{figure}
