# Logical Reasoning for Task Oriented Dialogue Systems

Sajjad Beygi
<EMAIL_ADDRESS>Maryam Fazel-Zarandi
<EMAIL_ADDRESS>Alessandra Cervone
<EMAIL_ADDRESS>Prakash Krishnan
<EMAIL_ADDRESS>Siddhartha Reddy Jonnalagadda
<EMAIL_ADDRESS>
###### Abstract

In recent years, large pretrained models have been used in dialogue systems to
improve successful task completion rates. However, lack of reasoning
capabilities of dialogue platforms make it difficult to provide relevant and
fluent responses, unless the designers of a conversational experience spend a
considerable amount of time implementing these capabilities in external rule
based modules. In this work, we propose a novel method to fine-tune pretrained
transformer models such as Roberta and T5. to reason over a set of facts in a
given dialogue context. Our method includes a synthetic data generation
mechanism which helps the model learn logical relations, such as comparison
between list of numerical values, inverse relations (and negation), inclusion
and exclusion for categorical attributes, and application of a combination of
attributes over both numerical and categorical values, and spoken form for
numerical values, without need for additional training dataset. We show that
the transformer based model can perform logical reasoning to answer questions
when the dialogue context contains all the required information, otherwise it
is able to extract appropriate constraints to pass to downstream components
(e.g. a knowledge base) when partial information is available. We observe that
transformer based models such as UnifiedQA-T5 can be fine-tuned to perform
logical reasoning (such as numerical and categorical attributes’ comparison)
over attributes that been seen in training time (e.g., accuracy of 90%+ for
comparison of smaller than $k_{\max}$=5 values over heldout test dataset).

Logical Reasoning for Task Oriented Dialogue Systems

Sajjad Beygi<EMAIL_ADDRESS>Maryam Fazel-Zarandi<EMAIL_ADDRESS>

Alessandra Cervone<EMAIL_ADDRESS>Prakash Krishnan<EMAIL_ADDRESS>Siddhartha Reddy Jonnalagadda<EMAIL_ADDRESS>

##  1 Introduction

Figure 1: The dialogue system with reasoning ability.

Logical reasoning is an important aspect of human thinking and communication.
Humans reason over beliefs, preferences, time, facts, and other contextual
information to achieve complex tasks, derive meaning, and analyze emotions.
Current task-oriented dialogue systems, however, only support very limited
forms of logical reasoning. More specifically, although reasoning ability has
been investigated as part of chatbots Cui et al. (2020) and question-answering
systems Huang et al. (2019); Chen et al. (2020), in many task-oriented
dialogue systems today, the reasoning is mainly focused on determining which
slot values are still unknown to the system but are required and elicit them
Guo et al. (2017). However, in realistic task-oriented dialogues, logical
reasoning is required to understand the user’s request, ask questions that
help address the user’s task successfully and minimize asking irrelevant
questions. The lack of robust, generalizable reasoning capabilities for
dialogue systems, requires developers of the system to spend a considerable
amount of time implementing these capabilities in external, rule-based and
domain specific components. This leads to a poor user experience requiring
users to often correct the system’s understanding, repeat themselves to ask
the same question in different ways, restart the conversation when the system
fails to recover from a ‘dead-end’, or even change their goal.

In this work, we propose to build on recent advances in research on logical
reasoning and deep networks (e.g., Dong et al. 2019; Wang et al. 2019; Xie et
al. 2019; Clark et al. 2020; Arabshahi et al. 2020) to bring reasoning
capabilities to task-oriented dialogue systems. Our primary focus in this work
is on mechanisms by which logical reasoning can be learned and used in
conversational systems. In this direction, we propose a novel deep learning
method to fine-tune pretrained models to reason over numerical and categorical
attributes in the dialogue context and present an architecture for the
integration of this model in task-oriented dialogue systems. Our objective is
for the model to do logical reasoning to respond to queries from the dialogue
context when it has all the required information available in the dialogue
context without additional external logic (e.g., “Add the most popular to my
cart” in Figure 1), extract constraints and inform downstream components when
it only has partial context (e.g., “Actually I’m allergic to berries. Find
something cheaper and with vanilla flavor” in Figure 1, where cheaper means
cheaper than what was shown so far), and not provide an answer when it does
not have any relevant information and delegate to the dialogue policy to
determine the next action.

We specifically choose to fine-tune transformers since these models operate on
language directly, do not impose any structure on the reasoning process Clark
et al. (2020), and we can leverage the knowledge and diversity of language
that the pretrained models have already learned. Furthermore, Ding et al.
(2020) recently showed that these approaches can outperform neuro-symbolic
methods. Our approach is similar to recent works on using transformers as soft
reasoners Clark et al. (2020); Talmor et al. (2020). However, compared to
these methods, we focus on use cases relevant to conversational systems and
our model goes beyond predicting a true/false response to directly predicting
the answer when the model has the information or extract constraints when it
has partial information. In this direction, we report experimental results
that show using our training method transformers can learn to reason over
numerical and categorical attributes in the dialogue context.

Note that although we use transformers for our experiments, our proposed
method can be used to generate data and train any other seq2seq model for the
same task and be integrated with any dialogue system in a similar manner.
Furthermore, our proposed method is different from question-answering or
machine reading comprehension in that we are not looking for an answer in a
specific passage; rather, we want the model to reason over facts in the
dialogue context to draw parallels and conclusions to inform decision making,
similar to how humans reason over a multi-turn conversation.

##  2 Related Work

The approaches for integrating reasoning with deep networks can be categorized
into the following.

#### Reasoning after Semantic Parsing

These approaches convert utterances to a semantic representation and feed it
to a set of rules or a formal reasoner for reasoning. For example, Kamath and
Das (2018) provide examples where given a natural language utterance and
context in the form of a relational database, the system first converts the
natural language utterance to a SQL query that is then executed using standard
SQL grammar to retrieve the answer. This is also similar in approach to how
some teams that participated in the WikiSQL task Victor et al. (2017)
developed natural language interfaces for relational databases. However,
writing and maintaining rules is not scalable especially as more complex types
of reasoning become needed. The data annotation itself becomes hard to manage
efficiently as more functionalities need to be supported. Furthermore, deep
semantic parsing and reliably extracting attributes and relations and
operating on multi-sentence input remains a challenge.

#### Satisfiability-based Approaches

Wang et al. (2019) propose to integrate a differentiable maximum
satisfiability solver into the loop of larger deep learning systems, and use
this approach to successfully learn logical structures such as the rules of
Sudoku. Previous works have shown that temporal reasoning can be modeled as a
propositional satisfiability problem Pham et al. (2008); however,
generalizability to other types of reasoning needs further investigation.
Although covering a rich class of problems, these approaches impose a
structure on the reasoning problem Clark et al. (2020), i.e., learning of
logical structure specifically as expressed by satisfiability problems.

#### Neuro-symbolic Approaches

Neuro-symbolic systems are hybrid models that leverage neural networks and
symbolic reasoning to integrate learning and reasoning. Besold et al. (2017)
provide a survey of how symbolic approaches for reasoning are integrated with
the machine learning approaches that bring in reasoning. More recently, Dong
et al. (2019) propose Neural Logic Machines and apply them to different tasks
such as relational reasoning and sorting. Arabshahi et al. (2020) propose an
end-to-end differentiable solution that uses a Prolog proof trace to learn
rule embeddings from data, and apply their approach to the task of uncovering
commonsense presumptions. Similarly, Xie et al. (2019) generate a graph model
to embed logic rules into the prediction. However, Ding et al. (2020) show
that a fully-learned neural network with the right inductive biases can
outperform neuro-symbolic approaches in the context of spatio-temporal
interactions between objects.

#### Transformer Approaches

Clark et al. (2020 ) and Talmor et al. (2020) propose to train transformers to
reason over natural language sentences, bypassing a formal representation and
show such reasoning over language is learnable. Ding et al. (2020) apply a
similar technique to visual question answering and show that their approach
outperforms neuro-symbolic approaches. Han et al. (2020) use a similar
approach to fine-tune a language model for event temporal reasoning. Our
approach builds on top of these works in that we integrate reasoning into
task-oriented dialogues and go beyond predicting a true/false response for an
input and instead directly predict the answer when the model has the
information or extract constraints when it has partial information.

#### Knowledge Grounding in Dialogue

Similar to how Victor et al. (2017) retrieve knowledge from Wikipedia,
approaches such as Ghazvininejad et al. (2018); Neelakantan et al. (2019);
Gopalakrishnan et al. (2019) retrieve knowledge from a database to be
incorporated into dialogue. These approaches extend the seq2seq approach to
condition on the facts present in the knowledge bases. While this is a
promising architecture, such approaches are good for applications such as
knowledge-grounded open domain chat but not for supporting reasoning in task-
oriented dialogues.

#### Other Approaches

There are also other techniques in the literature such as integrating rules
defined in first-order logic with knowledge distillation Hu et al. (2016) that
are outside the above categories. There have also been efforts such as CLUTRR
Sinha et al. (2019), bAbI dataset Weston et al. (2015), Single Rule Test
Richardson et al. (2020), QuaRTz dataset Tafjord et al. (2019), HotpotQA Yang
et al. (2018), and ROPES (Reasoning over Paragraph Effects in Situations) Lin
et al. (2019), that focus on creating benchmarks for reasoning that measure
how well existing systems perform on generalized reasoning.

##  3 Problem Statement

Task-oriented dialogue systems use a natural language understanding component
to extract semantic meaning from the user utterance, and elicit constraints
from users to understand their goals in order to provide information, perform
a task or provide options and alternatives for users to choose from, retrieved
from external knowledge sources (e.g, through API calls). As such, we focus on
reasoning over tasks and recommended items in the dialogue which are typically
characterized by different attributes, for example, movie names and show-times
for a ticket booking scenario. These systems rely on such representations to
answer user queries such as _“At what time is Vertigo playing?”_ by performing
API calls (e.g. _searchTime(movie=Vertigo)_) which return the required
information in a structured form (Movie=Vertigo, Times=[12:30-2:30 PM, 3-5
PM], Theater=Cineplex). The required information is then returned to the user
in natural language (e.g. _Vertigo is playing today from 12.30 to 2.30 PM and
from 3 to 5 PM_.). However, in most currently available task-oriented dialogue
systems if the user said next “Book me the earliest one,” although this
information is already available to the system from the previous API call,
given the lack of reasoning abilities the system would either not support such
queries, or it would have to make an additional independent API call (e.g.,
_searchEarliestTime(movie=Vertigo)_ or _searchTime(movie=Vertigo,
modifier=earliest)_), creating redundant latency in the response and requiring
the developer of the system to add APIs/rules to handle these use cases.

