because we have considered a scenario in which: i) the capacity of the wired
portion of the network is overprovisioned; ii) the AP/STAs can buffer
unlimited amount of data for each flow; iii) the wireless channel is error-
free. What happens when the above assumptions do not hold?

We can expect that factors preventing MU-MIMO from achieving its maximum
capacity gains under ideal conditions (i.e., in the absence of losses) persist
also under non-ideal conditions (i.e., in the presence of losses), leading to
even worse throughput. Here, we explore this issue in exemplary scenarios as
follows, for both the downlink and uplink bottleneck regime.

Figure 3.13: Impact of finite buffer size at the AP, in the downlink
bottleneck regime with $B_{\textrm{\tiny AP}}=B_{\textrm{\tiny STA}}$.

Fig. 3.13 shows TCP throughput obtained by simulation in the reference
scenario with $K=4$ stations, $D=0$, under the downlink bottleneck regime (the
analogous of Fig. 3.5). We assume now that the AP can buffer a finite number
$B$ of data packets for each flow, and consider $B=100,50,10$. Here, TCP flows
suffer from losses due to buffer overflow at the AP, limiting their congestion
window size as dictated by the congestion control algorithm (in our case,
NewReno). Since aggregation of a number of data frames larger that the buffer
size is impossible, curves flatten for $B_{\textrm{\tiny AP}}\geq B$. A small
overshoot is observed when $B_{\textrm{\tiny AP}}$ approaches $B$ from below.

Figure 3.14: Throughput obtained by simulation in the reference system, with
$B_{\textrm{\tiny AP}}=\infty$, $D=0$, $K=4$ as function of $B_{\textrm{\tiny
STA}}$, for different values of packet loss probability.

Fig. 3.14 shows TCP throughput obtained by simulation in the reference
scenario with $K=4$ stations, $D=0$, under the same MAC and physical-layer
assumptions considered in Fig. 3.7, where we observed, in the absence of
losses, the onset of the uplink bottleneck regime. We now ask whether the
presence of losses can cause the network to not enter the uplink bottleneck
regime. The answer to this question is in the affirmative since, by increasing
the loss probability we make TCP flows operate at smaller and smaller window
sizes, eventually leading to the condition in which station queues are no
longer saturated, and performance gets limited by TCP dynamics, rather than by
wireless channel dynamics. In this respect, the (poor) throughput obtained in
the absence of losses (when we get into the uplink bottleneck regime), acts as
an upper bound to the throughput achievable with the addition of losses.

To show this fact, we introduce an artificial (Bernoulli) loss probability $p$
in the downlink, which could model non-ideal conditions due to i) congestion
in the wired network, ii) residual errors on the wireless channel not
automatically recovered by the MAC protocol.

With loss probability $0.1\%$, we obtain a curve similar to that obtained in
the uplink bottleneck regime (achieved under zero losses). We also observe
that increasing the aggregation size at the STA beyond about 10 does not
provide any benefit, which can be explained by the fact that frame aggregation
performed at the STAs gets limited by the TCP window size. Higher loss
probabilities lead to further throughput reductions: when TCP flows operate at
too small window size, MAC-layer dynamics are no longer the bottleneck
(actually we are no longer in the uplink bottleneck regime), and overall
performance is essentially determined by TCP dynamics in response to losses
and end-to-end delay.

##  Chapter 4 Passive AP-side Estimation and Decomposition of WLAN Latency

This chapter presents the design of Uplink Latency Microscope (uScope) which
enables a passive AP-side estimation of WLAN uplink latency and its
constituent components. In Sec. 4.1, we present the high level problem
formulation followed by a description of uScope framework in Sec. 4.2.

###  4.1 High Level Problem Formulation

Let $t_{\textrm{enq}}$ denote the time at which a particular packet to be
analyzed is enqueued at the STA and $t_{\textrm{rx\\_end}}$ denote the time
when the AP successfully receives the packet. Our goal is to enable the AP to
passively compute the mean uplink latency ($\bar{L}_{\textrm{uplink}}$), i.e.,
the average duration between $t_{\textrm{enq}}$ and $t_{\textrm{rx\\_end}}$
for any of its associated STAs. Further for each associated STA, the AP should
break down the mean uplink latency into its constituent components. While
doing so, the AP cannot perform any active measurements (such as probing),
cannot seek any STA side co-operation, does not have any additional hardware
infrastructure (e.g., a network of sniffers) for collecting extra measurements
and is thus constrained to make an estimate solely based on passive AP side
observations.

For ease of discussion, the associated STA under consideration is hereby
referred to as the target STA. Our network scenario comprises multiple BSSs
co-existing together. Remaining STAs from the same and neighboring BSSs as
well as APs from neighboring BSSs are hereby referred to as non-target STAs.
The notations used in this and the following sections are summarized in Table
4.1.

To understand the components of $\bar{L}_{\textrm{uplink}}$ and the challenges
in estimating $\bar{L}_{\textrm{uplink}}$ and these components based on
passive AP-side observations, consider the journey of a packet from when it
gets enqueued at the target STA until it reaches the AP successfully. It is
possible that when the packet gets enqueued, the target STA’s queue already
has a backlog of previously queued packets that are waiting to get serviced.
Consequently, prior to reaching the head of the queue at time denoted by
$t_{\textrm{head}}$, the packet will experience a queuing delay of
$t_{\textrm{head}}-t_{\textrm{enq}}$. The average queuing delay is denoted by
$\bar{\Phi}_{\textrm{queuing}}$. If the target STA has multiple flows pushing
packets into the layer 2 queue, the average queuing delay
$\bar{\Phi}_{\textrm{queuing}}$ will have contributions from each of these
flows and consequently,
$\bar{\Phi}_{\textrm{queuing}}=\sum_{i=1}^{N}\bar{\Phi}_{q,i}$ where
$\bar{\Phi}_{q,i}$ denotes the average contribution to
$\bar{\Phi}_{\textrm{queuing}}$ from the $i^{th}$ flow from the target STA.

Figure 4.1: An example timeline to denote $t_{\textrm{head}}$,
$t_{\textrm{rx\\_start}}$, $t_{\textrm{rx\\_end}}$ and
$t_{\textrm{tx\\_end}}$. Here the target STA (STA 1) makes one retransmission
and defers twice each to STA 2 and AP.

When the packet reaches the head of the queue at $t_{\textrm{head}}$, the STA
chooses a random backoff and begins to contend in accordance with the rules of
802.11 to gain access to the wireless channel. As depicted in Fig. 4.1, the
target STA contending for channel access might have to defer as some non-
target STA captures the channel. It is also possible that the target STA
captures the channel and makes an unsuccessful transmission (due to
collisions, channel errors, etc.) forcing the STA to double its contention
window size, choose another random backoff and attempt again. Finally, after
several retransmission attempts the AP successfully receives the packet. The
start time of this reception is denoted by $t_{\textrm{rx\\_start}}$. We
define the duration between $t_{\textrm{head}}$ and $t_{\textrm{rx\\_start}}$
as the uplink channel access delay with its mean value denoted by
$\bar{\Phi}_{\textrm{access}}$.

Recall that the AP is constrained to estimate $\bar{L}_{\textrm{uplink}}$,
$\bar{\Phi}_{\textrm{queuing}}$, $\bar{\Phi}_{q,i}$ and
$\bar{\Phi}_{\textrm{access}}$ based on passive observations. Consequently,
the AP encounters a few challenges. First, these parameters are determined by
the joint effect of a number of factors such as network topology, interfering
links to the target STA (from same BSS as well as neighboring BSSs), user
activity, traffic load of interfering nodes, their PHY capabilities, data
rates, etc. These factors are not directly observable by the AP. Further, for
each packet received on the uplink by the AP, it cannot directly observe
$t_{\textrm{enq}}$ and $t_{\textrm{head}}$. As a result, the AP cannot
estimate $\bar{L}_{\textrm{uplink}}$, $\bar{\Phi}_{\textrm{queuing}}$ and
$\bar{\Phi}_{\textrm{access}}$ based on direct observation of uplink
transmissions from the target STA. Since the AP is unaware of
$t_{\textrm{enq}}$ and $t_{\textrm{head}}$, for a packet received on the
uplink from a target STA, the AP cannot directly observe which of the target
STA’s flows contributed to the queuing delay of the observed packet and the
amount of contribution made.111Under the assumption that the target STA is
fully backlogged, $t_{\textrm{head}}$ for a given packet is indeed the end
time of the preceding packet’s transmission. However, devices can also have
idle times based on user activity.

The mean uplink channel access delay ($\bar{\Phi}_{\textrm{access}}$) is
affected by two key factors - (i) the number of retransmissions the STA has to
make and (ii) the amount of time the STA defers prior to
$t_{\textrm{rx\\_start}}$. We denote the average number of retransmissions and
the mean defer time per packet transmission by $\bar{R}$ and
$\bar{\Psi}_{\textrm{defer}}$ respectively. Passive estimation of these
parameters is challenging as the AP is unaware of which non-target STAs the
target STA defers to as some of them may be hidden from the AP. This prevents
the AP from directly observing the amount of time the channel is kept busy by
hidden non-target STAs. The AP also cannot directly count the number of
retransmissions from a target STA. Consequently, based on passive
observations, the AP cannot directly compute $\bar{\Psi}_{\textrm{defer}}$ and
$\bar{R}$ for a target STA.

Finally, as the STA makes a successful transmission, it occupies the channel
for a time which includes any MAC layer overhead, interframe spacings, data
transmission time and the time to send the MAC layer acknowledgement. The
average duration between the start of the successful transmission and its
completion is the mean transmission delay ($\bar{\Phi}_{\textrm{tx}}$).

Thus the mean uplink latency ($\bar{L}_{\textrm{uplink}}$), which is the
average duration between $t_{\textrm{enq}}$ and $t_{\textrm{rx\\_end}}$, has
contributions from three components as follows

$\bar{L}_{\textrm{uplink}}=\bar{\Phi}_{\textrm{queuing}}+\bar{\Phi}_{\textrm{access}}+\bar{\Phi}_{\textrm{tx}}.$
(4.1)

Our objective is to enable the AP to passively estimate
$\bar{L}_{\textrm{uplink}}$ and decompose it into its components. Since
$\bar{\Phi}_{\textrm{tx}}$ can be directly observed by the AP, we focus only
on $\bar{\Phi}_{\textrm{queuing}}$ and $\bar{\Phi}_{\textrm{access}}$. As
stated previously, the AP should be able to further decompose these two
components. Thus, the target STA can have an arbitrary number of flows
contributing to $\bar{\Phi}_{\textrm{queuing}}$ and the AP should be able to
infer their individual contributions ($\Phi_{q,i}$). Further, the AP should
also be able to estimate $\bar{R}$ and $\bar{\Psi}_{\textrm{defer}}$ which
affect $\bar{\Phi}_{\textrm{access}}$ for the target STA. Note that
$\bar{L}_{\textrm{uplink}}$, $\bar{\Phi}_{\textrm{access}}$,
$\bar{\Psi}_{\textrm{defer}}$, $\bar{R}$, $\bar{\Phi}_{\textrm{queuing}}$ and
$\bar{\Phi}_{q,i}$ can vary from STA to STA depending on their traffic load
and the network conditions experienced by the individual STA.

Table 4.1: Definition of parameters used in the estimation and decomposition technique $t_{\textrm{enq}}$ |  time when a packet is enqueued at the target STA
---|---
$t_{\textrm{head}}$ |  time when a packet reaches the head of the target STA queue
$t_{\textrm{rx\\_start}}$ |  time when the packet reception starts at the AP
$t_{\textrm{rx\\_end}}$ |  time when an uplink packet reception is complete
$t_{\textrm{tx\\_end}}$ |  time when a downlink packet transmission is complete
$t_{\textrm{tx\\_end}}^{\textrm{seg}}$ |  time when TCP segment transmission on the downlink is complete
$t_{\textrm{enq}}^{\textrm{ack}}$ |  time when TCP ACK is enqueued at the target STA
$t_{\textrm{head}}^{\textrm{ack}}$ |  time when TCP ACK reaches the head of the STA queue
$t_{\textrm{rx\\_start}}^{\textrm{ack}}$ |  time when TCP ACK reception starts at the AP
$t_{\textrm{rx\\_end}}^{\textrm{ack}}$ |  time when TCP ACK reception on the uplink is complete
$t_{\textrm{rx\\_start}}^{\textrm{int(N)}}$ |  time when the reception of the $N^{th}$ intermediate uplink packet from the target STA starts. An intermediate uplink packet is a packet received by the AP from the target STA between $t_{\textrm{tx\\_end}}^{\textrm{seg}}$ and $t_{\textrm{rx\\_start}}^{\textrm{ack}}$
$t_{\textrm{rx\\_end}}^{\textrm{int(N)}}$ |  time when the reception of the $N^{th}$ intermediate uplink packet from the target STA ends.
$\bar{\Phi}_{\textrm{queuing}}$ |  the average queuing delay at the target STA.
$\bar{\Phi}_{q,i}$ |  the average contribution of the $i^{th}$ flow from the target STA to $\bar{\Phi}_{\textrm{queuing}}$.
$\bar{\Phi}_{\textrm{access}}$ |  the average access delay for the target STA.
$\bar{\Phi}_{\textrm{tx}}$ |  the average transmit delay. This duration includes time to transmit the packet, any MAC layer overhead and interframe spacings.
$\bar{L}_{\textrm{uplink}}$ |  the average uplink latency for a target STA.
$\bar{R}$ |  the average number of retransmissions faced before a packet is successfully transmitted on the uplink by the target STA.
$\bar{\Psi}_{\textrm{defer}}$ |  the average defer time faced by the target STA for an uplink transmission.
$\bar{\theta}_{\textrm{defer,k}}$ |  the average defer time faced by the target STA in the $k^{th}$ retransmission attempt.
$\bar{\theta}_{\textrm{contn,k}}$ |  the average contention time for the $k^{th}$ retransmission attempt.
$\bar{\theta}_{\textrm{occ,k}}$ |  the average amount of time for which the channel is occupied in the $k{th}$ retransmission attempt.

