Unrelenting traffic growth, device heterogeneity, and load unevenness create scalability challenges for traffic monitoring. In this paper, we propose Robust Distributed Computation (RoDiC), a new approach that addresses these challenges by shifting a portion of the monitoring-task execution from an overloaded network element to another element that has spare resources. Moving the entire execution of the task away from the overloaded element might be infeasible because execution on multiple elements is inherent in the task or requires at least partial participation by the designated overloaded element. Furthermore, distributed execution of a stateful task has to be resilient to network noise in the form of packet reordering and loss. The RoDiC approach relies on two main principles of packet grouping and state overlap to support exact robust distributed monitoring of traffic flows under network noise. RoDiC uses an open-loop paradigm that does not add any control packets, communicates flow state in-band by appending few control bits to packets of monitored flows, and keeps measurement latency low. We apply RoDiC to the problem of flow-size computation and discuss how to instantiate our general technique for real-time packet-loss telemetry. The paper develops robust algorithms, proves their correctness and performance properties, and reports an evaluation driven by realistic traffic traces. The RoDiC algorithms successfully distribute the monitoring-task load while keeping the memory and computation overhead low.

pub