\documentclass[aspectratio=169,obeyspaces,spaces,hyphens,dvipsnames]{beamer}
\usepackage[utf8x]{inputenc}
\usepackage{lmodern}% http://ctan.org/pkg/lm
\usepackage{minted}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage[normalem]{ulem}
\usepackage{textcomp}

\usepackage{multimedia}

\mode<presentation>
\usetheme{Bootlin}

\def\signed #1{{\leavevmode\unskip\nobreak\hfil\penalty50\hskip2em
  \hbox{}\nobreak\hfil(#1)
  \parfillskip=0pt \finalhyphendemerits=0 \endgraf}}

\newsavebox\mybox
\newenvironment{aquote}[1]
  {\savebox\mybox{#1}\begin{quotation}}
  {\signed{\usebox\mybox}\end{quotation}}

\title{Offloading Network Traffic Classification}
\conference{Embedded Linux Conference Europe, October 2019}
\authors{Maxime Chevallier}
\email{{\tiny maxime.chevallier@bootlin.com}}
\institute{Bootlin}
\slidesurl{https://bootlin.com/pub/conferences/2019/elce/chevallier-network-classification-offload/}

\begin{document}

\addtocontents{toc}{\protect\setcounter{tocdepth}{-1}}
\section{Offloading Network Traffic Classification}
\addtocontents{toc}{\protect\setcounter{tocdepth}{2}}

\begin{frame}{Maxime Chevallier}
  \begin{itemize}
    \item Linux kernel engineer at Bootlin.
      \begin{itemize}
        \item Linux kernel and driver development, system integration,
          boot time optimization, consulting\dots
        \item Embedded Linux, Linux driver development, Yocto Project
          \& OpenEmbedded and Buildroot training, with materials
          freely available under a Creative Commons license.
        \item \url{https://bootlin.com}
      \end{itemize}
    \item Contributions:
      \begin{itemize}
        \item Worked on network (MAC, PHY, switch) engines.
        \item Contributed to the Marvell EBU SoCs upstream support.
        \item Also worked on SPI and real-time topics.
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Preamble - goals}
  \begin{itemize}
    \item Discover the classification operations in the kernel.
    \item Discover the hardware technologies used to offload packet classification
    \item Learn about the use cases for classification
    \item Based on \textbf{PPv2}'s behaviour and design, similar on other NICs
  \end{itemize}
\end{frame}

\section{Introduction to Ingress Classification}

\begin{frame}{Packet path from the hardware to userspace}
	\begin{columns}
		\begin{column}{0.55\linewidth}
			\begin{enumerate}
				\item A frame arrives to the \code{PHY}
				\item It is transferred to the \code{MAC}
				\item The MAC performs offloaded operations
				\item The packet is copied to \code{RAM} via \code{DMA}
				\item The \code{MAC} raises an interrupt
			\end{enumerate}
		\end{column}
		\begin{column}{0.45\linewidth}
			\begin{center}
				\includegraphics[width=0.8\textwidth]{graphics/packet-path.pdf}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{MAC}
	\begin{itemize}
		\item Upon receiving a frame, the packet goes through a \textbf{Packet Processor}
		\item The \code{MAC} receives the frames and places them into a buffer using \code{DMA}
		\item Descriptors for that buffer are placed into a \textbf{receive queue}
		\item Once the frame is received, the \code{MAC} raises an \textbf{interrupt}
		\item Receive queues can have dedicated interrupts, pinned to CPUs
	\end{itemize}

	\begin{center}
		\includegraphics[width=0.3\textwidth]{graphics/rxqs.pdf}
	\end{center}
	% RxQs, DMA, irqs.
\end{frame}

\begin{frame}{Kernel path}
	\begin{itemize}
		\item The interrupt is handled, mostly in \code{softirq} context
		\item \code{napi} is used to coalesce interrupts
		\item Packet processing is done on the CPU that handled the interrupt
		\item Before going up the network stack, the packet goes through the \code{TC} subsystem
		\item L2 handling, to deal with \code{MAC} filtering and VLANs
		\item L3 handling, to deal with \textbf{routing}
		\item L4 handling, where we find the \textbf{socket} that will consume the payload
	\end{itemize}
	% meh, chopper un schéma quelquepart
\end{frame}

\begin{frame}{Classification}
	\begin{itemize}
		\item Classification consists in \textbf{identifying packets of interest}
		\item We can then perform \textbf{actions} on these packets
		\item We first need to \textbf{dissect} the packet
		\item Determining the various attributes of interest isn't straightforward
		\item All fields don't have a fixed offset in the packet
	\end{itemize}

	\begin{center}
		\includegraphics[width=0.7\textwidth]{graphics/headers.pdf}
	\end{center}
\end{frame}

\begin{frame}{Flows}
	\begin{itemize}
		\item A \textbf{flow} characterizes a group of packets that have a common source and destination.
		\item We group packets based on common attributes, such as :
			\begin{itemize}
				\item The source and destination IP addresses (2-tuple)
				\item The L4 protocol, source and destination ports (5-tuple)
			\end{itemize}
		\item We manipulate flows to avoid reordering and optimize locality
		\item We need to extract the required information from the headers.
	\end{itemize}
\end{frame}

\begin{frame}{TC flower}
	\begin{itemize}
		\item \textbf{T}raffic \textbf{C}ontrol
		\item Used for traffic shaping, scheduling, policing and filtering
		\item In our case, we'll focus on the \textbf{tc flower} ingress filter
		\item \textbf{tc flower} is a \textbf{classifier}, which uses either software or hardware
		\item \code{tc qdisc add dev eth0 ingress}
		\item \code{tc filter add dev eth0 protocol ip parent ffff: flower ip_proto tcp dst_port 80 action drop}
	\end{itemize}
\end{frame}

\begin{frame}{ethtool}
	\begin{itemize}
		\item \code{ethtool} is used to interact with network drivers
		\item \code{ethtool -N} can be used to configure \textbf{n-tuple} filters
		\item It acts on specific \textbf{flow types} : \code{tcp4}, \code{udp6}, \code{ether}, etc.
		\item Rules are \textbf{ordered}, the first one that matches takes precedence
		\item \code{ethtool -N eth0 flow-type tcp4 dst-port 80 action -1 loc 0}
		\item Actions can be :
			\begin{itemize}
				\item Steer to a Receive Queue
				\item Steer to a RSS context
				\item Drop
			\end{itemize}
	\end{itemize}
\end{frame}

\section{Offloading Classification}

\begin{frame}{When and why}
	\begin{itemize}
		\item Reduce \code{CPU} load
		\item Spread traffic across \code{CPU}s with per-cpu interrupts
		\item Early drop in case of Denial-of-Service attack
		\item Early redirection with switches
	\end{itemize}
	We must however be careful :
	\begin{itemize}
		\item The kernel might not see important packets
		\item The kernel might want to have access to the first packet of new flows
		\item Counters are not up to date anymore
	\end{itemize}

	% not suitable for all use cases : In some situations, the packet HAS to
	% be handled by the kernel. (first packet of a flow).
	% Accelerate redirect, drops and so on.
	% For server world ?
\end{frame}

\begin{frame}{Hardware design}
	\begin{itemize}
		\item Need to extract the required fields from the headers at wire speed
		\item These fields aren't always at a know position
		\item We need fast ways to lookup these fields, using a \textbf{parser}
		\item The attributes extracted by the parser are then used for \textbf{classification}
	\end{itemize}

	\begin{center}
		\includegraphics[width=0.9\textwidth]{graphics/hwpath.pdf}
	\end{center}
\end{frame}

\begin{frame}{Ternary Content Addressable Memory}
	\begin{itemize}
		\item Very fast lookups, but takes place on the die
		\item Addressed by value, returns the index of the first match
		\item Match on a ternary value : \code{0}, \code{1} and \code{X}
		\item The matched pattern is extracted from the header starting from an offset
		\item The returned index is used to lookup a SRAM containing match actions
	\end{itemize}

	\begin{center}
		\includegraphics[width=0.6\textwidth]{graphics/tcam.pdf}
	\end{center}
\end{frame}

\begin{frame}{Parser}
	\begin{itemize}
		\item Acts as a \textbf{dissector}
		\item Extract useful information from the packet header
		\item Take into account the various offsets due to DSA, VLAN and L3/L4
		\item Used as a pre-step for classification
		\item Often hardcoded in a firmware or a driver
		\item Multiple iterations per packet, flags are accumulated
	\end{itemize}
	\begin{center}
		\includegraphics[width=0.6\textwidth]{graphics/parser.pdf}
	\end{center}
	% extract info from packet header, for classification.
\end{frame}

\begin{frame}{Classifier}
	\begin{itemize}
		\item Uses information from the \textbf{parser}
		\item Can use several engines to classify and perform actions :
			\begin{itemize}
				\item TCAM engines, for exact matches
				\item Hash-based engines, for rate limiting and \code{RSS}
				\item Logic engines for complex rules
			\end{itemize}
		\item A final policing step decides what to do based on results from engines
		\item Not all these possibilities can be expressed by the generic frameworks
	\end{itemize}

	\begin{center}
		\includegraphics[width=0.6\textwidth]{graphics/classifier.pdf}
	\end{center}
	% uses results from parser to perform actions.
\end{frame}

\begin{frame}{RSS}
	\center{Receive Side Scaling}
	\begin{itemize}
		\item Spread traffic across multiple CPUs
		\item Compute a hash from specific fields from the header
			\begin{itemize}
				\item \textbf{s} : Source IP, \textbf{d} : Destination IP
				\item \textbf{f} : Source port, \textbf{n} : Destination port
				\item \textbf{v} : VLAN tag, \textbf{m} : Destination MAC
			\end{itemize}
		\item Make sure that traffic from the same flows ends up on the same CPU
		\item Spreading is configured using an \textbf{RSS Table}
	\end{itemize}

	\begin{itemize}
		\item \code{ethtool -N eth2 rx-flow-hash tcp4 sdfn}
		\item \code{ethtool -X eth0 weight 2 1 1 0}
	\end{itemize}
\end{frame}

\begin{frame}{PPv2 example}
	\begin{itemize}
		\item PPv2 is found on Marvell SoCs, such as the Armada 70xx and 80xx
		\item Has a TCAM parser with 256 entries, performing up to 16 matches on 11B
		\item Classifier has one 512 instruction table, subdivided in subflows
		\item Has 4 classification engines :
			\begin{itemize}
				\item \textbf{C2} : TCAM match engine, 8B keys, 256 entries
				\item \textbf{C3} : Exact match engine, 12B keys, 4K entries
				\item \textbf{C4} : Classification and Marking engine, uses if-then-else constructs
				\item \textbf{C3Hx} : Computes hashes, for RSS and C3 lookups.
			\end{itemize}
		\item Can perform drop (in parser or classifier), steer to queue or RSS, limit traffic, modify and redirect packets.
		\item Parser and Classifier is shared between multiple ports
	\end{itemize}
\end{frame}

\begin{frame}{PPv2 : Current support}
	\begin{itemize}
		\item Support for basic RSS
		\item Support steering on 2-tuple, 5-tuple and VLAN tag
		\item MAC and VLAN filtering, performed by the parser
		\item Support steering to RSS tables
		\item All Parser and Classifier configuration is done by the kernel, no firmware involved
		\item Only \code{C2} and \code{C3Hx} engines are used, others are way too complex
	\end{itemize}
\end{frame}

\begin{frame}{Conclusion}
	\begin{itemize}
		\item Offloading classification requires a lot of hardware configuration
		\item Most of the time, we need to limit ourselves to a subset of what the HW can do
		\item There are ongoing efforts to solve the issue of stats reporting
		\item Performance and power consumption improvements make it worth it
		\item In most cases, a firmware is in charge of configuring most of the tables
	\end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
    \Huge
    Thank you! \\
    Questions? Comments?\\
    \vspace{1cm}
    \large
    Maxime Chevallier — \code{maxime.chevallier@bootlin.com}\\
    \vspace{1cm}
    Slides under CC-BY-SA 3.0
    \scriptsize
    \url{https://bootlin.com/pub/conferences/2019/elce/chevallier-network-classification-offload/}
  \end{center}
\end{frame}

\end{document}