###  4.2 uScope Framework

This section presents uScope , a tool to perform AP-side estimation and
decomposition of WLAN uplink latency for each of its associated STAs. We first
present virtual probing, the key idea for estimation and decomposition of WLAN
uplink latency in Sec. 4.2.1. Sec. 4.2.2 and 4.2.3 describe how by leveraging
virtual probing, uScope performs the estimation and decomposition.

####  4.2.1 TCP Handshake as a Virtual Probe

Consider a layer-4 handshake: The STA receives a TCP segment from the AP on
the downlink sent by any arbitrary server on the internet. Since the WLAN is
the last hop for this TCP segment, reception of this segment results in the
generation of a TCP ACK. This layer-4 handshake exposes three key attributes
that are not directly observable to the AP.

(i) Uplink enqueue timestamp. The STA will attempt to return the TCP ACK as
fast as possible. In other words, when the handshake occurs, the time when the
TCP ACK gets enqueued is approximately the time when the TCP segment is
received on the downlink from the AP. Therefore, the enqueue timestamp for the
TCP ACK can be inferred by the AP as $t_{\textrm{enq}}^{\textrm{ack}}\approx
t_{\textrm{tx\\_end}}^{\textrm{seg}}$.

(ii) Uplink aggregate layer-2 delay. After the layer-4 ACK gets enqueued at
the STA, it experiences queuing delay as the STA transmits previously
backlogged packets, if any. As the ACK reaches the head of the queue, it
experiences additional delays from uplink contention, deferral,
retransmissions and uplink transmission prior to reaching the AP. Thus, the
duration between the transmission of a TCP segment to reception of TCP ACK is
a sum of all layer-2 delays that any packet transmitted by the STA would
encounter.

(iii) Uplink backlog state indicator. In the time interval between
transmission of the TCP segment to reception of the TCP ACK, the STA is
guaranteed to be backlogged with at least one packet, the TCP ACK. As a
result, until the AP receives the TCP ACK, the STA’s queue can be considered
to be in a backlogged state. Any other packet received from the STA in this
period of time can be considered to be already present in the queue when the
TCP ACK gets enqueued.

uScope leverages these three inferences obtained from a layer-4 handshake to
estimate total uplink latency and its constituent components as described in
the following subsections. Thus, the methodology used in uScope is to perform
an assessment of uplink latency by leveraging layer-4 handshakes from TCP
flows in which the target STA receives data. Analogous to active probing (e.g,
ping) where the AP generates probe requests and the STA sends probe responses,
uScope leverages TCP handshakes as virtual probes. However, unlike active
probing, this methodology does not increase the traffic load as it leverages
layer-4 handshakes that would anyways occur due to TCP. Further, since uScope
leverages the fundamental closed loop property of TCP flows, the handshakes
can be a part of any TCP flow in which the target STA receives data (e.g., a
Netflix video stream).

####  4.2.2 Timing Analysis on Virtual Probes for Delay Estimation

For every packet received on the uplink, the AP can directly observe the
timestamps for reception start ($t_{\textrm{rx\\_start}}$) and reception end
($t_{\textrm{rx\\_end}}$). Further, for each packet transmitted on the
downlink, the AP can observe the timestamp corresponding to the end of the
transmission ($t_{\textrm{tx\\_end}}$). This section describes how virtual
probing enables uScope to estimate the total uplink latency, access delay and
queuing delay based on these timestamps for TCP segments and ACKs.

#####  4.2.2.1 Total Uplink Latency Estimation

The key challenge faced in estimation of the total uplink latency
($\bar{L}_{\textrm{uplink}}$) is that the AP cannot not directly observe the
enqueue timestamp ($t_{\textrm{enq}}$) for a packet received on the uplink
from a target STA. Inferring $t_{\textrm{enq}}$ for all or a subset of packets
received on the uplink would enable the AP to use $t_{\textrm{rx\\_end}}$ (a
directly observable parameter at the AP-side) and $t_{\textrm{enq}}$
corresponding to such packets to obtain $\bar{L}_{\textrm{uplink}}$. However,
as stated previously, when a layer-4 handshake occurs, the time at which the
TCP ACK gets enqueued is approximately the time at which the TCP segment is
received, i.e., $t_{\textrm{enq}}^{\textrm{ack}}\approx
t_{\textrm{tx\\_end}}^{\textrm{seg}}$. Therefore, for these TCP ACKs, the
enqueue timestamp can be inferred at the AP-side. uScope leverages this key
idea to estimate the total uplink latency for a target STA as

$\bar{L}_{\textrm{uplink}}=\overline{\big{(}t_{\textrm{rx\\_end}}^{\textrm{ack}}-t_{\textrm{tx\\_end}}^{\textrm{seg}}\big{)}}.$

#####  4.2.2.2 Uplink Access Delay Estimation

(a) Queued ACK handshake

(b) Immediate ACK handshake

Figure 4.2: Timeline to show queued ACK handshake and immediate ACK handshake.
In the illustration, STA 1 is the target STA and STA 2 is the non-target STA.
In queued ACK handshake shown in (a), there is one intermediate transmission
between $t_{\textrm{tx\\_end}}^{\textrm{seg}}$ and
$t_{\textrm{rx\\_start}}^{\textrm{ack}}$. In the immediate ACK handshake shown
in (b), the AP does not receive any intermediate transmissions from the target
STA before receiving the TCP ACK.

To estimate the access delay, the key information missing at the AP is the
time when the packet reached the head of the STA queue ($t_{\textrm{head}}$).
Suppose that there is a time interval in which the target STA’s queue is
backlogged with a few packets. Each packet will reach the head of the queue at
the end time of the transmission of the previous packet and thus the AP can
infer $t_{\textrm{head}}$ for each packet received in this duration on the
uplink. This inference, combined with the time of reception start
($t_{\textrm{rx\\_start}}$), which is directly observable at the AP, can help
compute the access delay that the STA encounters. Unfortunately, the AP cannot
directly observe time intervals when a STA’s queue is backlogged as the STA
can have some idle times based on user activity. However, virtual probing
provides a unique opportunity to the AP: Recall that the STA is guaranteed to
be backlogged until the TCP ACK is received, i.e., in the interval from
$t_{\textrm{tx\\_end}}^{\textrm{seg}}$ to
$t_{\textrm{rx\\_end}}^{\textrm{ack}}$. Therefore, by using packets received
on the uplink from the target STA in this duration, uScope can estimate the
uplink access duration as follows.

Let us say that the AP observes $N$ transmissions from the target STA between
$t_{\textrm{tx\\_end}}^{\textrm{seg}}$ and
$t_{\textrm{rx\\_start}}^{\textrm{ack}}$. We term such transmissions as
intermediate transmissions. Handshakes with $N>0$ are referred to as queued
ACK handshakes and those with $N=0$ are termed as immediate ACK handshakes.
Fig. 4.2 shows an illustration of these two handshakes. uScope analyses the
timestamps of the packets received from the target STA during these handshakes
to obtain instantaneous values of access delay as follows.
$\bar{\Phi}_{\textrm{access}}$ is computed by averaging over all these values.

(a) Queued ACK handshake: In such a case, the STA queue is not empty when the
TCP ACK is enqueued. Consequently, the AP witnesses transmission of previously
queued packets as intermediate transmissions prior to reception of the TCP ACK
on the uplink. The queued ACK handshake provides instantaneous values of
uplink access delay in two ways. One measurement is provided by each of the
intermediate transmissions and then one comes from the TCP ACK as follows. For
the $j^{th}$ intermediate transmission ($1<j\leq N$),
$t_{\textrm{head}}^{int(j)}=t_{\textrm{rx\\_end}}^{int(j-1)}$. Consequently,
the instantaneous value of uplink access delay is given by
$\big{(}t_{\textrm{rx\\_start}}^{int(j)}-t_{\textrm{rx\\_end}}^{int(j-1)}\big{)}$.
The TCP ACK reaches the head of the queue after the $N^{th}$ intermediate
transmission. Consequently, for the TCP ACK, the instantaneous value of uplink
access delay is given by
$\big{(}t_{\textrm{rx\\_start}}^{\textrm{ack}}-t_{\textrm{rx\\_end}}^{\textrm{int(N)}}\big{)}$.

(b) Immediate ACK handshakes: In this case, the STA queue is empty when the
TCP ACK gets enqueued and hence the TCP ACK does not wait prior to reaching
the head of the queue, i.e.,
$t_{\textrm{head}}^{\textrm{ack}}=t_{\textrm{enq}}^{\textrm{ack}}$. Recall
that for all handshakes,
$t_{\textrm{enq}}^{\textrm{ack}}=t_{\textrm{tx\\_end}}^{\textrm{seg}}$ and
hence the instantaneous value of uplink access delay for the immediate ACK
handshake is given by
$\big{(}t_{\textrm{rx\\_start}}^{\textrm{ack}}-t_{\textrm{tx\\_end}}^{\textrm{seg}}\big{)}$.

#####  4.2.2.3 Queuing Delay Estimation and Decomposition

Recall that our goal is to estimate the average queuing delay
($\bar{\Phi}_{\textrm{queuing}}$) and further decompose it into contributions
coming from individual uplink flows. To this end, uScope leverages the two
classes of TCP handshakes mentioned above as follows.

Consider the case of immediate ACK handshake. In this case, the target STA’s
queue is empty when the TCP ACK gets enqueued. Consequently, the ACK
immediately reaches the head of the queue (i.e.,
$t_{\textrm{enq}}^{\textrm{ack}}=t_{\textrm{head}}^{\textrm{ack}}$) and the
queuing delay is 0.

However, in the case of a queued ACK handshake, the TCP ACK experiences a
delay equal to the amount of time required to transmit the $N$ packets queued
before it. Consequently, the ACK reaches the head of the queue after the
$N^{th}$ intermediate transmission
($t_{\textrm{head}}^{\textrm{ack}}=t_{\textrm{rx\\_end}}^{\textrm{int(N)}}$)
and hence the instantaneous value of queueing delay is given by
$\big{(}t_{\textrm{rx\\_end}}^{\textrm{int(N)}}-t_{\textrm{tx\\_end}}^{\textrm{seg}}\big{)}$.
As before, $\bar{\Phi}_{\textrm{queuing}}$ can be computed by averaging over
all the instantaneous values obtained from the two types of handshakes.

The net queuing delay has contributions from each flow coming on the uplink
from the target STA. Each packet delays the TCP ACK from reaching the head of
the queue by an amount of time equal to the duration between when the packet
reaches the head of the STA queue to when the packet gets transmitted
successfully. As shown in Fig. 4.2a, the contribution to the net queuing delay
from packets of the $i^{th}$ flow is given by
$\big{(}t_{\textrm{rx\\_end}}^{int(j-1)}-t_{\textrm{rx\\_end}}^{int(j)}\big{)}$
if the $j^{th}$ intermediate packet belonged to the $i^{th}$ flow from the
target STA.

####  4.2.3 Retransmission and Defer Delay Estimation

The value of $\bar{\Phi}_{\textrm{access}}$ is influenced by two key factors,
(i) $\bar{\Psi}_{\textrm{defer}}$ which is the amount of time the medium is
sensed as busy by the target STA as it attempts to transmit and (ii) $\bar{R}$
which is the average number of retransmissions attempts per packet that the
target STA makes prior to the successful transmission.

The AP’s lack of knowledge of the connectivity links and contention
relationships for a target STA prevents it from knowing which nodes a target
STA defers to. In the network scenario we consider, due to asymmetry in the
contention relationships for the downlink and uplink, the target STA may be
deferring to nodes that are hidden from the AP. Likewise, the AP may hear
nodes that are hidden from the target STA. Further, the AP cannot directly
observe and record each failed transmission of the target STA. As a result,
both $\bar{\Psi}_{\textrm{defer}}$ and $\bar{R}$ can be directly observed only
at the STA and are unknown to the AP. This subsection presents a technique
that uScope leverages to perform joint estimation of
$\bar{\Psi}_{\textrm{defer}}$ and $\bar{R}$ passively at the AP.

Suppose that the STA has to make $K$ attempts on average prior to a successful
transmission ($K$ is not known or observable at the AP). Let $\bar{Z}_{k}$
denote the average duration for the $k^{th}$ attempt ($1\leq k\leq K$). Each
attempt duration consists of contention time, defer time and transmit time.
Therefore,

