The 2nd IEEE INFOCOM Workshop on Networking Algorithms (WNA 2022)

Session WNA-S1

Network Measurement Algorithms

10:00 AM — 11:30 AM EDT
May 2 Mon, 10:00 AM — 11:30 AM EDT

LSE: A Learning-based Per-flow Spread Estimation Framework for Network Data Streams

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

Per-flow spread estimation is an important research problem for network data streams, which has been widely used in various practical applications. However, most solutions proposed in the past decades must use dedicated hardware to process all packets in the network data stream. Moreover, they fail to leverage useful patterns in their input data to improve estimation accuracy. This paper proposes a learning-based per-flow spread estimation framework (LSE) to complement the previous work. The proposed framework adopts random sampling to select elements for estimating, which can be easily implemented by the general-purpose CPU. Per-flow sampled data will be recorded in a hash table and encoded into a counter array. And we design a lightweight learning model to extract useful patterns from per-flow counter arrays, which will efficiently improve the performance of per-flow spread estimation. Experimental results based on real-world datasets show that our solution performs better than state-of-the-art competitors.

An Observation of Packet Classification: Most Rules are at the Top

Chengjun Jia, Li Chenglong, Yifan Li, Xiaohe Hu and Jun Li (Tsinghua University, China)

Multi-field packet classification plays a critical role in a modern computer network. Many algorithms are designed, but the analysis of the rule sets is insufficient. In this paper, we analyze the rule sets from the aspect of rule overlapping with the tools from graph theory and network verification. The correctness of some designs is confirmed, such as the partition is necessary. We also propose a patch, PCG, based on our observation that most rules are at the top. PCG can apply to various algorithms to further improve the classification performance. We evaluate PCG on a state-of-art algorithm, CutSplit, and find that PCG introduces about 20% throughput improvement.

Detecting Proxies Relaying Streaming Internet Traffic

Henry E Clausen (University of Edinburgh); Aditya Manocha and Michael Gibson (BT Group)

Internet Service Providers (ISPs) have to manage vast quantities of data being transmitted by customers on their networks. They can also be responsible for hosting broadcast material, such as live sports. One of the main issues in handling broadcasts is preventing piracy, in this case a customer relaying broadcast material to non customers. A challenge for detecting illegal relays of content is the incompleteness of information arising from packet sampling commonly seen in an ISP perspective. In this paper, we explore how to extract strong signals of content relay that are robust to sampling by using a weighted metric to efficiently measure correlation of content streams. Our results indicate that this signal provides a clear distinction between proxy-traffic and non-relayed network behaviour.

A Formal Analysis of the Count-Min Sketch with Conservative Updates

