Vimalkumar Jeyakumar1, Abdul Kabbani2, Jeffrey C. Mogul2, Amin Vahdat2,3
1Stanford University, 2Google, 3UCSD

# Flexible Network Bandwidth and Latency Provisioning in the Datacenter

### Abstract

Predictably sharing the network is critical to achieving high utilization in
the datacenter. Past work has focussed on providing bandwidth to endpoints,
but often we want to allocate resources among multi-node _services_. In this
paper, we present Parley, which provides service-centric minimum bandwidth
guarantees, which can be composed hierarchically. Parley also supports
service-centric weighted sharing of bandwidth in excess of these guarantees.
Further, we show how to configure these policies so services can get low
latencies even at high network load. We evaluate Parley on a multi-tiered
oversubscribed network connecting 90 machines, each with a 10Gb/s network
interface, and demonstrate that Parley is able to meet its goals.

##  1 Introduction

Multi-tenancy is inevitable at large scale. In Google’s datacenters, we see on
average tens of jobs per server. A typical server is shared by applications
that have diverse performance requirements from the network, such as:

  * •

Bandwidth Intensive: A MapReduce job during its read and shuffle stages; or,
large file copies.

  * •

Latency Sensitive: The front-end for user-facing services, such as web search.

  * •

Bandwidth and Latency Sensitive: Infrastructure services, such a distributed
file system (DFS), often have a mix of bandwidth and latency sensitive flows.

These applications can also be adversarial. For example, tenant virtual
machines (VMs) sharing the same network, in public clouds such as Amazon EC2,
Google Compute Engine, HP Cloud, and Windows Azure, are not likely to be
cooperative.

Prior work (see mogul2012we [18] for a detailed summary) in this space has
already made the case for sharing bandwidth across entities that are coarser-
grained than a TCP flow. For example, Oktopus ballani2011towards [2],
Gatekeeper rodrigues2011gatekeeper [23], EyeQ jeyakumar2013eyeq [14] and
ElasticSwitch popa2013elasticswitch [20] all provide, for a tenant’s
collection of VMs, the abstraction of a dedicated physical network, with a
specified guaranteed bandwidth for each endpoint VM. This abstraction of a
shared network can be useful for providers wishing to support predictable
behavior for tenant applications provisioned at a VM granularity.

However, these prior systems that support bandwidth guarantees raise the
following questions:

  * •

How should we realize notions of sharing that are (a) more flexible than
guarantees (e.g. _weighted_ sharing); and (b) service-centric, where services
are a collection of endpoints?

  * •

How should the service provision bandwidth to achieve service-level
objectives, such as a bounded 99th percentile (tail) latency?

In this paper, we present Parley, a system we built to understand answers to
the above questions. Parley has several features which make it attractive for
practical deployment: (1) it supports a mixture of policies, such as bandwidth
guarantees to service end-points, and hierarchical, weighted sharing,
constructed by nesting service endpoints; (2) it uses a simple model of
traffic characteristics to predict a service’s tail latency based on its own,
and collocated services’ provisioned bandwidth, that is accurate at high
loads.

We built Parley by systematically leveraging prior bandwidth sharing systems
to achieve our goals (we modify the open-sourced system EyeQ jeyakumar2013eyeq
[14]). There are two parts to Parley: (a) static provisioning, which the
provider specifies when services are instantiated, and (b) runtime
provisioning, which Parley determines based on bandwidth usage. While
bandwidth guarantees are easy to statically provision using admission control,
Parley differs from EyeQ in that runtime provisioning for hierarchical and
weighted sharing requires information about services’ bandwidth usage.

Figure 1: Parley supports a hierarchical sharing policy. The top figure shows
the service placement on machines under the rack of a given capacity, and the
bottom half illustrates sharing policies at the machine and rack.

For example, Figure 1 shows an example of a static sharing policy, in which
the DFS service is allocated at least 6Gb/s, and at most 8Gb/s; and all (non-
paying) VMs are allocated a maximum of 1Gb/s. That aggregate of 1Gb/s is then
shared in a ‘weighted max-min’ [bertsekas1992data, 4, Sec. 6.5.2] fashion
among VMs in the rack. Each VM’s allocation depends on their own, and the
total bandwidth consumption of other VMs in the rack. This requires global
service-level visibility of bandwidth usage that EyeQ does not have.

Parley adds this missing piece of global visibility on top of EyeQ, while
retaining its strengths, as follows: At the core of Parley’s runtime system is
a “bandwidth broker” that allocates capacities to services in a hierarchical
fashion. At the lowest level, each VM (or job, or service endpoint) on a
machine is allocated an aggregate transmit and receive _hose capacity_. These
capacities are periodically tuned by the bandwidth broker to conform to the
global policy, based on (i) service endpoint’s machine-level utilization
(§3.2.1), (ii) service’s rackswitch-level utilization (§3.2.2), and (iii)
service’s overall fabric utilization (§3.2.3). Hose capacities are enforced
directly in the _dataplane_ using distributed, end-to-end congestion control.
This decomposition of the global sharing objective into rack and machine sub-
problems enables Parley to scale to a large datacenter.

Specifically, the main contributions of our paper are:

  * •

The design and implementation of Parley that manages datacenter network
bandwidth among services, in a flexible, and scalable fashion. Parley adds
support for hierarchical allocations and distributed rate limiting,
generalizing the notion of bandwidth guarantees provided by systems such as
EyeQ and ElasticSwitch.

  * •

Demonstrating that a service’s soft-realtime latency requirements can be met
by appropriately controlling peak network load.

##  2 Background and Requirements

Datacenter bandwidth is not free. Modern datacenter network topologies are
typically multi-staged Clos topologies greenberg2009vl2 [10] with few over-
subscription points (typically only at the top-of-rack switch). Measurements
from a highly-utilized datacenter show that packet drops occur predominantly
at such over-subscription points in the topology, as shown in Figure 2. The
contention can be broadly classified into three cases:

  * •

Host level: multiple jobs sharing a host share the host (NIC) transmit and
receive bandwidth. On the transmit side, the host network stack is back-
pressured, so we do not see any drops. However, a large fraction of dropped
packets happen at the receiver, due to incast-like traffic patterns. We call
this _host fanin_.

  * •

First rackswitch: Due to rackswitch over-subscription, hosts under a rack can
overwhelm the limited-capacity uplinks. We call this the _uplink overload_.

  * •

Last rackswitch: Finally, some small fraction of drops happen _within the
fabric_ , because the fabric overwhelms the rackswitch’s limited capacity to
its hosts. We call this _downlink overload_.

Very few drops occur elsewhere within the fabric. We observe similar trends in
other highly-utilized clusters.

Our goal is to address contention-induced packet drops, because TCP is the
dominant protocol in the datacenter, and its default response to dropped
packets aims at fair per-flow bandwidth allocation—without taking service-
level requirements into consideration.

Figure 2: The contention points for intra-cluster bandwidth that Parley
addresses.

###  2.1 What does ‘predictability’ mean?

Our primarily goal is to share bandwidth in a programmable and well-specified
fashion, and to have low, bounded tail latency. We argue that many seemingly
different notions of predictability can be mapped to offering guarantees on
aggregate bandwidth at a contention point.

Service-level guarantees. Consider large-scale data-analysis jobs with
multiple MapReduce stages, which care most about total completion time. The
total job completion time is a complex function of the number of CPUs (number
of workers), the available network bandwidth, and the number of barriers
(stages) in the job ferguson2012jockey [8]. Job completion time generally does
not depend on short-term network latency. Parley allows the job scheduler to
request bandwidth while accounting for contention at the machine and rack
level. This explicit guarantee allows the job scheduler to make better
decisions ferguson2012jockey [8] when placing jobs and orchestrating
transfers, _enabling_ predictable job completion times.

Latency. Infrastructure services also have have stringent requirements on tail
latency (e.g., $<$20ms response time for 1MB IO operations at the 99th
percentile). Achieving tail latency guarantees is hard, as this fundamentally
depends on the stochastic nature of flow arrivals. This fundamental dependence
cannot be avoided. However, given a model of flow arrivals, a bandwidth
guarantee can _bound_ tail completion times.

For example, if the inter-flow arrival times are exponentially distributed,
and their processing times (i.e. flow sizes) are also exponentially
distributed, then the distribution of flow completion times can be explicitly
written down as a function of the service instance’s allocated bandwidth. That
is, in a steady state $M/M/1/{\rm FIFO}$ queue, the flow completion time $t$
(i.e. waiting time + service time) has the probability density function
queueing [12]

$f(t)=\begin{cases}\mu(1-\rho)\exp\left({-\mu(1-\rho)t}\right)&t>0\\\
0&\text{otherwise.}\end{cases}$

where $\mu$ is the average service _rate_ (a function of the available
capacity), and $\rho\in(0,1)$ is the average load on queue. For example, if
the average flow size 1MB, $\mu$ is 1.25 per ms at 10Gb/s; we can then deduce
that 99% of flow completion times are $<$18.4ms.

By empirically measuring the distribution of flow sizes, service times, and
inter-arrival times (all of which change relatively infrequently), we can do
an offline simulation to derive a bandwidth guarantee requirement that will
support robust bounds on a flow’s tail latency. Though the formula makes an
assumption about the distribution of flow sizes and their inter-arrival times,
we discuss in §4 how we can bound latency without modeling or making
assumptions about the arrival process, using a simple counting argument.

Thus, to deal with latency requirements, Parley can explicitly guarantee
aggregate capacity to service endpoints, and control the peak load on the
network.

Summary: The main takeaway is that for many use cases, explicit bandwidth
guarantees at the level of service endpoints (e.g. VMs), and control of the
peak load on the network, helps application-specific schedulers to maintain
predictability for their own metrics. Hence, Parley provides knobs to share
network bandwidth in a flexible fashion, and strives to meet these
requirements as quickly as possible.

###  2.2 Related Work

Many works address bandwidth management within a cluster. Since we build on
top of EyeQ jeyakumar2013eyeq [14], we inherit its benefits over prior work
such as Seawall shieh2011sharing [24], Gatekeeper rodrigues2011gatekeeper
[23], Oktopus ballani2011towards [2], and FairCloud popa2012faircloud [21]. We
therefore focus on more recent work.

