An apparatus that recursively classifies packets includes a hierarchical set of classification engines that perform parallel classification of the packets in a packet processing queue. In particular, a first classification engine separates the packets based on physical-layer information and/or link-layer information in the packets. Then, second classification engines further separate the packets into multiple parallel pipelines based on layer information in the packets that is other than the physical-layer information and the link-layer information. The first classification engine and the second classification engines maintain a relative ordering of the packets in network sub-flows while allowing changes in relative ordering among different network flows.