Andreea Anghel

Robert Birke

Mitch Gusat

Scalable High Resolution Traffic Heatmaps: Coherent Queue Visualization for Datacenters

Keywords: Network monitoring, L2 sampling, Traffic analysis, QCN

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The proliferation of Big Data applications -such as Hadoop, MapReduce -together with 10-100 Gbps datacenter networks (DCNs) -such as Converged Enhanced Ethernet (CEE), with µs latency -raises new challenges. One of them is the need for faster and scalable network monitoring methods. Deep understanding of such workloads and their communication patterns is key to the design of future workload-optimized datacenters. For example, the ability to accurately detect and optimize (via adapted routing) workload-induced congestion at fine granularity has significant potential in terms of reducing system cost and improving the application run-time [START_REF] Prisacari | Fast pattern-specific routing for fat tree networks[END_REF]. Switches today have outdated monitoring software that cannot cope with the sampling frequency and the network scale needed to orchestrate large datacenters. Hence our target is to coherently (i.e., time-space synchronized) and scalably detect, record and replay ephemeral -yet consequential -transients, essential for workload characterization: e.g., TCP Incast [START_REF] Zhang | Modeling and understanding TCP incast in data center networks[END_REF], Head-of-Line blocking [START_REF] Jurczyk | Phenomenon of higher order head-of-line blocking in multistage interconnection networks under nonuniform traffic patterns[END_REF], and congestion trees [START_REF] Pfister | Hot spot contention and combining in multistage interconnection networks[END_REF], phenomena that may trigger within few 10s of µs and significantly affect the network and workload performance.

To address these issues, a significant improvement is required in the way we design and implement network monitoring. The challenges of 10-100 Gbps load monitoring and visualization for high resolution datacenter network management are three-fold. Space-wise, how to collect, correlate and visualize several 1000s of queues, quasi-simultaneously (correlation may be due to either Hadoop/HPClike workload phases, or the activation of low-level flow control). Time-wise, we face a resolution challenge, i.e., the "µs wall" -one must detect, record, visualize, and/or react to network events that happen at µs (packet duration) timescales. Finally, the method must conceptually scale to million-node datacenters and Tbps link speeds. Hence the need for commodity hardware queue samplers, possibly reusing existing resources. All while helping the users and operators to better understand their load dynamics and nature.

As an exemplary Big Data workload, the Hadoop Partition/Aggregate pattern consists of multiple congestive episodes within few 100s of µs, known as TCP Incasts. The Aggregate phases actually determine the load, dynamic behavior, stability, and finally the user-perceived performance. However, the Incast phases at and above 10 Gbps are too volatile for the current sFlow [START_REF] Phaal | InMon corporation's sFlow: A method for monitoring traffic in switched and routed networks[END_REF], NetFlow [START_REF] Claise | Cisco systems NetFlow services export version 9[END_REF], and SNMP [START_REF] Case | A simple network management protocol (SNMP)[END_REF] monitoring techniques. Hence the need for a faster and lighter load sensing method able to 'catch' such ephemerally volatile correlated transients, scale to large networks, and also drill-in, i.e., zoom into a region of interest of a few 10s-100s queues.

We therefore propose a high-resolution (both) temporal and spatial monitoring technique based on IEEE 802 Quantized Congestion Notification (QCN) [START_REF]Virtual bridged local area networks -Amendment: Priority-based flow control. Technical report[END_REF], Ethernet's new congestion management protocol. Triggering, sampling, aggregating, communicating and visualizing network events are based on the concept of time-coherent snapshots of the queue occupancy levels. Coherency is achieved by using a network time difference estimation protocol implemented by the switches -a high accuracy alternative to current clock synchronization protocols such as GPS, NTP [START_REF] Mills | Network time protocol version 4: Protocol and algorithms specification[END_REF], and IEEE 1588 [START_REF]IEEE/ANSI: 1588 Standard for a precision clock synchronization protocol for networked measurement and control systems[END_REF]. We validate the above via simulations using accurate Layer-2 CEE-compliant 10 Gbps fabric models. As a first, our method detects and captures in real time the TCP Incast-like events in lossless fabrics, revealing their inception, evolution and global dynamic behavior at µs scale.

Selected Related Work

The area of network monitoring, telemetry and topography is exceedingly rich in literature. However, practically only a few schemes have been widely adopted by hardware and software vendors. Thus, despite much larger and faster DCNs, the current state of the art in hardware network monitoring has remained limited to sampling a few, possibly isolated, links with a granularity in the 0.01s to 1s range: e.g., sFlow, NetFlow and SNMP. These methods we consider insufficient for today's 10/100 Gbps DCNs and large distributed workloads.

More recent proposals, such as [START_REF] Kompella | Every microsecond counts: tracking fine-grain latencies with a lossy difference aggregator[END_REF], suggest new router extensions to perform path sampling using hardware synchronization via IEEE 1588. By instrumenting switches with a hash-based primitive, the authors measure latencies down to 10s of µs and 1 loss in a million. By contrast, our proposal (ab)uses the QCN standard to sample queues (instead of paths) with a theoretical sub-µs sampling. Node levels start at 0 from bottom to top (L0 to L3). Nodes within a level start at 0 from left to right. For simplicity reasons, only the switch levels (L1, L2, L3) are shown. L0 is populated with 2 (nodes) • 12 (L1-switches) = 24 (nodes). We highlight one path from switch 4 on L1 to switch 0 on L1. The red link represents the upstream queue of port 0 at switch 2 on L2.

Batraneanu et al. [START_REF] Batraneanu | Operational model of the ATLAS TDAQ network[END_REF] propose a tool-set developed to demonstrate aggregate achievable cross-sectional bandwidth for specific traffic profiles, as well as to analyze network hot spot behavior. Queues are being monitored at µs using sFlow and an FPGA implementation. Though the achieved timescale is similar, their solution is fundamentally different in various perspectives: we use the readily available QCN queue samplers, provide a coherent globally synchronized trigger-driven method, developed a record-and-replay tool validated in PFCenabled 10 Gbps CEE networks, and show that our heatmaps scale with low overhead.

Another related proposal [START_REF] Fisher | Using visualization to support network and application management in a data center[END_REF] identifies the challenges of datacenter and cloud monitoring and visualization: scale, rapidity, difficulties of detection, localization, and diagnose of performance problems. The proposed tool, i.e., Visual-I, relates directly to our targets. However, while we share goals with Visual-I, our method differs on the use of coherent heatmaps and the novel Layer-2 capabilities of the upcoming CEE-based datacenter networks.

Traffic Heatmap Method

We propose a matrix-based traffic visualization scheme as follows. Each packet sent from a source to a destination follows a certain route in the network, as depicted in Fig. 1, and travels through the corresponding set of queues in the forwarding switches, contributing to their respective occupancies. A network congestion/traffic heatmap is an instantaneous time-synchronous 2D snapshot image of the occupancy of all the switch queues in the network. Each heatmap cell represents a single queue providing a fine-grained spatial view of the network.

The occupancy is linearly color-coded on 16 bits using shades of red. The color ranges from white, empty, to dark red, full. Since the heatmaps are timesynchronous, they represent a snapshot of the network queues' status. This allows us to temporally concatenate such sequentially-acquired snapshots into an animated 'movie'. This movie not only provides insights into the network status evolution -congestion levels and locations -but also into the volatile causes and effects of network anomalies such as congestion trees.

The heatmaps are created by a controller which is the central element of the monitoring framework. The forwarding switches sample their queue occupancies -by reusing the commodity QCN hardware mechanism -and send them to the controller (see Subsec. 3.2). The controller then performs two mappings: one in time and one in space. In time, each sample is timestamped using the local clock of the switch it originated from. Since each switch has its own clock, the controller needs to map all the timestamps to a single common timeline (see Subsec. 3.4). The converted timestamps are sorted chronologically. The configuration of the heatmap at any given moment on the timeline is then given by the most recent occupancy value received for every queue previous to that moment. In space, the controller must know the network topology and location of each switch and queue. We assume the existence of a topology discovery protocol that detects and signals topology changes to the controller, for example, through the information gathered by the spanning tree protocol. Each queue has a unique identifier, thus each sample can be mapped to a precise cell using a topology-dependent bijective function. Since we focus on datacenter networks, we only present the mapping for fat trees (Subsec. 3.3). However, our method can be extended to other topologies by changing the mapping bijection.

The final raw result is a time-series of complete space-time mappings of all queue occupancy samples of all the switches. The heatmap thus created allows the detection of even ephemeral network anomalies. Once a critical area has been identified -e.g. due to particularly frequent congestion events -it is possible to increase the sampling frequency of those switches/queues to further enhance the detection accuracy. Also, once the culprits are identified, it is possible to take online or offline corrective actions and solve the hotspots or the detected events. An example is given in Sec. 5.1.

Datacenter Network Topology

Today, fat trees, i.e., multistage k-ary n-fly topologies, are typically the base for large datacenters [START_REF] Leiserson | Fat-trees: universal networks for hardware-efficient supercomputing[END_REF][START_REF] Petrini | Performance evaluation of the Quadrics interconnection network[END_REF]. These topologies can be described by extended generalized fat trees (XGFTs) [START_REF] Ohring | On generalized fat trees[END_REF]. An XGF T (h; m 1 , ...m h ; w 1 , ...w h ) has h + 1 node levels divided into leaf and inner nodes. The h i=1 m i leaf nodes reside on level 0 and serve as end nodes/servers. Inner nodes occupy levels 1 to h and serve as switches. Each inner node on level i has m i child nodes and each non-root node on level j has w j+1 parent nodes. Fig. 1 shows an exemplary XGFT(3;2,4,3;1,2,2).

Load Sensing: Queue Sampling