Both EyeQ jeyakumar2013eyeq [14] and ElasticSwitch popa2013elasticswitch [20]
only offer work-conserving (and non work-conserving) bandwidth guarantees to
individual service endpoints. CloudMirror lee2013cloudmirror [16] argues for
asymmetric transmit and receive guarantees. However, they are limited in their
ability to handle network congestion in a flexible fashion. If the network is
congested, bandwidth is shared in a max-min fashion either across receiving
endpoints (EyeQ), or across contending source/destination host pairs
(ElasticSwitch), which need not necessarily match service-specific goals. In
§6.3 we show how this flexibility helps in controlling tail latency at high
loads.

The bandwidth enforcer in Google’s B4 SDN WAN jain2013b4 [13] allocates
bandwidth at the granularity of (QoS,src-datacenter,dst-datacenter) tunnels.
This approach does not scale to allocations within a datacenter, due to the
large number of (source,destination) pairs. Instead, Parley’s optimization
decomposition decouples mechanisms for pairwise allocations between
source/destination hosts from service-level allocations, which helps
scalability.

Hadrian ballani2013chatty [1] describes a hierarchical, work-conserving hose
model to guarantee a tenant a minimum inter-tenant bandwidth. However, Hadrian
requires switch changes to count the number of flows on a per-tenant basis,
which changes quite frequently. It is unclear if this is practical, and
whether Hadrian’s allocations are stable over time. However, the policy
framework we describe in this work is rich enough to capture inter-tenant
isolation as well.

DRL raghavan2007cloud [22] focuses on distributed rate limits by having
service endpoints exchange demands using a gossip-protocol. However,
distributed rate limits alone is insufficient in sharing bandwidth in a
predictable fashion, as a service can target its entire bandwidth share at a
single machine. Our approach is inspired by DRL, but uses a hierarchical
decomposition to explicitly handle the major oversubscription points. For
instance, by aggregating service endpoints at a machine and rack level, we
flexibly share limited machine and rack bandwidth.

Commercial switches cisco:qos [6] do support hierarchical sharing policies.
However, these policies are limited: First, switches can only drop packets,
and we need traffic admission control to deal with malicious traffic. Second,
switches only offer a link-centric sharing policy. In practice, we desire an
_end-to-end_ view for allocating bandwidth, regardless of the physical
topology.

The line of work on Dominant Resource Fairness (DRF) ghodsi2011dominant [9, 5]
defines a fairness metric when sharing _across_ multiple resource types, such
as CPU, memory, and network, but rely on other mechanisms to _enforce_ these
allocations. Parley can be used as an enforcer for network bandwidth.

##  3 Design

We now detail the design of Parley, starting with its approach to specifying
bandwidth guarantees. We then describe the high-level system architecture, and
each component in more detail.

###  3.1 Specifying Sharing Policies

In Parley, a policy is specified with respect to hierarchies of services at
one contention point. Services are traffic bundles that are uniquely
identifiable using a packet filter; a service can be a single endpoint, a
collection of endpoints, or sub-flows within an endpoint. The service
hierarchy must be a tree (i.e. no loops). Each service has both a machine-
level and rack-level policy, to cover the primary contention points in a
datacenter. A service can have different policies for transmit and receive.

For instance, at the machine level, all flows terminating at the Distributed
File System (DFS) service port are part of the DFS service, even if they
involve multiple source servers. At the rack level, the DFS endpoints can be
aggregated into one service S1, and VM endpoints can be aggregated into
another service S2, but a DFS endpoint cannot be part of both S1 and S2.

A flow between a source and destination can be part of multiple services;
e.g., traffic from a MapReduce client to a DFS server consumes bandwidth both
at MapReduce and DFS, and is therefore charged to both services. The guarantee
for traffic between two services is limited to the minimum of the two service-
specific guarantees. E.g., a flow between a MapReduce client guaranteed 2Gb/s
and a DFS server guaranteed 1Gb/s will be guaranteed only 1Gb/s.

A policy is configured using several parameters:

  * •

Min bandwidth: the guaranteed bandwidth for the service; the default is 0,
implying no guarantee.

  * •

Max bandwidth: the limit on the service’s bandwidth; the default is
“unlimited.”

  * •

Weight: excess bandwidth (what remains after all guarantees have been met) is
shared among contenders based on their weights (subject to their max limits).
Weights encode a service’s relative importance. The default weight is 1.

Policies can be specified statically, or can be changed any time to support
dynamic reservations xie2012only [27]. Note that in the case of guarantees,
admission control and job placement must ensure that the guarantees can be
satisfied in the worst case (i.e., when all services demand their full
guaranteed bandwidth). When aggregating services, the guarantee for the parent
service must at least be the sum of guarantees of its child services.

The most constrained policy determines the service allocation. For instance,
consider a situation where there are 10 MapReduce jobs in a rack, and each job
has machine-level policy (weight = 1, max = 1Gb/s). If MapReduce jobs in
aggregate have a rack-level policy (max = 5Gb/s), and all jobs are active,
each job can send at 0.5Gb/s. However, if only one job is active, it cannot
grab the entire 5Gb/s, since its machine-level policy is the most constrained,
and takes effect. Thus, besides the static policy, there is a dynamically
computed _runtime policy_ which is actually enforced. Note that service
policies are implicitly constrained by machine and rack capacities.

Why have hierarchical policies? A hierarchical policy is one way to quantify
the over-provisioning _risk_ , which makes sharing _unambiguous_ at every
contention point, instead of letting services battle it out between
themselves. Without hierarchy, we would have to provision for the worst case
simultaneously at each contention point, which usually does not happen often,
and can waste capacity. Hierarchies are also useful from an operational
perspective; since Parley exposes both guarantees and runtime policies for
every service, it is easier to debug when a service does not get its
bandwidth.

###  3.2 Design components

Figure 3: Parley consists of distributed machine shapers, rack-local brokers
and a fabric broker that work together to enforce policies at different
contention points.

Parley consists of three components, each responsible for computing and
enforcing both transmit and receive bandwidth allocations, at different
contention points. Figure 3 shows the high-level architecture. These
components work together to enforce the static policy.

  * •

The Machine shaper handles host fanin and fanout. Its job is to enforce
service shares only at a machine granularity, according to the static and
runtime machine policy. It allocates bandwidth at the granularity of
(source,destination) pairs of communicating hosts jeyakumar2013eyeq [14].

  * •

The Rack broker handles the downlink and uplink overload on every rack. Its
job is to dynamically compute per-service per-machine policy, so that the
static rack policy is enforced by the machine shaper.

  * •

The Fabric broker handles distributed rate limits, to enforce bandwidth caps
on various services at the global scale. It dynamically computes a per-rack,
per-service policy to enforce the static fabric policy.

Figure 1 in §1 shows an example with two services: VMs and DFS. To simplify
discussion, we assume there are no fabric-level shares for both services.
There are two machines with 10Gb/s capacities under the rackswitch, which has
a 10Gb/s bandwidth to the fabric. The rack sharing policy is to divide
bandwidth such that VMs gets at most 1Gb/s, and DFS gets at least 6Gb/s. Thus,
when every service is active, (M1,VM), (M2,VM) will get 0.5Gb/s each, and
(M1,DFS), (M2,DFS) are allocated 4Gb/s each. When (M2,DFS) is idle, (M1,DFS)
is allocated 8Gb/s, and when all VMs are idle, (M1,DFS) is allocated the
entire 9Gb/s.

Note that the rack broker only computes (machine,service) shares, and is not
concerned with traffic patterns that change frequently. The machine shaper
works at fast timescales, to ensure machine runtime policy is enforced
regardless of fine-grained communication patterns. This timescale requirement
has a direct impact on the design of the individual components, which we
detail next.

####  3.2.1 Machine shaper

A machine may run a number of services, each perhaps in its own virtual
machine. The problem of enforcing machine-level bandwidth shares is the same
problem solved by EyeQ jeyakumar2013eyeq [14]: On the transmit side, the
machine shaper consists of a single root rate limiter that enforces an
aggregate rate limit on the service’s traffic leaving the machine. In
addition, per-destination rate limiters enforce receive-bandwidth shares. The
receive-bandwidth shares are computed at the receiver, and signalled back to
the sources using a feedback packet.

On the receive side, each service is attached to a rate meter, which is
allocated some capacity $C$. The rate meter periodically measures the
aggregate bandwidth utilization $y(t)$ of the service, and continuously
computes _one_ rate $R(t)$ such that the aggregate utilization $y(t)$ matches
the service capacity $C$. This is done iteratively using a control equation:

$R(t+T)=R(t)\times\left(1-\alpha\frac{y(t)-C}{C}-\mathds{1_{\rm
marked(t,t+T)}}\frac{\beta}{2}\right)$

where $T$ is a configurable time period, $\alpha$ is a parameter chosen for
stability. The value $\beta$ is the fraction of Explicit Congestion
Notification (ECN) marked packets, and is used only if there are marked
packets in the interval $t$ and $t+T$ (denoted as $\mathds{1_{\rm
marked(t,t+T)}}$). The control equation water-fills $R(t)$ such that the
utilization $y(t)$ matches capacity $C$.

The receiver samples incoming packets (1 every 10kB) and sends feedback to the
source IP address. Sampling ensures that heavy hitters are rate limited. The
feedback message encodes $R(t)$ serialized in a custom IP packet. When a
sender service receives feedback from a particular destination, it
creates/updates a rate limiter to the destination, under the sender’s root
rate limiter, to enforce the bandwidth allocation (as shown in Figure 4) .

Figure 4: An example of a max-min fair allocation (across senders at a
receiver) computed by the machine shaper. The allocation is computed at the
receiver, and communicated to senders using feedback messages. The end-to-end
allocation is computed in a distributed fashion using only local information.

