Scheduling Processing Resources in Programmable Routers

Title: Scheduling Processing Resources in Programmable Routers

Authors: Prashanth Pappu and Tilman Wolf

Abstract: To provide flexibility in deploying new protocols and services, general-purpose processing engines are being placed in the datapath of routers. Such network processors are typically simple RISC multiprocessors that perform forwarding and custom application processing of packets. The inherent unpredictability of execution time of arbitrary instruction code poses a significant challenge in providing QoS guarantees for data flows that compete for such processing resources in the network. However, we show that network processing workloads are highly regular and predictable. Using estimates of execution times of various applications on packets of given lengths, we provide a method for admission control and QoS scheduling of processing resources. We present a processor scheduling algorithm called Estimation-based Fair Queuing (EFQ) which uses these estimates and provides significantly better delay guarantees than processor scheduling algorithms which do not take packet execution times into consideration.

Published: Prashanth Pappu and Tilman Wolf, "Scheduling processing resources in programmable routers," in Proc. of the Twenty-First IEEE Conference on Computer Communications (INFOCOM), Hong Kong, Mar. 2002, pp. 104-112.

Download: PDF

BibTeX:
@inproceedings{Pappu:SPR02,
   author       = {Pappu, Prashanth and Wolf, Tilman},
   title        = {Scheduling Processing Resources in Programmable Routers},
   booktitle    = {Proc. of the Twenty-First IEEE Conference on Computer Communications (INFOCOM)},
   year         = 2002,
   month        = jun,
   address      = {New York, NY},
   pages        = {104--112}
}

Copyright: © 2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.