Session D-7

Measurement and Monitoring

10:00 AM — 11:30 AM EDT
May 13 Thu, 10:00 AM — 11:30 AM EDT

Self-Adaptive Sampling for Network Traffic Measurement

Yang Du, He Huang and Yu-e Sun (Soochow University, China); Shigang Chen (University of Florida, USA); Guoju Gao (Soochow University, China)

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, complementing sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, overlooking that the sampling rates different flows require to meet the same accuracy constraint are different. It leads to a waste in storage and communication resources. In this paper, we present self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose two algorithms, SAS-LC and SAS-LOG, which are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. Experimental results based on real Internet traces show that, when compared to NDS in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. Moreover, SAS-LOG can save 40% on-chip space and reduce up to 96% communication cost for large flows than NDS in per-flow size estimation.

MTP: Avoiding Control Plane Overload with Measurement Task Placement

Xiang Chen (Peking University, Pengcheng Lab, and Fuzhou University, China); Qun Huang (Peking University, China); Wang Peiqiao (Fuzhou China, China); Hongyan Liu (Zhejiang University, China); Yuxin Chen (University of Science and Technology of China, China); Dong Zhang (Fuzhou University, China); Haifeng Zhou (Zhejiang University, and Zhejiang Lab, China); Chunming Wu (Zhejiang Lab, and Zhejiang University, China)

In programmable networks, measurement tasks are placed on programmable switches to keep pace with high-speed traffic. At runtime, programmable switches send events to the control plane for further processing. However, existing solutions for task placement overlook the limitations of control plane resources. Thus, excessive events may overload the control plane. In this paper, we propose MTP, a system that eliminates control plane overload via careful task placement. For each task, MTP analyzes its structure to estimate its maximum possible rate of sending events to the control plane. Then it builds an optimization framework that addresses the resource restrictions of both switches and the control plane. We have implemented MTP on Barefoot Tofino switches. The experimental results indicate that MTP outperforms existing solutions with higher accuracy across four real use cases.

Low Cost Sparse Network Monitoring Based on Block Matrix Completion

Kun Xie and Jiazheng Tian (Hunan University, China); Gaogang Xie (Institute of Computing Technology, Chinese Academy of Sciences, China); Guangxing Zhang (Institute of Computing Technology Chinese Academy of Sciences, China); Dafang Zhang (Hunan University, China)

Due to high network measurement cost, network-wide monitoring faces many challenges. For a network consisting of n nodes, the cost of one time network-wide monitoring will be O(n 2 ). To reduce the monitoring cost, inspired by recent progress of matrix completion, a novel sparse network monitoring scheme is proposed to obtain network-wide monitoring data by sampling a few paths while inferring monitoring data of others. However, current sparse network monitoring schemes suffer from the problems of high measurement cost, high computation complexity in sampling scheduling, and long time to recover the un-sampled data. We propose a novel block matrix completion that can guarantee the quality of the un-sampled data inference by selecting as few as m = O(nr ln(r)) samples for a rank r N × T matrix with n = max{N, T }, which largely reduces the sampling complexity as compared to the existing algorithm for matrix completion. Based on block matrix completion, we further propose a light weight sampling scheduling algorithm to select measurement samples and a light weight data inference algorithm to quickly and accurately recover the un-sampled data. Extensive experiments on three real network monitoring data sets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithms.

Expectile Tensor Completion to Recover Skewed Network Monitoring Data

Kun Xie and Siqi Li (Hunan University, China); Xin Wang (Stony Brook University, USA); Gaogang Xie (Institute of Computing Technology, Chinese Academy of Sciences, China); Yudian Ouyang (Hunan University, China)

