# DiffPerf: Towards Performance Differentiation and Optimization with SDN
Implementation

Walid Aljoby†, Xin Wang†, Dinil Mon Divakaran∗, Tom Z. J. Fu§, Richard T. B.
Ma†
† School of Computing, National University of Singapore
∗ Trustwave, Singapore § Bigo Technology Pte Ltd, Singapore
{algobi, xin.wang<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Continuing the current trend, Internet traffic is expected to grow
significantly over the coming years, with video traffic consuming the biggest
share. On the one hand, this growth poses challenges to access providers
(APs), who have to upgrade their infrastructure to meet the growing traffic
demands as well as find new ways to monetize their network resources. On the
other hand, despite numerous optimizations of the underlying transport
protocol, a user’s utilization of network bandwidth and is thus the user’s
perceived quality still being largely affected by network latency and buffer
size. To address both concerns, we propose DiffPerf, a class-based
differentiation framework, that, at a macroscopic level dynamically allocates
bandwidth to service classes pre-defined by the APs, and at a microscopic
level statistically differentiates and isolates user flows to help them
achieve better performance. We implement DiffPerf on OpenDaylight SDN
controller and programmable Barefoot Tofino switch and evaluate it from an
application perspective for MPEG-DASH video streaming. Our evaluations
demonstrate the practicality and flexibility that DiffPerf provides APs with
capabilities through which a spectrum of qualities are provisioned at multiple
classes. Meanwhile, it assists in achieving better fairness and improving
overall user’s perceived quality within the same class.

##  I Introduction

Today’s Internet is dominated by content traffic, especially video streams.
According to Cisco Annual Internet Report [1], video will make up 82% of the
total downstream Internet traffic by 2022. In today’s home, Internet video
drives our work and life, particularly with COVID-19 pandemic [2], meanwhile
video applications continue to be of a significant demand for the bandwidth in
the future [1]. To accommodate high traffic, content providers (CPs) have been
deploying wide-area infrastructures to bring content closer to users, e.g.,
Netflix uses third-party content delivery networks such as Akamai and
Limelight, and builds its own [3]. However, as end-users rely on last-mile
access providers (APs) for accessing the Internet, APs’ bandwidth capacity
still limit user throughput due to network congestion [4]. For example, the
average throughput of Netflix users behind Comcast [5], the largest U.S.
broadband provider, degraded 25% from over 2 Mbps in Oct 2013 to 1.5 Mbps in
Jan 2014.

To sustain traffic growth, APs need to upgrade network infrastructures and
expand capacities; however, their incentives depend on the business model and
the corresponding mechanism used to monetize bottleneck bandwidth, which is
crucial to the viability of the current Internet model in the future. A
general approach used by APs is to differentiate services and prices, e.g.,
APs provide premium peering [6] options for CPs to choose and multiple data
plans for end-users with different data usage to choose. However, the former
can only be implemented with large CPs via peering agreements, while the
latter does not guarantee the performance of end-users in any sense. The
bandwidth allocation is typically a function of the application endpoints, and
is traditionally embodied as part of transport layer’s congestion control
mechanism. TCP CUBIC and BBR are the most popular protocols control the
majority of Internet traffic. However, both of them strive for efficient
utilization of the bandwidth, while being unaware of the negatively biased
user’s Quality of Experience (QoE) affected by Round-Trip Times (RTT) and
network buffer size. Consequently, there exists a fundamental mismatch between
the differentiated services and the underlying resource allocation that
differentiates for predictable performance.

To resolve this mismatch, we consider a class-based differentiation approach,
under which CPs and users can choose a service class (SC) to join. We propose
DiffPerf, a dynamic performance differentiation framework, at APs vantage
point to manage their bottleneck bandwidth resources in a principled and
practical manners. From a macroscopic perspective, DiffPerf dynamically
allocates bandwidth to each SC according to the changing number of active
flows in each SC, by maximizing the weighted $\alpha$-fair utilities, which
enables APs to trade-off fairness. Nevertheless, as the users in the same
service class might not perceive a fair quality due to the consequences of the
complex interaction between the transport protocol and the inherent network
conditions such as heterogeneous RTTs and buffer sizes, as shown in our
experimental explorations and known by conventional wisdom [7]. Thus, at a
microscopic level, DiffPerf uses a new performance-aware mechanism, called
($\beta,\gamma$)-fairness to further optimize and make more fine-grained
bandwidth allocation within each SC, so as to more efficiently utilize the
aggregate capacity and achieve fairer performance for flows. Our main
contributions are as follows:

  1. 1\.

We derive the closed-form bandwidth allocation solution and show that this
solution achieves guaranteed performance differentiation in terms of
controllable ratios of the average per-flow throughput across the different
SCs.

  2. 2\.

Within each SC, we present ($\beta,\gamma$)-fairness and a neat statistical
method to differentiate and isolate flows automatically based on their
achieved throughput, to mitigate the bias brought by the TCP protocol due to
its interaction with network latency (i.e., RTT) and buffer size.

  3. 3\.

By leveraging SDN capabilities, we develop a native OpenDaylight (ODL) control
plane application that dynamically manages network resources, including
tracking flows, inquiring flow statistics and allocating bandwidth capacity.
Furthermore, to measure the impact of network buffer sizes, we also implement
DiffPerf on programmable Barefoot Tofino switch which allows flexible buffer
sizing and enables fine-grained and flexible line-rate telemetry.

  4. 4\.

We carry out comprehensive evaluations of DiffPerf from an application
perspective for DASH video streaming, as a mainstream accounts for the
majority of Internet video traffic.

We believe that DiffPerf demonstrates a new avenue for APs to differentiate
and optimize the performance of video flows and corresponding perceived user
QoE so as to better monetize their bottleneck network resources. This will
further incentivize APs to deploy more bandwidth capacity to accommodate the
growth of Internet content traffic.

##  II The DiffPerf Framework

In this section, we present the DiffPerf framework in a top-down manner. We
first describe how DiffPerf allocates bandwidth capacity among the SCs, based
on an optimization approach. We will derive closed-form allocation solution
and show its feature of guaranteed performance differentiation. We then
discuss the performance issues due to the consequences of TCP congestion
control mechanism that responds to the heterogeneity of flows’ RTTs and
network’s buffer sizes. To solve this problem, we show how DiffPerf classifies
flows and optimizes bandwidth allocation within each SC.

###  II-A Inter-Class Bandwidth Allocation

We consider an access provider that offers a set $\mathcal{S}$ of service
classes over a bottleneck link with capacity $C$. We denote the set of active
flows in any service class $s\in\mathcal{S}$ by $\mathcal{F}_{s}$ and the
cardinality of $\mathcal{F}_{s}$, i.e., the number of flows in class $s$, by
$n_{s}$. To differentiate the performance for flows in different service
classes, the access provider needs to allocate appropriate amount of bandwidth
to each service class. To accomplish this in a principled manner, we formulate
the bandwidth allocation as an optimization of the allocation
$\mathbf{X}=(X_{s}:s\in\mathcal{S})$ that solves a general utility
maximization problem as follows.

$\displaystyle\underset{\mathbf{X}}{\text{max}}\quad\sum_{s\in\mathcal{S}}n_{s}U_{s}\left(\frac{X_{s}}{n_{s}}\right)$
(1) $\displaystyle\text{s.t.}\quad\ \
\underset{s\in\mathcal{S}}{\sum}X_{s}\leq C\ \ \text{and}\ \ X_{s}\geq 0,\
\forall s\in\mathcal{S}.$ (2)

Under the link capacity constraint (2), the above mathematical program tries
to maximize the aggregate utility over all service classes, where for each
service class $s$, it counts the number of flows $n_{s}$ multiplied by the
per-flow utility $U_{s}(X_{s}/n_{s})$ over the average capacity $X_{s}/n_{s}$
allocated to each flow. In particular, we adopt and generalize the well-known
weighted $\alpha$ fairness family of utility functions [8] as follows. In this
family of utility functions, each service class $s$ will be assigned a weight
$w_{s}$ that indicates the relative importance of the service class, resulting
in differentiated per-flow bandwidth allocation across the service classes. By
controlling the parameter $\alpha$, the access provider can express different
preferences over various notions of fairness. When $\alpha$ approach $0$, the
utility tends to be measured purely by the allocated bandwidth; when $\alpha$
approaches $+\infty$, the solution converges to the weighted max-min fair
allocation among the flows. In particular, a trade-off of a weighted
proportional fair solution can be obtained by solving the optimization problem
when $\alpha$ is set to be $1$. Thus, besides the differentiation factor
$w_{s}$ among service classes, the service operator can choose the value of
$\alpha$ to tradeoff fairness.

######  Theorem 1.

If an allocation $\mathbf{X}$ maximizes the aggregate utility over all service
classes, it must satisfy

$X_{s}=\frac{n_{s}\sqrt[\alpha]{w_{s}}}{{\underset{s^{\prime}\in\mathcal{S}}{\sum}n_{s^{\prime}}\sqrt[\alpha]{w_{s^{\prime}}}}}\
C,\quad\forall s\in\mathcal{S}.$ (3)

Theorem 1 provides the closed-form solution of the utility maximization
problem. Based on the optimal allocation solution in Equation (3), we derive
the ratio of the average per-flow capacities of any two service classes
$s,s^{\prime}\in\mathcal{S}$ as

$\left(\frac{X_{s}}{n_{s}}\right):\left(\frac{X_{s^{\prime}}}{n_{s^{\prime}}}\right)=\sqrt[\alpha]{\frac{w_{s}}{w_{s^{\prime}}}}.$
(4)

This result implies that performance differentiation is achieved by enforcing
a fixed ratio for the per-flow bandwidth capacity across SCs, which is
controlled by the weights $w_{s},w_{s^{\prime}}$ and the fairness parameter
$\alpha$. Equation (4) explicitly shows that the optimal solution effectively
allocates a higher average per-flow capacity in the service class that has a
larger weight, which is desirable and expected for the better service class.
In particular, we also see that when $\alpha$ is set to be $1$, the weighted
proportional fair allocation leads an average per-flow allocation that are
proportional to the weights of the SCs.

###  II-B Intra-Class Bandwidth Allocation

Motivation: Given $X_{s}$ amount of bandwidth capacity allocated to the
$n_{s}$ flows in SC $s$, each flow $f\in\mathcal{F}_{s}$ is expected to
achieve an average throughput of $X_{s}/n_{s}$. However, the actual throughput
achieved, denoted by $x_{f}$, might be significantly less than the mean. This
can adversely affect the QoE that the corresponding user perceives. At the
last-mile bottleneck, parameters such as RTT, TCP congestion control algorithm
(e.g., CUBIC v/s BBR), and buffer size affect the performance of flows [9, 10,
11]. The heterogeneity of RTTs experienced by the flows as well as the
interaction of the TCP-based congestion control mechanisms that respond to the
RTTs and network buffer size differently, lead to multiple competing flows
achieving different throughput. We analyzed the performance of 100 competing
DASH flows on a testbed, where all flows run TCP BBR and share a bottleneck
link connecting to a DASH server. The bottleneck link capacity is set to
120Mbps, and 30% of the flows experience relatively longer RTTs than the rest.
We run the experiments by changing one of the key parameters, i.e. the network
buffer size. The experiment results show that the average stalling time of
DASH flows at 10MB network buffer size, is 35% higher than that of DASH flows
when the network buffer size is 1MB. However, by “isolating” flows that
perceived dissimilar QoE at the last-mile bottleneck link, we observed that
average stalling time of DASH flows is reduced by 50% and 25% at the buffer
sizes of 1MB and 10MB, respectively, thereby improving the overall QoE
significantly.

Motivated by this observation, we propose a practically scalable solution to
classifying similar flows into sub-groups and isolating them into separate
sub-classes by allocating appropriate amount of bandwidth to them within each
SC. Next, we describe 1) a flexible statistical method that DiffPerf uses to
classify flows within a SC, and 2) the intra-class bandwidth allocation used
by DiffPerf for sub-group isolation.

