Towards scalable traffic measurements in high-speed networks

Resumo

Passive measurements are needed to understand how traffic flows across high speed packet-switched networks like the Internet to diagnose and troubleshoot network problems and to engineer and optimize network usage. Within passive measurements, the per-flow approach is an attractive paradigm that allows to trade off detail for volume of measurement data. However, increases in transmission speeds, constraints in memory technology and the huge number of flows that can concurrently share high-speed Internet links pose several scalability issues and make the collection of measurements at the flow level challenging nowadays. In the past, the problem of updating counters in memory per packet has been solved through sampling techniques. The scalability issue of keeping state for thousands of flows, by concentrating on the measurement of the largest flows; those potentially having the greatest impact on traffic dynamics and being of most interest from a traffic engineering point of view. Unfortunately, existing sampled-based flow-level measurement techniques are lightweight and flexible but inaccurate, whereas the techniques known to identify large flows are memory-efficient and accurate, but heavyweight and much less scalable in speed as they require the inspection of each packet, memory operations per packet or frequently processing their data structures so as to keep their memory requirements low. The central aim of this thesis is the proposal and study of flow-level measurement solutions that are both accurate and scalable. To this end, four algorithms to identify and measure large flows are presented. The most salient feature of the schemes proposed is that they scale well in both space and speed. The algorithms obey common principles and are presented in an incremental fashion; much in the order they were conceived when addressing the distinct issues that appeared in each. The performance of the algorithms is compared to prior approaches theoretically and empirically, and several implications of the approaches in terms of implementability are discussed. The last algorithms proposed probably constitute the most scalable solutions to the general problem of identifying frequent items and the most attractive solutions to detecting and measuring large flows at high speeds for their flexibility, guaranteed performance, robustness, cost of implementation and ease of use.