Network applications, such as network state tracking and forecasting, anomaly detection, and failure recovery, require complete network monitoring data. However, the monitoring data are often incomplete due to the use of partial measurements and the unavoidable loss of data during transmissions. Tensor completion has attracted some recent attentions with its capability of exploiting the multi-dimensional data structure for more accurate un-measurement/missing data inference. Although conventional tensor completion algorithms can work well when the application data follow the symmetric normal distribution, it cannot well handle network monitoring data which are highly skewed with heavy tails. To better follow the data distribution for more accurate recovery of the missing entries with large values, we propose a novel expectile tensor completion (ETC) formulation and a simple yet efficient tensor completion algorithm without hard-setting parameters for easy implementation. From both experimental and theoretical ways, we prove the convergence of the proposed algorithm. Extensive experiments on two real-world network monitoring datasets demonstrate the effectiveness of the proposed ETC.

Session Chair

Xiaolong Zheng (Beijing University of Posts and Telecommunications, China)

Session D-8


12:00 PM — 1:30 PM EDT
May 13 Thu, 12:00 PM — 1:30 PM EDT

BLESS: BLE-aided Swift Wi-Fi Scanning in Multi-protocol IoT Networks

Wonbin Park and Dokyun Ryoo (Seoul National University, Korea (South)); Changhee Joo (Korea University, Korea (South)); Saewoong Bahk (Seoul National University, Korea (South))

Wi-Fi scanning that searches neighboring access points (APs) is an essential prerequisite for Wi-Fi operations such as initial association and handover. As the traffic demand increases, APs are more densely deployed and the number of operating Wi-Fi channels also increases, which, however, results in additional scanning delay and makes the scanning a burdensome task. In this paper, we note that the co-location of Wi-Fi protocol with BLE protocol is a common practice in IoT networks, and develop a Wi-Fi passive scanning framework that uses BLE to assist scanning. Although the framework has great potential to improve scanning performance without explicit message exchanges, there are technical challenges related to time synchronization and channel switching delay. We address the challenges and develop a practical passive scanning scheme, named BLESS-Sync. We verify its performance through testbed experiments and extensive simulations, and show that BLESS-Sync significantly outperforms legacy Wi-Fi scanning in terms of scanning delay and energy efficiency.

Efficient Association of Wi-Fi Probe Requests under MAC Address Randomization

Jiajie Tan and S.-H. Gary Chan (The Hong Kong University of Science and Technology, China)

Wi-Fi-enabled devices such as smartphones periodically search for available networks by broadcasting probe requests which encapsulate MAC addresses as the device identifiers. To protect privacy (user identity and location), modern devices embed random MAC addresses in their probe frames, the so-called MAC address randomization. Such randomization greatly hampers statistical analysis such as people counting and trajectory inference. To mitigate its impact while respecting privacy, we propose Espresso, a simple, novel and efficient approach which establishes probe request association under MAC address randomization. Espresso models the frame association as a flow network, with frames as nodes and frame correlation as edge cost. To estimate the correlation between any two frames, it considers the multimodality of request frames, including information elements, sequence numbers and received signal strength. It then associates frames with minimum-cost flow optimization. To the best of our knowledge, this is the first piece of work that formulates the probe request association problem as network flow optimization using frame correlation. We have implemented Espresso and conducted extensive experiments in a leading shopping mall. Our results show that Espresso outperforms the state-of-the-art schemes in terms of discrimination accuracy (> 80%) and V-measure scores (> 0.85).

Coexistence of Wi-Fi 6E and 5G NR-U: Can We Do Better in the 6 GHz Bands?

Gaurang Naik and Jung-Min (Jerry) Park (Virginia Tech, USA)

Regulators in the US and Europe have stepped up their efforts to open the 6 GHz bands for unlicensed access. The two unlicensed technologies likely to operate and coexist in these bands are Wi-Fi 6E and 5G New Radio Unlicensed (NR-U). The greenfield 6 GHz bands allow us to take a fresh look at the coexistence between Wi-Fi and 3GPP-based unlicensed technologies. In this paper, using tools from stochastic geometry, we study the impact of Multi User Orthogonal Frequency Division Multiple Access, i.e., MU OFDMA-a feature introduced in 802.11ax-on this coexistence issue. Our results reveal that by disabling the use of the legacy contention mechanism (and allowing only MU OFDMA) for uplink access in Wi-Fi 6E, the performance of both NR-U networks and uplink Wi-Fi 6E can be improved. This is indeed feasible in the 6 GHz bands, where there are no operational Wi-Fi or NR-U users. In so doing, we also highlight the importance of accurate channel sensing at the entity that schedules uplink transmissions in Wi-Fi 6E and NR-U. If the channel is incorrectly detected as idle, factors that improve the uplink performance of one technology contribute negatively to the performance of the other technology.

