# Computationally Efficient Optimization
of Plackett-Luce Ranking Models for Relevance and Fairness

Harrie Oosterhuis  Radboud UniversityNijmegenThe Netherlands
<EMAIL_ADDRESS>
(2021)

###### Abstract.

Recent work has proposed stochastic Plackett-Luce (PL) ranking models as a
robust choice for optimizing relevance and fairness metrics. Unlike their
deterministic counterparts that require heuristic optimization algorithms, PL
models are fully differentiable. Theoretically, they can be used to optimize
ranking metrics via stochastic gradient descent. However, in practice, the
computation of the gradient is infeasible because it requires one to iterate
over all possible permutations of items. Consequently, actual applications
rely on approximating the gradient via sampling techniques.

In this paper, we introduce a novel algorithm: PL-Rank, that estimates the
gradient of a PL ranking model w.r.t. both relevance and fairness metrics.
Unlike existing approaches that are based on policy gradients, PL-Rank makes
use of the specific structure of PL models and ranking metrics. Our
experimental analysis shows that PL-Rank has a greater sample-efficiency and
is computationally less costly than existing policy gradients, resulting in
faster convergence at higher performance. PL-Rank further enables the industry
to apply PL models for more relevant and fairer real-world ranking systems.

Learning to Rank; Policy Gradients; Ranking Metric Optimization

††copyright: rightsretained††journalyear: 2021††copyright:
rightsretained††conference: Proceedings of the 44th International ACM SIGIR
Conference on Research and Development in Information Retrieval; July 11–15,
2021; Virtual Event, Canada††booktitle: Proceedings of the 44th International
ACM SIGIR Conference on Research and Development in Information Retrieval
(SIGIR ’21), July 11–15, 2021, Virtual Event, Canada††doi:
10.1145/3404835.3462830††isbn: 978-1-4503-8037-9/21/07††ccs: Information
systems Learning to rank††submissionid: 100

##  1\. Introduction

Learning to Rank (LTR) is a branch of machine learning that covers methods for
optimizing ranking systems (Liu, 2009). As a result, LTR is very important for
search and recommendation applications that heavily depend on well-functioning
ranking systems. These systems go through large collections of items and
produce a ranking: a small ordered set of items. A good ranking can make it
very easy for the user to find the items they are looking for, even when these
items are part of a very large collection (Chapelle and Chang, 2011; Qin and
Liu, 2013; Dato et al., 2016).

Traditionally, ranking systems consist of a scoring function that assigns an
individual score to each item, and subsequently, produce rankings by sorting
items according to their assigned scores (Liu, 2009; Burges, 2010; Wang et
al., 2018b; Joachims, 2002). The crucial difference with LTR and regression or
classification is that only the relative differences between scores matter. In
other words, in LTR it is not important what the exact score of an item is but
how much greater or smaller it is than the scores of the other items. The main
difficulty in LTR is that the ranking procedure is deterministic and non-
differentiable, since there is no gradient w.r.t. the sorting function. The
methods in the LTR field can be divided in applying one of two solutions:
optimizing a heuristic function that bounds or approximates the ranking
performance (Joachims, 2002; Burges et al., 2005; Liu, 2009; Burges, 2010;
Wang et al., 2018b; Bruch et al., 2019); or optimizing a probabilistic ranking
system (Cao et al., 2007; Xia et al., 2008; Taylor et al., 2008; Oosterhuis
and de Rijke, 2018).

In recent years, the popularity of the Plackett-Luce (PL) ranking model has
increased (Plackett, 1975; Luce, 2012; Burges, 2010; Singh and Joachims, 2019;
Diaz et al., 2020). It models ranking as a succession of decision problems
where each individual decision is made by a PL model (also known as the _Soft-
Max_ in deep learning). Previous research from the industry indicates that the
probabilistic nature of the PL model leads to more robust performance (Bruch
et al., 2020). In online LTR, it appears the PL model is very good at
exploration because it explicitly quantifies its uncertainty (Oosterhuis and
de Rijke, 2018, 2021). Recent work has also posed that the PL model is well
suited to address fairness aspects of ranking (Singh and Joachims, 2019; Diaz
et al., 2020), because unlike deterministic models, it can give multiple items
an equal probability of being the top-item.

However, calculating the gradient of a PL ranking model requires an iteration
over every possible ranking that the model could produce, i.e., every possible
permutation. In practice this computational infeasibility is circumvented by
estimating the gradient based on rankings sampled from the model (Oosterhuis
and de Rijke, 2020, 2021; Singh and Joachims, 2019; Diaz et al., 2020). The
main downside of this approach is that it can be computationally very costly.
This is a particular problem in online settings where optimization is
performed periodically as more data is gathered (Oosterhuis and de Rijke,
2020, 2021; Singh and Joachims, 2019; Morik et al., 2020).

In this paper, we introduce PL-Rank a novel method that can efficiently
optimize both relevance and exposure-based fairness ranking metrics or linear
combinations of them. We contribute to the theory of the LTR field, by
deriving novel estimators that can unbiasedly estimate the gradient of a PL
ranking model w.r.t. a ranking metric, on which PL-Rank is build. To the best
of our knowledge, PL-Rank is the first LTR method that utilizes specific
properties of ranking metrics and the PL-ranking model. Our experimental
results show that compared to existing LTR methods, PL-Rank has increased
sample-efficiency: it requires less sampled rankings to reach the same
performance, and increased computational time-efficiency: PL-Rank requires
less time to compute the estimation of the gradient and less computational
time to converge at optimal performance. The introduction of PL-Rank makes the
optimization of PL ranking models more practical by greatly reducing its
computational costs, additionally, these gains also help in the further
promotion of fairness aspects of ranking models (Diaz et al., 2020).

##  2\. Related Work

One of the earliest LTR approaches is the pairwise approach where the loss
function is based on the order of pairs of items (Joachims, 2002; Burges et
al., 2005; Liu, 2009). While pairwise losses are easy to compute and scale
well with the number of items to rank, pairwise loss functions do not consider
the entire ranking (Burges, 2010; Liu, 2009). As a result, minimizing a
pairwise loss often does not translate to the optimal ranking behavior.
Subsequently, the idea of a listwise method that considers the complete
ranking was introduced with the ListNet and ListMLE methods (Cao et al., 2007;
Xia et al., 2008). These methods optimize PL ranking models to maximize the
probability of the optimal ranking. They have three main limitations:  (i)
They assume there is a single optimal ranking per query, while often there are
multiple optimal rankings.  (ii) They are not based on actual ranking metrics
and thus may not actually maximize the desired metrics over the entire
dataset.  (iii) They bring substantial computational costs, i.e. the cost of
ListNet is so high Cao et al. only optimize the top-1 ranking (Cao et al.,
2007).  Some of these issues are avoided by the later _LambdaRank_ and
_LambdaMART_ methods (Burges, 2010). LambdaRank is an extension of the
pairwise _RankNet_ method, where the loss function weights each pair by the
absolute difference in Discounted Cumulative Gain (DCG) that would result from
swapping the pair. This approach optimizes a deterministic ranking model and
also works for other ranking metrics than DCG (Burges, 2010; Wang et al.,
2018b). The Lambda methods are listwise because their gradient is based on the
ranking metric values of the current ranking and therefore consider the
complete ranking. While initially, there was only empirical evidence for the
great performance of Lambda methods in optimizing ranking metrics (Burges,
2010; Donmez et al., 2009). Recently, Wang et al. (2018b) proved that the
Lamba methods optimize a lower bound on ranking metrics and introduced a novel
bound in the form of the LambdaLoss framework (Wang et al., 2018b). Thus
although the Lamba methods are based around ranking metrics and are
computationally feasible, they do not optimize metrics directly and are
therefore heuristic methods. Another heuristic approach is to replace the rank
function in a metric by a differentiable probabilistic approximation, notable
examples of this approach are _SoftRank_ (Taylor et al., 2008) and
_ApproxNDCG_ (Bruch et al., 2019). While all of these methods can be useful in
practice, none optimize rankings metrics directly in a computationally
feasible manner.

Interestingly, multiple lines of previous work have found PL-ranking models to
be very effective for various ranking tasks: for result randomization in
interleaving (Hofmann et al., 2011), multileaving (Schuth et al., 2015) and
counterfactual evaluation (Oosterhuis and de Rijke, 2020); for exploration in
online LTR (Oosterhuis and de Rijke, 2021, 2018); for fair distributions of
attention exposure (Singh and Joachims, 2019; Diaz et al., 2020); and for
topic diversity in ranking (Xia et al., 2017; Wei et al., 2017). In
particular, Bruch et al. (2020) argue that the stochastic nature of PL models
results in more robust ranking performance. Furthermore, Bruch et al. show
that, with small alterations, many existing LTR methods can adequately
optimize PL methods. An interesting property of the PL ranking model is that
it has a gradient w.r.t. ranking metrics but that it is generally infeasible
to compute, existing work has thus approximated this gradient (Oosterhuis and
de Rijke, 2020, 2021; Singh and Joachims, 2019; Diaz et al., 2020) (see
Section 4). The computational costs are particularly relevant because the PL
model is often used in online settings where it optimization is performed
repeatedly and frequently (Oosterhuis and de Rijke, 2020, 2021; Singh and
Joachims, 2019). For instance, Oosterhuis and de Rijke (2021) show that
frequently optimizing the logging-policy model during the gathering of data
greatly reduces the data-requirements for online/counterfactual LTR.
Similarly, Morik et al. (2020) show that to prevent very unfair distributions
of exposure, rankings should be updated continuously as more interaction data
is gathered. To the best of our knowledge, no previous work has developed a
novel LTR method specifically for PL ranking models that optimizes ranking
metrics directly nor with a focus on computational efficiency.

##  3\. Relevance Ranking Metrics

Generally, LTR methods assume each item $d$ has some _relevance_ w.r.t. a
query $q$ (Liu, 2009), in the context of fairness this is often considered the
_merit_ of an item (Diaz et al., 2020). This is often modelled as the
probability that a user finds the item $d$ relevant for their issued query
$q$. To keep our notation brief, we use $\rho_{d}$ to denote this probability:
$P(R=1\,|\,q,d)=\rho_{d}.$ Whenever we talk about the relevance of an item, it
will be clear from the context what the corresponding query is, hence we keep
$q$ out of our notation for the sake of brevity.

Rankings are ordered lists of items, we use $y$ to denote a ranking and
$y_{k}$ for the $k$th item in ranking $y$: $y=[y_{1},y_{2},\ldots,y_{K}],$
thus $y_{k}=d$ means that $d$ is the item at rank $k$ in ranking $y$. We will
assume that all rankings are of length $K$, for instance, because only $K$
items can be displayed. A ranking model $\pi$ can be seen as a distribution
over rankings, where $\pi(y\mid q)$ indicates the probability that ranking $y$
is sampled for query $q$ by model $\pi$. For brevity, we will use
$\pi(y)=\pi(y\mid q)$ as the corresponding query will always be clear from the
context.

The relevance performance (also called the reward) of a ranking model is
represented by the metric value $\mathcal{R}$. Relevance ranking metrics use
weights per rank $\theta$ where the relevance of an item at rank $k$ is
weighted by $\theta_{k}$. For a single query, the metric is computed as an
expectation over the ranking behavior of $\pi$:

(1)
$\begin{split}\mathcal{R}(q)&=\sum_{y\in\pi}\pi(y\,|\,q)\sum_{k=1}^{K}\theta_{k}P(R=1\,|\,q,y_{k})\\\
&=\sum_{y\in\pi}\pi(y)\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}=\mathbb{E}_{y}\left[\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}\right].\end{split}$

By choosing $\theta_{k}$ accordingly, $\mathcal{R}(q)$ can represent the most
common relevance ranking metrics. For example, top-$K$ DCG is computed with
the following weights: $\theta_{k}^{\text{DCG@K}}=\frac{\mathds{1}[k\leq
K]}{\log_{2}(k+1)}$, precision at $K$ with:
$\theta_{k}^{\text{PREC@K}}=\frac{1}{K}\mathds{1}[k\leq K]$, or Average
Relevance Position (ARP) can be represented by: $\theta_{k}^{\text{ARP}}=-k$.
The overall relevance of a ranking system $\pi$ is simply the expected
performance over the distribution of user-issued queries:

(2)
$\mathcal{R}=\mathbb{E}_{q}\left[\mathcal{R}(q)\right]=\sum_{q\in\mathcal{Q}}P(q)\mathcal{R}(q).$

The value of $\mathcal{R}$ is also often called the _performance_ or the
_reward_. Accordingly, LTR for relevance optimizes $\pi$ to maximize
$\mathcal{R}$, given the item relevances $\rho_{d}$ and according to the
chosen metric represented by $\theta_{k}$.

##  4\. Plackett-Luce Ranking Models

As noted in Section 2, the PL model (Plackett, 1975; Luce, 2012) has often
been deployed to model a probabilistic distribution over rankings (Hofmann et
al., 2011; Oosterhuis and de Rijke, 2020, 2021, 2018; Singh and Joachims,
2019; Diaz et al., 2020; Xia et al., 2017; Wei et al., 2017; Bruch et al.,
2020). In the PL model, an item is chosen from a pool of available items based
on the individual scores each item has. For our ranking problem, a learned
prediction model $m$ predicts the log score of an item $d$ w.r.t. to query $q$
as $m(q,d)\in\mathds{R}$. For brevity, we again keep the query out of our
notation: $m(q,d)=m(d)$.

The probability that item $d$ is chosen to be the $k$th item in ranking $y$
from the set of items $\mathcal{D}$ is the score of $d$: $e^{m(d)}$, divided
by the sum of scores for the items that have not been placed yet:

(3) $\pi(d\,|\,y_{1:k-1},\mathcal{D})=\frac{e^{m(d)}\mathds{1}[d\not\in
y_{1:k-1}]}{\sum_{d^{\prime}\in D\setminus y_{1:k-1}}e^{m(d^{\prime})}},$

where $y_{1:k-1}$ indicates the ranking up to rank $k-1$, i.e.,

(4) $y_{1:k-1}=[y_{1},y_{2},\ldots,y_{k-1}].$

As such the placement probabilities at $k$ depend only on the scores of the
items not placed before rank $k$. Because the learned $m$ predicts the log
score, the actual score is always greater than zero: $e^{m(d)}>0$,
consequently, $\pi(d\,|\,y_{1:k-1})$ is always a valid probability
distribution over the unplaced items. We note that this probability is
extremely similar to the Soft-Max function commonly used in deep learning. To
prevent items from appearing in a ranking twice, the probability of
$\pi(d\,|\,y_{1:k-1},\mathcal{D})=0$ if $d$ has already been placed: $d\in
y_{1:k-1}$.

Finally, the probability of a ranking is simply the product of the placement
probabilities of each individual item:

(5) $\pi(y)=\prod_{k=1}^{K}\pi(y_{k}\,|\,y_{1:k-1},\mathcal{D}).$

###  4.1. Computationally Efficient Sampling

An advantage of the PL ranking model is that rankings can be sampled quite
efficiently. At first glance, sampling a ranking may seem computationally
costly, as it involves repeatedly sampling from the item distribution and
renormalizing it. However, using the Gumbel Softmax trick (Gumbel, 1954) one
can sample an entire ranking without having to calculate any of the actual
probabilities (Bruch et al., 2020).

Our goal is to acquire a sampled ranking $y^{(i)}$ from the $\pi$
distribution: $y^{(i)}\sim\pi$. Instead of calculating the actual placement
probabilities, for each item a sample from the Gumbel distribution is taken:
$\gamma^{(i)}_{d}\sim\text{Gumbel}(0,0).$ This can be done by first sampling
uniformly from the $[0,1]$ range: $\zeta^{(i)}_{d}\sim\text{Uniform}(0,1)$,
and then applying: $\gamma^{(i)}_{d}=-\log(-\log(\zeta^{(i)}_{d}))$.
Subsequently, per item we take the sum of their Gumbel sample and their log
score:

(6) $\hat{m}^{(i)}_{d}=m(d)+\gamma^{(i)}_{d}.$

Finally, we sort the items according to their $\hat{m}^{(i)}$ values,
resulting in the sampled ranking:

(7) $\begin{split}y^{(i)}&=[y_{1}^{(i)},y_{2}^{(i)},\ldots,y_{K}^{(i)}]\\\
&\text{s.t. }\,\,\,\forall(y_{x}^{(i)},y_{z}^{(i)}),\quad
x<z\rightarrow\hat{m}^{(i)}_{y_{x}}\geq\hat{m}^{(i)}_{y_{z}}.\end{split}$

This sampling procedure follows the PL distribution of $\pi$ (Gumbel, 1954;
Bruch et al., 2020). In practice, this means we can sample rankings as quickly
as we can sort top-$K$ rankings, which translates to a computational
complexity of $\mathcal{O}(|\mathcal{D}|\log(|\mathcal{D}|))$.

###  4.2. Basic Policy Gradient Estimation

As noted by Singh and Joachims (2019) and Bruch et al. (2020), PL ranking
models can be optimized via policy-gradients. They utilize the famous _log-
trick_ from the _REINFORCE_ algorithm (Williams, 1992). We apply the log-trick
to Eq. 5 to obtain:

(8) $\frac{\delta}{\delta m}\pi(y)=\pi(y)\left[\frac{\delta}{\delta
m}\log(\pi(y))\right].$

By combining this result with Eq. 1, we find that the derivate can be
expressed as an expectation over the ranking distribution $\pi$:

(9) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)&=\sum_{y\in\pi}\left[\frac{\delta}{\delta
m}\pi(y)\right]\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}\\\
&=\sum_{y\in\pi}\pi(y)\left[\frac{\delta}{\delta
m}\log(\pi(y))\right]\left(\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}\right)\\\
&=\mathbb{E}_{y}\Bigg{[}\underbrace{\vphantom{\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)}\left[\frac{\delta}{\delta
m}\log(\pi(y))\right]}_{\text{gradient w.r.t.\ complete
ranking}}\underbrace{\left(\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}\right)}_{\text{full
reward}}\Bigg{]}.\end{split}$

We see that this policy gradient is composed of two parts: a gradient w.r.t.
the log probability of a complete ranking multiplied by the reward for that
ranking. In practice, it is infeasible to compute this gradient exactly since
it requires a summation over every possible ranking $y$. Luckily, because the
gradient can be expressed as an expectation over ranking $y$ w.r.t. to the
distribution according to $\pi$, the gradient can be estimated using a simple
sampling strategy. If we sample $N$ rankings from $\pi$ for query $q$, with
$y^{(i)}$ denoting the $i$th sample, then the gradient can be estimated using:

(10) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)\approx\frac{1}{N}\sum_{i=1}^{N}\left[\frac{\delta}{\delta
m}\log(\pi(y^{(i)}))\right]\left(\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}^{(i)}}\right).\end{split}$

A straightforward implementation first samples $N$ rankings using Gumbel
sampling (Section 4.1), and then computes the reward for each ranking, to
finally use a machine learning framework to compute the gradient w.r.t. the
log probabilities: $\left[\frac{\delta}{\delta m}\log(\pi(y^{(i)}))\right]$.
This approach works well with currently popular deep-learning frameworks such
as _PyTorch_ (Paszke et al., 2019) or _Tensorflow_ (Abadi et al., 2016).

This concludes our description of the basic policy gradient approach to
optimizing PL ranking models. While this approach works adequately, our
results show that this approach is computationally expensive and can have
convergency issues when $N<1000$. Finally, we note that this approach is not
specific to PL-ranking models as it essentially just applies the very general
_REINFORCE_ algorithm (Williams, 1992). In contrast, the remainder of this
paper will introduce methods that make use of specific PL properties, and as a
result, show better performance in our experimental results.

##  5\. Method: PL-Rank for Relevance

In this section, we will derive three novel methods for estimating the
gradient of a PL-ranking model. The latter two estimators make our proposed
PL-Rank method, the former is an intermediate step between the basic policy
gradient estimation and PL-Rank. Unlike existing methods, PL-Rank utilizes
specific properties about PL ranking models and ranking metrics.

###  5.1. Ranking Metric Based Approximation

The basic estimator in Eq. 10 only deals with the reward of the entire
ranking. This can lead to very unintuitive behavior, for instance, when a
ranking is sampled that receives a very high reward but only due the first
placed item, the gradient w.r.t. entire ranking will be multiplied with this
reward. Thus despite the fact that only the first item contributed positively
to the reward, the probability of placement for all items will be increased.

By rewriting Eq. 1 we can see that relevance rewards only need to interact
with the probability of the ranking up to the corresponding rank:

(11)
$\begin{split}\mathcal{R}(q)&=\sum_{y\in\pi}\pi(y)\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}=\sum_{k=1}^{K}\theta_{k}\sum_{y\in\pi}\pi(y)\rho_{y_{k}}\\\
&=\sum_{k=1}^{K}\theta_{k}\sum_{y_{1:k}\in\pi}\pi(y_{1:k})\rho_{y_{k}},\end{split}$

where $\sum_{y_{1:k}\in\pi}$ is a summation over all possible (sub)rankings of
length $k$ according to $\pi$. In other words, the relevance $\rho_{y_{k}}$ at
any rank $k$ only interacts with the probability of the ranking up to $k$:
$\pi(y_{1:k})$. Inuitively this makes sense because the placement of any item
after $k$ will not affect the previously obtained reward. We can use this fact
when estimating the gradient w.r.t. the complete reward.

Before we derive the gradient w.r.t. the complete reward, we first consider
that the derivate of the log probability of a ranking can be decomposed as a
sum over log probabilities of the individual item placements. Using Eq. 5:

(12) $\begin{split}\left[\frac{\delta}{\delta
m}\pi(y_{1:k})\right]&=\pi(y_{1:k})\left[\frac{\delta}{\delta
m}\log(\pi(y_{1:k}))\right]\\\
&=\pi(y_{1:k})\sum_{x=1}^{k}\left[\frac{\delta}{\delta m}\log(\pi(y_{x}\mid
y_{1:x-1}))\right].\end{split}$

We can now use to get the derivative w.r.t. to $\mathcal{R}(q)$ using Eq. 11 &
12:

$\displaystyle\frac{\delta}{\delta m}\mathcal{R}(q)$
$\displaystyle=\sum_{k=1}^{K}\theta_{k}\sum_{y_{1:k}\in\pi}\rho_{y_{k}}\left[\frac{\delta}{\delta
m}\pi(y_{1:k})\right]$
$\displaystyle=\sum_{k=1}^{K}\theta_{k}\sum_{y_{1:k}\in\pi}\pi(y_{1:k})\rho_{y_{k}}\sum_{x=1}^{k}\left[\frac{\delta}{\delta
m}\log(\pi(y_{x}|y_{1:x-1}))\right]$ (13)
$\displaystyle=\sum_{k=1}^{K}\mathbb{E}_{y_{1:k}}\left[\theta_{k}\rho_{y_{k}}\sum_{x=1}^{k}\left[\frac{\delta}{\delta
m}\log(\pi(y_{x}\mid y_{1:x-1}))\right]\right]$
$\displaystyle=\mathbb{E}_{y}\left[\sum_{k=1}^{K}\theta_{k}\rho_{y_{k}}\sum_{x=1}^{k}\left[\frac{\delta}{\delta
m}\log(\pi(y_{x}\mid y_{1:x-1}))\right]\right]$
$\displaystyle=\mathbb{E}_{y}\Bigg{[}\sum_{k=1}^{K}\underbrace{\vphantom{\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}}\left[\frac{\delta}{\delta
m}\log(\pi(y_{k}\mid y_{1:k-1}))\right]}_{\text{grad.\ w.r.t.\ item placement
}}\underbrace{\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)}_{\text{
following reward}}\Bigg{]},$

