Date Added: Jan 2012
An Origin-Destination (OD) flow between two routers is the set of packets that pass both routers in a network. Measuring the sizes of OD flows is important to many network management applications such as capacity planning, traffic engineering, anomaly detection, and network reliability analysis. Measurement efficiency and accuracy are two main technical challenges. In terms of efficiency, the authors want to minimize per-packet processing overhead to accommodate future routers that have extremely high packet rates. In terms of accuracy, they want to generate precise measurement results with small bias and standard deviation. To meet these challenges, they design a new measurement method that employs a compact data structure for packet information storage and uses a novel statistical inference approach for OD-flow size estimation.