Full Text:   <1263>

CLC number: TP393

On-line Access: 


Revision Accepted: 2004-02-23

Crosschecked: 0000-00-00

Cited: 3

Clicked: 3145

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2004 Vol.5 No.7 P.816~826


An integrated DBP for streams with (m,k)-firm real-time guarantee

Author(s):  WANG Zhi, CHEN Ji-ming, SUN You-xian

Affiliation(s):  National Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   wangzhi@iipc.zju.edu.cn

Key Words:  (m, k)-firm, Weakly hard real-time, Real-time schedule, DBP, Quality of service

Share this article to: More

WANG Zhi, CHEN Ji-ming, SUN You-xian. An integrated DBP for streams with (m,k)-firm real-time guarantee[J]. Journal of Zhejiang University Science A, 2004, 5(7): 816~826.

@article{title="An integrated DBP for streams with (m,k)-firm real-time guarantee",
author="WANG Zhi, CHEN Ji-ming, SUN You-xian",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T An integrated DBP for streams with (m,k)-firm real-time guarantee
%A CHEN Ji-ming
%A SUN You-xian
%J Journal of Zhejiang University SCIENCE A
%V 5
%N 7
%P 816~826
%@ 1869-1951
%D 2004
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2004.0816

T1 - An integrated DBP for streams with (m,k)-firm real-time guarantee
A1 - WANG Zhi
A1 - CHEN Ji-ming
A1 - SUN You-xian
J0 - Journal of Zhejiang University Science A
VL - 5
IS - 7
SP - 816
EP - 826
%@ 1869-1951
Y1 - 2004
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2004.0816

(m, k)-firm real-time or weakly hard real-time (WHRT) guarantee is becoming attractive as it closes the gap between hard and soft (or probabilistic) real-time guarantee, and enables finer granularity of real-time QoS through adjusting m and k. For multiple streams with (m, k)-firm constraint sharing a single server, an on-line priority assignment policy based on the most recent k-length history of each stream called distance based priority (DBP) has been proposed to assign priority. In case of priority equality among these head-of-queue instances, Earliest Deadline First (EDF) is used. Under the context of WHRT schedule theory, DBP is the most popular, gets much attention and has many applications due to its straightforward priority assignment policy and easy implementation. However, DBP combined with EDF cannot always provide good performance, mainly because the initial DBP does not underline the rich information on deadline met/missed distribution, specially streams in various failure states which will travel different distances to restore success states. Considering how to effectively restore the success state of each individual stream from a failure state, an integrated DBP utilizing deadline met/missed distribution is proposed in this paper. Simulation results validated the performance improvement of this proposal.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Atiquzzaman, M., Hassan, M., 2001. Guest editorial: Adaptive real-time multimedia transmission over packet switching networks.Real-Time Imaging,7(3):219-220.

[2] Bernat, G., Burns, A., 2001. Weakly hard real-time systems.IEEE Transactions on Computers,50(4):308-321.

[3] Bernat, G., Cayssials, R., 2001. Guaranteed On-Line weakly Hard Real-Time Systems. Proceedings of IEEE Conference on Real-Time Systems, p.25-35.

[4] Giorgio, C.B., 1997. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Application. Kluwer Academic Publisher.

[5] Chou, C.C., Shin, K.G., 1997. Statistical real-time channels on multi-access bus networks.IEEE Transaction on Parallel and Distributed Systems,7(8):769-780.

[6] Cruz, R.L., 1991. A calculus for network delay, Part I.IEEE Transactions on Information Theory,37(1):114-131.

[7] Hamdaoui, M., Ramanathan, P., 1995. A dynamic priority assignment technique for streams with (m,k)-firm deadlines.IEEE Transactions on Computers,44(4):1443-1451.

[8] Hamdaoui, M., Ramanathan, P., 1997. Evaluating dynamic failure probability for streams with (m,k)-firm deadline.IEEE Transactions on Computers,46(12):1325-1337.

[9] Koren, G., Shasha, D., 1995. Skip-over: Algorithms and Complexity for Overloaded Systems that Allow Skips. Proceedings of Real-Time Systems Symposium, p.110-117.

[10] Kuo, T.W., Mok, A.K., 1991. Load Adjustment in Adaptive Real-time. Proceedings of 12th IEEE Real-Time System Symposium, p.160-170.

[11] Lee, C., Rajkumar, R., Mercer, C., 1996. Experiences with Processor Reservation and Dynamic QoS in Real-Time. Proceedings of Multimedia.

[12] Lehoczky, J.P., 1990. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines. Proceedings of IEEE Real-Time Systems Symposium, p.201-209.

[13] Lindsay, W., Ramanathan, P., 1997. DBP-M, A Technique for Meeting End-to-end (m,k)-Firm Guarantee Requirements in Point-to-point Networks. Proceedings ofIEEE Conference on Local Networks, p.294-303.

[14] Nagarajan, R., Kurose, J., Towsley. D., 1994. Finite-horizon statistical quality of service measure for high-speed networks.Journal of High Speed Network,3(4):351-373.

[15] Nakajima, T., 1998. Resource Reservation for Adaptive QoS Mapping in Real-time Mach. Proceedings of 6th International Workshop on Parallel and Distributed Real-time System.

[16] Poggi, E.M., Song, Y.Q., Kouba. A., Wang, Z., 2003. Matrix-DBP for (m,k)-firm Real-time Guarantee. Proceedings of Real-Time and Embedded System, Paris, France, p.457-482.

[17] Quan, G., Hu, X., 2000. Enhanced Fixed-priority Scheduling with (m,k)-firm Guarantee. Proceedings of IEEE Real-Time Systems Symposium, p.79-88.

[18] Ramamritham, K., 1996. Where do time constraints come from and where do they goInternational Journal of Database Management,7(2):4-10.

[19] Ramanathan, P., 1999. Overload management in real-time control applications using (m,k)-firm guarantee.IEEE Transactions on Parallel and Distributed Systems,10(6):549-559.

[20] Rom, R., Sidi, M., 1990. Multiple Access Protocols Performance and Analysis. Springer-Verlag, New York.

[21] Song, Y.Q., Kouba, A., Simonot, F., 2002. Switched Ethernet for Real-time Industrial Communication: Modelling and Message Buffering Delay Evaluation. Proceedings of 4th IEEE WFCS, p.27-30.

[22] Song, Y.Q., 2003. Gestion Dynamique de la QdS Temps-réel Selon (m,k)-firm. Report in Ecole Temps Réel, Toulouse, France, ETR'03.

[23] Striegel, A., Manimaran, G., 2000. Best-effort scheduling of (m,k)-firm real-time streams in multihop networks.Computer Communications,23(13):1292-1300.

[24] Striegel, A., Manimaran, G., 2002. Packet scheduling with delay and loss differentiation.Computer Communications,25(1):21-31.

[25] Striegel, A., Manimaran, G., 2003. Dynamic class-based queue banagement for scalable media servers.Journal of Systems & Software,66:119-128.

[26] Takagi, H., 1990. Queuing Analysis of Polling System: An Update in Stochastic Analysis of Computer and Communication System. Elsevier Science North Holland, Amsterdam, p.267-318.

[27] Wang, Z., Song, Y.Q., Poggi, E.M., Sun, Y.X., 2002. Survey of Weakly Hard Real-time Schedule Theory and its Application. Proceedings of International Symposium on Distributed Computing and Applications to Business, Engineering and Science, p.429-437.

[28] West, R., Schwan, K., Poellabauer, C., 1999. Scalable Scheduling Support for Loss and Delay Constrained Media Streams.Proceedings of IEEE Real-Time Technology and Applications Symposium.

[29] West, R., Poellabauer, C., 2000. Analysis of A Window-constrained Scheduler for Real-time and Best-effort Packet streams.Proceeding of 21st IEEE Real-Time Systems.

[30] Zhang, Z.L., Nelakuditi, S., Aggarwal, R., Tsang, R.P., 2001. Efficient selective frame discard algorithms for stored video delivery across resource constrained networks.Real-Time Imaging,7(3):255-273.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE