Minimizing the Maximum End-to-End Delay on Tree Structure Using the Distributed Pinwheel Model
Resource
Real-Time Computing Systems and Applications, 2000. Proceedings. Seventh International Conference on, 127-134
Journal
Seventh International Conference on Real-Time Computing Systems and Applications
Pages
127-134
Date Issued
2000
Date
2000
Author(s)
Huang, Yu-Sheng
Abstract
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.
SDGs
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
14.pdf
Size
23.22 KB
Format
Adobe PDF
Checksum
(MD5):0cbbc32c8481e19fbd4eec2413904d38