The queue sampling is performed in a distributed manner: each switch samples its own local queues. Sampling can start either periodically or remotely triggered upon a controller request. In the latter case, the controller sends a request to andc). Whereas, each cell in a column represents top-down the output queues ordered by: (1) the switch and (2) the port within that switch. E.g., C3 shows the downstream output queues of the L3 switches: 4 switches • 3 ports • 1 queue = 12 queues. Typical current switches have 1 to 4 hardware queues per port, but for increased clarity of results in paper format we will assume herein a single queue per port -the generalization to several queues is nonetheless trivial.

the switch with the desired sampling duration, rate and start time translated to the switch's own clock. The novelty of our approach consists in extending the use of the QCN load sensor to traffic monitoring. QCN is Ethernet's new endto-end congestion management which, together with its new flow control, i.e., Priority Flow Control (PFC), is being adapted by a growing number of network equipment to ease the network convergence commonly known as CEE.

To detect congestion, QCN uses load sensors monitoring all the queues. Its main objective is to keep the queue occupancy at a target equilibrium Q eq . At each frame arrival, QCN samples with probability π the queue occupancy. For each sampled frame, the load sensor computes a feedback value based on the current and past occupancy. Negative feedbacks are sent back to the frame's source, which reduces its injection rate, thus adjusting it to the available bandwidth.

Extending the use of the QCN load sensor to monitoring has the great benefit of readily available hardware which can sample all the queues at fine, i.e. subµs timescales, theoretically even per packet arrival -during limited zoom-in sampling intervals.

This improves upon other state of the art monitoring tools both in terms of temporal -10s of ns -and spatial granularity -each output queue. However two additional steps are needed to enhance the native behavior of QCN's load sampler: (1) to timestamp and locally store the QCN samples; and (2) to make the samples available to the heatmap controller.

To avoid flooding the network with monitoring traffic, we use compressive sampling and filtering based on the feedback values computed by QCN. The informative samples are mainly related to a congestive event. Hence, all negative feedback samples, signaling a congestion, are sent to the controller. During positive feedback sampling periods, only the first sample is sent back to the controller. During normal network operation, this filter removes most of the samples. To further reduce the monitoring overhead, it is possible to reduce the probability π (see Subsec. 5.3), and compress and aggregate multiple samples into MTU frames. Jumbo frames up to 10-20 KB could be used for high radix switches with thousands of queues (per port and priority). Once the frame is full or upon a timeout -to bound the reporting delay in case of sparse sample reporting -the resulting local snapshot frame is sent to the controller for heatmap assembly.

XGFT Mapping: Heatmap Bijection

Each heatmap cell represents a specific queue. Fig. 2 shows in steps the heatmap creation of the XGFT in Fig. 1. If level c has S switches, each switch P ports in the upstream/downstream direction, and each port Q queues, then within that level/column, row r = s • P • Q + p • Q + q represents queue q belonging to port p of switch s, where 0 s < S, 0 p < P and 0 q < Q. Conversely, given a row r within column c, the reverse mapping is: q = r modulo Q , p = r Q modulo P , s = r P •Q and the unfolded network level is c. This mapping is valid for homogeneous switches, i.e., same port and queue numbers, which is typical in practice. However, the mapping can be extended to accommodate non-homogeneous configurations. Moreover, although in this paper we only address the mapping of fat tree topologies (which are the most commonly used in datacenters), the mapping can be extended to multi-dimensional topologies by using topological isomorphisms as proposed in [START_REF] Dally | Principles and practices of interconnection networks[END_REF].

Coherent Sampling: Clock Difference Estimation Protocol

A coherent network heatmap requires: (1) a snapshot of the queues at the same time instant, i.e., 10s of ns timescale; and (2) a common time reference for the occupancy samples. Since each switch has its own internal clock, this problem is not trivial and goes beyond the scope of this paper. Nevertheless, we shortly introduce a clock estimation method based on the following linear drift model:

t i = δ i • t + ω i ( 1
)
where t is the controller reference time, t i the time at switch S i , and δ i and ω i the absolute clock drift and offset at switch S i . We also assume that all δ i and ω i are constant and that ω i > 0. This model entails that given two switches S i and S j , we have:

Probing Packet 1 Δ q 1 Δ t 1 Δ p 1 T i r 1 T j r 1 T j e 1 T i e 1 Δ q 2 Δ t 2 Δ p 2 T i r 2 T j r 2
t i = δ ij • t j + ω ij (2)
where δ ij = δ i /δ j and ω ij = ω i -δ ij • ω j are the relative drift and offset between S i and S j .

We rely on an adhoc neighbor-to-neighbor protocol between the switches to minimize estimation errors on the one-way latency due to queuing delays in intermediate hops. Fig. 3a) shows the method to calculate the relative drifts and offsets between two neighboring switches S i and S j . S i sends a probe of size P s to S j over a link with speed BW containing the local enqueuing time T i e and local queue size Q i s . We assume the one-way latency ∆ to be the sum of three delays: (i) queuing ∆ q = Qs BW , (ii) transmission ∆ t = Ps BW , and (iii) propagation ∆ p which depends only on the type and cable length, hence assumed to be constant. Using Eq. 1, the arrival time t j r at S j can be expressed as T j r = δ ji • T + ω ji and T i r = T i e + ∆. Thus, we have:

T j r = δ ji • (T i e + ∆ q + ∆ t + ∆ p ) + ω ji (3)
containing only three unknowns: δ ij , ω ij and ∆ p . For each probe, the receiving switch adds one equation to an equation system. Solving this system allows to obtain δ ji and ω ji , which are sent to the controller. From all the relative drifts and offsets, the controller then computes the absolute drifts and offsets as shown in Fig. 3b). It computes the absolute δ i and ω i for each switch by iteratively applying Eq. 1 on all consecutive switch pairs along the path. The general equation given a switch S p reachable via the path S p ⇒ S p-1 ⇒ ... ⇒ S 1 ⇒ C is shown in Eq. 4.

t p = p i=2 δ i,i-1 • t + p-1 i=1   p-1 j=i δ j+1,j   • ω + ω p,p-1 = δ p • t + ω p (4)
This approach allows for a non-intrusive clock compensation without alteration of the internal switch clocks. The temporal correlation among queue samples, as well as among the start/stop sampling commands, is achieved without explicit synchronization of the switch clocks.

Network and Simulation Environment

To show the benefits of such monitoring tool, we identify congestion trees in a lossless datacenter network. More in detail, we consider the same XGFT topology as presented in Sec. 3, comprising 24 end nodes and 22 switches interconnected by 10 Gbps CEE-compliant links. CEE aims at providing a reliable Layer-2 in contrast to the conventional Ethernet which drops frames as soon as a buffer reaches its maximum capacity. CEE achieves this by relying on two distinct protocols: PFC and QCN.

Similar to IEEE 802.3x PAUSE, PFC avoids packet losses during congestion by pausing the sender using explicit control frames. However PFC uses the concept of service classes: a paused priority does not affect the others. QCN counteracts the congestion entity by limiting the injection rates of the culprit sources. Even if mitigated by QCN, PFC can be affected by Head-of-Line blocking building up into congestion trees in the network: a blocked sender may fill up its buffer and recursively other devices will possibly get paused spreading the congestion backwards. Congestion trees can significantly degrade network performance [START_REF] Pfister | Hot spot contention and combining in multistage interconnection networks[END_REF], and hence it is useful to detect them to act quickly on their removal.

The occupancy samples are generated using high-accuracy Layer-2 simulations from an event-driven simulator based on OMNeT++ [START_REF] Minkenberg | Trace-driven co-simulation of high-performance computing systems using OMNeT++[END_REF]. The simulator is a two-level architecture network modeling platform. The higher level is the topological or system level where we gain a generic overview of the whole simulated infrastructure as an interconnection of modules. The lower level is that of the internal structure of each network module: e.g., hosts, and switches. We used our own network simulator due to its enhanced support for the CEE standards and detailed models of the Layer-2 switch and adapter micro-architectures. We extended our simulator to include: (1) the modified QCN load sensor additionally timestamping, storing and aggregating the queue samples as described in Subsec. 3.2 and (2) the clock difference estimation protocol described in Sec. 3.4. The drifts and offsets values are derived from empirical distributions obtained by instrumenting an Intel e1000 network driver and by analyzing the speed at which clocks of neighboring systems drift. A JAVA-based application collects the queue occupancy samples from the simulator and generates the heatmaps.

w/o Adaptive Routing Open Loop X X X X X
a1) T+0.07 ms a2) T+0.17 ms a3) T+0.65 ms a4) T+14.12 ms a5) T+17. 5 Results and Discussion

Congestion Tree Detection Heatmap Movie

As use case we propose a TCP Incast-like scenario, typical of Partition/Aggregate workloads. This bursty and correlated congestive pattern is also typical for barrier-based HPC applications, commonly using lossless fabrics. The surge in correlated packet arrivals overflows the aggregation buffer. In TCP over legacy Ethernet frames will be dropped, and subsequently recovered via TCP timeouts -thus leading to significantly increased delays. In modern CEE fabrics, PFC prevents such drops and improves performance [START_REF] Crisan | Short and Fat: TCP performance in CEE datacenter networks[END_REF]. However, transient congestion trees may still degrade the performance -under certain conditions: flow sizes, buffer settings, hotspot/incast degree. Such congestion trees and their evolution can be observed in Fig. [START_REF] Gusat | R3C2: Reactive route and rate control for CEE[END_REF] balances the load over the multiple paths available in fat trees. In contrast to Fig. 2c), each heatmap in Fig. 4 includes one additional column (C5) representing the downstream queues of the L1 switches. Row (a), i.e., open loop without adaptive routing, shows that the congestion tree fully builds up within 700 µs. Its root, i.e., designated hotspot, is located on the first downstream output queue, the flows convergence point. After 17 ms the congestion tree is drained, no longer affecting the flow delays. Closing the QCN loop (row b) mitigates the congestion as seen both from the lighter shades of red and the ∼ 2.4× shorter draining time (7 ms). As expected, when enabling adaptive routing many more queues share the load -since the traffic is spread across multiple paths (row c and d); now all the 'incast' flows meet only at the destination, relocating the previous tree root. Again closing the QCN loop (row d) reduces the congestion duration, draining faster by a factor ∼ 3×. While these results meet the initial expectations, now they are also revealed to external observers without the benefit of apriori knowledge. The events of potential interest are automatically detected based on the programmable QCN threshold setpoint, recorded, and visualized for offline analysis.