note that we use following:
$\sum_{k=1}^{K}\mathbb{E}_{y_{1:k}}\left[f(y_{1:k})\right]=\mathbb{E}_{y}\left[\sum_{k=1}^{K}f(y_{1:k})\right]$,
to move the expectation from partial rankings to complete rankings. Eq. 5.1
shows us that the derivative consists of two parts: the gradient w.r.t.
individual item placements and the reward received following each placement.
Again, this gradient can be estimated using rankings sampled from $\pi$:

(14) $\frac{\delta}{\delta
m}\mathcal{R}(q)\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{k=1}^{K}\left[\frac{\delta}{\delta
m}\log(\pi(y_{k}^{(i)}|y_{1:k-1}^{(i)}))\right]\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}^{(i)}}.$

We will call this estimator the _placement policy gradient estimator_ , in
contrast with the basic policy gradient estimator (Eq. 10), this estimator
weights the gradients of placement probabilities with the observed following
rewards. By doing so, it makes use of the structure of ranking metrics and
thus is more tailored towards these metrics than the basic estimator.

###  5.2. Computationally Efficient Estimation

So far our placement policy gradient estimator has made use of the fact that
the probability of a ranking is a product of individual placement
probabilities, however, it has made no further use of the fact that $\pi$ is a
PL ranking model. We will now show that using the knowledge that $\pi$ is a PL
model can lead to an estimator that can be computed with greater computational
efficiency. We start by taking the derivative of an item placement
probability:

(15) $\displaystyle\frac{\delta}{\delta m}$ $\displaystyle\pi(d\mid
y_{1:k-1})=$ $\displaystyle\pi(d\mid
y_{1:k-1})\left(\left[\frac{\delta}{\delta
m}m(d)\right]-\sum_{d^{\prime}\in\mathcal{D}}\pi(d^{\prime}\mid
y_{1:k-1})\left[\frac{\delta}{\delta m}m(d^{\prime})\right]\right).$

We note that the probability of placing an item that has already been placed
is zero: $d\in y_{1:k-1}\rightarrow\pi(d\mid y_{1:k-1})=0$. Combining Eq. 5.1
& 15 results in the following gradient:

$\displaystyle\frac{\delta}{\delta m}\mathcal{R}(q)$
$\displaystyle=\mathbb{E}_{y}\Bigg{[}\sum_{k=1}^{K}\vphantom{\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}}\left[\frac{\delta}{\delta
m}\log(\pi(y_{k}\mid
y_{1:k-1}))\right]\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\Bigg{]}$ (16)
$\displaystyle=\mathbb{E}_{y}\Bigg{[}\left(\sum_{k=1}^{K}\left[\frac{\delta}{\delta
m}m(y_{k})\right]\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\right)$
$\displaystyle\hskip
9.95863pt-\Bigg{(}\sum_{k=1}^{K}\sum_{d^{\prime}\in\mathcal{D}}\pi(d^{\prime}\mid
y_{1:k-1})\left[\frac{\delta}{\delta
m}m(d^{\prime})\right]\Bigg{)}\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\Bigg{]}.$

For the sake of simplicity, we will further derive the resulting two parts of
Eq. 16 separately, starting with the first part:

(17)
$\begin{split}\mathbb{E}_{y}&\Bigg{[}\left(\sum_{k=1}^{K}\left[\frac{\delta}{\delta
m}m(y_{k})\right]\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\right)\Bigg{]}\\\
&=\mathbb{E}_{y}\Bigg{[}\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\left(\sum_{k=1}^{K}\mathds{1}[y_{k}=d]\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\right)\Bigg{]}\\\
&=\mathbb{E}_{y}\Bigg{[}\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\left(\sum_{k=1}^{K}\mathds{1}[d\in
y_{1:k}]\theta_{k}\rho_{y_{k}}\right)\Bigg{]}\\\
&=\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\mathbb{E}_{y}\Bigg{[}\sum_{k=\text{rank}(d,y)}^{K}\theta_{k}\rho_{y_{k}}\Bigg{]}.\end{split}$

We see that this first part results in summing over the derivatives of each
item score according to model $m(d)$ weighted by the reward expected to follow
a placement of $d$.

Then for the second part of Eq. 16:

(18)
$\begin{split}&\mathbb{E}_{y}\Bigg{[}\sum_{k=1}^{K}\sum_{d\in\mathcal{D}}\pi(d\mid
y_{1:k-1})\left[\frac{\delta}{\delta
m}m(d)\right]\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\Bigg{]}\\\
&\,=\mathbb{E}_{y}\Bigg{[}\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\sum_{k=1}^{K}\pi(d\mid
y_{1:k-1})\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\Bigg{]}\\\
&\,=\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\mathbb{E}_{y}\Bigg{[}\sum_{k=1}^{\text{rank}(d,y)}\pi(d\mid
y_{1:k-1})\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\Bigg{]},\end{split}$

where we used the fact that: $k>\text{rank}(d,y)\rightarrow\pi(d\mid
y_{1:k-1})=0$. We see that the second part sums over each rank where it
multiplies the expected probability that an item was added with the expected
following reward. This product represents the _risk_ imposed by an item $d$:
if $d$ is not placed at $k$ then $\pi(d\mid y_{1:k-1})$ indicates how likely
$d$ would have been placed instead of $y_{k}$ and in which case the following
reward $\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}$ may not have occurred. For cases
where $d$ is the item at rank $k$: $d=y_{k}$, the risk stops the log score
$m(d)$ from increasing too far as the placement probability $\pi(d\mid
y_{1:k-1})$ may already be very great. By combining Eq. 16, 17 & 18 we obtain
the full derivative:

(19) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)&=\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\mathbb{E}_{y}\Bigg{[}\overbrace{\left(\sum_{k=\text{rank}(d,y)}^{K}\theta_{k}\rho_{y_{k}}\right)}^{\text{reward
following placement}}\\\
&\qquad\qquad-\underbrace{\sum_{k=1}^{\text{rank}(d,y)}\pi(d\mid
y_{1:k-1})\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)}_{\text{risk
imposed by placement probability}}\Bigg{]}.\end{split}$

We see that the derivative multiplies the gradient of the item log score
$m(d)$ with the expected reward following its placement minus the expected
risk imposed by $d$ before it is placed. Finally, this gradient can also be
estimated using $N$ sampled rankings:

(20) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)&\approx\frac{1}{N}\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\sum_{i=1}^{N}\left(\sum_{k=\text{rank}(d,y^{(i)})}^{K}\theta_{k}\rho_{y_{k}^{(i)}}\right)\\\
&\qquad\quad\,-\sum_{k=1}^{\text{rank}(d,y^{(i)})}\pi(d\mid
y_{1:k-1}^{(i)})\left(\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}^{(i)}}\right).\end{split}$

We call this estimator _PL-Rank-1_ , to the best of our knowledge this is the
first gradient estimation method that is specifically designed for optimizing
PL-ranking models w.r.t. ranking metrics. While both the placement policy
gradient estimator (Eq. 14) and PL-Rank-1 (Eq. 20) estimate the same gradient,
their formulas look radically different. A big advantage of PL-Rank-1 is that
it can be computed with a time-complexity of $\mathcal{O}(N\cdot K\cdot D)$.
Our experimental results indicate that while both estimators have comparable
sample-efficiency, PL-Rank-1 requires considerably less time to compute than
using a machine learning framework to automatically compute the placement
policy gradient.

###  5.3. Improving Sample-Efficiency

In Eq. 19 we see that an item receives a positive weight from the expected
following reward. Therefore, even when an item has a low probability of being
placed it can compensate with a high relevance ($\rho_{d}$) to get a positive
weight. However, when an estimate of the gradient is based on a low number of
samples ($N$), they may not include a ranking where such an item is placed at
all and thus these items will nevertheless receive a negative weight in the
estimate. We propose one last estimator to mitigate this potential issue.

First, we can rewrite the expected reward following placement so that the
reward obtained from $d$ and that from items placed afterwards are separated:

(21) $\begin{split}\mathbb{E}_{y}&\hskip
7.39755pt\left[\sum_{k=\text{rank}(d,y)}^{K}\theta_{k}\rho_{y_{k}}\right]\\\
&=\mathbb{E}_{y}\left[\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\rho_{y_{k}}\right)+\theta_{\text{rank}(d,y)}\rho_{d}\right]\\\
&=\mathbb{E}_{y}\left[\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\rho_{y_{k}}\right)+\sum_{k=1}^{K}\pi(d\mid
y_{1:k-1})\theta_{k}\rho_{d}\right]\\\
&=\mathbb{E}_{y}\left[\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\rho_{y_{k}}\right)+\sum_{k=1}^{\text{rank}(d,y)}\pi(d\mid
y_{1:k-1})\theta_{k}\rho_{d}\right],\end{split}$

where again we make use of the fact that:
$k>\text{rank}(d,y)\rightarrow\pi(d\mid y_{1:k-1})=0$. Combining this result
with Eq. 19 we get:

(22) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)&=\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\mathbb{E}_{y}\Bigg{[}\overbrace{\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\rho_{y_{k}}\right)}^{\text{future
reward after placement}}\\\
&\quad\,\,\,\,+\underbrace{\sum_{k=1}^{\text{rank}(d,y)}\pi(d\mid
y_{1:k-1})\left(\theta_{k}\rho_{d}-\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)}_{\text{expected
direct reward minus the risk of placement}}\Bigg{]}.\end{split}$

We see that the gradient w.r.t. an item’s log score $m(d)$ is weighted by the
reward after placement (not including the reward from $d$) plus the expected
direct reward (the reward from $d$) minus the expected risk imposed by $d$
before its placement. From Eq. 22 we can derive the following novel estimator:

(23) $\begin{split}\frac{\delta}{\delta
m}\mathcal{R}(q)&\approx\frac{1}{N}\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\sum_{i=1}^{N}\left(\sum_{k=\text{rank}(d,y^{(i)})+1}^{K}\theta_{k}\rho_{y_{k}^{(i)}}\right)\\\
&\hskip 22.76228pt+\sum_{k=1}^{\text{rank}(d,y^{(i)})}\pi(d\mid
y_{1:k-1}^{(i)})\left(\theta_{k}\rho_{d}-\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}^{(i)}}\right).\end{split}$

We will call this estimator: _PL-Rank-2_. Unlike PL-Rank-1 (Eq. 20), PL-Rank-2
can provide a positive weight to items that were not in the top-K of any of
the $N$ sampled rankings. While this is expected to increase the sample-
efficiency, it does not come at the cost of computational complexity as both
PL-Rank-1 and PL-Rank-2 have a complexity of $\mathcal{O}(N\cdot K\cdot D)$.

###  5.4. The PL-Rank Algorithm

Finally, we will show how PL-Rank-2 can be implemented efficiently. Our goal
is to compute a $\lambda_{d}$ weight per item $d$ so that the gradient is
estimated by:

(24) $\frac{\delta}{\delta
m}\mathcal{R}(q)\approx\frac{1}{N}\sum_{d\in\mathcal{D}}\lambda_{d}\left[\frac{\delta}{\delta
m}m(d)\right],$

where following Eq. 23 these weights are:

(25)
$\begin{split}\lambda_{d}=\frac{1}{N}\sum_{i=1}^{N}&\Bigg{(}\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\rho_{y_{k}}\right)\\\
&\,\,+\sum_{k=1}^{\text{rank}(d,y)}\pi(d\mid
y_{1:k-1})\left(\theta_{k}\rho_{d}-\sum_{x=k}^{K}\theta_{x}\rho_{y_{x}}\right)\Bigg{)}.\end{split}$