$Z_{k}=\bar{\theta}_{\textrm{contn,k}}+\bar{\theta}_{\textrm{defer,k}}+\bar{\theta}_{\textrm{occ,k}}$
(4.2)

where $\bar{\theta}_{\textrm{contn,k}}$ represents the mean contention time,
$\bar{\theta}_{\textrm{defer,k}}$ denotes the mean defer time and
$\bar{\theta}_{\textrm{occ,k}}$ denotes the mean transmission time in the
$k^{th}$ attempt. We assume that $\bar{\theta}_{\textrm{occ,k}}$ remains fixed
until the successful transmission and hence
$\bar{\theta}_{\textrm{occ,k}}\approx\bar{\Phi}_{\textrm{tx}}$. Further, we
also assume that $\bar{\theta}_{\textrm{defer,k}}$’s are iid. This results in
an error and we show how uScope compensates for it later. While limited to
first order effects, these assumptions lead to a simple methodology to
estimate $\bar{\Psi}_{\textrm{defer}}$ and $\bar{R}$ that nonetheless lead to
accurate results (as shown in later sections).

The number of such attempt durations that can fit within the sum of average
access delay ($\bar{\Phi}_{\textrm{access}}$) and transmission delay
($\bar{\Phi}_{\textrm{tx}}$) is equal to the average number of transmission
attempts or in other words the average number of retransmission attempts
($\bar{R}$) plus one. The sum of defer time across all these intervals is the
average defer delay ($\bar{\Psi}_{\textrm{defer}}$). Therefore, to estimate
$\bar{R}$ and $\bar{\Psi}_{\textrm{defer}}$, uScope must estimate the number
of attempt durations that can fit within
$\bar{\Phi}_{\textrm{access}}+\bar{\Phi}_{\textrm{tx}}$ (a value that can be
computed based on previously described techniques). However, notice that for
doing this, uScope must have knowledge of the average duration of each attempt
for a given STA. Unfortunately, the average attempt durations are not directly
observable at the AP. Therefore, uScope must estimate the average duration for
each attempt for a given STA. To this end, uScope uses a protocol based
inference methodology coupled with virtual probing to make estimates for each
attempt duration.

#####  4.2.3.1 Protocol Based Inference

Under the above formulation, the duration of each attempt differs from the
others based on the value of contention time. However, contention time can be
estimated by leveraging knowledge of the 802.11 standard. Recall that the
standard defines the rules governing the contention process. In each round of
attempt, the target STA chooses a random number that is uniformly distributed
in $[0,W-1]$ where $W$ is the maximum contention window size. $W=2^{A}$ where
$A$ starts with an initial value of 4 for the first attempt and increments for
each round of transmission attempt. Therefore,

$\bar{\theta}_{\textrm{contn,k}}=\frac{(2^{3+k}-1)*\sigma}{2}$ (4.3)

where $\sigma$ is the slot duration. Based on our assumptions and from Eq.
(4.3) and Eq. (4.2), we get

$Z_{k}=\frac{(2^{3+k}-1)*\sigma}{2}+\bar{\theta}_{\textrm{defer,1}}+\bar{\Phi}_{\textrm{tx}}$
(4.4)

where $\bar{\theta}_{\textrm{defer,1}}$ is the average defer delay faced by
the STA during first attempt. Therefore, to obtain an estimate for each
$Z_{k}$, the only unknown left is $\bar{\theta}_{\textrm{defer,1}}$. However,
the key challenge to estimate $\bar{\theta}_{\textrm{defer,1}}$ is that the AP
cannot directly measure who the target STA defers to and for how long.
Further, the AP also cannot directly observe when each retransmission attempt
of the target STA started. As a result, $\bar{\theta}_{\textrm{defer,1}}$ is
not directly known at the AP either. Next, we show how uScope leverages
virtual probing to overcome this challenge.

#####  4.2.3.2 Virtual Probing for First Attempt Defer Delay

Recall that virtual probing provides instantaneous values of uplink access
delays as stated in the previous subsection. We restate that each uplink
access delay is a sum of total contention time, defer delays and transmission
delays. Consider TCP handshakes whose TCP ACK was successfully transmitted by
the STAs in the first attempt. Notice that the average defer delay faced by
such ACKs is the average defer delay for the first attempt, i.e.,
$\bar{\theta}_{\textrm{defer,1}}$. Since the TCP ACK is transmitted in the
first attempt, the average contention time can be computed based on Eq. (4.3)
with $k=1$. Further recall that transmission delays are directly observable to
the AP. By subtracting these two quantities from the average defer delay of
such TCP ACKs, uScope can estimate $\bar{\theta}_{\textrm{defer,1}}$.

To identify such handshakes, uScope uses the retry bit in the 802.11 MAC
header of the packet carrying the TCP ACK. The retry bit indicates if the
current packet experienced any retransmissions and is set to 1 for all
retransmitted packets and 0 for those that are successfully transmitted in the
first attempt. Note that the retry bit does not indicate the number of
retransmissions experienced by the packet. Based on such handshakes, uScope
estimates $\bar{\theta}_{\textrm{defer,1}}$ as

$\bar{\theta}_{\textrm{defer,1}}=\overline{t_{\textrm{rx\\_end}}^{\textrm{ack}}-t_{\textrm{head}}^{\textrm{ack}}}-(\bar{\theta}_{\textrm{contn,1}}+\bar{\theta}_{\textrm{tx}}).$
(4.5)

Finally, to compensate for any errors arising from the iid assumption made
about $\bar{\theta}_{\textrm{defer,k}}$, uScope adds the residual after
subtraction of all possible $Z_{k}$s from
$\bar{\Phi}_{\textrm{access}}+\bar{\Phi}_{\textrm{tx}}$ to the
$\bar{\Psi}_{\textrm{defer}}$ estimate.

##  Chapter 5 Experimental Platforms

We experimentally validate virtual speed test and uScope using off the shelf
Wi-Fi chipsets as well as simulation based frameworks. This section describes
the platforms that were used and the framework implementation using those
platforms. Section 5.1 describes the Intel NUC based testbed used for the
validation of virtual speed test. This is followed by a description of the
implementation of uScope in Sec. 5.2. Finally, we describe out ns 3 based
implementation for both virtual speed test as well as uScope in Sec. 5.3.

###  5.1 Intel NUC Based Testbed

Virtual speed test is evaluated using a commodity hardware based testbed
developed by using an Intel NUC shown in fig. 5.1. Below we describe the
detailed capabilities of the hardware platform.

Figure 5.1: Intel NUC for virtual speed test validation [1].

Platform specifications. Our AP runs on a Linux operating system and is
factory installed with 32 GB DDR4 SO-DIMM RAM, 2.4 GHz dual core CPU with
slots for USB, HDMI and a Gigabit LAN port. The AP is equipped with a Ralink
RT3070 off-the-shelf WiFi chipset. The radio card supports IEEE 802.11b/g/n
utilizing up to 40 MHz bandwidth and a peak PHY rate of 300 Mbps. The STAs are
a mix of portable laptops running on either Windows or Linux OS whose network
interface card supports 802.11b/g/n as well. This AP is hereby referred to as
the VST (virtual speed test) AP. These parameters are summarized in Table 5.1.

Per-packet statistics. We build APIs that enable the acquisition of a number
of per packet statistics at the access point as well as the STAs. While a rich
raw characterization of each packet is available at all the devices, we only
feed the AP side packet timestamps, source and destination IP addresses, frame
sizes, and PHY rates into the L2 edge TCP model for throughput estimation.
Nonetheless, the remaining statistics enable us to characterize the operating
environment as will be described later. As described earlier, the parameter
estimation methodologies employ packet timestamps as a part of the computation
process. While the absolute value of these timestamps can be infected with
system dependent offsets, their post-subtraction residue becomes negligible as
they have a low second moment. The timestamps on the VST AP are available on a
nanosecond granularity. However, timestamp resolution has hardware dependency
and can vary based on processor architecture, system clock, operating system
time stamping policies, etc. Since the packet timeline operates on a scale
greater than microsecond, even a microsecond resolution - a capability
available on many hardware platforms [37], is sufficient to capture the time
domain information between packets necessary to estimate $u_{\textrm{\tiny
access}}$.

Table 5.1: Intel NUC based testbed specification  Parameter |  Value
---|---
Peak datarate |  300 Mbps
Maximum bandwidth |  40 MHz
CPU |  2.4 GHz Dual core
RAM |  32 GB DDR4 SO-DIMM
Operating system |  Linux

###  5.2 Linksys WRT3200ACM Based Testbed

uScope is evaluated using experiments performed on an off-the-shelf Wi-Fi
chipset. This section provides details on the software modules and the
commodity hardware based testbed implementation.

####  5.2.1 System Implementation

The system consists of two main parts, a stats manager module which gathers AP
side observations and a stats processor module which implements the uScope
core.

Stats manager. The stats manager runs on the AP and implements the framework
for collection of AP side observation logs. This module employs a libpcap
engine [38] to collect logs from the network interface card of the device. The
logs consists of aggregate transmission (TX) and reception (RX) statistics
which include packet timestamps, 802.11 radio tap headers and packet headers
for transmissions and receptions. Further, the logs also contain neighboring
BSS’s statistics which comprise of timestamps and airtime utilization for
transmissions from co-existing BSSs.

Stats processor. The information gathered by the stats manager is operated
upon by an instance of the stats processor. The stats processor is a Python
based framework with over 7,000 lines of code to implement the uScope core.
This module implements techniques to parse the AP-side log and separate
individual flows. The parsed log is piped into the uScope core which
implements the techniques described in the previous section to estimate
$\bar{L}_{\textrm{uplink}}$, $\bar{\Phi}_{\textrm{access}}$,
$\bar{\Psi}_{\textrm{defer}}$, $\bar{R}$, $\bar{\Phi}_{\textrm{queuing}}$ and
$\bar{\Phi}_{q,i}$.

####  5.2.2 Testbed Characterization

Figure 5.2: Linksys WRT3200ACM used as an Access Point for uScope validation
[2].

Access Point. We use the Linksys WRT3200ACM as the Access Point as shown in
Fig. 5.2. The device is an Armada-385 based router running a variant of Linux
operating system. The AP has a dual architecture design wherein a general
purpose system on chip (SoC) controls the mother board and a peripheral SoC
executes the 802.11 PHY and MAC protocols. The dual band radio card has 4
external antennas providing antenna gains of 2.52 dBi in the 2.4 GHz band and
3.81 dBi in the 5 GHz band thereby providing a theoretical range upto 100 m
which is far higher compared to those provided by some of the common dualband
antenna designs [39, 40, 41, 42, 43, 40]. The AP is IEEE 802.11ac compliant
and supports up to 3 simultaneous spatial streams and up to 160 MHz bandwidth.
The peak data rates supported on the AP are 2.6 Gbps (802.11ac, 5 GHz), 600
Mbps (802.11n, 2.4 GHz) and 54 Mbps (802.11a/g). The AP is equipped with a 1.8
GHz dual core ARM based CPU, 256MB Flash, 521MB DDR3 RAM, 4 Gigabit LAN ports
and a Gigabit WAN port. These parameters are specified in Table. 5.2.

Table 5.2: Linksys WRT3200ACM based testbed specifications Parameter |  Value
---|---
CPU |  1.8 GHz dual core ARM based CPU
Number of antennas |  4
Maximum spatial streams |  3
Bandwidth |  160 MHz
Peak datarate (2.4 GHz) |  600 Mbps
Peak datarate (5 GHz) |  2.6 Mbps
RAM |  521MB DDR3 RAM

While the computational capability of the AP is sufficient to support on board
operation of both the stats manager and stats processor, the AP’s on board
memory becomes a critical bottleneck. Like most commodity hardware platforms,
the AP’s on board memory is optimized by the vendor to suffice the execution
of only legacy functionalities. Consequently, less than 10% of the memory
($\approx$ 23MB) is available for implementing uScope . To overcome this
bottleneck, we offload the stats processor module to a remote server which has
sufficient memory for storage of AP logs whereas the stats manager runs on the
AP. We further modify the stats manager in the following way. The statistics
collected by the libpcap engine are temporarily stored in the kernel space of
the AP which is probed by a periodic transfer routine. When a packet log is
encountered by the routine, it fires a transfer command which sends the log to
the remote server for storage. The estimates from the uScope core are stored
in the output log on the remote server. The work flow is illustrated in Fig.
5.3.

STAs. The STAs are portable laptops running either Windows or Linux operating
system. The STAs are upgraded to support IEEE 802.11ac by using an open source
IEEE 802.11ac capable Edimax EW-7822ULC Wi-Fi chipset. The radio card has 2
internal antennas and supports communication on both 2.4 and 5GHz bands. The
wireless interface has peak rates of 144, 300 and 867 Mbps while using the 20,
40 and 80MHz bandwidth respectively. Web activities on the STAs are performed
by using the Mozilla Firefox web browser.

An instance of the stats manager also runs on the STAs to gather STA side
observation log and stores it locally on the device for post-experiment
retrieval. While uScope does not require STA side log for making estimations,
this information helps in characterization of ground truth which is required
for validation of uScope .