The fine-grained timescale achievable with our coherent 'snapshooting' method naturally lends itself to movie-like playbacks, with variable temporal resolutions in frames/s. This not only enhances the user experience, but also enables temporal zooming (fast/slow motion, fast forward). Thus we can monitor longer time intervals without loosing track of the -potentially ephemeral -events of interest.

Time Estimation Accuracy

To test the accuracy of our clock estimation protocol, we use the same network as above, with uniform all-to-all background (i.i.d.) traffic at 60% load. Results show a mean error among all 10 Gbps switches of 380 ns with a standard deviation of 465 ns. The achieved accuracy is comparable to the hardware-aided implementation of IEEE 1588 [START_REF] Ferrari | Synchronization of the probes of a distributed instrument for real-time Ethernet networks[END_REF] and 2x-3x better than the software-only IEEE 1588 version [START_REF] Correll | Design considerations for software only implementations of the IEEE 1588 precision time protocol[END_REF].

Monitoring Overhead

The overhead of our QCN-based sampling technique depends on several parameters: average network diameter, injected traffic, average congestion level/severity and its duration. Here we show only the influence of the QCN parameters. In particular we consider the queue sampling probability π ∈ [1%, 2%, 4%, 10%] and the queue equilibrium setpoint Q eq ∈ [2KB, 4KB, 8KB, 16KB]. We assume a sample size of 8B including a queue identifier (16 bit), queue occupancy (16 bit), queue occupancy variation (16 bit), timestamp offset (16 bit); plus a standard Ethernet-IP-TCP header (54B) extended with a switch identifier 6B and a base timestamp 8B (Timestamp = Base + Offset, for space saving). We compute the sampling overhead as the ratio between the sampling traffic reported to the controller and the total traffic sent by all hosts during the sampling period. The results show that π directly affects the overhead, but even for aggressive sampling probabilities, i.e. 10% (e.g., one in 10 packet arrivals in a 128-port switch fully N-to-1 congested can lead to sub-µs periods at 10 Gbps), the obtained overhead is less than 0.2%. For π of less than 5%, the overhead is below 0.1%. This overhead is approximately constant with respect to Q eq .

Switch Code Complexity

The additional switch code complexity is low. On the data plane, the switch only needs to locally save and timestamp the occupancy samples already collected by the QCN sampler. On the control plane, the switch needs to perform two sets of operations: (1) aggregate, compress, and send the QCN samples to a centralized controller; (2) collect probes for the clock difference estimation protocol through a heartbeat protocol. The actual derivation of the relative offsets and drifts can be performed either locally or, if too complex for the local switch control processor, offloaded to the controller.

Conclusions

We presented a high resolution monitoring method with: (1) µs queue sampling period, (2) based on the newly available IEEE 802 QCN hardware load sensing;

(3) fabric-level coherence, i.e., global synchronous trigger-driven method; (4) multi-queue heatmap 'snapshooting' that scales up with low traffic overheads; [START_REF] Phaal | InMon corporation's sFlow: A method for monitoring traffic in switched and routed networks[END_REF] an intuitive matrix representation of the datacenter system based on a bijective mapping of the common XGFT networks; (6) a record and replay visualization tool, validated in lossless link-level flow-controlled 10 Gbps accurate Layer-2 simulations.

As proof of concept, we have designed and implemented a method that displays the time-coherent heatmap snapshots and movies showing the simultaneous occupancy of -some or all -the queues in a simulated network. For the first time now, the detection and visualization -in quasi-real time -of congestion trees and Incast events, correlated across the entire fabric, have been shown to operate in a lossless 10 Gbps commodity Ethernet. Thus, this method enables finer resolution insights into workload-specific traffic patterns and detects persistent and transient anomalies. This fast and efficient monitoring approach can benefit researchers, architects, network administrators, Big Data application developers, etc., to better understand the interaction between complex workloads and the underlying networks in large multitenant datacenters.

Fig. 1 .

 1 Fig. 1. Folded topology representation of XGFT(3;2,4,3;1,2,2). Links are bidirectional.Node levels start at 0 from bottom to top (L0 to L3). Nodes within a level start at 0 from left to right. For simplicity reasons, only the switch levels (L1, L2, L3) are shown. L0 is populated with 2 (nodes) • 12 (L1-switches) = 24 (nodes). We highlight one path from switch 4 on L1 to switch 0 on L1. The red link represents the upstream queue of port 0 at switch 2 on L2.

Fig. 2 .

 2 Fig. 2. Spatial mapping example. Intermediate Fig. a) and b) show how the XGFT from Fig. 1 is mapped onto the heatmap in c). a) unfolds and rotates the topology by 90 degrees. Links are unidirectional: traffic flows from left to right. Each level corresponds to the up-/down-stream direction. All figures highlight the same exemplary path from switch 4 on L1 to switch 0 on L1. Similarly, red highlights the send queue(s) of port 0 at switch 2 of level 2 (L2). Each link level in a) corresponds to a column in b)and c). Whereas, each cell in a column represents top-down the output queues ordered by: (1) the switch and (2) the port within that switch. E.g., C3 shows the downstream output queues of the L3 switches: 4 switches • 3 ports • 1 queue = 12 queues. Typical current switches have 1 to 4 hardware queues per port, but for increased clarity of results in paper format we will assume herein a single queue per port -the generalization to several queues is nonetheless trivial.

Fig. 3 .

 3 Fig. 3. a) Method to calculate the relative drifts and offsets of two neighboring switches Si and Sj. b) Method to calculate the absolute drift and offset of a switch Sp to a reference controller system C.

Fig. 4 .

 4 Fig.[START_REF] Pfister | Hot spot contention and combining in multistage interconnection networks[END_REF]. XGFT(3;2,4,3;1,2,2) under many-to-one traffic (nodes 0-15 send to node 23 at full link speed, i.e. 10 Gbps, for 10 ms starting at T). Each row corresponds to a different network configuration and shows 5 time steps of the congestion evolution. The first 3 steps show the congestion tree onset, while the last 2 steps show the network recovery. The congestion tree root is marked by X.

  4, which shows selected frames of the heatmap movie under different network configurations: (a) open/closed QCN congestion control loop; (b) without or with adaptive routing. In open loop, the QCN rate limiters are disabled, i.e., congestion notifications are ignored; while in closed loop, the QCN rate limiters react by adjusting the injection rate. The adaptive routing scheme


Walter De Donato
email: walter.dedonato@unina.it

Alessio Botta
email: a.botta@unina.it

Antonio Pescapé
email: pescape@unina.it

HoBBIT: a Platform for Monitoring Broadband Performance from the User Network

In the last years the problem of measuring and monitoring broadband performance has attracted a lot of attention. In this paper we present our recent work in this area, providing the following main contributions: firstly, we analyze the literature, illustrating the different existing approaches and the main requirements of platforms implementing these approaches; secondly, we describe the lessons learned designing and implementing a platform called HoBBIT; thirdly, we analyze and share the results obtained from the current deployment in Italy. The lessons learned and the design guidelines of the platform can be of help in light of the recent research and standardization efforts in this area. The results and the dataset we shared with the community provide information on the current status of broadband in Italy and allow other researchers to access fresh measurements from a real and large scale deployment. 6 BMWG, https://datatracker.ietf.org/wg/bmwg/charter/ 7 HomeNet, https:

Introduction

Recently, a great interest has been focused on the performance evaluation of broadband access networks, in order to shed light on (i) what is the real experience perceived by users on a large scale [1] and (ii) to provide empirical data for policymakers [START_REF] Flamm | Measuring broadband: Improving communications policymaking through better data collection[END_REF]. Most projects pursuing this objective perform active measurements to evaluate common QoS metrics. They operate such measurements by adopting different techniques and from different viewpoints, each of them affecting obtained results in a different way: most projects require users to cooperate by running a software on their computer or by deploying a special device in their home network, acting as vantage points (VPs) to perform the measurements 1 .

In this paper we describe our recent research work, basically providing a twofold contribution. On the one hand, (i) we briefly analyze the literature by providing a taxonomy of approaches for evaluating broadband performance; (ii) we identify the most effective ones by evaluating their pros and cons; (iii) we outline the main characteristics and requirements of a platform suitable for applying such approaches. On the other hand, (iv) we describe the solutions we adopted in designing and developing a measurement platform called HoBBIT2 To highlight and summarize the significance of the contribution proposed in this work, we underline that, to the best of our knowledge, it extends the results in literature (a) by providing design guidelines for implementing platforms for large scale measurements of broadband accesses, and (b) by collecting, analyzing, and sharing a rich set of data from real users in a specific geographical region for 3 years. The importance of the contribution should also be seen in the light of the work that various bodies are doing for standardizing the different aspects related to these platforms (architectures4 , metrics5 , methodologies 6 , use cases 7 , etc.) and it is witnessed by recent events like the 1st NMRG workshop on large scale network measurements 8 .

Platforms for broadband monitoring and measurement

