A network anomaly detector evaluates two complementary measurements of network statistics, a time variation and correlation among those statistics, to provide an extremely robust detection of network anomalies. In one embodiment, the variability and correspondence are compared against historically derived thresholds to provide for a system that accommodates to local network conditions and evolving network qualities.