Weighted allocation across senders. When two services communicate with each
other, their receivers can divide allocated capacity in a weighted fashion
across senders: The sender simply scales its feedback to $w_{\rm sender}\times
R(t)$. The weight ensures that the rates of senders 1 and 2 are always in the
ratio $w_{1}:w_{2}$.

Figure 5: Inter-tenant sharing is a special case of hierarchical sharing.

Inter-tenant sharing. For the heavy bandwidth consumers such as DFS, a common
requirement is to share bandwidth among its own users, according to some
specified policy (typically weighted shares). Since the notion of a ‘service’
is flexible, it can further be _deaggregated_ into ‘service:user.’ For
instance, if HBase (HB) and VMs both use DFS, we can create the service
hierarchy shown in Figure 5 (S2 being another service). Deaggregation enables
delegation, where services can use Parley to manage their bandwidth. Each
packet is associated with a leaf node identified using packet classification
rules installed on the machine, both on the transmit and the receive path.

Parameter guidelines: We use the same parameter settings as in EyeQ:
$T=200\mu{}s$ and $\alpha=0.5$. Note that the receiver _does not keep track of
the number of senders_. This is by design: datacenter measurements
benson2010network [3] show high flow-arrival rates at a host
(hundreds/second), which makes per-flow tracking expensive and complex.

####  3.2.2 Rack broker

The machine shaper realizes an allocation using only information locally
available at a machine, so it can only satisfy the machine policy. The rack
broker aggregates service-level bandwidth usages across machines in a rack,
uses these values as ‘demands,’ and computes a machine-level transmit/receive
runtime policy for each service. This policy determines the service’s transmit
and receive capacity. The transmit capacity is set on the (machine,service)
root rate limiter, and the receive capacity is set on the (machine,service)
root rate meter. Once these capacities are set, the machine shaper enforces
these capacities continuously. _Note that the rack broker does not track
(source-ip,destination-ip) communicating pairs._ This is the key difference
between our mechanism and a similar control mechanism in Oktopus
[ballani2011towards, 2, §4.3].

Figure 6: An example illustrating the hierarchical max-min allocation,
computed at the rack level in two steps: (i) aggregate measurements, and (ii)
enforce allocations. The red boxes denote the only entities (service
instances) that are rate-limited.

The design of the rack broker is best explained by an example. Consider the
desired sharing policy shown in Figure 6 (assume for now that the demands were
computed before the rack broker kicks in). The problem of determining the per-
machine service policy that satisfies the rack policy can be done in two
passes:

  1. 1.

A bottom-up pass from child to root that computes the aggregate demand at each
intermediate node in the sharing hierarchy.

  2. 2.

A top-down pass that computes the new runtime policies at each node in the
sharing hierarchy, according to the parent’s policy.

We make two assumptions: First, knowing the rack’s capacity to the fabric core
(i.e., the 50Gb/s in Figure 6) greatly simplifies bandwidth allocation. This
is feasible as datacenter operators have full control over their network
infrastructure, and so the rack broker can periodically query (say) an
OpenFlow controller about the rack uplink capacities. Second, we assume that
the uplinks are evenly utilized, so we can treat them as one single link. But
recall that the machine shaper’s allocations fall back gracefully even if
there is in-network congestion (which is often only transient).

Allocation Algorithm: The runtime weighted max-min allocations and min/max
guarantees can be computed by the classical water-filling algorithm
[bertsekas1992data, 4, § 6.5.2]. Each iteration of the algorithm satiates the
demand for one service. We do not rate limit endpoints whose demand is less
than its capacity determined by the water-fill algorithm, as rate limiting
shows a flow’s progress, and increases its flow completion time (§4,§7).

####  3.2.3 Fabric broker

The rack broker allocates bandwidth based on a capacity assigned to the rack,
and based on (rack,service) limits. These limits can in turn be adjusted based
on the global fabric bandwidth consumption of a particular service. The rack
broker at each rack communicates the (rack,service) demands to a global fabric
broker, which uses these demands and in turn computes new (rack,service)
allocations using the same max-min algorithm shown above. The fabric broker
operates at a slower timescale, running every $T_{\rm fabric}=10$ seconds.

###  3.3 Scalability

The EyeQ jeyakumar2013eyeq [14] paper discusses scalability of the machine
shaper in detail. We therefore focus on the rack and fabric brokers, both of
which have the same design.

Using measurements from production clusters, we find that the approach that
aggregates (machine,service) tuples across machines under a rack and fabric
scales well. To make the right allocations, the rack broker only needs to know
the bandwidth utilization of the heavy bandwidth consuming services. If we
define a “heavy rack-consumer” as a service using at least 100Mb/s of rack
bandwidth (averaged over 5-minute intervals) we observe 10–100 of such heavy
consumers per rack. If we set a higher threshold of 1Gb/s for a “heavy fabric-
consumer” the number rapidly diminishes. It is therefore practical to collect
and process service-level usages.

###  3.4 Optimization Decomposition

The key idea behind splitting the problem into multiple sub-problems is the
principle of optimization decomposition. A sharing objective is decomposed
into multiple sub-problems that execute in a distributed fashion. We refer the
reader to palomar2006tutorial [19] for a detailed discussion on the
mathematical foundations of optimization decomposition.

Figure 7: Optimization decomposition in Parley.

Parley uses this approach, which has also been adopted by other bandwidth-
management systems jain2013b4 [13, 25], and inherits several benefits:

  * •

Scalability: Each shaper/broker is responsible only for a portion of the
datacenter, and the optimization decomposition leads to a design that scales
with the datacenter size. The machine shaper deals with no more than a few
tens of services; the rack broker deals with no more than a few 100s of
(machine,service) pairs in the rack; and the fabric broker deals with more no
than tens to hundreds of racks.

  * •

Fault tolerance: The scale-out design ensures graceful degradation, as un-
failed parts of the system will continue normal operation. For instance, since
the machine shaper uses ECN marks to detect when the network is congested, the
rack broker can fail without significantly affecting the system. The
allocations degrade gracefully, and by design, the receivers will get a max-
min share of the rackswitch bandwidth.

The main disadvantage of optimization decomposition is that the bandwidth
allocation according to specified policy is not computed in one shot, but over
a sequence of iterations. This can delay the speed at which a service can get
its full allocation. While this is typically not a big concern at fabric
scale, a service must be able to grab its fair bandwidth share quickly at the
rack level. Our design choice to not rate limit services that are not
consuming their full bandwidth share gives them the ability to ramp up
quickly.

One possible concern is that services, when not rate limited, can burst to
gain an unfair share of bandwidth and affect other service allocations. The
effect of this burst is limited, as the machine-shaper kicks in quickly
(within hundreds of micro-seconds) during transient network congestion,
ensuring that services are not starved.

###  3.5 Are demands stable?

The bandwidth brokers operate at three different timescales: (i) the machine
shaper operates at network round-trip timescales, (ii) the rack broker
operates at timescales of seconds, and (iii) the fabric broker operates on
multiple tens of seconds. One might wonder if the (machine,service) demands
are stable for a long enough period that the rack broker can kick in, and the
same for the global fabric broker. Figure 8 presents evidence that demands are
indeed stable, so the individual brokers can operate effectively over the
timescales they are designed for.

Figure 8: Time series of uplink and downlink utilizations (averaged over 1s)
of a highly utilized rack, showing that the link utilizations are fairly
stable over multiple seconds.

By design, the rack broker kicks in and enforces allocations only when the
bandwidth usage is above limits specified by policy. Figure 8 shows the
utilization (averaged over 1 sec.) of one highly-utilized rack in a production
data center. We see that the aggregate transmit and receive utilizations
remain fairly stable over multiple seconds, and thus the timescale of a few
seconds is pragmatic. We don’t have visibility at smaller timescales in
production traffic.

##  4 Provisioning for Latency

In §2, we showed how a bandwidth guarantee enables services to achieve a bound
on the tail flow completion times. The formula, however, made an assumption
that flow arrivals are Poisson, and that flow sizes are exponentially
distributed with a given mean.

While this model serves as a useful guide to provision systems, it is often
the case that flow arrivals are not Poisson. Prior datacenter measurement work
shows that flow arrivals are _bursty_ benson2010network [3]. Therefore, we
seek a guideline that does not make assumptions on flow sizes (except that
they are finite), or flow service order (except that the system is work-
conserving), or any particular flow arrival pattern. Since we make minimal
assumptions, the bound will serve as a useful guideline to reason about the
worst-case performance.

We model a latency-sensitive endpoint as a work-conserving queue of capacity
$C$ that is shared with other endpoints. It is impossible to have any
guarantees unless we constrain the arrivals in some fashion. Suppose
$B(t_{1},t_{2})$ refers to the number of bytes received by the queue between
time $t_{1}$ and $t_{2}$. Consider a constrained arrival process parameterized
by $(\sigma,\rho)$ cruz1991calculus [7] such that:

$B(t_{1},t_{2})\leq\sigma+\rho\;C\;(t_{2}-t_{1})$ (1)

for all $t_{1}<t_{2}$. Here, $\sigma$ quantifies the arrival burstiness, and
$\rho\in(0,1)$ quantifies the average long-term rate. Then, we can show that
the flow completion time ${\rm FCT}(f)$ of any flow $f$ of size $Z(f)$
satisfies:

${\rm FCT}(f)\leq\frac{\sigma+Z(f)}{C(1-\rho)}$ (2)

The proof is by a counting argument: Let $S(f)$ and $F(f)$ denote the start
time and finish time for a flow $f$. Now, the number of bytes arriving to the
server between $S(f)$ and $F(f)$ is constrained by Equation 1. We have:

###### .

$\displaystyle F(f)$ $\displaystyle\leq\text{Start time + Waiting time +
Service time}$ $\displaystyle F(f)$ $\displaystyle\leq
S(f)+\frac{B(S(f),F(f))}{C}+\frac{Z(f)}{C}$ $\displaystyle(1-\rho)\;F(f)$
$\displaystyle\leq(1-\rho)\;S(f)+\frac{\sigma+Z(f)}{C}$

Since $\rho\in(0,1)$, the quantity $(1-\rho)>0$, and therefore:

