removed ifpps as std tool

[ana-net.git] / doc / papers / ancs2011 / epics.tex

% This is "sig-alternate.tex" V1.9 April 2009
% This file should be compiled with V2.4 of "sig-alternate.cls" April 2009
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.4 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.4) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.9 - April 2009

\documentclass{sig-alternate}
\usepackage{paralist}
\usepackage{color}
\newcommand{\wolfgang}[1]{\textcolor{blue}{\emph{WM: #1}}}
\newcommand{\ariane}[1]{\textcolor{green}{\emph{AK: #1}}}

\usepackage{url}
\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{ANCS}{2011 Brooklyn, New York, USA}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{Efficient Implementation of Dynamic Protocol Stacks in Linux}
% in Linux\wolfgang{title is ok, but could be more trendy ... I'll think about it}}

%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Ariane Keller\\
       \affaddr{ETH Zurich, Switzerland}\\
       \email{ariane.keller@tik.ee.ethz.ch}
% 2nd. author
\alignauthor
Daniel Borkmann\\
        \affaddr{ETH Zurich, Switzerland}\\
        \affaddr{HTWK Leipzig, Germany}\\
        \email{dborkma@tik.ee.ethz.ch}
% 3rd. author
\alignauthor 
Wolfgang M{\"u}hlbauer\\
       \affaddr{ETH Zurich, Switzerland}\\
       \email{muehlbauer@tik.ee.ethz.ch}
%\and  % use '\and' if you need 'another row' of author names
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\date{30 July 2011}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}

%\wolfgang{I tried to think about an abstract, see next paragraph. Feel free to change ... It's a little bit long, but first sentence can be dropped, etc. Maybe, it's also useful for the intro}
%Beyond doubt, the Internet has grown out of its infancy. Yet, 
Network programming is widely understood as programming strictly defined socket
interfaces. Only some frameworks (e.g., ANA, Click, Active Networking) have made a step
towards \emph{real} network programming by decomposing networking functionality
into small modular blocks that can be assembled in a flexible manner. In this
paper, we tackle the challenge of accommodating 3 partially conflicting
objectives: (i) high flexibility for network programmers and network
application designers, (ii) re-configuration of the network stack at runtime,
and (iii) high packet forwarding rates.  First experiences with a prototype
implementation suggest little performance overhead compared to the standard
Linux protocol stack. 
\end{abstract}

% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Theory}

%\keywords{ACM proceedings, \LaTeX, text tagging}

\section{Introduction}

Beyond doubt, the Internet has grown out of its infancy. A huge variety of networked applications and a diverse range of protocols are available, ranging from protocols for the communication over fibre, cat5 or over the air to protocols supporting specific applications such as p2p, web or voIP. However, the architecture is not designed to also allow for an easy integration of new protocols between these two layers. We argue that an architecture that would not limit innovation to the outer layers would give the Internet another boost.
\ariane{should also motivate runtime here.}

Some research with this goal was already done in active networking \cite{ANSurvey2}, with the Click modular router \cite{click} or with openflow \cite{openflow}. However, none of the available implementations fulfils the following three partially conflicting objectives. 
%The fast speed of the growth of the Internet and the huge effect on everyday life could lead to the thought that it is perfectly designed and nothing should be changed on the underlying architecture. However, researcher are working continuously on new protocols that improve the communication performance for different communication scenarios. Be it in the area of routing, transport or completely new network architectures. The evaluation of such protocols has shown to be difficult as simulations are not realistic enough and as it is difficult to change anything in standard operating systems protocol stacks. To overcome this difficulty some environments dedicated for testing were built, for example Click \cite{click} and openflow \cite{openflow} in the routing area or NetFPGA \cite{netFPGA} for the evaluation of hardware implementations. None of these platforms is specifically designed for evaluating protocols on the end nodes and none of these platforms are designed for an adaptation of the protocol stack at run time. In this paper we present the architecture of a framework that is designed for the following three goals. 
\begin{compactenum}
%\item Provide a platform in which it is easy to test new protocols on end nodes. In order to simplify testing further it should not require any specialized hardware. 
\item Simple integration and testing of new protocols on end nodes on all layers of the protocol stack.
\item Runtime reconfiguration of the protocol stack in order to allow for even bigger flexibility.
\item High performance packet forwarding rate.
%\item Provide a platform that imposes as little overhead as possible. This is required that the evaluation of new protocols delivers meaningful results. 
%\item Provide a platform which allows us to continuously optimize the protocol stack. This is especially useful in mobile scenarios where network characteristics such as delay or packet loss change frequently. Being able to use a protocol optimized for the given network characteristics might improve the connection quality drastically.
\end{compactenum}

Therefore we propose another architecture that was designed with those three goals in mind.
The architecture is based on the ideas of the \textit{Autonomic Network Architecture (ANA)}. \cite{ANAJournal}. In ANA network functionality is divided into functional blocks that can be combined as required. Each functional block implements a protocol such as \textit{ip, udp, encryption, content centric routing, etc.} ANA does not impose any protocols to be used other than Ethernet, rather it provides a framework that allows for the flexible composition and recomposition of functional blocks to a protocol stack. This allows for the experimentation with protocol stacks that are not known by todays standard operating system and it allows for the optimization of the protocol stack at runtime without communication tear down or application support.
The existing implementation of ANA shows the feasibility of such a flexible architecture but it suffers sever performance issues. 
In this paper we present the \textit{Lightweight Autonomic Network Architecture (LANA)}. It allows for a similar functionality than ANA but demonstrates that flexibility does not have to come at the cost of reduced performance.



\section{LANA}


%\wolfgang{quickly say first why you propose another architecture; e.g., Click configuration if an kernel cannot be changed at runtime or not happy with Ana's performance; it should be come clear that we try to accommodate conflicting objectives, see my abstract}
%LANA provides a framework for setting up protocol stacks not known by todays standard operating systems. Within LANA it is also possible to change the protocol stack at runtime, without communication teardown or application support. These properties build the basis for a networking system that provides protocol stacks that are better targeted to a networking situation than the well known TCP/IP protocol stack.

%LANA provides a framework for setting up protocol stacks not known by 
%todays standard operating systems. Within LANA it is also possible to 
%change the protocol stack at runtime, without communication teardown or 
%application support. These properties build the basis for a networking 
%system that provides protocol stacks that are better targeted to a 
%networking situation than the well known TCP/IP protocol stack.

Generally, the LANA network system is built similarly to the network system of the Linux kernel.
Applications can send and transmit packets via the BSD socket interface and the actual packet processing is done in a \textit{packet processing engine (PPE)} in the kernel space.
The hardware and device drivers interfaces are hidden from the PPE behind a \textit{virtual link interface}. This allows for a simple integration of different underlaying networking technologies such as Ethernet, Bluetooth or InfiniBand. Additionally, virtual link interface devices are represented as usual kernel networking devices and can be managed with standard tools such as \texttt{ifconfig} or \texttt{ethtool}.

Each functional block is implemented as a Linux kernel module. It offers a \textit{receive function} that is registered with the PPE upon module insertion. 
A functional block can either drop a packet, forward a packet to either ingress or egress direction or duplicate a packet. After having processed the packet it returns the identifier of the next functional block that should process this packet. In addition functional blocks belonging to the virtual link interface will queue the packets in the network drivers transmit queue and functional blocks communicating with BSD sockets will queue the packets in the sockets receive queue.

The PPE is responsible for calling one functional block after the other and for queuing packets that need to be processed.

%Data is transmitted between the functional blocks by function calls and is 
%therefore not being copied between functional blocks.
% A network packet is 
%processed by the LANAs packet processing engine, which calls receive handlers 
%of functional blocks that are bound to each other in the processing path. Data is then 
%either forwarded to the subsequent functional block or discarded. A certain
%path can be traversed in ingress or egress direction, thus functional
%blocks can also flip the packets direction within the packet processing engine.
%Moreover, the packet processing engine has per-CPU backlog queues so that
%functional blocks which spawn new network packets can enqueue the like for
%processing.

%There are two special functional blocks - those of the virtual link interfaces 
%communicating with a network driver and those communicating with BSD sockets.
%These functional blocks push network packets either in the drivers transmit 
%queue or in the sockets receive queue.

\begin{figure}
\centering
\includegraphics[width=0.47\textwidth]{figures/architecture.pdf}
%\epsfig{file=fly.eps}
\caption{LANA architecture}
\label{fig:architecture}
\end{figure}

%\begin{figure}
%\centering
%\includegraphics[width=0.4\textwidth]{figures/stack.pdf}
%\caption{Lana protocol stack showing in which contex which functionality is implemented}
%\label{fig:stack}
%\end{figure}

\subsection{Configuration Interface}
The protocol stack can be configured from user space with the help of a 
command line tool. The most important commands are summarized below.
\begin{compactitem}
\item \texttt{add}, \texttt{rm}: Adds (removes) a functional block from the 
      list of available functional blocks in the kernel. 
\item \texttt{set}: sets specific properties of a functional block with a 
      \texttt{key=value} semantic
\item \texttt{bind}, \texttt{unbind}: Binds (unbinds) a functional block 
      to another in order to be able to send messages to it. 
\item \texttt{replace}: Replaces one functional block with another 
      functional block. The connections between the blocks are maintained. 
      Private data can either be transferred to the new block or dropped.
\item \texttt{subscribe}, \texttt{unsubscribe}: Subscribes (Unsubscribes) one 
      functional block to receive event messages from another functional block.
%      (An implicit subscribtion (unsubscribtion) is done on bind (unbind).)
\end{compactitem}
Within the Linux kernel the notification chain framework is used to propagate those configuration messages to the individual functional blocks. This framework is also used to distribute other, internal, configuration messages. 

\subsection{Improving the Performance}
We have evaluated different possibilities for the integration of the PPE with the 
Linux kernel. We summarize our insights to provide guidance for researchers that have to do fundamental changes on the Linux protocol stack.

We compared the maximum packet reception rate of the Linux kernel while not doing any packet processing with our architecture. Here packets are forwarded between three functional blocks that do only packet forwarding. 

%Our goal was to be able to process as many \textit{minimum sized Ethernet frames} 
%as the Linux kernel is able to process. In order to compare the performance of 
%the Linux Kernel and the performance of our engine we have bypassed all packets 
%from the Linux Kernel protocol stack into the LANA stack via a
%\texttt{netdev\_rx\_handler} in bottom half context as soon as they arrived.

%In our system the packets were processed by the \texttt{fb\_eth} functional 
%block followed by two \texttt{fb\_dummy} functional blocks that were simply 
%forwarding the packets. We can distinguish the following three approaches:
\begin{compactitem}
\item One high priority LANA thread per CPU achieves approx. half the performance of the default stack. The performance degradation is due to 'starvation' of the software interrupt handler (ksoftirqd). Changing the priority of the LANA thread only slightly increases the throughput (since the ksoftirqd is a low-priority thread).
\item Explicit preemption and scheduling control achieves approx. two third of the performance of the default stack. The performance is still reduced by scheduling overhead. 
\item Execution of the PPE in ksoftirqd context. This approach achieves
      approximately $95\%$ of the performance of the Linux kernel.
\end{compactitem}

The corresponding numbers are listed in Table \ref{tab:performance}.
\begin{table}[htb]
\begin{tabular}{ l r }
Mechanism & Performance\\
\hline
Dedicated kernel thread (high priority) & 700.000\\
Dedicated kernel thread (normal priority) & 750.000\\
Dedicated kernel thread (controlled scheduling) & 900.000\\
Execution in ksoftirqd & 1.300.000\\
Linux kernel networking stack & 1.380.000\\
\end{tabular}
\caption{Performance evaluation in pps with 64 Byte packets.
% The evaluation was done with the kernel packet generator \texttt{pktgen} on two directly 
%connected machines with 
(Intel Core 2 Quad Q6600 with 2.40GHz, 4GB RAM, Intel 82566DC-2 NIC, Linux 3.0rc1)}
\label{tab:performance}
\end{table}

\subsection{Software Available}
The current sofware is available under the GNU General Public License from 
\cite{lana}. In addition to the framework it also includes four functional 
blocks: Ethernet, Berkeley Packet Filter, Tee (duplication of packets), Packet 
Counter and Forward (an empty block that just forwards the packets to 
another block). The framework does not need any patching of the Linux kernel
but it requires a new Linux 3.X kernel.

\section{Conclusions and Future Work}
We have shown that it is possible to implement a flexible protocol stack that has a similar performance than the default protocol stack in the Linux kernel. The flexibility allows for the easy inclusion of new, still to be developed protocols and for the change of the protocol stack at runtime. Both might lead to a protocol stack that is better suited for a given networking situation than the well known TCP/IP protocol stack.
%to include for example compression or encryption as the networking conditions change. 

In the short-term we will compare the performance of our system with the performance of other systems (e.g., default Linux stack, Click router, etc.). 
In the mid-term we will work on mechanisms that automatically configures protocol stacks based on the applications as well as the networks needs. 
%Applications will characterize which properties a communication channel should have and monitoring elements will provide information about the network. A controller will be responsible for negotiating a protocol stack with a peer and for setting up the protocol stack on the local node.
The end goal will be to have a networked system that requires less configuration as compared to todays networks and that is able to adapt itself to changing network conditions.   



%In the midterm we will develop a mechanism that automatically sets up a protocol stack for an Application whereby the Application can specify some characteristics the communication channel should have, but not exactly how this has to be achieved. For example the application could require a "reliable communication channel" and a controller would choose between different protocols that provide reliability (e.g., one for wired communication, one for wireless communication, one for wireless, multi-hop communication). The setup of the protocol stack will have to be negotiated between the source and destination node. 

%\end{document}  % This is where a 'short' article might terminate

%ACKNOWLEDGMENTS are optional
\section{Acknowledgments}
The research leading to these results has received funding from the European Union Seventh Framework Programme under grant agreement $n^o 257906$.
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{epics}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
\end{document}