Existing Internet traffic classification techniques achieve impressively low misclassification rates, but do not provide performance guarantees for particular classes of interest. In this paper, we propose two novel online traffic classifiers - one based on Neyman-Pearson classification and one based on the Learning Satisfiability (LSAT) framework - that can provide class-specific performance guarantees on the false alarm and false discovery rates, respectively. We also present a preprocessor for our classifiers that predicts, after the reception of only a small number of packets, whether a flow will be 'large' (as defined by a network operator). Only these resource-intensive flows are passed to the classifier, greatly reducing the computation burden imposed. We validate our methodology by testing our approaches using traffic data provided by an ISP.