$\displaystyle F(f)-S(f)$ $\displaystyle\leq\frac{\sigma+Z(f)}{C(1-\rho)}$
$\displaystyle\implies\;\;{\rm FCT}(f)$
$\displaystyle\leq\frac{\sigma+Z(f)}{C(1-\rho)}$

∎

_Alternatively, this bound can be used as a guideline to limit the peak load
$\rho$ on the network to keep FCT under a desired value._ The bound only
assumes a $(\sigma,\rho)$ constraint on arrivals to the work-conserving queue,
and that latency-sensitive flows are not rate limited. A rate-based congestion
control can control the long-term load $\rho$. The burst size $\sigma$ is the
maximum of two components: (i) the excess line-rate burst due to delayed
convergence of the congestion control algorithm, and (ii) the burstiness of
sender rate limiters. From experiments, we found that the burst due to
convergence time is the dominant factor; i.e., if the congestion control
algorithm converges in $t$ seconds, then the queue sees a maximum burst of
$C\times{}t$.

For example, if C=100Mb/s, and the congestion control algorithm takes 10ms to
converge, then the maximum burst size is about 83 MTU sized packets. Once the
congestion control algorithm converges, the only burstiness is due to rate
limiters at senders. To quantify this burst, we set up an experiment using the
Mininet network emulator as follows: 100 hosts talk to one receiver using
long-lived TCP flows rate limited to to 1/100th of the desired load $\rho$ at
the receiver. The rate limiters were configured with a maximum burst size of
64kB, and we measure the queue sizes at the receiver. Figure 9 plots the
distribution of queue sizes for various values of $\rho$. We find that even at
90% load, the 99th percentile queue size is less than 25 packets, which is
smaller than the maximum burst due to delayed convergence (83 packets),
indicating that the burst contribution due to the delayed convergence of
congestion control algorithm plays a dominant role in determining the worst
case flow completion time.

Figure 9: CDF of queue sizes as a function of load.

Though the bound is on the worst case FCT, flows can be reordered (e.g.
through prioritization) to achieve better individual FCTs. How a service
schedules its own flows in accordance to bandwidth guarantees is completely up
to it. We echo the insight of recent work pFabric alizadeh2013pfabric that
rate control is perhaps a poor choice for fine-grained prioritization across
_mice flows_ (e.g. flows less than a few 100kB). Parley’s rate control is
decoupled from the flow’s priority. In practice, datacenter measurements
alizadeh2010data; greenberg2009vl2 [10] show that most of the bandwidth
consumption is from the elephant flows that last long enough to be accurately
rate limited (flows between a few MB to 100s of MB last a few msec. to 100s of
msec.).

##  5 Implementation

Our prototype of Parley builds on top of EyeQ.111http://jvimal.github.io/eyeq/
We first briefly review the implementation of the machine shaper in EyeQ,
discuss our new improvements, and then describe the implementation of the rack
broker and fabric broker. Though we prototyped Parley in software, its control
logic (rate brokers) could interface with a hardware datapath (e.g., rate
limiters on a NIC, or in switches within the fabric).

###  5.1 Machine shaper

The machine shaper consists of a transmit and receive side component. As in
EyeQ, we use hierarchical rate limits to enforce sharing policies on the
transmit side. At a service endpoint on a machine, the rate limiter hierarchy
is shown in Figure 10. In the hierarchy, rack uplink traffic is controlled by
rate limits set by the rack broker (on the service root rate limiter). This
means that inter- and intra-rack traffic share the same rate limit if there is
congestion at the rack uplinks; however, when we look at measurements from
several datacenters, we see that most of the traffic is _inter-rack_ , so we
did not optimize for fate sharing. Nevertheless, we could separate inter- and
intra-rack traffic below the service root rate limiter, and have the rack
broker set limits only on inter-rack traffic. The rate limiters and rate
meters are designed for high throughput using per-CPU datastructures.

Figure 10: The rate limiter hierarchy at the sender, and rate meters at the
receiver, shaded by service type.

###  5.2 Rack broker

We implemented the rack broker as a user-space program in C++. There are many
ways to query the aggregate link utilization across services: the program can
install counters on the rackswitch and use OpenFlow mckeown2008openflow [17]
to count the per-service utilization. However, for ease of deployment, we
implemented a simple approach to aggregating the (machine,service) counters.
The rack broker is distributed across machines, and each machine queries the
local machine shaper to obtain a list of (machine,service) pairs. Each machine
then broadcasts this list of tuples to other machines in the rack, and
aggregates tuples from other machines. Thus, each machine will have its own
copy of the list of (machine,service) counters for all machines and services
in the rack. Using this information, each machine runs the water-fill
algorithm to determine all (machine,service) allocations, and each machine
locally enforces allocations for its own services. The machines broadcast the
counters using UDP once every $T_{\rm rack}$ seconds.

Tolerance to failures: In the absence of rack shaper, the machine shapers fall
back gracefully to a max-min fair allocation across receiving VMs/service
instances (as in EyeQ). Thus, rack broker failures do not cause global
failures. However, the rack broker is highly fault tolerant, as it runs on
every machine. If a few machines die, the remaining rack brokers continue
working as expected. If the broadcast packets are intermittently lost, the
last updated value of (machine,service) is used to compute bandwidth shares.
We prevent small rate allocations from sticking permanently by having machine
shapers reset their allocations to their static configuration after a long
timeout. This timeout value $T^{t}_{\rm rack}$ is chosen so that the machine
shaper can be certain about a rack broker failure.

###  5.3 Fabric broker

The fabric broker uses the (rack,service) shares for a given rack, to
determine new (rack,service) allocations on a per-rack basis. The fabric
broker runs relatively infrequently on a few machines spread across the
datacenter. On each rack, one of the rack brokers is designated as the leader,
and the leader sends the rack-level bandwidth consumption to the fabric
broker’s service address. As with rack broker, the fabric broker need not be
perfectly reliable.

The rack leader sends an RPC to the fabric broker once every 10 seconds. Even
with 10000 racks within a cluster, sending 10kB data (which encodes
utilizations for over 1000 services) to the fabric shaper consumes only 80Mb/s
of traffic at the fabric broker.

Tolerance to failures: The strategy that rack brokers use to handle handle
fabric broker failures is exactly the same as the strategy machine shapers use
to handle rack broker failures. However, we set a larger timeout, $T^{t}_{\rm
fabric}=50\text{~{}seconds}$. If the rack broker doesn’t hear from the fabric
broker in 50 seconds, it resets the runtime policy to the statically
configured policy.

##  6 Evaluation

We demonstrate that Parley achieves our goals of predictable bandwidth
sharing.

Since we built Parley on top of EyeQ, we refer the reader to measurements in
the EyeQ paper [jeyakumar2013eyeq, 14, §5.1]. Parley inherits EyeQ’s results
for: (i) low CPU overhead when compared to state-of-the-art software rate
limiters; (ii) millisecond-timescale convergence times at the machine shapers.

The new aspects of Parley that we cover are:

  * •

Rack brokers are highly efficient, and consumes less than 2ms wall-clock time
to allocate bandwidth to as many as 100k services. The bandwidth overhead is
less than 3Mb/s when rack broker interval is 1s. Moreover, they converge to
the fair rates within a few seconds.

  * •

In an emulation, the fabric broker converges within 10s to limit the maximum
bandwidth consumption across 100 racks.

  * •

The rack broker can control the maximum utilization on the rackswitch,
ensuring predictable tail latency for services in the rack, even in the
presence of a malicious service that tries to grab all bandwidth.

  * •

Parley, unlike EyeQ, controls tail latency even if the network core is
congested, while allowing work-conserving allocations to services.

Topology and parameters: Unless otherwise noted, we use a leaf-spine topology,
where 9 rackswitches are connected to 2 spine switches in a bipartite graph as
shown in Figure 11 . There are 10 hosts under each of the 9 rackswitches. Each
host has a 10Gb/s NIC. The network is oversubscribed 1:1.25 at the rackswitch.
We use the Parley parameters shown in Table 1.

RCP aggressiveness | $\alpha$ | 0.5
---|---|---
RCP time interval | $T$ | 200$\mu$s
Rack broker frequency | $T_{\rm rack}$ | 1s
Fabric broker frequency | $T_{\rm fabric}$ | 10s
Rack broker timeout at machine broker | $T^{t}_{\rm rack}$ | 5s
Fabric broker timeout at rack broker | $T^{t}_{\rm fabric}$ | 50s
ECN marking threshold |  | 80kB
Table 1: Parameters used in evaluating Parley. Figure 11: Topology of the
testbed. The network is oversubscribed by a factor of 1.25 (100Gb/s to 80Gb/s)
at the rackswitch.

###  6.1 Machine shaper microbenchmarks

Graceful degradation during network congestion: The machine shaper senses
congestion when link utilization approaches capacity, which is not sufficient
if the network is congested. Hence, the machine shaper also uses ECN feedback
from the network to back off when links are congested. We evaluate this
scenario by having two service instances under different racks send traffic to
two their respective receivers under the same rack, but on two different
machines. We induce network congestion by disabling all but one fabric link at
the receiving rackswitch, creating a 2-to-1 over-subscription at the
rackswitch.

Figure 12 highlights an important point that the machine shaper must operate
at a fast enough timescale. At time t=0, only one service is active. At t=40s,
both services are active, causing network congestion; therefore, bandwidth is
shared almost equally (Jain’s Fairness Index is 0.99). At time t=60s, we
increased $T$ from 200$\mu$s to 1ms; notice that the machine shaper is now too
slow to guarantee fair shares across receivers, as the transport layer (TCP)
also backs off due to network congestion.

If we were allowed to change TCP to back off less aggressively, or to use UDP,
a 1ms timescale for reaction time would be sufficient. We discuss the
tradeoffs between accurate and coarse-grained rate limiting and its impact on
flow completion times in §7.

Figure 12: When there is network congestion at the rackswitch, Parley
gracefully falls back to a sharing model where receivers get (almost) equal
shares of the network bottleneck link.

###  6.2 Microbenchmarks: Rack and Fabric brokers