Given the above description, our objective is to train a model to learn how to
reason over the information provided in the context. We assume the following
scenarios for each user utterance:

1\. Reasoning-required, answer available in the context: The case where the
user utterance requires reasoning and it is possible to infer the answer to
the user query from the information returned by the previous API calls (e.g.,
“Give me the earliest one”). Rather than extracting mentions and querying the
knowledge base again, in this case the model directly outputs the predicted
next system action along with its arguments.

2\. Reasoning-required, answer not available in the context: The case where
the user utterance requires reasoning, but it is not possible to infer the
answer to the user query from the information returned by the previous API
calls (e.g., “Show me cheaper options”). In this case the model extracts
constraints from the user utterance to be passed to the back-end API.

3\. Reasoning-not-required: The case where the user utterance does not require
reasoning (e.g., “Please repeat”).

In order to support these scenarios, the model needs to learn to 1) compare
between different items based on numerical and categorical attributes, 2)
compare across a list of numerical values to identify the minimum/maximum
value among alternatives, 3) be able to formulate constraints when it is not
possible to infer the answer to the user query given the dialogue context but
partial inference can be made, and 4) respond no answer when no reasoning is
required for answering the user’s request.

Figure 2: The reasoning model can be easily integrated in task-oriented
dialogue architecture, as a component of the Dialogue Manager, i.e., the
module in charge of predicting the next system action.

Figure 2 shows the overall architecture of a dialogue system with the
reasoning model. The new model is part of the dialogue manager which predicts
the next system action, along side a domain specific dialogue policy. The
dialogue policy can predict API calls for retrieving information from a back-
end Knowledge Base (KB) or can predict a list of natural language generation
(NLG) actions for communicating information to the user (requesting
constraints, informing available options, etc.). The reasoning model is added
as a modular component that runs along-side the dialogue policy model.
Although it would be possible to combine the two models, e.g, by extending the
reasoning model to also predict domain specific APIs and actions, we believe
that this modular architecture allows the reuse of a trained reasoning model
across different domains and tasks.

Figure 3: Task structure for the generative model.

##  4 Method

In this work we propose to fine-tune transformers to learn logical reasoning
over dialogue context in the form of natural language sentences, bypassing a
formal representation and showing such reasoning over language is learnable.

###  4.1 Data Generation

We describe a general methodology111Upon acceptance, we plan to release the
data generated with the described methodology with the research community. for
automatically creating a dataset for logical reasoning in task-oriented
dialogue systems. Each example in the dataset is a triple (user-query,
context, answer), where the user-query refers to the last user utterance, the
context refers to the dialogue context and information returned by API calls
to the back-end system (see an example in Figure 1), and the answer refers to
the next action to be taken by the dialogue system. The user-query and the
context constitute the information given as input to the model, while the
answer represents the output.

In order to simulate the context, the objects returned by API calls to the
back-end system, we assume an available knowledge base (KB). We further assume
that the KB will have different items, identified by an item-name (e.g.,
_Yogurt Anisakis_), an item-type (e.g., _yogurt_), and a series of attributes,
each with an attribute key and value (e.g., _price: $\$3.40$_). For
generalizability, we do not assume that all item types have the same
attributes, nor that all items of the same type have the same attributes.

Type | Name | Template | Example
---|---|---|---
Context Statement | IsA | [subject] is [object]. | Yogurt Anisakis is a yogurt.
Context Statement | HasAttribute | [subject] has attribute [attribute] with value [value]. | Yogurt Anisakis has attribute price with value $3.55$.
User Query | Inform | I want something [predicate] [value]. | I want something cheaper than $\$5$.
|  | Which one is [predicate]? | Which one is the cheapest?
User Query | Inform_TrueFalse | Is [subject] [predicate]? | Is Yogurt Anisakis the cheapest?
User Query | Select | Select [predicate]. | Select the cheapest.

Table 1:  Examples of templates for context statements (in pseudo-language)
and user queries (in natural language)

The data generation procedure consists of four main steps:

1\. Items sampling: In order to construct input-output pairs for training, we
first randomly select $k$ items, where $0\leq k\leq k_{max}$, with the same
item-type to create the input context $c$. While in this work we compare items
of the same item-type, this is not a strict requirement of data generation.
The motivation behind this choice is given by a typical scenario of a task-
oriented dialogue system where a user might search for a specific object
(movie times of Vertigo) and the system would subsequently present different
options for that object (“Vertigo is playing today from 12:30 to 2:30 PM and
from 3 to 5 PM.”).

2\. Context conversion to pseudo-language: Once a set of items has been
sampled, we transform the structured information (list of triplets) associated
to each item into pseudo-language by using a template-based approach, as in
Figure 3. Our templates are constructed in a domain-agnostic way, so that they
would be directly applicable to other scenarios. We define two main types of
statements in pseudo-language, each one associated to a specific template (see
first two rows in Table 1). The IsA template is used to define the type of an
item, while the HasAttribute relation is used for triplets expressing the
value of a given attribute for the specified item. We note that other
templates for the context statements could easily be created to accommodate
different scenarios. Finally, we concatenate all the generated statements,
after randomizing their order for improving robustness, to form the final
input context.

Reasoning Answer Action Example Output Required in Context Type Yes Yes Inform
Is the first one cheaper than the second one? inform <true/false> Yes Yes
Inform Which one is the cheapest? inform <item_name> Yes Yes Select Add the
cheapest to my cart. select <item_name> Yes No Constraint Give me something
cheaper <relation> <attribute> <value> No $-$ No Answer Find yogurt. NoAnswer

Table 2:  Output space. In cases where there are multiple answers/constraints,
they are concatenated with and.

User Utterance Constraint Give me something vegan. include diet vegan I don’t
want mango. exclude flavor mango It should cost $\$1.50$. equal price $1.50$ I
want it cheaper than $\$2$ less-than price $2$ Anything more popular? more-
than rating $4.5$

Table 3:  Examples of constraints representation, given as context the one in
Figure 2.

3\. Query generation: In this step we generate a set of user queries $q$
suitable for the given context using templates, thus generating several number
of different input pairs $(c,q_{i})$ where $i$ is an index over possible
queries related to the context $c$. Note that templates for the queries are
manually created for each attribute, but they are all agnostic from the domain
of the task-oriented dialogue system. Examples of user queries are shown in
Table 1. As it can be seen, each template for the user query was associated to
the expected output action predicted by the system and the particular
reasoning ability involved (e.g., Inform). We also consider more complex cases
such as _negation_ , e.g., “I don’t want anything vegan,” and _conjunction_ ,
e.g., “Which is the cheapest one and doesn’t have strawberry?”. Additionally,
each template is associated with several different surface form variations to
add robustness to the model. Each generated user query is then prepended to
the context $c$. An additional optional post-processing step consists of
converting all the numerical values in the user queries from written to spoken
format (e.g. _“ $\$3.50$”_ is converted to _“three dollars fifty”_). This step
might be required in the context of a spoken dialogue system scenario, which
takes directly as input the output of the Automatic Speech Recognition model.

4\. Output creation: In the final step, for each generated input, we
automatically create the output by combining the information from each
template in regards to the action type to take and calculating the correct
answer from the context, e.g., _Yogurt Anisakis is the cheapest_. The output
space consists of four main outcomes, as shown in Table 2, depending on
whether reasoning is required to respond to the user utterance, and whether
the answer is retrievable from the available context. We use the special token
NoAnswer for user queries that do not require reasoning. When the answer is
retrievable from the context and reasoning is required, we further distinguish
between two main cases: inform, when the user is simply seeking information
(e.g., _“Which one is the cheapest?”_), thus performing an Information-
Transfer type of Dialogue Act (see Bunt et al. (2010)), and select, when the
user is requesting the system to perform a specific action (e.g., _“Add the
cheapest to my cart.”_), an Action-Discussion Dialogue Act. For the inform
action, we also distinguish in the output space between True/False questions
and open-answer questions.

In the case of constraint extraction answers, i.e., when the user utterance
requires reasoning but the context has partial information, the output
consists of the list of constraints extracted from the user query and
concatenated with and, as shown in Table 3. The constraints extracted from the
user query depend on the context, not only in terms of action to take (whether
to provide an answer directly or to extract constraints), but also in terms of
constraints generation. In the last row of Table 3, for user query ("..more
popular?") the reasoning model relies on the context by looking at the ratings
of the available products to extract the appropriate rating constraint (e.g,
more-than rating $4.5$).

###  4.2 Training Procedure

In order to teach the model rules such as inverse relations and transitivity
by example, we investigate the use of appending to the context clues that
describe the relations of one or more items. These clues are appended to the
final input context during training, but not at inference time. We consider
two types of clues: 1) _Comparative clue_ describes a comparison of two items
in the context along a specific attribute. The template for this clue is:
[subject] is [predicate] [object], where predicate refers to the quality
regarding which the items are being judged (e.g., “cheaper than”, “pricier
than”, “less than”, “equal to”). 2) _Superlative clue_ describes an object at
the upper/lowest range of a specific attribute. The template for this clue is:
[subject] is [predicate] with value [value]. Using the base data generation
and clue generation, we are able to construct three types of training
scenarios, as follows:

Case I - Clueless context: This scenario uses the base context encompassing
the information about the items’ different attributes. This is also the
scenario we expect at inference time.

Case II - Comparative clues: In this scenario, we sort the items in the base
context according to the values of their attributes and append to the base
context the comparative relation between pairs of items that are neighbors.
The direction of comparison selected is random (e.g. “A is larger than B” or
“B is smaller than A”) and independent from the user query. This scenario is
designed to assess the ability of the model to learn inverse relations, since
in some queries users will ask for a relation in the opposite direction in
regards to the comparative clue in the context (e.g., user asks “Is the second
one cheaper than the first one?” while in the context we have “A is pricier
than B”), so that the model could learn that these two statements are
equivalent. When we have more than two items in context, we can also assess
the ability of the model to learn transitivity, as we might have cases where
the user asks “Is the first one pricier than the third one?” and in the
context we have “A is pricier than B” and “B is pricier than C”.

