A Two-Competitive Approximate Schedulability Analysis of CAN
Ref: HURRAY-TR-070625 Publication Date: 25 to 28, Sep, 2007
A Two-Competitive Approximate Schedulability Analysis of CAN
Ref: HURRAY-TR-070625 Publication Date: 25 to 28, Sep, 2007Abstract:
Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.
Björn Andersson
Nuno Pereira
Eduardo TovarDocument:
View
Download12th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA'07), IEEE, pp 1400-1403.
Patras, Greece.
DOI:10.1109/EFTA.2007.4416947.
WOS ID: 000254117100202.
Record Date: 1, May, 2007