Bandwidth overhead: In our rack broker implementation, each machine broadcasts
its own service utilizations to other machines under the rack. Each service
can be represented as a 4B integer, and its utilization as another 4B floating
point number. At 8B per service, even 1000 bandwidth-intensive services in a
rack would generate only 8KB of data, plus some overhead for packet headers.
If there are 40 machines in a rack, unicasting this data to each machine
once/sec would cost less than 3Mb/s per machine.

Computation overhead: The rack broker repeatedly computes hierarchical max-min
shares among $N$ services. Table 2 shows the wall-clock time of computing
these shares for a single level in a hierarchy, for various values of $N$
(using one core of a 2.4GHz Linux desktop machine). We initialized demands
randomly such that the load is close to the capacity. Although our
implementation of the water-fill algorithm [bertsekas1992data, 4, Sec. 6.5.2]
is $O(N^{2})$, the wall-clock time to convergence scales well with $N$. This
is because every iteration of the water-fill satisfies the demand for _at
least_ one service, and we track demands with a precision of 1Mb/s. Thus, it
does not take more than $\sim$80000 iterations to water-fill 80Gb/s capacity.

$N$ | 100 | 1k | 10k | 100k
---|---|---|---|---
Time | 2$\mu$s | 12$\mu$s | 320$\mu$s | 1.6ms
Table 2: Average wall-clock time per iteration of max-min share computation.

Convergence speed: The hierarchical max-min algorithm converges in _one
invocation_ , and therefore the convergence speed only depends on the speed of
exchanging information and the computation time. The rack broker can also work
at the rate of 10 times per second, consuming 30Mb/s bandwidth, converging to
the allocations in 100ms. In practice, however, we found 1s time granularity
to be sufficient in ensuring isolation, as the machine shaper works at faster
timescales to ensure the network does not experience persistent congestion.

Figure 13: At t=0, we start the fabric broker, and it takes 10s for it to take
effect. However, once the fabric broker starts to allocate bandwidth, it
converges within a few iterations (at t=30s) and limits the tenant’s usage to
$<$20Mb/s, despite its bursty traffic pattern.

Fabric broker: To test the convergence of the fabric broker at large scale, we
emulated a 100 rack cluster in Mininet handigol2012reproducible [11] with one
tenant that is rate limited to 20Mb/s. Each rack has a 100Mb/s link to the
fabric; it picks another rack at random and sends a UDP data burst for 5s, and
sleeps for another 2s until t=300s (on-off). In another experiment, the
traffic is less bursty (steady): it does not sleep for 2s, but instead, it
immediately sends traffic to another random rack. The burst time is smaller
than the 10s interval at which the racks communicate with the fabric broker.
Figure 13 shows the time series of the aggregate utilization of the tenant: as
we can see, the fabric broker converges after the first burst, and within a
few iterations, the tenant is limited to its 20Mb/s, 50Mb/s, 100Mb/s, 150Mb/s,
20Mb/s and back to 100Mb/s every 50s (to illustrate convergence). In practice,
the rack broker will ensure the initial burst does not adversely affect the
performance of other services within the rack. This global service limit would
not be feasible with proposals such as EyeQ/ElasticSwitch, as the service’s
per-rack limit depends on bandwidth usages of other racks.

###  6.3 Macrobenchmarks

Policy: We demonstrate how Parley can protect the rackswitch links from
persistent congestion on a real (i.e., non-emulated) network. On each machine
in the topology, we instantiate two service endpoints A and B, each of which
is given equal bandwidth at the machine level. At the rack uplink, service A
is given at most 30Gb/s, and service B is given at least 30Gb/s, but the peak
load on the rack is limited to 60Gb/s. Recall that Parley’s final allocation
depends on the most constrained resource.

Throughput protection: One of the racks is designated as the receiver. The
traffic pattern consists of long-lived transfers between every pair of sender
and receiver (a full mesh). Figure 14 shows the utilization of each service at
the receiving rackswitch. At the start of the experiment, only service A is
active; notice that it uses only 30Gb/s. At about T=300s, we start service B,
which takes around 50s to ramp up. Parley converges faster than the time it
takes for all flows of service B to ramp up, but by the time all flows are
running at full line rate, service B is able to utilize its full 30Gb/s link
capacity. When service A finishes, service B is able to utilize all the
remaining capacity up to 60Gb/s.

Figure 14: Two services A and B sharing limited rackswitch capacity. Service A
can consume at most 30Gb/s, while service B can consume at least 30Gb/s but
the total is limited to 60Gb/s. The utilization data is obtained every second,
and the plot marks are every 30s.

Latency protection: Using the same policy as above, we show how Parley can
protect the latency of a service against high-rate adversarial traffic. We run
the same configuration as above, and both services mimic a client-server
workload with all-to-all communication between senders spread across all but
one rack, and receivers in the one remaining rack. There are 24 TCP
connections between each (service,machine) pair.

Service A initiates 200kB transfers using RPCs such that _its_ total ingress
offered load is 14% of the receivers’ rackswitch capacity. Service B uses 1MB
RPCs such that the _total ingress offered load_ on the rackswitch is 15%, 50%,
70% and $>$100%. Table 3 shows the 99th percentile FCT of 200kB RPCs, while we
varied the total load at the rackswitch. The mean RPC inter-arrival time
$t_{\mu}$ is chosen to match the load, and the inter-arrivals are sampled
uniformly at random between 0 and $2t_{\mu}$. The 99th percentile FCT is
computed after running for 20 minutes.

The results in Table 3 show, not surprisingly, that Parley does not
significantly affect latency at offered loads below 100%. The table also shows
that service A’s latency increases with the total offered load, even though
A’s offered load is constant, since it is sharing contention points with
service B. Therefore, one must assume that B is fully utilizing its maximum
bandwidth allocation when deriving a tail-latency bound for A.

These results also demonstrate that without Parley, the tail latency of
service A can become very large when B tries to increase its load past its
allocated capacity, but Parley protects A’s tail latency. Naturally, B’s own
tail latency becomes unbounded when its load exceeds its guaranteed bandwidth.
Since the over-subscription is at the receiving rackswitch, and the load is
uniformly spread across machines under that switch, Parley’s protection is
primarily due to the rack broker’s allocations.

| Total offered load at receiver rackswitch
---|---
Service | 15% | 50% | 70% |  $>100$%
| Without guarantees
A | 2.34ms | 3.50ms | 6.17ms | 939.79ms
B | 7.89ms | 7.64ms | 14.30ms | -
| With EyeQ guarantees
A | 2.33ms | 3.44ms | 6.03ms | 701.26ms
B | 9.12ms | 7.71ms | 14.19ms | -
| With Parley guarantees
A | 2.34ms | 3.42ms | 6.08ms | 38.74ms∗
B | 9.34ms | 7.62ms | 15.07ms | -
| Bounds (equation 2)
A | 9.01ms | 15.32ms | 25.53ms | 38.30ms
B | 9.77ms | 16.60ms | 27.67ms | -
Table 3: The 99th percentile RPC completion time, as a function of the total
load offered at the receiver rackswitch, with and without (w/o) Parley. The
bounds on tail latency are computed using equation 2. As indicated in
boldface, the latency without Parley suffers at high utilization.

The total load at the rackswitch was limited to 60Gb/s (or about 80% of its
capacity). For this experiment, the machine shaper iterates every 500$\mu$s to
recompute $R(t)$, and it converges (in the worst case) to within 30
iterations, to allocations within 0.01% of the ideal rate, regardless of the
number of flows jeyakumar2013eyeq [14]. In practice, we found that fewer than
15 iterations suffice. Thus, the burst size $\sigma$ can be bounded and is
dominated by the convergence time of the congestion control algorithm. Table 3
also shows the bounds on the flow completion time computed using Equation 2.
As we can see, the bounds are useful indicators of performance at high load.
The bounds are a bit pessimistic at lower loads as the bounds are calculated
making no assumptions on the arrival process; with more assumptions, they can
be improved.

Parley improves over EyeQ because it can control tail latency even when
services A and B are given work-conserving allocations, and therefore could
congest the network fabric. In this scenario, these services will saturate the
rackswitch uplink, causing overload at congestion point (iii) in Figure 2.
Since EyeQ assumes a congestion-free core it cannot control tail latency in
such scenarios; instead, EyeQ will default to a TCP-like behavior as
highlighted in Table 3.

In EyeQ, the only solution that would control tail latency would be to do
admission control on service instances, ensuring that the rack uplink
bandwidth is never over-committed. In other words, EyeQ could not support
work-conserving allocations, and instead would have to cap (for example) each
of the ten instances of both services to 3Gb/s, so as to limit the total
allocation to 60Gb/s and prevent any congestion. Such static allocations,
however, could waste a large fraction of the scarce uplink bandwidth if either
service is inactive or lightly loaded, while the other is highly loaded. In
contrast to EyeQ, Parley dynamically adjusts each service’s allocation, thus
maximizing resource utilization under the constraint of limited tail latency.

Remark: Table 3 shows results averaged over 3 runs. The standard deviation was
under 0.3ms, except (a) in the highlighted cases, where the means exceed
700ms, the std. dev. is above 100ms, and (b) in the case marked ‘*,’ where
during one run, two (out of ten) rack brokers in the receiving rack crashed.
In the latter case, the remaining eight rack brokers continued to function and
under-estimated the total ingress utilization, which resulted in excessive
99th percentile latency.222The 99th percentile latency from the three runs
were 15.54ms, 16.07ms, and 84.62ms. We have not yet re-run this experiment
with 3 bug-free runs.

##  7 Discussion

Timescales for traffic shaping: As the authors of EyeQ noted
[jeyakumar2013eyeq, 14, §2.2], rate control must be fast enough to react
before queues build up and increase latency for competing flows. However, we
also found that such fast and accurate rate control can also hurt the
completion times of RPC transfers. This insight is not specific to Parley, but
applies to any bandwidth management scheme targeted at an environment with
relatively high bandwidth and low latency.

Figure 15: To rate limit or not: Rate limiting and accurate pacing improves
sharing but increases RPC completion times.

