| |
[摘要]：With the advent of powerful network processors (NPs) in the market, many computation-intensive tasks such as routing table lookup, classification, IPSec, and multimedia transcoding can now be accomplished more easily in a router. An NP consists of a number of on-chip processors to carry out packet level parallel processing operations. Ensuring good load balancing among the processors increases throughput. However, such multiprocessing also gives rise to increased out-of-order departure of processed packets. In this paper, we first propose an Ordered Round-Robin (ORR) scheme to schedule packets in a heterogeneous NP assuming that the workload is perfectly divisible. The processed loads from the processors are ordered perfectly. We analyze the throughput and derive expressions for the batch size, scheduling time, and maximum number of schedulable processors. To effectively schedule variable length packets in an NP, we propose a Packetized ORR (P-ORR) scheme by applying a combination of deficit round-robin (DRR) and surplus round-robin (SRR) schemes. We extend the algorithm to handle multiple flows based on a fair scheduling of flows depending on their reservations. Extensive sensitivity results are provided through analysis and simulation to show that the proposed algorithms satisfy both the load balancing and in-order requirements for parallel packet processing. |
|
