Data stream algorithms for scalable bandwidth management

We propose an efficient and scalable scheme for bandwidth reservation and monitoring. Our scheme is based on a reserve-and-refresh strategy [I. Stoica and Hui Zhang, 19994], [S. Machiraju et al., 2002], where each flow is periodically refreshed in its initial reservation. We propose novel algorithms to handle various forms of misbehavior, e.g., attempting to refresh more than what was reserved (control plane), exceeding reservations (data plane). Our solutions are based on data stream algorithms that are extremely efficient in terms of memory requirements and time required to process each packet. Specifically, we compute very short sketches of packet traffic with which we can provably guarantee that no more than a tiny fraction of the bandwidth is lost to misbehaving flows. Since our solutions are robust, incrementally deployable, and have very low time/space requirements, we believe they are ideally suited for supporting QoS, flow and congestion control, and more generally, for bandwidth management in active network architectures.