Case III - Superlative clues: In this scenario, besides comparative clues, we
also add superlative clues to the context to give hints to the model about
which item in the context has the extreme value of the attributes (e.g. “A is
the cheapest”).

We pick the number of items in each context randomly from $0$ to $k_{max}$, so
that the model can be robust in its prediction for different number of items
in the context. We also consider an additional training procedure, which we
refer to as Case IV, where we randomly select one of Case I, Case II, or Case
III as our context. The random selection of context helps the model to
experience all three different cases and by cross learning between different
cases, it learns to apply the inverse and transitivity rules for examples with
Case I context to draw the right conclusion.

##  5 Experiments

We showcase our proposed methodology in the context of a dialogue system for a
shopping assistant (see Appendix A for an example interaction). We use an
ontology for data generation which consists of item-type (e.g. yogurt) and
item-name (“Greek yogurt Anisakis”) and each item is characterized by two
numerical attributes price and rating, and two categorical attributes diet and
flavor. This choice of attributes can help us explore and assess the model’s
performance based on attribute’s characteristics. Table 4 summarizes the size
of the catalog or range of values for each attribute.

Rating Price Diet Flavor Bounded
Numeric Unbounded
Numeric 10 10K

Table 4:  Attributes and their catalogs size.

We consider two settings for assessing the logical reasoning capability of
transformer models. In the first setting, we fine-tune RoBERTa-base Liu et al.
(2019) with a training dataset generated for reasoning using only numerical
attributes. In this setting, we only focus on True/False prediction for each
query $q$ given the facts provided in the context $c$. The objective of this
experiment is to understand whether transformer models can learn to reason
over numerical attributes. In the second setting, we use a T5 model Raffel et
al. (2019) fine-tuned for the UnifiedQA data Khashabi et al. (2020), to
predict a sequence similar to one given in Table 2. In both cases, we use
disjoint catalogs to generate examples for train/dev/test datasets to avoid
over-fitting to attribute values.

###  5.1 True/False Queries

We consider True/False reasoning over attributes such as assessing a
conclusion about the comparison of two values of an attribute, or finding
minimum or maximum value among list of values of an attribute for several
items. Example queries include “is the second item the cheapest one” and “is
the first one cheaper than the fourth one”. We fine-tune RoBERTa to predict
True/False for each ($q$, $c$) by adding a classification layer on top of the
RoBERTa encoder model to perform binary classification. The training hyper-
parameters for fine-tuning this model are provided in Appendix B. For these
experiments, we generate $120$K samples for train, $5$K for dev, and $25$K for
test set.

Clueless Training: In this case, we only add IsA and HasAttribute relations
and don’t include any clue in the context $c$ in the training data (i.e., Case
I). For each generated context, the data generation process attaches all
possible forms of queries and the potential true/false label and adds them to
training samples. For evaluation, we generate the test samples in a similar
fashion. Table 5 summarizes the model performance for predicting the right
label for each query given the context with $k\in{2,3,5}$ number of items in
the context.

Train/Test I/I II/II III/III 2 items $90\%$ $97\%$ $97\%$ 3 items $88\%$
$95\%$ $95\%$ 5 items $77\%$ $91\%$ $93\%$

Table 5: Roberta-Base model performance for T/F Reasoning over Price and
Rating.

We can see that by increasing the context size (or number of returning items
from back-end) the model performance decreases. To understand how well a model
with larger $k$ with comparative or superlative clues can generalize to fewer
number of items in context, Table 6 shows the performance of a model trained
with context size of $5$ items using Case II or Case III samples and tested on
samples generated by Case I and with $k\in{2,3,5}$ items. We observe that the
model does not generalize to different context sizes if we fix the number of
items in the context during model training.

Train $\rightarrow$ Case II Case III Test $\downarrow$ (5 items) (5 items)
Case I, (2 items) $75\%$ $76\%$ Case I, (3 items) $70\%$ $71\%$ Case I, (5
items) $67\%$ $69\%$

Table 6:  Train on Case II or Case III with $5$ items in all the contexts and
test on Case I with $2$, $3$, or $5$ items.

Clue-Aware Training: To resolve the issues in clueless training, we add
comparative and superlative clues randomly to each context during the training
such that the model can learn the inverse and transitivity rules; and also we
add random number of items to each individual context (up to $k_{max}$). Note
that we do not add clues to the context during evaluation/inference. Results
in Table 7 show the accuracy performance of models trained using samples
generated by Case IV and tested on Case I (clue-less), Case II (only
comparative clues), and Case III (both comparative and superlative clues)
samples.

Train/Test IV/I IV/II IV/III up-to 5 items 98.70% 99.70% 99.70%

Table 7: Training with CaseIV: Roberta model performance for T/F reasoning
over numerical attributes.

From the results, we observed that adding clues during model training helps
the model to achieve better performance.

###  5.2 Beyond True/False Queries

For this set of experiments, we pick the T5 transformer model which can enable
us to perform text-to-text prediction. Similar to Khashabi et al. (2020), we
remove the task prefix that has been used in the original T5 models, since we
will use this model only for a single reasoning task within our defined
framework. To take advantage of transfer learning from other publicly
available question-answering datasets, we start our fine-tuning from the
pretrained Unified-QA-T5 small model. We generate $100$K samples for training
dataset, $5$K for dev, and $20$K examples for each test set. In our test set
we make sure that for each element in Table 8, we have at least $5$K examples.
Samples are generated as described in Section 4.1. The training hyper-
parameters for fine-tuning this model are provided in Appendix B.

In Table 8, we summarize the performance of the fined-tuned model for
different scenarios, reporting the results separately for pair of ($q$, $c$)
such that $q$ can have one (e.g., “Give me something organic’) or two
attributes (e.g., ‘Something cheaper than $\$100$ but not vegan”) about user-
preferences. We use the exact-match (EM) accuracy metric to evaluate model
performance. We can observe that the model can achieve an EM accuracy of over
$90\%$ across all the scenarios. Furthermore, we see that when increasing the
number of items in the reasoning context, predicting the correct Inform/Select
or Extract output form becomes harder with more attributes in the user query.
Evaluating the model performance on all examples (about $8$K samples) from our
test set that include spoken form of numerical values in $q$ (e.g., “Give me
something cheaper than five dollars”), we observe $95\%$ EM accuracy, showing
the ability of the model to compare written form and spoken form versions of
numbers. We should note that the accuracy of the model for predicting the
cases with no reasoning (e.g., “Checkout please”) is important because it
makes the integration with the overall dialogue system simpler where the model
can delegate to the domain specific dialogue policy. In our experiments, we
observe an accuracy of $100\%$ on these cases; however, this value can vary by
increasing the size of out-of-domain space/vocabulary.

# of Attr.s $k_{m}$ Inform/Select Extract 1 0 – $99.5\pm 0.02\%$ 1 $98.6\pm
0.05\%$ $99.2\pm 0.03\%$ 2 $97.3\pm 0.05\%$ $98.5\pm 0.05\%$ 3 $97.0\pm
0.05\%$ $98.0\pm 0.03\%$ 4 $96.0\pm 0.10\%$ $98.0\pm 0.05\%$ 5 $95.5\pm
0.09\%$ $96.0\pm 0.06\%$ 2 0 – $98.6\pm 0.03\%$ 1 $98.5\pm 0.05\%$ $97.8\pm
0.02\%$ 2 $95.0\pm 0.08\%$ $96.7\pm 0.01\%$ 3 $94.5\pm 0.05\%$ $96.3\pm
0.03\%$ 4 $91.5\pm 0.09\%$ $95.0\pm 0.03\%$ 5 $90.0\pm 0.11\%$ $93.5\pm
0.06\%$

Table 8: EM accuracy for test sets with different number of attributes,
context size, and reasoning task.

##  6 Conclusions

In this paper, we proposed an architecture for the integration of a reasoning
model in task-oriented dialogue systems. We formulated the problem as a
sequence prediction problem given a user query and context, and presented an
approach for generating data and fine-tuning generative models to reason over
a set of facts in the dialogue context. We demonstrated our approach for a
shopping assistant and reported experimental results for different
formulations of the problem. We showed that these models can learn to do
logical reasoning to 1) answer questions form the dialogue context when all
the information is available, 2) extract constraints when partial information
is available, and 3) delegate to the dialogue policy when no reasoning is
required. For future work, we plan to investigate the application of our
method to other reasoning tasks (e.g., temporal and spatial reasoning).
Furthermore, we plan to explore how logical reasoning can be used to
disambiguate with the user when multiple conclusions can be made.