####  II-B1 Flow Classification and Isolation

By relying on QoE as a similarity metric to classify the flows, clearly this
choice requires an explicit feedback via the receiver to the AP vantage point,
which is difficult to afford in practice. We therefore want to leverage SDN
functionalities to find other metrics to use at the vantage point. The first
metric that comes to mind is RTT. However, the use of real-time RTT samples
could not be taken solely as indicators of performance issues without other
information such as underlying congestion control mechanism, buffer size [9],
and packet route security. Even if we make assumptions of the availability of
these information, measuring flow RTT at the APs is unreliable. Measuring RTT
at the SDN control plane inflates a variable and high RTT based on our
measurements in ODL control plane, while measuring it in the SDN data plane
[12] may not scale well due to the memory space constraints. Instead, we
emphasize that throughput of TCP flows is the appropriate and robust metric
that indicates the collective impact of the interaction of network parameters
to the user-perceived performance. Next we show how to utilize the throughput
measure as a proxy to determining whether flows are similar to each other and
to identify effectively which flows are affected.

Because the number of groups and the number of flows for each group may change
and are not known in real scenarios, we adopt general statistical metrics for
classification. Given the achieved throughput $x_{f}$ of the flows
$f\in\mathcal{F}_{s}$ in any SC $s\in\mathcal{S}$, the mean and standard
deviation of the flows’ throughput are defined as
$\bar{x}_{s}=\frac{1}{n_{s}}\underset{f\in\mathcal{F}_{s}}{\sum}x_{f}\quad\text{and}\quad\sigma_{s}=\sqrt{\sum_{f\in\mathcal{F}_{s}}\frac{(x_{f}-\bar{x}_{s})^{2}}{n_{s}}}$.
Because the achieved throughput $x_{f}$ of each flow depends on the number
$n_{s}$ of competing flows and their characteristics, buffer size, and the
allocated capacity $X_{s}$ that ultimately determines the network congestion
imposed on the SC, instead of using absolute throughput thresholds to classify
flows, we adopt the following statistical metric that orders and measures the
relative throughput values among all flows in the same SC.

######  Definition 1.

Given the mean $\bar{x}_{s}$ and standard deviation $\sigma_{s}$, the standard
score of a flow $f$’s throughput is defined by
$z_{f}=(x_{f}-\bar{x}_{s})/\sigma_{s}.$

When a flow’s throughput is above (or below) the mean, its standard score or
$z$-score is positive (or negative, respectively). This $z$-score captures the
signed fractional number of standard deviations by which it is above the mean
value.

Without loss of generality, we divide a set $\mathcal{F}_{s}$ of flows into
two sub-classes: lower sub-class $\mathcal{F}_{s}^{L}$ and upper sub-class
$\mathcal{F}_{s}^{H}$, based on each flow’s $z$-score compared with a pre-
defined threshold $\beta$, where
$\mathcal{F}_{s}^{L}(\beta)=\\{f\in\mathcal{F}_{s}:z_{f}<\beta\\}\quad\text{and}\quad\mathcal{F}_{s}^{H}(\beta)=\mathcal{F}_{s}\backslash\mathcal{F}_{s}^{L}(\beta).$
The set $\mathcal{F}_{s}^{L}$ contains the flows that achieved the lowest
throughput values (i.e., the negatively affected flows). Thus, our goal is to
identify them so that we isolate and allocate appropriate amount of bandwidth
to them accordingly. We use a non-positive value of $\beta$ to capture flows
whose throughput are $|\beta|$ deviations lower than the achieved average
$\bar{x}_{f}$. Because the set $\mathcal{F}_{s}^{L}$ grows monotonically with
the parameter $\beta$, i.e.,
$\mathcal{F}_{s}^{L}(\beta_{1})\subseteq\mathcal{F}_{s}^{L}(\beta_{2})\
\forall\beta_{1}<\beta_{2}$, a smaller value of $\beta$ makes a more
conservative decision on the lowest throughput flows, avoiding mis-
classifications. We will further study how the values of $\beta$ affect the
performance of flows in a later section via experimental evaluations.

####  II-B2 Bandwidth Allocation Model

After classifying flows in each SC into two sub-groups, we isolate them into
two sub-classes and determine how much bandwidth $X_{s}^{L}$ and $X_{s}^{H}$
to allocate for each sub-class. To fully utilize bandwidth capacity, our
solution needs to satisfy $X_{s}^{L}+X_{s}^{H}=X_{s}$.

The throughput of some flows might be naturally low and might not be able to
achieve the targeted throughput $X_{s}/n_{s}$ even allocated that amount of
capacity. As a result, enforcing the per-flow allocation of $X_{s}/n_{s}$ will
result in resource wastage. The key question to answer is how much per-flow
capacity we should allocate to the flows $\mathcal{F}_{s}^{L}$, whose innate
throughputs are less than what is needed to achieve the average throughput
$\bar{x}_{s}$ or to utilize the per-flow allocated capacity $X_{s}/n_{s}$ in
theory. Since these flows might not be able to achieve the average throughput,
the per-flow allocation should be no higher than $X_{s}/n_{s}$. On the other
hand, by isolating negatively affected flows from high-throughput flows (i.e.,
the flows $\mathcal{F}_{s}^{H}$ that cause the performance issues of flows
$\mathcal{F}_{s}^{L}$), we expect them to achieve higher throughput than what
are being achieved; and therefore, we should allocate more capacity for the
set $\mathcal{F}_{s}^{L}$ of flows than their aggregate achieved throughput.
To this end, we allocate the average amount of bandwidth capacity for the per
flow of set $\mathcal{F}_{s}^{L}$ as

$\displaystyle\frac{X_{s}^{L}(\beta,\gamma)}{|\mathcal{F}_{s}^{L}(\beta)|}=\gamma\frac{\sum_{f\in\mathcal{F}_{s}^{-}}x_{f}}{|\mathcal{F}_{s}^{-}|}+(1-\gamma)\frac{X_{s}}{n_{s}},$
(5)

where we define the set of flows whose throughput are below the mean
$\bar{x}_{s}$ by
$\mathcal{F}_{s}^{-}\triangleq\\{f\in\mathcal{F}_{s}:x_{f}<\bar{x}_{s}\\}$ and
introduce a parameter $\gamma\in[0,1]$ to control the allocated capacity
flexibly. In particular, for one extreme of $\gamma=1$, the solution allocates
the average throughput of the set $\mathcal{F}_{s}^{-}$ of flows as the per-
flow capacity for the lower sub-class $\mathcal{F}_{s}^{L}(\beta)$, which must
be lower than the average throughput $\bar{x}_{s}$ and the average capacity
$X_{s}/n_{s}$ of all flows. In this case, the per-flow capacity allocated for
the lower sub-class $\mathcal{F}_{s}^{L}$ is lower than that allocated for the
upper sub-class $\mathcal{F}_{s}^{H}$, under which resource wastage is reduced
and resource is utilized more efficiently. For the other extreme of
$\gamma=0$, the solution simply isolates the two sub-classes and equally
allocates an average capacity $X_{s}/n_{s}$ as the per-flow capacity for both
upper and lower sub-classes, under which per-flow fairness is enforced
regardless of how efficiently the resource is utilized. Thus, by choosing the
value of $\gamma$ between $0$ and $1$, we can make a trade-off between
resource fairness and utilization. However, this depends on the interaction of
TCP algorithm with network buffer size. As opposed to the shallow buffer, the
deep buffer allows low-throughput TCP flows (especially those negatively
affected due to heterogeneity of RTTs) to stabilize their transfer. Thus, in
the vantage point of deep buffer, if the low-throughput flows were crowded out
by others, then they can perform better if $\gamma=0$. However, this is not
the case in shallow buffer that does not allow negatively affected flows to
ramp up quickly and perhaps this even leads to lower utilization.

By Eq.(5), we also have the next theorem showing 1) lower bounds of per-flow
capacities re-allocated to the lower and upper sub-classes
$\mathcal{F}_{s}^{L}$ and $\mathcal{F}_{s}^{H}$; and 2) the monotonicity of
the average throughput of the flows within $\mathcal{F}_{s}^{L}$ and the
average per-flow capacity re-allocated to the $\mathcal{F}_{s}^{H}$ on the
parameter $\beta$.

######  Theorem 2.

Given any fixed parameter $\gamma$, for any service class $s\in\mathcal{S}$,
1) the average achieved throughput of the flows within the lower sub-class
$\mathcal{F}^{L}_{s}$ is non-decreasing in $\beta$ and always no higher than
the average per-flow capacity re-allocated to $\mathcal{F}^{L}_{s}$; 2) the
average per-flow capacity re-allocated to the upper sub-class
$\mathcal{F}^{H}_{s}$ is non-decreasing in $\beta$ and always no lower than
$X_{s}/n_{s}$.

Theorem 2 states that as the parameter $\beta$ increases, the average
throughput of the flows $\mathcal{F}_{s}^{L}$ of the lower sub-class would
also increase because more high-throughput flows would be classified into
$\mathcal{F}_{s}^{L}$. It also tells that this achieved average throughput
must be no higher than the the per-flow capacity re-allocated to them in
$\mathcal{F}_{s}^{L}$. This property guarantees our design objective of
allocating more capacity for the flows in the lower sub-class than their
aggregate achieved throughput. Theorem 2 also states that as $\beta$
increases, flows within the upper sub-class $\mathcal{F}_{s}^{H}$ would be re-
allocated more per-flow bandwidth capacity although fewer flows would be
classified into the sub-class. Thus, service operators can choose the value of
$\beta$ to control the scales of the sub-classes and both $\beta$ and $\gamma$
to control the bandwidth capacity allocated to the flows of the two sub-
classes, which we refer to it as ($\beta$,$\gamma$)-fairness.

Before we close this section, we would like to emphasize that although
DiffPerf classifies the flows in each SC into two sub-groups for simplicity,
its statistical method of classification and the corresponding bandwidth
allocation can be applied in a top-down recursive manner to further split any
sub-group for a more fine-grained optimization.

##  III Implementation

###  III-A DiffPerf Prototype on OpenDaylight with OpenFlow

We implement DiffPerf as an application on the popular industry-grade open-
source SDN platform—the OpenDaylight (ODL) controller. We particularly develop
a native MD-SAL (Model-Driven Service Adaptation Layer) application on ODL
which comprises use of different technologies such as OSGI, Karaf, YANG,
blueprint container, and messaging patterns as RPC, publish-subscribe, and
data store accesses [13]. We skip implementation details for the sake of
brevity.

Figure 1: DiffPerf implementation

Figure 1 depicts the implementation structure of DiffPerf on ODL. There are
four main modules: Flow Processor, Bandwidth Optimizer, Bandwidth Enforcer and
Stats Collector and are interconnected as shown in the figure; we briefly
describe them below.

####  III-A1 Flow Processor

The Flow Processor module on the ODL performs two primary functions. First, it
assigns user-specified service classes to newly joining flows in the network.
We use the YANG modeling language [14] to define the service classes. Second,
the module carries out regular flow maintenance; i.e., the flow processor
inserts new flows into the data store, determines the pre-defined service
class and assigns the corresponding weight to new flows, removes inactive or
completed flows, etc.

####  III-A2 Statistics Collector

DiffPerf performs in-network performance optimization. For DiffPerf to work,
we need to estimate throughput of each active flow. Let $x_{f}{(t)}$ denote
the average throughput of a flow $f$ until time $t$. By measuring the
instantaneous throughput $\tilde{x}_{f}$ of flow $f$ during the past immediate
time period $\Delta_{t}$, the average throughput for the next time period
$\Delta_{t}$ is updated as follows:
$x_{f}{(t+\Delta_{t})}\leftarrow\delta\times
x_{f}{(t)}+(1-\delta)\times\tilde{x}_{f}.$ where $\delta\in[0,1]$, is a
weight. Having measured the average throughput of the active flows, we use
these estimates to group flows into sub-classes so that flows with similar
achieved throughput fall into the same sub-class.

To obtain real-time estimates of the throughput of each active flow as well as
link bandwidth, we implement a Stat. Collector module on ODL. This module
registers per-flow rules to pull out measurement information using event-based
handlers from the operational data store in ODL. The data store in turn uses
the OpenFlow plugin (as indicated in Figure 1) to request the switches to
report flow measurements; The per-flow measures of interest are packet counts,
byte counts and duration.

####  III-A3 Bandwidth Optimizer

The core part of DiffPerf is the Bandwidth Optmitizer module, which is
responsible for inter- and intra-class bandwidth optimization described in
Section II. The optimizer runs every $\Delta_{t}$ interval, getting input from
two modules described above - Flow Processor and Stat. Collector (see Figure
1). While the former provides mapping of flows to user-specified service
classes, the latter provides real-time measurements on the active flows in the
switch. Given the input information, the inter- and intra-class optimizers are
executed; the output of optimization are: (i) the portion of bandwidth
allocated to each service class (SC), and (ii) the portion of bandwidth for
each sub-class within every service class.

####  III-A4 Bandwidth Enforcer

To materialize bandwidth allocation, each sub-class should use its designated
bandwidth in an isolated manner. A naive approach to implementing this is to
leverage multi-queues at the switch egress port so that each sub-class maps
into an isolated queue. However, there are two practical challenges. First, in
commodity switches the number of queues at egress port is usually limited to a
small number [15][16], meaning that the number of available queues could be
less than the number flow sub-classes. Second, current OpenFlow switches do
not expose APIs to update the weight of the queues dynamically. Without this
capability (of dynamically changing queue weights), the bandwidth allocated to
queues cannot be changed as and when required.

To overcome both limitations, we leverage the metering feature available in
OpenFlow switches. Instead of defining queues and updating their bandwidth at
egress port, we develop a Bandwidth Enforcer module that essentially does
enforcement at the ingress side of the switch. That is, multiple meters
corresponding to the number of sub-classes are defined; and based on the
output of the Bandwidth Optimizer, flow rate of each sub-class is attached to
a specific meter dynamically. The Bandwidth Enforcer uses the OpenFlow plugins
to encapsulate the allocated bandwidth into OpenFlow messages and install them
on to the switch(es).

###  III-B DiffPerf Prototype with Programmable Data Plane

Next, we implement another prototype of DiffPerf on a lightweight C controller
that is connected to Barefoot Tofino programmable switch [17] which enables
flexible buffer sizing and fine-grained line-rate telemetry. We particularly
implement statistics building block in the data plane to track number of bytes
transmitted by the active flows. Additionally, we re-implement Bandwidth
Enforncer and Statistics Collector modules in the control plane. We leverage
the Tofino switch exposed APIs to update the weight of the queues dynamically
and configure their sizes by the control plane. The remaining modules are kept
the same with minor modifications.

##  IV Experimental Evaluation

We evaluate DiffPerf by carrying out experiments on a realistic testbed. We
describe the details below.

###  IV-A Testbed setup

OpenFlow Brocade switch experiments: We set up a testbed for video streaming
between a DASH client (i.e., video player) called dash.js and DASH server over
an SDN network; Our testbed consists of 12 servers, 10 of which are used to
host DASH clients and one each for hosting DASH server and ODL controller. The
10 servers running DASH clients are connected to the DASH server such that
they compete (for video segments) at a downstream bottleneck link from a SDN-
enabled Brocade ICX-6610 24-port physical switch. We evaluated DiffPerf in
three different scenarios. In Scenario 1 (Section IV-C1) and Scenario 2
(Section IV-C2), each physical server hosts up to $4$ DASH clients, each
client runs in a VM, and all clients are connected to the DASH server over a
50 Mbps downstream bottleneck link. For Scenario 3 (Section IV-C3), we scale
up the number of DASH clients—each physical server hosts $15$ DASH clients,
all run as docker containers and connected to the DASH server over a 200 Mbps
downstream bottleneck link.

Barefoot Tofino switch experiments: The experiments with Tofino programmable
switch concentrate on evaluating the impact of buffer size on the performance
of bottlenecked flows and how DiffPerf enables switch buffer to perform better
(i.e., improve the overall flow performance). The evaluations are carried out
with multiple switch buffer sizes: $100$KB, $1$MB, and $10$MB. Tofino exposes
a set of APIs for Traffic Manager applications to manage buffer allocation
from both ingress and egress ends. We use bf_tm_q_app_pool_usage_set API to
aid in setting buffer size for the queues of the egress port attached to the
bottlenecked link. Buffer size is specified in terms of cells, where each cell
size is 80 bytes. The buffer precedes a $120$ Mbps bottleneck link that
transfers video segments from DASH server to $100$ DASH clients. The results
are presented under the last part of Scenario 2 (Section IV-C2).

Except for Scenario 1 (Section IV-C1), assuming majority of flows in the
Internet have short RTTs [18], we partition the clients into two sets in 70:30
ratio based on the $\text{RTT}_{\text{min}}$ values configured: the mean and
standard deviation of the bigger set are 64ms and 16ms, respectively, and that
of the other are 224ms and 32ms, respectively. We use the network emulator
netem [19] at the server machines running the DASH clients to set the latency.
For streaming, we use the Big Buck Bunny video sample that lasts for 600
seconds and has been encoded into 3 bitrate levels—1.2 Mbps, 2.2 Mbps and 4.1
Mbps—of equal segments (i.e., each segment is 2 seconds long). Thus, a DASH
client can choose the bitrate levels and segments for streaming video, based
on the measured congestion level of the network. We compare DiffPerf against
two most popular TCP congestion control algorithms on the Internet [20]; TCP
CUBIC [21] and TCP BBR [22].

###  IV-B Metrics for evaluation

To evaluate the performance of DiffPerf and TCP variants, we use two metrics.
One is per-flow average throughput, which in our case corresponds to the
average throughputs of all DASH client. The other metric of importance is the
user-perceived quality-of-experience (QoE). The QoE metric is adopted based on
the widely used model proposed by [23], and is expressed as:
$\text{QoE}=\sum_{n=1}^{N}q(R_{n})-\lambda\sum_{n=1}^{N-1}|q(R_{n+1})-q(R_{n})|-\mu
T_{stall}-\mu_{s}T_{s}.$ This QoE definition uses various performance factors
such as the average playback bitrate $R_{n}$ over the total $N$ segments of
the video, the average variability of the consecutive segments bitrate
represented by the second summation, the duration of rebuffering $T_{stall}$
(i.e., the duration of time the player’s playout buffer has no content to
render), and startup delay ($T_{s}$) (i.e., the lag between the user clicking
and the time to begin rendering). As in [24][23], $q$ maps a bitrate to a
quality value; $\lambda$ is usually set to one, $\mu$ and $\mu_{s}$ are set to
the maximum bitrate of the video sample. We measure QoE for the entire
duration of the video.

(a) Throughput

(b) QoE

Figure 2: The Achieved throughput and corresponding QoE of multiple service
classes for different values of $\alpha$

###  IV-C Results

