loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00)
Minimizing the maximum end-to-end delay on tree structure using the distributed pinwheel model
Cheju Island, South Korea
December 12-December 14
ISBN: 0-7695-0930-4
Yu-Sheng Huang, Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan
Chih-Wen Hsueh, Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan
Distributed real-time systems often have some end-to-end timing requirements. Minimizing the maximum end-to-end delay is one of the most important timing constraints we would like to guarantee for quality of services. The network topology of many distributed systems on Internet is often a tree structure. In this paper, we extend our research on distributed pinwheel scheduling from pipeline structure to tree structure for minimizing the maximum end-to-end delay. We derive a tight maximum delay bound between two nodes and a linear-time algorithm to find the minimax delay between two nodes. With this bound and algorithm, it is easier and faster to schedule distributed real-time tasks with distance constraints and minimize the maximum end-to-end delay. Since the general scheduling problem is very difficult (NP-hard), we derive a more efficient heuristic algorithm than previous researches to minimize the maximum end-to-end delay. We also compare the simulation results of our heuristic and previous researches. The distributed pinwheel scheduling model can be used for distance-constrained real-time tasks on tree structure to reduce a lot of the maximum end-to-end delay and provide a predictable result.
Index Terms:
quality of service; timing; processor scheduling; computer networks; Internet; heuristic programming; computational complexity; maximum end-to-end delay minimisation; tree structure; distributed pinwheel model; distributed real-time systems; end-to-end timing requirements; timing constraints; pipeline structure; tight maximum delay bound; linear-time algorithm; heuristic algorithm; simulation result; NP-hard problems
Citation:
Yu-Sheng Huang, Chih-Wen Hsueh, "Minimizing the maximum end-to-end delay on tree structure using the distributed pinwheel model," rtcsa, pp.127, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000
Usage of this product signifies your acceptance of the Terms of Use.