By analyzing the literature and the main projects addressing the evaluation of access network performance, we defined a simple but effective taxonomy. As illustrated in Fig. 1, it classifies the approaches depending on where the VPs initiating the measurements are located: WAN-based approaches exploit VPs deployed in Internet at different locations, such as the network of the user's ISP [START_REF] Cho | The impact and implications of the growth in residential user-to-user traffic[END_REF][START_REF] Siekkinen | Performance limitations of adsl users: A case study[END_REF][START_REF] Maier | On dominant characteristics of residential broadband internet traffic[END_REF], transit networks [START_REF] Dischinger | Characterizing residential broadband networks[END_REF][START_REF] Croce | Capacity estimation of adsl links[END_REF], or stub networks hosting real services [START_REF]Youtube[END_REF]; UN-based approaches deploy VPs inside the user's network, such as the home gateway [1,[START_REF] Sundaresan | Measuring home broadband performance[END_REF] or a software running on generic hosts (laptops, tablets, etc.) in the form of a standalone application [START_REF] Grenouille | Grenouille[END_REF][START_REF] Han | Mark-and-sweep: Getting the inside scoop on neighborhood networks[END_REF][START_REF] Bernardi | Bsense: a system for enabling automated broadband census: short paper[END_REF][START_REF]Neubot[END_REF][START_REF]Ne.me.sys[END_REF][START_REF] Joumblatt | Characterizing end-host application performance across multiple networking environments[END_REF] or a browser executing a web application [START_REF]Speedtest.net[END_REF][START_REF] Kreibich | Netalyzr: Illuminating the edge network[END_REF][START_REF]Glasnost: Bringing Transparency to the Internet[END_REF].

The study of the literature allowed to understand that all the approaches have both advantages and drawbacks, but those working from user network result to be more effective 9 : they can better take into account the context in which measurements are performed. Among them, we identify gateway-and applicationbased as the most promising approaches: they allow to perform repeated exper-iments on the same access link over a long time period, thus obtaining more statistically significant results. A trade-off exists between these two approaches: gateway-based ones are more accurate, but have some drawbacks (e.g., shipping devices is costly, gateways offer limited resources); client-based ones are less accurate (e.g., they cannot directly consider all the cross traffic potentially affecting measurement results), but enable to easily obtain capillary large-scale deployments. These aspects make the latter more effective for obtaining a fine-grained geographical view of broadband performance.

While in [START_REF] Sundaresan | Measuring home broadband performance[END_REF] we presented a gateway-based platform, in this work we describe what we learned while designing and implementing an application-based platform for measuring broadband access networks. We believe that this contribution can be of great help for the research and standardization efforts ongoing in this field and can stimulate fresh and interesting discussions at the workshop. Proposed Reference Architecture. As illustrated in Fig. 2, a UN-based platform should include three essential components: (i) measurement clients (henceforth clients) running inside the user's network, which periodically ask for instructions about experiments to execute, and report back the obtained results; (ii) measurement servers (MRSs) acting as counterparts for active measurements, possibly deployed on networks with high-capacity links to the main backbones; (iii) a management server10 (MGS) responsible for: configuring and planning experiments to be performed by clients; collecting, organizing, and storing measurement results; monitoring the operating state of clients and MRSs; pushing software updates to clients. Platform Requirements. Ideally, VPs should cover all the geographic locations of interest, ISPs, and service plans (henceforth plans). MRSs should be properly distributed to have at least one of them at the shortest network distance, while their number should be proportional to the number of clients in a given location.

We further identify the following requirements:

scalability: it should be able to cope with a large number of clients; accuracy: it should provide accurate measurements while avoiding significant interferences among them; portability: clients should be as portable as possible, in order to potentially involve any user; flexibility: performed measurements should be dynamically tunable to behave according to the context; autonomicity: it should automatically obtain any required information (e.g., plan details, geographical area) without relying on user cooperation (which may lead to unverifiable mistakes); manageability: it should provide an easy way to manage experiments (e.g., definition, configuration, deployment); traceability: every measurement taken should include a timestamp and refer to a well-identified access network; non-intrusiveness: it should mitigate the impact of measurements on user traffic; security: it should not represent a potential vulnerability for the user network; privacy: collected data should always be treated in order to preserve user privacy; -(geolocalized) visibility: collected data should be properly presented to the user as an incentive to participate; independence: it should operate independently on ISPs funding or control to guarantee unbiased results; inexpensiveness: the deployment cost should be limited in order to allow the number of clients to scale quickly.

The HoBBIT Platform

According to the guidelines defined in Sec. 2, we designed and implemented HoBBIT, an application-based platform currently operated on the Italian territory 11 . Volunteers can install a portable client application on their computer(s) for monitoring the performance of their access network(s). Since HoBBIT clients can move among different access networks (henceforth connections), we designed the platform by using a connection-centric approach. Each connection is associated to its geographical position (up to the zip code granularity) and to its network details (i.e., ISP, plan). Every user may own more installations of the client, each possibly contributing to the performance evaluation of several connections. As for measurements, they are referred to as experiments, which are organized in campaigns having a specific goal. Each experiment is periodically executed following a detailed schedule, which is defined by the specific campaign. Each experiment can produce more than one measurement output (i.e., a set of samples collected at a specific sampling rate) or a failure log. Finally, a set of MRSs is available for supporting the experiments with part of their resources (slices).

At runtime -every 5 minutes -each client asks the MGS for a list of experiments. If the list is not empty, it sequentially executes all the experiments and finally reports back all the results. All the messages exchanged between the clients and the MGS are XML-encoded and transferred over the HTTPS protocol. In the following, by adopting a problem/solution scheme, we briefly describe the main lessons we learned while designing and implementing HoBBIT, with the aim to satisfy most of the requirements outlined in Sec.2. We refer the reader to [START_REF] Donato | Large scale benchmarking of broadband access networks: Issues, methodologies, and solutions[END_REF] for a detailed discussion. Tracking client-connection associations. HoBBIT clients can move among different connections or operate together behind the same connection. This is primarily true for mobile devices (e.g., laptops, tablets), which are today really common. It is then necessary to properly track their association with connections, supporting also plan upgrades and ISP changes. Solution. The client computes a hash value starting from the MAC address of its current default gateway, which is used by the MGS to uniquely identify the connection. The hash is computed adding to the string representing the MAC address a progressive number, which is incremented every time a plan upgrade or an ISP change is detected or notified by the user. Hence, the history of a connection can be reconstructed. Since a gateway may have more than one network interface (e.g., wired and wireless), different hash values may be associated to the same connection. To cope also with such case, we implement an aliasing condition: we consider two connections in alias only if different clients report the same public IP address close enough in time 12 . This solution enables different clients to be coordinated by the MGS for evaluating the performance of a connection. Hence, it helps to satisfy both accuracy and traceability requirements. Detecting service plan and location. Every time a new connection is identified, it is necessary to detect its main properties: ISP, plan details, and geographic location. We found that asking such information directly to users is not sufficient: they tend to leave the information empty or, worst, to provide wrong answers. This is particularly true for plan details (e.g., advertised downstream and upstream rates, and access technology), since most users do not have enough technical knowledge to provide correct information. Solution. In order to mitigate as much as possible the voluntary or accidental introduction of errors caused by users, we adopted a semi-automatic approach that tries to obtain most of the information automatically, while requesting the remaining information to the user in a guided way. We automatically detect: i) the ISP, using the public IP address of the client; ii) the plan, matching the results of an ad-hoc measurement campaign against a database of existing ISPs and plans; iii) the location up to the zip code granularity (only if GPS is available). Then, we present the inferred information to the user on a web page, where he can confirm, correct, or refine it. This procedure is performed every time an unknown connection is detected and is aimed at providing autonomicity. Providing a flexible measurement framework. In order to cope with heterogeneous and evolving network scenarios, the platform should be able to support any measurement tool and to dynamically adjust its parameters depending on the context. Moreover, measurements should be scheduled according to the needs of the specific campaign, which may require to repeatedly execute an experiment at a specific time on a particular set of connections. Solution. We designed the HoBBIT framework to give high flexibility in the definition, configuration and execution of the experiments and in their assignment to clients. On the one hand, each experiment is defined by the (P i , P o , S) tuple, where the P i and P o sets represent input and output parameters, and S is a wrapper script acting as an adaption layer between the client and the underlying measurement tool. On the other hand, each campaign can be assigned to a subset of connections by means of configurable parameters (e.g., all the DSL connections in a specific area). Providing accurate measurements. Obtaining accurate results is fundamental for any measurement platform and, when focusing on the access network, it is important to isolate most of the confounding factors coming from both the user network and the Internet. Moreover, accurate tools should be adopted and their execution should be controlled in order to avoid excessive interferences. Indeed, since many clients conduct measurements toward a few servers, it is important to properly coordinate the execution of the experiments to avoid interferences on the server side. Solution. In order to isolate most of the confounding factors, we adopt the following strategy: (i) we try to deploy dedicated MRSs in networks having highcapacity links to the main backbones (in order to push the bottleneck toward the access link) and in different locations (in order to be able to select the MRS closest to the client both in terms of end-to-end latency and hops); (ii) we avoid conducting measurements if user-generated traffic and CPU usage exceed thresholds defined for the connection (depending on upstream and downstream rates, access network capacity, etc.). (iii) since we cannot take into account all the interferences, we try to repeat as many measurements as possible in the same conditions (e.g., same daytime and day of week), in order to count on big numbers for isolating outliers; (iv) for each measurement, we take note of the involvement of a wireless link (e.g., Wi-Fi) between the host and the access link.

As for the accuracy of the tools, we purposely designed the measurement framework to support any underlying pre-existing tool. Hence, standard and well-tested tools are and can be adopted depending on the context.

To cope with server-side interferences, we designed a centralized scheduling algorithm executed by the MGS while assigning experiment targets to clients 13 . We assign MRSs a network capacity made of reservable fixed-size slices. For each slice we keep a timestamp representing the time when a slice will be free again. When a client asks for an experiment target MRS, the MGS reserves -according to the experiment duration and required bandwidth -the set of slices having the lower timestamp values on a single MRS. If not enough slices are immediately available, the reply includes a delay time, i.e. the time to wait before starting the experiment.