Figure 5.3: The workflow of commodity hardware based implementation of uScope
. The implementation comprises of two key modules: (i) stats manager running
on the AP and (ii) stats processor running on a remote server. The stats
manager implements key functionalities for recording AP side observations
which are sent to the remote server and piped into the uScope core for
obtaining the final estimates.

###  5.3 ns-3 Based Simulation Platform

ns3 is a discrete event simulator whose source code is open source [29]. It is
one of the most popular tools for performing network simulations [44, 27, 22]
and has rigorously implemented modules for capturing the behavior of the
802.11 MAC and PHY.

We extend ns3 to include functionalities that enable a validation of both
virtual speed test and uScope . Specifically, we extend the MAC high and MAC
low modules inside the ns3 core to implement functionalities for virtual speed
test and uScope implementation. A workflow of the extended version of the
simulator is as shown in Fig. 5.4.

Figure 5.4: The workflow of the extended ns3 simulator. We extract packet
information out of the MAC high, MacRxMiddle and MacLow modules and pass them
into the virtual speed test and uScope module.

##  Chapter 6 Virtual Speed Test Evaluation

In this chapter, we present the evaluation of virtual speed test. Our
experimental methodology is to first evaluate the estimation accuracy of
virtual speed test under the variation of one performance factor and then to
perform extensive field trials in which a number of these factors co-exist and
vary together. In Sec. 6.1, we present results from our controlled
experiments. This is followed by Sec. 6.2 which presents results from our in-
field trials.

###  6.1 Controlled Experiments

The first factor that we consider for evaluation is network topology. Network
topology and especially the presence of hidden terminals has a significant
impact on the achievable download and upload speeds. To evaluate the
performance of virtual speed test, we set up the following scenario in ns 3.

Table 6.1: Details of simulation parameters  Parameter |  Value
---|---
Wireless standard |  802.11n
Rate adapation |  Minstrel
Frequency |  2.4 GHz
AP antenna count |  1
STA antenna count |  1

We consider multiple STAs deployed on a circle with a fixed radius around the
Access point. Both the AP as well as the STAs have a single antenna. Neither
the AP nor the STAs perform any frame aggregation and all nodes are static. In
this case, we chose one STA as the target STA and the remaining STAs as non-
target STAs. The target STA performs a TCP download from a server with a one
way backbone delay of 5 ms to the AP. Using the TCP handshakes from this
download, the AP makes an estimate using the L2 Edge TCP model. The non-target
STAs have fully backlogged uplink UDP flows. Note that the nature of traffic
does not have an impact on the estimation error. Following, the estimate, we
re-run the simulation with the same background traffic but with a speed test-
like flow from a server with a one way latency of 1 ms (low latency server)
from the AP. This flow emulates the flooding based mechanism of speed test by
having 10 parallel flows with each flow jump started to a congestion window
size of 100. The TCP throughput reported by the STA for this flow after the
simulation completes is considered as the ground truth. We summarize the
simulation parameters used for this and the remaining simulations in Table.
6.1. The STAs do not perform any frame aggregation in this case.

We first consider a case in which the value of the radius is 5m. In this case,
all nodes can carrier sense each other and no hidden terminals are present.
Fig. 6.1 shows the results of the speed test flow in this scenario. As
expected, the ground truth value of download and upload speeds decays with an
increasing number of STA. Next, we consider the scenario wherein the radius is
approximately equal to the cell edge radius. In this case, each additional STA
(non-target) added to the network is a hidden terminal. In the case of both
download as well as upload, the addition of hidden terminals results in a
significant throughput degradation in comparison to the corresponding case
without hidden terminals.

An increase in the number of hidden terminals causes an increase in the
collision rate for the STA’s transmissions on the uplink. However, recall that
the delay caused by retransmissions is accounted for in the uplink channel
access time parameter in the model. Consequently, the impact of hidden
terminals gets captures in the estimates and the virtual speed test estimates
for the download and upload speeds demonstrate a close match with the ground
truth values. This demonstrates the effectiveness of virtual speed test in the
presence of hidden terminals as well as with an increasing STA density.

(a) Download speed test throughput estimation

(b) Upload speed test throughput estimation

Figure 6.1: Virtual speed test performance in the presence and absence of
hidden terminals and with an increasing STA density.

TCP ACK thinning mechanism enables a TCP receiver to reduce the number of TCP
ACKs generated by generating an ACK for every $n^{th}$ TCP segment. Typically,
while operating at maximum segment size, $n=2$ [44, 18, 27, 22]. Note,
however, that massive use of delayed ACK techniques (beyond the standard TF =
2) has detrimental effects to TCP [32], and would require sophisticated cross-
layer design to be implemented in a WLAN.

It is important that when TCP uses the TCP ACK thinning feature, virtual speed
test can still make estimates accurately. Fig. 6.2 shows the estimates and the
corresponding ground truth values when the ACK thinning ratio is kept at 1 and
2. Recall from the L2 Edge TCP model described previously that framework
accounts for ACK thinning by reducing the number of jobs circulating in the
virtual network and instead further inflating the service times for the
missing jobs. Consequently, as shown in Fig. 6.2, a variation in the ACK
thinning ratio does not affect the estimation accuracy of virtual speed test.

(a) Download speed test throughput estimation

(b) Upload speed test throughput estimation

Figure 6.2: Estimation accuracy of virtual speed test in the presence of TCP
ACK thinning mechanism.

Typical WLANs involve presence of mobile users moving at indoor human mobility
speeds. Consequently, a speed estimation tool such as virtual speed test much
estimate download and upload speeds accurately in the presence of node
mobility. Next, we evaluate the performance of virtual speed test in the
presence of node mobility. We consider light indoor mobility speeds ranging
between walking speeds of 1 m/s to maximum sprinting speeds of up to 5 m/s.
Mobility introduces packet loss and forces the devices to perform rate
adaptation. Interestingly, we notice from Fig. 6.3, user mobility has a very
negligible effect on the ground truth value of download and upload speeds.
Further, virtual speed test demonstrates a high level of accuracy in the
estimation for both download as well as upload speed estimations.

(a) Download speed test throughput estimation

(b) Upload speed test throughput estimation

Figure 6.3: Validation of virtual speed test in the presence of node mobility.

###  6.2 In-field Trials

Next, we perform an extensive set of field trials with our commodity hardware
based testbed. These field trials are conducted in the residential and office
environment. Below, we provide details of our field trials.

####  6.2.1 Deployment Characterization

To understand the estimation accuracy of virtual speed test, we deploy the VST
AP and STAs in two environments.

Deployment description. The first deployment is in a 5m x 3m student office
located in a 3 storied building on a University campus. In this deployment,
the VST AP and the STAs co-exist with a University administered enterprise
network and 2 APs deployed in nearby student offices. Here the VST AP has 6
STAs associated with it. We deploy a second network in a 3 storied residential
building primarily consisting of apartments with 1 or 2 bedrooms per unit.
This residential network consists of 7 STAs. These devices co-exist with 4 APs
from neighboring apartments. The VST AP deployed in the office performs
measurements for a period of two days whereas the residential scenario
measurements are carried out for a period of one week. During the entire
duration of deployment, the VST AP observed a total of 113,047 snooped flows.
These flows are the result of multiple applications running on end devices
such as video streaming (via YouTube), music streaming (via Pandora), pdf
downloads (via IEEE Xplore) and sending and receiving emails (via Gmail). The
STAs use Mozilla Firefox web browser for performing these online activities.
The traffic flows consist of single application traffic where each STA runs
only one web application as well as a mix of web applications running
concurrently. Aside from the applications mentioned above, some of the STAs
have Dropbox installed on them which occasionally adds to the uplink traffic
from these devices in addition to that generated by email activities. We do
not suppress any control packet transmissions at any of the layers.

(a) Office

(b) Residential

Figure 6.4: pdf of application layer data sizes encountered in the office and
residential deployment.

The ground truth values of the L2 edge TCP model parameters are affected by
operating conditions determined by the traffic characteristics, active STA
count and the MAC and PHY statistics. It is important that virtual speed test
is able to estimate both the upload and download throughputs accurately
despite a variation in these factors.

Traffic statistics. Packet size variation causes a microscopic fluctuation in
the air time utilization for non-target STAs and transmit time for the target
STAs. Fig. 6.4 shows the application layer data size distribution for both the
scenarios. The minimum size encountered in the trace is 20 bytes whereas the
maximum size is 1.4K bytes. In addition to this, a fluctuation in the per
minute download statistics as shown in Fig. 6.5 causes a variation in the
network load affecting queuing delays and idle times for both the target and
non-target STA.

Active STA count diversity. A variation in the number of active STAs in the
network affects ground truth value of $V$ and the ‘access’ parameters. In both
deployments, the number of active STAs is varied to cover a total of 36 and 49
combination of STA sets in the office and residential scenario respectively.
In these combinations, active STA sets of all possible sizes are covered and
the VST AP makes predictions for each device in the set.

(a) Office

(b) Residential

Figure 6.5: Variation in the amount of data downloaded per minute in the
office and residential deployment. The values are normalized with respect to
the overall maximum encountered in that particular deployment.

MAC and PHY statistics. Link diversity in terms of signal propagation
characteristics (due to LoS and non-LoS links to the VST AP), overheard
transmissions from neighboring BSSs, active STA count variation and traffic
statistics mentioned above result in a variation in MAC and PHY statistics
across devices. Fig. 6.6 shows the normalized signal strength distribution of
the VST AP across all STA locations in the office and residential scenario.
The signal strength distribution is normalized with respect to the maximum VST
AP signal strength encountered in that environment across all STA positions.
Due to the small size of the office, the received signal strength of the VST
AP across all STA locations is very close to the encountered maximum. In
comparison, the residential scenario exhibits a wide distribution of the VST
AP’s signal strength across the apartment resulting in a variation in
supported PHY rates across different STA positions which affects the ‘tx’
parameters.

(a) Office

(b) Residential

Figure 6.6: Distribution of signal strength of the VST AP across all the STA
positions in the office and residential deployments. The values are normalized
with respect to the maximum signal strength encountered in that particular
deployment. Figure 6.7: Distribution of fraction of a TCP flow’s total
duration that a device spends deferring to transmissions from neighboring BSS

Moreover the multi-AP nature of these experiments results in devices in the
network deferring to transmissions from co-existing BSS thereby affecting the
‘access’ parameters. Fig. 6.7 depicts a distribution of the fraction of time
during a download that a device spends deferring to transmission from
neighboring BSS in both the office and residential scenario. The activity in
the neighboring BSS varied in both the deployments. For instance, during
approximately 30% of the flows in both the office and the residential
scenario, there was no activity on the neighboring BSS. On the other hand, the
maximum portion of a TCP flow’s duration that a STA spent deferring to
neighboring BSS is 38.8% for the residential scenario and 51.4% in the office
scenario.

All the above environment characteristics result in a variation in all the
model parameters which the VST AP intends to estimate for the purpose of
throughput prediction.

####  6.2.2 Ground Truth Procurement

We compare the outcome of virtual speed test with that obtained from online
speed test applications [3, 4, 5] as well as iperf. We focus on iperf for
procuring ground truth as online tests are subject to an additional and
uncontrolled source of variation due to server selection. Namely, recall that
during the setup phase, the server selection process of these speed test
applications tries to minimize the backbone delay between the server and the
AP with the ideal case being a server in the same LAN as the AP. In practice,
a server within the same LAN may not be available in the server pool probed by
these applications. Consequently, results obtained from a non-local server may
be affected by backbone load and delay.

To explore this effect, we keep one 802.11n laptop associated with the AP and
run multiple speed test applications 10 times with a gap of 10 mins between
each run. We attempt to realize static WLAN conditions, _i.e._ , with minimal
activity on co-existing BSS, no device or environmental mobility, etc., in
which the outcome of speed test applications should remain stable. We compare
these results with those obtained by running iperf from a local server to
remove backbone and server selection effects. Fig. 6.8 shows the values
obtained for upload and download throughput from exemplary online speed test
applications as well as iperf. Compared to iperf, the speed test applications
demonstrate throughput reductions and fluctuations due to backbone and server
selection effects. On the other hand, the values obtained from iperf remain
stable. Therefore, to obtain stable and more reliable ground truth values in
our experiments, we use the iperf tool.

(a) Download speed test

(b) Upload speed test

Figure 6.8: Iperf results as compared to exemplary online speed test
applications.

####  6.2.3 Experimental Methodology

In our experiments, virtual speed test throughput estimates are obtained
solely via AP measurements, i.e., by using AP-snooped TCP data - ACK
handshakes from existing network traffic to estimate the parameters required
by the L2 edge TCP model. Immediately following each throughput estimation,
the ground truth is measured via iperf on instrumented clients. While network
traffic is composed of both download and upload traffic, virtual speed test
only leverages download flows for $u_{\textrm{\tiny access}}$ estimation.

####  6.2.4 Parameter Estimation Accuracy

Throughput and virtual service time are impacted by the uplink access time.
Recall that this model parameter is not directly observable at the AP. Rather,
the VST AP leverages snooped handshakes from TCP flows existing in the network
to estimate uplink access time. In our deployment, the VST AP observes cases
involving only single application traffic as well as those with mixed
application traffic involving concurrent TCP flows with a mix of downloads and
uploads. To correctly estimate the uplink access time, the VST AP needs to
first identify TCP flows based on the address and size signatures and then
accurately identify the occurrence of the ACK queuing and ACK immediate
regimes. We first explore the efficacy of the $u_{\textrm{\tiny access}}$
estimation method by comparing the estimates made by the VST AP using snooped
flows with the ground truth values obtained from the STA-side.

Fig. 6.9 shows a scatter plot of measured values of $u_{\textrm{\tiny
access}}$ vs. the ground truth value. For each deployment scenario, both of
these values are normalized with respect to the maximum ground truth value in
that particular scenario. Fig. 6.9 shows that as the ground truth values of
$u_{\textrm{\tiny access}}$ varies due to numerous factors such as background
traffic characteristics, active STA count, etc., the points in the scatter
plot continue to be closely located to the identity line. Fig. 6.9 also
demonstrates the existence of homoscedasticity between estimates obtained by
VST AP and the ground truth value of $u_{\textrm{\tiny access}}$ obtained from
the STA-side. In essence, this shows that as the ground truth value of
$u_{\textrm{\tiny access}}$ varies due to the numerous factors mentioned
previously, the estimated value of $u_{\textrm{\tiny access}}$ retains its
accuracy.

(a) Office Scenario

(b) Residential Scenario

Figure 6.9: Scatter plot of $u_{\textrm{\tiny access}}$ measured and ground
truth value in the office and residential deployments. In each sub-figure,
both the axis are normalized with respect to the maximum ground truth value in
that particular deployment.

####  6.2.5 Throughput Estimation Accuracy

The ultimate goal of virtual speed test is to estimate $\theta_{\textrm{\tiny
dl}}$ and $\theta_{\textrm{\tiny ul}}$. To evaluate throughput estimation
accuracy, we calculate the percent estimation error between the ground truth
values obtained from iperf and the estimates of virtual speed test as
$\%error=\frac{|(\theta_{\textrm{\tiny gt}}-\theta_{\textrm{\tiny
est}})|*100}{\theta_{\textrm{\tiny gt}}}$ where $\theta_{\textrm{\tiny gt}}$
denotes the ground truth value of throughput and $\theta_{\textrm{\tiny est}}$
denotes the estimated value from virtual speed test. We remark that since the
$\%error$ is calculated after weighing by $\theta_{\textrm{\tiny gt}}$, it is
sensitive to the value of $\theta_{\textrm{\tiny gt}}$, _i.e._ , the same
absolute error at a smaller ground truth value is bound to yield higher
estimation error.

Fig. 6.10 summarizes the percent throughput estimation error statistics in
both the office and residential deployments. Overall virtual speed test shows
a good match against ground truth values with a mean percentage error of 4.09%
and 4.3% for upload and download speeds respectively in the office scenario.
In the residential scenario, these values are 5.51% and 2.9% respectively.

(a) Office Scenario

(b) Residential Scenario

Figure 6.10: Percent throughput estimation error statistics in the office and
residential deployments. In the table, GT denotes the ground truth value and
Est denotes the throughput estimated by virtual speed test.

####  6.2.6 Observation Set Size Characterization

(a) Office: Download

(b) Office: Upload

(c) Residential: Download

(d) Residential: Upload

Figure 6.11: Throughput estimation error as a function of the observation set
size available at the AP

Virtual speed test estimates the target STA’s throughput by collecting
measurements from its TCP traffic. Therefore, a key factor that determines the
estimation accuracy of virtual speed test is the number of measurements that
the VST AP can obtain from the target STA’s TCP traffic which in turn depends
on the target STA’s online activity. On one extreme, a large number of
observations obtained from either a single large file download or a series of
consecutive small file download results in refined parameter estimation. We
experimentally investigate the observation set size required to avoid a
deterioration in estimation accuracy as follows. Since the backbone delay
between the snooped flow’s server and the VST AP is inconsequential, we
initiate a single TCP flow from a local server to the target STA and treat it
as a snooped flow. We control the observation set size available at the VST AP
by changing the download file size and computing the percent throughput
estimation error as before.

Fig. 6.11 depicts the mean estimation error as a function of the size of the
observation set available at the VST AP. The mean estimation error
demonstrates an exponential decrease with an increasing set size. When the
sample set size is on the order of a few 10s of samples, the estimation error
is as high as 70%. The variance in this case is also very high. This is due to
the fact that the number of measurement samples are insufficient to accurately
characterize the model parameters. With an increasing sample set size, the
precision in the model estimation increases as expected. Fig. 6.11 reveals
that even when the observation set contains a few 1000s of samples (which
could easily be obtained from observing the download of a research paper from
IEEE Xplore), the mean estimation error of virtual speed test is under 5% in
both the deployments.

##  Chapter 7 uScope Evaluation

In this chapter, we show the evaluation of uScope under the impact of numerous
factors such as network topology, device mobility, environmental mobility,
etc. First we show controlled experiments in Sec. 7.1 followed by in-field
trials experiments in Sec. 7.2.

###  7.1 Controlled Experiments

The goal of uScope is to estimation uplink WLAN latency and decompose it into
its constituent components. Specifically, uScope enables an AP-side estimation
of queuing delays, channel access delays, defer delays and the retransmission
rate for the STA on the uplink. Our experimental approach is to validate the
estimation accuracy of uScope in the presence of factors that cause a
variation in these parameters.

We begin by evaluating the estimation accuracy of uScope in the presence of a
variation in queuing delays. In this experiment, we keep one STA associated
with the AP. The STA performs a TCP download from a server with a one way
latency of 10 ms. It is important to note that the value of the backbone
latency does not affect the ground truth or the parameter estimate for the
uplink. In addition to this flow, the STA has one additional uplink UDP flow
which pushes packets into the STA queue. The packet generation rate of this
uplink UDP flow is controlled in the experiment.

Figure 7.1: Estimation accuracy of uScope in the presence of varying queuing
delay on the STA.

In this experiment, the AP observes the handshakes from the TCP download of
the STA and makes an estimate for the queuing delay at the STA-side on the
uplink. The ground truth is reported based on the knowledge of the timestamps
corresponding to when the packet gets enqueued and when it reaches the head of
the STA queue.

As shown in Fig. 7.1, a variation in the traffic generation rate of the uplink
UDP flow causes an increase in the amount of queuing delay that is experienced
on the STA side. However, as the queuing delay varies from a minimum of 1 Mbps
to 10 Mbps, the estimate made by the AP shows a close match with the ground
truth value.

Next, we validate the accuracy of uScope in estimating the amount of time a
STA defers to transmit on the uplink. Here we consider to types of topologies
and validate the performance for an increasing number of nodes for each case.
First, we consider a scenario in which all nodes are within carrier sensing
range of each other. In this scenario, each additional node added to the
experiment makes the target STA or in other words the STA for which the AP is
making an estimate defer. Next, we consider a scenario in which every non-
target STA is hidden from the target STA. Consequently, an increasing number
of non-target STAs results in an increasing number of hidden terminals in the
network for the target STA.

(a) Absence of hidden terminals

(b) Presence of hidden terminals

Figure 7.2: Defer delay estimation accuracy of uScope in the presence and
absence of hidden terminals.

Fig. 7.2 shows the defer delay estimate made by the AP for the target STA. As
depicted, in the case where all nodes are within carrier sensing range of each
other, an increasing number of non-target STAs results in an increasing defer
delay for the target STA. However, in the case where no hidden terminals are
present, an increasing number of non-target STAs does not result in an
increasing defer delay. This is because these non-target STAs are hidden from
the target STA. Consequently, the target STA does not defer to them. In fact,
the target STA defers to only one node which is the AP. Therefore, an
increasing number of non-target STAs does not result in an increasing defer
delay for the target STA. It is important to note that if the AP had solely
made an estimate based on the defer delay for the downlink, this case would
have caused a false positive. However, uScope can estimate the defer delay in
both the cases with a high level of accuracy.

Next, we evaluate the estimation accuracy of uScope in estimating the
retransmission rate. We consider the same scenarios as before and evaluate the
accuracy of uScope in both the scenarios. Fig. 7.3 shows the retransmission
rate estimation accuracy as a function of increasing number of non-target
STAs. In the first scenario, an increasing number of non-target STAs increases
the retransmission rate due to a rise in collision probability as the number
of contending STAs increases. However, in the second case, the rise is even
faster as each non-target STA added to the simulation is hidden from the
target STA and consequently results in a rapid increase in the collision
probability. Fig. 7.3 reveals that in both the scenarios, uScope estimates the
retransmission rate with a high accuracy which is demonstrated by a close
match between the ground truth value and the estimated values.111Since, we
already show the estimation accuracy for uplink access delay in the previous
chapter, we do not repeat it hear again.

(a) Absence of hidden terminals

(b) Presence of hidden terminals

Figure 7.3: Retransmission rate estimation accuracy of uScope in the presence
and absence of hidden terminals.

###  7.2 In-field Trials

Next we perform extensive field trials in which a number of factors co-exist
together thereby enabling us to validate the performance of uScope in complex
scenarios representative of a typical multi-BSS environment.

####  7.2.1 Deployment Characterization

The empirical values of total uplink latency and its constituent components
are affected by a number of factors such as traffic statistics, network
topology as well as MAC and PHY statistics. It is important that as these
factors vary, uScope is able to accurately estimate total uplink latency as
well as decompose it into is constituent components. This section
characterizes the diverse operating conditions encountered in these tests.

Deployment overview. We deploy our AP and STAs in two locations. The first
location is a university campus. Here the AP is deployed in a 3m x 5m office
located in a 3 story building. The STAs are deployed both inside the office as
well as outside the office at different locations on the same floor. The
second deployment is an apartment located in a residential complex which
comprises 1 or 2 bedroom units. Both of these environments comprise multiple
BSSs co-existing together. In the university deployment, our devices co-exist
with a university administered enterprise WLAN and 4 student deployed APs in
nearby offices. Whereas in the residential environment, our devices co-exist
with 12 APs from neighboring apartments. In each of these deployments, our AP
has a total of 10 STAs associated with it. Each of these scenarios are
characterized by a diversity in links (i.e., LoS and non-LoS paths), light
human and environmental mobility as well as device mobility. We validate
uScope via an extensive number of tests conducted in these deployments.
Specifically, the total number of tests run were 1,296,000 of which 576,000
were run in the university deployment whereas 720,000 were run in the
residential deployment.

(a)

(b)

Figure 7.4: Aggregate per hour download and upload statistics in the
university and residential deployments (a) Per hour download distribution, (b)
Per hour upload distribution.

(a)

(b)

Figure 7.5: Aggregate uplink flow statistics in the university and residential
deployments. (a) Distribution of number of active uplink flows per hour (b)
Distribution of the duration of an active flow.

Traffic statistics. The STAs in our deployments run online internet
applications that perform video streaming (using YouTube and Amazon Prime
Video), music streaming (via Pandora), pdf downloads (from IEEE Xplore), email
activities (using Gmail) and Gigabit file downloads and uploads to Dropbox and
Google Drive. The tests involve cases with both single application traffic
where only one of the above applications is run at a time as well as mixed
application traffic were a number of these applications run in parallel. These
internet applications are run using Mozilla Firefox web browser. In addition,
some of the STAs also performed UDP downloads and uploads to local servers. A
distribution of the amount of per hour download and upload is shown in Fig.
7.4 and a distribution of the number of active uplink flows and their duration
is shown in Fig. 7.5. This variation causes a fluctuation in the queuing
delays experienced by the STAs as well as a variation in the per flow queuing
delay.

(a) University deployment

(b) Residential deployment

Figure 7.6: Packet size distribution for the university and residential
deployments. In each of these deployments, the minimum packet size encountered
is around 200 bytes and the maximum packet size is around 1.6KB.

The packet size distributions encountered in each of these scenarios are shown
in Fig. 7.6. The minimum packet size is around 200 bytes and the maximum is
around 1600 bytes. A variation in a STA’s packet sizes affects the amount of
air time utilization thereby causing a microscopic fluctuation in the defer
delays experienced by other STAs. This in turn affects uplink access delays.
Further, packet size variation also affects transmission delays.

Network topology. The network topology determines the number of interfering
nodes which affects the retransmission rate and defer delays. These in turn
affect the uplink access delay. The residential and university scenarios cover
a total of 250 and 200 number of topologies respectively. These topologies
arise from a combination of weak links, strong links, near and far away nodes,
hidden terminals, etc. Further, the tests cover cases with active STA sets of
all possible sizes and the AP makes an estimate for each associated STA.

(a) University deployment

(b) Residential deployment

Figure 7.7: Distribution of STA’s signal strength in the university and
residential deployments.

MAC and PHY statistics. A diversity in both the network topology as well as
the traffic characteristics of the STAs result in a variation in the MAC and
PHY statistics of the devices in our network. This variation affects the total
uplink latency as well as its constituent components. Fig. 7.7 shows the
distribution of rssi values for the STAs during the experiments. Rssi affects
selected data rates which affects transmission delays and hence total uplink
latency. Transmission delays of non-target STAs affects the amount of time
that the target STA defers thereby affecting its defer delays and access
delays.