## References

  * Arabshahi et al. (2020) Forough Arabshahi, Jennifer Lee, Mikayla Gawarecki, Kathryn Mazaitis, Amos Azaria, and Tom Mitchell. 2020.  Conversational neuro-symbolic commonsense reasoning.  _arXiv preprint arXiv:2006.10022_.
  * Besold et al. (2017) Tarek R Besold, Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pascal Hitzler, Kai-Uwe Kühnberger, Luis C Lamb, Daniel Lowd, Priscila Machado Vieira Lima, et al. 2017.  Neural-symbolic learning and reasoning: A survey and interpretation.  _arXiv preprint arXiv:1711.03902_.
  * Bunt et al. (2010) Harry Bunt, Jan Alexandersson, Jean Carletta, Jae-Woong Choe, Alex Chengyu Fang, Koiti Hasida, Kiyong Lee, Volha Petukhova, Andrei Popescu-Belis, Laurent Romary, Claudia Soria, and David Traum. 2010.  Towards an ISO standard for dialogue act annotation.  In _Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10)_ , Valletta, Malta. European Language Resources Association (ELRA).
  * Chen et al. (2020) Xiuying Chen, Zhi Cui, Jiayi Zhang, Chen Wei, Jianwei Cui, Bin Wang, Dongyan Zhao, and Rui Yan. 2020.  Reasoning in dialog: Improving response generation by context reading comprehension.  _CoRR_ , abs/2012.07410.
  * Clark et al. (2020) Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020.  Transformers as soft reasoners over language.  _arXiv preprint arXiv:2002.05867_.
  * Cui et al. (2020) Leyang Cui, Yu Wu, Shujie Liu, Yue Zhang, and Ming Zhou. 2020.  Mutual: A dataset for multi-turn dialogue reasoning.  _CoRR_ , abs/2004.04494.
  * Ding et al. (2020) David Ding, Felix Hill, Adam Santoro, and Matt Botvinick. 2020.  Object-based attention for spatio-temporal reasoning: Outperforming neuro-symbolic models with flexible distributed architectures.  _arXiv preprint arXiv:2012.08508_.
  * Dong et al. (2019) Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. 2019\.  Neural logic machines.  _arXiv preprint arXiv:1904.11694_.
  * Ghazvininejad et al. (2018) Marjan Ghazvininejad, Chris Brockett, Ming-Wei Chang, Bill Dolan, Jianfeng Gao, Wen-tau Yih, and Michel Galley. 2018.  A knowledge-grounded neural conversation model.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 32(1).
  * Gopalakrishnan et al. (2019) Karthik Gopalakrishnan, Behnam Hedayatnia, Qinlang Chen, Anna Gottardi, Sanjeev Kwatra, Anu Venkatesh, Raefer Gabriel, and Dilek Hakkani-Tür. 2019.  Topical-Chat: Towards Knowledge-Grounded Open-Domain Conversations.  In _Proc. Interspeech 2019_ , pages 1891–1895.
  * Guo et al. (2017) Xiaoxiao Guo, Tim Klinger, Clemens Rosenbaum, Joseph P Bigus, Murray Campbell, Ban Kawas, Kartik Talamadupula, Gerry Tesauro, and Satinder Singh. 2017.  Learning to query, reason, and answer questions on ambiguous texts.
  * Han et al. (2020) Rujun Han, Xiang Ren, and Nanyun Peng. 2020.  Deer: A data efficient language model for event temporal reasoning.  _arXiv preprint arXiv:2012.15283_.
  * Hu et al. (2016) Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. 2016.  Harnessing deep neural networks with logic rules.  _arXiv preprint arXiv:1603.06318_.
  * Huang et al. (2019) Lifu Huang, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2019.  Cosmos QA: Machine reading comprehension with contextual commonsense reasoning.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2391–2401, Hong Kong, China. Association for Computational Linguistics.
  * Kamath and Das (2018) Aishwarya Kamath and Rajarshi Das. 2018.  A survey on semantic parsing.  _arXiv preprint arXiv:1812.00978_.
  * Khashabi et al. (2020) Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. 2020.  Unifiedqa: Crossing format boundaries with a single QA system.  _CoRR_ , abs/2005.00700.
  * Lin et al. (2019) Kevin Lin, Oyvind Tafjord, Peter Clark, and Matt Gardner. 2019.  Reasoning over paragraph effects in situations.  _arXiv preprint arXiv:1908.05852_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Neelakantan et al. (2019) Arvind Neelakantan, Semih Yavuz, Sharan Narang, Vishaal Prasad, Ben Goodrich, Daniel Duckworth, Chinnadhurai Sankar, and Xifeng Yan. 2019.  Neural assistant: Joint action prediction, response generation, and latent knowledge reasoning.  _CoRR_ , abs/1910.14613.
  * Pham et al. (2008) Duc Nghia Pham, John Thornton, and Abdul Sattar. 2008.  Modelling and solving temporal reasoning as propositional satisfiability.  _Artificial Intelligence_ , 172(15):1752–1782.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _CoRR_ , abs/1910.10683.
  * Richardson et al. (2020) Kyle Richardson, Hai Hu, Lawrence Moss, and Ashish Sabharwal. 2020.  Probing natural language inference models through semantic fragments.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8713–8721.
  * Sinha et al. (2019) Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L Hamilton. 2019\.  Clutrr: A diagnostic benchmark for inductive reasoning from text.  _arXiv preprint arXiv:1908.06177_.
  * Tafjord et al. (2019) Oyvind Tafjord, Matt Gardner, Kevin Lin, and Peter Clark. 2019.  Quartz: An open-domain dataset of qualitative relationship questions.  _arXiv preprint arXiv:1909.03553_.
  * Talmor et al. (2020) Alon Talmor, Oyvind Tafjord, Peter Clark, Yoav Goldberg, and Jonathan Berant. 2020\.  Leap-of-thought: Teaching pre-trained models to systematically reason over implicit knowledge.  _arXiv preprint arXiv:2006.06609_.
  * Victor et al. (2017) Zhong Victor, Xiong Caiming, and Socher Richard. 2017.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  _CoRR_ , abs/1709.00103.
  * Wang et al. (2019) Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. 2019.  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  In _International Conference on Machine Learning_ , pages 6545–6554. PMLR.
  * Weston et al. (2015) Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_.
  * Xie et al. (2019) Yaqi Xie, Ziwei Xu, Mohan S Kankanhalli, Kuldeep S Meel, and Harold Soh. 2019.  Embedding symbolic knowledge into deep networks.  _arXiv preprint arXiv:1909.01161_.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018.  Hotpotqa: A dataset for diverse, explainable multi-hop question answering.  _arXiv preprint arXiv:1809.09600_.

##  Appendix A Example Interaction with the Shopping Assistant

The following is an example interaction with the shopping assistant with our
reasoning model integrated with the dialogue policy.

Speaker Utterance User I want to buy apples Agent The top 3 relevant products
are: Organic Honycrisp Apple, Organic Gala Apple, and Organic Pink Lady Apple.
Which one would you like to add to the cart? User Which one is the cheapest?
Agent The second one, Organic Gala Apple with a price of $2.49. User Which one
is the most expensive? Agent The first one, Organic Honeycripst Apple with a
price of $3.99 User Is the first one cheaper than the second one? Agent No.
The first one, Organic Honeycripst Apple, costs $3.99 but the second one,
Organic Gala Apple, costs $2.49. User Is the second one cheaper? Agent Yes,
that is correct. The second one, Organic Gala Apple, costs $2.49. User Give me
something cheaper Agent Top relevant product is Fuji Apple. Would you like to
add it to the cart? User Does it cost less than two dollars? Agent Yes, that
is correct. Fuji Apple costs $1.89. User Add it to my cart Agent I have added
Fuji Apple to your cart. What else would you like to buy? User Buy grapes
Agent The top 2 relevant products are: Red Seedless Grapes and Conventional
Cut Grapes. Which one would you like to add to the cart? User Is the second
one more popular? Agent No. The second one, Conventional Cut Grapes has a
rating of 4.3 but the first one, Red Seedless Grapes has a rating of 4.5. User
Add the highest rated one to my cart Agent I have added Red Seedless Grapes to
your cart. What else would you like to buy? User Find cheese Agent The top 2
relevant products are: Zola and Muller. Which one would you like to add to the
cart? User Anything vegan and cheaper than five dollars? Agent I couldn’t find
anything vegan with price less than five dollars. But I found Vegan Artisan
cheese with price of $7.99. Would you like to add it to the cart? User Sure
Agent I have added Vegan Artisan cheese to your cart. What else would you like
to buy? User What’s in my cart? Agent You have 3 items in the cart with total
amount of $12.87. Do you want to hear detailed description? User Checkout
Agent I have placed your order.

##  Appendix B Training Hyper-parameters

In this section, we provide the parameters that are used to fine-tune the
transformer models in this work. The following table summarizes the key
parameters that are used during the fine-tuning of Roberta-base and
UnifiedQA-T5-small pretrained models. For the optimizer, we use AdamW
Loshchilov and Hutter (2017).

Model Batch Size Epoch Optimizer Learning Rate Weight Decay Roberta-Base 192
15 AdamW $10^{-5}$ 0.1 UnifiedQA-T5-small 1024 20 AdamW $10^{-5}$ 0.0

##  Appendix C Discussion

###  C.1 Generalization to non-synthesis datasets

One of the directions that currently we are working on is to create realistic
(human based) conversations with logical reasoning use cases during the
interactions with the dialog systems. This type of dataset can help us to
evaluate the proposed idea with higher degree of confidence. Since no matter
how much one spends time on generating synthetic datasets, there will always
be some uncontrolled structures introduced by design of data simulation
mechanisms that can corrupt the fair evaluation of deep neural network models
and their learning process. However, we believe the True/False scenarios in
our current study are less prone to this type of issues and are quite helpful
in understating of reasoning capabilities such as negation, numerical
comparison, or inclusion/exclusion of categorical values of our proposed
algorithm, since model needs to learn the reasoning procedure. In other words,
the only way to come up with the right prediction by model is to apply the
underlying reasoning procedure to formulate the output True/False results. We
will consider: a) better algorithms for generating training data, and b) more
realistic general purpose possibly human in the loop training data to make the
data generation more general and less domain specific, for future exploration.

###  C.2 Error Analysis

During our evaluation, we observed that the Transformer models (such as
Roberta and T5) performance degrades when the length of the reasoning context
increases, i.e., the number of items in the context for reasoning are longer.
Also based on the results on Table 8, we see that increasing the number of
items in reasoning context leads to performance degradation. Another issue
with Transformer models or in general LM models is during the output
generation process beyond the True/False scenario. When the size of the output
sequence length increases, e.g., there are several items that all satisfy the
user-query. The prediction misses some of the items in the response after the
length of the output sequence (number of predicted tokens/words) meets some
threshold. This issue is related to both long sequence generation of LM models
and also reasoning ability when the multiple items match the user-query’s
criteria which mostly occurs when the number of items in context are larger.

###  C.3 Generalization to unseen attribute with common values