Making the platform scalable. A platform conducting periodic measurements and potentially involving a huge number of clients has to properly address scalability from different viewpoints: i) network load introduced by both control and measurement traffic; ii) available computational and networking resources on MRSs; iii) storage and processing of the amount of data collected on the MGS(s). Solution. While the scheduling algorithm described above allows to address the first two viewpoints by properly dimensioning the number of MRSs and tuning the periodicity of the experiments, further work is necessary to address the third one. Indeed, the amount of data collected over time tends to increase very quickly, and processing it in realtime becomes unfeasible without special arrangements. Since the objective is to maintain the finest granularity on the measurements performed (i.e. the samples produced by every single experiment) while offering different levels of aggregation on different axes (i.e. temporal and geographical), we structured the HoBBIT database in order to store and aggregate data in an efficient manner (e.g., materializing views, partitioning tables). To cope with the increasing amount of samples produced by every single experiment, we are also studying and comparing different reduction approaches. Making the platform easily manageable. To properly control and configure a complex platform made of several distributed nodes, it is fundamental to have a (logically) single management point, which should allow to easily reconfigure or update any part of the platform, in order to support remote troubleshooting and debugging without user intervention. Solution. HoBBIT has been purposely designed to control any aspect of the platform from the MGS(s). It provides a web-based management interface which gives full control on the configuration of campaigns, experiments and related aspects, while giving visibility on monitored connections, installations running on them, and collected measurement results. Moreover, we can set any client in debug mode (to send detailed debug logs back to the MGS) and automatically update them in automatic or on-demand (i.e., only for specific clients) modes 14 . This solution provides manageability. Involving as many users as possible. The success of platforms like HoBBIT is determined by the ability to involve as many users as possible, possibly using different ISPs and plans, and with a large geographical coverage. Main problems here are the diversity of user equipments (PCs, OS, etc.) and the necessity to find effective incentives [START_REF] Lee | Dynamic pricing incentive for participatory sensing[END_REF][START_REF] Choffnes | Crowdsourcing service-level network event monitoring[END_REF]. Solution. In order to make the client portable to the most widespread operating systems, we made the following choices: i) we developed the client using the Qt libraries, which provide high portability and flexibility; ii) we selected the bash and gawk interpreters for implementing wrapper scripts, because they are natively available on Linux and Mac OSX, while they have Cygwin-based versions for Windows 15 ; iii) we select measurement tools according to their portability. As for providing incentives for the users, we give them visibility and guided interpretation on the performance measured, enabling the comparison with nearby connections.

Preserving user experience. Frequent measurements are important to compensate the effect of confounding factors and to observe time-dependent trends.

On the other side, it is fundamental to avoid a noticeable impact on user experience, to keep them involved in the long term.

Solution. The HoBBIT client has been purposely designed to provide nonintrusiveness. On the one hand, the user interface normally consists in a system tray icon displaying the current status (e.g., measure in progress, idle, etc.), while limited user interactions are required only when a new connection is detected. Moreover, interacting with the icon, the user can always know when the next set of experiments will be performed and decide to temporarily disable their execution for a predefined period (e.g., from half hour up to four hours). On the other hand, experiments are performed only if computational and networking resources are not over two different thresholds, defined according to the host capabilities and to the plan respectively. If after a number of retries such conditions are not satisfied, the experiment is aborted.

Experimental analysis

Since December 2010 HoBBIT is running a measurement campaign named Basic Performance Evaluation (BPE). Its objective is to measure a basic set of performance metrics on a regular basis and for a long period. We present preliminary results from about 190K experiments performed on 310 selected connections monitored by the current deployment, which counts about 400 clients.

BPE campaign details

Tab. 1 reports details about BPE. Round-trip latency, jitter and packet loss are evaluated generating 10 isochronous UDP packets per second for 30 seconds, while upstream and downstream throughput are measured imposing for 15 seconds a constant bitrate -5% higher than the advertised rate (AR) -with both UDP and TCP protocols. Such measurements are performed every half hour toward three MRSs located at the University of Napoli by embedding the D-ITG tool [START_REF] Botta | A tool for the generation of realistic network workload for emerging networking scenarios[END_REF].

Preliminary results from the real deployment

Analyzing the data collected, we tried to answer to the following important questions about broadband in Italy.

To what extent ISPs offer the advertised performance? Most ISPs advertise only the downstream and upstream capacity of their connections. We compared them with the average throughput results obtained for each monitored connection. Fig. 3 reports the comparison of measured and advertised rates in downstream (left) and upstream (right), where x and y axes respectively report advertised and measured speeds, each point identifies a monitored connection, and the histograms highlight their percentage with respect to both speeds. At first glance, it is evident how no connection meets or outperforms the advertised maximum rates. The discrepancy between actual and advertised performance is highly variable, ranging from 10% to 90% for downstream and from 5% to 100% for upstream. It is also noticeable that users owning high-end plans observe a higher performance penalty than those owning low-end plans. Clustering the observed ADSL performance by plans, some other characteristics are more evident. Fig. 4 -divided in four groups according to the advertised upstream capacity for ease of reading -reports the average rates measured in both directions, where each point (red 'o' marker) represents the measured rates of a connection and a line connects each of them to the corresponding advertised rates (black '*' marker). In this kind of plot nearly horizontal (vertical) lines highlight a very asymmetric discrepancy with respect to the downstream (upstream) direction. On the one hand, Fig. 4(a) highlights how 20 Mbps plans are in general very far from the promised maximum rates, which is a consequence of a technological constraint: the distance between the modem and the DSLAM is often too long to avoid excessive signal attenuation. Furthermore, 25% of monitored high-end plans (more expensive) achieve rates advertised by low-end plans

Conclusion

Shedding light on broadband performance on a large scale is still a challenging task. In this work, starting from the definition of a taxonomy for the existing approaches, we presented the lessons we learned while designing and implementing HoBBIT, which tries to satisfy most of the requirements we identified as necessary to measure and monitor broadband performance from the user network, using an application-based approach. We discussed the main issues encountered and the practical solutions we adopted for them. Thanks to the deployment of HoBBIT on the Italian territory, we also collected and shared fresh results on the performance of broadband in Italy. By analyzing these measurements, we tried to answer three basic questions about the performance perceived by users. We detected that (i) in average most plans promise maximum rates which are far from actual average rates, (ii) 25% of HoBBIT users may obtain the same performance -and save money -by choosing a cheaper plan, and (iii) unadvertised QoS metrics can make the difference among similar plans. Finally, we underline that to obtain more reliable insights about performance on a geographic basis, a more capillary deployment is necessary. Accordingly, in our ongoing work we are investigating incentive mechanisms to reach a wider user participation. We further plan to perform an experimental comparison among HoBBIT and similar platforms, and to design and deploy in it new measurement techniques for detecting network neutrality violations and Internet censorship [START_REF] Aceto | User-side approach for censorship detection: home-router and client-based platforms[END_REF].

Fig. 1 .

 1 Fig. 1. A taxonomy for broadband performance evaluation approaches based on the location of the VPs initiating the measurements. (Host-Based Broadband Internet Telemetry); (v) we analyze the preliminary results obtained from the current deployment; (vi) we release open data sets to the community 3 .To highlight and summarize the significance of the contribution proposed in this work, we underline that, to the best of our knowledge, it extends the results in literature (a) by providing design guidelines for implementing platforms for large scale measurements of broadband accesses, and (b) by collecting, analyzing, and sharing a rich set of data from real users in a specific geographical region for 3 years. The importance of the contribution should also be seen in the light of the work that various bodies are doing for standardizing the different aspects related to these platforms (architectures 4 , metrics 5 , methodologies 6 , use cases 7 , etc.) and it is witnessed by recent events like the 1st NMRG workshop on large scale network measurements 8 .

Fig. 2 .

 2 Fig. 2. Platform architecture overview.

Fig. 3 .

 3 Fig. 3. Average discrepancy between advertised and actual performance.

  Average packet loss distribution.

Fig. 5 .

 5 Fig. 5. Average unadvertised QoS metrics from 4 major Italian ISPs: Telecom Italia (TI), Wind (WI), Fastweb (FW), Tele2 (T2).

Fig. 6 .

 6 Fig. 6. Average performance ranges measured: Italian regions and municipalities around Napoli.

tween 4 and 6

 6 Mbps in most regions, a few of them observe values lower than 2 Mbps and the same happens at municipality level. The average upstream throughput (Fig.6(b)) is higher than 512 Kbps only in three regions and a few municipalities, while most of other areas provide values between 256 and 512 Kbps. Finally, only a few areas report average latencies (Fig.6(c)) above 40 ms, both at region and municipality level.

Table 1 .

 1 Experiments part of the BPE campaign.

			Adopted Required Measure Sampling
	ID Measured metrics	transport bandwidth duration	rate
			protocol	(kbps)	(sec)	(msec)
		Round-trip
	#1	Latency, Jitter	UDP	0	30
		& Packet loss
	#2 #4 #3 #5	Upstream throughput Downstream throughput	UDP TCP UDP TCP	f (ARup) f (AR dw )	15	1000

In this work we explicitly target fixed broadband access networks and related issues. Mobile broadband is out of the scope of this paper.

http://hobbit.comics.unina.it

http://traffic.comics.unina.it/Traces

LMAP, https://datatracker.ietf.org/wg/lmap/charter/

IPPM, https://datatracker.ietf.org/wg/ippm/charter/

A single point of failure can be avoided by deploying multiple servers.

Since some ISPs assign to users private IP addresses, we apply the aliasing condition only if we detect one private hop between the client and the Internet.

Because of space constraints, we refer the reader to[START_REF] Donato | Large scale benchmarking of broadband access networks: Issues, methodologies, and solutions[END_REF] for a detailed description of the algorithm

The HoBBIT client is not installed system wide and does not require administration privileges to perform updates.

Both the Cygwin library and the interpreters are embedded into the client.

Acknowledgment

This work has been partially funded by MIUR in the PLATINO (PON01 01007) and SMART HEALTH (PON04a2 C) projects.

//datatracker.ietf.org/wg/homenet/charter/ 8 http://tinyurl.com/pqfkd7e 9 We refer the reader to [19] for the details about such analysis.