To understand this, consider the scenario in Figure 15, where service receives
three 2.5MB RPCs at the same time, and then waits for 10ms; thus, its demand
oscillates between 0 and 6Gb/s (measured over 10ms) every 20ms. Suppose our
policy limits the service to 3Gb/s; over a period of 20ms, its usage complies
with the policy. However, over a 10ms interval (e.g., from 0–10ms), the
service exceeds its allocation by 3Gb/s.

If we use a fast-acting rate-control mechanism, the service is always
precisely rate limited, so demand from 0–10ms spills over to the next
interval. This means that all RPCs take 20ms to finish. If, however, the
service is not rate-limited at all, all of its RPCs will finish in 10ms, thus
halving the maximum completion time. This highlights a fundamental tradeoff
between accurate rate guarantees and RPC completion times. However, it is
difficult to upper bound the rate-limiting burst size, as the example in
Figure 15 still holds if RPC sizes (and timescales) are scaled up by a factor
of 10.

Thus, at the machine shaper, the service rate limiters should have a
configurable burst size for coarse-grained rate limiting, and rate meters
should have a configurable time interval to measure ingress utilizations. In
general, the burst size of a latency-sensitive service should be higher than a
collocated throughput-sensitive service. This burst size approach is a special
case of the more general _fair service curves_ stoica1997hierarchical [26], an
approach to decouple rate guarantees from delay guarantees. A rule of thumb is
to set burst sizes larger than the size of RPCs that have low-latency
requirements.

Tighter latency bounds: The latency bound shown in Equation 2 depends both on
the capacity $C$ and on the total load $\rho$ on the network queues, and
increases steeply as load increases (i.e. as $\rho\rightarrow 1$). Thus, if
the resulting latency bounds are unacceptable, either (a) low-latency RPCs
must not be exposed to load offered by other services, which can be achieved
by prioritization, or (b) network capacity should be increased. Parley helps
in two ways: (i) it can control the peak utilization at the rack
uplinks/downlinks regardless of the number of service endpoints under the
rack; (ii) Parley serves as a useful monitoring and protection mechanism for
buggy services that might consume more bandwidth than what is specified
according to a policy.

##  8 Conclusion

We presented Parley, a framework to flexibly and predictably share datacenter
bandwidth across services at the machine, rack, and fabric levels. We showed
showed how to systematically decompose a sharing objective into rack-local and
machine-local objectives. On a cluster of 90 machines, we demonstrated that
Parley is able to meet its goals. We also outlined how predictable bandwidth
shares can help services maintain low tail latencies, despite potentially
malicious traffic patterns of collocated jobs.

## References

  * [1] Hitesh Ballani et al.  “Chatty Tenants and the Cloud Network Sharing Problem”  In _USENIX NSDI_ , 2013
  * [2] Hitesh Ballani, Paolo Costa, Thomas Karagiannis and Antony Rowstron  “Towards Predictable Datacenter Networks”  In _SIGCOMM_ , 2011
  * [3] Theophilus Benson, Aditya Akella and David A Maltz  “Network Trafﬁc Characteristics of Data Centers in the Wild”  In _IMC_ , 2010
  * [4] Dimitri P Bertsekas, Robert G Gallager and Pierre Humblet  “Data networks”  Prentice-Hall International, 1992
  * [5] Arka A Bhattacharya et al.  “Hierarchical scheduling for diverse datacenter workloads”  In _SoCC_ , 2013
  * [6] “Cisco: Hierarchical Queueing Framework (HQF)”, http://www.cisco.com/en/US/docs/ios/qos/configuration/guide/qos_frhqf_support.html, Retrieved October 4, 2013
  * [7] Rene L Cruz  “A calculus for network delay. I: Network elements in isolation”  In _IEEE Transactions on Information Theory_ , 1991
  * [8] Andrew D Ferguson et al.  “Jockey: Guaranteed Job Latency in Data Parallel Clusters”  In _EuroSys_ , 2012
  * [9] Ali Ghodsi et al.  “Dominant Resource Fairness: Fair Allocation of Multiple Resource Types”  In _NSDI_ , 2011
  * [10] Albert Greenberg et al.  “VL2: a scalable and flexible data center network”  In _SIGCOMM_ , 2009
  * [11] Nikhil Handigol et al.  “Reproducible Network Experiments Using Container-based Emulation”  In _CoNEXT_ , 2012
  * [12] Peter G. Harrison  “Response time distributions in queueing network models”  In _Performance Evaluation of Computer and Communication Systems_ 729, LNCS  Springer Berlin Heidelberg
  * [13] Sushant Jain et al.  “B4: Experience with a Globally-Deployed Software Defined WAN”  In _SIGCOMM_ , 2013
  * [14] Vimalkumar Jeyakumar et al.  “EyeQ: Practical network performance isolation at the edge”  In _USENIX NSDI_ , 2013
  * [15] Vimalkumar Jeyakumar, Abdul Kabbani, Jeffrey C. Mogul and Amin Vahdat  “Technical Report: Flexible Bandwidth and Latency Provisioning in a Datacenter”, http://arxiv.org/abs/1405.0631
  * [16] Jeongkeun Lee et al.  “CloudMirror: Application-Aware Bandwidth Reservations in the Cloud”  In _USENIX HotCloud_ , 2013
  * [17] Nick McKeown et al.  “OpenFlow: enabling innovation in campus networks”  In _SIGCOMM_ , 2008
  * [18] Jeffrey C Mogul and Lucian Popa  “What We Talk About When We Talk About Cloud Network Performance”  In _SIGCOMM_ , 2012
  * [19] Daniel Pérez Palomar and Mung Chiang  “A Tutorial on Decomposition Methods for Network Utility Maximization”  In _IEEE Journal on Selected Areas in Communications_ , 2006
  * [20] Lucian Popa et al.  “ElasticSwitch: Practical Work-Conserving Bandwidth Guarantees for Cloud Computing”  In _SIGCOMM_ , 2013
  * [21] Lucian Popa et al.  “FairCloud: Sharing The Network In Cloud Computing”  In _SIGCOMM_ , 2012
  * [22] Barath Raghavan et al.  “Cloud Control with Distributed Rate Limiting”  In _SIGCOMM_ , 2007
  * [23] Henrique Rodrigues et al.  “Gatekeeper: Supporting bandwidth guarantees for multi-tenant datacenter networks”  In _USENIX WIOV_ , 2011
  * [24] Alan Shieh et al.  “Sharing the Data Center Network”  In _USENIX NSDI_ , 2011
  * [25] David Shue, Michael J Freedman and Anees Shaikh  “Performance Isolation and Fairness for Multi-Tenant Cloud Storage”  In _OSDI_ , 2012
  * [26] Ion Stoica, Hui Zhang and T. S. Eugene Ng  “A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services”  In _SIGCOMM_ , 1997
  * [27] Di Xie, Ning Ding, Y Charlie Hu and Ramana Kompella  “The Only Constant is Change: Incorporating Time-Varying Network Reservations in Data Centers”  In _SIGCOMM_ , 2012


# Securing the Classification of COVID-19 in Chest X-ray Images: A Privacy-
Preserving Deep Learning Approach

Wadii Boulila1,2, Adel Ammar1, Bilel Benjdira1, Anis Koubaa1
1RIOTU Lab, Prince Sultan University, Riyadh, Saudi Arabia
2RIADI Laboratory, National School of Computer Sciences, University of
Manouba, Manouba, Tunisia

###### Abstract

Deep learning (DL) is being increasingly utilized in healthcare-related fields
due to its outstanding efficiency. However, we have to keep the individual
health data used by DL models private and secure. Protecting data and
preserving the privacy of individuals has become an increasingly prevalent
issue. The gap between the DL and privacy communities must be bridged. In this
paper, we propose privacy-preserving deep learning (PPDL)-based approach to
secure the classification of Chest X-ray images. This study aims to use Chest
X-ray images to their fullest potential without compromising the privacy of
the data that it contains. The proposed approach is based on two steps:
encrypting the dataset using partially homomorphic encryption and
training/testing the DL algorithm over the encrypted images. Experimental
results on the COVID-19 Radiography database show that the MobileNetV2 model
achieves an accuracy of 94.2% over the plain data and 93.3% over the encrypted
data.

###### Index Terms:

Privacy preserving, deep learning, encryption, homomorphic encryption,
Paillier scheme, chest X-ray images, COVID-19.

##  I Introduction

The protection of human private data is a persistent challenge. This matter
has always been taken seriously in computer science. However, due to the
efficiency of deep learning (DL) algorithms, many have used them without any
care for the protection of private data. All have been pleased by improving
the accuracy of learning and delaying any privacy concerns.

A small interest in this topic has been raised after the deployment of remote
DL models over the internet. In fact, a variety of cloud platforms were
designed using DL models for both the training and inference phases. The
service offered by these platforms was coined later as Deep Learning as a
Service (DLaaS) [1]. Hence, private data are transferred over the internet and
may also be stored on servers with high vulnerability for leakage. The leakage
can be made in an intentional or unintentional way. It can be leaked
intentionally through hacking, piracy, or social engineering. It can also be
leaked unintentionally by the user himself or the service provider employees.
Although being unexpected, the employees are behind 43% of the whole data
leakage cases, as affirmed by Intel Security [2]. Around half of these cases
were made unintentionally.

The first event that triggered global interest in this problem is the Facebook
data privacy scandal [3]. People have discovered that Facebook has sold the
personal data of 80 million users to the British firm Cambridge Analytica to
train DL algorithms to make political advertising [4]. People have sensed that
their private data are threatened and should be protected. DL algorithms
should be accompanied during the training and inference by privacy-preserving
techniques that prevent any identification of personal data.