Algorithm 1 displays the PL-Rank-2 algorithm in pseudo-code. As input it
requires the item collection $\mathcal{D}$, the relevances $\rho$, the (pre-
computed) log scores per item $m(d)$ according to the current model $m$, the
metric weights per rank $\theta$, and finally, the number of rankings to
sample $N$ (Line 1). First, $N$ rankings are sampled using Gumbel sampling
(Line 2) and zero weights are initialized for every $\lambda$ (Line 2).
Subsequently, the initial denominator for the PL model is computed and stored
(Line 4). Then the algorithm starts iterating over each of the sampled
rankings, where first, the rewards following each rank $k$ are precomputed
(Line 9). Second, it loops over every rank $k$ where it adds the following
reward to the $\lambda_{d}$ of $d$ at rank $k$ in the sampled ranking (Line
11), thus computing the first part of Eq. 23. For every item, the placement
probability $\pi(d\mid y_{k}^{(i)})$ is computed (Line 14) and multiplied by
the difference between the item’s direct reward and the following reward (Line
15), this is added to $\lambda_{d}$ to compute the second part of Eq. 23.
Finally, the denominator is updated to account for the item placed at rank $k$
(Line 16).

Algorithm 1 reveals that PL-Rank-2 can be computed in $\mathcal{O}(N\cdot
K\cdot D)$, we note that with small alterations to Line 11 and 15 PL-Rank-1
can be computed with this algorithm as well.

Algorithm 1 PL-Rank-2 Gradient Estimation

1: Input: items: $\mathcal{D}$; Relevances: $\rho$; Metric weights: $\theta$;
Input Scores: $m$; Number of samples: $N$.

2: $\\{y^{(1)},y^{(2)},\dots,y^{(N)}\\}\leftarrow\text{Gumbel\\_Sample}(N,m)$

3: $\lambda\leftarrow\mathbf{0}$ // initialize zero weight per item

4: $M\leftarrow\sum_{d\in\mathcal{D}}\exp(m(d))$ // initialize PL denominator

5: for $i\in[1,2,\ldots,N]$ do

6: $M^{\prime}\leftarrow M$ // copy initial PL denominator

7: $\omega_{K}\leftarrow\theta_{K}\rho_{y_{K}^{(i)}}$ // reward for last rank

8: for $k\in[K-1,K-2,\ldots,1]$ do

9: $\omega_{k}\leftarrow\omega_{k+1}+\theta_{k}\rho_{y_{k}^{(i)}}$ // pre-
compute reward following rank $k$

10: for $k\in[1,2,\ldots,K]$ do

11: $\lambda_{y_{k}^{(i)}}\leftarrow\lambda_{y_{k}^{(i)}}+\omega_{k+1}$ // add
future reward $k$

12: for $d\in\mathcal{D}$ do

13: if $d\not\in y_{1:k-1}^{(i)}$ then

14: $P\leftarrow(\exp(m(d))/M^{\prime})$ // placement probability

15: $\lambda_{d}\leftarrow\lambda_{d}+P\cdot(\theta_{k}\rho_{d}-\omega_{k})$
// 2nd part of Eq. 23

16: $M^{\prime}\leftarrow M^{\prime}-\exp(m(y_{k}^{(i)}))$ // renormalize
denominator

17: return $\frac{1}{N}\lambda$

##  6\. Method: PL-Rank for Fairness

So far we have introduced the PL-Rank algorithms for estimating the gradient
of a PL ranking model w.r.t. a relevance metric. However, the applicability of
these algorithms are much wider than just relevance metrics, in particular,
they can be applied to any _exposure-based_ metrics (Singh and Joachims, 2019;
Diaz et al., 2020; Morik et al., 2020; Biega et al., 2018). Exposure
represents the expected number of people that will examine an item. In
general, user behavior has _position-bias_ which means that they are less
likely to examine an item if it displayed at a lower rank (Wang et al., 2018a;
Craswell et al., 2008). Let the rank weight $\theta_{k}$ indicate the
probability that a user examines an item at rank $k$, then the exposure an
item $d$ receives under $\pi$ is:

(26)
$\mathcal{E}(q,d)=\mathbb{E}_{y}\left[\sum_{k=1}^{K}\theta_{k}\mathds{1}[y_{k}=d]\right]=\sum_{y\in\pi}\pi(y)\sum_{k=1}^{K}\theta_{k}\mathds{1}[y_{k}=d],$

where again for brevity we denote $\mathcal{E}_{d}=\mathcal{E}(q,d)$. Thus
$\mathcal{E}_{d}$ could be interpreted as the probability that a user examines
$d$ when $\pi$ is deployed. Most fairness metrics for rankings consider how
exposure is distributed over items and specifically how _fair_ this
distribution is. Regardless of the exact metric, PL-Rank can be applied to a
fairness metric $\mathcal{F}$ if the chain-rule can be applied as follows:

(27) $\frac{\delta}{\delta
m}\mathcal{F}(q)=\sum_{d\in\mathcal{D}}\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}\frac{\delta\mathcal{E}_{d}}{\delta
m}.$

To derive this gradient, we first note that the $\mathcal{E}_{d}$ (Eq. 26) and
$\mathcal{R}(q)$ (Eq. 1) are equivalent if $\forall
d^{\prime}\,\rho_{d^{\prime}}=\mathds{1}[d^{\prime}=d]$, therefore if we
replace $\rho$ in PL-Rank-2 (Eq. 22) accordingly, it will provide us the
gradient $\frac{\delta\mathcal{E}_{d}}{\delta m}$. If we combine this fact
with Eq. 27 we obtain the following PL-Rank-2 based gradient:

(28) $\displaystyle\frac{\delta}{\delta m}\mathcal{F}$
$\displaystyle(q)=\sum_{d\in\mathcal{D}}\left[\frac{\delta}{\delta
m}m(d)\right]\mathbb{E}_{y}\Bigg{[}\left(\sum_{k=\text{rank}(d,y)+1}^{K}\theta_{k}\left[\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{y_{k}}}\right]\right)$
$\displaystyle+\sum_{k=1}^{\text{rank}(d,y)}\pi(d\,|\,y_{1:k-1})\left(\theta_{k}\left[\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}\right]-\sum_{x=k}^{K}\theta_{x}\left[\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{y_{x}}}\right]\right)\Bigg{]}.$

In other words, we can apply PL-Rank by simply replacing the item relevances
with the gradients: $\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}$
before computation. Similarly, any linear combination of $\mathcal{R}$ and
$\mathcal{F}$ can be optimized by replacing the relevances with the
corresponding linear combination between $\rho_{d}$ and
$\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}$.

For instance, we can follow Singh and Joachims (2019) and choose a disparity-
based metric. This metric measures the disparity between two items via a
function $D(d,d^{\prime})$ and takes the average disparity over all item
pairs:

(29)
$\mathcal{F}(q)=\frac{1}{|\mathcal{D}|(|\mathcal{D}|-1)}\sum_{d\in\mathcal{D}}\sum_{d^{\prime}\in\mathcal{D}}D(d,d^{\prime}).$

Singh and Joachims (2019) divide the exposure of an item $d$ by its relevance:
$\frac{\mathcal{E}_{d}}{\rho_{d}}$ to model the proportion between the
exposure and the merit of an item. However, in our experimental datasets many
items have zero relevances, thus making such a division impossible. Instead,
we introduce a novel alternative disparity measure:

(30)
$D(d,d^{\prime})=\left(\mathcal{E}_{d^{\prime}}\rho_{d}-\mathcal{E}_{d}\rho_{d^{\prime}}\right)^{2}.$

This measure looks at the reward item $d$ would receive if it had the exposure
of $d^{\prime}$: $\mathcal{E}_{d^{\prime}}\rho_{d}$, in other words, the
reward $d$ would receive if it was treated as $d^{\prime}$ is. This measure
can handle items without merit and has the gradient:

(31)
$\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}=\frac{4}{|\mathcal{D}|(|\mathcal{D}|-1)}\sum_{d^{\prime}\in\mathcal{D}}\left(\mathcal{E}_{d^{\prime}}\rho_{d}-\mathcal{E}_{d}\rho_{d^{\prime}}\right)\rho_{d^{\prime}}.$

Thus in order to apply PL-Rank-2 to this fairness metric, one only needs to
compute (or estimate) Eq. 31 and then run Algorithm 1 where the relevances are
replaced with the gradients:
$\frac{\delta\mathcal{F}(q)}{\delta\mathcal{E}_{d}}$.

To conclude, we have shown that PL-Rank-2 can efficiently estimate the
gradient of exposure-based fairness metrics, in addition to relevance metrics
and any linear combination of any set of these metrics.

##  7\. Experimental Setup

The experiments performed for this paper aim to answer three research
questions:

  1. RQ1

Does PL-Rank require fewer sampled rankings for optimal convergence than
policy gradients or LambdaLoss?

  2. RQ2

Is less computational time needed to reach high performance with PL-Rank than
with policy gradients or LambdaLoss?

  3. RQ3

Is PL-Rank also effective at optimizing an exposure-based fairness metric?

In other words, we address the sample-efficiency and the computational costs
of PL-Rank, in addition to its applicability to ranking-fairness metrics.

To evaluate these aspects we compare with three baselines:  (i) the policy
gradient as described in Section 4.2, this is the most basic form of gradient
estimation (Singh and Joachims, 2019; Williams, 1992; Bruch et al., 2020);
(ii) the placement policy gradient as introduced in Section 5.1, this gradient
estimation considers individual item placements; and  (iii) LambdaLoss (Wang
et al., 2018b), a state-of-the-art heuristic for optimizing deterministic
ranking models. Following Bruch et al. (2020) we apply an average of the
gradients over $N$ sampled rankings. One can easily extend the existing proof
that LambdaLoss optimizes a lower bound on the performance of a deterministic
model (Wang et al., 2018b) to prove our approach also optimizes a lower bound
on the expected performance of a stochastic PL ranking model.  We note that
Bruch et al. (2020) introduced additional heuristic methods for PL-Ranking
model optimization, due to their high similarity with LambdaLoss we omitted
these methods from our baselines. To the best of our knowledge, our choice of
baselines cover every category of existing methods for the metric-based
optimization of PL-Ranking models.

We base our experiments on the three largest publicly-available LTR industry
datasets: _Yahoo! Webscope_ (Chapelle and Chang, 2011), _MSLR-WEB30k_ (Qin and
Liu, 2013), and _Istella_ (Dato et al., 2016). Each dataset contains queries,
preselected documents per query, and relevance labels indicating the expert-
judged relevance of a preselected document w.r.t. a query. Query-document
combinations are represented by feature vectors, each dataset varies in the
number of features, queries and average number of preselected documents: Yahoo
contains 29,921 queries and on average 24 preselected documents per query
encoded in 700 features; MSLR has 30,000 queries, on average 125 documents per
query and 136 features; and lastly, Istella has 33,118 queries, on average 315
documents per query and 220 features.

For our relevance experiments, we optimize top-5 _Discounted Cumulative Gain_
(DCG@5) and choose $\theta$ accordingly (Eq. 3).111We chose DCG instead of
normalized DCG based on the advice of Ferrante et al. (2021). The relevance of
a document is set to a transformation of its label:
$\rho_{d}=2^{\text{relevance\\_label}(d)}-1$. For the fairness experiments, we
optimize the disparity metric introduced in Section 6, exposure values
$\mathcal{E}_{d}$ are estimated using $1000$ sampled rankings. To compare the
computational costs of each method, we ran repeated experiments under
identical circumstances on a single _Intel Xeon Silver 4214_ CPU and measured
the time taken to complete each epoch. All our reported results are averaged
over 20 independent runs.

Based on preliminary parameter tuning, we chose to optimize neural networks
with two hidden layers of 32 sigmoid activated nodes, we used standard
stochastic gradient descent with a $0.01$ learning rate for all methods. For
calculating gradients we utilize _Tensorflow_ (Abadi et al., 2016) with two
exceptions: the sampling of rankings and $\frac{\delta\mathcal{R}(q)}{\delta
m}$ with the PL-Rank algorithm (Algorithm 1) are computed using _Numpy_
(Harris et al., 2020).

Table 1.  Average time in minutes taken to perform one training epoch for different numbers of sampled rankings $N$, the standard deviation is displayed in brackets.  |  | $N=1$ | $N=10$ | $N=100$ | $N=1000$
---|---|---|---|---|---
Yahoo | LambdaLoss | 2.48 ( 0.05) | 2.53 ( 0.04) | 3.06 ( 0.08) | 10.25 ( 0.53)
Policy Gradient | 3.79 ( 0.09) | 3.80 ( 0.06) | 4.28 ( 0.15) | 8.27 ( 0.50)
Placement P.G. | 3.83 ( 0.08) | 3.86 ( 0.05) | 4.42 ( 0.10) | 8.26 ( 0.44)
PL-Rank-1 | 2.45 ( 0.06) | 2.49 ( 0.06) | 2.82 ( 0.09) | 5.70 ( 0.14)
PL-Rank-2 | 2.49 ( 0.06) | 2.52 ( 0.06) | 2.87 ( 0.08) | 6.22 ( 0.15)
MSLR | LambdaLoss | 2.73 ( 0.11) | 3.96 ( 0.59) | 36.36 ( 31.46) | 1669.59 ( 450.69)
Policy Gradient | 3.30 ( 0.10) | 3.45 ( 0.10) | 5.25 ( 0.35) | 24.20 ( 2.77)
Placement P.G. | 3.32 ( 0.17) | 3.42 ( 0.13) | 5.27 ( 0.41) | 23.97 ( 2.68)
PL-Rank-1 | 2.16 ( 0.14) | 2.28 ( 0.13) | 3.34 ( 0.13) | 18.48 ( 2.10)
PL-Rank-2 | 2.19 ( 0.15) | 2.35 ( 0.17) | 3.45 ( 0.06) | 21.10 ( 2.78)
Istella | LambdaLoss | 3.53 ( 0.12) | 4.50 ( 0.10) | 27.81 ( 19.20) | 142.74 ( 16.25)
Policy Gradient | 4.10 ( 0.17) | 4.51 ( 0.16) | 8.74 ( 0.26) | 44.29 ( 2.17)
Placement P.G. | 4.08 ( 0.17) | 4.51 ( 0.18) | 8.72 ( 0.23) | 44.74 ( 2.55)
PL-Rank-1 | 3.01 ( 0.12) | 3.27 ( 0.09) | 6.90 ( 0.19) | 39.80 ( 2.65)
PL-Rank-2 | 3.04 ( 0.13) | 3.31 ( 0.10) | 7.02 ( 0.14) | 40.64 ( 3.96)
| $N=10$ | $N=100$ | $N=1000$
---|---|---|---
Yahoo! Webscope |  |  |
MSLR-WEB30k |  |  |
Istella |  |  |
|  Training Epoch |  Training Epoch |  Training Epoch
Figure 1.  Performance in DCG@5 of PL ranking models trained using different
gradient estimation methods with varying number of sampled rankings $N$ per
estimation. Results are the mean of 20 independent runs.

##  8\. Results

Our discussion of the results is divided per research question, our results
are displayed in Figure 1, 2 and 3 and Table 1 and 2.

###  8.1. Sample-Efficiency

We will first consider RQ1: _whether PL-Rank needs fewer sampled rankings for
optimal convergence_. Figure 1 shows the performance of PL ranking models
trained using different gradient estimation methods with varying numbers of
sampled rankings used for estimation. We see that increasing the number of
samples beyond $N=10$ does not have any noticeable effect on the performance
of LambdaLoss. In all cases, LambdaLoss converges at suboptimal performance
after only a few epochs. In contrast, the basic policy gradient is very
affected by $N$ and on all three datasets it requires $N=1000$ to get close to
optimal performance, it has extreme convergence issues when $N=10$. However,
in all cases the placement policy gradient outperforms the basic policy
gradient and can converge near optimal performance with $N=100$. The
performance of PL-Rank-1 and the placement policy gradient are
indistinguishable. This strongly suggests that PL-Rank-1 and the placement
policy gradient perform the same estimation, although Section 8.2 will reveal
that PL-Rank-1 does so in a more computationally efficient way. Lastly, we see
that PL-Rank-2 outperforms PL-Rank-1 and the policy gradient methods when
$N=10$ on the Yahoo and Istella datasets. Noticeable but limited improvements
are also present with $N=100$ on these datasets. Thus while we can conclude
that PL-Rank-2 has the best sample-efficiency of all the methods, the
improvements over PL-Rank-1 and the placement policy gradient are most
substantial when $N<100$.

Overall, we see that the basic policy gradient and LambdaLoss are poor choices
for optimization, despite the fact that these are the methods we find in
previous work (Singh and Joachims, 2019; Bruch et al., 2020). The choice
between PL-Rank-1 and the placement policy gradient does not seem to matter
when only the number of epochs is considered. PL-Rank-2 appears the safest
choice because, in all tested cases, it either outperforms or has comparable
performance to the other methods.

To conclude, we answer RQ1 in the affirmative: PL-Rank-2 is the most sample-
efficient method, although when $N>100$ PL-Rank-1 and the placement policy
gradient have comparable performance.

Yahoo! Webscope | MSLR-WEB30k | Istella
---|---|---
|  |
Minutes Trained |  Minutes Trained |  Minutes Trained
Figure 2.  Performance in DCG@5 of PL ranking models trained using different gradient estimation methods following a dynamically updated number of sampled rankings $N$ per estimation. Results are the mean of 20 independent runs.  Table 2. DCG@5 reached using different gradient estimation methods following a dynamically updated $N$ and being optimized for the same amount of time. Results are the mean of 20 independent runs, the standard deviation is displayed in brackets, $\triangledown$ indicates the result is significantly worse ($p<0.01$) than that of PL-Rank-2 on the same dataset. | Yahoo | MSLR | Istella
---|---|---|---
Minutes Optimized | 100 | 120 | 200
LambdaLoss | 11.11 ▽ ( 0.05) | 7.80 ▽ ( 0.09) | 18.75 ▽ ( 0.10)
Policy Gradient | 11.03 ▽ ( 0.04) | 8.21 ▽ ( 0.07) | 18.75 ▽ ( 0.10)
Placement Policy Gradient | 11.31 ▽ ( 0.02) | 8.33 ▽ ( 0.04) | 19.23 ▽ ( 0.06)
PL-Rank-1 | 11.38 ▽ ( 0.03) | 8.39 - ( 0.04) | 19.31 ▽ ( 0.05)
PL-Rank-2 | 11.42 - ( 0.02) | 8.39 - ( 0.03) | 19.38 - ( 0.05)
Yahoo! Webscope |
---|---
|
Minutes Trained |
Figure 3.  The mean disparity error of models trained using different gradient
estimation methods following a dynamically updated number of sampled rankings
$N$ per estimation. Results are the mean of 20 independent runs.

###  8.2. Computational Costs and Time-Efficiency

In order to answer RQ2: _whether PL-Rank requires less computational time to
reach optimal performance_ , we first consider Table 1 which displays the
average time taken to perform a single epoch per method for various $N$
values.

We see that in all cases PL-Rank-1 takes the least amount of time to compute,
with PL-Rank-2 being the second fastest method. There is little difference
between the policy gradient methods but they are always much slower than the
PL-Rank methods. Depending on the dataset and $N$, the difference between PL-
Rank and the policy gradients varies from around a minute to almost five
minutes. In Figure 1 we see that convergence requires at least 40 training
epochs, thus differences in minutes per epoch can easily add up to reaching
convergence over an hour earlier.

LambdaLoss is especially affected by the $N$ parameter, a likely explanation
is that it is the only method that has to sample the complete ranking, whereas
the other methods only need to sample the top-$k$ ranking (top-$5$ in this
case).

By considering both the results from Table 1 and Figure 1, we can make three
observations:  (i) when $N=10$, decent but not optimal performance is reached;
(ii) $N=100$is enough to converge near optimal performance; and  (iii)
performing an epoch with $N=10$ is considerably faster than with $N=100$.
Based on these observations, it seems reasonable to increase $N$ at every
training step so that decent performance is reached very quickly but
convergence is still optimal. We found that
$N=10+90\cdot\frac{\text{epoch}}{40}$ outperformed the static choices $N=10$
and $N=100$ in terms of learning speed while maintaining optimal convergence.

Figure 2 shows the performance of PL ranking models trained using this dynamic
$N$ strategy over training time in minutes. Again we see that LambdaLoss
converges fast but at suboptimal performance. Similarly, there is clearly a
large difference visible between the basic policy gradient and the placement
policy gradient. However, on all datasets, we see an improvement of PL-Rank-1
over the placement policy gradient which is very large on Yahoo and MSLR but
smaller on Istella. This improvement can be attributed to the reduced
computational costs of PL-Rank-1, as a result, it is capable of completing
more epochs in the same amount of time and can therefore reach a higher
performance in less computational time. Finally, compared to PL-Rank-1, PL-
Rank-2 has an even higher performance on the Yahoo and Istella datasets but
not on MSLR. It appears that its increased sample-efficiency helps PL-Rank-2
initially, when $N$ is low, except on the MSLR dataset where Figure 1 also
shows us that the difference in sample-efficiency is very limited. To better
verify that PL-Rank-2 is the best choice, we performed a two-sided student
t-test on the performance differences, the results are displayed in Table 2.
We see that Pl-Rank-2 is significantly better compared to the other methods in
all tested cases, with the single exception of PL-Rank-1 on the MSLR dataset.

To conclude, we answer RQ2 in the affirmative: the PL-Rank methods achieves
significantly higher performance with less computational time required than
LambdaLoss or the policy gradients. In particular, PL-Rank-2 is the most time-
efficient method across all datasets.

###  8.3. Optimizing a Ranking Fairness Metric

Finally, we address RQ3: _whether PL-Rank is effective at optimizing ranking
fairness_. Figure 3 displays the mean disparity error for models optimized
with the different gradient estimation methods, with the same increasing $N$
strategy applied as in Section 8.2. While all methods decrease the disparity,
the PL-Rank methods and the placement policy gradient are considerably more
efficient than LambdaLoss and the basic policy gradient. Unlike with the
optimization for relevance, there appears only a very small improvement of the
PL-Rank methods over the placement policy gradient. Therefore, we answer RQ3
in the affirmative: PL-Rank can effectively optimize ranking fairness, where
we note that the placement policy gradient has comparable time-efficiency.

##  9\. Conclusion

In this paper, we tackled the optimization of PL-ranking models for both
relevance and fairness ranking metrics. While previous work has found PL-
ranking models effective for various ranking tasks, their optimization can
involve large computational costs. To alleviate these costs, we introduced
three new estimators for efficiently estimating the gradient of a ranking
metric w.r.t. a PL ranking model: the placement policy gradient and two PL-
Rank methods. The latter two can be computed using the PL-Rank algorithm. To
the best of our knowledge, PL-Rank is the first algorithm designed
specifically for efficiently optimizing PL ranking models w.r.t. ranking
metrics. Our experimental results indicate that our novel methods considerably
reduce the computational time required to reach optimal performance compared
to existing methods. In particular, the PL-Rank-2 method has the best sample-
effiency and was found to reach significantly higher performance when ran for
the same amount of time as other methods. Compared to the popular basic policy
gradient, PL-Rank-2 converges several hours earlier, thus immensely
alleviating the computational costs of optimization.

With the introduction of PL-Rank, we hope that the usage of stochastic ranking
models is made more attractive in real-world scenarios. Finally, we think PL-
Rank is also an important theoretical contribution to the LTR field, as it
proves that PL ranking models can be optimized with computational efficiency,
without relying on heuristic methods.

### Code and data

To facilitate reproducibility, this work only made use of publicly available
data and our experimental implementation is publicly available at
https://github.com/HarrieO/2021-SIGIR-plackett-luce.

## References

  * (1)
  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  Tensorflow: A system for large-scale machine learning. In _12th USENIX symposium on operating systems design and implementation OSDI’16)_. 265–283.
  * Biega et al. (2018) Asia J Biega, Krishna P Gummadi, and Gerhard Weikum. 2018\.  Equity of attention: Amortizing individual fairness in rankings. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 405–414.
  * Bruch et al. (2020) Sebastian Bruch, Shuguang Han, Michael Bendersky, and Marc Najork. 2020.  A Stochastic Treatment of Learning to Rank Scoring Functions. In _Proceedings of the 13th International Conference on Web Search and Data Mining_. 61–69.
  * Bruch et al. (2019) Sebastian Bruch, Masrour Zoghi, Michael Bendersky, and Marc Najork. 2019.  Revisiting approximate metric optimization in the age of deep neural networks. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1241–1244.
  * Burges et al. (2005) Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005.  Learning to rank using gradient descent. In _Proceedings of the 22nd international conference on Machine learning_. 89–96.
  * Burges (2010) Christopher J.C. Burges. 2010\.  _From RankNet to LambdaRank to LambdaMART: An Overview_.  Technical Report MSR-TR-2010-82. Microsoft.
  * Cao et al. (2007) Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. 2007.  Learning to rank: from pairwise approach to listwise approach. In _Proceedings of the 24th international conference on Machine learning_. 129–136.
  * Chapelle and Chang (2011) Olivier Chapelle and Yi Chang. 2011.  Yahoo! Learning to Rank Challenge Overview.  _Journal of Machine Learning Research_ 14 (2011), 1–24.
  * Craswell et al. (2008) Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. 2008.  An experimental comparison of click position-bias models. In _Proceedings of the 2008 international conference on web search and data mining_. 87–94.
  * Dato et al. (2016) Domenico Dato, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2016\.  Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees.  _ACM Transactions on Information Systems (TOIS)_ 35, 2 (2016), Article 15.
  * Diaz et al. (2020) Fernando Diaz, Bhaskar Mitra, Michael D. Ekstrand, Asia J. Biega, and Ben Carterette. 2020\.  _Evaluating Stochastic Rankings with Expected Exposure_.  Association for Computing Machinery, New York, NY, USA, 275–284.
  * Donmez et al. (2009) Pinar Donmez, Krysta M Svore, and Christopher JC Burges. 2009\.  On the local optimality of LambdaRank. In _Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval_. 460–467.
  * Ferrante et al. (2021) Marco Ferrante, Nicola Ferro, and Norbert Fuhr. 2021\.  Towards Meaningful Statements in IR Evaluation. Mapping Evaluation Measures to Interval Scales.  _arXiv preprint arXiv:2101.02668_ (2021).
  * Gumbel (1954) Emil Julius Gumbel. 1954\.  _Statistical theory of extreme values and some practical applications: a series of lectures_. Vol. 33.  US Government Printing Office.
  * Harris et al. (2020) Charles R. Harris, K. Jarrod Millman, St’efan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fern’andez del R’ıo, Mark Wiebe, Pearu Peterson, Pierre G’erard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020.  Array programming with NumPy.  _Nature_ 585, 7825 (2020), 357–362.
  * Hofmann et al. (2011) Katja Hofmann, Shimon Whiteson, and Maarten de Rijke. 2011\.  A Probabilistic Method for Inferring Preferences from Clicks. In _CIKM_. ACM, 249–258.
  * Joachims (2002) Thorsten Joachims. 2002\.  Optimizing Search Engines Using Clickthrough Data. In _Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 133–142.
  * Liu (2009) Tie-Yan Liu. 2009\.  Learning to Rank for Information Retrieval.  _Foundations and Trends in Information Retrieval_ 3, 3 (2009), 225–331.
  * Luce (2012) R Duncan Luce. 2012\.  _Individual choice behavior: A theoretical analysis_.  Courier Corporation.
  * Morik et al. (2020) Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. 2020.  _Controlling Fairness and Bias in Dynamic Learning-to-Rank_.  ACM, 429–438.
  * Oosterhuis and de Rijke (2018) Harrie Oosterhuis and Maarten de Rijke. 2018.  Differentiable Unbiased Online Learning to Rank. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. ACM, 1293–1302.
  * Oosterhuis and de Rijke (2020) Harrie Oosterhuis and Maarten de Rijke. 2020.  Taking the Counterfactual Online: Efficient and Unbiased Online Evaluation for Ranking. In _Proceedings of the 2020 International Conference on The Theory of Information Retrieval_. ACM.
  * Oosterhuis and de Rijke (2021) Harrie Oosterhuis and Maarten de Rijke. 2021.  Unifying Online and Counterfactual Learning to Rank. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM’21)_. ACM.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library. In _Advances in neural information processing systems_. 8026–8037.
  * Plackett (1975) Robin L Plackett. 1975\.  The analysis of permutations.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ 24, 2 (1975), 193–202.
  * Qin and Liu (2013) Tao Qin and Tie-Yan Liu. 2013.  Introducing LETOR 4.0 datasets.  _arXiv preprint arXiv:1306.2597_ (2013).
  * Schuth et al. (2015) Anne Schuth, Robert-Jan Bruintjes, Fritjof Buüttner, Joost van Doorn, Carla Groenland, Harrie Oosterhuis, Cong-Nguyen Tran, Bas Veeling, Jos van der Velde, Roger Wechsler, et al. 2015\.  Probabilistic multileave for online retrieval evaluation. In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 955–958.
  * Singh and Joachims (2019) Ashudeep Singh and Thorsten Joachims. 2019.  Policy learning for fairness in ranking. In _Advances in Neural Information Processing Systems_. 5426–5436.
  * Taylor et al. (2008) Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. 2008.  Softrank: optimizing non-smooth rank metrics. In _Proceedings of the 2008 International Conference on Web Search and Data Mining_. 77–86.
  * Wang et al. (2018a) Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018a.  Position Bias Estimation for Unbiased Learning to Rank in Personal Search. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_. ACM, 610–618.
  * Wang et al. (2018b) Xuanhui Wang, Cheng Li, Nadav Golbandi, Michael Bendersky, and Marc Najork. 2018b.  The LambdaLoss Framework for Ranking Metric Optimization. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. ACM, 1313–1322.
  * Wei et al. (2017) Zeng Wei, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017.  Reinforcement learning to rank with Markov decision process. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 945–948.
  * Williams (1992) Ronald J Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8, 3-4 (1992), 229–256.
  * Xia et al. (2008) Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. 2008.  Listwise approach to learning to rank: theory and algorithm. In _Proceedings of the 25th international conference on Machine learning_. 1192–1199.
  * Xia et al. (2017) Long Xia, Jun Xu, Yanyan Lan, Jiafeng Guo, Wei Zeng, and Xueqi Cheng. 2017\.  Adapting Markov decision process for search result diversification. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 535–544.

  *[LTR]: Learning to Rank
  *[PL]: Plackett-Luce
  *[DCG]: Discounted Cumulative Gain
  *[ARP]: Average Relevance Position


#  ORACLE: Collaboration of Data and Control Planes to Detect DDoS Attacks

Sebastián Gómez Macías Universidad de Antioquia
Medellín, Colombia
<EMAIL_ADDRESS>Luciano Paschoal Gaspary Universidade F. do Rio
Grande do Sul
Porto Alegre, Brasil
<EMAIL_ADDRESS>Juan Felipe Botero Universidad de Antioquia
Medellín, Colombia
<EMAIL_ADDRESS>
###### Abstract

The possibility of programming the control and data planes, enabled by the
Software-Defined Networking (SDN) paradigm, represents a fertile ground on top
of which novel operation and management mechanisms can be fully explored,
being Distributed Denial of Service (DDoS) attack detection based on machine
learning techniques the focus of this work. To carry out the detection, this
paper proposes ORACLE: cOllaboRation of dAta and Control pLanEs to detect DDoS
attacks, an architecture that promotes the coordination of control and data
planes to detect network attacks. As its first contribution, this architecture
delegates to the data plane the extraction and processing of traffic
information collected per flow. This is done in order to ease the calculation
and classification of the feature set used in the attack detection, as the
needed flow information is already processed when it arrives at the control
plane. Besides, as the second contribution, this architecture breaks the
limitations to calculate some features that are not possible to implement in a
traditional OpenFlow-based environment. In the evaluation of ORACLE, we
obtained up to 96% of accuracy in the testing phase, using a K-Nearest
Neighbor model.

###### Index Terms:

DDoS, Security, SDN, P4, Machine-Learning

##  I Introduction

A DDoS attack is considered a powerful weapon against Internet security due to
its ability to bring down even the largest websites by overloading servers’
resources [1]. In turn, Software-Defined Networking (SDN) is an emerging
network paradigm that decouples the control and data planes where the network
control is logically centralized and programmable. Considering the different
proposed DDoS detection approaches, several leverage the SDN advantages:
global network view and control plane programmability. Among these mechanisms,
those based on Machine Learning (ML) algorithms are considered the best in
terms of key metrics such as detection speed, accuracy, and reliability [2,
3].

A traditional ML-based detection system is mainly based on: i) a traffic
information collecting mechanism, ii) a feature calculation module, and iii) a
classification model; all of them implemented at the control plane. The
collecting mechanism obtains traffic information from the packets that arrive
at the SDN controller (Packet_in) and also from the statistics provided by
OpenFlow (SDN southbound interface). The feature calculation module processes
the collected information to build the set of descriptors, and, finally, the
classification module classifies this set of features in search of possible
ongoing DDoS attacks. However, in the implementation of these detection
systems, we observe two design challenges, which we enumerate and describe
next.

The first challenge is to prevent overloading the control plane due to the
execution of tasks related to polling information from the network traffic, as
well as the calculation and classification of the feature set. To carry out
these tasks, the detection system has to store, update, and filter different
information samples, which are sorted and processed per flow, connection, or
source-destination pair. The execution of these tasks in the presence of large
amounts of packets and flows can easily overload the control plane.

The second challenge lies in extracting, in real-time, the information needed
to calculate the feature set selected as the best traffic descriptors. In an
OpenFlow-based SDN environment, limited processing can be performed on a per-
packet basis at the data plane. The extraction of sufficient traffic
information with fine granularity needed to calculate a wide variety of
features in real-time becomes impractical. Therefore, from a huge amount of
traffic features proposed in the literature, just a specific group of them
(e.g., flow’s byte/packet count and duration) are possible to implement.

In order to overcome these challenges, we propose ORACLE, an approach based on
the cOllaboRation of dAta and Control pLanEs to detect DDoS attacks using the
paradigm of programmable data planes. The proposed approach fully explores the
programming of packet processing at a switch level. To program the data plane,
we use the P4 programming language [4] together with the P4Runtime interface
(to provide communication with the control plane). At the data plane, we
propose a hash-based data structure to store customized per-flow information.
We also propose a mechanism to periodically report such information to the
control plane, where the feature set is subsequently calculated and classified
per each reported flow. The main contributions of ORACLE are:

  * •

A novel strategy that is expected to be deployed over the proposed SDN-P4
architecture to periodically calculate specific flow features to be used by
the detection system.

  * •

An architecture that delegates to the data plane the tasks of collecting,
processing, and storing the required information per traffic flow. This
facilitates the calculation and classification of the feature set by the
control plane. The architecture is not limited only to DDoS attacks. On the
contrary, it provides the framework for the calculation of any feature needed
to detect other attacks.

##  II Background and Related Work

According to [5], for traffic classification, the list of potential features
is divided in five categories: packet level (e.g., packet length mean), flow
level (e.g., average packet length and packets per flow), connection level
(e.g., advertised window sizes), intra-flow level (e.g., features based on
inter-arrival times between packets of the same flow), and multiflow.

In order to extract information at the flow or intra-flow level, three flow
definitions apply [5]: unidirectional flow, made up of packets sharing the
same fields (source/destination IP, source/destination TCP/UDP ports and
transport protocol number); bidirectional flow, made up of a pair of
unidirectional flows that are going in opposite directions between the same
source and destination IP addresses and ports; and full flow, a bidirectional
flow captured during its entire lifetime.