Younes Ben Mazziane (Universite Cote d'Azur & INRIA, France); Sara Alouf (INRIA, France); Giovanni Neglia (Inria, France)

Count-Min Sketch with Conservative Updates (CMS-CU) is a popular algorithm to approximately count items' appearances in a data stream. Despite CMS-CU's widespread adoption, the theoretical analysis of its performance is still wanting because of its inherent difficulty. In this paper, we propose a novel approach to study CMS-CU and derive new upper bounds on the expected value and the CCDF of the estimation error under an i.i.d. request process. Our formulas can be successfully employed to derive improved estimates for the precision of heavy-hitter detection methods and improved configuration rules for CMS-CU. The bounds are evaluated both on synthetic and real traces.

Session Chair

Jiaqi Zheng

Session WNA-S2

Routing and Scheduling Algorithms

12:30 PM — 2:00 PM EDT
May 2 Mon, 12:30 PM — 2:00 PM EDT

DDPG-based Computation Offloading and Service Caching in Mobile Edge Computing

Lingxiao Chen (China Three Gorges University, China); Guoqiang Gong (University of Three Gorges, China); Jiang Kai (Wuhan University, China); Huan Zhou and Rui Chen (China Three Gorges University, China)

Mobile Edge Computing (MEC) migrates the computing center to the network edge to provide computing services for Mobile Users (MUs). However, due to the limited capacity of MUs and insufficient types of services stored by edge servers, it brings great challenges to computation offloading and service caching in Internet of Things (IoT) network. In this paper, we investigate the joint optimization problem of computation offloading, resource allocation and service caching replacement in a collaborative MEC system to minimize the total cost of all MUs under the latency and resource constraints. Accordingly, we formulate the problem as a Mixed Integer Non-linear Programming (MINLP) problem. In order to solve this problem, the Deep Deterministic Policy Gradient (DDPG)-based algorithm is proposed. The simulation results show that the proposed algorithm is better than other benchmark schemes in different scenarios.

Cost Effective Routing in Large-scale Multi-hop LoRa Networks

Silin Feng, Jiajun Chen and Zhiwei Zhao (University of Electronic Science and Technology of China, China)

Low-Power Wide-Area Network (LPWAN) technologies promoted the communication capacities of Internet of Things (IoT) to several even dozens of kilometers. LoRa is one of these technologies which has the characteristics of long-range, low data rates and low power consumption. For some application scenarios, the LoRaWAN architecture is applied to a star-of-stars topology, which works well. However, for several non-line-of-sight or larger deployment range scenarios, such as underground deployment and large-scale military launch, the single-hop topology may not meet the requirements of scenarios. Adding gateways to increase coverage increases deployment complexity and reduces information sharing. Furthermore, the exhaustion of a single node in the network will bring extra cost of replacing the battery artificially, further reducing the network life bottleneck. consequently, this paper introduces a multi-hop protocol MLoRa to solve these problems. MLoRa gives a routing strategy upon network layer, which brings a greater coverage area and a lower and balanced consumption in original coverage in LoRa networks.

Programmable Packet Scheduling With SP-PIFO: Theory, Algorithms and Evaluation

Balázs Vass, Csaba Sarkadi and Gábor Rétvári (Budapest University of Technology and Economics, Hungary)

Push-In First-Out (PIFO) is a theoretical hardware model for programmable packet scheduling, enabling scheduling policies to be comprehensibly and dynamically reconfigured, and SP-PIFO is a practical emulation for PIFO that can be readily implemented with stock P4 switches. The efficiency of SP-PIFO hinges on a simple heuristic, Push-Up\slash Push-Down (PUPD), which is responsible for dynamically adapting the mapping of input packets to a fixed set of strict priority queues so as to minimize the rate of scheduling errors with respect to an ideal PIFO. In this paper, we present the first formal analysis of the PUPD algorithm. Our competitive analysis yields that the capacity of PUPD to emulate an optimal PIFO model is getting linearly worse as we keep on adding priority queues to the system. Motivated by this finding, we present an optimal offline scheme, which, given a stochastic model of the input, outputs the optimal SP-PIFO configuration in polynomial time, and we introduce an online heuristic that aims to approximate the offline optimum without requiring a stochastic input model. Our simulations show that the online algorithm can improve the performance of SP-PIFO by a factor of 2x in certain configurations.

End-to-end TCP-compatible Backpressure Routing

Christos Liaskos (Institute of Computer Science, Foundation of Research and Technology, Hellas, Greece); Konstantinos Alexandris and Siyu Tang (Huawei Technologies Duesseldorf GmbH, Germany); Anindya Das (Huawei Technologies Munich, Germany)

Backpressure constitutes a well-known throughput-optimal packet scheduler. Backpressure scheduling decisions are taken based on commodity queue build-ups at the network nodes, and constant status updates among neighbors. Nonetheless, it is also well known for its incompatibility with TCP, which uses congestion control to avoid queue build-ups, while also being sensitive to packet timeouts and their delivery order. These factors limit the use of backpressure in the local packet forwarding plane, e.g., within switches. The present work presents a breakthrough in combining TCP and backpressure at the network layer, overcoming any compatibility issues. The key-idea is to apply the Lyapunov framework cumulatively, over a large set of router hardware clock ticks. This approach allows for the throughput-optimal backpressure decisions to be expressed via regular traffic engineering routing rules, instead of explicit per-packet forwarding directives. Moreover, these throughput-optimizing routing rules are derived using common metrics logged at commercial routers, and not via queue build-ups. Simulation results validate the analytical findings and demonstrate significant throughput gains over state-of-the-art related approaches.

Session Chair

Haipeng Dai

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