(cheaper), causing a waste of money for the user. On the other hand, Fig. 4(c) and 4(d) show how low advertised upstream rates are more likely to be achieved. From the above results, the answer is that actual performance unlikely reaches the maximum advertised rates and the difference between actual and measured rates is not negligible in many cases. What unadvertised QoS metrics do different ISPs provide? By looking at unadvertised QoS parameters, different ISPs may offer significantly diverse performance. Fig. 5(b), 5(c), and 5(d) report the empirical cumulative distributions of such metrics for four major Italian ISPs, for which HoBBIT monitored the amount of connections reported in Fig. 5(a). According to Fig. 5(b) all the ISPs provide latencies below 100 ms in 80% of cases, but only the Wind operator provides under 40 ms latencies in more than 50% of cases. On the other hand, according to Fig. 5(c) and Fig. 5(d), Wind provides high jitter values in more than 40% of cases and some packet losses in 25% of cases. A possible explanation of such results is that Wind configures ADSL plans in fast mode, which provides low latencies at the cost of higher loss probability.

To what extent performance depends on geographic location? We analyzed the maps reported on the HoBBIT website. Fig. 6 shows average performance aggregated per region (nation wide) and per municipality (in the area around Napoli). While in average the downstream throughput (Fig. 6(a)) is be-


Zied Ben Houidi
email: zied.ben\_houidi@alcatel-lucent.comfinamore

Giuseppe Scavo
email: giuseppe.scavo1@alcatel-lucent.comfinamore

Samir Ghamri-Doudane
email: samir.ghamri-doudane@alcatel-lucent.comfinamore

Alessandro Finamore

Stefano Traverso
email: traverso@tlc.polito.it

Marco Mellia
email: mellia@tlc.polito.it

Gold mining in a River of Internet Content Traffic ⋆

With the advent of Over-The-Top content providers (OTTs), Internet Service Providers (ISPs) saw their portfolio of services shrink to the low margin role of data transporters. In order to counter this effect, some ISPs started to follow big OTTs like Facebook and Google in trying to turn their data into a valuable asset. In this paper, we explore the questions of what meaningful information can be extracted from network data, and what interesting insights it can provide. To this end, we tackle the first challenge of detecting "user-URLs", i.e., those links that were clicked by users as opposed to those objects automatically downloaded by browsers and applications. We devise algorithms to pinpoint such URLs, and validate them on manually collected ground truth traces. We then apply them on a three-day long traffic trace spanning more than 19,000 residential users that generated around 190 million HTTP transactions. We find that only 1.6% of these observed URLs were actually clicked by users. As a first application for our methods, we answer the question of which platforms participate most in promoting the Internet content. Surprisingly, we find that, despite its notoriety, only 11% of the user URL visits are coming from Google Search.

Introduction

The Internet ecosystem has been historically composed only by two actors: carriers (e.g., ISPs) offering telephony services and Internet connectivity, and endusers. Recently, a new class of actors progressively gained a prime role: Over-The-Top content and application providers (OTTs [START_REF] York | What is an over-the-top (ott) application or service?[END_REF]), i.e., third parties that are involved in the cross-domain distribution of content. Nowadays, this class of providers offers to end-users the same services that used to be offered by ISPs, plus a plethora of novel services. This is the case for instance of voice, texting and video services (e.g., Skype and Viber, WhatsApp and iMessage, or Netflix and YouTube).

In this context, ISPs are more and more assuming the low profitable role of "bits carriers". To counter this effect, ISPs have been trying to find new added-value services that go beyond the traditional network connectivity business, investing in platforms to offer content [START_REF]Telecom italia vod[END_REF] or cloud services [START_REF]At&t cloud service[END_REF][START_REF]Telefonica cloud service[END_REF].

However, one of the possible assets of an operator is the information about its customer-base. Some major ISPs such as AT&T and Verizon have recently investigated how to translate this asset into profit [START_REF]At&t joins verizon, facebook in selling customer data[END_REF][START_REF] Kleinman | Verizon selling customers' cell phone data: Report[END_REF], for instance by re-selling customers' data to advertisement agencies as already done by other big OTTs such as Facebook and Google.

Extending this concept further, ISPs are thinking of leveraging the information their networks carry. By looking at the traffic that naturally flows, they have access to a humongous river from which possibly gold mining valuable information. This information could be used for at least two use cases. First, for web analytics/marketing purposes. Second, it can serve as an input for novel recommendation systems based on network traffic observation. And, differently from most 3 OTTs, ISPs have a unique vantage point that offers a wide-angle perspective, where multiple services and customers' habits are possibly exposed. They can try to exploit this unique vantage point respecting end-users privacy and regulations, for example, avoiding targeting single users, but considering aggregate information only.

Putting ourselves in the same position of an ISP observing the traffic in its network, we first address the technical issues related to i) how to identify the "contents" that users access from the enormous set of "objects" the network carries, and ii) how to pinpoint "interesting content" that is worth recommending out of the previous set. Second, we contrast the information that ISPs could get against the one OTTs have. This is instrumental to quantify if the ISPs are really in a more rewarding vantage point compared to the OTT position.

In this work we focus on HTTP traffic, the standard protocol used to transport web objects 4 . We consider all URL requests that are passively observed on a link of an ISP network. Immediately, we realize that the very large fraction of these URLs consists of requests automatically generated by browsers to fetch objects that are part of a web page (images, CSS files, JavaScript code, etc.), or by applications to poll automatic services (e.g., software update, chat keepalive, etc.). We refer to these as browser-URLs. We are instead interested in the small subset of URLs that were intentionally visited by users, which we call user-URLs. Lot of ingenuity has to be used to extract this second subset, and, to the best of our knowledge, little work has been conducted in the literature, with few methodologies that are either obsolete for nowadays scenarios [START_REF] Choi | A behavioral model of web traffic[END_REF][START_REF] Barford | Generating representative web workloads for network and server performance evaluation[END_REF], or too complex for our needs [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF]. Our goal is to reach a good accuracy at identifying user-URLs using only HTTP requests, without the need to correlate them with corresponding responses.

Next, we address the problem of identifying interesting-URLs, i.e., those user-URLs that are possibly worth recommending in an eventual content promoting scenario. For instance, a popular news is worth being suggested, while the homepage of a home banking portal is less interesting.

To develop and validate our methodologies we use a set of ground truth traces collected by manually visiting the top 1,000 most popular web sites rated by Alexa and 1,000 news promoted by Google News. Then, we show the goodness of our methodologies with a three-day long HTTP traffic trace passively collected from a PoP of an European ISP.

Our major contributions are:

• We present a first set of algorithms and filtering stages to extract user-URLs from passive HTTP traces. We tune and quantify the performance of the algorithms using the dataset for which we have the ground truth. Our results show that we successfully detect 96% of user-URLs with only 1% of false positive rate and 66% of precision. Besides, precision can be enhanced to 80% with a loss of only 6% of user-URLs. When applied to the ISP trace, we found that only 1.6% of the 190 million HTTP requests in the dataset corresponds to actual URLs intentionally visited by users.

• We propose two algorithms to detect which user-URLs should be promoted also as interesting-URLs. Both algorithms leverage the social network information that is typically present in popular and interesting web sites. We found that only 15% of user-URLs may be classified as interesting-URLs.

• We show how rich the perspective of an ISP can be. We observe users accessing videos hosted on 9 different platforms, and news coming from 80 different news portals. This indicates that the view most OTTs get is different from the wideangle picture an ISP could get. We further demonstrate this view by providing early web analytics results on the referral shares of well known content promotion platforms. We show that, surprisingly, only 11% of all user-URL views happened after (thanks to) a Google Search, and, in the best case, no more than 13% of them came from Facebook, Twitter or Google News. The rest of this paper is organized as follows. First, Sec. 2 describes the background and resumes the related work of this paper. Second, Sec. 3 describes the datasets we use. Sec. 4 describes our algorithms and presents their performance evaluation. Sec. 4 applies our filtering methods on real data. Finally, Sec. [START_REF] Kleinman | Verizon selling customers' cell phone data: Report[END_REF] presents the open problems of this work and concludes the paper.

Background and Related Work

The structure of a web page has considerably grown in complexity in the last decade. Today, it often consists of a complicated tangle of HTML, JavaScript, multimedia objects, CSS, XML files, etc. As depicted in Fig. 1, when attempting to view a web page, the browser downloads each of these objects using separate HTTP requests. As a consequence, a simple user's click on a URL generates a cascade of several HTTP requests between the user terminal and an almost unpredictable number of servers and caches that store these objects. Besides, JavaScript, Ajax and Flash objects may generate extra HTTP traffic that was not intentionally requested by the user (e.g., the automatic fetching of a YouTube video). Furthermore, many non-web applications nowadays rely on HTTP to exchange their data (e.g., Dropbox and software updates). Therefore, even when a trace of HTTP transactions performed by a terminal is available, identifying which requests actually correspond to a human interaction is not a straightforward task.

To the best of our knowledge, only few methods have been proposed in the literature to detect URLs that were intentionally visited by users [START_REF] Barford | Generating representative web workloads for network and server performance evaluation[END_REF], [START_REF] Choi | A behavioral model of web traffic[END_REF], [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF].

The first method is time-based [START_REF] Barford | Generating representative web workloads for network and server performance evaluation[END_REF], it relies on the intuition that a cascade of browser-URLs follows the initial user-URL. Browser-URLs are tightly grouped in time after the user-URL request has been observed (see red dotted boxes in Fig. 1). As such, the first request after a given inactivity period can be considered as a new user-URL, while all the following HTTP requests happening before a time threshold are assumed to be browser-URLs. Unfortunately the estimation of the algorithm time thresholds is not a straightforward task, and many factors (e.g., latencies due to network conditions) may harm the performance of this method [START_REF] Ihm | Towards understanding modern web traffic[END_REF].

Another methodology, presented in [START_REF] Choi | A behavioral model of web traffic[END_REF], is type-based. It relies on the media information reported in the Content-Type field contained in the HTTP responses: the URLs associated to responses specifying text/HTML type are considered as main pages while the others are considered as browser-URLs. However, this approach has been shown to be unreliable [START_REF] Schneider | Pitfalls in http traffic measurements and analysis[END_REF].

