Processor Scheduler for Multi-Service Routers
- 1 December 2006
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2006 27th IEEE International Real-Time Systems Symposium (RTSS'06)
- p. 225-235
- https://doi.org/10.1109/rtss.2006.38
Abstract
In this paper, we describe the design and evaluation of a scheduler (referred to as Everest) for allocating processors to services in high performance, multi-service routers. A scheduler for such routers is required to maximize the number of packets processed within a given delay tolerance, while isolating the performance of services from each other. The design of such a scheduler is novel and challenging because of three domain-specific characteristics: (1) difficult-to-predict and high packet arrival rates, (2) small delay tolerances of packets, and (3) significant overheads for switching allocation of processors from one service to another. These characteristics require that the scheduler be agile and wary simultaneously. Whereas agility enables the scheduler to react quickly to fluctuations in packet arrival rates, wariness prevents the scheduler from wasting computational resources in unnecessary context switches. We demonstrate that by balancing agility and wariness, Everest, as compared to conventional schedulers, reduces by more than an order of magnitude the average delay and the percentage of packets that experience delays greater than their tolerance. We describe a prototype implementation of Everest on Intel's IXP2400 network processorKeywords
This publication has 22 references indexed in Scilit:
- Interposed proportional sharing for a storage service utilityPublished by Association for Computing Machinery (ACM) ,2004
- OverQoSACM SIGCOMM Computer Communication Review, 2003
- A proportional share resource allocation algorithm for real-time, time-shared systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Deadline fair scheduling: bridging the theory and practice of proportionate pair scheduling in multiprocessor systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Hierarchical CPU Scheduler for Multimedia Operating Systems**This research was supported in part by IBM Graduate Fellowship, IBM Faculty Development Award, Intel, the National Science Foundation (Research Initiation Award CCR-9409666), NASA Mitsubishi Electric Research Laboratories (MERL), and Sun Microsystems Inc.Published by Elsevier BV ,2002
- SEDAPublished by Association for Computing Machinery (ACM) ,2001
- SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networksPublished by Association for Computing Machinery (ACM) ,2001
- Network Address Translation - Protocol Translation (NAT-PT)Published by RFC Editor ,2000
- Efficient fair queueing algorithms for packet-switched networksIEEE/ACM Transactions on Networking, 1998
- Dynamic vs. static quantum-based parallel processor allocationPublished by Springer Science and Business Media LLC ,1996