(a) University deployment

(b) Residential deployment

Figure 7.8: Airtime utilization of devices in co-existing BSSs in the
university and residential deployments.

Both deployment scenarios are characterized by co-existing BSSs. As a result,
the STAs in our network defer to these nodes depending on their air time
utilization which affects their defer delays and access delays. Fig. 7.8 shows
the distribution of air time utilization of devices in the co-existing BSSs.

####  7.2.2 Parameter Estimation Accuracy

In this section, we investigate the performance of uScope in the two
deployment scenarios.

(a) Total uplink latency estimation error

(b) Access delay estimation error

(c) Queuing delay estimation error

(d) Per flow queuing delay estimation error

(e) Retransmission rate estimation error

(f) Defer delay estimation error

Figure 7.9: Parameter estimation accuracy of uScope for the university and
residential deployments. The average estimation error across all the
parameters is less than 10%.

First we experimentally evaluate the parameter estimation accuracy of uScope .
Recall that the key idea in uScope is to treat TCP handshakes as virtual
probes and use them to drive measurement based estimation of total uplink
latency and its constituent components. In our deployment, the system
estimates total uplink latency and its components for each associated STA
every 30 seconds. Therefore, in this test duration, the system gathers AP logs
and pipes them into the uScope core to obtain estimates. These estimates are
time-stamped and stored on the remote server. Recall that the instance of
stats manager running on the STAs locally stores the STA log. Similar to the
AP, this log is collected every 30 seconds. This log captures the ground truth
observed by the STAs. In the deployment scenarios, the STA uses each packet
transmitted on the uplink as a recording of ground truth. However, the AP only
uses the TCP handshake coupled with the techniques described in the Ch. 4 to
estimate the parameters.

We compare the estimates for $\bar{L}_{\textrm{uplink}}$,
$\bar{\Phi}_{\textrm{access}}$, $\bar{\Phi}_{\textrm{queuing}}$,
$\bar{\Phi}_{q,i}$, $\bar{R}$ and $\bar{\Psi}_{\textrm{defer}}$ made by the
uScope system with those obtained from the STA side. To evaluate the parameter
estimation accuracy, we compute the percent error in the estimate calculated
as $\frac{|\beta_{est}-\beta_{gt}|*100}{\beta_{gt}}$ where $\beta_{est}$ is
the estimate for a parameter obtained from the uScope system and $\beta_{gt}$
is the ground truth for the parameter obtained from the STA side.

Fig. 7.9 summarizes the estimation error statistics for both the university
and the residential scenario. Overall, uScope demonstrates a mean estimation
error below 10% across all parameters. However, Fig. 7.9 reveals that in some
cases, the worst case estimation errors are much larger compared to the
average. This primarily occurs due to the following reason. Recall that uScope
is driven by measurements collected from TCP handshakes at the AP side. As a
result, for an accurate estimation, the AP must observe a sufficiently large
number of TCP handshakes. In our deployments, the number of handshakes
observed by the AP in any given test duration is dependent on the activity of
the internet application running on the STA. Consequently, in test intervals
where the AP observes an insufficient number of TCP handshakes, the estimate
made by the AP demonstrates a high error. We further explore how estimation
error varies as a function of number of TCP handshakes in the next subsection.

####  7.2.3 Estimation Error Characterization

(a) Total uplink latency estimation error

(b) Access delay estimation error

(c) Queuing delay estimation error

(d) Per flow queuing delay estimation error

(e) Retransmission rate estimation error

(f) Defer delay estimation error

Figure 7.10: Mean estimation error for total uplink latency and its
constituent components as a function of the number of TCP handshake
measurements available to the AP while making an estimate in the residential
deployment.

(a) Total uplink latency estimation error

(b) Access delay estimation error

(c) Queuing delay estimation error

(d) Per flow queuing delay estimation error

(e) Retransmission rate estimation error

(f) Defer delay estimation error

Figure 7.11: Mean estimation error for total uplink latency and its
constituent components as a function of the number of TCP handshake
measurements available to the AP while making an estimate in the university
deployment.

uScope is a measurement driven framework. These measurements are collected by
observing TCP handshakes from TCP flows of a STA. Consequently, the parameter
estimation error is a function of the number of TCP handshakes that the AP
observes. Here we experimentally investigate the relationship between the
estimation error and the number of TCP handshakes observed by the AP.

In order to do so, we leverage the logs collected from the AP and all the STAs
in the field trials. We modify the stats processor to iterate through the log
and pass a specified number of consecutive TCP handshakes to the uScope core.
As a result, uScope is constrained to make an estimate solely based on these
samples. This number is varied to understand the relationship between
estimation error and number of observed TCP handshakes.222To ensure that the
AP sees a non-retransmitted TCP ACK for defer delay and retransmission rate
estimation, we start the test with a minimum of 100 measurement samples.

Fig. 7.10 and 7.11 depict the estimation error as a function of the number of
observed handshakes in the residential and the university scenario
respectively. The estimation error demonstrates a similar trend across all the
parameters. When the number of TCP handshakes observed by the AP are on the
order of a few 100s, the mean estimation error is extremely high. This is
because the number of measurements is not sufficient to characterize the total
uplink latency and its constituent components. In this regime, the variance in
the error is also high. Both the estimation error and the variance demonstrate
a rapid decay with an increase in the number of observed TCP handshake. Fig.
7.10 and 7.11 reveal that even with over 1,000 observed TCP handshakes, the
estimation error of uScope across all the parameters is less than 10%.

##  Chapter 8 Related Work

###  8.1 Analytical Models for TCP Throughput Estimation

Several analytical modeling approaches are available in literature that lead
to closed form expression for TCP throughput. Classic models for TCP focus on
capturing the macroscopic behavior of TCP over a network path with a given
round trip time (RTT) and a loss probability [45, 46, 47, 48, 49, 50].
Extensions of these approach have been applied to capture the performance of
TCP over advanced physical layer technologies such as MIMO [51, 52, 53, 54].

On the other hand, powerful models for Wi-Fi focus on capturing the
microscopic packet dynamics including queuing behavior, traffic burstiness,
etc. Classic models target predictions of layer-2 throughput by taking into
account the backoff and contention process of 802.11 [30, 55, 56, 57]. Several
papers further extend these models by incorporating various MAC and PHY layer
aspects of Wi-Fi [22, 58, 27].

Unfortunately, the models are not applicable or extensible to our goal of
passive AP-side TCP throughput estimation as they require AP-side knowledge of
network topology, interfering nodes including those from neighboring BSS,
their traffic patterns, PHY capabilities, data rates, etc. Obtaining this
information requires STA-side co-operation and regular reporting. On the other
hand, the L2 edge TCP model that we propose enables throughput estimation with
zero STA-side co-operation and no reporting.

###  8.2 Active Probing Based Tools

Active probing techniques involve use of special purpose probing packets. The
classic work on packet pair leverages the dispersion of packet pairs to
estimate network parameters [59, 60, 61, 62]. Probing techniques such as such
as [63, 64] involve usage of probing packets to estimate bandwidth.

In the context of latency measurements, probing methods available in
literature can be further divided into AP-initiated probing and STA-initiated
probing. Techniques such as [65, 66, 67, 68, 7, 69, 70] make use of AP
initiated probing can be used to measure and decompose WLAN uplink latency.
Likewise, tools such as [71, 72, 73, 74, 8, 75] can be used to collect STA
side information via user initiated measurements and reporting to analyze
uplink latency.

Unfortunately, these tools involve active measurements which increases the
traffic load on the network. Consequently, their usage for periodic monitoring
can potentially disrupt user traffic thereby worsening both throughput and
latencies for other users and draining the battery of mobile devices. Further,
STA-side tools such as [74] also require special purpose software installation
on the STAs for data collection and reporting which end users may be unwilling
to install. In contrast, our frameworks are completely passive, do not require
any special purpose STA side software and make estimates solely based on AP
side observations.

###  8.3 Passive Measurements Approaches

Deploying a network of sniffers can enable collection of packet traces which
could facilitate a passive inference of the inter-node connectivity in the
network and activity of interfering nodes for a given STA [76, 77, 78, 79, 80,
81]. Such insights can enable estimation and decomposition of WLAN uplink
latency for all STAs that the sniffers can sense. Unfortunately, such passive
approaches involve deploying an additional hardware infrastructure which adds
to the cost of network deployment and maintenance. On the other hand, our
works do not require any additional hardware infrastructure and can make an
estimate solely based on passive observations from a single AP.

###  8.4 Learning Based Approaches

In this approach, followed by [15, 82, 83], network clients store empirical
throughput of all TCP sessions and report them to the AP to build a database
of TCP throughputs. This coupled with AP-side records of wireless conditions
during the TCP session (e.g., the session’s MCS, busy air time, and collision
rate) enable the AP to predict throughput by correlating the current
conditions with historical averages corresponding to similar conditions.

Machine learning tools can also be employed to estimate WLAN uplink latency
and its components [84, 85, 86, 87]. With an accurately trained model, these
approaches can achieve an accuracy over 95%.

Unfortunately, these tools require ground truth collection and reporting from
each device in the network for the purpose of model training. In contrast, the
tools presented in this thesis do not seek any information from the STAs and
can make estimates solely based on passive AP-side observations.

###  8.5 TCP Based Network Analysis

TCP flows have been used to collect information that is valuable for network
analysis, performance monitoring as well as detection of security threats.
Tools like [88, 89] analyze TCP headers to provide several IP and TCP
statistics such as segment reordering, duplication, etc. which aids network
measurement research whereas tools like [9] leverage observation of TCP flows
in the network to predict achievable TCP throughput for all STAs in the
network. On the other hand, [90, 91] utilizes TCP flow characteristics to
identify security threats. In contrast, the frameworks presented by this
thesis leverages TCP’s layer 4 handshake to estimate download and upload
speeds, WLAN latency and its constituent components.

###  8.6 Conflict Graph Based Estimation

Techniques to infer conflict relationships amongst wireless nodes are
available in literature [92, 93, 94]. Such techniques augmented with knowledge
of conflicting nodes in terms of of their traffic pattern, PHY capabilities,
transmission rates, etc. can indeed enable an estimation of TCP throughput,
latency and breakdowns. Unfortunately, the AP lacks information about these
parameters and would require either active measurements or co-operation among
all co-existing BSS nodes to obtain this additional data. On the other hand,
our frameworks can make an estimation solely based on passive AP-side
observations and does not need any additional data collection mechanism.

##  Chapter 9 Conclusion

This thesis overcomes the challenges faced in performing AP-side WLAN
analytics. This is achieved through the design, implementation and
experimental evaluation of two key frameworks that enable passive monitoring
of user experience metrics at the AP-side.

The first framework is called virtual speed test. Virtual speed test enables a
passive AP-side estimation of the download and upload speeds that a STA can
achieve over its current wireless connection. While doing so, virtual speed
test does not require any active measurements (e.g., internet speed tests), no
client side co-operation (e.g., special purpose software installations) and no
additional hardware information (e.g., sniffer deployment) to collect more
data. Virtual speed test can make an estimation solely based on passive AP-
side observations. Virtual speed test employs a novel data-driven throughput
estimation model called L2 Edge TCP model which enables speed test estimation
based on passive AP-side observations.

We implement virtual speed test on a commodity hardware platform and perform
extensive field trials in an office environment and in an apartment complex.
In both the environments, virtual speed test demonstrates a high estimation
accuracy with estimation errors less than 10%.

The second framework is uplink latency microscope (uScope ) which enables an
AP-side estimation of uplink WLAN latency and decomposition into its
constituent components. Similar to virtual speed test, uScope does not require
any active probing, no client side co-operation and no additional hardware
installations for collection of more information and can make estimations
solely based on passive AP-side observations. The key idea in uScope is to use
layer-4 handshakes of TCP as virtual probes to drive a measurement based
estimation of uplink WLAN latency, queuing delays, defer delays and
retransmission rate on the uplink for any associated STA.

We implement uScope on a commodity hardware platform and run extensive field
trials on a university campus and in a residential apartment complex. In these
field trials, uScope demonstrates a high estimation accuracy with estimation
errors under 10% for both the deployments.