To the best of our knowledge, the most recent methodologies to investigate the composition of modern web pages are StreamStructure [START_REF] Ihm | Towards understanding modern web traffic[END_REF] and ReSurf [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF]. They both exploit the Referer 5 field to split HTTP transactions into multiple streams, thus reducing the temporal overlaps between clicks on different URLs (e.g., when a user keeps several tabs open in her browser, for the same time window the technique can identify different streams). StreamStructure processes each detected stream separately. On each of them, it first applies a type-based filter (based on Content-Type) to keep only HTML/text pages. It then applies a time-based filter to detect main pages. To set a proper time threshold, the method leverages the Google Analytics beacon: once the Google Analytics beacon is downloaded, the page is considered as loaded, so that there is no need to set a static time threshold. Despite the improvements, StreamStructure still suffer from some limitations. First, it leverages Google Analytics information, which is present in only 40% of web pages (according to [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF]). Furthermore, it relies on the HTTP Content-Type field which has two drawbacks: (1) it has been shown to be often unreliable [START_REF] Schneider | Pitfalls in http traffic measurements and analysis[END_REF] and (2) this needs to monitor both HTTP requests and corresponding responses, which increases the complexity of the traffic extraction phase . We target a solution that overcomes these drawbacks, and for which only outgoing network traffic is needed to be monitored, so that the traffic extraction and filtering are kept as simple as possible. More recently, ReSurf [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF] has been proposed. Although it does a great job in overcoming the limitations of [START_REF] Ihm | Towards understanding modern web traffic[END_REF], it still rely on the Content-Type (as well as the Content-Size), which makes it inadequate for our needs.

Datasets

While per-object information is sufficient to study caching (e.g., assess caching policies and gains) or filtering (e.g., blocking unwanted objects), further processing is needed to infer human-induced HTTP transactions. This is one of the challenges that we tackle in this paper. For this purpose, we rely on two types of traces. The first is collected in a controlled test-bed where the ground truth is known and used. The second corresponds to a real traffic trace on which we apply our algorithms to appreciate the type of information that is possible to extract.

For the preliminary evaluation of our methods, we collect two ground truth traces. First, similarly to [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF], we build a trace (HTTP-Alexa) by manually visiting the top 100 most popular web sites according to Alexa ranking. In each of these sites, we randomly visit up to 10 links contained in them. We manually collect all the clicked URLs as they were reported by the browser bar. In parallel, we capture and extract HTTP requests generated by the browser. This resulted in a total list of 905 user-URLs, corresponding to 39025 browser-URLs. Second, we build a similar trace (HTTP-GNews) by visiting around 900 news sites promoted on Google News.

For the real data, we use the open-source traffic monitoring tool Tstat [START_REF] Finamore | Experiences of Internet traffic monitoring with Tstat[END_REF] to rebuild HTTP conversations. Thanks to this tool, we obtained a three-day long HTTP traffic trace, HTTP-ISP, which we collected at a vantage point of a commercial ISP network. The dataset contains the HTTP requests generated by about 19,000 residential customers. In total we observed more than 190 millions of HTTP requests.

Content Filtering Algorithms

In this section, we introduce and evaluate our web object filtering algorithms. First, we aim at distinguishing between intentionally visited URLs, i.e., user-URLs, and automatically requested ones, i.e., browser-URLs.

Identification of user-URLs

As explained in Sec. 2, we believe that new and simpler methods must be devised to identify user-URLs. As a design choice, we assume the ability to parse only HTTP requests to reduce the complexity at the probe capturing the traffic and the amount of data to process. To this end, we propose four filtering mechanisms and compare their performance as detailed below. 1) F-Referer: This method exploits the Referer field, not to separate requests in different streams as done in [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF], but to directly pinpoint user-URLs. As shown in Fig. 1, when the URL of a web page is clicked, a sequence of HTTP requests is generated by the browser to retrieve all the embedded objects, thus generating a cascade of browser-URLs. All these requests have as a referer the starting user-URL (see Fig. 1). Therefore, for each request, this filter ignores the URL and focuses on the referer field, so that we are sure of capturing all the original user-URLs. However, observe that this approach captures all web objects with a hierarchical structure (e.g., JavaScript and CSS files that embed themselves other files).

2) F-Children: The nowadays trend of web page design goes towards including lots of embedded objects, which we call children. By counting the number of URLs seen with a given referer, it is possible to know the number of children composing the corresponding parent URL. Thus, we can filter out those URLs with a low number of children, e.g., simple objects that contain few other objects (e.g., URL-3c in Fig. 1).

3) F-Type: Similar in spirit to [START_REF] Choi | A behavioral model of web traffic[END_REF], this filter acts on URLs based on their type. However, instead of relying on the Content-Type field which is exposed in HTTP responses, we inspect the extensions of the objects queried by the HTTP requests: we discard URLs pointing to .js, .css, .swf objects. 4) F-Ad: A large amount of advertisement is embedded in nowadays web pages through the mean of iframe HTML nodes. By design, an advertisement iframe may embed several other objects itself that has as referer the advertisement page. Thus, ads likely to pass all above filters. To counter this phenomenon, we blacklist URLs pointing to known advertisement platforms using the filter provided by AdBlock [START_REF]Adblock Plus[END_REF].

In addition to these methods, we also test a time-based filter (F-Time) as proposed in [START_REF] Barford | Generating representative web workloads for network and server performance evaluation[END_REF], [START_REF] Ihm | Towards understanding modern web traffic[END_REF], [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF], using a static time threshold. Performance on ground truth datasets We first evaluate these methods on the HTTP-Alexa dataset, described in Sec. 3. In Fig. 2 we graphically report the performance of filters F-Referer alone, F-Referer + F-Type and F-Referer + F-Type + F-Ad through a Venn diagram. We observe that the F-Referer method alone has a high "filtering capacity". In fact, it reduces the set of browser-URLs from the 39025 URLs in HTTP-Alexa to only 2616 candidate user-URLs. It has therefore a 4,4% of false positive rate (FPR) 6 . Besides, it has a high recall7 (98,34%). Manually inspecting the few misses, we find that they either correspond to HTTPS visits which did not pass the referer field, or to Flash content for which no URL requests are issued for browsing. However, its precision 8 is still low (34%), which means that there is still a considerable amount of false positives. To reduce the set of false positives, we combine the F-Referer filter with the other filters with different configurations, i.e., considering different thresholds. The results are summarized in Tab. 1. Both F-Time and F-Children enhance the precision when we increase respectively the time threshold and the minimum number of children (they invalidate false positives). However, they come at the cost of decreasing the recall (invalidating valid user-URLs). On the other hand, the F-Type and the F-Ad filters let us enhance the precision, with almost no impact on the recall. In reality, the F-Ad filter removes 16 valid user-URLs (see the dark green slice that is cut by the introduction of F-Ad in Fig. 2), but these were unintentionally visited when we collected the trace 9 .

We acknowledge that there is a tradeoff between recall and precision. The best combination to apply depends therefore on whether we want to capture all user-URLs or to remove all false positives. As a start, we opt for now for a most conservative approach that favors recall over precision. For the rest of the paper, we retain the F-Type coupled with F-Ad filters applied after the F-Referer method (i.e., F-Referer + F-Type + F-Ad). This guarantees 96.57% of recall, with only 1.17% of false positive rate.

Pinpointing Interesting URLs via OSN metadata

With the goal of targeting a recommendation system, we are now interested in identifying interesting-URLs among the detected user-URLs. Indeed, manually looking we find that many of them do not correspond to URLs that might attract users' attention (e.g., the web portal of an online bank). Therefore, an extra step in the filtering is needed to go from user-URLs to interesting-URLs. Finding a measure of interest is challenging since it involves human subjects and tastes. We investigate on simple heuristics that leverages online social network meta-information. We assume that interesting URLs should be rich with "social" features (e.g., share buttons). The idea is that if a web page is meant to be shared, then it might interest other people. We thus develop two methods to understand which user-URLs are "social-networks enabled". In particular we considered two approaches: 1) Active: This method uses a web scraper to actively query the URL and parse the returned HTML code looking for the presence of the OpenGraph protocol 10 [14]. If the protocol is present, the user-URL is classified as interesting.

2) Passive: This approach aims at passively detecting if a web page contains any of the well known social networks buttons. Given a user-URL X, we inspect its children, i.e., URLs having X as referer, and match them against a list of URLs necessary to load such buttons 11 . Such list was built by following the web development guidelines of several different social networks.

Performance on ground truth datasets

To evaluate these methods, we test if they already work on platforms that are known to be "interesting". In particular, we test them against Google News. For this purpose, we visit 1000 URLs promoted by Google News. Applying the active and the passive methods on this trace, we find that they classify as interesting respectively 79% and 70.72% of Google News URLs. For the active method, this means that 79% of Google news URLs actually implement the OpenGraph protocol. To understand the passive method's false negatives, we manually inspect them. We find that they correspond to web sites that use custom methods to embed the social networks buttons and that our filter fails to identify. For instance, YouTube uses a non standard solution. However, since it is OpengGraph compliant, our active method correctly detects it. To estimate the capability of pinpointing interesting web objects, we first apply the filter chain F-Referer + F-Type + F-Ad on HTTP-Alexa trace to detect user-URLs; then we use our social-aware heuristics. Intuitively, the URLs Alexa ranking are less likely to be promoted than the Google News URLs, we expect them therefore to contain much less interesting URLs. This was confirmed by our both methods which gave similar results: 33% of the user-URLs were labeled as interesting-URLs using the active method, and 35% using the passive one. These methods look promising, we use them in the rest of the paper and leave their enhancement for future work.

Applying the filtering on real data

In this section, we apply our filtering methods on the real data (HTTP-ISP ) with two purposes in mind: first to rank and analyze user-URLs and interesting-URLs, and second to do some preliminary web analytics job.

Additional problems

When considering the real HTTP traffic for filtering, some additional sources of error have been detected and called for more ingenuity. In particular, we noticed two main problems, and we propose two simple mechanisms to factor them out.

