Client-Side Routing-Agnostic Gateway Selection for Heterogeneous Wireless Mesh Networks
Best path to best gateway scheme for multichannel multi-interface wireless mesh networks Advances in wireless community networks with the community-lab testbed
Client-Side Routing-Agnostic Gateway Selection for
Heterogeneous Wireless Mesh Networks
Emmanouil Dimogerontakis , João Neto , Roc Meseguer , Leandro Navarro and Luís Veiga
Universitat Politècnica de Catalunya, Barcelona, Spain
Tecnico Lisboa/INESC-ID Lisboa, Lisboa, Portugal
Abstract—Citizens develop Wireless Mesh Networks (WMN) IP tunnels. Guiﬁ.net’s registered users (12,500) can use any
in many areas as an alternative or their only way for local
of the 356 web proxies (May 2016). In addition, the network
interconnection and access to the Internet. This access is often
links between nodes are contributed and managed by the
achieved through the use of several shared web proxy gateways.
participants. Therefore, paths between nodes, such as client to
These network infrastructures consist of heterogeneous technolo-
proxy may not be reliable 8 or guaranteed, especially when
gies and combine diverse routing protocols. Network-aware state-
of-art proxy selection schemes for WMNs do not work in this compared to commercial offerings from centrally managed
heterogeneous environment. We developed a client-side gateway
ISPs. Access to the Internet through web proxy gateways
selection mechanism that optimizes the client-gateway selection,
relies on users or organizations sharing the full or spare
agnostic to underlying infrastructure and protocols, requiring no
capacity of their Internet connection with other guiﬁ.net users.
modiﬁcation of proxies nor the underlying network. The choice is
As a consequence of the lack of regulation, and despite
sensitive to network congestion and proxy load, without requiring
a minimum number of participating nodes. Extended Vivaldi being a critical service for the community, current proxy
network coordinates are used to estimate client-proxy network
gateway services are quite fragile, especially considering
performance. The load of each proxy is estimated passively by
large-scale usage 9. Some proxies may be overloaded and,
collecting the Time-to-First-Byte of HTTP requests, and shared
therefore, offer degraded or unusable performance, while
across clients. Our proposal was evaluated experimentally with
others may remain underutilized. Users of overloaded proxies,
clients and proxies deployed in guiﬁ.net, the largest community
wireless network in the world. Our selection mechanism avoids or those using congested links to reach their proxy, experience
proxies with heavy load and slow internal network paths, with
degraded quality of experience (QoE) in web access. It is
overhead linear to the number of clients and proxies.
interesting to note that the set of overloaded and underutilized
proxies varies according to the access patterns of the users.
In this paper we focus on the challenges to improve web
The majority of the world’s population does not have access experience in an heterogeneous large-scale inter-WMN
adequate, if at all, access to the Internet 1. This implies
community, using a pool of shared web proxies. The challenge
that the Internet cannot provide service to the general public,
is that client-nodes could select the right proxy according to
reaching anyone without discrimination. Global access to the
the network path performance and the status of available web
Internet requires a dramatic reduction in the Internet access
proxies. This is related with the net effect, which explores the
costs, especially in geographic areas and populations with low
problem of a large population of C clients who can browse the
penetration 2. Wireless Mesh Networks (WMNs) 3 allow
web taking advantage of the aggregated capacity of a pool of
local communities to build their own network infrastructures,
P web proxies, with C P, over a heterogeneous WMN in-
known as Community Networks (CNs), providing affordable
frastructure, at a fraction of the cost of C Internet connections.
inter-networking with the Internet and including isolated
To tackle this issue, we aim to improve the proxy system,
rural communities worldwide 4. Sharing resources, such as without making any changes that could be incompatible with
infrastructure or Internet access, is encouraged at all levels 5, the existing environment. The solution should be: i) Incre-
6 to lower the cost of network infrastructures and services. mental and backwards-compatible since we should be able to
Among many others, the guiﬁ.net community network deploy it incrementally, so that it works well for both baseline
exempliﬁes how communities can develop their own or enhanced clients. ii) Dynamic since users should switch
network infrastructures as a commons 7, using several proxies wisely to maximize their QoE. This can be due to
interconnected WMNs. This results in a large-scale network changes in network topology, path load, or proxy performance.
with heterogeneous network performance, which uses diverse iii) Decentralized therefore not requiring any central compo-
routing protocols in different network zones. Moreover, nent. iv) Routing-agnostic thus independent of the transport
guiﬁ.net exempliﬁes how participants are sharing several and routing algorithms, or any speciﬁc network features.
Internet gateways among them for web access, the most The contributions of this paper are threefold. First, we
popular trafﬁc in CNs. This resource sharing is typically propose and evaluate a mechanism where clients use two
implemented using web proxies, and at a smaller fraction, by latency-based metrics to rank proxies and select the top ones in
arXiv:1708.02893v1 cs.NI 9 Aug 2017terms of QoE, or to switch to the next best proxy when perfor- Internet Connection (available capacity). 11, 13 require
mance degrades (see Sec. VI). Second, we evaluate a network the gateways to participate in the monitoring process by
performance metric based on the usage of the Vivaldi network measuring the queue length of their Internet interface,
coordinates and for external nodes to the Vivaldi network (web while 15 is performing active probes. Contrary to these
proxies), in a heterogeneous wireless network environment approaches, our solution is totally passive, implying though
(see Sec. IV). Third, we design and evaluate a web proxy less accuracy in exchange of saving scarce network resources.
performance estimator based on Time-To-First-Byte (TTFB), As presented later, we used the Vivaldi 17 network coor-
which is typically used to measure destination web servers dinates system for estimating network performance. From an
(see Sec. V). The proposed mechanism is client-side, as abstract perspective, network coordinates are a virtual position-
described in the overview of our approach (see Sec. III). Our ing system where nodes gather information about the network
evaluation conﬁrms that our mechanism can avoid hotspots, to position themselves and other nodes in a coordinate space
while maintaining a low overhead as proved in Sec. VII. and are used to estimate the inter-node latency. Vivaldi 17 is
The metrics and the client selection mechanism were a fully distributed network coordinates system that functions
instantiated in guiﬁ.net using the Community-Lab.net 10 based on the idea of placing nodes in a two-dimensional eu-
infrastructure. In this mechanism, nodes are acting as clients clidean space. The measuredping latency between the nodes is
interacting with a set of guiﬁ.net web proxies. Experimental used to position them in the euclidean space. In addition to the
results show that our proposal is reliable and effective: our probing, Vivaldi also uses spring-relaxation to nudge nodes in
method is able to provide good measures of client-proxy and the Euclidean space to minimize prediction errors. While there
proxy-Internet latencies, following its variability. We found have been proposals for updates of the Vivaldi algorithm the
out that our client selection mechanism is cost-effective in original algorithm is performing ﬁne compared to the improve-
ﬁnding proxies that result in good web performance and QoE ments 18. Moreover, the state of the art of network coordi-
for users. Our results show improvements in the cost-beneﬁt nates includes more sophisticated and more accurate systems,
of our proposal in comparison with other quick-to-measure which nevertheless are not fully distributed since they are
alternatives (such as Vivaldi-only and minimum hops). Our based on the idea of the external landmarks, like Pharos 19.
mechanism also proved to be less costly in trafﬁc and delay
As it can be seen, while the performance measurement and
than slower performance-oriented measures.
gateway selection in WMNs are had been studied in the past,
the existing approaches cannot be applied in a large-scale
II. RELATED WORK
heterogeneous environment, as in the presented scenario.
Our proxy selection problem is strongly related with
the topic of gateway selection in wireless mesh networks
which has been extensively studied in the past. The works Our goal is to design a practical, non-optimal but best-
presented in 11, 12 fail to function in heterogeneous effort, scheme where clients (user nodes) can select a proxy
environments since they present solutions that operate in using network and proxy performance metrics that would not
the mesh routing layer as they require modiﬁcations in the require the modiﬁcation of any network components and that
infrastructure routers, inherently prohibitive in heterogeneous could function in a heterogeneous environment. To this end,
environments. 13, 14 require additional software in the side we implemented an estimation-based monitoring framework
of the gateways. All the works mentioned, despite proposing for proxy selection, where clients cooperate sharing their
interesting solutions, they lack practical implementation or network and proxy performance estimations in order to
testing in a real environment. An exception to the above,
prioritize their list of known proxies. This allows clients to
and closer to our work is 15, where the clients cooperate
be able to make an informed proxy selection decision. Unlike
to probe the gateways and then use the results to select a other proposals, the framework does not try to ﬁnd an optimal
proxy. Furthermore, while conceptually 15 can function in client-proxy assignment, but helps clients avoid bad choices
heterogeneous environments, in practice it needs modiﬁcation (overloaded proxies, slow Internet connections or slow
of the existing underlying routing protocols. internal network path) that would degrade signiﬁcantly their
Concerning heterogeneous wireless mesh network service experience. The non-optimality is the price we have to
performance measurements, the majority of the solutions for pay in order to achieve a scalable and practical solution that
wireless mesh networks are based on active monitoring of can be applied in real heterogeneous WMNs while retaining a
network metrics, such as path delay in 15, 16, estimated low overhead. The proposed framework is user-friendly. This
link quality in 11, 13, link interference in 11, 13 means that the users do not manage the proxy selection nor
and path packet loss rate in 15. All these approaches switching. They just need to install our component in their
would entail a high monitoring overhead, except 15, where client nodes. It is also important to note that we do not cover
monitoring is done cooperatively to reduce the overhead. the orthogonal problem of proxy discovery in this work. We
As far as Internet gateway performance measurement is assume the set of proxies are known beforehand by the clients.
concerned all the above proposals use active measurements The network performance estimator provides estimates of
to evaluate its performance. More speciﬁcally 16 uses the client-client and client-proxy network latency. It is based
a congestion delay function, 12 monitors the unused on Vivaldi network coordinates 17 and extended in a similarway to 20 in order to estimate the round-trip latency of nodes is measuring it. In Section V we validated this assumption.
that are not part of the Vivaldi network – the proxies. All the Finally,t is the time that proxyp takes to complete
clients of the proxy selection system participate in the Vivaldi the HTTP request. This time depends on the load and capacity
network, exchanging a small amount of messages periodically, of the proxy’s Internet connection and on the latency to access
which allows them to maintain an updated view of the latencies and retrieve the content, related to the distance from the
across them. Moreover, each client periodically has to monitor content and content availability. From all the above, we deduce
one of the proxies and share this information with the rest of that the request latency can be approximated by equation (3).
the clients. As we demonstrate in Section IV, these measure- We argue thatt andt can provide clients with
ments sufﬁce to allow the clients to create a preference list, a good preference indicator allowing them to avoid loaded
which orders the proxies according to their network latency. proxies and proxies located in slow paths. Section IV describes
The proxy performance estimator provides estimates of how we use Vivaldi to estimate t , while Section V
the load of the proxy, concerning the quality of the service elaborates on how TTFB can be used to estimate t .
currently being provided. It is based on the widely used Experimental Environment In order to assess our
practical assumption that the TTFB of an HTTP request can decisions, we experimented separately with each component
reﬂect the service performance 21, 22. In our framework, of our solution. Following the practical approach of our
each client passively calculates the TTFB of the HTTP replies work, we decided to perform our experiments in guiﬁ.net,
that he receives from his proxy. Then the client can use this under real heterogeneous wireless network conditions. For
value to estimate the load of his proxy and share it with his the experiments, we were given access to 5 end-nodes across
Vivaldi neighbors. Notice that cache does not help in this different guiﬁ.net networks and 3 proxies that are also being
case. There are many proxies with little or no space and used by guiﬁ.net users. The nodes and the proxies are
most of the requests are not cacheable, as we show in 9. distributed in various locations of Catalonia, Spain. Despite
In addition, the mechanism is applicable to non-transparent the small scale of our experiments, we are still able to assess
gateways such as NATs. Our proxy load estimator, based on the behavior of the presented components.
latency (TTFB), is at application layer, so it could perform As explained in Section IV, proxies do not actively
on any type of gateway that accept HTTP requests. As we participate in the measurements, they nevertheless, need to
present in Section V, this mechanism allows clients to avoid respond to UDP pings, allowing clients to estimate their
proxies with heavy load or high delay Internet connections. round-trip latency. While for the results presented here we
System Model For the model description we assume a static used a UDP echo server in the proxies, obstacle which can
be practically overcome with tools such as Scriptroute 23.
wireless network topology. We make no assumptions about the
quality of the network, and we allow dynamic link conditions
IV. NETWORK PERFORMANCE ESTIMATION
(a very slow link is indistinguishable from a very congested
In this section we describe and demonstrate how an
link). Latency is our metric of load, for both links and proxies.
extended version of Vivaldi 17 can be used to estimate the
Let C denote the set of clients (user nodes), and P denote
current performance of the network, expressed as a latency
the set of proxies. For every request that a client c2 C is
metric, helping the clients to avoid overloaded paths.
sending to a proxyp2P , equation (1) shows the experienced
Estimating Latency with Network Coordinates Each
client in our system participates in a Vivaldi network
t t +t +t (1)
lat request_c_p proxy_p response_c_p
coordinates system to estimate his round-trip latencies to the
t At (2) other clients. Based on the clients’ network coordinates, we
implement the ideas described in 20, modifying them to
t 2t +t +t (3)
lat mesh_rtt_c_p proxy_p response_c_p
provide more accurate estimates and to estimate latencies
for external nodes to the Vivaldi network. We show that this
Where t represents the time required by client c
allows the clients to maintain an updated estimation about
to connect to proxy p and send the request. It is proportional
to the round-trip time between c and p, t . The their latency towards each proxy, but excluding proxies from
t latency, equation (2), depends on the network the Vivaldi network. Although Vivaldi was designed to predict
conditions of the chosen path between client c and proxy latency between hosts in the Internet (mostly wired), we show
p. For the rest of this paper we assume that A equals to 2, that it can also be used to predict latencies in WMNs despite
which corresponds to the client-proxy TCP handshake and the the RTT variations caused by the wireless environment.
HTTP request. The t latency represents the total time Vivaldi estimates RTT by sending ping between nodes.
that proxyp needs to process the request until he initiates the Each Vivaldi node maintains a list ofC+R neighbors:C that
request to the remote server. This includes the time that the are estimated to be the closest nodes, and R other random
request is waiting before starting to be served, which is a good nodes, located anywhere in the network. The algorithm works
indicator of the load of proxy p, as it correlates directly with in rounds, which are triggered every T seconds. In every
the number of outstanding proxy requests yet to be served. We round, a node randomly selects a neighbor from the list, sends
assume that at a given point in time different clients experience N UDP pings to him, and asks him to send back its own pings
the same t if they use proxy p, independently of who and its neighbors’ coordinates. The variablesC andR can be
proxy_ptuned depending on the size of the network and the topology rounds to adjust its estimates to be over 200 ms. However,
in order to increase random/remote node discovery or to create as seen in ﬁgure 6, proxy estimates are much faster to adapt,
strong local clusters. The variable N affects the accuracy of taking around 12 rounds to re-adjust the estimates.
the prediction in exchange for the ping trafﬁc overhead. We show that our system can, under real heterogeneous
Using the client-client estimations we can satisfactorily mesh network conditions, estimate the round-trip times be-
predict round-trip latency from a Vivaldi node to each proxy, tween clients as well as between clients and proxies with errors
leaving the proxies unmodiﬁed since they do not actively smaller than 5 ms and 2.5 ms respectively. These low predic-
participate in the network coordinates system. In this extended tion and triangulation errors (median relative error in the range
Vivaldi version, each Vivaldi node maintains coordinates that of 10%) are comparable to the original Vivaldi on the Internet.
represent C +R proxies, as described above. In every round, Moreover, we observe that our estimation can eventually trace
a node performsN UDP pings to a proxyp, which is selected serious anomalies in the latency of paths. Therefore, we argue
in a similar manner than how the node selects its neighbors. that these estimates are satisfactory in order to prioritize paths
Then, the node updates the coordinates it maintains for p and from clients to proxies that present differences in latency
shares the measured latency with its selected neighbor for higher than 5 ms and avoid highly loaded paths.
this round. Then, the neighbor updates the coordinates that it Estimation Based on Other Metrics We decided to focus
maintains for proxy p as described in 20. on latency as the most relevant distance metric, considering
Latency Estimation Evaluation For our evaluation, simi- that the type of web access most essential to users is
larly to 17, we deﬁne the error of a path as the absolute differ- comprised of typically small HTTP requests and replies (web
ence between the predicted RTT for the path (using the coordi- requests requesting updates to mailboxes, blogs and social
nates for the two nodes located at the ends of the link) and the network sites, messaging apps, and notiﬁcations). In this
actual RTT. The error of a node is deﬁned as the median of the context, latency is the most relevant metric to consider in
path errors for paths involving that node. The error of the sys-
order to assess quality-of-service as perceived by users.
tem is deﬁned as the median of the node errors for all nodes.
Considering other web access patterns where larger content
We experimented, using the described environment, in order
dominates (non-essential, though popular), we can adapt
to characterize the behavior of the Vivaldi coordinates in an
the Vivaldi network coordinates system to employ different
heterogeneous large-scale wireless mesh network. First, we
distance metrics, estimating minimum (or median) sustained
performed an experiment where clients are using Vivaldi to
throughput (instead of latency) without signiﬁcant additional
estimate the latencies between them and the extended version
overhead. Existing approaches, such as Spruce 24, exploit
of Vivaldi to estimate their RTT to the proxies. This way the probe gap model (PGM) to collect information about
we can understand the predictive potential of the selected time gaps over consecutive probe packets. This approach
algorithms. It is worth reminding that our experiment was precludes the need for large data transfer to infer throughput
executed in nodes that participate in a real network and that would seriously affect clients, proxies, hindering overall
therefore were processing real network trafﬁc and using shared system scalability. In the speciﬁc context of multimedia
links. Figures 1 and 2 show the real and predicted latencies be- streaming, related estimation and adaptation techniques for
tween clients throughout the experiment. The median latency video streaming over HTTP 25 could be used instead.
between the clients was 22.29 ms, while the predicted median
V. PROXY PERFORMANCE ESTIMATION
was 20.82 ms. The median latency between clients and proxies
was 9.8 ms while the corresponding predicted median was This section shows how TTFB can estimate the current
performance of the proxy, expressed as a latency metric,
9.36 ms. Figure 3 depicts the absolute prediction error of the
allowing clients to rank choices, avoiding overloaded proxies
Vivaldi estimation between clients as well as the one between
and proxies with Internet connection that exhibit high delays.
clients and proxies. We observe that the error of the latency
Estimating Proxy Load with TTFB TTFB has been
prediction between clients and proxies is lowerThis can be
widely used in real deployments but also in recent Internet
attributed to the smaller variation of the real latency between
clients and proxies, but also to our improvements related to measurement research 21, 22 to indicate the responsiveness
20. The empirical cumulative distribution function of the of a web service since it combines the TCP connection time
absolute errors of the prediction, as seen in ﬁgure 4, shows and the remote server processing time. Moreover, TTFB is
that the median absolute error of the predicted latency between a useful web performance estimator because it is measured
clients is 3.37 ms, while 80% of the experimentation time the passively on the client-side, leveraging information from the
nodes had a median error of less than 5 ms. As far as client- already existing client trafﬁc. Nevertheless, our scenario is
proxy Vivaldi latency prediction is concerned, the median ab- more complicated, since we aspire to utilize client-side TTFB
solute prediction error is 1.07 ms, while 80% of the experimen- measurements to estimate the performance of the proxy
tation time the nodes had a median error of less than 2.5 ms. between the client and the requested content.
In our second experiment we tested the ability of the Assuming that t is the time the proxy needs to
Vivaldi’s extended version to adapt to network changes. receive the ﬁrst byte of response from the server thent
Figure 5 shows that there is some delay for Vivaldi to adapt from equation (3) can also be expressed as equation (4).
to latency changes between the clients, taking around 30 Where t is the time until the client has
transport_responseFigure 1. Clients’ estimated latency can track Figure 2. Clients/Proxies estimated latency Figure 3. Clients/Proxies estimated RTT error
RTT behaviour but with various faulty spikes. successfully tracks RTT behaviour. is lower than Clients’ RTT error.
Figure 4. Clients/Proxies estimated RTT error Figure 5. Predicted Clients’ RTT reﬂects the Figure 6. Predicted Clients/Proxies RTT adapts
is asymptotically lower than Clients’ RTT error. changes in real RTT for clients but slowly fast to changes in real RTT
received the complete response. Both t and t can provide an estimation of the proxy performance,
t depend on the available bandwidth of the calculated by equation (6) with the measured TTFB on the
proxy Internet connection, and the delays in the path from the client-side and the network. However, the TTFB measurements
proxy to the destination server, as well as the responsiveness can be very noisy (sometimes packets are signiﬁcantly delayed
of the end-server. Additionally, t depends due the proxy or network load, or proxies may complete a
on the performance of the client-proxy path. Considering request quickly despite heavy load). To minimize the effect of
equation (3), the TTFB as measured on the client-side can noise on our estimation, we deﬁne the extended TTFB, where
be expressed as equation (5). the obtained t values are ﬁltered with an exponential
moving average which can be tuned by a parameter . When
t t +t (4)
response_c_p proxy_ttfb transport_response
is too high, the effect of noise in the measurements leaks
t 2t +t +t (5)
into the ﬁltered value, while when is too low, the ﬁltered
ttfb_c_p mesh_rtt_c_p proxy_p proxy_ttfb
values adapt slower to the measured real values, smoothing
t t 2t (6)
proxy_p ttfb_c_p mesh_rtt_c_p
the peaks and valleys. Moreover, since the TTFB of HTTP
t differs depending on the proxy, the remote server
proxy_ttfb requests is measured periodically, we must handle delays
and the requested content. The analysis of the variability of
that are higher than the measurement period. Therefore, we
different t latencies, related to how well the proxies
proxy_ttfb introduced a penalty scheme to extended TTFB, assuming
are connected to speciﬁc remote servers, lies beyond the scope
that the request will eventually be completed. Our scheme is
of this work. Therefore, in our current work we choose not to
based on the simple idea that the TTFB value will be at least
study t and assume it is stationary for each proxy,
as high as the time that the client waited for it. Thus, if a
representing the delays in the proxy’s Internet connection.
client has not received the ﬁrst byte for longer than the last
Nevertheless, as part of our future work we plan to investigate
t value then the estimated value keeps increasing in
whether and how it is possible to create an estimation model,
every measurement period until it is received.
where each client will be able to use his current and previous
HTTP connections to various remote servers in order to iden- Clients periodically exchange the calculated t , thus
tify how this metric affects the measured TTFB. For the rest of reducing the need for probing, as the value indicates how good
this work we assume that all the clients are trying to access the a proxy is at serving requests for any client. These messages
same content that is always available, located in remote servers are forwarded through the Vivaldi network. Currently, we as-
in similar distance from all the proxies and all the proxies have sume that the client is performing HTTP requests sequentially.
the same Internet connection bandwidth capacity. However, this is not a realistic assumption, since in a typical
Therefore, based on equations (3) and (5), the latency scenario a browser generates multiple parallel HTTP requests
incurred by the proxy could be expressed as equation (6). targeting different servers. As part of our future work we planFigure 7. Estimators can assimilate proxy load Figure 8. PCA: Extended estimator ( = 0:05) Figure 9. Responsiveness of estimators to In-
metrics behaviour ( = 0:05) can track high proxy load ternet connection delays ( = 0:05)
to investigate how to choose or combine measures from mul-
tiple HTTP transfers to estimate a TTFB value for each proxy.
Proxy Load Estimation Evaluation In our ﬁrst experiment
we evaluate the relation between the t and the proxy
load. The proxy load is represented by various variables
monitored on the proxy, including the CPU and the number
of incoming and outgoing packets per second in the internal
and the external interfaces. Figure 7 allows the comparison
between the normalized median of the proxy variables
compared to the estimation and the extended estimation of
Figure 10. Strong correlation (Spearman’s rank) between the clients’ Ex-
t . The proxy is loaded with external requests 150
tended TTFB estimators (=0.05)
seconds after the beginning of the experiment and t
starts presenting high peaks while the extended estimator
accurate estimator in terms of absolute values, but has a
presents a more clear relation to the load behavior. Figure 8
behavior similar to the proxy load, enabling the client to rank
presents another perspective of the relation between the
choices and avoid saturated proxies. Moreover, the extended
proxy load and the extended estimator, including the plot of
estimator calculated by one client behaves similarly throughout
the Principal Component Analysis which demonstrates that
the different clients and can, thus, be disseminated across them
the higher the load values are the higher the values of the
reducing the overhead and allowing clients to have updated
extended estimator. As a result, we can argue that our extended
information concerning proxies they are not currently using.
estimator is behaving similarly to the proxy load, and therefore
we can claim it can be used to detect heavily loaded servers.
VI. PROXY SELECTION
The goal of our second experiment was to evaluate how
After describing our approach for measuring the
our estimator responds to proxies having Internet connections
with signiﬁcant delays. Hence, we introduce artiﬁcial network performance of the network and the proxies, in this
delay in the external network interface of the proxy. As seen in section we describe how clients are able to select proxies
informed by the presented metrics. Moreover, we present an
ﬁgure 9, both the simple and the extended estimator success-
experiment where clients, adopting our solution, manage to
fully measure the introduced delay. Nevertheless, the extended
avoid overloaded proxies, very slow internal paths and very
estimator appears to need more time to return to the normal
slow Internet connections, whereas if a minimum hop or
levels, as expected. Therefore, we verify that our estimators
minimum delay selection approach was to be adopted, the
are responsive to the proxies’ Internet connection delays.
clients would not be able to avoid service deterioration.
Sharing Estimations Across Clients Despite the fact that
On top of our performance estimation tools we built
our estimators behave similarly with the proxy load, we need
an application-level proxy selection platform. Each client
to verify that the estimator measured from clientc for proxyp
maintains a proxy selection table, similarly to a routing table,
can be useful for other clients as well. To investigate this issue,
where each line corresponds to a known proxy and contains
we performed an experiment where one single proxy was used
the estimated distance, as described in section IV, the extended
that was serving all the nodes. Figure 10 represents the Spear-
estimation of the proxy latency, as described in section V and
man’s rank correlation coefﬁcient 26 between the extended
the number of hops to that proxy. Based on this information
estimators of the different clients throughout the experiment.
Spearman’s rank correlation coefﬁcient targets to identify various proxy selection strategies can be implemented.
correlations that can be expressed by a monotonic function, Nevertheless, the implementations need to take into account
thus resulting in high values, as we observe in our result, when the described sensitivity of the provided estimators.
both of the compared sets ascend or descend similarly. We used the provided estimators to implement a proxy
The described proxy performance estimator is not an selection strategy suitable to their rationale, aiming to avoidsaturated proxies, proxies with saturated Internet connection as more apparent for min_hop, that is a static strategy. min_load
well as proxies behind saturated paths. Therefore, the selection manages to minimize the number of peaks, conﬁrming our
strategy orders the proxies according to the sum of the network argument that it succeeds to avoid the loaded options. The
latency estimation and the proxy latency estimation, selecting manner in which min_load is avoiding the loaded options is
the lowest value. Our implementation avoids unnecessary also shown in ﬁgure 13, where we observe that clients avoid
oscillations by deﬁning a minimum threshold which should be proxy_3 when loaded by requests (150-350 seconds), as well
overcome in order to change the selected proxy. Additionally, as proxy_2 in the ranges of 550-650 seconds and 1050-1350
we implemented a recovery mechanism for situations where a seconds where we simulate the network path delay and Internet
proxy is not being used by any client for a signiﬁcant amount connection delay respectively. It is also worth pointing out that
of time, therefore his current performance estimation value in the performed experiment min_delay and min_hop do not
is unknown. In order to prevent all the clients from querying appear to be affected by some of the obstacles introduced, but
the proxy at the same time, the clients maintain a personalized this is a result of the speciﬁc experiment conditions (network
timeout that depends on a global recovery time, the locally last latencies and distances) and not of their ability to avoid it.
known measurement of the proxy and their personal network
The results we presented in this section verify how the
distance to that proxy. If the timeout is reached without
performance estimators presented in the previous sections can
receiving any updates, the client is actively probing the proxy
be used by clients to rank and make informed choices from
to learn its know TTFB value. This way, we manage to make
a large set of proxy Internet gateways, avoiding proxies that
clients that are close to the proxy in charge of querying it and
would deteriorate their user experience.
then propagate the information to the other nodes.
To evaluate our minimum load selection strategy, following
VII. OVERHEAD AND SCALABILITY ANALYSIS
an approach similar to 15, we implemented two simple
proxy selection strategies based on the minimum hop metric
The two performance estimation components of our system
and the minimum network delay metric, that were used to
function in parallel. Thus, the total overhead is :
compare to the minimum load solution. Under the minimum
hop strategy each client selects the closest proxy in terms of
overhead = overhead +overhead (7)
hops while in the minimum network delay strategy the clients
select the proxy that has the smallest Vivaldi latency estimator.
According to the challenges that Vivaldi 17 faces by
The objective of the evaluation experiment was to describe
design, a network coordinates system should produce a min-
how the different strategies of the clients deal with the
imal amount of overhead trafﬁc when probing. The overhead
disruptions of the provided service. The clients use the
network trafﬁc generated by Vivaldi is, in bytes per second:
proxies selected by the routing strategies to repeatedly
download ﬁles of 1 Mb from the same remote server
overhead = (2ping ping +data)n (8)
choosing every 10 seconds, our Vivaldi period, a new proxy
data = (n 160+n 160+10)=round (9)
vivaldi p n period
if necessary. The value of 1Mb was chosen because in normal
ping = round =round (10)
conditions a client needs less than the period of 10 seconds to pings period
download the ﬁle, therefore we can evaluate more accurately
In the formulas above, n represents the number of nodes in
the selection alterations. We adopt as evaluation metric the
the Vivaldi system and n and p are the maximum number
download time experienced by the clients. The experiment n n
of known neighbors and proxies, respectively. We can see that
lasted 1600 seconds and was repeated for each strategy.
the overhead of Vivaldi increases linearly with the amount of
Between 50 and 350 seconds we introduce a high amount
participants. Vivaldi works in rounds: in every round (which
of requests in one of the proxies. Between 550 and 850
occurs every few seconds) each node sends a few pings to
seconds we simulate in one of the proxies an external Internet
each one of its neighbors. In our deployment we use 8 pings
connection with high delays. Between 1050 and 1350 seconds
per round, with a round starting every 10 seconds. Moreover,
we simulate a slow network path in one of the proxies.
in our case it corresponds to one neighbor plus one proxy,
Figure 11 depicts the median clients’ download time per
and the maximum number of neighbors and proxies is 8. That
strategy. We observe that our strategy leads the clients to expe-
equates to 436 bytes per second per client, which is acceptable
rience a very small amount of download time peaks, especially
even in a wireless mesh network environment. For example,
compared to the static min_hops solution. The y axis of the
assuming all the 30,000 nodes of guiﬁ.net were clients, the
plot is limited to 2 seconds in order to allow easier comparison,
overhead would be approximately 1.5 MB/s, distributed all
nevertheless the overall distribution of the values can be seen
over the network, which sums up to be 1.6% of the average
in ﬁgure 12. As depicted, min_hop and min_delay present
daily incoming Internet trafﬁc 7 (data from 2015).
higher average values compared to min_load (0.76s,0.71s
and 0.48s respectively). Most importantly, related to avoiding The TTFB metrics are passively collected for the proxy
overloaded options, min_hop and min_delay have many currently selected by the client, and then shared between the
more and signiﬁcantly higher peaks compared to min_load nodes of the system. Nevertheless, we may ping a proxy if
(maximum 6.33s,4.89s and 1.23 respectively). This is even we have not had any metrics for a certain time period asFigure 11. Median client download time for Figure 12. Improvement of median user down- Figure 13. Clients avoid bad choices using
1Mb per strategy load time using min_load min_load strategy
described in Section VI. The network overhead of the proxy timator is proven to converge in large scale scale networks for
TTFB protocol (in bytes per second) is: the selected parameters. The global convergence of selection
is not trivial. We are considering probabilistic strategies from
overhead =O(proxies)payload=timeout (11)
a time perspective as well as individual selection choices
payload = payload +payload (12)
that would provide stable aggregate results without further
overhead as the system scales, given the decentralized nature
timeout =m proxy +m num_closer+b (13)
of our solution that avoids the overhead of global coordination.
Whenever a client overcomes the personalized timeout in the
proxy information, we query it. If we set them factor too low,
the information will not have time to propagate and many
Communities of citizens develop network infrastructures co-
nodes will query the proxy. However, if we set the m factor
operatively, based on heterogeneous Wireless Mesh Networks.
too high, it may take a long time until a node is ﬁnally queried.
They can achieve global Internet or Web access using a pool
Due to the randomly selected neighbors, let us make the
of web proxy gateways shared across many participants in
assumption that any node may be connected to any other
the local community network. This affordable Internet access
node. Let us assume that a single node pings the proxy. Then,
method requires a simple but effective mechanism to arbitrate
in the next round (assuming a synchronous model), any of the
the client-proxy selection, ensuring a good quality of service
other N 1 nodes may query this knowledgeable node with
and avoiding degradation in the user experience. This paper
probability 1=(N 1), pulling the desired proxy information.
introduces reliable and inexpensive latency-based metrics
The number of nodes learning the desired information at a
capable of predicting and triangulating performance indicators.
given round can be modeled through a binomial distribution
It also presents a client-side proxy selection mechanism that
with p =k=N, where k is the number of nodes that possess
combines these metrics to make good choices in terms of QoE
such information. The expected value is k – we expect k
or performance, taking into account the contribution of the
nodes learning the information at each round. This means that local network, proxy gateways and their Internet connection.
we expect all nodes, in average, to learn the information after This mechanism avoids heavy loaded proxies, proxies with
log (N) rounds. For the 30;000 nodes currently registered in slow Internet connection and slow internal network paths. The
guiﬁ.net, that equates to 15 rounds. Moreover, it is important
overhead is linear to the number of the clients and proxies.
to notice that equation (11) assumes that m and b parameters
Future work will explore the sensitivity of proxy delay-
are correctly tuned so that the proxy is contacted by a very
based metrics to diverse HTTP trafﬁc. We will utilize multiple
low number of nodes with high probability.
HTTP requests to improve proxy performance estimation and
Scalability Assessment The scalability of our approach use TTFB trafﬁc instead of the additional UDP pings for
stems from four main factors. First, the low client and
the client-proxy measures in our extended Vivaldi coordinate
proxy overhead which was already addressed in this section.
system. We also aspire to extend the system to account for
Second, the lack of need for centralized coordination, evident
bandwidth-demanding usage, like video streaming and large
in our approach, having no central coordinator in charge of
ﬁle downloads, where latency requirements are less relevant.
global decisions. Therefore there are no participants whose
processing, state or message load would grow boundless as
the number of clients and proxies increase. Third factor is This work was partially supported by the EU funded
bounded storage and trafﬁc, where state size and message Erasmus Mundus Joint Doctorate in Distributed Comput-
count exchanged by each client increase logarithmically ing (EMJD-DC) (FPA 2012-0030), the EU Horizon 2020
with the number of participants. Additionally, the gossip-like project netCommons (H2020-688768), the Spanish gov-
propagation of the estimators ensures fast propagation under ernment (TIN2016-77836-C2-2-R), and the Generalitat de
increasing number of nodes. The fourth factor is the good Catalunya (2014-SGR-881), the Fundação para a Ciência e
convergence of the estimators, where the Vivaldi network es- a Tecnologia (UID/CEC/50021/2013).REFERENCES 14 J. J. Galvez, P. M. Ruiz, and A. F. G. Skarmeta, “A distributed algorithm
for gateway load-balancing in wireless mesh networks,” in Wireless
1 Internet Society. (2015, October) Global internet report 2015. Online.
Days, 2008, pp. 1–5.
15 B. J. Ko, S. Liu, M. Zafer, H. Y. S. Wong, and K. W. Lee, “Gateway
2 G. WG, “Global access to the internet for all research group,” 2016,
selection in hybrid wireless networks through cooperative probing,”
Accessed 14-September-2016. Online. Available: https://irtf.org/gaia
in International Symposium on Integrated Network Management (IM),
3 D. Vega, R. Baig, L. Cerdà-Alabern, E. Medina, R. Meseguer, and
2013, pp. 352–360.
L. Navarro, “A technological overview of the guiﬁ.net community
16 E. Bortnikov, I. Cidon, and I. Keidar, “Scalable Load-Distance Bal-
network,” Computer Networks, vol. 93, Part 2, pp. 260 – 278, 2015,
ancing,” in International Symposium on Distributed Computing (DISC),
Berlin, Heidelberg, 2007, pp. 77–91.
4 C. Rey-Moreno, Z. Roro, W. D. Tucker, M. J. Siya, N. J. Bidwell, and
J. Simo-Reigadas, “Experiences, challenges and lessons from rolling out
17 F. Dabek, R. Cox, F. Kaashoek, and R. Morris, “Vivaldi: A decentralized
a rural wiﬁ mesh network,” in ACM Computing for Development (ACM-
network coordinate system,” ACM SIGCOMM Computer Communica-
DEV). ACM, 2013, p. 11.
tion Review, vol. 34, no. 4, pp. 15–26, 2004.
5 International Telecommunication Union. (2009, July) Trends in
18 Y. Chen, X. Wang, C. Shi, E. K. Lua, X. Fu, B. Deng, and X. Li,
telecommunication reform 2008. ch. six degrees of sharing. Online.
“Phoenix: A weight-based network coordinate system using matrix
factorization,” IEEE Transactions on Network and Service Management,
6 European Parliament and Council, “Directive 2014/61/eu of the european
vol. 8, no. 4, pp. 334–347, 2011.
parliament and the council of 15 may 2014 on measures to reduce the
19 Y. Chen, Y. Xiong, X. Shi, J. Zhu, B. Deng, and X. Li, “Pharos: accurate
cost of deploying high-speed electronic communications networks.” May
and decentralised network coordinate system,” IET Communications,
2014. Online. Available: http://ec.europa.eu/newsroom/dae/document.
vol. 3, no. 4, pp. 539–548, 2009.
20 J. Ledlie, M. Seltzer, and P. Pietzuch, “Proxy network coordinates,”
7 R. Baig, R. Roca, F. Freitag, and L. Navarro, “guiﬁ.net, a crowdsourced
Target, vol. 22, p. 25, 2008.
network infrastructure held in common,” Computer Networks, vol. 90,
pp. 150–165, 2015.
21 S. Sundaresan, N. Feamster, R. Teixeira, and N. Magharei, “Commu-
8 I. F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: A
nity contribution award – measuring and mitigating web performance
survey,” Computer networks, vol. 47, no. 4, pp. 445–487, 2005.
bottlenecks in broadband access networks,” in Internet Measurement
9 E. Dimogerontakis, R. Meseguer, and L. Navarro, “Internet access for
Conference (IMC). ACM, 2013, pp. 213–226.
all: Assessing a crowdsourced web proxy service in a community
22 F. Chen, R. K. Sitaraman, and M. Torres, “End-user mapping: Next gen-
network,” in Passive and Active Measurement Conference (PAM), 2017.
eration request routing for content delivery,” ACM SIGCOMM Computer
10 L. Navarro, R. B. Vinas, C. Barz, J. Bonicioli, B. Braem, F. Freitag, and
Communication Review, vol. 45, no. 4, pp. 167–181, 2015.
I. V. i Balaguer, “Advances in wireless community networks with the
23 N. Spring, D. Wetherall, and T. Anderson, “Scriptroute: A public internet
community-lab testbed,” IEEE Communications Magazine, vol. 54, pp.
measurement facility,” in USENIX Symposium on Internet Technologies
and Systems (USITS), vol. 4. USENIX Association, 2003, pp. 17–17.
11 M. Boushaba and A. Haﬁd, “Best path to best gateway scheme for
24 J. Strauss, D. Katabi, and M. F. Kaashoek, “A measurement study of
multichannel multi-interface wireless mesh networks,” in Wireless Com-
available bandwidth estimation tools,” in Internet Measurement Confer-
munications and Networking Conference (WCNC). IEEE, 2011, pp.
ence (IMC), 2003, pp. 39–44.
25 Z. Li, X. Zhu, J. Gahm, R. Pan, H. Hu, A. C. Begen, and D. Oran,
12 E. Ancillotti, R. Bruno, and M. Conti, “Load-balanced routing and
“Probe and adapt: Rate adaptation for HTTP video streaming at scale,”
gateway selection in wireless mesh networks: Design, implementation
IEEE Journal on Selected Areas in Communications, vol. 32, no. 4, pp.
and experimentation,” in World of Wireless Mobile and Multimedia
Networks (WoWMoM), 2010, pp. 1–7.
13 U. Ashraf, S. Abdellatif, and G. Juanole, “Gateway selection in backbone
26 C. Spearman, “The proof and measurement of association between two
wireless mesh networks,” in Wireless Communications and Networking
things,” The American journal of psychology, vol. 15, no. 1, pp. 72–101,
Conference, (WCNC). IEEE, 2009.