One of the aspect that we like to understand is the scalability/generalization
of the proposed trained reasoning model to unseen attributes during the test
time. There are two possibility for a new attribute: (1) doesn’t shares values
and keywords that user may use to describe the attribute compared to the
attributes that are used during the training process e.g., color attribute for
experiment in Section 5 222For query about the color user may use keywords
such as: [darker, lighter, warmer, red, blue, …, etc. ] one, and attribute
values are red, blue, dark blue, …. etc. which doesn’t overlap with none of
the attributes that we have already in our training dataset, i.e., diet,
flavor, price, and rating. (2) shares same values but keywords that user may
use to describe the attribute doesn’t overlap with any of the ones used during
the training process, e.g., calorie 333For query about the calories user may
use keywords such as: [healthier, higher calories, more energetic…, etc. ]
one, and attribute values are numeric value that are shared possibly with
price and rating [considering we have done unit normalization for attributes].
It would be very challenging to teach model in a few-shot manner to learn
about attributes from bucket (1). However, based on our initial experiments we
have seen that model can easily generalize to the attributes from bucket (2),
by fine-tuning to small number of examples in a few-shot manner. For example,
we fine-tuned the model which only trained for diet, flavor, price, and rating
attributes and fine-tuned using only $100$ new reasoning context examples
which had $calorie$ attribute as well. Table 9 summarize the model performance
before and after fine-tuning. The test set used for this analysis only has
user-query about calories and includes $3K$ examples about Calorie attribute.

Model EM accuracy Before fine-tuning $33\%$ After fine-tuning $80\%$

Table 9:  Model EM accuracy performance before/after fine-tuning to new
attribute calorie.


* Parsa  _et al._ (2020) S. Parsa, E. Santanach-Carreras, L. Xiao, and D. A. Weitz, “Origin of anomalous polymer-induced fluid displacement in porous media,” Physical Review Fluids 5, 022001 (2020).
  * Druetta and Picchioni (2020) P. Druetta and F. Picchioni, “Influence of physical and rheological properties of sweeping fluids on the residual oil saturation at the micro-and macroscale,” Journal of Non-Newtonian Fluid Mechanics 286, 104444 (2020).
  * Kundu, Cohen, and Dowling (2015) P. K. Kundu, I. M. Cohen, and D. R. Dowling,  _Fluid Mechanics_ (Academic press, 2015).
  * James (2009) D. F. James, “Boger fluids,” Annual Review of Fluid Mechanics 41, 129–142 (2009).
  * Jackson, Walters, and Williams (1984) K. Jackson, K. Walters, and R. Williams, “A rheometrical study of boger fluids,” Journal of Non-Newtonian Fluid Mechanics 14, 173–188 (1984).
  * Verhoef, Van den Brule, and Hulsen (1999) M. Verhoef, B. Van den Brule, and M. Hulsen, “On the modelling of a pib/pb boger fluid in extensional flow,” Journal of Non-Newtonian Fluid Mechanics 80, 155–182 (1999).
  * Joo and Shaqfeh (1994) Y. L. Joo and E. S. Shaqfeh, “Observations of purely elastic instabilities in the taylor–dean flow of a boger fluid,” Journal of Fluid Mechanics 262, 27–73 (1994).
  * Alves, Pinho, and Oliveira (2005) M. Alves, F. Pinho, and P. J. Oliveira, “Visualizations of boger fluid flows in a 4: 1 square–square contraction,” AIChE journal 51, 2908–2922 (2005).
  * Bot, Hulsen, and Van den Brule (1998) E. Bot, M. Hulsen, and B. Van den Brule, “The motion of two spheres falling along their line of centres in a boger fluid,” Journal of Non-Newtonian Fluid Mechanics 79, 191–212 (1998).
  * James and Roos (2021) D. F. James and C. A. Roos, “Pressure drop of a boger fluid in a converging channel,” Journal of Non-Newtonian Fluid Mechanics 293, 104557 (2021).
  * Sousa  _et al._ (2009) P. Sousa, P. Coelho, M. Oliveira, and M. Alves, “Three-dimensional flow of newtonian and boger fluids in square–square contractions,” Journal of Non-Newtonian Fluid Mechanics 160, 122–139 (2009).
  * Wei  _et al._ (2007) Y. Wei, G. Seevaratnam, S. Garoff, E. Ramé, and L. Walker, “Dynamic wetting of boger fluids,” Journal of Colloid and Interface science 313, 274–280 (2007).
  * Mitsoulis (2010) E. Mitsoulis, “Extrudate swell of boger fluids,” Journal of Non-Newtonian Fluid Mechanics 165, 812–824 (2010).
  * Anna (2008) S. L. Anna, “Non-newtonian fluids in microfluidics,” in  _Encyclopedia of Microfluidics and Nanofluidics_, edited by D. Li (Springer US, Boston, MA, 2008) pp. 1480–1488.
  * Mei and Qian (2022) L. Mei and S. Qian, “Editorial for the special issue on micromachines for non-newtonian microfluidics,” (2022).
  * Nghe  _et al._ (2011) P. Nghe, E. Terriac, M. Schneider, Z. Li, M. Cloitre, B. Abecassis, and P. Tabeling, “Microfluidics and complex fluids,” Lab on a Chip 11, 788–794 (2011).
  * Haward  _et al._ (2011) S. J. Haward, J. A. Odell, M. Berry, and T. Hall, “Extensional rheology of human saliva,” Rheologica Acta 50, 869–879 (2011).
  * Juarez and Arratia (2011) G. Juarez and P. E. Arratia, “Extensional rheology of dna suspensions in microfluidic devices,” Soft Matter 7, 9444–9452 (2011).
  * Bloomfield, Johnston, and Bilston (1998) I. Bloomfield, I. Johnston, and L. Bilston, “Effects of proteins, blood cells and glucose on the viscosity of cerebrospinal fluid,” Pediatric Neurosurgery 28, 246–251 (1998).
  * Chhabra and Richardson (2011) R. P. Chhabra and J. F. Richardson,  _Non-Newtonian Flow and Applied Rheology: Engineering Applications_ (Butterworth-Heinemann, 2011).
  * Everts and Meyer (2018) M. Everts and J. P. Meyer, “Heat transfer of developing and fully developed flow in smooth horizontal tubes in the transitional flow regime,” International Journal of Heat and Mass Transfer 117, 1331–1351 (2018).
  * Varshney and Steinberg (2019) A. Varshney and V. Steinberg, “Elastic alfven waves in elastic turbulence,” Nature Communications 10, 1–7 (2019).
  * Varshney and Steinberg (2018b) A. Varshney and V. Steinberg, “Mixing layer instability and vorticity amplification in a creeping viscoelastic flow,” Physical Review Fluids 3, 103303 (2018b).
  * Khan and Sasmal (2022b) M. B. Khan and C. Sasmal, “Electro-elastic instability in electroosmotic flows of viscoelastic fluids through a model porous system,” European Journal of Mechanics-B/Fluids (2022b).
  * Kandlikar  _et al._ (2005) S. Kandlikar, S. Garimella, D. Li, S. Colin, and M. R. King,  _Heat transfer and fluid flow in minichannels and microchannels_ (elsevier, 2005).
  * Ghiaasiaan (2007) S. M. Ghiaasiaan,  _Two-phase flow, boiling, and condensation: in conventional and miniature systems_ (Cambridge University Press, 2007).
  * Kim and Mudawar (2014) S.-M. Kim and I. Mudawar, “Review of databases and predictive methods for heat transfer in condensing and boiling mini/micro-channel flows,” International Journal of Heat and Mass Transfer 77, 627–652 (2014).
  * Cheng, Mewes, and Luke (2007) L. Cheng, D. Mewes, and A. Luke, “Boiling phenomena with surfactants and polymeric additives: a state-of-the-art review,” International Journal of Heat and Mass Transfer 50, 2744–2771 (2007).
  * Wang  _et al._ (2015a) J. Wang, J. Wang, L. Feng, and T. Lin, “Fluid mixing in droplet-based microfluidics with a serpentine microchannel,” RSC Advances 5, 104138–104144 (2015a).
  * Song, Chen, and Ismagilov (2006) H. Song, D. L. Chen, and R. F. Ismagilov, “Reactions in droplets in microfluidic channels,” Angewandte Chemie International Edition 45, 7336–7356 (2006).
  * Chen, Sun, and Chen (2019) R. Chen, Z. Sun, and D. Chen, “Droplet-based microfluidics for cell encapsulation and delivery,” in  _Microfluidics for Pharmaceutical Applications_ (Elsevier, 2019) pp. 307–335.
  * Clausell-Tormos  _et al._ (2008) J. Clausell-Tormos, D. Lieber, J.-C. Baret, A. El-Harrak, O. J. Miller, L. Frenz, J. Blouwolff, K. J. Humphry, S. Köster, H. Duan, _et al._ , “Droplet-based microfluidic platforms for the encapsulation and screening of mammalian cells and multicellular organisms,” Chemistry & Biology 15, 427–437 (2008).
  * Mazutis  _et al._ (2013) L. Mazutis, J. Gilbert, W. L. Ung, D. A. Weitz, A. D. Griffiths, and J. A. Heyman, “Single-cell analysis and sorting using droplet-based microfluidics,” Nature Protocols 8, 870–891 (2013).
  * Shembekar  _et al._ (2016) N. Shembekar, C. Chaipan, R. Utharala, and C. A. Merten, “Droplet-based microfluidics in drug discovery, transcriptomics and high-throughput molecular genetics,” Lab on a Chip 16, 1314–1331 (2016).
  * Liu and Zhu (2020) W.-w. Liu and Y. Zhu, ““development and application of analytical detection techniques for droplet-based microfluidics”-a review,” Analytica Chimica Acta 1113, 66–84 (2020).
  * Seemann  _et al._ (2011) R. Seemann, M. Brinkmann, T. Pfohl, and S. Herminghaus, “Droplet based microfluidics,” Reports on Progress in Physics 75, 016601 (2011).
  * Xuan and Li (2000) Y. Xuan and Q. Li, “Heat transfer enhancement of nanofluids,” International Journal of heat and fluid flow 21, 58–64 (2000).
  * Das  _et al._ (2007) S. K. Das, S. U. Choi, W. Yu, and T. Pradeep,  _Nanofluids: science and technology_ (John Wiley & Sons, 2007).
  * Chamkha  _et al._ (2018) A. J. Chamkha, M. Molana, A. Rahnama, and F. Ghadami, “On the nanofluids applications in microchannels: a comprehensive review,” Powder Technology 332, 287–322 (2018).
  * Mohammed  _et al._ (2011) H. Mohammed, G. Bhaskaran, N. Shuaib, and R. Saidur, “Heat transfer and fluid flow characteristics in microchannels heat exchanger using nanofluids: a review,” Renewable and Sustainable Energy Reviews 15, 1502–1512 (2011).
  * Ramesh, Sharma, and Rao (2021) K. N. Ramesh, T. K. Sharma, and G. Rao, “Latest advancements in heat transfer enhancement in the micro-channel heat sinks: a review,” Archives of Computational Methods in Engineering 28, 3135–3165 (2021).
  * Yang  _et al._ (2012) J.-C. Yang, F.-C. Li, W.-W. Zhou, Y.-R. He, and B.-C. Jiang, “Experimental investigation on the thermal conductivity and shear viscosity of viscoelastic-fluid-based nanofluids,” International Journal of Heat and Mass Transfer 55, 3160–3166 (2012).
  * Yang  _et al._ (2013) J.-C. Yang, F.-C. Li, Y.-R. He, Y.-M. Huang, and B.-C. Jiang, “Experimental study on the characteristics of heat transfer and flow resistance in turbulent pipe flows of viscoelastic-fluid-based cu nanofluid,” International Journal of Heat and Mass Transfer 62, 303–313 (2013).
  * Hayat  _et al._ (2017) T. Hayat, F. Haider, T. Muhammad, and A. Alsaedi, “On darcy-forchheimer flow of viscoelastic nanofluids: A comparative study,” Journal of Molecular Liquids 233, 278–287 (2017).
  * Yang  _et al._ (2015) J. Yang, F. Li, H. Xu, Y. He, Y. Huang, and B. Jiang, “Heat transfer performance of viscoelastic-fluid-based nanofluid pipe flow at entrance region,” Experimental Heat Transfer 28, 125–138 (2015).
  * Adler and Brenner (1988) P. M. Adler and H. Brenner, “Multiphase flow in porous media,” Annual Review of Fluid Mechanics 20, 35–59 (1988).
  * Gerami  _et al._ (2017) A. Gerami, R. T. Armstrong, B. Johnston, M. E. Warkiani, N. Mosavat, and P. Mostaghimi, “Coal-on-a-chip: visualizing flow in coal fractures,” Energy & Fuels 31, 10393–10403 (2017).
  * He  _et al._ (2015) K. He, L. Xu, Y. Gao, X. Yin, and K. B. Neeves, “Evaluation of surfactant performance in fracturing fluids for enhanced well productivity in unconventional reservoirs using rock-on-a-chip approach,” Journal of Petroleum Science and Engineering 135, 531–541 (2015).
  * Torabzadey (1984) S. Torabzadey, “The effect of temperature and interfacial tension on water/oil relative permeabilities of consolidated sands,” in  _SPE Enhanced Oil Recovery Symposium_ (OnePetro, 1984).
  * Qin  _et al._ (2018) Y. Qin, Y. Wu, P. Liu, F. Zhao, and Z. Yuan, “Experimental studies on effects of temperature on oil and water relative permeability in heavy-oil reservoirs,” Scientific Reports 8, 1–9 (2018).
  * Afolabi  _et al._ (2022) F. Afolabi, S. M. Mahmood, N. Yekeen, S. Akbari, and H. Sharifigaliuk, “Polymeric surfactants for enhanced oil recovery: A review of recent progress,” Journal of Petroleum Science and Engineering 208, 109358 (2022).
  * Raffa, Broekhuis, and Picchioni (2016) P. Raffa, A. A. Broekhuis, and F. Picchioni, “Polymeric surfactants for enhanced oil recovery: A review,” Journal of Petroleum Science and Engineering 145, 723–733 (2016).
  * Souas, Safri, and Benmounah (2020) F. Souas, A. Safri, and A. Benmounah, “On the rheological behavior of light crude oil: a review,” Petroleum Science and Technology 38, 849–857 (2020).
  * Ariffin, Yahya, and Husin (2016) T. S. T. Ariffin, E. Yahya, and H. Husin, “The rheology of light crude oil and water-in-oil-emulsion,” Procedia Engineering 148, 1149–1155 (2016).
  * Hasan, Ghannam, and Esmail (2010) S. W. Hasan, M. T. Ghannam, and N. Esmail, “Heavy crude oil viscosity reduction and rheology for pipeline transportation,” Fuel 89, 1095–1100 (2010).
  * Livescu (2012) S. Livescu, “Mathematical modeling of thixotropic drilling mud and crude oil flow in wells and pipelines—a review,” Journal of Petroleum Science and Engineering 98, 174–184 (2012).
  * Liu, Lu, and Zhang (2018) H. Liu, Y. Lu, and J. Zhang, “A comprehensive investigation of the viscoelasticity and time-dependent yielding transition of waxy crude oils,” Journal of Rheology 62, 527–541 (2018).
  * Guo  _et al._ (2022) L. Guo, X. Xu, Y. Lei, L. Wang, P. Yu, and Q. Xu, “Study on the viscoelastic-thixotropic characteristics of waxy crude oil based on stress loading,” Journal of Petroleum Science and Engineering 208, 109159 (2022).
  * Pimenta and Alves (2018) F. Pimenta and M. Alves, “Electro-elastic instabilities in cross-shaped microchannels,” Journal of Non-Newtonian Fluid Mechanics 259, 61–77 (2018).
  * Sadek, Pinho, and Alves (2020) S. H. Sadek, F. T. Pinho, and M. A. Alves, “Electro-elastic flow instabilities of viscoelastic fluids in contraction/expansion micro-geometries,” Journal of Non-Newtonian Fluid Mechanics 283, 104293 (2020).
  * Masliyah and Bhattacharjee (2006) J. H. Masliyah and S. Bhattacharjee,  _Electrokinetic and Colloid Transport Phenomena_ (John Wiley & Sons, 2006).
  * Wang  _et al._ (2015b) G. Wang, D. Niu, F. Xie, Y. Wang, X. Zhao, and G. Ding, “Experimental and numerical investigation of a microchannel heat sink (mchs) with micro-scale ribs and grooves for chip cooling,” Applied Thermal Engineering 85, 61–70 (2015b).
  * Vafai and Zhu (1999) K. Vafai and L. Zhu, “Analysis of two-layered micro-channel heat sink concept in electronic cooling,” International Journal of Heat and Mass Transfer 42, 2287–2297 (1999).
  * Demello (2006) A. J. Demello, “Control and detection of chemical reactions in microfluidic systems,” Nature 442, 394–402 (2006).
  * Alihosseini  _et al._ (2020) Y. Alihosseini, M. Z. Targhi, M. M. Heyhat, and N. Ghorbani, “Effect of a micro heat sink geometric design on thermo-hydraulic performance: A review,” Applied Thermal Engineering 170, 114974 (2020).
  * Doi, Edwards, and Edwards (1988) M. Doi, S. F. Edwards, and S. F. Edwards,  _The theory of polymer dynamics_ , Vol. 73 (oxford university press, 1988).


# Dynamic Traffic Allocation in IEEE 802.11be Multi-link WLANs

Álvaro López-Raventós, and Boris Bellalta All the authors are with the
Wireless Networking (WN) research group at Universitat Pompeu Fabra,
Barcelona, Spain (e-mail: alvaro.lopez, boris.bellalta@upf.edu). This work has
been partially supported by the Spanish Government under grant WINDMAL
PGC2018-099959-B-I00 (MCIU/AEI/FEDER,UE), and Cisco.

###### Abstract

The multi-link operation (MLO) is a key feature of the next IEEE 802.11be
Extremely High Throughput amendment. Through its adoption, it is expected to
enhance users’ experience by improving throughput rates and latency. However,
potential MLO gains are tied to how traffic is distributed across the multiple
radio interfaces. In this paper, we introduce a traffic manager atop MLO, and
evaluate different high-level traffic-to-link allocation policies to
distribute incoming traffic over the set of enabled interfaces. Following a
flow-level approach, we compare both non-dynamic and dynamic traffic balancing
policy types. The results show that the use of a dynamic policy, along with
MLO, allows to significantly reduce the congestion suffered by traffic flows,
enhancing the traffic delivery in all the evaluated scenarios, and in
particular improving the quality of service received by video flows. Moreover,
we show that the adoption of MLO in future Wi-Fi networks improves also the
coexistence with non-MLO networks, which results in performance gains for both
MLO and non-MLO networks.

###### Index Terms:

IEEE 802.11be, multi-link operation, traffic management, dynamic allocation,
WLANs.

##  I Introduction

The multi-link operation (MLO) is a revolutionary feature that is planed to be
part of the IEEE 802.11be Extremely High Throughput (EHT) amendment [1]. By
the use of multiple radio interfaces, MLO-capable devices will be able to send
and receive traffic over different wireless links, allowing devices to
experience higher throughput rates, as well as lower end-to-end latency
delays. To support such implementation, the Task Group ”be” (TGbe) has
proposed several modifications to the standard, being the nodes’ architecture
one of the most significant. In this regard, it is suggested to split common
and link-specific medium access control (MAC) functionalities into two
different levels [2].

With such approach, the TGbe aims to provide nodes with a dynamic, flexible,
and seamless inter-band operation. To that end, a unique MAC instance is
presented to the upper-layers, while each interface is able to maintain an
independent set of channel access parameters [3]. However, proper traffic
balancing over the different interfaces is required to make the most out of
the MLO. To implement such a load balancing, we rely on the existence of a
traffic manager on top of the MLO framework, in order to apply different
traffic management policies to allocate new incoming flows/packets across the
enabled interfaces111We refer to enabled interfaces as those in which at least
a wireless link has been established.. This approach allows to control the
allocation process, ensuring a more balanced usage of the network resources.

Although MLO is gaining relevance at a very fast pace, none of the existing
works have tackled how traffic allocations may be performed. For instance,
existing MLO works relate to feature improvements, as the work in [4], in
which the authors prove that MLO can reduce latency by means of minimizing the
congestion. Similarly, [5] shows experimentally that MLO is able to reduce Wi-
Fi latency in one order of magnitude in certain conditions by just using two
radio interfaces. Additionally, authors in [6] suggest that the use of MLO
per-se may not be sufficient enough to provide the prospected gains without a
coordination between access points (AP) in high density areas. Hence, they
propose a coordination framework to achieve high throughput in those
circumstances. On the other hand, works in [7, 8] focus on maximizing the
medium utilization, while the interference suffered by constrained nodes is
minimized. As shown, none have tackled neither the implementation of a traffic
manager atop MLO, nor considered the performance gains from a flow-level
perspective.

A first evaluation of the capabilities of the proposed traffic manager was
presented in [9]. There, it was shown —as expected— that congestion-aware
policies outperform a blindfolded scheme. Additionally, and more important, it
was shown that allocating the whole traffic of an incoming flow to the
emptiest interface was almost as good, as proportionally distributing the flow
over multiple interfaces. Such finding relies on the fact that using more
interfaces, a traffic flow becomes more vulnerable to suffer a congestion
episode due to the changing spectrum occupancy conditions caused by the
neighboring wireless local area networks (WLANs).

In this letter, we introduce and evaluate a dynamic traffic balancing policy
for the traffic manager, which periodically modifies the traffic-to-link
allocation accordingly to the instantaneous channel occupancy conditions.
Thus, we expect to minimize the negative impact of neighboring WLANs over the
traffic flows by reacting to changes in the spectrum occupancy. The presented
results show that the application of a dynamic policy has a significant impact
on the spectrum usage efficiency, while improving the service received by the
flows. For instance, we observe that video flows are able to keep up to 95%
their performance in most of the scenarios, when the dynamic policy is
applied. Additionally, we showcase that the adoption of MLO in future Wi-Fi
networks eases coexistence issues with non-MLO networks, which performance is
improved up to 40% when surrounded by MLO BSSs.

##  II Policy-based traffic management for MLO-capable WLANs

The multi-interface availability allows to naturally think of a manager in
order to distribute traffic. Following the proposals of the TGbe, this logical
entity should be placed at the upper MAC level, since the interface
assignation is performed once traffic goes through it [10]. Once a
connection222A connection is defined to be a logical link, in which traffic of
a certain application is exchanged between two end hosts. is established
between an AP-STA pair, and traffic streams start to flow, the traffic manager
is in charge to allocate the traffic to the corresponding interfaces. Such
approach allows to not only achieve an efficient use of the network resources,
but better control the capabilities of multi-link devices (MLDs) supporting,
for instance, advanced traffic differentiation, beyond the default MLO’s TID-
to-link mapping functionality [2]. Figure 1 shows an schematic of a MLD
architecture, with a traffic manager representation.

To perform the allocation process, the transmitting MLD gathers the
instantaneous channel occupancy at each interface according to the set of
enabled interfaces at the receiving node. Then, the traffic manager is able to
ensure that the transmitting MLD will not allocate traffic to congested
interfaces, distributing it over all of them proportionally to their
occupancy. At the following, we present the different policies, which can be
classified into non-dynamic and dynamic in regards of their behavior.

Figure 1: Scenario and architecture representation. The high, medium and low
shaded areas represent the operation range for the 6 GHz, 5 GHz and 2.4 GHz
bands, respectively. Colored in red is represented the traffic allocated to
each interface, whereas in gray is represented the channel occupancy.

###  II-A Non-dynamic congestion-aware policies

Under a non-dynamic strategy, each flow maintains the same traffic-to-link
allocation during its lifetime. That is, upon a flow arrival, the channel
occupancy is gathered, and the traffic is distributed either proportionally
over multiple interfaces according to their congestion, or fully into the less
congested one. We define two different non-dynamic policies:

  * •

Single Link Less Congested Interface (SLCI). Upon a flow arrival, pick the
less congested interface, and allocate the new incoming flow to it.

  * •

Multi Link Congestion-aware Load balancing at flow arrivals (MCAA). Upon a
flow arrival, distribute the new incoming flow’s traffic accordingly to the
observed channel occupancy at the AP, considering the enabled interfaces of
the receiving station. Namely, let $\rho_{i}$ the percentage of available
(free) channel airtime at interface $i$. Then, the fraction of the flow’s
traffic allocated to interface $i$ is given by
$\ell_{i\in\mathcal{J}}~{}=~{}\ell\frac{\rho_{i}}{\sum_{\forall
j\in\mathcal{J}}{\rho_{j}}}$, with $\ell$ being the traffic load, and
$\mathcal{J}$ the set of enabled interfaces at the target station. If there
are any other active flows at the AP, their traffic allocation remain the same
as it was.

Due to their straightforward approach, the application of non-dynamic policies
are well-suited for scenarios where the interfaces’ congestion levels remains
almost stationary. Their computational cost is low, as only few calculations
are done at flow arrivals.

###  II-B Dynamic congestion-aware policies

A dynamic strategy is able to periodically adjust the traffic-to-link
allocation in order to follow channel occupancy changes, and so, taking the
most out of the different enabled interfaces. In this regard, a traffic
(re)allocation may be triggered by two different events: a new flow arrival or
a periodic timer, which wakes up every $\delta$ units of time. Under both
events, the channel occupancy is gathered to proportionally (re)distribute the
traffic load of all active flows to any of the enabled interfaces. It is worth
mention that, the dynamic reallocation of traffic is performed by adjusting
the interfaces’ traffic weights (i.e., traffic percentage associated to each
one), which are tracked by the traffic manager at the upper MAC level.
Besides, we consider such reallocation to be instantaneous. We define the
following dynamic policy:

  * •

Multi Link Congestion-aware Load balancing (MCAB). Upon a flow arrival or at
every $\delta$ units of time, collect the channel occupancy values and sort
all flows (including the incoming one) in ascending order, considering the
number of enabled interfaces at the destination station (i.e., first the flows
with less enabled interfaces). In case two or more flows have the same number
of enabled interfaces in the destination station, they are ordered by arrival
time. After, start (re)allocating the flows’ traffic accordingly to the same
procedure as in MCAA.

Through its dynamic implementation, the MCAB minimizes the effect of
neighboring BSSs actions, as they usually result in abrupt changes in the
observed congestion at each link. Therefore, such policy scheme is able to
adjust the traffic allocated to each link, exploiting the different traffic
activity patterns while maximizing the traffic delivery. However, it is
noticeable that the MCAB gain is conditioned to perform multiple operations in
shorts amounts of time, which may be impractical in high density areas, as the
computational requirements to (re)distribute all flows grows with the number
of active users.

##  III System model

###  III-A Scenario

To assess the performance of the different policies, we consider an scenario
with $N$ BSSs, each composed by an AP and $M$ stations as depicted in Figure
1. In every scenario, we place the $\text{BSS}_{\text{A}}$ at the center, and
the other $N-1$ BSSs are distributed uniformly at random over the area of
interest. To consider a random generated scenario as valid, the inter-AP
distance must be equal or higher than 3 m. Otherwise, the scenario is
discarded and a new one is generated. For each BSS, stations are placed within
a distance $d\in[1-5]$ m and an angle $\theta\in[0-2\pi]$ from its serving AP,
both selected uniformly at random.

Figure 2: $\text{AP}_{\text{A}}$’s avg. satisfaction per policy.

###  III-B Node operation

All APs and stations have three wireless interfaces, each one operating at a
different frequency band (i.e., 2.4 GHz, 5 GHz and 6 GHz). For each station,
the set of enabled interfaces includes all the interfaces that can be
effectively used (i.e., the power received from the serving AP is above the
clear channel assessment (CCA) threshold). The modulation and coding scheme
(MCS) used by the serving AP at each interface is selected accordingly to the
signal-to-noise ratio (SNR). All stations are inside the coverage area of its
serving AP for at least the 2.4 GHz band. All APs’ interfaces corresponding to
the same band are configured with the same radio channel.

Unless otherwise stated, all the APs and stations will be considered MLO-
capable, using an asynchronous transmission mode [2]. Besides, except for
$\text{AP}_{\text{A}}$, which will be set either with the SLCI, MCAA or MCAB,
the rest of the APs will implement either the SLCI or MCAA policy schemes,
which will be selected with the same probability. Regarding the MCAB policy,
we set the time between two adaptation periods to be $\delta$ s. In this
paper, $\delta$ is set to 1 s. The MCAB dependency in regards of $\delta$ is
kept out of this article due to space limitations.

###  III-C Traffic considerations

Only downlink traffic is considered. The deployed stations are defined as data
or video depending on the traffic that they will request. Also, only one
connection is considered per station, which is set to be alive during the
whole simulation time. Video traffic is modeled as a single Constant Bit Ratio
(CBR) traffic flow of $\ell_{S}$ Mbps, whereas data traffic behaves following
an ON/OFF Markovian model, where each ON period is treated as a new flow.
Therefore, for data flows, their traffic load is $\ell_{E}$ Mbps during the ON
period, and zero otherwise. Both ON and OFF periods are exponentially
distributed with mean duration T${}_{\text{ON}}$ and T${}_{\text{OFF}}$,
respectively.

TABLE I: Evaluation setup

Parameter | Description
---|---
Carrier frequency | 2.437 GHz/5.230 GHz/6.295 GHz
Channel bandwidth | 20 MHz/40 MHz/80 MHz
AP/STA TX power | 20/15 dBm
Antenna TX/RX gain | 0 dB
CCA threshold | -82 dBm
AP/STA noise figure | 7 dB
Single user spatial streams | 2
MPDU payload size | 1500 bytes
Path loss | Same as [11]
Avg. data flow duration | T${}_{\text{on}}$ = 3 s
Avg. data flow interarrival time | T${}_{\text{off}}$ = 1 s
MCAB adaptation period |  $\delta=$ 1 s
Packet error rate | 10%
Simulation time | 120 s (1 simulation)
Number of simulations | N${}_{\text{s}}$ (variable)

(a) SCLI

(b) MCAA

(c) MCAB

Figure 3: $\text{AP}_{\text{A}}$’s congestion distribution per interface, and
per policy application.

##  IV Performance evaluation

Flow-level simulations are performed using the Neko333The Neko simulation
platform can be found in GitHub at: https://github.com/wn-upf/Neko simulation
platform, which implements the CSMA/CA abstraction presented in [11]. This
abstraction relies on the channel occupancy observed by each AP to calculate
the allocable airtime for each flow, preserving the inherent Wi-Fi ’fair’
share of the spectrum resources. Table I describes the complete set of
parameters.

###  IV-A Long-lasting flows

Here, we analyze the effects between the dynamic and non-dynamic traffic-to-
link allocation policies in regards of video flows (i.e., flows with constant
traffic requirements, and long lifetimes). To do so, we generate
N${}_{\text{s}}$ = 500 scenarios, placing $N$ = 5 BSSs over a 20x20
$\text{m}^{2}$ area. At the central BSS (i.e., $\text{BSS}_{\text{A}}$), we
configure a unique video station with $\ell_{S}\sim\textit{U}[20,25]$ Mbps,
whereas the remaining BSSs will have $M~{}\sim~{}\textit{U}[5,15]$ stations
requesting data traffic with $\ell_{E}\sim\textit{U}[1,3]$ Mbps.

Figure 2 plots the cumulative distribution function (CDF) of the average
satisfaction ($\overline{s}$) experienced by the traffic flow served by
$\text{AP}_{\text{A}}$, per policy type. We define $\overline{s}$ as the sum
of the satisfaction of each station divided by the total number of stations in
the BSS. Also, we refer to the satisfaction of a flow as the ratio between the
allocated airtime by the AP during the flow lifetime, and the total amount of
airtime required. As expected, the MCAB outperforms both non-dynamic policies.
For instance, it is able to increase by 17% and 6% the $\overline{s}$ in
regards of the MCAA and SLCI, respectively, for the 5% worst case scenarios.
Besides, we observe that the MCAB provides satisfaction values up to 95% in
more than the 90% of the scenarios. This performance gains are provided by the
periodic evaluation of the channel occupancy, which allows to leverage the
emptiest interfaces, and so, making a better use of the available resources.

Further details are presented in Figure 3. There, we observe in detail the
congestion evolution for each $\text{AP}_{\text{A}}$’s interface, during the
first 30 s of a single simulation. Figure 3(a) and Figure 3(b) expose the main
drawbacks of SLCI and MCAA, respectively, as the temporal evolution of the
congestion reveals how unbalanced the interfaces are. First, the SLCI
overloads the 6 GHz link by placing the whole video flow in it, while there is
still room for some traffic in the other interfaces. On the contrary, the MCAA
does not leverage the fact of having empty space at the 6 GHz interface, which
makes the proportional parts of the flow allocated to the 2.4 GHz and 5 GHz
links to suffer from congestion. Such inefficient operation from the non-
dynamic policies is shown in Figure 3(c) to be overcomed by the MCAB, as it
reveals a more balanced use of the interfaces. However, we also observe that
most of the time the congestion values for the 6 GHz interface are lower than
for the other two. Such effect is related to the unequal number of neighboring
nodes detected at each band. As a result, even if most of the traffic is
allocated to this interface, it still manages to provide traffic with fewer
congestion episodes.

###  IV-B Coexistence with legacy networks

Wi-Fi’s constant evolution makes newer devices, which implement up-to-date
specifications, to coexist with others with less capabilities. As a result,
last generation devices may decay in performance due to its coexistence with
legacy ones. To assess if Multi-Band Single Link (MB-SL) BSSs affects the
performance of MLO ones, we analyze four different cases in which we increment
the fraction of MLO BSSs around the central one from 0, to 0.3, 0.7, and 1. To
do so, we generate N${}_{\text{s}}$ = 200 scenarios, placing $N$ = 11 BSSs. At
the central BSS (i.e.,$\text{BSS}_{\text{A}}$), we configure a single video
station with $\ell_{S}\sim\textit{U}[20,25]$ Mbps, whereas the remaining BSSs
will have $M~{}\sim~{}\textit{U}[5,15]$ stations requesting background data
traffic of $\ell_{E}\sim\textit{U}[1,3]$ Mbps. It is worth mention that, MB-SL
APs are equipped with 3 interfaces, considering the associated stations are
distributed across all three bands uniformly at random.

Figures 4(a), 4(b), and 4(c) show the CDF of the $\overline{s}$ for each
policy. Regardless of the policy used, the central $\text{BSS}_{\text{A}}$
experiences a negative trend when it is surrounded by more legacy BSSs, as the
results show lower satisfaction values when so. Although the MCAA and MCAB
experience low gains when increasing the number of MLO BSSs, the SLCI presents
a 17% improvement for the 25th percentile, when comparing the performance
results between the best and the worst (i.e., all MLO and all MB-SL,
respectively) cases. Such an improvement is caused by the higher link
availability from the neighboring BSSs to allocate traffic, which also avoid
to overload the interfaces by the use of congestion-aware policies. On the
other hand, comparing policies, we find that the MCAB outperforms the other
ones. Specially, we observe that the MCAB tends to perform better in the cases
with more MB-SL neighboring BSSs. In those situations, the $\overline{s}$ when
using MCAB is above 94% in half of the scenarios, whereas below 85% when using
the SLCI and MCAA. Although the optimal solution will be to avoid coexistence
issues by not having any legacy BSSs, the periodic channel evaluation of the
MCAB adds the required flexibility to minimize negative coexistence effects.

At last, Figure 4(d) shows the avg. satisfaction when $\text{BSS}_{\text{A}}$
is set as a legacy MB-SL with the aim to observe if the presence of MLO
devices will benefit legacy ones. As previously, we incremented the fraction
of MLO BSSs from 0, to 0.3, 0.7, and 1. Figure 4(a) reveals that legacy MB-SL
BSSs can benefit from the fact of having MLO BSSs around them, as the
improvement is highly noticeable. In fact, we observe that between the best
and worst cases the satisfaction increases by a 40% for half of the scenarios
evaluated. Then, from the perspective of a legacy BSS, the adoption of the MLO
by other BSSs represents also a performance improvement.

(a) SCLI

(b) MCAA

(c) MCAB

(d) MB-SL

Figure 4: Coexistence performance per policy type, and MB-SL.

##  V Conclusions and future work

In this letter, we assessed the implementation of a traffic manager to perform
traffic allocation on top of MLO-capable BSSs. We evaluated three policy
schemes under different conditions to shed some light on the potential
performance gains of dynamic policies in comparison to non-dynamic ones. Under
a wide variety of scenarios, our results shown that dynamic policies should be
applied in presence of long-lasting flows, since their frequent adaptation to
the instantaneous congestion conditions allows to minimize the effect of the
neighboring AP MLDs’ actions. By the nature of video flows, it has been found
also that the MCAB is able to maximize the traffic delivery by keeping a
satisfaction ratio of 95% for most of the evaluated scenarios. Under
coexistence conditions, we observe that an excessive number of legacy BSSs may
harm the performance of MLO ones. However, we found that the MCAB is able to
reduce the negative impact of legacy BSSs by almost 10% compared to MCAA, as
it is able to react to changes in the channel occupancy of the different
interfaces.

Regarding future research, we plan to extend current traffic management
policies to also support link aggregation at channel access. Regarding
improving QoS provisioning in next generation Wi-Fi networks, traffic
differentiation policies should be further investigated in presence of
heterogeneous stations, providing solutions that go beyond the default TID-to-
link mapping functionality. Finally, we also consider the redesign of the
traffic management module as part of an end-to-end Software Defined Networking
solution, closely working with an external controller in charge of multiple
APs to properly allocate traffic flows to interfaces.

## References

  * [1] IEEE P802.11be/D1.0 Draft Standard for Information Technology. Telecommunications and Information Exchange between Systems Local and Metropolitan Area Networks. Part 11. Amendment 8: Enhancements for Extremely High Throughput (EHT), May 2021.
  * [2] Álvaro López-Raventós and Boris Bellalta.  Multi-link Operation in IEEE 802.11 be WLANs.  arXiv preprint arXiv:2201.07499, 2022.
  * [3] Joseph Levy and Xiaofei Wang.  802.11be Architecture/Association Discussion.  IEEE 802.11 Documents. 2020. [Online]. Available: https://mentor.ieee.org/802.11/documents?is_dcn=1122&is_group=00be.
  * [4] Gaurang Naik, Dennis Ogbe, and Jung-Min Jerry Park.  Can Wi-Fi 7 Support Real-Time Applications? On the Impact of Multi Link Aggregation on Latency.  In ICC 2021-IEEE International Conference on Communications, pages 1–6. IEEE, 2021.
  * [5] Marc Carrascosa, Giovanni Geraci, Edward Knightly, and Boris Bellalta.  An experimental study of latency for ieee 802.11 be multi-link operation.  arXiv preprint arXiv:2111.09281, 2021.
  * [6] Mao Yang, Bo Li, Zhongjiang Yan, and Yuan Yan.  AP Coordination and Full-duplex Enabled Multi-band Operation for the Next Generation WLAN: IEEE 802.11 be (eht).  In 2019 11th International Conference on Wireless Communications and Signal Processing (WCSP), pages 1–7.
  * [7] Sharan Naribole, Wook Bong Lee, Srinivas Kandala, and Ashok Ranganath.  Simultaneous Transmit-Receive Multi-Channel Operation in Next Generation WLANs.  In 2020 IEEE Wireless Communications and Networking Conference (WCNC), pages 1–8. IEEE.
  * [8] Sharan Naribole, Srinivas Kandala, Wook Bong Lee, and Ashok Ranganath.  Simultaneous Multi-Channel Downlink Operation in Next Generation WLANs.  In GLOBECOM 2020-2020 IEEE Global Communications Conference, pages 1–7. IEEE, 2020.
  * [9] Álvaro López-Raventós and Boris Bellalta.  IEEE 802.11be Multi-Link Operation: When the Best Could Be to Use Only a Single Interface.  In 2021 19th Mediterranean Communication and Computer Networking Conference (MedComNet), pages 1–7.
  * [10] Mark Hamilton and Joseph Levy.  Mld architecture part 2.  IEEE 802.11 Documents. 2021. [Online]. Available: https://mentor.ieee.org/802.11/documents?is_dcn=1111&is_group=00be.
  * [11] Álvaro López-Raventós and Boris Bellalta.  Concurrent Decentralized Channel Allocation and Access Point Selection using Multi-Armed Bandits in multi BSS WLANs.  Computer Networks, 180, 2020.