## References

  * [1] Intel NUC mini PC, https://www.intel.com/content/www/us/en/products/boards-kits/nuc.html, accessed: 2019-09-09.
  * [2] Linksys WRT3200ACM MU-MIMO Gigabit WiFi Router, https://www.linksys.com/us/p/P-WRT3200ACM/, accessed: 2019-09-09.
  * [3] Ookla Speedtest, http://www.speedtest.net/, accessed: 2019-08-08.
  * [4] AT & T Internet Speed Test, http://speedtest.att.com/speedtest/, accessed: 2019-08-08.
  * [5] Xfinity Speed Test, http://speedtest.xfinity.com/, accessed: 2019-08-08.
  * [6] D. Murray, T. Koziniec, S. Zander, M. Dixon, and P. Koutsakis, “An analysis of changing enterprise network traffic characteristics,” in _In Proc. of IEEE APCC_ , 2017.
  * [7] MobiPerf, https://measurementlab.net/tests/mobiperf, accessed: 2019-08-08.
  * [8] Speed Test, http://www.speedtest.net/, accessed: 2019-08-08.
  * [9] P. Nayak, S. Pandey, and E. W. Knightly, “Virtual Speed Test: an AP Tool for Passive Analysis of Wireless LANs,” in _In Proc. of IEEE INFOCOM_ , 2019\.
  * [10] Ookla SpeedTest, “How does the Begin Test button select a server?” 2012.
  * [11] Ookla Speedtest, “How does the test itself work? How is the result calculated?”,” 2012.
  * [12] O. Goga and R. Teixeira, “Speed measurements of residential internet access,” in _Proc. of PAM_ , 2012.
  * [13] E. Altman, D. Barman, B. Tuffin, and M. Vojnovic, “Parallel TCP Sockets: Simple Model, Throughput and Validation.” in _In Proc. of IEEE INFOCOM_ , 2006.
  * [14] S. Bauer, D. Clark, and W. Lehr, “Understanding broadband speed measurements,” 2010.
  * [15] A. Patro, S. Govindan, and S. Banerjee, “Observing Home Wireless Experience Through WiFi APs,” in _In Proc. of ACM MobiCom_ , 2013.
  * [16] M. Harchol-Balter, _Performance Modeling and Design of Computer Systems: Queueing Theory in Action_. Cambridge University Press, 2013.
  * [17] D. Murray and T. Koziniec, “The state of enterprise network traffic in 2012,” in _Proc. of APCC_ , 2012.
  * [18] R. Braden, “RFC-1122: Requirements for internet hosts,” _Request for Comments_ , pp. 356–363, 1989.
  * [19] IEEE Std. 802.11ac-2013, “Enhancements for Very High Throughput for Operation in Bands Below 6 GHz,” 2013.
  * [20] IEEE Std. 802.11n-2009, “Enhancements for Higher Throughput,” 2009.
  * [21] P. Jon, “Transmission control protocol–darpa internet program protocol specification,” RFC-793, DARPA, Tech. Rep., 1981.
  * [22] P. Nayak, M. Garetto, and E. W. Knightly, “Multi-User Downlink with Single-User Uplink Can Starve TCP,” in _In Proc. of IEEE INFOCOM_ , 2017\.
  * [23] O. Bejarano, E. W. Knightly, and M. Park, “IEEE 802.11 ac: from channelization to multi-user MIMO,” _IEEE Communications Magazine_ , vol. 51, no. 10, pp. 84–90, 2013.
  * [24] I. S. Association _et al._ , “IEEE Computer Society:” Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications; Amendment 4: Enhancements for Very High Throughput for Operation in Bands Below 6 GHz”, IEEE Std 802.11 ac™, The Institute of Electrical and Electronics Engineers,” 2013.
  * [25] J. L. García-Dorado, A. Finamore, M. Mellia, M. Meo, and M. Munafo, “Characterization of isp traffic: Trends, user habits, and access technology impact,” _IEEE Transactions on Network and Service Management_ , vol. 9, no. 2, pp. 142–155, 2012.
  * [26] A. K. Marnerides, D. P. Pezaros, and D. Hutchison, “Internet traffic characterisation: Third-order statistics & higher-order spectra for precise traffic modelling,” _Computer Networks_ , vol. 134, pp. 183–201, 2018.
  * [27] P. Nayak, M. Garetto, and E. W. Knightly, “Modeling Multi-User WLANs Under Closed-Loop Traffic,” in _IEEE/ACM Transactions on Networking_ , 2019.
  * [28] E. Perahia and R. Stacey, _Next Generation Wireless LANS: 802.11 n and 802.11 ac_. Cambridge university press, 2013.
  * [29] ns3, https://www.nsnam.org/, accessed: 2018-07-15.
  * [30] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” _IEEE Journal on selected areas in communications_ , vol. 18, no. 3, pp. 535–547, 2000.
  * [31] A. Kumar, E. Altman, D. Miorandi, and M. Goyal, “New insights from a fixed point analysis of single cell IEEE 802.11 WLANs,” in _In Proc. of IEEE INFOCOM_ , 2005.
  * [32] D. Miorandi, A. A. Kherani, and E. Altman, “A queueing model for HTTP traffic over IEEE 802.11 WLANs,” _Computer networks_ , vol. 50, no. 1, pp. 63–79, 2006.
  * [33] F. Calì, M. Conti, and E. Gregori, “Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit,” _IEEE/ACM Transactions on networking_ , vol. 8, no. 6, pp. 785–799, 2000.
  * [34] M. Garetto and C.-F. Chiasserini, “Performance analysis of 802.11 WLANs under sporadic traffic,” in _In Proc. of Springer ICRN_ , 2005.
  * [35] K. Tan, H. Liu, J. Fang, W. Wang, J. Zhang, M. Chen, and G. M. Voelker, “SAM: enabling practical spatial multiple access in wireless LAN,” in _In Proc. of ACM MobiCom_ , 2009.
  * [36] A. B. Flores, S. Quadri, and E. W. Knightly, “A scalable multi-user uplink for Wi-Fi,” in _In Proc. of USENIX NSDI_ , 2016.
  * [37] P. Guide, “Intel® 64 and IA-32 Architectures Software Developer’s Manual,” _Volume 3B: System programming Guide, Part_ , vol. 2, 2011.
  * [38] V. Jacobson and S. McCanne, “Libpcap: Packet Capture Library,” _Lawrence Berkeley Laboratory, Berkeley, CA_ , 2009.
  * [39] P. B. Nayak, S. Verma, and P. Kumar, “Multiband fractal antenna design for cognitive radio applications,” in _In Proc. of IEEE ICSC_ , 2013.
  * [40] R. Endluri, P. B. Nayak, and P. Kumar, “A Low Cost Dual Band Antenna for Bluetooth, 2.3 GHz WiMAX and 2.4/5.2/5.8 GHz WLAN,” _International Journal of Computer Applications_ , vol. 975, p. 8887.
  * [41] P. B. Nayak, S. Verma, and P. Kumar, “Ultrawideband (UWB) antenna design for cognitive radio,” in _In Proc. of IEEE CODEC_ , 2012.
  * [42] P. B. Nayak, R. Endluri, S. Verma, and P. Kumar, “Compact dual-band antenna for WLAN applications,” in _In Proc. of IEEE PIMRC_ , 2013.
  * [43] P. B. Nayak, S. Verma, and P. Kumar, “A novel compact tri-band antenna design for WiMax, WLAN and bluetooth applications,” in _In Proc. of IEEE NCC_ , 2014.
  * [44] P. Nayak, “Performance Evaluation of MU-MIMO WLANs Under the Impact of Traffic Dynamics,” Master’s thesis, 2016.
  * [45] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP throughput: A simple model and its empirical validation,” _ACM SIGCOMM Computer Communication Review_ , vol. 28, no. 4, pp. 303–314, 1998.
  * [46] J. Padhye, V. Firoiu, and D. Towsley, “A stochastic model of tcp reno congestion avoidence and control,” 1999.
  * [47] N. Parvez, A. Mahanti, and C. Williamson, “An analytic throughput model for TCP NewReno,” _IEEE/ACM Transactions on Networking (ToN)_ , vol. 18, no. 2, pp. 448–461, 2010.
  * [48] Q. He, C. Dovrolis, and M. Ammar, “On the predictability of large transfer TCP throughput,” in _ACM SIGCOMM Computer Communication Review_ , vol. 35, no. 4. ACM, 2005, pp. 145–156.
  * [49] M. Kim, M. Médard, and J. Barros, “Modeling network coded TCP throughput: A simple model and its validation,” in _In Proc. of ACM VALUETOOLS_ , 2011\.
  * [50] B. Sikdar, S. Kalyanaraman, and K. S. Vastola, “An integrated model for the latency and steady-state throughput of TCP connections,” _Performance Evaluation_ , vol. 46, no. 2-3, pp. 139–154, 2001.
  * [51] S. Y. Oh, M. Gerla, and J.-S. Park, “MIMO and TCP: A case for cross layer design,” in _In Proc. of IEEE MILCOM_ , 2007.
  * [52] A. K. Chaurasia and A. K. Jagannatham, “Dynamic parallel TCP for scalable video streaming over MIMO wireless networks,” in _In Proc. of IEEE WMNC_ , 2013.
  * [53] A. L. Toledo, X. Wang, and B. Lu, “A cross-layer TCP modelling framework for MIMO wireless systems,” _IEEE transactions on wireless communications_ , vol. 5, no. 4, pp. 920–929, 2006.
  * [54] A. L. Toledo and X. Wang, “TCP performance over wireless MIMO channels with ARQ and packet combining,” _IEEE Transactions on Mobile Computing_ , vol. 5, no. 3, pp. 208–223, 2006.
  * [55] G. Bianchi, “IEEE 802.11-saturation throughput analysis,” _IEEE communications letters_ , vol. 2, no. 12, pp. 318–320, 1998.
  * [56] G. Bianchi and I. Tinnirello, “Remarks on IEEE 802.11 DCF performance analysis,” _IEEE communications letters_ , vol. 9, no. 8, pp. 765–767, 2005\.
  * [57] G. Bianchi, L. Fratta, and M. Oliveri, “Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 wireless LANs,” in _In Proc. of IEEE PIMRC_ , 1996.
  * [58] D. Miorandi, A. A. Kherani, and E. Altman, “A queueing model for HTTP traffic over IEEE 802.11 WLANs,” _Computer networks_ , vol. 50, no. 1, pp. 63–79, 2006.
  * [59] X. Liu, K. Ravindran, and D. Loguinov, “What signals do packet-pair dispersions carry?” in _In Proc. of IEEE INFOCOM_ , 2005.
  * [60] C. Dovrolis, P. Ramanathan, and D. Moore, “What do packet dispersion techniques measure?” in _In Proc. of IEEE INFOCOM_ , 2001.
  * [61] A. Pásztor and D. Veitch, “The packet size dependence of packet pair like methods,” in _In Proc. of IEEE International Workshop on Quality of Service_ , 2002.
  * [62] S. Keshav, “Packet-pair flow control,” _IEEE/ACM transactions on Networking_ , pp. 1–45, 1995.
  * [63] K. Lakshminarayanan, V. N. Padmanabhan, and J. Padhye, “Bandwidth Estimation in Broadband Access Networks,” in _In Proc. of ACM SIGCOMM_ , 2004.
  * [64] R. Kapoor, L.-J. Chen, L. Lao, M. Gerla, and M. Y. Sanadidi, “CapProbe: A Simple and Accurate Capacity Estimation Technique,” in _In Proc. of ACM SIGCOMM_ , 2004.
  * [65] K. Sui, M. Zhou, D. Liu, M. Ma, D. Pei, Y. Zhao, Z. Li, and T. Moscibroda, “Characterizing and Improving Wi-Fi Latency in Large-Scale Operational Networks,” in _In Proc. of MobiSys_ , 2016.
  * [66] F. Cangialosi, D. Levin, and N. Spring, “Ting: Measuring and Exploiting Latencies Between All Tor Nodes,” in _In Proc. of ACM IMC_ , 2015.
  * [67] N. Baranasuriya, V. Navda, V. N. Padmanabhan, and S. Gilbert, “QProbe: Locating the Bottleneck in Cellular Communication,” in _In Proc. of ACM CoNEXT_ , 2015.
  * [68] G. Jackson, P. Keleher, and A. Sussman, “A Ping Too Far: Real World Network Latency Measurement,” in _In Proc. of IEEE e-Science_ , 2015.
  * [69] J. Huang, C. Chen, Y. Pei, Z. Wang, Z. Qian, F. Qian, B. Tiwana, Q. Xu, Z. Mao, M. Zhang _et al._ , “Mobiperf: Mobile network measurement system,” _Technical Report. University of Michigan and Microsoft Research_ , 2011.
  * [70] Mingzhe Li, M. Claypool, and R. Kinicki, “WBest: a Bandwidth Estimation Tool for IEEE 802.11 Wireless Networks,” in _In Proc. of IEEE LCN_ , 2008\.
  * [71] R. Das, N. Baranasuriya, V. N. Padmanabhan, C. Rödbro, and S. Gilbert, “Informed Bandwidth Adaptation in Wi-Fi Networks using Ping-Pair,” in _In Proc. of ACM CoNEXT_ , 2017.
  * [72] N. D. Mickulicz, U. Drolia, P. Narasimhan, and R. Gandhi, “Zephyr: First-Person Wireless Analytics from High-Density In-Stadium Deployments,” in _In Proc. of IEEE WoWMoM)_ , 2016.
  * [73] K.-H. Kim, H. Nam, J.-H. Park, and H. Schulzrinne, “MoT: A Collaborative Network Troubleshooting Platform for the Internet of Things,” in _In Proc. of IEEE WCNC_ , 2014.
  * [74] K. Kim, H. Nam, and H. Schulzrinne, “WiSlow: A Wi-Fi network performance troubleshooting tool for end users.” in _In Proc. of INFOCOM_ , 2014.
  * [75] S. Rosen, S.-j. Lee, J. Lee, P. Congdon, Z. M. Mao, and K. Burden, “MCNet: Crowdsourcing Wireless Performance Measurements through the Eyes of Mobile Devices,” _IEEE Communications Magazine_ , vol. 52, no. 10, pp. 86–91, 2014\.
  * [76] N. Mishra, A. Chaurasia, A. Kallavi, B. Raman, and P. Kulkarni, “Usage of 802.11n in Practice: A Measurement Study,” in _In Proc. of IEEE COMSNETS_ , 2015.
  * [77] W. Zeng, J. Cote, X. Chen, Y.-A. Kim, W. Wei, K. Suh, B. Wang, and Z. J. Shi, “Delay Monitoring for Wireless Sensor Networks: An Architecture Using Air Sniffers,” _Elsevier Ad Hoc Networks_ , vol. 13, pp. 549–559, 2014.
  * [78] U. Paul, A. Kashyap, R. Maheshwari, and S. R. Das, “Passive Measurement of Interference in Wi-Fi Networks with Application in Misbehavior Detection,” _IEEE Transactions on Mobile Computing_ , vol. 12, no. 3, pp. 434–446, 2013\.
  * [79] L. DiCioccio, R. Teixeira, and C. Rosenberg, “Impact of Home Networks on End-to-end Performance: Controlled Experiments,” in _In Proc. of ACM HomeNets_ , 2010.
  * [80] Y.-C. Cheng, J. Bellardo, P. Benkö, A. C. Snoeren, G. M. Voelker, and S. Savage, “Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis,” in _In Proc. of ACM SIGCOMM_ , 2006.
  * [81] A. Kashyap, U. Paul, and S. R. Das, “Deconstructing Interference Relations in Wi-Fi Networks,” in _In Proc. of IEEE SECON_ , 2010.
  * [82] C. Rattaro and P. Belzarena, “Throughput prediction in wireless networks using statistical learning,” in _In Proc. of LAWDN_ , 2010.
  * [83] M. Mirza, K. Springborn, S. Banerjee, P. Barford, M. Blodgett, and X. Zhu, “On the accuracy of TCP throughput prediction for opportunistic wireless networks,” in _In Proc. of IEEE SECON_ , 2009.
  * [84] W. Zhou, Z. Wang, and W. Zhu, “Mining Urban Wi-Fi QoS Factors: A Data Driven Approach,” in _In Proc. of IEEE BigMM_ , 2017.
  * [85] I. Syrigos, N. Sakellariou, S. Keranidis, and T. Korakis, “On the Employment of Machine Learning Techniques for Troubleshooting Wi-Fi Networks,” in _In Proc. of IEEE CCNC_ , 2019.
  * [86] M. O. Khan and L. Qiu, “Accurate Wi-Fi Packet Delivery Rate Estimation and Applications,” in _In Proc. of IEEE INFOCOM_ , 2016.
  * [87] D. Croce, D. Garlisi, F. Giuliano, N. Inzerillo, and I. Tinnirello, “Learning From Errors: Detecting Cross-Technology Interference in Wi-Fi Networks,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 4, no. 2, pp. 347–356, 2018.
  * [88] M. Mellia, A. Carpani, and R. L. Cigno, “Tstat: TCP Statistic and Analysis Tool,” in _In Proc. of Springer QoS-IP_ , 2003.
  * [89] C. Favi, “CFTStat: A Tool for Passive Tcp Analysis, Statistics and User’s Web Experience Gathering.”
  * [90] Y. Chen and K. Hwang, “TCP Flow Analysis for Defense against Shrew DDoS Attacks,” in _In Proc. of IEEE ICC_ , 2007.
  * [91] L. Zhou, Z. Li, and B. Liu, “P2P Traffic Identification by TCP Flow Analysis,” in _In Proc. of IWNAS_ , 2006.
  * [92] W. Li, J. Zhang, and Y. Zhao, “Conflict graph embedding for wireless network optimization,” in _In Proc. of IEEE INFOCOM_ , 2017.
  * [93] X. Zhou, Z. Zhang, G. Wang, X. Yu, B. Y. Zhao, and H. Zheng, “Practical conflict graphs in the wild,” _IEEE/ACM Transactions on Networking (ToN)_ , vol. 23, no. 3, pp. 824–835, 2015.
  * [94] C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan, “Measurement-based models of delivery and interference in static wireless networks,” in _ACM SIGCOMM Computer Communication Review_ , vol. 36, no. 4. ACM, 2006, pp. 51–62.

