# Constructing large scale biomedical knowledge bases from scratch with rapid
annotation of interpretable patterns

Julien Fauqueur
BenevolentAI
4-8 Maple St, London
W1T 5HD
<EMAIL_ADDRESS>
Ashok Thillaisundaram11footnotemark: 1
BenevolentAI
4-8 Maple St, London
W1T 5HD
<EMAIL_ADDRESS>
Theodosia Togia11footnotemark: 1
BenevolentAI
4-8 Maple St, London
W1T 5HD
<EMAIL_ADDRESS>
Equal contribution. Listing order is alphabetical. Theodosia proposed and co-
ordinated the research project, built the early prototypes and contributed the
different methods for extracting and lexicalising patterns. Ashok provided
conceptual work on the metrics for ranking simplifications and for the
intrinsic evaluation, developed the simplification extraction module, ran the
experiments for the automated workflow (with all the parameter variations) and
performed all the extrinsic evaluations. Julien was mainly responsible for the
system architecture and workflow, the intrinsic evaluation (including
interacting with the experts), handling negation and speculation and the
clustering algorithm.

(May 2019)

###### Abstract

Knowledge base construction is crucial for summarising, understanding and
inferring relationships between biomedical entities. However, for many
practical applications such as drug discovery, the scarcity of relevant facts
(e.g. gene X is therapeutic target for disease Y) severely limits a domain
expert’s ability to create a usable knowledge base, either directly or by
training a relation extraction model. In this paper, we present a simple and
effective method of extracting new facts with a pre-specified binary
relationship type from the biomedical literature, without requiring any
training data or hand-crafted rules. Our system discovers, ranks and presents
the most salient patterns to domain experts in an interpretable form. By
marking patterns as compatible with the desired relationship type, experts
indirectly batch-annotate candidate pairs whose relationship is expressed with
such patterns in the literature. Even with a complete absence of seed data,
experts are able to discover thousands of high-quality pairs with the desired
relationship within minutes. When a small number of relevant pairs do exist -
even when their relationship is more general (e.g. gene X is biologically
associated with disease Y) than the relationship of interest - our system
leverages them in order to i) learn a better ranking of the patterns to be
annotated or ii) generate weakly labelled pairs in a fully automated manner.
We evaluate our method both intrinsically and via a downstream knowledge base
completion task, and show that it is an effective way of constructing
knowledge bases when few or no relevant facts are already available.

##  1 Introduction

In many important biomedical applications, experts seek to extract facts that
are often complex and tied to particular tasks, hence data that are truly fit
for purpose are scarce or simply non-existent. Even when only binary relations
are sought, useful facts tend to be more specific (e.g. mutation of gene X has
a causal effect on disease Y in an animal model) than associations typically
found in widely available knowledge bases. Extracting facts with a pre-
specified relationship type from the literature in the absence of training
data often relies on handcrafted rules, which are laborious, ad-hoc and hardly
reusable for other types of relations. Recent attempts to create relational
data from scratch by denoising the output of multiple hand-written rules
Ratner et al. (2016) or by augmenting existing data through the induction of
new black-box heuristics Varma and Ré (2018) are still dependent on ad-hoc
human effort or pre-existing data. Our approach involves discovering and
recommending, rather than prescribing, rules. Importantly, our rules are
presented as text-like patterns whose meaning is transparent to human
annotators, enabling integration of an automatic data generation (or
augmentation) system with a domain expert feedback loop.

In this work, we make the following contributions:

  * •

We propose a number of methods for extracting patterns from a sentence in
which two eligible entities co-occur; different types of patterns have
different trade-offs between expressive power and coverage.

  * •

We propose a simple method for presenting patterns in a readable way, enabling
faster, more reliable human annotation

  * •

For cases where a small number of seed pairs are already available, we propose
a method which utilises these seed pairs to rank newly discovered patterns in
terms of their compatibility with the existing data. The resulting patterns
can be used with or without a human in the loop.

The rest of the paper is organised as follows. Section 2 describes some
related work. Section 3 explains the relationship between patterns and
labelling rules and presents some pattern types along with techniques for
rendering them interpretable. Section 4 provides a high-level overview of the
system and covers details of our different workflows (with and without seed
data; with and without human feedback). Section 5 explains how we measure the
system’s performance both intrinsically and via a downstream knowledge base
completion task. In section 6, we report the details of our main experiments
while in sections 7 and 8 we present some analysis along with further
experiments. The paper ends with conclusions and proposals for further work in
section 9.

##  2 Related work

The idea of extracting entity pairs by discovering textual patterns dates back
to early work on bootstrapping for relation extraction with the DIPRE system
Brin (1999). This system was designed to find co-occurrences of seed entity
pairs of a known relationship type inside unlabelled text, then extract simple
patterns (exact string matches) from these occurrences and use them to
discover new entity pairs. Agichtein et al. Agichtein and Gravano (2000)
introduced a pattern evaluation methodology based on the precision of a
pattern on the set of entity pairs which had already been discovered; they
also used the dot product between word vectors instead of an exact string
match to allow for slight variations in text. Later work Greenwood and
Stevenson (2006); Xu et al. (2007); Alfonseca et al. (2012) has proposed more
sophisticated pattern extraction methods (based on dependency graphs or kernel
methods on word vectors) and different pattern evaluation frameworks (document
relevance scores).

Two recent weak supervision techniques, Data Programming Ratner et al. (2016)
and the method underlying the Snuba system Varma and Ré (2018) have attempted
to combine the results of handcrafted rules and weak base classifiers
respectively. Data Programming involves modelling the accuracy of ideally
uncorrelated rules devised by domain experts, then combining their output into
weak labels. Although this approach does not require any seed data, it does
rely on handwritten rules, which are both time consuming and ad-hoc due to the
lack of a data-driven mechanism for exploring the space of possible rules.
Snuba learns black-box heuristics (parameters for different classifiers) given
seed pairs of the desired relationship. This method avoids the need for
manually composing rules, however, the rules it learns are not interpretable,
which makes the pipeline harder to combine with an active learning step.
Second, the system requires gold standard pairs. In contrast, while our system
can leverage gold standard annotations, if available, in order to reduce the
space of discovered rules, as well as tune the ranking of newly discovered
patterns, it is entirely capable of starting without any gold data if ranking
is heuristics-based (e.g. prioritisation by frequency) and a human assesses
the quality of the highest coverage rules suggested. Our method does not
preclude use within a data programming setup as a way of discovering labelling
functions or within a system like Snuba, as a way of generating seed pairs.
Another body of work, distant supervision Verga et al. (2018); Lin et al.
(2016) has been a recent popular way to extract relationships from weak
labels, but does not give the user any control on the model performance.

A well known body of work, OpenIE Banko et al. (2007); Fader et al. (2011);
Mausam et al. (2012); Angeli et al. (2015) aims to extract patterns between
entity mentions in sentences, thereby discovering new surface forms which can
be clustered Mohamed et al. (2011); Nakashole et al. (2012) in order to reveal
new meaningful relationship types. In the biomedical domain, Percha and Altman
Percha and Altman (2018) attempt something similar by extracting and
clustering dependency patterns between pairs of biomedical entities (e.g.
chemical-gene, chemical-disease, gene-disease). Our work differs from these
approaches in that we extract pairs for a pre-specified relationship type
(either from scratch or by augmenting existing data written with specific
guidelines), which is not guaranteed to correspond to a cluster of discovered
surface forms.

##  3 Extracting interpretable patterns

In a rule-based system, a rule, whether handwritten or discovered, can be
described as a hypothetical proposition “$if~{}P~{}then~{}Q$”, where $P$ (the
antecedent) is a set of conditions that may be true or false of the system’s
input and $Q$ (the consequent) is the system’s output. For instance, a
standard rule-based relation extraction system can i) take as input a pair of
entities (e.g. TNF-GeneID:7124 and Melanoma-MESH:D008545) that are mentioned
in the same piece of text, ii) test whether certain conditions are met (e.g.
presence of lexical or syntactic features) and iii) output a label (e.g. 1:
Therapeutic target, 0: Not therapeutic target.)

In this work, patterns are seen as the antecedents of rules that determine
which label (consequent) should be assigned to some input (e.g. candidate pair
+ text that mentions it.) We aim to extract patterns that are expressive
enough to allow a system or a domain expert to discriminate between the
different labels available for an input but also generic enough to apply to a
wide range of inputs. In this work, we have made the following simplifying
assumptions:

  1. 1.

Relationships are binary (i.e. hold between exactly two entities).

  2. 2.

A pair of entities are candidates for relation extraction if they are
mentioned simultaneously in the same sentence.

  3. 3.

There is a one-to-many relationship between patterns and inputs. An input
(i.e. sentence + entity pair) is described by a single pattern (although this
pattern can be a boolean combination of other patterns) but one pattern can
correspond to multiple inputs.

  4. 4.

We can select patterns which are expressive enough to represent the
relationship, so it is possible to classify the input from which a given
pattern has been extracted by examining the pattern alone. However, the
omitted part of the sentence may contain contextual information which
specifies the condition when or where the relationship holds. Modeling such
contextual information would be useful but is beyond the scope of this work. A
consequence of this assumption is that it is possible to batch-annotate a
group of inputs that correspond to the same pattern by annotating the pattern
itself.

#### Pattern interpretability

An important consideration in this research is pattern interpretability, which
could assist domain experts (who are not NLP experts) in exploring the space
of labelling rule antecedents for a given relationship type in a given corpus.
Hence, for each pattern, we construct what we call a pattern lexicalisation,
that is converting a pattern to a readable text-like sequence.

#### Pattern types

Simple patterns, which can potentially be combined with boolean operators, can
be of different types. We illustrate some types of patterns used in our
experiments through the following example sentences that include mentions of a
gene-disease pair: “We investigate the hypothesis that the knockdown of BRAF
may affect melanoma progression.” “The study did not record higher NF-kb
activity in cancer patients.”

Below are some types of patterns, as well as their lexicalisations:

  * •

keywords: words (e.g. ‘inhibiting’) or lemmas (e.g. ‘inhibit’) in the entire
sentence or in the text between the entities. This pattern’s lexicalisation
is, trivially, the word itself.

  * •

path: shortest path between the two entity mentions in the dependency graph of
the sentence. For instance, in example (3), the path could be BRAF <-pobj- of
<-prep- knockdown <-nsubj- affect -dobj-> progression -compound-> melanoma; in
example (3), the path could be NF-kb <-compound- activity -prep-> in -pobj->
patients -compound-> cancer). To lexicalise patterns of this type, we extract
the nodes (i.e. words) from the path, arrange them as per their order in the
sentence and replace the entity mentions by a symbol denoting simply their
entity types. For instance, the first pattern becomes "knockdown of GENE
affect DISEASE progression". This pattern is used extensively in our
experiments because it strikes a good balance between expressive power and
coverage. We call its lexicalisation a simplification because it is a text-
like piece that simplifies a sentence by discarding all but the most essential
information.

  * •

path_root: the root (word with no incoming edges) of the shortest path between
the two entities (e.g. ‘affect’ and ‘activity’ in examples (3) and (3)
respectively). The lexicalisation could be trivial (i.e. the root itself) or,
alternatively, if this pattern is used in an AND boolean combination with the
path pattern, the root can simply be highlighted (e.g. "knockdown of GENE
affect DISEASE progression")

  * •

sentence_root: the root of the dependency graph of the entire sentence (e.g.
‘investigate’ and ‘record’ in the examples above), which is often not the same
as root of the path connecting the two entities. It can be lexicalised
similarly to the pattern above.

  * •

path_between_roots: the path between the root of the entire sentence and the
root of the path between the two entities (e.g. investigate -dobj-> hypothesis
-acl-> affect and record -dobj-> activity for examples (3) and (3)
respectively). The pattern can be lexicalised as what we have called
“simplification” (e.g. investigate hypothesis affect, or, if AND-ed with the
path pattern, all the words from both patterns can be merged and arranged as
per their original order in the sentence, potentially with some highlighting
to differentiate the two simpler patterns (e.g. "investigate hypothesis
knockdown of GENE affect DISEASE progression")

  * •

sentence_root_descendants: the direct descendants of the sentence_root, for
instance, ‘did’, ‘not’ and ‘activity’ in the example (3), because of the edges
did <-aux- record, not <-neg- record and record -dobj-> activity. To
lexicalise this pattern, we can extract the words and merge them with words of
other patterns. Alternatively, we can devise some simpler sub-patterns, for
instance, descendants with aux, that is auxiliary, edges, such as ‘may’, or
descendants with neg edges such as ‘not’ and place them outside any
simplification: "investigate hypothesis knockdown of GENE affect DISEASE
progression + hedging:[may]"

  * •

path_root_descendants: the direct descendants of the root of the path between
the entities (e.g. ‘may’ and ‘progression’ in example (3) because may <-aux-
affect and affect -dobj-> progression; ‘higher’ and ‘in’ in the example (3)
because higher <-amod- activity and activity -prep-> in). Its lexicalisation
can be the same as that of the previous pattern type.

Other examples of patterns could be regular expressions or rules informed by
an external biomedical ontology (e.g. GENE is a Rhodopsin-like receptor) or
with lexical information from databases like WordNet Miller (1995) (e.g. for
increasing pattern coverage leveraging synonyms or hypernyms of words in a
pattern.)

It should be obvious that the more expressive a pattern becomes (for instance
by AND-ing multiple other patterns), the less capable it is of subsuming many
sentences. It is important to discover patterns with this trade-off in mind.

##  4 System overview

In this section, we will describe each step of our system, outlined in Figure
1.

Figure 1: System overview. Diamond box is present only in workflows with seed
labels available (i.e. “no expert but labels” and “expert with labels”),
elliptical box is only present in workflows involving an expert (i.e. “expert
- no labels” and “expert with labels”) and rectangular boxes are always
present.

###  4.1 Data preparation

#### Extracting named entities and patterns

The first step is performing named entity recognition (NER) on the sentences
in the corpus to enable us to identify all the sentences which contain entity
pairs of interest. Our experiments are focused on gene-therapeutic target
pairs, however, the system is designed to be agnostic to different types of
entities and relationships between them. We then extract the desired patterns
from each of these sentences, as described in section 3. For simplicity, we
limited our experiments to sentences that contain exactly one gene-disease
pair, however, extending the system to handle multiple pairs is
straightforward.

We index each sentence in a database along with the lexicalisation for its
pattern (e.g. the ‘simplification’ for path or path_between_roots patterns)
and the entity pair found. This allows us to easily query this database i) for
all entity pairs that correspond to a pattern (which is now lexicalised and
stored as a string) or ii) for all patterns that correspond to an entity pair.

#### Filtering out sentences with negation and hedging.

Since we are interested in inputs which unambiguously encode affirmations of
facts about entities, we filter out any sentences which contain negation,
speculation, or other forms of hedging. We adopt a conservative approach by
excluding sentences which match specific instantiations of these pattern
types: i) keywords (e.g. presence of terms such as “no”, “didn’t”, “doubt”,
“speculate” etc. in the sentence); our list is modified from NegEx Chapman et
al. (2013), ii) sentence_root AND sentence_root_descendants (e.g. “study we
investigated”, which makes no statement of results), iii) path_root AND
path_root_descendants (e.g. “was used”, “was performed”), iv)
path_between_roots (e.g. “found associated”) This filtering is applied at all
stages in our system where sentences are used.

###  4.2 Ranking patterns

Below we describe methods for ranking and selecting top patterns in the
presence or absence of domain expertise or labelled training data.

#### Baseline workflow: “no expert - no labels”

In this workflow, we simply extract new pairs using simplifications (from the
path pattern type, but other types are also described in our experiments) that
have a high enough ($>=5$) count of entity pairs.

#### Manual curation in the absence of any labelled training data: “expert -
no labels”

In this workflow, we have a domain expert (a biologist) available for manual
curation but there is no labelled training data. It is not possible for a
domain expert to annotate all simplifications; this would be too time-
consuming. In such cases, active learning can be helpful in deciding which
simplifications should be shown to the domain experts for manual curation to
best improve the output of our system. The approach that we adopt here is
simple but the system could be extended with more sophisticated active
learning strategies. We rank the simplifications by their count of entity
pairs; by this we mean the number of unique pairs contained in the sentences
in our corpus which correspond to a given simplification (similar to section
4.2). We then show the top ranked simplifications (i.e. those with the
greatest pair count) to our domain expert with a fixed number of random
example sentences who then decides if a given simplification is an appropriate
heuristic to extract new entity pairs from the corpus, by selecting one of
three options “Yes”, “No”, “Maybe”.

#### Automated workflow: “no expert but labels”

For this workflow, a set of gold standard pairs exists as training data but we
have no domain experts available. The sentence simplifications can be ranked
using various metrics calculated against the gold standard training data. Each
simplification is considered as a classifier: A given pair is ‘classified’ by
the simplification as positive if the pair can be discovered using the
simplification’s underlying rule in the corpus. Otherwise, it is classified as
negative. The metrics we use to rank the simplifications are precision and
recall. The gold standard pairs will form the positive pairs in our training
data. To obtain negative pairs, we operate under the closed world assumption:
any entity pair found in our corpus of sentences not present in our gold
standard set is taken to be negative. This results in an imbalance in the
sizes of positive and negative training data which skews the value of
precision. To address this, we use a precision metric where the number of true
positives and false positives are normalised by the total number of positive
and negative pairs respectively in our training data. For each simplification
$S$ we define true positives ($TP_{S}$) and false positives ($FP_{S}$) as the
sets of correctly and incorrectly positive-labelled entity pairs respectively.
Our variant of precision for a simplification $S$ is then,
$precision_{S}=\frac{|TP_{S}|/N_{P}}{|TP_{S}|/N_{P}+|FP_{S}|/N_{N}}$ where
$N_{P}$ and $N_{N}$ are the number of positive and negative pairs respectively
in the training data. With this metric, if a simplification classifies 10% of
the positive pairs as true positives and 10% of the negative pairs as false
positives then $precision_{S}=\frac{0.1}{0.1+0.1}=0.5$. The metric utilises
the percentage of each class instead of the absolute number of pairs, as would
be the case for the standard precision metric. The definition of recall for a
given simplification $S$ is with respect to just the positive training data
and is thus unaffected by an imbalance in the sizes.

#### Manual curation with labelled data: “expert with labels”

For this workflow, both domain experts and labelled training data are
available to us. We improve on our methodology in the “expert - no labels”
workflow by making use of the metrics discussed in the “no expert but labels”
workflow which are calculated using the labelled training data. As we want to
maximise the number and precision of new pairs extracted, we keep only
simplifications with recall and precision above certain respective thresholds
and present them to domain experts ranked by pair count to ensure they see the
most impactful simplifications first.

###  4.3 Generating new pairs

All previous stages aim at generating a list of good simplifications. We now
have a collection of rules which can be used to extract new entity pairs from
the corpus. Any simplification selected as useful implies that all entity
pairs recovered from the corpus using this rule can be added as positive
examples to the dataset. With the selected simplifications, we can batch-
annotate thousands of sentences, and hence pairs, with minimal effort. We
simply query our database for all new pairs which are found in a sentence
expressing any of our selected simplifications.

#### Clustering simplifications

We found that many simplifications can be very similar up to a few characters.
We create clusters of quasi-identical simplifications, and use them i) to
enforce diversity in the selection of simplifications for the user to
annotate, by picking only one simplification per cluster and, ii) to safely
extend the selection of positive simplification to other simplification in the
cluster. We create clusters of simplifications by detecting connected
components in a graph where the nodes are the simplifications and the edges
are between simplifications which are at a maximum Levenshtein distance of 2.
This allows us to be invariant to plural forms, upper/lower case, to short
words like in/of etc. Note that some (not all) of these variations could be
captured with a lemmatiser. Example of a distance 2 cluster:
{GENE effects on DISEASE,
GENE effect on DISEASE,
GENE effects in DISEASE}
With a distance of 2, we typically increase the number of positive
simplifications by 50%, which significantly increases the recall on new pairs.

##  5 Evaluation

We implement two evaluation frameworks. The first is an intrinsic evaluation
of the quality of the new extracted pairs. The second is extrinsic; we
consider how the inclusion of the new pairs discovered by our system affects
the performance of a downstream knowledge base completion task.***We consider
the second type of evaluation extrinsic because knowledge base completion aims
to recover latent relationships, whereas knowledge base construction, which
the system is built for, is limited to extracting pairs from the literature.

###  5.1 Intrinsic evaluation

#### Pair-level

Our aim in this subsection is to construct an intrinsic evaluation framework
which can directly measure the quality of the discovered pairs. We do this by
holding out a fraction of the gold standard positive pairs and the negative
pairs (under the closed world assumption) to be used as a test set. The
remaining fraction is used as training data. We evaluate our system by
measuring its recall, specificity (true negative rate), precision, and F-score
against this test set. In more detail, the new pairs discovered by our
selected simplifications are taken to be the positive pairs predicted by our
system. The overlap between these new pairs and the positive test set are the
true positives ($TP$) while the overlap with the negative test set are the
false positives ($FP$). Recall and specificity take their standard
definitions. Again, we consider a precision score which is normalised to
correct for the imbalance in numbers between positive and negative pairs,
$precision=\frac{|TP|/N_{P}}{|TP|/N_{P}+|FP|/N_{N}}$, where $N_{P}$ and
$N_{N}$ are the numbers of positive and negative pairs respectively present in
the test set (as described in section 4.2). We take the F-score to be the
harmonic mean of this precision variant and recall.

#### Simplification-level

For the manual workflows, we also consider the expert annotations while
assessing the quality of the simplifications. We report $MSP$, the manual
simplification precision, based on $N_{Yes}$, $N_{No}$ and $N_{Maybe}$, the
number of simplifications that the expert has annotated as “Yes”, “No” and
“Maybe”. $MSP=\frac{N_{Yes}}{N_{Yes}+N_{No}+N_{Maybe}}$. We expect MSP to be
as high as possible.

#### Extrinsic evaluation via knowledge base completion

The setup for our extrinsic evaluation framework is straightforward and
intuitive. The initial gold standard set of positive pairs is split into
training and test data. A graph completion model is then trained using the
training data and evaluated to determine whether it can predict the existence
of the pairs in the test data. To determine whether our knowledge base
construction system can add value, we use the new pairs found from our system
to augment the training data for the graph completion model, and observe
whether this improves its performance against the test set. We use ComplEx
Trouillon et al. (2017), a well-established tensor factorisation model, as our
knowledge base completion model. We provide standard information retrieval
metrics to quantify the performance of the graph completion model. These are
the precision, $P(k)$, and recall, $R(k)$, calculated for the top $k$
predictions along with the mean average precision ($mAP$). For gene-disease
entity pairs, for example, $mAP=\frac{1}{N_{d}}\sum\limits_{d}AveP$, where the
sum is over the diseases $d$ with $N_{d}$ being the total number of diseases,
and $AveP=\sum\limits_{k}P(k)\left(R(k)-R(k-1)\right)$ with $P(k)$ and $R(k)$
as defined above.

##  6 Main experiments and results

###  6.1 Datasets

For all the following experiments, our data was drawn from the following
datasets: DisGeNET Pinero et al. (2016) and Comparative Toxicogenomics
Database (CTD) Davis et al. (2018). CTD contains two relation types:
‘marker/mechanism’ and ‘therapeutic’. We use both the entire CTD dataset and
the subset of therapeutic gene-disease pairs which we refer to as CTD
therapeutic.

The datasets above are first restricted to human genes and then to the gene-
disease pairs which appear in our corpus of sentences; this corpus consists of
sentences from PubMed articles which have been restricted, for simplicity, to
sentences which contain just one gene-disease pair each. With these
restrictions in effect, the CTD dataset has 8828 gene-disease pairs, CTD
therapeutic has 169 pairs, and Disgenet has 33844 pairs.

###  6.2 Intrinsic evaluation results

In table 1, we report the pair-level metrics (see section 5.1) for our three
proposed workflows and a baseline (see section 4). We also report the expert-
based metric $MSP$ (see section 5.1) for the two manual workflows. The CTD
therapeutic dataset was the most suitable dataset for this evaluation because
i) it is very relevant to crucial domains of application such as drug
discovery, and ii) its small size makes it a good candidate for expansion. In
each session, the expert annotated 200 simplifications accompanied by 20
sentences. It took the expert about 3 hours to annotate the first session,
which is a rapid way to generate thousands of new pairs from scratch.

Selection method | MSP | New pairs | Recall | Specificity | Precision | F-score
---|---|---|---|---|---|---
expert with labels | 0.315 | 8875 | 0.286 | 0.976 | 0.923 | 0.436
expert - no labels | 0.265 | 9560 | 0.250 | 0.975 | 0.908 | 0.392
no expert but labels | - | 30006 | 0.679 | 0.920 | 0.894 | 0.772
no expert - no label (baseline) | - | 59913 | 0.774 | 0.842 | 0.830 | 0.801
Table 1: Intrinsic evaluation results for the main experiments on the CTD
therapeutic dataset. This was carried out with a train/valid/test split of
0.4/0.1/0.5, and precision threshold of 0.6 for the ‘expert with labels’ and
‘no expert but labels’ workflows. MSP is our “manual simplification precision”
metric. The precision and F-scores reported here are normalised as described
in the section 4.2.

We find that our three main proposed workflows (‘expert - with labels’,
‘expert - no labels’, and the fully automated ‘no expert but labels’) all
discover a significant number of new gene-disease therapeutic pairs. As
confirmed by both pair-level and user-based metrics, incorporating the use of
domain expert’s time and the use of labelled data results in higher precision
at the expense of recall.

###  6.3 Extrinsic evaluation results

In table 2, we list the results of the downstream knowledge base completion
task for the fully automated workflow and the baseline. We compare the
performance of our knowledge base completion model when trained with just the
initial seed training data versus the seed training data augmented with the
new pairs discovered by our fully automated workflow (and baseline workflow).

The addition of new pairs from the fully automated workflow gives us a higher
mean average precision ($mAP$) than with just the seed dataset. We obtain a
higher precision (for the top 100 and top 1000 predictions) while maintaining
the same level of recall. For the baseline workflow, $mAP$ is higher but with
lower precision (for the top 100 and 1000 predictions respectively).

Selection method | New pairs | MAP | Precision | Recall
---|---|---|---|---
seed dataset only | - | 0.0414 | 0.0179 / 0.0179 | 1.0 / 1.0
no expert but labels | 30006 | 0.0545 | 0.0192 / 0.0192 | 1.0 / 1.0
no expert - no label (baseline) | 59913 | 0.1885 | 0.01 / 0.0015 | 0.6019 / 0.9208
Table 2: Extrinsic evaluation results for the CTD therapeutic dataset. The
experiment parameters are the same as those given in table 1. Precision
figures are given as ‘top 100 / top 1000’ and similarly for recall.

##  7 Top simplifications

In table 3, we show the simplifications with the highest count of Disease-Gene
pairs in our whole corpus (after the sentence filtering), which have been
annotated by the expert as “Yes” or “No”, for the CTD therapeutic dataset.
While “Yes” and “No” patterns look similar, we can clearly see differences in
language. The “No” annotations look unspecific while the “Yes” ones express
the target has a therapeutic effect on the disease.

Pairs |  “Yes” simplif.
---|---
3345 |  role of GENE in DISEASE
839 |  GENE plays in DISEASE
648 |  GENE involved in DISEASE
321 |  GENE target in DISEASE
318 |  GENE target for DISEASE
289 |  GENE mice develop DISEASE
279 |  DISEASE caused by mutations in GENE
276 |  GENE gene for DISEASE
273 |  role of GENE in development of DISEASE
237 |  GENE promotes DISEASE

Pairs |  “No” simplif.
---|---
6629 |  GENE DISEASE
4110 |  DISEASE GENE
3350 |  GENE and DISEASE
2370 |  GENE in DISEASE
2333 |  DISEASE and GENE
1228 |  GENE DISEASE cells
904 |  DISEASE of GENE
879 |  DISEASE in GENE
638 |  DISEASE in GENE mice
572 |  role for GENE in DISEASE
528 |  GENE in DISEASE patients

Table 3: Top 10 simplifications for CTD Therapeutic annotated “Yes” (left) and
“No” (right) by the expert.

##  8 Further experiments

We performed several other experiments using our fully automated workflow to
evaluate the quality of the new pairs discovered as we varied our experiment
parameters.

We consider three dimensions of variation: varying the precision threshold for
selecting simplifications, varying the size of the seed training set, and
varying the expressiveness of the simplification (for example, by including
the sentence_root or restricting to simplifications with at least a specified
number of words).

The intrinsic evaluation results for these experiments are listed in tables 4,
5, and 6. In all cases, as we make our system more selective either by raising
the precision threshold, by starting with fewer seeds pairs, or by restricting
to more informative simplifications, we unsurprisingly obtain higher precision
at the expense of lower recall.

The extrinsic evaluation framework is less sensitive to these changes but
improvements were observed (without any noticeable trend) for all these
parameter changes.