The proposed work in this paper focuses on this topic. We designed a data
privacy technique to keep private data protected during DL training and
inference. The data preserving technique presented in this paper is designed
for preserving Chest X-Ray images used to distinguish COVID-19 cases from
normal, lung opacity, and pneumonia cases. The DL model does not have access
to any identifiable information. It takes only as input encrypted images. The
encryption of the Chest X-Ray is done from the user side before feeding them
to the DL model. This encryption is homomorphic, which means that the final
classification result does not need any decryption of the image. The DL model
will only work with these encrypted data without requiring any personally
identifiable information. We think this feature is essential, especially in
the current COVID-19 pandemic. In fact, several research works are conducted
to show the importance of using Chest X-Ray images to detect COVID-19 cases
[5, 6, 7, 8, 9, 10]. Moreover, many people explicitly require that the body
details shown in these kinds of images must be kept private and secure [11].
The technique presented in this paper fulfills their requirement at a very low
cost (around a 1% decrease in accuracy).

The remainder of this paper is ordered as follows: in Section II, the
background section, we will discuss the research works that targeted the
topics of Privacy-Preservation Deep Learning (PPDL) and homomorphic
encryption. Later, in Section III, we will introduce our PPDL approach for
protecting COVID-19 data during the classification task. Then, in Section IV,
we will describe the experimental results that defend the utility of the
proposed approach. Finally, in Section V, we conclude our work and raise the
main limitations that should be targeted in the next research works.

##  II Background

###  II-A Privacy-Preserving Deep Learning

Data privacy is an important issue for training and testing DL models,
especially in the case of training and inferring sensitive data (e.g. health
records, financial details, location logs, and satellite images) [12, 13].
Many PPDL techniques focused on allowing multiple input parties to train and
test DL models without revealing their private data in its original form.
These techniques can be subdivided into three groups: cryptographic,
perturbation, secure enclaves, and hybrid techniques [14]. Cryptographic
methods are used to train and test DL techniques on encrypted data [15]. This
category of methods includes Homomorphic Encryption (HE), Secret Sharing (SS),
Secure Multi-Party Computation (SMPC), and Garbled Circuit (GC). The
perturbation methods aim to alter data values to maintain individual record
confidentiality [16]. This category of methods includes Differential Privacy
(DP) [17, 18, 19] and Dimensionality Reduction (DP) [20]. In secure enclaves-
based approaches [21] [22], both the prediction model and the data are
separately sent by the client and the server to a trusted, secure enclave
environment for execution. On the other hand, hybrid methods aim at combining
more than one PPDL technique to improve the privacy of data [23, 24, 25, 26].
A recent survey on privacy-preserving deep learning approaches can be found in
[27].

Nevertheless, many of these solutions are not efficient on complex data, but
only on simple classification tasks [27], such as MNIST or CIFAR-10. Besides,
they often add an important computational cost and communication overhead.
Moreover, there is always a trade-off between privacy and model accuracy, due
to the use of approximated activation functions.

Figure 1: Proposed approach.

###  II-B Homomorphic encryption

Most existing encryption algorithms do not allow working on data unless
decrypted. However, decrypting the data undermines privacy requirements. Once
the data are encrypted by someone, they must first be decrypted before
processing, which makes them vulnerable to unauthorized access.
HE removes the need for decrypting the data before usage. In other words, data
integrity and privacy are protected while processing the data [28, 29]. HE is
a cryptographic technique that has the ability to allow DL techniques to run
over encrypted data without losing context. It eliminates the tradeoff between
data usability and data privacy and ensures that data remains secure in
untrusted environments.
In the case of DL, the algorithm can be trained and tested over encrypted
data. If the DL algorithm reaches a good prediction accuracy, it can be
deployed, and therefore, in real cases, it will provide a decision over the
encrypted data. Using a unique secret key, the user can decrypt the obtained
data. Thus, the data’s privacy and security are maintained. The HE techniques
can be divided mainly into three subcategories, namely Partially Homomorphic
Encryption (PHE), Somewhat Homomorphic Encryption (SWHE), and Fully
Homomorphic Encryption (FHE). PHE enables only one form of mathematical
operation on the encrypted data. SHE enables all addition and multiplication
operations with only a limited range on the encrypted data. FHE enables
various types of assessment operations on encrypted data with an unbounded
range. PHE schemes are in general more efficient than SHE and FHE, mainly
because they are homomorphic with regard to only one type of operation
(addition or multiplication). SHE is more general than PHE since it supports
more operations; however, it can perform them on only a limited range. The
main drawback of FHE is its slow computation speed.

##  III Proposed Approach

This section describes the proposed approach for PPDL in the case of Covid-19
classification. The proposed workflow is based on two phases as depicted in
Figure 1. The first phase aims to encrypt the COVID-19 dataset using the
Paillier method. Then, the encrypted dataset is fed to the DL algorithm for
securing training. Phase 2 allows determining the class of encrypted input
images based on the trained DL model.

###  III-A HE-based Encryption

In this paper, the Paillier method is used to ensure the encryption of images.
Paillier encryption is a PHE satisfying additive homomorphism. In the
following, we describe the main concepts used in this study, which are key
generation, encryption, and homomorphic addition.

  * •

Key generation: The public key is ($n$,$g$) and the private key is
($\lambda$,$\mu$ ) computed as follows:

    1. 1.

Compute two random and independent large-prime numbers p and q, where
$\gcd(pq,(p-1)(q-1))=1$

    2. 2.

Compute n and $\lambda$, where $n=pq$ and
$\lambda=\operatorname{lcm}(p-1,q-1)$. lcm denotes the least common multiple.

    3. 3.

Select a random integer g.

    4. 4.

Compute n, where $\mu=(L(g^{\lambda}\bmod$ $n^{2}))^{{-1}}{\bmod}$ $n$ and
$L(x)={\frac{x-1}{n}}$.

  * •

Encryption: Compute the ciphertext $c$, where $c=g^{m}\cdot r^{n}{\bmod}$
$n^{2}$ and $r$ is a random number ($0<r<n$ and $gcd(r,n)=1$)

  * •

Homomorphic addition: The product of two ciphertexts will be decrypted to the
sum of their corresponding plaintexts: $D(E(m_{1},r_{1})\cdot
E(m_{2},r_{2}){\bmod n}^{2})=(m_{1}+m_{2}){\bmod}$ $n$, and the product of a
ciphertext with a plaintext will be decrypted to the sum of the corresponding
plaintexts: $D(E(m_{1},r_{1})\cdot g^{{m_{2}}}{\bmod
n}^{2})=(m_{1}+m_{2}){\bmod}$ $n$.

###  III-B Secure Training

The goal of the secure training is to run the DL algorithm on the encrypted
dataset and be able to achieve good performance on identifying the different
classes.
The purpose of the presented work is to evaluate the performance of DL
algorithms over Paillier-encrypted images. The main challenge is to find a
trade-off between the accuracy of the DL algorithm in identifying COVID-19
classes and the security of images. To assess the first point, a good
alternative will be to check the performance of the selected DL algorithms on
plain and encrypted data. In case of a small difference between the accuracy
of the DL algorithm on plain and encrypted data, we can assert that it
performs well and can be adopted in real cases. Otherwise, the encryption
method used for the PPDL is not adequate since it doesn’t allow the DL
algorithm to learn from encrypted images.
In this paper, we have used MobileNetV2, which is a CNN composed of 53 layers.
MobileNetV2 algorithm can be replaced by any other transfer learning
algorithm. Figure 2 depicts the architecture of the secure training algorithm
used in this study.

Figure 2: Architecture of the secure training algorithm.

##  IV Experimental Results

This section is divided into three parts: dataset description, image
encryption results, and CNN classification performances.

###  IV-A Dataset Description

In this paper, the COVID-19 Radiography database is used [30, 31]. It is a
public dataset that contains four classes, namely COVID-19, viral pneumonia,
normal, and lung opacity. The dataset is randomly split into 80% for training,
10% for validation, and 10% for testing. Table I shows the number of images
used for training, validation, and testing for each class.

TABLE I: Dataset Partition Class | Training | Validation | Testing
---|---|---|---
COVID-19 | 2801 | 350 | 350
Lung Opacity | 4801 | 601 | 601
Normal | 5403 | 675 | 676
Viral pneumonia | 963 | 120 | 121

###  IV-B Implementation Details

The experiments are carried out using a server with the following
configuration properties: an x64-based processor, an Intel(R) Xeon(R) Gold
5218 CPU @ 2.30GHz, and a 512 GB RAM, with 8 GPUs (NVIDIA Quadro RTX 8000, 48
GB), running on Ubuntu 18.04 . The DL networks are programmed under Python 3.7
programming language. We used both the Keras 2.6 library and the TensorFlow-
GPU 2.3 backend.

###  IV-C Results

The first step is to encrypt the dataset using the Paillier encryption scheme.
Figure 3 depicts a sample of image encryption for the four classes COVID-19,
viral pneumonia, normal, and lung opacity.

Figure 3: Sample of plain and encrypted images for each class.

Then, the proposed DL architecture is applied to both plain and encrypted
datasets. The training and validation accuracy of the MobileNetV2 with plain
and encrypted data are depicted in Figures 4 and 5, respectively. The maximum
validation accuracy for the plain dataset is 95.04% obtained at the epoch 74.
Whereas, the maximum validation accuracy for the encrypted dataset is 94.97%
obtained at the epoch 77.
In order to assess more robustly the performance on each dataset, we
calculated the confusion matrix on the testing part which did not participate
in any way in the training procedure nor in the selection of the best weights.
Figures 6 and 7 show the resulting confusion matrices for the plain and
encrypted datasets, respectively. In both cases, most misclassified images
(76% and 67% of all misclassifications for the plain and encrypted datasets,
respectively) are between the ’Normal’ and ’Lung opacity’ classes. Tables II
and III show the detailed results, in terms of precision, recall, and
f1-score, on the testing set of the plain and encrypted data, respectively. We
notice that the ’Viral Pneumonia’ class is the most affected by the encryption
process, with an f1-sore decreasing from 98.3% to 87.6%, due to the reduced
number of images for this class (7% of the dataset) while the three other
classes were much less affected. The difference in terms of overall
classification accuracy between encrypted (94.22%) and plain (93.25%) data is
less than 1% on the testing set. Hence, we can conclude that the Paillier
encryption scheme ensures the privacy of data while also maintaining a highly
accurate prediction of the class type in the COVID-19 Radiography dataset.