Recent research efforts indicate that SDN is suitable for the implementation
of sophisticated software solutions that allow detecting DDoS attacks. The
following proposals, implemented at the control plane, make use of different
feature sets and ML-based detection techniques.

In [6], the authors perform the DDoS detection by polling, each second,
OpenFlow statistics per each unidirectional flow. To calculate the feature
set, they store several samples of the same bidirectional flow (computed in
the control plane from the unidirectional flows) to calculate features based
on average and standard deviation (std) at flow level. Results show 96% of
accuracy with the Random Forest (RF) classifier.

The authors of [7] propose an integrated framework that comprises two
operational phases at the control plane: 1) a lightweight processing phase
that consists of monitoring the flows looking for an entropy anomaly, and 2) a
heavyweight processing phase that is only invoked when an anomalous flow is
detected. The heavyweight process uses OpenFlow statistics (packet_count,
byte_count, duration) at flow level to detect DDoS attacks. A Support Vector
Machine (SVM) is used as the ML-classifier providing a detection accuracy
score of 88%. This means that the reduction of heavy processes at the control
plane is achieved at big costs in terms of accuracy.

In the previous detection systems, and also in others such as [8], we noticed
that the implemented features are limited to a specific group coming from
header field values extracted from the OpenFlow packet_in event. In [9], we
can find a wide variety of features that one could implement to detect
different attacks (e.g., DDoS). Among the huge list of features, those at the
intra-flow level and several at the connection level are not possible to
calculate in an SDN/OpenFlow environment. Consequently, we propose ORACLE,
where the calculation of such features is possible, in real-time, via the
programming and coordination of the data and control planes.

##  III ORACLE: cOllaboRation of dAta and Control pLanEs to detect DDoS
attacks

###  III-A Architecture

ORACLE is organized in two modules, namely Data Plane and Control Plane, which
we show in Fig. 1 and describe next.

Figure 1: ORACLE system architecture

Data Plane: ORACLE relies on a time window-based implementation. During each
window, the data plane performs two tasks simultaneously: it i) collects new
flow information, and ii) reports flow information collected and processed in
the previous time window to the control plane. The data plane’s module is
composed of the following four components, developed using P4 primitives such
as registers, clone packet, hash functions, and basic binary operations
(+,-,*).

  * •

Data Structure: It is used for the statistics organization, management, and
storage per unidirectional flow. To access them, the flow identifier (flow-id)
is mapped, through a hash function, to the respective index (position where
the statistics are stored) in the data structure.

  * •

Statistics Collector: In charge of extracting and processing the needed
information from the bit string of every packet traversing the device. With
this information, the statistics of the flow associated with the packet are
updated.

  * •

Pipeline Handler: In charge of controlling the time window duration and
validating if the data structure contains new flow information to report. If
so, the incoming packet is cloned and forwarded to the Information Transmitter
component along with the per-flow information that will be subsequently sent
to the controller.

  * •

Information Transmitter: This component transforms the cloned packet in a
report packet that is forwarded to the control plane using the P4Runtime
interface. The cloned packet is modified by eliminating its payload and adding
the flow information as a new custom header.

Control Plane: It is composed of an SDN controller and a traffic
classification component connected via REST-API. To classify the reported
flows, three components are involved:

  * •

Extract Flow Information: This component extracts the custom header from the
report packet and parses it to get the information of every flow sent by the
data plane.

  * •

Feature Calculation: It builds a tuple with the features set calculated with
the flow information.

  * •

Classifier: An already loaded ML model classifies every tuple received in DDoS
or Benign class. When a possible attack is detected, an alarm is issued.

###  III-B Data Plane Storage Mechanism

Figure 2: Mechanism to store statistics per flow.

ORACLE collects and stores statistics of packets belonging to each flow on the
programmable switches. It guarantees that flow statistics can be consulted and
updated each time a new packet belonging to the flow arrives to the P4 device.

We use P4 registers to define a data structure to store flow statistics. A
register is a fixed-size array that uses an index to point to the stored
elements. To consolidate the structure, we use a set of such registers to
build a matrix-like structure, where each row stores values of the same
statistics belonging to different flows, and each column stores different
statistics of the same unidirectional flow (see Fig. 2). To designate a unique
index (column) to each unidirectional flow, we use the hash function with an
input value (Flow-Id) that consists of source/destination IP,
source/destination port, and transport protocol. The hash’s output is the
index mapped to the flow.

Figure 2 shows how per-flow statistics are stored and updated by the
Statistics Collector component. Once a packet enters the P4 device, its bit
string is parsed to extract and map each header field value to P4 variables.
From these variables, the collector builds the 5-tuple (Flow-Id) to calculate
the hash function. Once having the flow index, the flow statistics are updated
in the data structure with the needed information that is obtained by
processing the P4 variables.

As we are working with bidirectional flows and the method stores
unidirectional flows, it is important to identify the pair of flows (indexes)
defining the bidirectional flow within the data structure. To know the index
of the opposite direction of the flow, we calculate again the hash function
exchanging the order of the flow identifier fields (see Fig. 2). Hence, we
define forward (FWD) as the direction of the first packet of the flow and
backward (BWD), the opposite direction.

###  III-C Data Plane Flow Reporting Mechanism

The Pipeline Handler component is in charge of reporting flow information to
the control plane at the beginning of each time window. In order to forward
the information of all bi-directional flows collected at the previous time
window to the control plane, it is necessary to know the indexes that point to
the specific flows within the data structure. To ease this process, each time
a new flow is instantiated at the statistics data structure, both indexes (FWD
and BWD) are stored in a new data structure composed of two registers and a
counter (see Fig. 2). One register stores the indexes of the FWD
unidirectional flows, and the other stores the indexes of the BWD flows.
Hence, each column will contain the indexes of a different bidirectional flow
and the counter will be just a reference to know the position of the last pair
of stored indexes. This data structure works like a LIFO buffer: indexes are
stored sequentially as the flows are instantiated. When the information is to
be sent to the control plane, the indexes are consumed from the buffer in the
reverse arrival order.

Figure 3: Lane-based mechanism to handle time windows and buffers.

The implementation of the control data structure with a single buffer implies
that the data plane interrupts the process of collecting information from new
flows until the buffer is emptied. As the system must be able to perform both
tasks (collecting and reporting flows to the control plane) simultaneously, we
propose to abstract the idea of two independent monitoring “lanes”, each one
with its buffer. Therefore, is possible to delegate, over a same time window,
one task to each lane, avoiding the process to be interrupted (see Fig. 3).

Using this strategy based on independent buffers to store the indexes of
bidirectional flows, the Pipeline Handler component can validate, in each time
window, if there are flow statistics available to forward to the control
plane. If so, this component looks for per-flow statistics from the data
structure, clones the number of incoming packets needed to transmit this
information, and delegates the transmitting process to the respective
component. The Information Transmitter component embeds the information of
each flow into a custom header. The number of fields (flows) within this
header should be as big as the network MTU value to avoid injecting too many
report packets into the network.

##  IV Detection System Implemented on ORACLE

As proof of concept, we implemented a DDoS attack detection system that uses
the feature set listed in Table I. These features are recommended in [9],
where the authors used the RandomForestRegressor technique to select, among 80
features, a small set considered the most adequate for DDoS attack detection.
This set is made up of two features at flow level (F1 and F3) and two at
intra-flow level (F2 and F4). On the other hand, there are features that are
calculated considering the statistics in both flow directions (bidirectional),
and one of them (F4) considering only the BWD direction.

TABLE I: Selected feature set

# | Feature name | Description | Level / Type
---|---|---|---
F1 | FlowDuration | Flow duration in microseconds | Flow /
|  |  | (Bidirectional)
F2 | FlowIATStd | Standard deviation of packet inter-arrival | Intra-Flow /
|  | times of the same flow. | (Bidirectional)
F3 | avgPacketSize | Average of packet payload sizes of the | Flow /
|  | same flow. | (Bidirectional)
F4 | BwdPktLenStd | Standard deviation of packet payload | Intra-Flow /
|  | sizes of the same flow in the backward | (Unidirectional)
|  | direction |

In Table I, F2, F3, and F4 are based on average (avg) and standard deviations
(std) operations, calculated using Eq. 1 and 2, respectively. $x_{i}$
corresponds to an information unit extracted from packet $i$, which belongs to
a group of $n$ packets (of a same flow). The meaning of $x_{i}$ changes
depending on the feature to calculate; for F2, it corresponds to the packet
inter-arrival time (IAT), and for F3-F4, it corresponds to the size in bytes
of the packet’s payload.

$\footnotesize avg=\overline{x}=\frac{\sum_{i:1}^{n}x_{i}}{n-1}$ (1)
$\footnotesize
std=\sqrt{\frac{\sum_{i:1}^{n}\left(x_{i}-\overline{x}\right)^{2}}{n-1}}=\sqrt{\frac{\sum_{i:1}^{n}x_{i}^{2}-2\overline{x}\sum_{i:1}^{n}x_{i}+n\overline{x}^{2}}{n-1}}$
(2)

In an SDN/OpenFlow environment, the features at flow level (F1 and F3) can be
calculated from OpenFlow statistics. The real challenge is to calculate the
intra-flow features (F2 and F4) because: i) OpenFlow does not permit to know
the packet IAT, and ii) to calculate the std of an intra-flow measure, every
$x_{i}$ value is required at the control plane to subtract the mean from it
when the sum is being computed (see Eq. 2, left side).

ORACLE allows overcoming these limitations as it stores individual information
for each packet, even IAT values, and reports it periodically to the control
plane. However, this may result in high latency and storage/processing
resource consumption. A more ambitious solution would be to calculate these
features directly on the data plane and avoid sending every $x_{i}$. This
solution is not possible because programmable data planes are usually limited
in the available mathematical operations (e.g., division and square root are
not allowed).

TABLE II: Information per-Flow Reported by the Data Plane

# | Feature / Statistic | Description
---|---|---
F1 | FlowDuration | Flow duration in microseconds
S2 | TotFwdPkt | Total number of packets in the FWD direction
S3 | TotBwdPkt | Total number of packets in the BWD direction
S4 | TotLenFwdPkt | Aggregation of packets’ payload size in FWD
|  | direction $\left(\sum x_{i}\right)$
S5 | TotLenBwdPkt | Aggregation of packets’ payload size in BWD
|  | direction $\left(\sum x_{i}\right)$
S6 | TotLenBwdPktSqrt | Aggregation of packets’ payload size
|  | square in BWD direction $\left(\sum x_{i}^{2}\right)$
S7 | IATTotal | Aggregation of the packet inter-arrival times
|  | $\left(\sum x_{i}\right)$
S8 | IATTotalSqrt | Aggregation of the packet inter-arrival times
|  | square $\left(\sum x_{i}^{2}\right)$

Therefore, we propose the following alternative. The traditional std (Eq. 2)
is transformed using arithmetic properties to have the right side
representation. Now, this new representation depends on two sums: the
aggregation of values $\left(\sum x_{i}\right)$, and the aggregation of square
values $\left(\sum x_{i}^{2}\right)$. Using the data plane mechanisms proposed
in ORACLE, we calculate, directly at the data plane, the result of both sums
per each flow, as the on-going packets traverse the data plane device.
Therefore, when these aggregation results are reported together with the
packet counters to the control plane (see Table II), the controller has only
to replace them in Eq. 1 and 2 to calculate F2, F3, and F4 per each flow in an
easy and fast way, as specified below. Regarding F1, it is calculated directly
in the data plane and reported to the control plane together with the
statistics.

  * •

FlowIATStd (F2):

$\footnotesize
n=S2+S3\quad(Bidir.)\quad\quad;\quad\quad\overline{x}=\frac{S7}{n-1}$ (3)
$\footnotesize std=\sqrt{\frac{S8-2*\overline{x}*S7+n\overline{x}^{2}}{n-1}}$
(4)

  * •

