State aggregation of large network domains

Many important network functions (e.g., QoS provision, admission control, traffic engineering, resource management) rely on the availability and the accuracy of network state information. It is impractical to maintain the complete state information of a large internetwork at a single location. Large networks are often hierarchically structured, with each domain advertising its aggregated state. To achieve scalability, a delicate tradeoff has to be made between minimizing the size and maximizing the accuracy of the aggregated state. Given certain space limitation, inaccuracy introduced by different aggregation methods varies greatly. This paper gives a unified account of state aggregation based on approximation curves. The existing aggregation methods are special cases in the solution space under this model. New aggregation methods based on polynomial curves, cubic splines, and polylines are proposed, and their accuracy/space tradeoffs are studied. Extensive simulations show that these new methods approximate the network state far more accurately than the existing ones. In particular, the polylines achieve the best accuracy/space tradeoff.