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
Dr.HannaNgman Profile Pic
Dr.HannaNgman,Mauritius,Researcher
Published Date:23-12-2017
Your Website URL(Optional)
Comment
Client-Side Routing-Agnostic Gateway Selection for Heterogeneous Wireless Mesh Networks y    y Emmanouil Dimogerontakis , João Neto , Roc Meseguer , Leandro Navarro and Luís Veiga  Universitat Politècnica de Catalunya, Barcelona, Spain edimoger,jlneto,meseguer,leandroac.upc.edu y Tecnico Lisboa/INESC-ID Lisboa, Lisboa, Portugal luis.veigainesc-id.pt Abstract—Citizens develop Wireless Mesh Networks (WMN) IP tunnels. Guifi.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 guifi.net users. modification 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 guifi.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. I. INTRODUCTION 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 guifi.net community network deploy it incrementally, so that it works well for both baseline exemplifies 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 guifi.net exemplifies how participants are sharing several and routing algorithms, or any specific network features. Internet gateways among them for web access, the most The contributions of this paper are threefold. First, we popular traffic 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 confirms 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 guifi.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 guifi.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 fine compared to the improve- finding 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-benefit 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 traffic 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 III. OVERVIEW 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 modifications in the require the modification 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 find 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 modification (overloaded proxies, slow Internet connections or slow of the existing underlying routing protocols. internal network path) that would degrade significantly 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 specifically 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 response_c_p 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 mesh_rtt proxy ments suffice 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 mesh_rtt the load of the proxy, concerning the quality of the service elaborates on how TTFB can be used to estimate t . proxy 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 reflect 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 guifi.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 guifi.net networks and 3 proxies that are also being case. There are many proxies with little or no space and used by guifi.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 latency model. 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 request_c_p mesh_rtt_c_p 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 request_c_p 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 mesh_rtt_c_p t latency, equation (2), depends on the network the Vivaldi network. Although Vivaldi was designed to predict mesh_rtt_c_p 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. proxy_p 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 figure 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 traffic 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 unmodified 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 define 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 notifications). In this actual RTT. The error of a node is defined 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 defined 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 significant 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 traffic and using shared system scalability. In the specific 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 figure 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 traffic. 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 proxy_ttfb Vivaldi’s extended version to adapt to network changes. receive the first byte of response from the server thent response 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 reflects 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, proxy_ttfb proxy_p t depend on the available bandwidth of the calculated by equation (6) with the measured TTFB on the transport_response 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 significantly delayed of the end-server. Additionally, t depends due the proxy or network load, or proxies may complete a transport_response 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 define the extended TTFB, where be expressed as equation (5). the obtained t values are filtered with an exponential proxy_p 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 filtered value, while when is too low, the filtered 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 specific 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 proxy_ttfb representing the delays in the proxy’s Internet connection. client has not received the first 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 proxy_p 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 proxy_p 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 first experiment we evaluate the relation between the t and the proxy proxy_p 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 proxy_p tended TTFB estimators ( =0.05) seconds after the beginning of the experiment and t proxy_p 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 significant delays. Hence, we introduce artificial 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 figure 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 coefficient 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 coefficient 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, confirming 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 figure 13, where we observe that clients avoid oscillations by defining 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 significant 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 specific 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) vivaldi ttfb 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 traffic when probing. The overhead disruptions of the provided service. The clients use the network traffic generated by Vivaldi is, in bytes per second: proxies selected by the routing strategies to repeatedly download files of 1 Mb from the same remote server overhead = (2ping ping +data)n (8) vivaldi size freq 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 freq download the file, 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 guifi.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 figure 12. As depicted, min_hop and min_delay present daily incoming Internet traffic 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 significantly 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) ttfb a time perspective as well as individual selection choices payload = payload +payload (12) that would provide stable aggregate results without further request response overhead as the system scales, given the decentralized nature timeout =m proxy +m num_closer+b (13) 1 2 distance of our solution that avoids the overhead of global coordination. Whenever a client overcomes the personalized timeout in the VIII. CONCLUSIONS 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 finally 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=(N1), 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 2 guifi.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 traffic. 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 traffic 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 file downloads, where latency requirements are less relevant. global decisions. Therefore there are no participants whose ACKNOWLEDGMENT 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 traffic, 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. Available: http://www.internetsociety.org/globalinternetreport/2015/ 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 guifi.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), community Networks. 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 wifi 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 Available: http://www.itu.int/pub/D-PREF-TTR.16-2015 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. cfm?doc_id=7390 20 J. Ledlie, M. Seltzer, and P. Pietzuch, “Proxy network coordinates,” 7 R. Baig, R. Roca, F. Freitag, and L. Navarro, “guifi.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 20–27, 2016. and Systems (USITS), vol. 4. USENIX Association, 2003, pp. 17–17. 11 M. Boushaba and A. Hafid, “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. 689–694. 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 719–733, 2014. 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. 1904.