Title: System-level timing analysis and scheduling for embedded packet processors
Abstract: Packet processors are high-performance, programmable devices with special architectural features that are optimized for network packet processing. They are mostly embedded within network routers and switches and are designed to implement complex packet processing tasks at high line speeds. In this thesis we study several issues related to system-level timing analysis and scheduling for such embedded packet processors. Our work is motivated by the fact that designing and analysing the hardware-software architectures for packet processors require new models and methods which do not fall within the preview of traditionally studied embedded systems. Both, timing analysis and scheduling have been widely studied in the context of system-level design of embedded systems. But most of these studies have either focussed on purely data-dominated applications like digital signal and image processing, or on purely control-dominated applications such as those found in automobile control systems or in appliances like washing machines and microwave ovens. Packet-processing applications, on the other hand, combine features from both these domains and additionally have several new characteristics and requirements. Their design also requires an integration of concepts from several areas, such as embedded systems, computer architecture and networking. As a result, the design and analysis of packet processors are not sufficiently supported by current high-level design methodologies and tools targeted towards embedded-systems design. This thesis partially fills this gap by proposing new models and algorithms specifically directed towards designing network packet processors, and makes the following main contributions. Packet processors typically consist of a collection of heterogeneous processing elements, which are required to process multiple packet flows at line speed. We pose the problem of determining the feasibility of a mapping of the different packet-processing tasks onto the different processing elements, as a schedulability analysis problem. It turns out that for the task model we consider, this schedulability analysis problem is intractable (NP-hard) and therefore can not be solved within any reasonable time. To get around this, we introduce a novel concept called “approximate schedulability analysis”, using which the problem can be solved in polynomial time if a small error in the decisions made by the algorithm is allowed. Using this concept, we demonstrate that in spite of the intractability result, a schedulability analysis can nevertheless be done in reasonable time for all practical purposes. We also show that this concept is not
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: dissertation
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot