A fast and robust scheme that classifies Internet packets according to their application types is proposed in this work. The scheme is deployed at ISP for QoS provisioning, scalability and reliability. The proposed classification scheme consists of two steps: feature selection and classification. For feature selection, practical features are extracted using the modified multistage filter. By using the genetic algorithm (GA) and a variant of the wrapper method, we obtain two sets of features for comparison. As to classifiers, decision trees such as J48 and REPTree. The decision trees are trained with selected features from real traffics. The trained decision trees are compared with a classifier using the NBKE approach in terms of accuracy and robustness. It is demonstrated by simulation results that decision trees with features selected by GA gives the best performance. Finally, early classification with modified multistage filters is proposed to reduce collision errors for fast and robust performance.