| Today most scheduling algorithms in network research provide guarantees for bandwidth and loss rate. However, as broadband capabilities on wired, wireless and mobile phone networks proliferate, timing guarantee, which is the focus of the real-time research community, becomes a prominent issue. Applications such as videoconferencing are typically sensitive to timeliness. Earliest Deadline First (EDF) is the best-known dynamic real-time scheduling algorithm and is suitable for providing timing guarantees. Nevertheless, previous research has focused primarily on deterministic analysis of the worst case. This can result in a low utilization such as 5%. This thesis addresses the fundamental problems in providing timing guarantees to a real-time network with high utilization (over 90%). The key contributions of this thesis are: (1) A new theory for analyzing an EDF network where all flows are stochastic; (2) Simulation experiments to validate the theory; (3) Quantitative real-time network design principles and methodology; (4) Analyses and experiments that showed the performance loss when only a limited number of bits are enough for encoding the deadline (for example: ToS/DS field of IP packets) and when the flow table is not used; (5) A modified EDF scheme that provides different lateness guarantees to different flows; (6) The development of a software tool, RETINA---REal-TIme Network Analyzer, for real-time network analysis, design, and tradeoffs. These, for the first time, provided a strong foundation in both theory and application perspectives on using EDF to provide timing guarantee in a network with fully stochastic traffic. Performance analysis for sophisticated applications such as videoconferencing can be built on such a framework. |
