Systems and methods for two-rate scheduling over a class hierarchy wherein controlled rates are delivered in a smooth manner, even over short time intervals. A minimum rate scheduler and an excess rate scheduler are employed. The minimum rate scheduler and/or the excess rate scheduler, employ special binary search trees to make selections at each parent node in the class hierarchy.