LoFi: Enabling 2.4GHz LoRa and WiFi Coexistence by Detecting Extremely Weak Signals

Gonglong Chen, Wei Dong and Jiamei Lv (Zhejiang University, China)

Low-Power Wide Area Networks (LPWANs) emerges as attractive communication technologies to connect the Internet-of-Things. A new LoRa chip has been proposed to provide long range and low power support on 2.4GHz. Comparing with previous LoRa radios operating on sub-gigahertz, the new one can transmit LoRa packets faster without strict channel duty cycle limitations and have attracted many attentions. Prior studies have shown that LoRa packets may suffer from severe corruptions with WiFi interference. However, there are many limitations in existing approaches such as too much signal processing overhead on weak devices or low detection accuracy. In this paper, we propose a novel weak signal detection approach, LoFi, to enable the coexistence of LoRa and WiFi. LoFi utilizes a typical physical phenomenon Stochastic Resonance (SR) to boost weak signals with a specific frequency by adding appropriate white noise. Based on the detected spectrum occupancy of LoRa signals, LoFi reserves the spectrum for LoRa transmissions. We implement LoFi on USRP N210 and conduct extensive experiments to evaluate its performance. Results show that LoFi can enable the coexistence of LoRa and WiFi in 2.4GHz. The packet reception ratio of LoRa achieves 98% over an occupied 20MHz WiFi channel, and the WiFi throughput loss is reduced by up to 13%.

Session Chair

Christoph Sommer (TU Dresden, Germany)

Session D-9


2:30 PM — 4:00 PM EDT
May 13 Thu, 2:30 PM — 4:00 PM EDT

VideoLoc: Video-based Indoor Localization with Text Information

Shusheng Li and Wenbo He (McMaster University, Canada)

Indoor localization serves as an important role in various scenarios such as navigation in shopping malls or hospitals. However, the existing technology is usually based on additional deployment and the signal suffers from strong environment interference in the complex indoor environment. In this paper, we propose video-based indoor localization with text information (i.e. "VideoLoc") without the deployment of additional equipment. Videos taken by the phone carriers cover more critical information (e.g. logos in malls), while a single photo may fail to capture it. To reduce redundant information in the video, we propose key-frame selection based on deep learning model and clustering algorithm. Video frames are characterized with deep visual descriptors and clustering algorithm efficiently clusters these descriptors into a set of non-overlapping snippets. We select keyframes from these non-overlapping snippets in terms of the cluster centroid that represents each snippet. Then, we propose text detection and recognition with transformation to make full use of stable and discriminative text information (e.g. logos or room numbers) in keyframes for localization. After that, we obtain the location of the phone carrier via triangulation algorithm. The experimental results show that VideoLoc achieves high precision of localization and is robust to dynamic environments.

The Effect of Ground Truth Accuracy on the Evaluation of Localization Systems

Chen Gu (Google, USA); Ahmed Shokry and Moustafa Youssef (Alexandria University, Egypt)

The ability to accurately evaluate the performance of location determination systems is crucial for many applications. Typically, the performance of such systems is obtained by comparing ground truth locations with estimated locations. However, these ground truth locations are usually obtained by clicking on a map or using other worldwide available technologies like GPS. This introduces ground truth errors that are due to the marking process, map distortions, or inherent GPS inaccuracy.

In this paper, we present a theoretical framework for analyzing the effect of ground truth errors on the evaluation of localization systems. Based on that, we design two algorithms for computing the real algorithmic error from the validation error and marking/map ground truth errors, respectively. We further establish bounds on different performance metrics.