####  IV-C1 Scenario 1: Evaluation of inter-class performance

In this scenario we evaluate DiffPerf’s inter-class bandwidth allocation
model. We assume the access provider offers three classes of services: Golden
(G), Silver (S) and Bronze (B), with weights of 3, 2 and 1, respectively. We
run a set of experiments to evaluate the bandwidth allocated to users of
different classes under different values of $\alpha$. We assign 13 DASH
clients to each service class, thereby having a total of 39 DASH clients in
this scenario. All flows experience homogeneous RTT in this scenario.

Figures 2(a) plots, for each SC, the average throughput achieved by all flows
in that class, for different values of $\alpha$. Evidently, the ratios of the
estimated average throughput of flows across the service classes closely
follow the ratios obtained from our model (refer Eq. 4). In addition, the
average throughput is converging with increasing $\alpha$.

Figure 2(b) plots the average QoE of all flows in each SC. Observe that the
QoE of service class B is low, when the average throughput achieved (given in
Figure 2(a) achieved is low. The QoE of the three service classes converge
with increasing value of $\alpha$. With increasing $\alpha$, as resources
would be fairly shared among the competing flows, it is expected that higher
level QoE also reflects this fair sharing given that the flows have
homogeneous RTTs.

####  IV-C2 Scenario 2: Evaluation of intra-class performance

In this part, we evaluate our proposed performance-aware fairness,
($\beta$,$\gamma$)-fairness. That is, DiffPerf’$\beta$ capability to mitigate
the bias brought against the affected flows by the interaction between TCP
CUBIC, TCP BBR, flows with heterogeneous RTTs, and switch buffer size. Also,
we present the flexibility of $\gamma$ in enabling a feature of practical
interest, the trade-off between network efficiency and user QoE fairness.
Recall, DiffPerf uses statistical flow classification and bandwidth allocation
to the classified sub-classes to appropriately allocate a higher capacity to
the negatively affected flows.

DiffPerf based on CUBIC.

Figure 3: Aggregate throughput of the SC sub-classes flows

(a) Upper sub-class (b) Lower sub-class

Figure 4: QoE of the SC sub-classes flows

In Figure 3, we present the aggregate throughput achieved by DASH clients
belonging to the two different sub-classes, under TCP CUBIC, TCP BBR and
DiffPerf over CUBIC. We run experiments for different values of $\beta$. For
better clarity, we show the results only for $\gamma=0.5$. The number of flows
classified into the lower sub-class based on our statistical classification,
for $\beta=0,-0.25,-0.5,-0.75,$ and $-1.0,$ are 22, 17, 12, 9, and 5,
respectively. The figure shows that DiffPerf’s isolation enables the DASH
clients in the lower sub-class to achieve higher throughput than both TCP
variants, while also being to achieve comparable aggregate throughput as
TCP111Notice that all CUBIC, BBR, and DiffPerf achieve aggregate throughput
slightly higher than 50Mbps; this is due to the burstiness tolerated by
OpenFlow meters. Also, BBR achieves the highest aggregate as it fundamentally
does not passively react to packet loss or delay as signals of congestion..
And $\beta$ gives an access provider flexibility to decide on the flow
classification based on a simple and intuitive metric ($z$-score). While small
number of flows get classified in the lower sub-class, we note that these were
also the worst affected onces. Figures 4(a) and (b) plot the QoE achieved by
each DASH client, for $\beta=-0.25$; here we plot for different values of
$\gamma$ as well. The former figure plots QoE of the upper sub-class of flows,
the the latter plots the same for the lower sub-class of flows. The key
observation is that, the flows in the lower sub-class perceive higher QoE
under DiffPerf than under both TCP variants, and only at the cost of a small
number of flows in the upper sub-class. Another observation is that, with
lower $\gamma$, DiffPerf gives fairer QoE to the clients; DiffPerf with
$\gamma=0$ is the most fair. DiffPerf not only improves the fairness, we
calculated the overall QoE values for all flows; and it shows that DiffPerf,
via flow isolation as well as performance-aware bandwidth allocation, improves
significantly the overall QoE compared to TCP solely. It performs $1.86$,
$1.62$, and $1.58$ times higher QoE than CUBIC, at $\gamma=0$, $0.5$, and $1$,
respectively; Similarly, it performs $1.63$, $1.42$, $1.38$ times higher QoE
than BBR.

Figure 5: DiffPerf fairness-efficiency tradeoff

Fairness-efficiency tradeoff: We run experiments for different values of
$\gamma$, to analyze the trade-off between efficiency (i.e., bandwidth
utilization) and fairness (user-perceived quality fairness), $\beta$ is set to
$-0.25$. Figure 5 depicts that the aggregate throughput increases as $\gamma$
increases. Meanwhile, the average throughput of the lower sub-class decreases
and that of the upper-class increases, as $\gamma$ is increased from 0 to 1
(refer the second Y-axis). Evidently, the parameter $\gamma$ affects the
average flow throughput of both sub-classes. This behavior is due to the fact
that, when $\gamma$ approaches 0, the clients are allocated equal bandwidth
regardless of the sub-class; hence the DASH clients tend to achieve higher
throughput (subject to their characteristics), and thus the fairness is also
improved. Conversely, when $\gamma$ approaches 1, DiffPerf helps the network
achieves better bandwidth utilization. DiffPerf allocates higher bandwidth to
upper sub-class that likely has flows with greater tendency to exploit
provisioned network bandwidth, and hence result in better network utilization.

DiffPerf based on BBR. As TCP BBR has recently gained wide-spread attention,
DiffPerf is evaluated over TCP BBR. Figure 6 shows that DiffPerf’s isolation
enables DASH clients in the lower sub-class (i.e., the affected flows) to
achieve higher throughput than BBR, while also being able to achieve
comparable aggregate throughput as BBR. The number of flows classified into
the sub-classes are illustrated next to DiffPerf bar. For example, at $\beta$
= $0$, $26$ flows are classified into lower sub-class, and $14$ flows to upper
sub-class. Figure 7(a) and (b) plot the perceived QoE of DASH clients in the
aforementioned sub-classes. The lower-subclass flows with DiffPerf perceive
better QoE than with BBR.

Figure 6: Aggregate throughput of the SC sub-classes flows

(a) Upper sub-class (b) Lower sub-class

Figure 7:  QoE of the SC sub-classes flows

Impact of buffer size: Based on the experiments carried out on the Tofino
switch, this part presents the impact of buffer size on the performance of
bottlenecked flows and the flow optimization achieved using DiffPerf. Note,
Tofino switch updates DiffPerf with flow statistics every 1s (i.e., the
sampling rate). At every interval of $\Delta_{t}$ = 5s, DiffPerf uses the last
measured statistics for regulating network flows in the next immediate time
interval. Figure 8 plots the QoE achieved by $100$ DASH clients competing for
$120$Mbps bottleneck link preceded at one experiment by $1$MB shallow buffer
and in the other experiment by $10$MB deep buffer. With shallow buffer, BBR
achieves three times higher QoE than with deep buffer.

Figure 8: Impact of switch buffer size

We then run same experiments for DiffPerf, with $\beta=-0.25$ and $\gamma=0$;
and it achieves $1.58$ times higher QoE than BBR with shallow buffer and $2.6$
times higher QoE than BBR with deep buffer. We note that shallow buffer leads
to overall better user-perceived quality. However, quality worsens with much
smaller buffer size (e.g. $100$KB). The deep buffer might help low-throughput
flows, especially those affected by the interaction of TCP with flow RTT, to
achieve better QoE but it increases packet queuing delay. The very shallow
buffer (e.g. $100$KB) reduces packet queuing delay but increases packet
losses. Hence, both these extreme buffer sizes increase DASH client’s average
stalling time (i.e., the duration of time the player’s playout buffer has no
content to render). With BBR, the client average stalling time is $92.2$,
$56.4$, and $76.5$ seconds, while under DiffPerf, the client average stalling
time is reduced to $38.8$, $28.8$, and $58.4$ seconds over buffer sizes
$100$KB, $1$MB, and $10$MB, respectively. DiffPerf thus demonstrates to be
effective in improving the user-perceived quality for multiple buffer sizes.
Lastly, it is worth noting that from this set of experiments, the buffer size
of $1$MB makes better trade-off between queuing delays and packet losses.

(a) Arrival-departure of the Clients (b) G-class active flows (c) S-class
active flows  (d) B-class active flows

Figure 9: DASH clients arrival-departure and service classes cumulative sum of
active flows

(a) Bandwidth allocation for G-class (b) Bandwidth allocation for S-class

(c) Bandwidth allocation for B-class

Figure 10: Dynamic service classes bandwidth allocation

Overall, DiffPerf is fairer than both CUBIC and BBR in terms of client’s
throughput, client’s QoE, and provides the highest overall QoE.

Scalability: DiffPerf operations on the Tofino switch are split across
controller and dataplane. The controller collects aggregate real-time
statistics of the active flows, performs the optimization, and reacts to data
plane regularly. The dataplane tracks the number of bytes transferred by the
active flows. DiffPerf does not impose high rate of sampling, which may lead
to inaccurate statistics, especially when the DASH clients enter OFF period.
Hence, the communication (between controller and dataplane) is only at the
scale of seconds, and this works well for long running video flows over the
Internet. This is also demonstrated by our experimental results.

####  IV-C3 Scenario 3: The Dynamics of DiffPerf

Finally, to understand how DiffPerf performs in real-world cases, we evaluate
it in a dynamic scenario, where users from different service classes join and
leave the network at different times. In this set of experiments, we conduct
the evaluation on OpenFlow network centralized by ODL controller, were 150
DASH clients share a $200$ Mbps bottleneck link; they have variable RTTs, with
the ratio and distribution same as in the previous scenario. The arrivals of
the DASH client requests follow the Poisson process with rate $\lambda=1$
client/s. A client exits after the entire video (that lasts for $600$ seconds)
is streamed. The DASH clients subscribe to G, S, and B, service classes in the
ratio 1:2:3. The weights of service classes are kept the same as before; i.e.,
G:S:B = 3:2:1. We set the values of $\alpha$, $\beta$ and $\gamma$ to $1$,
$-0.25$, and $0.5$, respectively. At every interval of $\Delta_{t}$ = 15s,
DiffPerf uses the last measured statistics, such as number of active flows and
each flow’s instantaneous throughput ($\delta$ = 0), to subsequently send
command to the switch for regulating network flows in the next immediate time
interval. OpenFlow switch updates DiffPerf with flow statistics every 3s
(i.e., the default sampling rate in Brocade ICX-6610 switch). Figure 9(a)
shows the arrival and departure of DASH flows. The number of active flows in
the two sub-classes, for each of the services classes, are depicted in Figures
9(b), (c), and (d). Although the video being streamed is of 600 seconds,
observe that the G-class clients complete earlier than S-class and B-class;
and this is true for both lower and upper sub-classes. Similarly, S-class
flows finish earlier than B-class flows. We observe a sudden decrease in the
active flows a few times (the dips on the curves); this is not because the
flow(s) actually leave the system, rather, due to the expiry of idle timeout
of flows. When DASH client does not receive video segments packets, the
timeout causes the flow to be deemed as an inactive flow. However, once the
client resumes receiving data, DiffPerf promptly counts it as an active flow.
Figure 10 plots the dynamic bandwidth allocation recommended by DiffPerf, for
each service class and the sub-classes within. The bandwidth allocated
accounts for number of active flows in each service class and their achieved
throughput, optimized via ($\beta$, $\gamma$) performance-aware mechanism. It
also shows that DiffPerf adapts quickly to the departure of flows (observe
time period after 600 seconds), allocating the spare capacity to the remaining
active flows.

##  V Related Work

###  V-A TCP Congestion Control

Increase of network bandwidth also saw the emergence of ‘high-speed’ TCP
variants such as FAST [25], BIC [26], CUBIC [21] and BBR [22] for transporting
Internet traffic. Yet, TCP’s inability to fairly share the bandwidth of flows
with heterogeneous RTTs—a problem known to the community for around two
decades [27, 28, 29]—still persists. As demonstrated by our experiments (and
also other works, e.g., [30]) CUBIC exhibits such a behavior, and so does BBR
[9, 31]. This unfairness in achieved throughput worsens when flows with
different TCP congestion control mechanisms compete [11]. Another interesting
observation from literature is that the relative performance degradation in
throughput can be due to more than the single factor of RTT. In this context,
we highlight that DiffPerf is agnostic to the specific RTT of flows and other
router specifications (e.g., buffer size) in performing optimization and
enforcement of the computed optimized bandwidth; indeed DiffPerf classifies
and isolates flows of dissimilar characteristics solely based on tracking
their achieved throughput.

###  V-B Service Differentiation

Service differentiation is at the core of network quality of service (QoS)
provisioning to serve traffic from multiple classes over the network [32, 33,
34, 35]. While IntServ [34] did not find adoption in the Internet, DiffServ
[32] inspired a body of work on providing differentiated services. However,
many of such solutions mandate a sophisticated scheduling with manual
configuration of QoS knobs on a per service class basis. Instead, we choose a
well-known utility function based framework which enables service operator to
practically specify number of service classes and make good balance between
the bandwidth share and performance.

In [36], authors proposed an approach for rate-delay (RD) differentiation by
maintaining two queues at the router’s output link. While the aspirations
resemble DiffPerf, it is still best-effort and does not promise any rate or
loss guarantees. [37] discussed a static service differentiation framework for
ISP. In short, class-based traffic control and service differentiation have
been largely limited to theoretical analyses [36, 38, 39, 40], and have not
been experimented on hardware switches with real application traffic.
DiffPerf’s inter-class utility is general enough to make trade-offs among
desirable performance metrics and operates dynamically based on active users
and available bandwidth.

###  V-C Fair Queuing

Fair queuing has been a topic for extensive research [41, 42, 43, 42, 44, 45,
46]. FQ-CoDel [42], a recent AQM discipline, offers good performance gain in
achieving fairness among the flows, by classifying them into different buckets
and serving them in a round-robin manner. However, large memory is extremely
expensive or unavailable in data plane, hence it is practically infeasible to
accommodate very large number of buckets for hashing large number of flows.
DiffPerf optimizer performs simply by comparing flow’s $z$ score with a pre-
defined $\beta$ threshold, (i.e., classifier requires no training).
Additionally, unlike AQM, DiffPerf is not limited to specific congestion
algorithm; it works on top of several interactive parameters such as buffer
size, flow characteristics, and congestion algorithm. Also, DiffPerf is
portable, it can be packaged as virtual network function (VNF) over SmartNIC
[47], to handle a presence of extremely heavy workload.

###  V-D User Quality of Experience (QoE)

In the context of video streaming, several studies proposed to improve user
QoE [24, 48] or to achieve QoE fairness [49]. These approaches continuously
attempt to improve the adaptive bitrate (ABR) algorithms in the DASH Reference
Player at application layer, based on several performance metrics seen in the
application. Our work differ from them in that we propose bottom-up
optimization. DiffPerf reacts to the interplay between several network’s
inherently coupled parameters by continuously improving affected traffic
flows. This in large part improves the performance metrics (e.g., QoE
fairness) at the application.

##  VI Conclusion

We propose DiffPerf that leverages the rapid development in network
softwarization and enables an agile and dynamic network bandwidth allocation
at the AP vantage point. At a macroscopic level, DiffPerf offers access
providers new capabilities for performance guarantees by dynamically
allocating bandwidth to service classes through which the trade-off between
fairness and differentiation can be made. At a microscopic level, DiffPerf
isolates and optimizes the affected flows as a result of interplay between
several network’s inherently coupled parameters such as flow characteristics,
buffer size, and congestion algorithm. We implemented two prototypes of
DiffPerf; one in ODL with OpenFlow, and the other on the programmable Tofino
switch. We evaluate DiffPerf from an application perspective by evaluating it
for MPEG-DASH video streaming. Our experiment results confirm DiffPerf’s
capabilities of QoE provisioning, fairness, and optimization.

##  Appendix A Proofs of Theorems

Proof of Theorem 1: From optimization theory, our bandwidth allocation problem
is a convex optimization problem. By Karush-Kuhn-Tucker (KKT) conditions, it
has a unique solution which satisfies

$\displaystyle\begin{cases}\displaystyle
w_{s}\left(\frac{X_{s}}{n_{s}}\right)^{-\alpha}-u+u_{G}=0\ \ \text{and}\ \
u_{s}X_{s}=0,\ \forall s\in\mathcal{S},\\\ \displaystyle
u\left(\sum_{s\in\mathcal{S}}X_{s}-C\right)=0\end{cases}$

where $u$ and $(u_{s}:s\in\mathcal{S})$ are KKT multipliers and satisfy
$u,u_{s}\geq 0$ for any $s\in\mathcal{S}$. By solving the above equations, we
can derive that
$X_{s}=\frac{n_{s}\sqrt[\alpha]{w_{s}}}{{\underset{s^{\prime}\in\mathcal{S}}{\sum}n_{s^{\prime}}\sqrt[\alpha]{w_{s^{\prime}}}}}\
C,\forall s\in\mathcal{S}$.

Proof of Theorem 2: By the definition of the set $\mathcal{F}^{L}_{s}(\beta)$,
we know that for any two thresholds $\beta_{1}<\beta_{2}$,
$\mathcal{F}^{L}_{s}(\beta_{1})\subseteq\mathcal{F}^{L}_{s}(\beta_{2})$. For
any two flows $\bar{f}$ and ${f}$ satisfying
$\bar{f}\in\mathcal{F}^{L}_{s}(\beta_{1})$ and
${f}\in\mathcal{F}^{L}_{s}(\beta_{2})\backslash\mathcal{F}^{L}_{s}(\beta_{1})$,
we have $x_{\bar{f}}<x_{\tilde{f}}$ because $z_{\bar{f}}<\beta_{1}\leq
z_{\tilde{f}}<\beta_{2}$. Therefore, it satisfies
$\frac{\sum_{f\in\mathcal{F}_{s}^{L}(\beta_{1})}x_{f}}{|\mathcal{F}_{s}^{L}(\beta_{1})|}\leq\frac{\sum_{f\in\mathcal{F}_{s}^{L}(\beta_{2})}x_{f}}{|\mathcal{F}_{s}^{L}(\beta_{2})|}$,
i.e., the average achieved throughput of the flows within the lower sub-class
$\mathcal{F}^{L}_{s}$ is non-decreasing in $\beta$. By Eq.(5), when $\beta=0$,
we have
$\frac{\sum_{f\in\mathcal{F}_{s}^{L}(\beta)}x_{f}}{|\mathcal{F}_{s}^{L}(\beta)|}=\frac{\sum_{f\in\mathcal{F}_{s}^{-}}x_{f}}{|\mathcal{F}_{s}^{-}|}\leq\frac{X_{s}^{L}(\beta)}{|\mathcal{F}_{s}^{L}(\beta)|}$
because $\mathcal{F}^{L}_{s}=\mathcal{F}^{-}_{s}$. In other words, the average
achieved throughput of the flows within the lower sub-class
$\mathcal{F}^{L}_{s}$ equals the average per-flow capacity re-allocated to
$\mathcal{F}^{L}_{s}$. Because $|\mathcal{F}^{L}_{s}|$ is non-decreasing in
$\beta$, $\gamma n_{s}/\left(n_{s}-|\mathcal{F}^{L}_{s}|\right)$ is non-
decreasing in $\beta$. By Eq.(5), the capacity allocated to the per-flow of
the upper sub-class satisfies
$\frac{X_{s}^{H}}{|\mathcal{F}^{H}_{s}|}=\frac{X_{s}-X^{L}_{s}}{|\mathcal{F}^{H}_{s}|}=\frac{\gamma
n_{s}}{n_{s}-|\mathcal{F}^{L}_{s}|}\left(\frac{X_{s}}{n_{s}}-\frac{\sum_{f\in\mathcal{F}_{s}^{-}}x_{f}}{|\mathcal{F}_{s}^{-}|}\right)+\gamma\frac{\sum_{f\in\mathcal{F}_{s}^{-}}x_{f}}{|\mathcal{F}_{s}^{-}|}+(1-\gamma)\frac{X_{s}}{n_{s}}\geq\frac{X_{s}}{n_{s}}$.
Thus it is non-decreasing in $\beta$ and no lower than $X_{s}/n_{s}$.

## References

  * [1] “Cisco Annual Internet Report (2018–2023),” https://www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/annual-internet-report/white-paper-c11-741490.pdf, acc. Aug. 2020.
  * [2] “Canopus Networks,” https://canopusnet.com/insights/, acc. May. 2020.
  * [3] “Open Connect,” https://openconnect.netflix.com/en/, acc. Aug. 2020.
  * [4] R. Kundel, J. Wallerich, W. Maas, L. Nobach, B. Koldehofe, and R. Steinmetz, “Queueing at the telco service edge: Requirements, challenges and opportunities,” in _Workshop on Buffer Sizing_ , 2019.
  * [5] “Netflix,” https://ispspeedindex.netflix.com/country/us/, acc. May. 2020\.
  * [6] P. Faratin, D. D. Clark, S. Bauer, and W. Lehr, “Complexity of Internet interconnections: Tech., incentives and implications for policy,” 2007.
  * [7] K. Bollen and R. Lennox, “Conventional wisdom on measurement: A structural equation perspective.” _Psychological bulletin_ , 2018.
  * [8] R. Srikant, _The mathematics of Internet congestion control_. Springer Science & Business Media, 2012.
  * [9] M. Hock, R. Bless, and M. Zitterbart, “Experimental evaluation of BBR congestion control,” in _Proc. IEEE ICNP_ , 2017.
  * [10] M. Mathis and A. McGregor, “Buffer sizing: a position paper,” in _Workshop on Buffer Sizing_ , 2019.
  * [11] J. Rüth, I. Kunze, and O. Hohlfeld, “An Empirical View on Content Provider Fairness,” in _”Proc. TMA_ , 2019.
  * [12] X. Chen, H. Kim, J. M. Aman, W. Chang, M. Lee, and J. Rexford, “Measuring tcp rtt in the data plane,” in _Workshop on SPIN_ , 2020.
  * [13] “OpenDaylight Project,” http://wiki.opendaylight.org, acc. Jul. 2019.
  * [14] M. Bjorklund _et al._ , “Yang - a data modeling language for the netconf protocol,” https://tools.ietf.org/html/rfc6020, acc. Aug 2020.
  * [15] “Cisco nexus 5500 series nx-os quality of service configuration guide.” https://www.cisco.com/c/en/us/td/docs/switches/datacenter/nexus5500/sw/qos/7x/b_5500_QoS_Config_7x.html, acc. Aug. 2020.
  * [16] “Brocade ICX 6610 Switches.” https://www.dataswitchworks.com/datasheets/switches/brocade-icx-6610-ds.pdf, acc. Aug. 2020.
  * [17] “Barefoot Networks, Tofino.” https://goo.gl/cdEK1E, acc. Aug. 2020.
  * [18] R. Farahbakhsh, A. Cuevas, A. M. Ortiz, X. Han, and N. Crespi, “How far is Facebook from me? Facebook network infrastructure analysis,” _IEEE Communications Magazine_ , 2015.
  * [19] “Network emulation with netem,” https://man7.org/linux/man-pages/man8/tc-netem.8.html, acc. Aug 2020.
  * [20] A. Mishra, X. Sun, A. Jain, S. Pande, R. Joshi, and B. Leong, “The great internet tcp congestion control census,” in _in Proc. ACM on MACS_ , 2019\.
  * [21] S. Ha, I. Rhee, and L. Xu, “CUBIC: a new TCP-friendly high-speed TCP variant,” _ACM SIGOPS operating systems review_ , 2008.
  * [22] N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, and V. Jacobson, “BBR: Congestion-Based Congestion Control,” _Queue_ , 2016.
  * [23] X. Yin, A. Jindal, V. Sekar, and B. Sinopoli, “A control-theoretic approach for dynamic adaptive video streaming over HTTP,” in _Proc. ACM SIGCOMM_ , 2015.
  * [24] P. K. Yadav, A. Shafiei, and W. T. Ooi, “Quetra: A queuing theory approach to dash rate adaptation,” in _Proc. ACM MM_ , 2017.
  * [25] D. X. Wei, C. Jin, S. H. Low, and S. Hegde, “FAST TCP: Motivation, Architecture, Algorithms, Performance,” _IEEE/ACM Tran. on Net._ , 2006\.
  * [26] Lisong Xu, K. Harfoush, and Injong Rhee, “BIC for fast long-distance networks,” in _Proc. IEEE INFOCOM_ , 2004.
  * [27] C. Barakat, E. Altman, and W. Dabbous, “On TCP performance in a heterogeneous network: a survey,” _IEEE Comm. Magazine_ , 2000.
  * [28] K. Tan, J. Song, Q. Zhang, and M. Sridharan, “A Compound TCP Approach for High-Speed and Long Distance Networks,” in _Proc. IEEE INFOCOM_ , 2006\.
  * [29] Y. Li, D. Leith, and R. N. Shorten, “Experimental Evaluation of TCP Protocols for High-Speed Networks,” _IEEE/ACM Tran. on Net._ , 2007.
  * [30] D. Miras, M. Bateman, and S. Bhatti, “Fairness of High-Speed TCP Stacks,” in _Proc. AINA_ , 2008.
  * [31] S. Ma, J. Jiang, W. Wang, and B. Li, “Towards rtt fairness of congestion-based congestion control,” _CoRR_ , 2017.
  * [32] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An architecture for differentiated service,” http://www.ietf.org/rfc/rfc2475.txt, acc. Aug 2020.
  * [33] X. Wang and H. Schulzrinne, “Pricing network resources for adaptive apps in a diff. services network,” in _Proc. IEEE INFOCOM_ , 2001.
  * [34] R. Braden, D. Clark, and S. Shenker, “Integrated services in the internet architecture,” http://www.ietf.org/rfc/rfc1633.txt, acc. Aug 2020.
  * [35] J. Rao, Y. Wei, J. Gong, and C.-Z. Xu, “Qos guarantees and service differentiation for dynamic cloud apps,” _IEEE Tran. on NSM_ , 2012.
  * [36] M. Podlesny and S. Gorinsky, “Rd network services: differentiation through performance incentives,” _Proc. ACM SIGCOMM_ , 2008.
  * [37] V. Sivaraman, S. C. Madanapalli, H. Kumar, and H. H. Gharakheili, “Opentd: Open traffic differentiation in a post-neutral world,” in _Proc. ACM SOSR_ , 2019.
  * [38] B. Han, V. Sciancalepore, D. Feng, X. Costa-Perez, and H. D. Schotten, “A utility-driven multi-queue admission control solution for network slicing,” in _Proc. IEEE INFOCOM_ , 2019.
  * [39] Y.-W. E. Sung, C. Lund, M. Lyn, S. G. Rao, and S. Sen, “Modeling and understanding end-to-end class of service policies in operational networks,” in _Proc. ACM SIGCOMM_ , 2009.
  * [40] M. Zou, R. T. Ma, X. Wang, and Y. Xu, “On optimal service differentiation in congested network markets,” _IEEE/ACM Tran. on Net._ , 2018.
  * [41] D. Katabi, M. Handley, and C. Rohrs, “Congestion control for high bandwidth-delay product networks,” in _Proc. ACM SIGCOMM_ , 2002.
  * [42] T. Hoeiland-Joergensen, P. McKenney, D. Taht, J. Gettys, and E. Dumazet, “The flow queue-codel packet scheduler and active queue management algorithm,” _IETF Draft, March_ , 2016.
  * [43] J. C. Bennett and H. Zhang, “Hierarchical packet fair queueing algorithms,” _IEEE/ACM Tran. on Net._ , 1997.
  * [44] N. K. Sharma, M. Liu, K. Atreya, and A. Krishnamurthy, “Approximating fair queueing on reconfigurable switches,” in _Proc. NSDI_ , 2018.
  * [45] M. Hedayati, K. Shen, M. L. Scott, and M. Marty, “Multi-queue fair queuing,” in _Proc. NSDI_ , 2019.
  * [46] A. Sivaraman, K. Winstein, S. Subramanian, and H. Balakrishnan, “No silver bullet: extending sdn to the data plane,” in _Proc. ACM Workshop on Hotnets_ , 2013.
  * [47] “Netronome, SmartNICs.” https://www.netronome.com/blog/ovs-offload-models-used-nics-and-smartnics-pros-and-cons/, acc. Aug. 2020.
  * [48] A. Bentaleb, A. C. Begen, and R. Zimmermann, “Sdndash: Improving qoe of http adaptive streaming using software defined networking,” in _Proc. ACM MM_ , 2016.
  * [49] P. Georgopoulos, Y. Elkhatib, M. Broadbent, M. Mu, and N. Race, “Towards network-wide qoe fairness using openflow-assisted adaptive video streaming,” in _Proc. ACM SIGCOMM workshop on FhMN_ , 2013.


Cl- | $96/100$ | $95/100$ | $97/100$ | $99/100$
Ca | $95/100$ | $97/100$ | $87/100$ | $100/100$
Ionised Ca | $93/100$ | $92/100$ | $85/100$ | $99/100$
CO2 | $92/100$ | $93/100$ | $93/100$ | $99/100$
Albumin | $96/100$ | $95/100$ | $96/100$ | $99/100$
Hb | $96/100$ | $95/100$ | $96/100$ | $100/100$
pH | $98/100$ | $98/100$ | $88/100$ | $100/100$
BE | $90/100$ | $94/100$ | $90/100$ | $98/100$
HCO3 | $95/100$ | $95/100$ | $94/100$ | $100/100$
FiO2 | $91/100$ | $99/100$ | $94/100$ | $99/100$
Glucose | $96/100$ | $96/100$ | $89/100$ | $99/100$
BUN | $94/100$ | $94/100$ | $93/100$ | $100/100$
Creatinine | $94/100$ | $94/100$ | $90/100$ | $100/100$
Mg | $90/100$ | $93/100$ | $90/100$ | $98/100$
SGOT | $92/100$ | $96/100$ | $84/100$ | $98/100$
SGPT | $90/100$ | $89/100$ | $93/100$ | $100/100$
Total Bili | $91/100$ | $91/100$ | $87/100$ | $100/100$
WBC | $97/100$ | $99/100$ | $93/100$ | $100/100$
Platelets | $94/100$ | $96/100$ | $95/100$ | $99/100$
PaO2 | $97/100$ | $98/100$ | $95/100$ | $100/100$
PaCO2 | $95/100$ | $95/100$ | $95/100$ | $99/100$
Lactate | $97/100$ | $97/100$ | $84/100$ | $100/100$
Input Total | $95/100$ | $95/100$ | $84/100$ | $99/100$
Input 4H | $83/100$ | $94/100$ | $94/100$ | $100/100$
Max Vaso | $0/100$ | $96/100$ | $30/100$ | $97/100$
Output Total | $92/100$ | $95/100$ | $89/100$ | $99/100$
Output 4H | $90/100$ | $96/100$ | $90/100$ | $100/100$
Table 9: A Subset of Stage Two Statistics for Sepsis Variable Name | . KS-Test . | . t-Test . | . F-Test . | Three Sigma Rule Test
---|---|---|---|---
Gender | $88/100$ | \- - | $64/100$ | \- -
Readmission | $97/100$ | \- - | $88/100$ | \- -
Mech | $100/100$ | \- - | $96/100$ | \- -
GCS | $93/100$ | \- - | $86/100$ | \- -
SpO2 | $97/100$ | \- - | $96/100$ | \- -
Temp | $95/100$ | \- - | $91/100$ | \- -
PTT | $94/100$ | \- - | $87/100$ | \- -
PT | $97/100$ | \- - | $96/100$ | \- -
INR | $99/100$ | \- - | $97/100$ | \- -
Table 10: The Remaining Stage Two Statistics for Sepsis

####  D.6.3 HIV

Variable Name | . KS-Test . | . t-Test . | . F-Test . | Three Sigma Rule Test
---|---|---|---|---
VL | $48/100$ | $90/100$ | $15/100$ | $100/100$
CD4 | $83/100$ | $97/100$ | $91/100$ | $91/100$
Rel CD4 | $85/100$ | $92/100$ | $100/100$ | $99/100$
Gender | $97/100$ | \- - | $49/100$ | \- -
Ethnic | $81/100$ | \- - | $38/100$ | \- -
Base Drug Combo | $73/100$ | \- - | $71/100$ | \- -
Comp. INI | $96/100$ | \- - | $73/100$ | \- -
Comp. NNRTI | $92/100$ | \- - | $95/100$ | \- -
Extra PI | $100/100$ | \- - | $73/100$ | \- -
Extra pk-En | $100/100$ | \- - | $95/100$ | \- -
VL (M) | $100/100$ | \- - | $72/100$ | \- -
CD4 (M) | $99/100$ | \- - | $94/100$ | \- -
Drug (M) | $100/100$ | \- - | $88/100$ | \- -
Table 11: The Stage Two Statistics for HIV

Of all the $13$ variables, only VL failed the KS-test. Similar to Max Vaso in
sepsis, VL was highly skewed and also failed the F-test. This shows the
difficulty in appropriately capturing the variability of highly skewed
distributions. Nonetheless, we found that VL was still realistic as it passed
the three sigma rule test with very good scores.

Both gender and ethnicity required extra attention. Even though both variables
passed the KS-test, they did not perform well on the ANOVA F-test. In fact,
several binary and categorical variables in the synthetic HIV dataset only
achieved acceptable (70$\%$+), instead of ideal (preferrably 85$\%$+), scores
for their F-tests. While we were unable to explain the exact reason for this,
we speculated that this was due to the combination of variables in the
dataset. Unlike the hypotension and sepsis datasets, the HIV dataset contained
very few numeric variables. Therefore, it is possible that many categorical
variables were more difficult to synthesise.

Overall, we believe that the synthetic HIV dataset is still realistic. All but
one variable passed the KS-test, and the numeric variables performed very well
on the three sigma rule test.

##  Appendix E The Correlations of Stage 3

This appendix contains details on the correlation assessments that we used in
stage 3 of the Realisticness Validation Procedure in the Technical Validation
section. The definitions of each test and potential alternatives are discussed
below.

Our readers can click here to resume to Stage Three: Correlations in the
Realisticness Validation Procedure section.

###  E.1 Kendall’s Rank Correlation

The non-parametric Kendall rank correlation, otherwise known as Kendall’s
$\tau$ correlation, is a statistic that measures the strength of association
between two variables. In this study, we used the $\tau$-b variant and we
refer to the original paper[48] for its precise definition.

The magnitude of the correlation between a pair of variables, $X^{(i)}$ and
$X^{(j)}$ for $i\neq j$, was measured by the score $\tau^{(i,j)}\in[-1,1]$. A
score of 1 or -1 indicated perfect positive or negative alignment between
$X^{(i)}$ and $X^{(j)}$ respectively; whereas 0 indicated no correlation. We
calculated the Kendall’s $\tau$ with the .corr() function of the Python [65]
package of Pandas [75].

###  E.2 Correlation Between Variables

Given the synthetic dataset $D_{\text{syn}}$ and the real dataset
$D_{\text{real}}$, the Kendall rank correlation scores were used to determine
whether correlations between any pair of variables (based on data from all
patients and timepoints) were captured in the generated data.

###  E.3 Average Correlation in Trends and in Cycles

The correlations in this section are used to investigate the behaviour of the
generated data over time. Our datasets comprise many patients, each of whom is
associated with a specific trajectory over time. Thus, correlations over time
were computed individually for every patient and pair of variables.
Afterwards, these correlations were averaged across patients.

More in detail, for a specific patient $p_{k}$ we selected a pair of variables
${}_{p_{k}}X^{(i)}$ and ${}_{p_{k}}X^{(j)}$. We assumed that they could be
linearly decomposed into trends an cycles:

${}_{p_{k}}X^{(i)}$
$\displaystyle=\text{Trend}(_{p_{k}}X^{(i)})+\text{Cycle}(_{p_{k}}X^{(i)})\text{
and}$ (13) ${}_{p_{k}}X^{(j)}$
$\displaystyle=\text{Trend}(_{p_{k}}X^{(j)})+\text{Cycle}(_{p_{k}}X^{(j)}).$
(14)

We implemented Cycle() with the signal.detrend() function of the Python [65]
package of Scipy [66]; whereas Trend() is simply the remainder of
$X-\text{Cycle}(X)$. By using the signal.detrend() function, we assumed that
each time series has a linear trend. Alternatively, non-linear trends over
time could be determined using moving average algorithms.

We repeat this process for every patient $p_{k}$, $k=1,\ldots,n$, and average
the correlation scores for trends and cycles (the number of patients in the
synthetic dataset might be different from the one in the real dataset, since
the GAN can be used to generate any amount of data). Pseudo-code for computing
the average correlations in trends and cycles is provided in Algorithm 2 for
additional clarity.

###  E.4 Remarks on Kendall’s Rank Correlation and Alternative Validation
Metrics

In this study, we conducted the technical validation using Kendall’s rank
correlation instead of the more common Pearson’s r correlation [36]. This was
because of two reasons. First, Pearson’s correlation requires all test
variables to be normally distributed [76]. As shown in Figure 3, there were
several variables that had long tail distributions and could not be power-
transformed appropriately. Second and unlike Pearson’s correlation, Kendall’s
rank correlation could be used for both binary and categorical variables.
Furthermore, Kendall’s rank correlation was even applicable in scenarios where
we needed to test the relations between a multi-class variable and a binary-
class variable.

Besides correlations, we also considered other metrics for validating the
quality of the generated synthetic data. For example, auto-correlations and
cross-correlations [77] would be useful to better understand the properties of
the generated time series. However, they do not appear suitable to assess the
similarity between patterns in two time series from two datasets. Similarly,
the Wilcoxon-Mann-Whitney [78] test would be helpful to determine if two
variables are independent; however, our focus was on the similarity of
relations between variables from two datasets.

Our validation setup also differs from the work of Goncalves et al.[22]. In
their study, Goncalves et al. employed log-cluster[79] and the
Kullback–Leibler (KL) divergence[80] to compare the relative similarity of
synthetic datasets generated by different models against their real “ground
truth” dataset. In our study, we compared synthetic datasets generated using
one GAN model to the real datasets.

Algorithm 2 The Psuedo-Code for the Average Correlations

1:$\\{\\}_{\text{trend:syn}},\\{\\}_{\text{cycle:syn}},\\{\\}_{\text{trend:real}},\\{\\}_{\text{cycle:real}}=\emptyset$
$\triangleright$ Create storage to record correlation scores.

2:.

3:for $k=1,n$ do$\triangleright$ Loop over each patient.

4: .

5: for $i=1,N$ do$\triangleright$ Select a variable $i$.

6: $\\{\\}_{\text{trend:syn}}^{\text{k,
i}},\\{\\}_{\text{cycle:syn}}^{\text{k,
i}},\\{\\}_{\text{trend:real}}^{\text{k,
i}},\\{\\}_{\text{cycle:real}}^{\text{k, i}}=\emptyset$ $\triangleright$
Create a separate storage for patient-variables pair.

7: .

8: for $j=1,(i-1)$ do$\triangleright$ And select another variable $j$.

9: .

10:
${}_{p_{k}}X^{(i)}_{\text{syn}}=\text{Trend}(_{p_{k}}X^{(i)}_{\text{syn}})+\text{Cycle}(_{p_{k}}X^{(i)}_{\text{syn}})$
$\triangleright$ Decompose the selected time series

11:
${}_{p_{k}}X^{(j)}_{\text{syn}}=\text{Trend}(_{p_{k}}X^{(j)}_{\text{syn}})+\text{Cycle}(_{p_{k}}X^{(j)}_{\text{syn}})$

12:
${}_{p_{k}}X^{(i)}_{\text{real}}=\text{Trend}(_{p_{k}}X^{(i)}_{\text{real}})+\text{Cycle}(_{p_{k}}X^{(i)}_{\text{real}})$

13:
${}_{p_{k}}X^{(j)}_{\text{real}}=\text{Trend}(_{p_{k}}X^{(j)}_{\text{real}})+\text{Cycle}(_{p_{k}}X^{(j)}_{\text{real}})$

14: .

15:
$\tau^{(i,j)}_{\text{trend:syn}}=\tau\left(\text{Trend}(X^{(i)}_{\text{syn}}),\text{Trend}(X^{(j)}_{\text{syn}})\right)$
$\triangleright$ Compute the respective correlation scores in trend.

16:
$\tau^{(i,j)}_{\text{trend:real}}=\tau\left(\text{Trend}(X^{(i)}_{\text{real}}),\text{Trend}(X^{(j)}_{\text{real}})\right)$

17:
$\tau^{(i,j)}_{\text{cycle:syn}}=\tau\left(\text{Cycle}(X^{(i)}_{\text{syn}}),\text{Cycle}(X^{(j)}_{\text{syn}})\right)$
$\triangleright$ And compute the respective correlation scores in cycle.

18:
$\tau^{(i,j)}_{\text{cycle:real}}=\tau\left(\text{Cycle}(X^{(i)}_{\text{real}}),\text{Cycle}(X^{(j)}_{\text{real}})\right)$

19: .

20: $\\{\\}_{\text{trend:syn}}^{\text{k,
i}}=\\{\\}_{\text{trend:syn}}^{\text{k,
i}}\cup\tau^{(i,j)}_{\text{trend:syn}}$ $\triangleright$ Record the scores for
each patient.

21: $\\{\\}_{\text{cycle:syn}}^{\text{k,
i}}=\\{\\}_{\text{cycle:syn}}^{\text{k,
i}}\cup\tau^{(i,j)}_{\text{cycle:syn}}$

22: $\\{\\}_{\text{trend:real}}^{\text{k,
i}}=\\{\\}_{\text{trend:real}}^{\text{k,
i}}\cup\tau^{(i,j)}_{\text{trend:real}}$

23: $\\{\\}_{\text{cycle:real}}^{\text{k,
i}}=\\{\\}_{\text{cycle:real}}^{\text{k,
i}}\cup\tau^{(i,j)}_{\text{cycle:real}}$

24: end for

25: end for

26:end for

27:.

28:for $i=1,N$ do$\triangleright$ For averaging across each patient.

29:
$\\{\\}_{\text{trend:syn}}=\\{\\}_{\text{trend:syn}}\cup\mathbb{E}_{k}(\\{\\}_{\text{trend:syn}}^{\text{k,
i}})$$\triangleright$ Acquire the average correlation in trends.

30:
$\\{\\}_{\text{trend:real}}=\\{\\}_{\text{trend:real}}\cup\mathbb{E}_{k}(\\{\\}_{\text{trend:real}}^{\text{k,
i}})$

31:
$\\{\\}_{\text{cycle:syn}}=\\{\\}_{\text{cycle:syn}}\cup\mathbb{E}_{k}(\\{\\}_{\text{cycle:syn}}^{\text{k,
i}})$$\triangleright$ Acquire the average correlation in cycles.

32:
$\\{\\}_{\text{cycle:real}}=\\{\\}_{\text{cycle:real}}\cup\mathbb{E}_{k}(\\{\\}_{\text{cycle:real}}^{\text{k,
i}})$

33:end for

##  Appendix F Full Correlation Plots for Sepsis

Figure 13: The Complete Static Correlation Plots for Sepsis

Our readers can click here to resume to Validation Outcome: Sepsis in the
Technical Validation section.

Figure 14: The Complete Dynamic Correlations in Trends for Sepsis

Figure 15: The Complete Dynamic Correlations in Cycles for Sepsis

##  Appendix G Assessment of Disclosure Risk

This appendix aims to provide more details for the assessment of disclosure
risk and covers some potential alternative metrics.

Our readers can click here to resume to the Security Confirmation Report in
the Technical Validation section.

###  G.1 El Emam et al.’s Disclosure Risk Metrics

This appendix provides more intuitions to El Emam et al.[38]’s risk evaluation
metrics. Assuming that an adversary was able to recover partial information
(i.e., the quasi-identifiers) of an individual (i.e., the acquaintance), El
Emam et al.[81] formulated the probability of the successful re-identification
(re-id) of the information of an acquaintance as

$\displaystyle\mathbb{P}(\text{re-
id},\text{acquaintance})=\mathbb{P}(\text{acquaintance})\times\mathbb{P}(\text{re-
id}|\text{acquaintance})$ (15)

using the Bayes rule.

Based on Equation (15), their population-to-sample re-identification risk for
the real dataset of

$\displaystyle\underbrace{\frac{1}{P}}_{\leavevmode\hbox to11.75pt{\vbox
to11.75pt{\pgfpicture\makeatletter\hbox{\hskip 5.87407pt\lower-5.87407pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\underbrace{\sum_{s=1}^{S}}_{\leavevmode\hbox
to11.75pt{\vbox to11.75pt{\pgfpicture\makeatletter\hbox{\hskip
5.87407pt\lower-5.87407pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\underbrace{\left(\frac{1}{f_{s}}\right)}_{\leavevmode\hbox
to11.75pt{\vbox to11.75pt{\pgfpicture\makeatletter\hbox{\hskip
5.87407pt\lower-5.87407pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$

considers that 2 for all individuals in the real sample dataset, calculate the
chance of 1 any randomly selected record from the population 3 being matched
to a specific record in the real dataset with its equivalent class of quasi-
identifiers known (e.g., male and 21 years old). Note that component 1
corresponds to $\mathbb{P}(\text{acquaintance})$ – the selection of a random
record from a population of size $P$. In addition, components 2 and 3 are
affiliated to $\mathbb{P}(\text{re-id}|\text{acquaintance})$ because all
patients with the same equivalent class of size $f_{s}$ (e.g., $3$ if there
are 3 males that are 21 years old) have an equal chance of being pinpointed
with accuracy $\frac{1}{f_{s}}$ (i.e., $\frac{1}{3}$ chance for each 21 years
old male to be identified).

Following the same line of thoughts, their sample-to-population re-
identification risk for the real dataset of

$\displaystyle\underbrace{\frac{1}{S}}_{\leavevmode\hbox to11.75pt{\vbox
to11.75pt{\pgfpicture\makeatletter\hbox{\hskip 5.87407pt\lower-5.87407pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\underbrace{\sum_{s=1}^{S}}_{\leavevmode\hbox
to11.75pt{\vbox to11.75pt{\pgfpicture\makeatletter\hbox{\hskip
5.87407pt\lower-5.87407pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\underbrace{\left(\frac{1}{F_{s}}\right)}_{\leavevmode\hbox
to11.75pt{\vbox to11.75pt{\pgfpicture\makeatletter\hbox{\hskip
5.87407pt\lower-5.87407pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.67407pt}{0.0pt}\pgfsys@curveto{5.67407pt}{3.13374pt}{3.13374pt}{5.67407pt}{0.0pt}{5.67407pt}\pgfsys@curveto{-3.13374pt}{5.67407pt}{-5.67407pt}{3.13374pt}{-5.67407pt}{0.0pt}\pgfsys@curveto{-5.67407pt}{-3.13374pt}{-3.13374pt}{-5.67407pt}{0.0pt}{-5.67407pt}\pgfsys@curveto{3.13374pt}{-5.67407pt}{5.67407pt}{-3.13374pt}{5.67407pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$

describes the scenario that 2 for all individuals in the real sample dataset,
calculate the chance of 4 any randomly selected record from the real dataset 5
that can be traced back to a specific record in the population sharing the
same equivalent class of quasi-identifiers. This time,
$\mathbb{P}(\text{acquaintance})$ corresponds to component 4 with
$\frac{1}{S}$ because the real dataset has a total of $S$ records; and that
$\mathbb{P}(\text{re-id}|\text{acquaintance})$ is now affiliated with 5 with
$\frac{1}{F_{s}}$ because the total amount of records and their equivalent
classes are now sourced from the population.

Our readers should note that Equation (4) was actually not the full
formulation of El Eman et al.’s risk definitions for the synthetic datasets.
Instead, their full formulations were expressed as

$\displaystyle\text{the population-to-sample risk}:\hskip
8.53581pt\frac{1}{P}\sum_{s=1}^{S}\left(\frac{1}{f_{s}}\times\lambda_{s}\times
R_{s}\right)\hskip 8.53581pt\text{and}$ (16) $\displaystyle\text{the sample-
to-population risk}:\hskip
8.53581pt\frac{1}{S}\sum_{s=1}^{S}\left(\frac{1}{F_{s}}\times\lambda_{s}\times
R_{s}\right).$ (17)

The full expressions included two extra terms. Under the section of Adjusting
for Incorect Matches in their paper, the authors noted that $\lambda$ was a
constant term $\in(0,1]$ that scaled down the original re-identifiability for
the records in the dataset. This term existed because that health data, and
generally any type of data from a data broker, were known to have some error
rates[51]; and $\lambda$ was introduced to correct the overestimation of
meaningful adversarial re-identifications. Furthermore and under the section
of Learning Something New, the authors noted that $R$ was a binary term and
that $R=1$ only when any matched records contributed towards learning non-
duplicated re-identified information. These two extra terms thus scaled down
the original population-to-sample risk and sample-to-population risk. In our
own work, we left these two terms out because that the unscaled risks were
already very low.

###  G.2 Alternative Disclosure Risk Metrics

In this study, we employed the Euclidean distance and the synthetic-to-real
disclosure risk to investigate the risks associated with the public release of
synthetic datasets. However, that there are many alternative options.

Instead of the Euclidean distance, the Mahalanobis distance[82] may be well
suited to the high dimensionality of electronic health records. Nonetheless,
the Euclidean distance was perfectly suitable to show that there were no
perfect matches between real and synthetic records.

Furthermore, El Emam et al.’s metrics are just two of the many available
metrics in the risk disclosure literature. Both the population-to-sample risk
and the sample-to-population risk can be seen as extended applications of
k-anonymity[83] – a desirable property for a dataset implying that multiple
records share the same equivalence class of quasi-identifiers, thus lowering
the chance of identity exposure (e.g., it is better if a released dataset
contains multiple 21-year-old makes instead of just one). However, it is well-
known that attributes of an anonymised dataset could still be inferred even if
k-anonymity is satisfied. Attribute disclosure is especially concerning if
homogeneity in patient data is high. For instance, if all 21-year-old males
suffer from stomach problems and a specific 21-year-old male is the target of
an adversary, then the adversary can acquire knowledge automatically without
the need to match any records. Attribute disclosure can be mitigated by
achieving l-diversity[84] and/or t-closeness[85] in addition to k-anonymity.
The former aims to increase the number of sensitive attributes within each
equivalence class; whereas the latter uses information theoretic measures to
verify if the records satisfy a minimal level of diversification.

Aside from Euclidean distances and disclosure risks, a practitioner could also
test the security of their synthetic datasets by building predictive models.
For instance, Choi et al.[41] used k nearest neighbours to predict a varying
number of known attributes in the datasets. This could be helpful to determine
whether any known sensitive variables could be easily reconstructed through
the quasi-identifiers.