Project Overview

Network processors are typically embedded multiprocessor systems and pose an interesting scheduling problem. Packets in queue memory need to be assigned to a processor for processing. Considerations for determining a schedule are:

• Fair sharing of processing resources between different flows.
• Maximum usage (utilization, efficiency) of processing resources.

One key observation for this scheduling problem is that traditional scheduling schemes (which have been studied intensely) have only limited application. Bandwidth scheduling algorithms rely on the knowledge of the length of the available packets. With the link bandwidth, the time that a packet uses the interface can easily be determined and a fair schedule can be computed. On network processors, however, the processing time of an arbitrary set of instructions cannot be determined in advance. Also, process scheduling as it is done in operating systems, has limited application, since context switching is an expensive operation relative to the short processing time of packets.

We have shown that processing times of packets are highly regular and therefore predictable for some applications. Using processing time estimation, a good schedule can be determined. The actual processing time can be fed back to the scheduler after processing to correct any incorrect predictions. Based on these ideas, we have developed two scheduling schemes:

• Locality-Aware Predictive scheduling (LAP), which maximizes the reuse of data in the instruction cache, by scheduling packets (from different flows) that require the same application to the same processor.
• Estimation-based Fair Queuing (EFQ), which guarantees fair sharing of processing resources based on processing time estimation.

Both algorithms assume that the entire packet processing application is executed on a single processor core. We are currently expanding our prior work to schedule application subtasks onto embedded multiprocessors in the mapping project.

Publications

• Tilman Wolf, Prashanth Pappu, and Mark A. Franklin, “Predictive scheduling of network processors,” Computer Networks, vol. 41, no. 5, pp. 601–621, Apr. 2003.
• Prashanth Pappu and Tilman Wolf, “Scheduling processing resources in programmable routers,” in Proc. of the Twenty-First IEEE Conference on Computer Communications (INFOCOM), New York, NY, June 2002, pp. 104–112.
• Tilman Wolf and Mark A. Franklin, “Locality-aware predictive scheduling for network processors,” in Proc. of IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Tucson, AZ, Nov. 2001, pp. 152–159.

For a complete list of NSL publications, see the publications page.