Validation of our theoretical assumptions and analysis using real data collected in a typical environment shows the ability of our theoretical framework to correct the estimated error of a localization algorithm in the presence of ground truth errors. Specifically, our marking error algorithm matches the real error CDF within 4%, and our map error algorithm provides a more accurate estimate of the median/tail error by 150%/72% when the map is shifted by 6m.

Train Once, Locate Anytime for Anyone: Adversarial Learning based Wireless Localization

Danyang Li, Jingao Xu, Zheng Yang, Yumeng Lu and Qian Zhang (Tsinghua University, China); Xinglin Zhang (South China University of Technology, China)

Among numerous indoor localization systems, WiFi fingerprint-based localization has been one of the most attractive solutions, which is known to be free of extra infrastructure and specialized hardware. To push forward this approach for wide deployment, three crucial goals on delightful deployment ubiquity, high localization accuracy, and low maintenance cost are desirable. However, due to severe challenges about signal variation, device heterogeneity, and database degradation root in environmental dynamics, pioneer works usually make a trade-off among them. In this paper, we propose iToLoc, a deep learning based localization system that achieves all three goals simultaneously. Once trained, iToLoc will provide accurate localization service for everyone using different devices and under diverse network conditions, and automatically update itself to maintain reliable performance anytime. iToLoc is purely based on WiFi fingerprints without relying on specific infrastructures. The core components of iToLoc are a domain adversarial neural network and a co-training based semi-supervised learning framework. Extensive experiments across 7 months with 8 different devices demonstrate that iToLoc achieves remarkable performance with an accuracy of 1.92m and > 95% localization success rate. Even 7 months after the original fingerprint database was established, the rate still maintains > 90%, which significantly outperforms previous works.

Failure Localization through Progressive Network Tomography

Viviana Arrigoni (Sapienza, University of Rome, Italy); Novella Bartolini (Sapienza University of Rome, Italy); Annalisa Massini (Sapienza Università di Roma, Italy); Federico Trombetti (Sapienza, University of Rome, Italy)

Boolean Network Tomography (BNT) allows to localize network failures by means of end-to-end monitoring paths. Nevertheless, it falls short of providing efficient failure identification in real scenarios, due to the large combinatorial size of the solution space, especially when multiple failures occur concurrently. We aim at maximizing the identification capabilities of a bounded number of monitoring probes. To tackle this problem we propose a progressive approach to failure localization based on stochastic optimization, whose solution is the optimal sequence of monitoring paths to probe. We address the complexity of the problem by proposing a greedy strategy in two variants: one considers exact calculation of posterior probabilities of node failures given the observation, whereas the other approximates these values through a novel failure centrality metric. We discuss the approximation of the proposed approaches.
Then, by means of numerical experiments conducted on real network topologies, we demonstrate the practical applicability of our approach. The performance evaluation evidences the superiority of our algorithms with respect to state of the art solutions based on classic Boolean Network Tomography as well as approaches based on sequential group testing.

Session Chair

Song Fang (University of Oklahoma)

Session D-10


4:30 PM — 6:00 PM EDT
May 13 Thu, 4:30 PM — 6:00 PM EDT

Safety Critical Networks using Commodity SDNs

Ashish Kashinath (University of Illinois at Urbana-Champaign, USA); Monowar Hasan (University of Illinois Urbana-Champaign, USA); Rakesh Kumar (University of Illinois, Urbana-Champaign, USA); Sibin Mohan (University of Illinois at Urbana-Champaign, USA); Rakesh B. Bobba (Oregon State University, USA); Smruti Padhy (University of Texas at Austin, USA)

Safety-critical networks often have stringent real-time requirements; they must also be resilient to failures. In this paper, we propose the RealFlow framework that uses commodity software-defined networks (SDNs) to realize networks with end-to-end timing guarantees, while also: (a) increasing resiliency against link/switch failures and (b) increasing network utilization. The use of SDNs in this space also improves the management capabilities of the system due to the global visibility into the network. RealFlow is implemented as a northbound SDN controller application compatible with standard OpenFlow protocols with little to no runtime overheads. We demonstrate feasibility on a real hardware testbed (Pica8 SDN switches+Raspberry Pi endhosts) and a practical avionics case study. Our evaluations show that RealFlow can accommodate 63% more network flows with safety-critical guarantees when compared to current designs and up to 18% when link resiliency (via backup paths) is also considered.