i) URLs generated by non-browser applications: Most applications use HTTP to automatically download web objects. The queried URLs are clearly not relevant, and must be ignored. We identify those URLs by inspecting the User-Agent field, which informs about which client application generated the HTTP request, and white-listing well-known browsers only. This discards around 15% of URL requests in our dataset.

ii) Inflated popularity induced by some users: Sometimes browsers generate multiple HTTP requests for the same content, e.g., automatically reloading a page, or downloading videos in chunks. This phenomenon inflates the popularity of some URLs. We counter this effect by counting a URL only once for each user-id.

Ranking and Classifying URLs

We first apply the F-Referer + F-Type + F-Ad filters, and study the popularity of the resulting user-URLs. Fig. 3 shows the popularity of all-URLs, user-URLs and interesting-URLs. The x-axis reports the rank of URLs, while the y-axis reports the actual number of occurrences of each URL, i.e., its popularity. Both axes are log-scale. Observe that the distribution follows a typical Zipf law, and many URLs show a low popularity: only 10,000 out of millions URLs have a popularity larger than 1000.

As expected, the user-URLs represent a tiny fraction of all the URLs. Our method detects that among the 190 million URL requests, only 1,6% correspond to actual user-URLs requests. Among these user-URLs views, only around 15% were detected as potentially interesting.

We next analyze the interesting user-URLs. We manually classify the top 1000 URLs to build a set of rules to help us having a preliminary classification of the rest of the URLs. Among these top 1000 URLs, we find that 482 are news (or blogs), 336 are services (e.g., online shops, travel engines, etc.) and 91 were videos. Extending a similar classification on the rest of the interesting user-URLs, we find that (at least) 18% correspond to videos coming from 9 different platforms (YouTube alone 15%) and 22% correspond to news from around 80 different news web sites. This observation confirms that the ISP is probably the only entity that has such a rich cross-service and wide-angle vantage point on the Internet.

Open issues We now report some of the limits observed with our filtering methods. First, for the user-URLs, although we drastically reduce the set of candidate URLs, our results still contain some false positives, which is not surprising given their relative high percentage. This is mainly due to the complex composition of web pages with a nested structure of objects. In the future, we plan to (1) test some of our other filtering methods that favor precision at the cost of recall (example the children method) as well as (2) work on enhancing our methods.

Another issue is that the returned list of the top most interesting-URLs contains popular and well-known web pages, e.g., the Google Search home page, or the most popular news portals. This confirms on the one hand the goodness of our algorithms; on the other hand, this opens the space for smarter algorithms to pinpoint interesting-but-not-obvious-URLs.

Finally, our algorithms outperform Resurf [START_REF] Xie | Resurf: Reconstructing web-surfing activity from network traffic[END_REF] in terms of processing speed. Applying F-Ref + F-Type + F-ad on one hour of HTTP-ISP (19,000 users) took us around 43 minutes. This is about the same time it took Resurf to process one hour traffic of only 1,000 users. However, our main bottleneck is the F-Ad due to the large size of its catalog; F-Ref + F-Type alone take only 3 minutes to complete. We plan to optimize it as part of our future work.

Early web analytics results

Web analytics is an important tool for business and market research. It helps companies to refine the target of their advertisement campaigns, eventually giving precious hints about where to place advertisement to collect more user clicks. Most of such tools today work on a per site basis: each site has a local view on where its visits came from (referring to it). Thus, a general view is missing, and it is not clear which web platforms drive most of today's user visits. Thanks to our filtering methods, ISPs overcome this limit, reaching a cross-service view, by simply inspecting the referers associated to the detected URLs.

As a preliminary step, we start by quantifying the referral share of Google, Facebook and Google News, i.e. how many visits are driven thanks to these promotion platforms. We report our results in Fig. 4 and Fig. 5, for user-URLs and interesting-URLs, respectively. The y-axis reports the referral share in percentage over all the views in the 3 days. In the x-axis, we apply the results on different populations of URLs depending on their popularity. The "No Referer" shares correspond to URLs which had no referer (e.g., due to direct browsing, bookmarks, email, etc.).

Interestingly, a considerable amount of visits came with no referer (around 13%). This goes up to 25% for the top 1000 interesting-URLs, meaning that direct browsing is common when browsing the web. As expected, the shares of visits driven by well-known platforms are larger for interesting-URLs compared to user-URLs. However, the share of requests coming from Google is more important for unpopular objects if compared to popular ones. This is again expected since users use search engines to look for unknown content rather than popular links. However, it is surprising that despite their notoriety, the referral shares of these platforms are relatively low: Only 11% of user URLs visits came from Google (and only 16% for interesting-URLs). Observe that the rest of the shares correspond to other platforms, such as news portals and blogs. We intend to rank them as part of our future work.

Open issues One of the main issues that we figured out in this study is due to usage of HTTPS. In fact, when going from a page served over HTTPS to another served over HTTP, the standard imposes to not include the referer field [START_REF] Fielding | Hypertext transfer protocol-http/1.1[END_REF], so that users' privacy is preserved. However, because of its importance to marketers, many websites implement workarounds, either by using the meta referer or HTTP redirections, to still inform the landing page where the visit came from. This biases our results inflating the "No Referer" share with visits that came from HTTPS pages, and for which the referer was not passed. To get a hint on the consistency of our results concerning Google and Facebook (that both use HTTPS for browsing), we made experiments employing several popular web browsers and different operating systems. We visited URLs starting from Google Search and Facebook and check whether the referer was correctly passed. For Google, we found that the referer is always passed, but this does not always hold for Facebook, indeed we observed different behaviors depending on the browser and operating system. As a consequence, the Facebook referral shares are underestimated, but upper bounded by the "No Referer" share. We plan to investigate more this issue as part of our future work.

Conclusions, Open Problems and Future Work

Driven by the intuition that ISPs have a great deal of information at their disposal that can be extracted from passive observation of the traffic flowing in their networks, we propose in this paper a set of algorithms to extract popular URLs from real Internet traffic. In this study we analyzed the feasibility of the automatic extraction of useful/interesting URLs from the humongous amount of HTTP data that flows through an ISP-wide network. Other challenges must be clearly faced, and ingenuity must be used to find appropriate solutions: i) Users' privacy: tracking users' activity is (commonly) performed by OTT providers and it has been strongly criticized recently [START_REF] Akkus | Non-tracking web analytics[END_REF]. ISPs face similar issues. They are allowed to monitor traffic for troubleshooting or even marketing purposes. Data could even be stored if properly anonymized and/or aggregated, i.e., if user's identity is irreversibly hidden. Our algorithms monitor aggregated data by design, without the need to offend users' privacy. ii) Traffic encryption: Apart the issue discussed in Sec. 5.3, traffic encryption deeply hampers whatever traffic mining operation. This is not a negligible aspect since today more than 20% of the HTTP traffic is encrypted [START_REF] Finamore | The need for an intelligent measurement plane: The example of time-variant cdn policies[END_REF]. Mining interesting URLs in presence of encrypted traffic is another interesting research direction. However, end-customers could be involved directly, e.g., offering them personalized services (such as media curation, or parental control filters) in exchange for installing some plugins that collect clicks. Our preliminary results suggest that the extraction of user-URLs from network traffic is a challenging task given the structure of nowadays web pages. However, "network gold mining" may represent a promising opportunity for ISPs to compete with OTTs in front of marketers and advertisers. Moreover, we believe information provided by our methodologies can be employed for a broad gamma of applications, ranging from new passive recommendation services to caching systems and parental control tools to name a few. In our ongoing efforts, we are developing each presented algorithm to run in a complete online extraction system, capable of working in a real ISP network scenario.

Fig. 1 .

 1 Fig. 1. Sequence of HTTP requests when accessing some standard web pages.

FFig. 2 .

 2 Fig. 2. Venn diagram reporting the effects of different filtering methods on our HTTP-Alexa dataset.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig.3. Content items popularity before and after filtering (HTTP-ISP ).

Table 1 .

 1 Performance of different filtering combinations.

	Method	Recall Precision FPR
	F-Ref + F-Time (0.01s)	97.90% 37.67% 3.7%
	F-Ref + F-Time (0.1s)	96.13% 41.09% 3.17%
	F-Ref + F-Time (1s)	87.51% 55.15% 1.39%
	F-Ref + F-Children (remove <= 1)	94.8% 43.13% 2.84%
	F-Ref + F-Children (remove <= 2)	93.14% 49.76% 2.06%
	F-Ref + F-Type	98.34% 46.35% 2.66%
	F-Ref + F-Ad	96.57% 44.14% 2.82%
	F-Ref + F-Type + F-Ad	96.57% 66.41% 1.17%
	F-Ref + F-Type + F-Ad + F-Children (remove <= 2) 91.82% 77.08% 0.45%
	F-Ref + F-Type + F-Ad + F-Children (remove <= 3) 89%	79.1% 0.29%

Google for instance observes a lot of visits thanks to its widespread Google analytics tool.

We ignore HTTPS for now. A discussion about how to deal with possible encryption is given in Sec. 6.

A field in the HTTP GET request that specifies from which previous page the URL has been referred.

Number of False Positives (here 1711) over the number of negatives (here 38120)

Number of URLs correctly labeled as user-URLs (true positives, here

890) over the number of user-URLs (ground truth, here 905).[START_REF] Barford | Generating representative web workloads for network and server performance evaluation[END_REF] Number of true positives over the number of items labeled as positive by the method (here 2616).[START_REF] Ihm | Towards understanding modern web traffic[END_REF] Although we acknowledge that some advertisements might interest people, we decide to skip them for now.

The OpenGraph protocol was developed by Facebook to help web pages getting integrated in "the social graph".

Available at http://www.retitlc.polito.it/finamore/plugins.txt.

⋆ This work was supported by the European Commission under the FP7 IP Project "An Intelligent Measurement Plane for Future Network and Application Management" (mPlane).