Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Scalable and Robust Solution for Bandwidth Allocation

Sridhar Machiraju, Mukund Seshadri and Ion Stoica

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-02-1176
2002

http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1176.pdf

We propose a novel architecture for providing bandwidth allocation and reservation that is both scalable and robust. Scalability is achieved by not requiring routers to maintain per-flow state on either the data or control planes. To achieve robustness, we develop two key techniques. First, we use an admission control mechanism based on lightweight certificates and random sampling to prevent malicious users from claiming reservations that were never allocated to them. Second, we use a recursive monitoring algorithm to detect misbehaving flows that exceed their reservations. We randomly divide the traffic into large aggregates, and then compare the data arrival rate of each aggregate to its reservation. If an aggregate misbehaves, i.e., its arrival rate is greater than its reservation, we split and monitor that aggregate recursively until we detect the misbehaving flow(s). These misbehaving flows are then policed separately. We conduct extensive simulations to evaluate our solutions. The results show that the proposed solution is very effective in protecting well-behaved flows when the fraction of misbehaving flows is limited.


BibTeX citation:

@techreport{Machiraju:CSD-02-1176,
    Author = {Machiraju, Sridhar and Seshadri, Mukund and Stoica, Ion},
    Title = {A Scalable and Robust Solution for Bandwidth Allocation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2002},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5661.html},
    Number = {UCB/CSD-02-1176},
    Abstract = {We propose a novel architecture for providing bandwidth allocation and reservation that is both scalable and robust. Scalability is achieved by not requiring routers to maintain per-flow state on either the data or control planes. To achieve robustness, we develop two key techniques. First, we use an admission control mechanism based on lightweight certificates and random sampling to prevent malicious users from claiming reservations that were never allocated to them. Second, we use a recursive monitoring algorithm to detect misbehaving flows that exceed their reservations. We randomly divide the traffic into large aggregates, and then compare the data arrival rate of each aggregate to its reservation. If an aggregate misbehaves, i.e., its arrival rate is greater than its reservation, we split and monitor that aggregate recursively until we detect the misbehaving flow(s). These misbehaving flows are then policed separately. We conduct extensive simulations to evaluate our solutions. The results show that the proposed solution is very effective in protecting well-behaved flows when the fraction of misbehaving flows is limited.}
}

EndNote citation:

%0 Report
%A Machiraju, Sridhar
%A Seshadri, Mukund
%A Stoica, Ion
%T A Scalable and Robust Solution for Bandwidth Allocation
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1176
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5661.html
%F Machiraju:CSD-02-1176