avgPacketSize (F3):

$\footnotesize
n=S2+S3\quad(Bidir.)\quad\quad;\quad\quad\overline{x}=\frac{S4+S5}{n-1}$ (5)

  * •

BwdPktLenStd (F4):

$\footnotesize
n=S3\quad(Unidir.)\quad\quad;\quad\quad\overline{x}=\frac{S5}{n-1}$ (6)
$\footnotesize std=\sqrt{\frac{S6-2*\overline{x}*S5+n\overline{x}^{2}}{n-1}}$
(7)

##  V Evaluation

###  V-A Experimental Setup and Methodology

We replicated the packet trace used in [9] over a real scenario. This
experiment consisted of a 20 minute-long DDoS attack generated from different
devices located in an external network, trying to deny the service provided by
a web service located in the DMZ of a local network. This trace, which has
traffic captured for 90 minutes, is composed of 762,973 DDoS packets and
1,382,900 benign packets, stored in a PCAP file.

Fig. 4 shows the implemented scenario. The data plane, emulated using Mininet,
consists of: i) a BMV2 virtual switch with P4 support (in charge of executing
the data plane strategy); ii) a host responsible for reproducing the traffic
trace using the TCPReplay tool (representing the external network where the
DDoS attack is originated); and iii) a victim host (Web Server), where all
replicated traffic is forwarded to. In turn, the control plane is composed by
the ONOS controller, which is connected to the BMV2 switch using the P4Runtime
interface. This plane has a classifier component, which loads a previously
trained ML-model. This scenario was implemented on a Core i5 5200 computer,
with 12 GB of RAM and the Ubuntu 18.04 LTE operating system.

Figure 4: Experimental setup.

The implementation of our proposed system was exposed to two different
workloads, one for the training phase of the ML model (WL1) and another for
the testing phase of the same model (WL2). To create both workloads, the pcap
file was divided into 18 sets of 5 minutes each, labeled from 1 to 18
considering their order in the trace. The sets with odd numbering were put
together to build WL1. Then, the sets with even numbering were also joined to
build WL2.

Before training the classification model, we had to build a database
containing flow information. To create it, an ONOS application was developed
to store, inside a .csv file, the feature set, and the respective tag (class:
“Benign”, or “DDoS”) for every flow reported by the data plane (see Fig 4).
These tags, needed to train the supervised model, were obtained directly from
the packets belonging to WL1. They were previously marked (00: Benign, 11:
DDoS) by modifying the last two bits of the IPv4 ToS header field.

Besides focusing on training the best ML model to detect DDoS attacks, we also
decided to investigate how the detection system could be affected by different
time window values at the data plane. For this assessment, we built a
different training dataset per each time window value. Table III shows the
characterization of the training datasets constructed considering different
time window values (5, 20, 40, and 60 seconds).

TABLE III: Training Dataset Characterization

Dataset per Time Window Duration
---
Tag / Time Window | 5 Sec | 20 Sec | 40 Sec | 60 Sec
Benign Flows | 61,736 | 40,462 | 31,894 | 29,670
DDoS Flows | 49,012 | 45,688 | 44,511 | 43,255
Total Flows per Dataset | 110,748 | 86,150 | 76,405 | 72,925

After creating the mentioned databases, the next step consisted of training
the ML models in an offline manner. We used and compared two ML classifiers
per each time window: RF and K-Nearest Neighbor (KNN) (8 models in total). To
build the models, we implemented cross-validation of 10 iterations using the
datasets shown in Table III. In each iteration, a grid search was performed to
find the best set of hyperparameter values that lead to the most accurate
models. After ten iterations, the best model was chosen (among the ten
evaluated). In Table IV, we show the best set of hyperparameter values with
which it was possible to train the best model found for each time window
duration.

TABLE IV: Best Hyperparameters / Training time

Random Forest (RF)
---
- | M1: 5 Sec | M2: 20 Sec | M3: 40 Sec | M4: 60 Sec
Max_depth | 6 | 6 | 6 | 6
N_estimators | 300 | 500 | 500 | 300
Training time [S] | 332.8 $\pm$ 6 | 304.4 $\pm$ 8.1 |  264.4 $\pm$ 20 | 272.6 $\pm$ 20
K-Nearest Neighbor (KNN)
- | M5: 5 Sec | M6: 20 Sec | M7: 40 Sec | M8: 60 Sec
# Neighbors | 3 | 3 | 3 | 3
Training time [S] | 59.8 $\pm$ 2 | 37.7 $\pm$ 1 | 36.3 $\pm$ 3 |  26.7 $\pm$ 1

In the testing phase, each model was pre-loaded into the classifier component.
Then, the WL2 was replicated eight times per each model for the online
evaluation. In these experiments, all packets of WL2 were also tagged to
compare the tag of each flow with the classifier’s classification result (in
real-time). In this phase, both the feature set and the flow tag were not
stored. Instead, they were sent to the classifier component.

The metrics used in the testing phase to evaluate the detection performance
are based on the number of true positive (TP), true negative (TN), false
positive (FP) and false negative (FN) classes (DDoS and Benign) obtained
during the experiment. The metrics are introduced as follows:

  * •

Accuracy is the number of correctly detected cases in the total flow sample,
considering both classes.

$\textstyle\small Accuracy=\frac{TN+TP}{TN+TP+FP+FN}$ (8)

  * •

Recall represents the proportion of DDoS samples correctly detected in
relation to the total DDoS flow samples. It is best known as the True Positive
Rate (TPR).

$\textstyle\small Recall=TPR=\frac{TP}{TP+FN}$ (9)

  * •

Selectivity represents the proportion of Benign samples correctly detected in
relation to the total Benign flow samples; also known as the True Negative
Rate (TNR).

$\textstyle\small Selectivity=TNR=\frac{TN}{TN+FP}$ (10)

  * •

F1_Score can be seen as the weighted average of the precision and recall
metrics values.

$\textstyle\small F1\\_score=\frac{2TP}{2TP+FP+FN}$ (11)

###  V-B Experimental Results

Table IV shows the average time to calculate the best set of hyperparameters
and train the model with them. We notice that KNN is the best option when it
comes to the performance of the training phase, as it is faster than RF.

Fig. 5 shows the detection accuracy results as a function of the time window
duration (in the testing phase). It is possible to observe that the eight
models trained lead to an accuracy higher than 93%, which is within the upper
range seen in the literature [6],[7]. Besides, the KNN accuracy results are
higher than the RF ones for all time windows. Nevertheless, the difference
between models does not exceed 1.2%.

Increasingly better results are obtained as the time window duration
increases, reaching the best values for time windows of 60 seconds. We
highlight here a vital trade-off between accuracy and detection delay. A
significant time window duration might lead to an intolerably high latency to
detect and mitigate a DDoS attack. We advocate that as the detection rates
vary just slightly (1.1% for KNN and 1.7% for RF), one should favor lower time
window durations.

Table V shows the results obtained for the remaining metrics. One can observe
how accurate every model is in classifying each class separately (Recall:
“DDoS”, Selectivity: “Benign”). Also, the F1 score shows the second indicator
of accuracy. Note that the main interest of the detection system is to have a
classification model very precisely classifying DDoS (low FN) and, at the same
time, presenting the least possible number of false alarms (low FP). According
to the metrics, a higher Recall value represents a model more accurately
detecting DDoS, and a higher Selectivity value represents a model with a lower
number of false alarms (see Equations 9 and 10). According to that, the M1
model is the most accurate in detecting DDoS attacks, with a Recall value of
98%. However, M1 has the lowest selectivity value, which makes this model one
of the least reliable, since the false alarm rate would be higher than the
other models. This analysis is reflected in the low value of the F1_Score.

Aiming at a better trade-off among accuracy, false alarms, and time window
duration, we consider that M3 and M7, both in the 40-second window, are the
best models to use by our detection system. These models have the closest
Recall and Selectivity values, which means a more balanced choice concerning
the mentioned optimization aspects.

Figure 5: Accuracy of the evaluated models as a function of window duration
TABLE V: Comparison of metric results obtained in the testing phase

Random Forest (RF)
---
T.W. / Metric | Recall | Selectivity | F1 Score
M1: 5 seg. | 0.982 $\pm$ 0.001 | 0.920 $\pm$ 0.003 | 0.934 $\pm$ 0.002
M2: 20 seg. | 0.933 $\pm$ 0.005 | 0.939 $\pm$ 0.003 | 0.933 $\pm$ 0.003
M3: 40 seg. |  0.957 $\pm$ 0.002 |  0.957 $\pm$ 0.003 |  0.952 $\pm$ 0.003
M4: 60 seg. | 0.963 $\pm$ 0.003 | 0.941 $\pm$ 0.002 | 0.959 $\pm$ 0.002
K-Nearest Neighbor (KNN)
T.W. / Metric | Recall | Selectivity | F1 Score
M5: 5 seg. | 0.967 $\pm$ 0.002 | 0.935 $\pm$ 0.003 | 0.937 $\pm$ 0.003
M6: 20 seg. | 0.951 $\pm$ 0.003 | 0.943 $\pm$ 0.004 | 0.945 $\pm$ 0.003
M7: 40 seg. |  0.970 $\pm$ 0.003 |  0.967 $\pm$ 0.003 |  0.962 $\pm$ 0.002
M8: 60 seg. | 0.970 $\pm$ 0.003 | 0.946 $\pm$ 0.003 | 0.964 $\pm$ 0.002

##  VI Conclusion and Future Work

In this paper, we presented ORACLE, an architecture implemented over an SDN/P4
environment that promotes the cooperation of both the control and data planes
to detect network attacks using Machine Learning models. ORACLE leverages data
plane programmability to extract flow information at a higher level of
granularity. This results in a more straightforward calculation and
classification of the feature set in the attack detection process. As proof of
concept, we implemented a DDoS detection system based on the computation of
intra-flow level features, which cannot be implemented in a traditional
SDN/OpenFlow environment. Obtained results show that the detection system has
an accuracy rate of up to 96% while reducing the processing complexity
performed by the controller. As future work, we envisage making ORACLE a
comprehensive detection system capable of detecting different types of
attacks.

## References

  * [1] S. Weisman. (2019) What is a distributed denial of service attack (ddos) and what can you do about them? norton. [Online]. Available: https://us.norton.com/internetsecurity-emerging-threats-what-is-a-ddos-attack-30sectech-by-norton.html
  * [2] J. C. C. Chica et al., “Security in sdn: A comprehensive survey,” _Journal of Network and Computer Applications_ , p. 102595, 2020.
  * [3] N. Sultana et al., “Survey on sdn based network intrusion detection system using machine learning approaches,” _Peer-to-Peer Networking and Applications_ , vol. 12, no. 2, pp. 493–501, Mar 2019.
  * [4] P. Bosshart et al., “P4: Programming protocol-independent packet processors,” _SIGCOMM CCR_ , vol. 44, no. 3, pp. 87–95, Jul. 2014.
  * [5] T. T. Nguyen and G. Armitage, “A survey of techniques for internet traffic classification using machine learning,” _IEEE communications surveys & tutorials_, vol. 10, no. 4, pp. 56–76, 2008.
  * [6] G. A. Ajaeiya et al., “Flow-based intrusion detection system for sdn,” in _IEEE ISCC 2017_. IEEE, 2017, pp. 787–793.
  * [7] A. S. da Silva et al., “Atlantic: A framework for anomaly traffic detection, classification, and mitigation in sdn,” in _IEEE NOMS 2016_. IEEE, 2016, pp. 27–35.
  * [8] C. Yoon et al., “Enabling security functions with sdn: A feasibility study,” _Computer Networks_ , vol. 85, pp. 19–35, 2015.
  * [9] I. Sharafaldin, A. H. Lashkari, and A. A. Ghorbani, “Toward generating a new intrusion detection dataset and intrusion traffic characterization.” in _ICISSP_ , 2018, pp. 108–116.