##  Appendix A Bounds on $W_{\textrm{\tiny m}}^{*}$

We break the proof into two parts. (a) In the first part, we show that
$W_{\textrm{\tiny m}}^{*}$ is upper bounded by $4$. (b) In the second part we
show this maximum value occurs when $S_{vf}=S_{vr}$.

(a) Suppose that $S_{vf}=max(S_{vf},S_{vr})$. Consequently,

$W_{\textrm{\tiny m}}^{*}=\frac{2*(S_{vf}+S_{vr})}{S_{vf}}\leq 4$ (A.1)

The same can be shown when $S_{vr}=max(S_{vf},S_{vr})$.

(b) It can be further stated that

$W_{\textrm{\tiny
m}}^{*}=\frac{4*(S_{vf}+S_{vr})}{\frac{(S_{vf}+S_{vr}+|S_{vf}-S_{vr}|)}{2}}$
(A.2)

Suppose that $S_{vf}\geq S_{vr}$. When $W_{\textrm{\tiny m}}^{*}$ reaches its
upper bound, it follows that

$\frac{2*(S_{vf}+S_{vr})}{S_{vf}}=4$ (A.3)

It follows that $S_{vf}=S_{vr}$. Again, the same can be shown when $S_{vf}\leq
S_{vr}$. In the absence of the equality condition, Eq. A.3 will not be
solvable.

##  Appendix B Computation of Joint Distribution $P(h,b)$

We can limit ourselves to the case in which stations send just one effective
TCP ACK in each channel access ($S_{\textrm{\tiny STA}}=1$). The extension to
the case in which stations send $S_{\textrm{\tiny STA}}>1$ effective ACKs in
each channel access is trivial, since it just requires to scale the
distribution obtained for $S_{\textrm{\tiny STA}}=1$ accordingly.

To obtain an exact expression of $P(h,b)$ in the case of zero-delay backbone,
we separately account for the impact of the initial deterministic ACK at the
beginning of a cycle (see Fig. 3.6). So, let us first consider the
distribution produced by uplink transmissions following the first one. For
them, we actually compute the more detailed joint pdf $\hat{P}(h_{1},h_{2},b)$
where: $b$ is the maximum queue length; $h_{1}\geq 1$ is the number of queues
having exactly length $b$; $h_{2}\geq 0$ is the number of queues having length
strictly less than $b$. By conditioning on the backoff value $x$ extracted by
the AP, we can write:

$\displaystyle\hat{P}(h_{1},h_{2},b)=\int_{0}^{\infty}\binom{K}{h_{1}}\left[\frac{(\mu
x)^{b}}{b!}e^{-\mu x}\right]^{h_{1}}\cdot$
$\displaystyle\binom{K-h_{1}}{h_{2}}\\!\\!\left(\sum_{j=1}^{b-1}\frac{(\mu
x)^{j}}{j!}e^{-\mu x}\right)^{h_{2}}\\!\\!\\!\\!\\!e^{-\mu
x(K-h_{1}-h_{2})}\mu e^{-\mu x}{\rm\,d}x$ (B.1)

Despite their ugly look, integrals of the form (B) have a closed-form
expression, obtained by expanding them into a sum of contributions, each
leading to an analytical solution. Just as an example, in the case of $K=4$,

$\hat{P}(2,1,3)=\binom{4}{2}\binom{2}{1}\frac{1}{(3!)^{2}}\left(\frac{7!}{1!5^{8}}+\frac{8!}{2!5^{9}}\right)=\frac{3024}{390625}$

Note that $\hat{P}(h_{1},h_{2},b)$ are some ‘universal’ numbers that depend
only on $K$, and that can be computed once and forall and made available
through, e.g., a table lookup.

To derive the final joint pdf $P(h,b)$ we have to add the contribution of the
first deterministic ACK:

$\displaystyle P(h,b)=\sum_{h_{1}+h_{2}=h-1}P(h_{1},h_{2},b)\frac{K-h+1}{K}+$
$\displaystyle\sum_{h_{1}+h_{2}=h}P(h_{1},h_{2},b-1)\frac{h_{1}}{K}+\sum_{h_{1}+h_{2}=h}P(h_{1},h_{2},b)\frac{h_{2}}{K}$
(B.2)

In the above expression, the first summation corresponds to the case in which
the first ACK increases the user-diversity (and not $b$); the second summation
corresponds to the case in which the first ACK does not increase the user-
diversity (but it increases $b$); the third summation corresponds to the case
in which the first ACK does not increase neither the user-diversity nor $b$.

##  Appendix C Full Aggregation Case With Non-negligible Delay

We compute the transition probabilities of the Markov Chain by considering the
number of batches that can arrive from the backbone between two consecutive
transmissions by the AP, and the fact that the AP, if it receives at least one
batch, will transmit again after a number of transmissions by the stations
uniformly distributed in $0,1,\ldots,m_{1}+m_{2}$.

Let $p_{[m_{1},m_{2}\rightarrow m_{1}^{\prime},m_{2}^{\prime}]}$ denote the
transition probability from state $(m_{1},m_{2})$ to state
$(m_{1}^{\prime},m_{2}^{\prime})$. To avoid unnecessary complications, we
assume that batches flying in the backbone, in number $m_{3}=K-m_{1}-m_{2}$,
can arrive at the AP during an interval of duration

$V(m_{1},m_{2})=T(m_{1},F_{s}W_{\max})+\sum_{j=1}^{m_{1}+m_{2}}\left(\frac{1}{\mu
j}+T_{\textrm{\tiny up}}\right)$

comprising the AP transmission at the end of previous cycle plus the time
required by stations to send up all of their batches by competing only among
themselves. Let $\lambda=1/D$ be the arrival rate of a batch from the
backbone. With probability $e^{-\lambda m_{3}V}$ no batch arrives, and we get
the (set of) transitions

$p_{[m_{1},m_{2}\rightarrow 1,0]}=e^{-\lambda(K-m_{1}-m_{2})V(m_{1},m_{2})}$
(C.1)

The reason for transiting to state $(1,0)$ is that, eventually, one batch will
arrive at the AP, while all of the others will be still flying in the
backbone.

With probability

$\rho(k,m_{1},m_{2})=\binom{m_{3}}{k}(1-e^{-\lambda
V})^{k}e^{-\lambda(m_{3}-k)V}$

we have, instead, $k$ batch arrivals during $V$ ($1\leq k\leq m_{3}$).
Assuming for simplicity that all these arrivals occur before nodes start to
contend again on the channel, the AP will transmit the above $k$ batches after
a number of transmissions by the stations uniformly distributed in
$0,\ldots,m_{1}+m_{2}$, leading to the transition probability:

$p_{[m_{1},m_{2}\rightarrow
k,m_{1}+m_{2}-j]}=\frac{\rho(k,m_{1},m_{2})}{m_{1}+m_{2}+1}\qquad 0\leq j\leq
m_{1}+m_{2}$

Note that one of these transitions, specifically the one with $k=1$,
$j=m_{1}+m_{2}$, should be added (i.e., contribute) to the one introduced
before in (C.1) (we have preferred to split the two contributions, with abuse
of notation, for better readability).

With the above transition probabilities, one can then solve the Markov Chain
and obtain the stationary probability distribution $\pi_{m_{1},m_{2}}$.

It remains to explain how this distribution can be used to compute the
numerator and the denominator of throughput formula (3.1). The numerator
(average number of packets sent in a cycle) is simply:

$\sum_{m_{1},m_{2}}\pi_{m_{1},m_{2}}m_{1}F_{s}W_{\max}$

The denominator (average cycle duration) can be expressed instead as an
average ‘reward’ over all possible transitions:

$\sum_{m_{1},m_{2},m_{1}^{\prime},m_{2}^{\prime}}\pi_{m_{1},m_{2}}\cdot
p_{[m_{1},m_{2}\rightarrow m_{1}^{\prime},m_{2}^{\prime}]}\cdot
r(m_{1},m_{2},m_{1}^{\prime},m_{2}^{\prime})$

where $r(m_{1},m_{2},m_{1}^{\prime},m_{2}^{\prime})$ is the reward associated
to the transition from state $(m_{1},m_{2})$ to state
$(m_{1}^{\prime},m_{2}^{\prime})$. Hence, we only need to specify the rewards
associated to the possible state transitions. The reward associated to the
zero arrival transition (C.1) is $V(m_{1},m_{2})+\frac{D}{K}+\frac{1}{\mu}$.
Indeed, after the interval of duration $V$ all batches will be flying in the
backbone, and the first will arrive on average $D/K$ later, and will be sent
by the AP after an average backoff $1/\mu$.

The reward associated to the transition with probability
$p_{[m_{1},m_{2}\rightarrow k,m_{1}+m_{2}-j]}$ instead, is equal to

$T(m_{1},F_{s}W_{\max})+\sum_{i=0}^{j}\frac{1}{\mu(m_{1}+m_{2}+1-i)}+jT_{\textrm{\tiny
up}}$

since, after the transmission by the AP, we have $j$ transmissions by the
stations, each preceded by a contention phase of proper average duration.