Research Outputs
A streaming algorithm and hardware accelerator to estimate the empirical entropy of network flows
The empirical entropy is used in network traffic monitoring and classification to detect anomalous events and manage network resources. Computing the entropy of high-speed traffic in real time requires dedicated hardware, such as programmable switches and FPGA-based accelerators. While these devices can achieve high performance by exploiting the parallelism of the algorithm, they possess limited on-chip storage. Thus, designing algorithms that estimate the entropy of network traffic with low error and memory usage is challenging. In this paper, we present an entropy-estimation streaming algorithm that operates on large datasets with sublinear memory usage. We use sketches to estimate the frequency and cardinality of network flows during an observation interval. We only store the frequencies of the most frequent flows and use them to estimate the rest of the frequencies by assuming a power-law distribution. Our results show that, using real network traces with observation intervals of up to 50 million flows, we can estimate their empirical entropy with 0.69% mean relative error, using more than three orders of magnitude less memory than an exact entropy-computation method. We also present an FPGA-based hardware accelerator for the algorithm that can operate at a line rate of more than 200 Gbps and an estimation latency of 16 μs. Using fixed-point arithmetic and function approximations in the accelerator increases the mean estimation error of our algorithm by only 0.07%.
Guaranteeing network reliability to 0-day exploits using Cost-Effective heterogeneous node migration
Network reliability has become an important concern to network administrators and service providers, and is prominently considered in network design. Particularly, 0-day vulnerabilities are an increasing threat to software-based networking systems. When shared between node appliances, they can be exploited simultaneously and compromise large portions of the network. Moreover, it has been observed that the number of 0-day vulnerabilities discovered yearly in node appliances tends to increase over time. Thus, we can expect that the reliability to 0-day exploits of a network implemented with these appliances will also worsen over time. In this work, we treat network reliability to 0-day exploits as a service, where he network provider agrees to deliver a reliability-based level of service over time. We propose a network reliability metric based on network connectivity and discovered appliance vulnerabilities. We formulate a strategy to guarantee a reliability value over time, based on heterogeneous networking and periodically running cost-effective partial node migrations. We use numerical evaluations to test our methodology on two software-defined wide-area networks based on known backbone IP topologies. Our significant findings are the following: First, when the network reliability becomes worse than the service guarantee, it can be restored in most cases by combining appliance reallocation and node migration. Second, our evaluations show a direct relationship between a network reliability value and the cost incurred to guarantee it. Third, we noted that, when using our appliance-to-node allocation strategy to guarantee the same reliability on different networks, their post-failure connectivity depends on the underlying network topology.