Packet routing analyses using probabilistic data structures in Multi-Tenant Networks based on programmable devices

Abstract

Given the network traffic growth, due to applications that heavily use computational cloud infrastructure, the need for improving the monitoring traffic techniques has increased. For traffic engineering, it is essential to gain total visibility into the traffic flowing across the network. The most used methods for traffic monitoring in the industry are those based on dedicated monitoring protocols as SNMP (Simple Network Management Protocol), NetFlow, SFlow, among others. With processing capacity evolution of forwarding devices, new techniques have been proposed. The use of sketches has become widely popular for traffic monitoring tasks. Sketches are compact data structures capable of summarizing and store information about the state of packets. Using sketches, it is possible to monitor a network traffic, understanding the path travelled by each packet and which devices were responsible for the packet forwarding. Analyzing traffic over the network is a challenge that changes the traditional monitoring approach. The current performance indicator metrics provided by network devices are not enough to analyze and create insights for the network traffic as a whole. We need a way to produce key performance indicators that can be correlated across different network devices on the same network. This new approach opens opportunities for researching and developing novel techniques to obtain a holistic network traffic visibility, to support decisions in traffic engineering, to detect traffic anomalies and other applications. Using a single sketch named BitMatrix, proposed in this work, it is possible to monitor network traffic, understand the path travelled per packet and which devices forwarded this packet along its path. In this context, this probabilistic structure was adopted to identify the path used to forward a packet in a multi-tenant network in two different scenarios: a) in an emulated network, using P4 routers and, b) in a simulated network, processing real traffic traces, using a Python framework. As a result, overloaded routers, links and paths and heavy user tenants were identified.