Flow-level traffic measurement is important for network traffic accounting, traffic engineering,
and network security. However, flow-level measurement in high speed networks poses great challenges due
to the requirements of high packet processing speed and large memory size (high time/space complexity). To
reduce these demanding requirements, sampling is usually used and samplers are deployed in the network.
But sampling incurs information loss. To address this issue, this paper studies the tradeoff between sampling
loss and complexity in distributed sampling system. We formulate the distributed sampling problem as a
constrained optimization problem; specifically, maximizing the measurement coverage (i.e., the percentage
of sampled traffic among the total traffic) and minimizing the complexity/budget. Considering the stochastic
nature of traffic flows, we further formulate the optimization problem under two stochastic criteria:
Stochastic Expected Value Optimization criterion (which is concerned with average performance) and
Stochastic Chance Constrained Optimization criterion (which is concerned with the distribution of
performance measure). Then we propose a Hybrid Intelligent algorithm to decide the optimal deployment
strategy for monitors’ placement and the sampling rate at each monitor. Equipped with the proposed
algorithm, we are able to address the optimal tradeoff between measurement coverage and deployment cost
for networks with random traffic, which has not been studied before. The extensive simulations and
experiments demonstrate the effectiveness of our models and algorithm: with careful deployment, monitoring
over a small fraction of nodes in a high speed network is sufficient to maintain a high level of measurement
coverage.