Dataset |  Thres. |  New pairs |  R |  S |  P |  F
---|---|---|---|---|---|---
CTD |  0.8 |  29592 |  0.297 |  0.918 |  0.783 |  0.430
CTD |  0.4 |  50329 |  0.379 |  0.863 |  0.735 |  0.500
DG |  0.8 |  17441 |  0.180 |  0.947 |  0.773 |  0.292
DG |  0.4 |  45446 |  0.314 |  0.867 |  0.703 |  0.434
Table 4: Intrinsic evaluation results (Recall, Specificity, Precision and F-score) on CTD and DisGeNET (DG) as we vary the precision threshold for the ‘no expert but labels’ workflow. Experiments are done with a train/valid/test split of 0.8/0.1/0.1 and we restrict to simplifications with at least 5 words to ensure that they are reasonably expressive. Train/val/test |  New pairs |  R |  S |  P |  F
---|---|---|---|---|---
0.8/0.1/0.1 |  29592 |  0.297 |  0.918 |  0.783 |  0.430
0.5/0.1/0.4 |  25539 |  0.274 |  0.930 |  0.798 |  0.408
0.2/0.1/0.7 |  18268 |  0.225 |  0.950 |  0.818 |  0.352
Table 5: Intrinsic evaluation results (Recall, Specificity, Precision and F-score) for CTD as we vary size of the seed training data for the ‘no expert but labels’ workflow. Experiments are done with a precision threshold of 0.8 and we restrict to simplifications with at least 5 words to ensure that they are reasonably specific. Min length |  sentence root |  New pairs |  R |  S |  P |  F
---|---|---|---|---|---|---
5 |  No |  29592 |  0.297 |  0.918 |  0.783 |  0.430
5 |  Yes |  13284 |  0.174 |  0.963 |  0.824 |  0.288
7 |  No |  5313 |  0.066 |  0.986 |  0.824 |  0.122
7 |  Yes |  1814 |  0.028 |  0.995 |  0.856 |  0.055
Table 6: Intrinsic evaluation results (Recall, Specificity, Precision and
F-score) for CTD as we vary simplification expressive power (minimum length)
for the ‘no expert but labels’ workflow. Experiments are done with a
train/valid/test split of 0.8/0.1/0.1 and a precision threshold of 0.8.

##  9 Conclusions and further work

We have presented a simple and effective method for knowledge base
construction when the desired relational data are scarce or absent. We have
demonstrated its effectiveness via i) classification metrics on a held-out
test set, ii) human evaluation and iii) performance on a downstream knowledge
base completion task. We further show that in the presence of a small set of
data, it is possible to control the quality of the pairs discovered, by
introducing stricter precision thresholds when ranking patterns. Our method
could in principle be extended in order to: 1) handle higher-order (e.g.
ternary) relations between tuples, as opposed to pairs (for instance using
dependency subgraphs that connect more than two entities cooccurring in a
sentence), 2) discover explicit negative examples of a binary relation instead
of simply positive examples, 3) train sentence-level relation extraction
systems, 4) collect and utilise continuous, rather than discrete annotations
for each pattern (e.g. annotators could indicate the percentage of correct
example sentences that correspond to a pattern displayed) as part of a more
sophisticated active learning strategy, 5) extract patterns from a semantic
representation Banarescu et al. (2013) and, finally, 6) map patterns to a
vector space using a distributional representation (e.g. defined by their
neighbouring words in sentences) and cluster them for an optimal balance
between expressive power and coverage.

## Acknowledgments

We are very grateful to Nathan Patel for his engineering support and to Alex
de Giorgio for his thorough feedback and domain expertise. We would also like
to thank many of our colleagues working on drug discovery and link prediction
for insightful conversations, as well as Felix Kruger for proofreading the
final version of this paper.

## References

  * Agichtein and Gravano (2000) Eugene Agichtein and Luis Gravano. 2000.  Snowball: Extracting relations from large plain-text collections.  In _Proceedings of the Fifth ACM Conference on Digital Libraries_ , DL ’00, pages 85–94, New York, NY, USA. ACM.
  * Alfonseca et al. (2012) Enrique Alfonseca, Katja Filippova, Jean-Yves Delort, and Guillermo Garrido. 2012\.  Pattern learning for relation extraction with a hierarchical topic model.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Short Papers - Volume 2_ , ACL ’12, pages 54–59, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Angeli et al. (2015) Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D. Manning. 2015.  Leveraging linguistic structure for open domain information extraction. In _ACL (1)_ , pages 344–354. The Association for Computer Linguistics.
  * Banarescu et al. (2013) Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013\.  Abstract meaning representation for sembanking.  In _Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse_ , pages 178–186, Sofia, Bulgaria. Association for Computational Linguistics.
  * Banko et al. (2007) Michele Banko, Michael J. Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni. 2007.  Open information extraction from the web.  In _Proceedings of the 20th International Joint Conference on Artifical Intelligence_ , IJCAI’07, pages 2670–2676, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * Brin (1999) Sergey Brin. 1999.  Extracting patterns and relations from the world wide web.  In _Selected Papers from the International Workshop on The World Wide Web and Databases_ , WebDB ’98, pages 172–183, London, UK, UK. Springer-Verlag.
  * Chapman et al. (2013) WW Chapman, D Hillert, S Velupillai, M Kvist, M Skeppstedt, BE Chapman, M Conway, M Tharp, DL Mowery, and L. Deleger. 2013.  Extending the negex lexicon for multiple languages.  In _Proceedings of the 14th World Congress on Medical & Health Informatics (MEDINFO)_.
  * Davis et al. (2018) AP Davis, CJ Grondin, RJ Johnson, D Sciaky, R McMorran, J Wiegers, TC Wiegers, and CJ Mattingly. 2018.  The comparative toxicogenomics database: update 2019.  _Nucleic Acids Res._
  * Fader et al. (2011) Anthony Fader, Stephen Soderland, and Oren Etzioni. 2011.  Identifying relations for open information extraction.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , EMNLP ’11, pages 1535–1545, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Greenwood and Stevenson (2006) MA Greenwood and Mark Stevenson. 2006.  Improving semi-supervised acquisition of relation extraction patterns.  In _Proceedings of the Workshop on Information Extraction Beyond The Document_ , IEBeyondDoc ’06, pages 29–35, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Lin et al. (2016) Yankai Lin, Zhiyuan Liu, Shiqi Shen, Huanbo Luan, and Maosong Sun. 2016.  Neural relation extraction with selective attention over instances.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2124–2133. Association for Computational Linguistics.
  * Mausam et al. (2012) Mausam, Michael Schmitz, Robert Bart, Stephen Soderland, and Oren Etzioni. 2012\.  Open language learning for information extraction.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , EMNLP-CoNLL ’12, pages 523–534, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Miller (1995) George Miller. 1995.  Wordnet A lexical database for English.  _Communications of ACM_ , 38(11):39–41.
  * Mohamed et al. (2011) Thahir P Mohamed, Estevam R Hruschka Jr, and Tom M Mitchell. 2011.  Discovering relations between noun categories.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 1447–1455. Association for Computational Linguistics.
  * Nakashole et al. (2012) Ndapandula Nakashole, Gerhard Weikum, and Fabian M. Suchanek. 2012.  Discovering and exploring relations on the web. _PVLDB_ , 5(12):1982–1985.
  * Percha and Altman (2018) Bethany Percha and Russ B. Altman. 2018.  A global network of biomedical relationships derived from text. _Bioinformatics_ , 34(15):2614–2624.
  * Pinero et al. (2016) Janet Pinero, Alex Bravo, Nuria Queralt-Rosinach, Alba Gutierrez-Sacristan, Jordi Deu-Pons, Emilio Centeno, Javier Garcia-Garcia, Ferran Sanz, and Laura I. Furlong. 2016.  Disgenet: a comprehensive platform integrating information on human disease-associated genes and variants. _Nucl. Acids Res._
  * Ratner et al. (2016) Alexander Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. 2016.  Data Programming: Creating Large Training Sets, Quickly.  _arXiv e-prints_ , page arXiv:1605.07723.
  * Trouillon et al. (2017) Theo Trouillon, Christopher R Dance, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. 2017.  Knowledge graph completion via complex tensor factorization.  _JMLR_.
  * Varma and Ré (2018) Paroma Varma and Christopher Ré. 2018.  Snuba: Automating weak supervision to label training data.  _Proc. VLDB Endow._ , 12(3):223–236.
  * Verga et al. (2018) P Verga, E Strubell, and A McCallum. 2018.  Simultaneously self-attending to all mentions for full-abstract biological relation extraction.  In _North American Chapter of the Association for Computational Linguistics (NAACL)_.
  * Xu et al. (2007) Feiyu Xu, Hans Uszkoreit, and Hong Li. 2007.  A seed-driven bottom-up machine learning framework for extracting relations of various complexity.  In _ACL_ , pages 584–591.


captionUnsupported document class

# Token Bucket-based Throughput Constraining in Cross-layer Schedulers

Jeremy Van den Eynde and Chris Blondia

###### Abstract

In this paper we consider upper and lower constraining users’ service rates in
a slotted, cross-layer scheduler context. Such schedulers often cannot
guarantee these bounds, despite the usefulness in adhering to Quality of
Service (QoS) requirements, aiding the admission control system or providing
different levels of service to users.

We approach this problem with a low-complexity algorithm that is easily
integrated in any utility function-based cross-layer scheduler. The algorithm
modifies the weights of the associated Network Utility Maximization problem,
rather than for example applying a token bucket to the scheduler’s output or
adding constraints in the physical layer.

We study the efficacy of the algorithm through simulations with various
schedulers from literature and mixes of traffic. The metrics we consider show
that we can bound the average service rate within about five slots, for most
schedulers. Schedulers whose weight is very volatile are more difficult to
constrain.

University of Antwerp - imec

IDLab - Department of Mathematics and Computer Science

Sint-Pietersvliet 7, 2000 Antwerp, Belgium

<EMAIL_ADDRESS>
Keywords: Cross-layer Scheduling, Quality of Service, Token Buckets, Resource
allocation

††footnotetext: Part of this research work was carried out at UAntwerpen, in
the frame of Research Project FWO nr. G.0912.13 ’Cross-layer optimization with
real-time adaptive dynamic spectrum management for fourth generation broadband
access networks’. The scientific responsibility is assumed by its authors.

##  1 Introduction

In shared communication networks users often have to compete for service. For
example, in wireless networks, the total available capacity is constantly
fluctuating due to interference, non-stationary objects etc. Hence, users have
to cooperate with each other to ensure the available capacity is shared
fairly.

Also in some wired network scenarios, such as DSL, there is competition
between users due to cross-talk [1]. This cross-talk occurs in the copper
cables when a user’s signal leaks into other users’ cables, thereby reducing
the rate region, the set of all users’ possible simultaneous data rates. This
rate region is considered convex, implying that increasing one user’s service
rate, will decrease other users’ rates.

In these two settings, the physical layer has many Pareto-optimal operating
points, which are all considered equally good to the physical layer. To the
upper layers they are, however, not all equally good: allocations that satisfy
the user’s QoS are preferable. For example, a live video feed has different
requirements than video on demand, with regard to delay and data rates.
Through cross-layering, the passing of information over the boundaries of the
traditional OSI model layers, the upper layers can steer the physical layer.
This cross-layering is often abstracted into a Network Utility Maximization
(NUM) problem, described by Equation 1.

$\mathbf{C^{*}}=\operatorname*{arg\,max}_{\mathbf{C}\in\mathcal{R}}\sum_{n=1}^{N}u{{}^{n}}(C^{n},\mathcal{S})$
(1)

Here $n$ is the user index, $N$ the number of users, and utility function
$u{{}^{n}}(\cdot)$ is an interface between the layers, representing the value
of a user receiving a service rate $C^{n}$. The state of the system
$\mathcal{S}$ can include any observable information, such as queue lengths,
arrivals, delays and others. We will omit $\mathcal{S}$ for readability when
it is clear from the context. In general $u{{}^{n}}(\cdot)$ is an increasing,
concave and differentiable function. Examples of cross-layer schedulers are
mentioned in subsection 1.2

Equation 1 chooses the operating point $\mathbf{C^{*}}$ from the rate region
(all possible combinations of service rates) such that average utility over
all users is maximized. In this system, a user $n$’s service rate depends on
the weight in relation to all other users. This implies that it is challenging
to control a single user’s service rate, since there is no correspondence
between one user’s isolated weight and its received rate. In spite of that,
sometimes we want to be able to constrain the short-term (and long-term)
average rates, for example to ensure the QoS of the users. We give more
reasons for implementing rate constraints in subsection 1.1

Most cross-layer schedulers, such as the ones listed in subsection 1.2 do not
offer the option to confine the service rate. Therefore, after reviewing the
system model in section 2 we describe our contribution, the Token Bucket Rate
Modifier (TBRM) algorithm, in section 3 It is a generic low-complexity
algorithm that constrains the short- and long-term average service rates of
all users in a utility function-based cross-layer scheduler. Each time slot
$t$, the NUM problem is solved, but each user’s weight is replaced by
$\phi{{}^{n}}\exp(\frac{k_{g}^{n}}{\sigma_{g}^{n}}+\frac{k_{M}^{n}}{\sigma_{M}^{n}})$.
Two counters, $k_{g}^{n}$ and $k_{M}^{n}$, track the deficiency and excess in
service, respectively. If a user $n$ has received less service than
$\rho_{g}^{n}$, the amount of tokens will accumulate, and the user’s weight
will increase, therefore raising the probability of receiving more data rate.
The parameters $\sigma_{g}^{n}$ and $\sigma_{M}^{n}$ are a measure for the
slowness to react to deficiency and excess respectively. The variable
$\phi{{}^{n}}$ accounts for non-positive weights. The algorithm is very easy
to incorporate into any scheduler, as it does not require manipulating the
original scheduler’s weight function.

In section 4 we evaluate our algorithm through multiple simulations. We
compare our results with the unbounded scenarios, and look at the influence of
the slot size $\tau$ and parameter $\sigma$. The metrics indicate that we can
bound the average service rate for all users within a limited amount of time.
Schedulers whose weight fluctuate heavily are more difficult to constrain.

We close the paper with related works in section 5 and a conclusion in section
6.

###  1.1 Motivation for service rate constraints

In a multi-user environment, it is useful to ensure that flows are guaranteed
a bound on the average service rate. A provider might offer different QoS
guarantees to different users, depending on the subscribed model. This might
include a guaranteed and/or maximal rate.

There are other reasons to ensure a minimal rate. For example applications
like audio and video need a minimal rate for a satisfying Quality of
Experience (QoE). Additionally, the authors of [2] observe that TCP-based
applications can lead to large queues when the throughput is too small.
Finally, a guaranteed rate ensures that misbehaving competing flows, cannot
smother flows from receiving their fair share.

Applying an upper bound on a user’s capacity is also useful. For example, to
accommodate a new flow into a network, admission control algorithms often
require an upper bound on the data rates [3]. If a flow disrespects this rate,
other applications in the network can suffer deteriorated QoS. By limiting the
maximal data rate, a misbehaving flow is isolated and cannot negatively impact
the other applications, but will only punish itself. In addition, it can also
be useful to provide different service levels to users, where an operator may
choose to cap the data rate for cheap data services, and remove this limit for
the more expensive premium services.

Although rate constraints can be implemented into the physical layer, it might
be interesting to handle it at higher layers. First, it reduces the degrees of
cross-layer freedom, and limits the communication necessary. Second, this
allows a more flexible approach, allowing for temporary violations. Finally,
it might not always be possible to introduce the rate constraints into the
physical layer. For example, the scheduler is implemented in hardware or
closed-source and cannot be modified, or the corresponding NUM problem’s
complexity might increase too much due to the additional constraints.

Imposing upper bound constraints can be easily accomplished using a token
bucket counter on a user’s output stream. This is wasteful though: as the
medium is shared, increasing one user’s service rate means decreasing other
users rates. By applying a token bucket, the excess capacity is thrown away as
it is reserved by a particular user.

###  1.2 Cross-layer schedulers

There are many existing cross-layer schedulers, each employing different
metrics. We list here schedulers that are used in the simulations in section 4

Most schedulers found in literature are linear, meaning that the utility is of
the form $u(C^{n})=\omega{{}^{n}}C^{n}$. For example, the Max-Weight (MW)
scheduler, presented in the seminal work [4], has $\omega{{}^{n}}=Q{{}^{n}}$.

The Modified Largest Weighted Delay First (M-LWDF) [5] uses
$\omega{{}^{n}}=\alpha^{n}\Gamma{{}^{n}}\frac{1}{\bar{C}^{n}}$, where
$\alpha^{n}=\frac{-\log(\varepsilon)}{\hat{T}{{}^{n}}}$, $\varepsilon$ is
maximal delay violation probability, $\hat{T}$ the delay upper bound,
$\Gamma{{}^{n}}$ is the Head-of-line delay and $\bar{C}^{n}$ the exponentially
averaged assigned data rates.

The Exponential/PF (EXP/PF) [6] scheduler, is a combination of Proportionally
Fair scheduler and an exponent. It calculates the weights for real-time flows
as
$\exp(\frac{\alpha^{n}\Gamma{{}^{n}}-\chi}{1+\sqrt{\chi}})\frac{1}{\bar{C}^{n}}$,
where $\chi=\frac{1}{N}\sum_{n=1}^{N}\alpha^{n}\Gamma^{n}$.

The Maximal Delay Utility (MDU) scheduler [7] employs the average waiting
time: $\omega{{}^{n}}=\frac{|u^{\prime n}(\bar{U}^{n})|}{\bar{\lambda}^{n}}$,
where $u^{\prime n}$ is the derivative of the traffic class’ utility function,
$\bar{U}^{n}$ the average waiting time and $\bar{\lambda}^{n}$ the average
arrival rate.

The MD scheduler is the non-linear equivalent of the MW scheduler, as it uses
the utility function $u(C^{n})={Q{{}^{n}}}/{C^{n}}$. Finally, the Minimal
Delay Violation (MDV) scheduler [8] is a non-linear scheduler of the form
$u(C^{n})=-\frac{\omega{{}^{n}}}{C^{n}}$, where the weight $\omega{{}^{n}}$
tries to minimize the amount of delay violations by looking at the queue and
past delays.

##  2 System model

Time in our model is divided into slots of $\tau$ seconds. There are $N$
users, indexed by $n\in\left[1,N\right]$, each of which can send $\tau\cdot
C^{n}(t)$ bits during slot $t\in\mathbb{N}$, where $0\leq
C^{n}(t)\leq\hat{C}{{}^{n}}$ is the capacity for user $n$.

The user’s arrivals and departures during slot $t$ are denoted by $A^{n}(t)$
and $D^{n}(t)$ respectively while the queue at the start of slot $t$ is
indicated by $Q^{n}(t)$. The capacities $\overline{\bm{C}}(t)$ are determined
by a scheduler, based on weights $\overline{\bm{\omega}}(t)$: at the start of
slot $t$, a request is made to the scheduler, the reply of which is applied at
the start of slot $t+1$. There is thus a delay of $\tau$ seconds between a
request and application of the rates. The scheduler takes the best matching
rate from the rate region $\mathcal{R}\subset\mathbb{R}^{N}_{+}$.

Each of the $N$ users has one traffic stream with delay upper bound
$\hat{T}^{n}$, with the additional constraint that flow $n$’s average service
rate is bounded: $0\leq\rho_{g}^{n}\leq
C^{n}\leq\rho_{M}^{n}\leq\hat{C}{{}^{n}}$.

##  3 The Token Bucket Rate Modifier algorithm

###  3.1 Token buckets

Token buckets are found in various situations, such as describing traffic
flows [9, 10, 11], to check conformance of incoming or outgoing traffic
(policing and shaping [12]), traffic marking in DiffServ [13, 14] and rate
estimation [15].

Conceptually, a token bucket $TB(\rho,\sigma)$ consists of a bucket holding
$k$ tokens (e.g. bits). Tokens are added at a constant rate $\rho$ to the
bucket, which is capped at $\sigma$ tokens. Whenever a packet of $B$ bit
passes and there are sufficient tokens, $B$ tokens are removed from the bucket
and the packet continues its journey. If $k<B$, the packet is considered non-
conforming and an appropriate action is taken, such as being color-marked non-
conforming, queued (shaping) or dropped (policing). Such a token bucket will
limit the long-term average outgoing rate to $\rho$. On a short-term scale,
bursts of up to $\sigma$ bits can be served.

###  3.2 Algorithm

In the following algorithm, this token bucket principle is used to lower and
upper bound the service rate in a cross-layer scheduler setting. But, in
contrast to a regular token bucket, we now do not cap the tokens to $\sigma$.
Rather, they are used to indicate the severity of the excess.

In the algorithm, instead of solving

$\operatorname*{arg\,max}_{\mathbf{C}\in\mathcal{R}}\sum_{n}f(C^{n})\omega{{}^{n}}$
(2)

where $f(C)=C$ for the linear, and $f(C)=C^{-1}$ for the reciprocal variant,
the NUM problem is modified to

$\operatorname*{arg\,max}_{\mathbf{C}\in\mathcal{R}}\sum_{n}f(C^{n})\phi{{}^{n}}\exp(\frac{k_{g}^{n}}{\sigma_{g}^{n}}+\frac{k_{M}^{n}}{\sigma_{M}^{n}})$
(3)

Here, $k_{g}^{n}\in\left[0,\infty\right[$ and
$k_{M}^{n}\in\left]\text{-}\infty,0\right]$ are the tokens for the guaranteed
and maximal token buckets, respectively. Every slot, the tokens are updated
according to the following rules:

$k_{g}^{n}(t+1)=\max\\{0,k_{g}^{n}(t)+(\rho_{g}^{n}-C^{n}(t))\tau\\}$ (4)
$k_{M}^{n}(t+1)=\min\\{0,k_{M}^{n}(t)+(\rho_{M}^{n}-C^{n}(t))\tau\\}$ (5)

When the received capacity for a user $n$ in the past slots is less than the
guaranteed rate $\rho_{g}^{n}$, the virtual token counter $k_{g}^{n}$ will
continue to increase as long as there is a deficit in received service, and
hence the weight will exponentially increase. Likewise, if a user $n$ has
received more than $\rho_{M}^{n}$ service, the virtual token counter
$k_{M}^{n}$ will have a negative drift, as long as more data rate is assigned
to the user. This will reduce the user’s weight exponentially. When the
service rate is less than $\rho_{M}^{n}$, the token counter will return to 0.

We introduce

$\phi{{}^{n}}=\begin{cases}\bar{\omega},&\text{if}\
\omega{{}^{n}}\leq\epsilon\ \text{and}\
\frac{k_{g}^{n}}{\sigma_{g}^{n}}+\frac{k_{M}^{n}}{\sigma_{M}^{n}}\neq 0\\\
\omega{{}^{n}},&\text{else}\end{cases}$ (6)

to account for non-positive weights $\omega{{}^{n}}$. Here $\bar{\omega}$ is
the exponentially averaged sum of all the positive weights, and $\epsilon$ a
small number that will result in a capacity close to zero (for the simulations
we used $\epsilon=\max_{n}\\{\omega{{}^{n}}\\}\cdot 10^{-5}$). If
$\omega{{}^{n}}\in\left]0,\epsilon\right]$ it becomes difficult to increase
the bandwidth reliably, and in the case of $\omega{{}^{n}}=0$, it is even
impossible, since the weight will remain zero. For a negative weight, which
can occur for example for best effort flows in the EXP/PF scheduler, the
additional factor would just result in an even lower weight, and would also
inhibit us from receiving service. $\bar{\omega}$ is used to approximate a
valid weight that is reasonably stable. This weight is scheduler and traffic
dependent, and thus must be calculated at run time.

Note that if $\rho_{g}^{n}=0$ or $\rho_{M}^{n}\geq\hat{C}{{}^{n}}$, then
respectively the first and second exponent will always be 1, and the
respective bound is disabled.

It can be seen that if a flow stays within the bounds, then the tokens
$k_{g}^{n}$ and $k_{M}^{n}$ will remain zero, and
$\phi{{}^{n}}=\omega{{}^{n}}$, resulting in the unmodified weight. Only if
some rate guarantee will not be met, weights will be adapted.

###  3.3 Discussion

##### Parameters $\rho_{g}^{n}$ and $\rho_{M}^{n}$

The choice of $\rho_{g}$ and $\rho_{M}$ influences the speed at which the rate
can adapt. For example, if the guaranteed rate
$\rho_{g}^{n}=0.75\hat{C}{{}^{n}}$, then in each slot the tokens can increase
by at most $0.75\hat{C}{{}^{n}}$, and the negative drift is at most
$0.25\hat{C}{{}^{n}}$. Thus, if this flow has been receiving no service, then
the tokens - and thus the weight too - will increase quickly. If it is
receiving service at a rate $\hat{C}{{}^{n}}$, then the tokens will decrease
more slowly. A small $\rho_{g}^{n}$ thus also implies a small positive and
large negative drift. A similar reasoning can be applied to the maximal rate
$\rho_{M}^{n}$.

##### Parameters $\sigma_{g}^{n}$ and $\sigma_{M}^{n}$

In the traditional token bucket algorithms, $\sigma$ is a measure for the
burstiness of a flow. For example, large values of $\sigma$ mean that large
bursts are allowed. In our algorithm, the $\sigma$ can be interpreted as a
measure for slowness to react. A large value of $\sigma_{M}^{n}$ means that
longer periods of above-guaranteed service rates are possible, because our
weight will decrease more slowly. Small values of $\sigma_{M}^{n}$ will react
quicker and can lead to an overreaction. The two token buckets can also
influence each other: in case of an overreaction, the other token bucket will
also have a sudden excess, and in turn have a fiercer reaction. This can be
observed for small values of $\sigma$ in the simulations of subsubsection
4.5.2

##### Slot size

In our system, the slot size implies a delay between a request for and
subsequent assignment of the capacity. A larger slot size means that changes
will be slower, and that predicting future traffic becomes more important.
This also matters to the rate constraint algorithm, since the scheduler’s
response to weights becomes more unpredictable, hence modifying the weights.
The simulations of subsubsection 4.5.3 briefly look at increasing slot sizes.

##### exp

The function $\exp$ is chosen here to modify the token fractions, but any
continuous, strictly increasing function $\alpha(\cdot)$ for which holds that
$\alpha(0)=1$, $\lim\limits_{x\rightarrow{-\infty}}\alpha(x)=0$ and
$\lim\limits_{x\rightarrow\infty}\alpha(x)=\infty$ will give rate guarantees,
albeit with different bounds. Tests with different functions resulted in more
short-time erratic behavior.

##### Additive form

Instead of using a product, it is also possible to use an additive form,

$\operatorname*{arg\,max}_{\mathbf{C}\in\mathcal{R}}\sum_{n}f(C^{n})\omega{{}^{n}}+(\alpha(\frac{k_{g}^{n}}{\sigma_{g}^{n}})+\alpha(\frac{k_{M}^{n}}{\sigma_{M}^{n}}))\beta$

Here $\alpha$ is a continuous, strictly increasing function with the
properties $\alpha(0)=0$,
$\lim\limits_{x\rightarrow{-\infty}}\alpha(x)=-\infty$ and
$\lim\limits_{x\rightarrow{\infty}}\alpha(x)=\infty$. An additional factor
$\beta$ must be introduced to account for the fact that $\omega{{}^{n}}$ is
usually not unitless.

We ran some simulations for $\alpha(x)=x$ and $\alpha(x)=x^{3}$, and
$\beta=\bar{\omega}$. The simulations showed that this approach is also
possible, and avoids the non-positive weight problem which forced us to
introduce the factor $\phi{{}^{n}}$. However, in the NUM problem, what matters
is the relative weights, rather than the absolute difference, which the
additive form expresses. Even though on larger timescales this leads to nicely
averaged data rates, on short timescales the behavior is very extreme, where
$C^{n}(t)$ alternates between $0$ and rates close to $\hat{C}{{}^{n}}$ in
successive slots.

##### Complexity

The space and time complexity of the TBRM algorithm is very low. Every slot we
update the $N$ users’ token counters $k_{g}^{n}$ and $k_{M}^{n}$ (Equations
(4) and (5)). Additionally, we have to select a suitable $\phi{{}^{n}}$ for
all $n$. The exponentially weighted $\bar{\omega}$ is a constant time
operation $\mathcal{O}(()1)$. The resulting time complexity is thus
$\mathcal{O}(()3N+1)=\mathcal{O}(()N)$.
Likewise, the space requirements are equally low: we track the $2N$ counters,
and a single exponentially weighted $\bar{\omega}$. The space complexity is in
this case $\mathcal{O}(()2N+1)=\mathcal{O}(()N)$.

##### Other considerations

Applying rate guarantees transforms a work-conserving scheduler into a non-
work conserving scheduler. I.e. the scheduler might have capacity assigned,
even though there are no jobs available.

Additionally, throughput constraints reduces the stability region of a
scheduler. Roughly, a scheduler is called stable for an arrival process if all
the queues remain bounded. The set of arrival rates for which a scheduler is
stable, is called the stability region. Schedulers such as MW [4] and MDU [7]
have been proven to be stable for the widest range of arrivals.
Applying a constraint on the data rate for such schedulers reduces its
stability region. Enforcing a maximal data rate inside the stability region,
clearly decreases this region. Also supporting a minimal throughput constraint
influences the stability region: a minimal throughput constraint can be
rewritten as a (more complex) maximal throughput constraint on the other
users.

##  4 Simulations

###  4.1 Simulation setup

We evaluated the TBRM algorithm using simulations for the schedulers listed in
subsection 1.2 We ran simulations in OMNeT++ using the INET framework. Every
$\tau=50\text{ms}$ the original weights and weight modifiers were computed.
The resulting NUM problem was then solved with the help of the nlopt [16]
library, by first applying the local variant of the DIviding RECTangles
algorithm [17], followed by the COBYLA algorithm[18], to obtain the final
rate, applying them in the next slot.

###  4.2 Rate region

The rate region was artificially generated by the following formula, which is
based on the n-sphere formula.

$\displaystyle r^{n}$
$\displaystyle=\hat{C}{{}^{n}}\prod_{i=1}^{n-1}\sin(\phi^{i})^{1-\gamma}\cos(\phi^{n})^{1-\gamma},r\in\left[1,N-1\right]$
$\displaystyle r^{N}$
$\displaystyle=C^{N}_{max}\prod_{i=1}^{N-1}\sin(\phi^{i})^{1-\gamma}$

For $N$ users, the rate region is the set of points generated by varying
$\phi^{i}\in\left[0,\frac{\pi}{2}\right],\forall i\in\left[1,N-1\right]$. The
modifier $\gamma\in\left[-1,1\right]$ changes the shape of the rate region. If
we set $\hat{C}{{}^{n}}=M,\forall n$, then the shape ranges from an n-simplex
for $\gamma=-1$, over an n-sphere with radius $M$ for $\gamma=0$, to a
hypercube for $\gamma=1$.

###  4.3 Scenarios

The scenarios listed in Table 1 show the different types of traffic and the
applied constraints.

Scenario |  User 1 |  User 2 |  User 3 |  User 4 |  User 5
---|---|---|---|---|---
1 |  SAT [150,250] |  SAT [250,350] |  SAT [350,400] |  SAT [150,350] |  SAT [50,100]
2 |  Starwars [50,150] |  Alice [250,350] |  Self-Similar [150,350] |  SAT [150,350] |  Sine2VS [50,120]
3 |  Starwars [50,150] |  Sine2F [250,350] |  Self-Similar [150,350] |  SAT [150,350] |  Sine2VS [50,120]
4 |  Sine2VS [150,250] |  Sine2VS [150,250] |  Sine2VS [250,300] |  Sine2VS [150,350] |  Sine2VS [50,400]
5 |  Sine2VS [150,250] |  Sine2VS [150,250] |  Sine2VS [250,300] |  Sine2VS [150,350] |  Self-Similar [0,0]
Table 1: Summary of scenarios. Listed for each user are traffic type, and
[$\rho_{g}$, $\rho_{M}$] in Mbps.

The traffic types behave differently on short and large timescales. The first
type of traffic consists of a sine-wave, superimposed with a faster
oscillating sine-wave. Some flows will oscillate slowly (Sine2VS) while others
oscillate fast (Sine2F). The second type of traffic is the heavy tail traffic,
which is either a trace file of a video file, such as Starwars, or a self-
similar flow, generated by a superposition of Pareto-distributed sources [19].
The last class of traffic, SAT, tries to send as much traffic as possible, by
ensuring the queue is always backlogged.

These scenarios are run for $\tau=0.05s$ in subsubsection 4.5.1 In
subsubsection 4.5.2 we vary $\sigma$, and in subsubsection 4.5.3 it is $\tau$
that changes.

###  4.4 Metrics

We examined three different metrics. The m2 and m3 metrics are defined on
windows of size $G$, which groups $G$ consecutive slots.

  1. m1

the percentage of slots that would be marked non-conforming by a token bucket
process $TB(\rho_{g},{\rho_{g}\tau x})$ and $TB(\rho_{M},{\rho_{M}\tau x})$
for respectively the guaranteed and maximal rate. $x\in\mathbb{R}^{+}$ is a
variable indicating the allowed burstiness. Increasing $x$ allows for more
burstiness, and will result in a smaller percentage of non-conforming slots.

  2. m2

The average amount of excess bits per window $G$. If we define the amount of
bit reserved in window $w$ as $C^{G}(w)=\sum_{t=wG}^{(w+1)G}C(t)\tau$, and $W$
as the total number of windows, then the m2 metric for respectively the
guaranteed and maximal rate can be formally described as
$\langle\\{\max\\{\rho_{g}G\tau-C^{G}(w),0\\}|w=0..W-1\\}\rangle$ and
$\langle\\{\max\\{C^{G}(w)-\rho_{M}G\tau,0\\}|w=0..W-1\\}\rangle$. This is a
representation of the severity of the average violation. A larger number
indicates more severe violations. The metric can be visualized by imagining
the surface above or below the required rate. Increasing $G$ decreases the m2
metric as we smooth out excess bits over a larger window.

  3. m3

$\langle B^{G}\rangle$: where $B^{G}$ is the set of consecutive violating
windows. This metric gives an idea of how grouped violations are. For example,
if this number is large, it means that a violation is resolved slowly.

###  4.5 Results

####  4.5.1 Regular scenarios

In the following plots, we averaged over all schedulers and scenarios, as
showing the individual schedulers would result in a cluttered plot. Important
discrepancies between schedulers will be discussed in the text.

Each plot has two curves, one of which displays the results for which no rate
constraints were applied, as a base case, and the other has our TBRM algorithm
applied.

##### m1

The m1 metric is shown in Figure 1, which displays on the x-axis the allowed
burstiness, and on the y-axis the percentage of non-conforming slots.

NormalWith TBRM

(a) m1: upper bound on rate

(b) m1: lower bound on rate

Figure 1: m1 for the regular scenarios

If we examine 1(a), which shows the m1 metric for the upper bound, then we can
see that for $x=1$, the number of violations is close to the results of the
unconstrained simulations. Increasing $x$, the allowed burstiness, however, we
can observe that the violation probability quickly drops for our TBRM
algorithm, and becomes almost 0 when the allowed burst size is
$5\rho_{M}\tau$. This indicates that the violations occur irregularly spread.
The unconstrained results remain fixed around 6% for a long time.

The underlying data shows that for the constrained scenarios all the
schedulers inhibit the same behavior: there is a steep decline in violations,
going from $x=1$ to $x=2$, and then they gradually go to almost 0 for $x=5$.

This behavior is the same for all schedulers over all traffic classes.
However, the initial violation probability for SAT class is slightly lower
than the video, self-similar and sine classes. The SAT traffic is easier to
correct due to its queue based nature.

In the m1 plot of the guaranteed rate in 1(b), our domain is limited to
$\left]0,1\right]$: if $x=1$, then it means that approximately in every slot
we allow a deficit of $\rho_{g}\tau$ bit, which is obviously the maximum
deficit we can attain per slot. In the plot, one can see that there is a much
wider gap between the constrained and unconstrained scenarios, confirming the
efficacy of our algorithm.

The data shows here that the majority of the violations come from the MW and
M-LWDF schedulers, and more specifically for the video streams. For example,
in the TBRM scenarios, for $x=0.1$, both schedulers have a violation
probability of about 20%, while the other schedulers are closer to 6%.

This difference can be explained by the fact that in those linear schedulers
the queue length is used as a weight. This number is immediate, which causes a
more unpredictable weight (especially in combination with a linear scheduler),
making it more difficult to estimate a suitable weight modifier. Additionally,
the weight can become 0 very easily. This requires the use of the additional
$\phi{{}^{n}}$ modifier. Even though $\bar{\omega}$ is smoother, the switch
between $\bar{\omega}$ and $\omega{{}^{n}}$ can also be disruptive. However,
this extra factor is necessary, as simulations without this correction
$\phi{{}^{n}}$, result in a much higher violation probability.

The curve looks quite linear. This can be explained by the fact that the
guaranteed rate violations are more evenly spread out.

##### m2

Ideally, we can limit the rate immediately. However, there is an inherent
delay of 1 slot, and an elasticity in the form of a burst factor. Therefore,
we study the rate, when we group $\frac{G}{\tau}$ slots into windows of size
$G$.

The m2 metric in Figure 2, displays the average amount of violated bits per
window, for increasing window sizes $G$.

NormalWith TBRM

(a) m2: upper bound on rate

(b) m2: lower bound on rate

Figure 2: m2 for the regular scenarios

It can be observed that for a window size of $G=0.05\text{s}$, for the
unconstrained scenarios there is an average of 30Mbit/window in excess of the
target rate. When we constrain it using our algorithm, this drops to about
10Mbit/window.

Increasing the window size $G$, averages out bursts. Like the results for m1,
there is a steep decline until $G=0.25\text{s}$, which coincides with 5 slots,
after which the bit violations remains stable in the upper bound case. Though
less pronounced, also here do the MW, M-LWDF and MD schedulers fare the worst
for small window sizes, mainly for the Self-Similar traffic.

The decline implies that bursts are usually short-lived: overflow and good
windows are usually close together, as they don’t violate the constraints when
merged. This is also confirmed in the m3 metric, below. The rate of decline is
similar for the scenarios with and without TBRM applied.

##### m3

The last metric discusses the average length of a violation streak. Figure 3
shows the average number of successive windows that violate their constraints
in a log-plot. The m3 metric, like the m2 metric, initially decreases quickly
as the window size increases, and then slowly decreases. It can be clearly
seen that, regardless of the unconstrained behavior, the TBRM algorithm limits
the bursts to 5 windows, for $G=\tau$, dropping to 2 windows for $G=5\tau$.
These short bursts confirm that the algorithm is able to fix excesses within
about 5 slots.

NormalWith TBRM

(a) m3: upper bound on rate

(b) m3: lower bound on rate

Figure 3: m3 for the regular scenarios

The main contributor to the average in this metric is the MDU scheduler. The
data show that this is because whereas other schedulers consist of many
smaller busy periods, the MDU scheduler has only one or two large busy
periods, increasing the average significantly.

Without the MDU data, the average for 5 windows is about 1, for the minimal
rate constraint, and 2 for the maximal rate constraint.

####  4.5.2 Study of parameter $\sigma$

In this section we look at the results of varying burst parameter $\sigma$. We
let $\sigma_{g}=i\tau\rho_{g}$ and $\sigma_{M}=i\tau\rho_{M}$, for
$i\in\left[10^{-2},10^{4}\right]$, and look at the effect on the m1 metric in
Figure 4, which shows the results for the individual schedulers.

MWMLWDFEXPPFMDUMDMDV

(a) m1: upper bound on rate

(b) m1: lower bound on rate

Figure 4: m1 for the $\sigma$ scenarios

The plot shows that for the upper bound constraints, the violation probability
is always very low (about 4% at most for $i=10^{4}$). The lower bound,
however, starts around 50% violation probability, and suddenly drops to
smaller probabilities for $i=10^{2}$.

Indeed, a small $\sigma_{M}$ will overflow quickly, which causes its weight to
be reduced swiftly, hence there will be less violations. As $\sigma_{M}$
grows, the weight modifier will decrease much more slowly, leaving more room
for violations. For the guaranteed rate, on the other hand, $k_{g}$ cannot
build up a deficit as fast as $k_{M}$, as discussed before. It is only when
the growths of the deficits are balanced that the m1 metric can lower, which
is around $i=10^{2}$ and upwards.

The schedulers that perform the worst are, unsurprisingly, the MW and M-LWDF
schedulers.

MWMLWDFEXPPFMDUMDMDV

(a) m1: upper bound on rate

(b) m1: lower bound on rate

Figure 5: m1 for the $\tau$ scenarios ($\sigma=5\tau\rho$)

####  4.5.3 Study of parameter $\tau$

In the previous simulations, we assumed a slot length of $\tau=0.05s$. This
study observes how the TBRM algorithm changes in function of $\tau$.

In Figure 5 the m1 metric for $\sigma=5\tau\rho$ is plotted. It can be
observed that mainly the lower bound in 5(b) is sensitive to an increasing
slot length. This might be because with an increasing $\tau$ also grows the
probability of a larger delay: if in a slot a low capacity was assigned
erroneously, the delays or queues will increase and additionally it takes
longer to correct, causing larger queues. Especially the EXP/PF scheduler
suffers from this, as it is of the form $\exp(\Gamma)$, where $\Gamma$ is the
Head-of-line. As the non-linear Min-Delay (MD) and MDV schedulers try to
minimize the delay, they suffer less from an increase of slot size.

For the upper bound in 5(a) only the MDU and EXP/PF schedulers seem to suffer
from the increased slot size. This is probably due to the fact that it is
easier to receive a service lower than $\rho_{M}$.

##  5 Related work

In [5, 20] the authors use virtual tokens as a measure for the average waiting
time, and incorporate it with the M-LWDF[5] and EXP/PF[6] scheduling algorithm
to warrant a minimal rate. It is, however, not transferable to other
schedulers. In other schedulers, the guaranteed rate constraint is built into
the scheduler itself [21, 22], but they are all scheduler-specific and don’t
allow enforcing a maximal data rate. The authors of [23] consider utility
based throughput allocation subject to certain properties, but is only valid
for linear utility functions. In [24] a related problem of maintaining an
optimal service rate is proposed. In [25], the authors consider a generic
algorithm with minimum and maximum rate constraints. It is, however, only
applicable to schedulers that operate in function of an average rate. As such,
it excludes for example the MW[4], MD and M-LWDF schedulers. Other schedulers,
such as, MDU[7] and MDV[8] have a more elaborate utility function and are more
difficult to characterize. The authors of [26] also employ a token system, but
assume that users lie about their demands to strategically maximize their
utility. In [27] constraints are applied to network slices of traffic
aggregates in a 5G context, using an additive approach.

##  6 Conclusion

In this paper we looked at restricting the service rates given to users in a
cross-layer scheduler setting. We implemented this using a low-complexity
algorithm that modifies the weights in a Network Utility Maximization problem,
using the concept of token buckets. We first discussed cross-layer scheduling,
and the need to both upper and lower limit data rates assigned to users. Then
we proposed the TBRM algorithm, and followed up with simulation results. We
ran simulations for six different schedulers, and multiple scenarios
demonstrating that using our approach it is possible to limit the service
rate, within error, after about five slots for the maximal and guaranteed
service rate for most schedulers. Schedulers that progress smoothly are easier
to constrain than schedulers that can behave wildly, such as EXP/PF for long
slot times, MW or M-LWDF. These are more difficult to restraint with respect
to guaranteeing a lower bound on the service rate.

## References

  * [1] J. Verdyck, C. Blondia, and M. Moonen, “Network utility maximization for adaptive resource allocation in dsl systems,” in 2018 26th European Signal Processing Conference (EUSIPCO), pp. 787–791, IEEE, 2018.
  * [2] R. Chakravorty, S. Katti, J. Crowcroft, and I. Pratt, “Flow aggregation for enhanced tcp over wide-area wireless,” in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, vol. 3, pp. 1754–1764, IEEE, 2003.
  * [3] J. Qiu and E. W. Knightly, “Measurement-based admission control with aggregate traffic envelopes,” IEEE/ACM Transactions on Networking (TON), vol. 9, no. 2, pp. 199–210, 2001.
  * [4] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE transactions on automatic control, vol. 37, no. 12, pp. 1936–1948, 1992.
  * [5] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, “Providing quality of service over a shared wireless link,” IEEE Communications magazine, vol. 39, no. 2, pp. 150–154, 2001.
  * [6] R. Basukala, H. M. Ramli, and K. Sandrasegaran, “Performance analysis of exp/pf and m-lwdf in downlink 3gpp lte system,” in Internet, 2009. AH-ICI 2009. First Asian Himalayas International Conference on, pp. 1–5, IEEE, 2009.
  * [7] G. Song, Cross-layer resource allocation and scheduling in wireless multicarrier networks.  PhD thesis, Citeseer, 2005.
  * [8] J. Van den Eynde, J. Verdyck, M. Moonen, and C. Blondia, “A delay-based cross-layer scheduler for adaptive dsl,” in Communications (ICC), 2017 IEEE International Conference on, pp. 1–6, IEEE, 2017.
  * [9] P. P. Tang and T.-Y. Tai, “Network traffic characterization using token bucket model,” in INFOCOM’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 1, pp. 51–62, IEEE, 1999.
  * [10] R. L. Cruz, “A calculus for network delay. i. network elements in isolation,” Information Theory, IEEE Transactions on, vol. 37, no. 1, pp. 114–131, 1991\.
  * [11] J.-Y. Le Boudec and P. Thiran, Network calculus: a theory of deterministic queuing systems for the internet, vol. 2050.  Springer Science & Business Media, 2001.
  * [12] D. Stiliadis and A. Varma, “Latency-rate servers: a general model for analysis of traffic scheduling algorithms,” IEEE/ACM Transactions on Networking (ToN), vol. 6, no. 5, pp. 611–624, 1998.
  * [13] J. Heinanen and R. Guerin, “Rfc 2697–a single rate three color marker,” IETF, September, 1999.
  * [14] J. Heinanen and R. Guerin, “Ietf rfc 2698.“,” A Single Rate Three Colour Marker, 1999.
  * [15] E. Zhang and L. Xu, “Capacity and token rate estimation for networks with token bucket shapers,” Computer Networks, vol. 88, pp. 1–11, 2015.
  * [16] Steven G. Johnson, “The nlopt nonlinear-optimization package.”
  * [17] J. M. Gablonsky and C. T. Kelley, “A locally-biased form of the direct algorithm,” Journal of Global Optimization, vol. 21, no. 1, pp. 27–37, 2001.
  * [18] M. J. Powell, “A direct search optimization method that models the objective and constraint functions by linear interpolation,” in Advances in optimization and numerical analysis, pp. 51–67, Springer, 1994.
  * [19] X. Bai and A. Shami, “Modeling self-similar traffic for network simulation,” arXiv preprint arXiv:1308.3842, 2013.
  * [20] S. Shakkottai and A. L. Stolyar, “Scheduling algorithms for a mixture of real-time and non-real-time data in hdr,” in Teletraffic Science and Engineering, vol. 4, pp. 793–804, Elsevier, 2001.
  * [21] M. Mohseni, R. Zhang, and J. M. Cioffi, “Optimized transmission for fading multiple-access and broadcast channels with multiple antennas,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1627–1639, 2006\.
  * [22] X. Wang and N. Gao, “Stochastic resource allocation over fading multiple access and broadcast channels,” IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2382–2391, 2010.
  * [23] X. Liu, E. K. Chong, and N. B. Shroff, “A framework for opportunistic scheduling in wireless networks,” Computer networks, vol. 41, no. 4, pp. 451–474, 2003.
  * [24] S. Borst and P. Whiting, “Dynamic channel-sensitive scheduling algorithms for wireless data throughput optimization,” IEEE Transactions on Vehicular Technology, vol. 52, no. 3, pp. 569–586, 2003.
  * [25] M. Andrews, L. Qian, and A. Stolyar, “Optimal utility based multi-user throughput allocation subject to throughput constraints,” in INFOCOM 2005\. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol. 4, p. 2415—2424, IEEE, 2005.
  * [26] S. M. Zahedi, S. Fan, and B. C. Lee, “Managing heterogeneous datacenters with tokens,” ACM Transactions on Architecture and Code Optimization, vol. 15, no. 2, p. 18, 2018.
  * [27] S. Mandelli, M. Andrews, S. C. Borst, and S. Klein, “Satisfying network slicing constraints via 5g mac scheduling,” IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, pp. 2332–2340, 2019.

  *[QoS]: Quality of Service
  *[DSL]: Digital Subscriber Line
  *[NUM]: Network Utility Maximization
  *[TBRM]: Token Bucket Rate Modifier
  *[QoE]: Quality of Experience
  *[MW]: Max-Weight
  *[M-LWDF]: Modified Largest Weighted Delay First
  *[EXP/PF]: Exponential/PF
  *[MDU]: Maximal Delay Utility
  *[MDV]: Minimal Delay Violation
  *[MD]: Min-Delay