Bandwidth Isolation Guarantee for SDN Virtual Networks

Gyeongsik Yang, Yeonho Yoo and Minkoo Kang (Korea University, Korea (South)); Heesang Jin (ETRI, Korea (South)); Chuck Yoo (Korea University, Korea (South))

We introduce TeaVisor, which provides bandwidth isolation guarantee for software-defined networking (SDN)-based network virtualization (NV). SDN-NV provides topology and address virtualization while allowing flexible resource provisioning, control, and monitoring of virtual networks. However, to the best of our knowledge, the bandwidth isolation guarantee, which is essential for providing stable and reliable throughput on network services, is missing in SDN-NV. Without bandwidth isolation guarantee, tenants suffer degraded service quality and significant revenue loss. In fact, we find that the existing studies on bandwidth isolation guarantees are insufficient for SDN-NV. With SDN-NV, routing is performed by tenants, and existing studies have not addressed the overloaded link problem. To solve this problem, TeaVisor designs three components: path virtualization, bandwidth reservation, and path establishment, which utilize multipath routing. With these, TeaVisor achieves the bandwidth isolation guarantee while preserving the routing of the tenants. In addition, TeaVisor guarantees the minimum and maximum amounts of bandwidth simultaneously. We fully implement TeaVisor, and the comprehensive evaluation results show that near-zero error rates on achieving the bandwidth isolation guarantee. We also present an overhead analysis of control traffic and memory consumption.

Online Joint Optimization on Traffic Engineering and Network Update in Software-defined WANs

Jiaqi Zheng, Yimeng Xu and Li Wang (Nanjing University, China); Haipeng Dai (Nanjing University & State Key Laboratory for Novel Software Technology, China); Guihai Chen (Shanghai Jiao Tong University, China)

State-of-the-art inter-datacenter WANs rely on centralized traffic engineering (TE) to improve the network performance, where TE computation is a periodical procedure and timely performs routing configurations (i.e., enforces TE polices via add, remove and modify forwarding rules) in response to the changing network conditions. The TE computation determines the routing configurations corresponding to the current network conditions and the network update operations change the routing configurations from last TE to current TE solution. Existing works take centralized TE computation and network update as two individual optimization procedures, which inevitably leads to suboptimal solution in the long run. In this paper we initiate the study of online joint optimization on TE computation and network update with the objective of minimizing the sum of TE cost and network update cost. We formulate this problem as an optimization program and propose a set of provable online algorithms with rigorous competitive and regret analysis. Trace-driven simulations on two empirical topologies demonstrate that our algorithms can significantly decrease the total cost.

Modeling the Cost of Flexibility in Communication Networks

Alberto Martínez Alba (Technische Universität München, Germany); Péter Babarczi (Budapest University of Technology and Economics, Hungary & Technische Universität München, Germany); Andreas Blenk and Mu He (Technische Universität München, Germany); Patrick Kalmbach (Technical University of Munich, Germany); Johannes Zerwas and Wolfgang Kellerer (Technische Universität München, Germany)

Communication networks are evolving towards a more adaptive and reconfigurable nature due to the evergrowing demands they face. A framework for measuring network flexibility has been proposed recently, but the cost of rendering communication networks more flexible has not yet been mathematically modeled. As new technologies such as software-defined networking (SDN), network function virtualization (NFV), or network virtualization (NV) emerge to provide network flexibility, a way to estimate and compare the cost of different implementation options is needed. In this paper, we present a comprehensive model of the cost of a flexible network that takes into account its transient and stationary phases. This allows network researchers and operators to not only qualitatively argue about their new flexible network solutions, but also to analyze their cost for the first time in a quantitative way.

Session Chair

Y. Richard Yang (Yale University)

Made with in Toronto · Privacy Policy · INFOCOM 2020 · © 2021 Duetone Corp.