Figure 4: Training and validation accuracy of the plain dataset. Figure 5: Training and validation accuracy of the encrypted dataset. Figure 6: Confusion matrix on the test part of the dataset of plain images. Figure 7: Confusion matrix on the test part of the dataset of encrypted images. TABLE II: Classification results on the testing set of the plain data. | precision | recall | f1-score | support
---|---|---|---|---
Covid | 0.994 | 0.949 | 0.971 | 350
Lung_Opacity | 0.953 | 0.903 | 0.927 | 601
Normal | 0.902 | 0.967 | 0.934 | 676
Viral_Pneumonia | 0.992 | 0.975 | 0.983 | 121
Accuracy |  |  | 0.942 | 1748
Macro avg | 0.96 | 0.949 | 0.954 | 1748
Weighted avg | 0.944 | 0.942 | 0.942 | 1748
TABLE III: Classification results on the testing set of the encrypted data. | precision | recall | f1-score | support
---|---|---|---|---
Covid | 0.986 | 0.980 | 0.983 | 350
Lung_Opacity | 0.921 | 0.912 | 0.916 | 601
Normal | 0.908 | 0.953 | 0.930 | 676
Viral_Pneumonia | 0.990 | 0.785 | 0.876 | 121
Accuracy |  |  | 0.932 | 1748
Macro avg | 0.951 | 0.907 | 0.926 | 1748
Weighted avg | 0.934 | 0.932 | 0.932 | 1748

##  V Conclusion

HE-based encryption has been used in many research works due to its
significant privacy benefits. The increasing need of ensuring privacy-
preserving of data while using DL techniques makes HE a very attractive topic
to the research community. In this paper, we propose using the PHE-based
Paillier algorithm to tackle the problem of the privacy of sensitive
healthcare data when using DL algorithms. The Paillier encryption enables
securing the data and preserving good classification accuracy. Experiments
conducted on the COVID-19 Radiography database show an accuracy of 94.2% for
plain data and 93.3% for encrypted data. In this sense, the proposed research
can serve as a tool to classify encrypted data by non-trustworthy third
parties without disclosing confidentiality. However, the main limitation of HE
encryption is its slow computation, which remains the major problem of this
technique. Further studies will focus on proposing hybrid encryption
techniques such as FHE encryption and SSC that can be used in conjunction with
one another.

## References

  * [1] S. Latif, M. Driss, W. Boulila, Z. e. Huma, S. S. Jamal, Z. Idrees, and J. Ahmad, “Deep learning for the industrial internet of things (iiot): A comprehensive survey of techniques, implementation frameworks, potential applications, and future directions,” _Sensors_ , vol. 21, no. 22, p. 7518, 2021.
  * [2] F. Mireshghallah, M. Taram, P. Vepakomma, A. Singh, R. Raskar, and H. Esmaeilzadeh, “Privacy in deep learning: A survey,” _arXiv preprint arXiv:2004.12254_ , 2020.
  * [3] B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi, and Z. Lin, “When machine learning meets privacy: A survey and outlook,” _arXiv preprint arXiv:2011.11819_ , 2020.
  * [4] S. Meredith, “Facebook-cambridge analytica: A timeline of the data hijacking scandal,” ttps://www.cnbc.com/2018/04/10/facebook-cambridge-analytica-a-timeline-of-the-data-hijacking-scandal.html, 2018, accessed: 2021-11-18.
  * [5] W. Taylor, Q. H. Abbasi, K. Dashtipour, S. Ansari, S. A. Shah, A. Khalid, and M. A. Imran, “A review of the state of the art in non-contact sensing for covid-19,” _Sensors_ , vol. 20, no. 19, p. 5665, 2020.
  * [6] S. B. Atitallah, M. Driss, W. Boulila, and H. B. Ghézala, “Randomly initialized convolutional neural network for the recognition of covid-19 using x-ray images,” _International Journal of Imaging Systems and Technology_ , vol. 32, no. 1, pp. 55–73, 2022.
  * [7] S. Ben Atitallah, M. Driss, W. Boulila, A. Koubaa, and H. Ben Ghézala, “Fusion of convolutional neural networks based on dempster–shafer theory for automatic pneumonia detection from chest x-ray images,” _International Journal of Imaging Systems and Technology_ , 2021.
  * [8] M. Rehman, R. A. Shah, M. B. Khan, N. A. A. Ali, A. A. Alotaibi, T. Althobaiti, N. Ramzan, S. A. Shaha, X. Yang, A. Alomainy _et al._ , “Contactless small-scale movement monitoring system using software defined radio for early diagnosis of covid-19,” _IEEE Sensors Journal_ , 2021.
  * [9] S. Guefrechi, M. B. Jabra, A. Ammar, A. Koubaa, and H. Hamam, “Deep learning based detection of covid-19 from chest x-ray images,” _Multimedia Tools and Applications_ , vol. 80, no. 21, pp. 31 803–31 820, 2021.
  * [10] M. Ben Jabra, A. Koubaa, B. Benjdira, A. Ammar, and H. Hamam, “Covid-19 diagnosis in chest x-rays using deep learning and majority voting,” _Applied Sciences_ , vol. 11, no. 6, 2021. [Online]. Available: https://www.mdpi.com/2076-3417/11/6/2884
  * [11] W. Boulila, S. A. Shah, J. Ahmad, M. Driss, H. Ghandorh, A. Alsaeedi, M. Al-Sarem, and F. Saeed, “Noninvasive detection of respiratory disorder due to covid-19 at the early stages in saudi arabia,” _Electronics_ , vol. 10, no. 21, p. 2701, 2021.
  * [12] W. Boulila, H. Ghandorh, M. A. Khan, F. Ahmed, and J. Ahmad, “A novel cnn-lstm-based approach to predict urban expansion,” _Ecological Informatics_ , vol. 64, p. 101325, 2021.
  * [13] M. Jemmali, L. K. B. Melhim, A. Alourani, and M. M. Alam, “Equity distribution of quality evaluation reports to doctors in health care organizations,” _PeerJ Computer Science_ , vol. 8, p. e819, 2022.
  * [14] J. Liu and X. Meng, “Survey on privacy-preserving machine learning,” _Journal of Computer Research and Development_ , vol. 57, no. 2, p. 346, 2020\.
  * [15] M. Alkhelaiwi, W. Boulila, J. Ahmad, A. Koubaa, and M. Driss, “An efficient approach based on privacy-preserving deep learning for satellite image classification,” _Remote Sensing_ , vol. 13, no. 11, p. 2221, 2021.
  * [16] M. A. P. Chamikara, P. Bertók, D. Liu, S. Camtepe, and I. Khalil, “Efficient data perturbation for privacy preserving and accurate data stream mining,” _Pervasive and Mobile Computing_ , vol. 48, pp. 1–19, 2018.
  * [17] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy.” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3-4, pp. 211–407, 2014.
  * [18] N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, and K. Talwar, “Semi-supervised knowledge transfer for deep learning from private training data,” _arXiv preprint arXiv:1610.05755_ , 2016.
  * [19] Z. Bu, J. Dong, Q. Long, and W. J. Su, “Deep learning with gaussian differential privacy,” _Harvard data science review_ , vol. 2020, no. 23, 2020.
  * [20] T. Chanyaswad, J. M. Chang, and S.-Y. Kung, “A compressive multi-kernel method for privacy-preserving machine learning,” in _2017 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2017, pp. 4079–4086.
  * [21] F. Tramer and D. Boneh, “Slalom: Fast, verifiable and private execution of neural networks in trusted hardware,” _arXiv preprint arXiv:1806.03287_ , 2018.
  * [22] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa, “Oblivious multi-party machine learning on trusted processors,” in _25th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 16)_, 2016, pp. 619–636.
  * [23] N. Kumar, M. Rathee, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow: Secure tensorflow inference,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 336–353.
  * [24] S. Truex, N. Baracaldo, A. Anwar, T. Steinke, H. Ludwig, R. Zhang, and Y. Zhou, “A hybrid approach to privacy-preserving federated learning,” in _Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security_ , 2019, pp. 1–11.
  * [25] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “GAZELLE: A low latency framework for secure neural network inference,” in _27th USENIX Security Symposium (USENIX Security 18)_ , 2018, pp. 1651–1669.
  * [26] M. Chase, R. Gilad-Bachrach, K. Laine, K. Lauter, and P. Rindal, “Private collaborative neural network learning,” _Cryptology ePrint Archive_ , 2017\.
  * [27] H. C. Tanuwidjaja, R. Choi, S. Baek, and K. Kim, “Privacy-preserving deep learning on machine learning as a service—a comprehensive survey,” _IEEE Access_ , vol. 8, pp. 167 425–167 447, 2020.
  * [28] P. V. Parmar, S. B. Padhar, S. N. Patel, N. I. Bhatt, and R. H. Jhaveri, “Survey of various homomorphic encryption algorithms and schemes,” _International Journal of Computer Applications_ , vol. 91, no. 8, 2014.
  * [29] F. Armknecht, C. Boyd, C. Carr, K. Gjøsteen, A. Jäschke, C. A. Reuter, and M. Strand, “A guide to fully homomorphic encryption.” _IACR Cryptol. ePrint Arch._ , vol. 2015, p. 1192, 2015.
  * [30] M. E. Chowdhury, T. Rahman, A. Khandakar, R. Mazhar, M. A. Kadir, Z. B. Mahbub, K. R. Islam, M. S. Khan, A. Iqbal, N. Al Emadi _et al._ , “Can ai help in screening viral and covid-19 pneumonia?” _IEEE Access_ , vol. 8, pp. 132 665–132 676, 2020.
  * [31] T. Rahman, A. Khandakar, Y. Qiblawey, A. Tahir, S. Kiranyaz, S. B. A. Kashem, M. T. Islam, S. Al Maadeed, S. M. Zughaier, M. S. Khan _et al._ , “Exploring the effect of image enhancement techniques on covid-19 detection using chest x-ray images,” _Computers in biology and medicine_ , vol. 132, p. 104319, 2021.