Guaranteeing Hard Real-Time Deadlines in FDDI Networks

分布式系统成功应用于硬实时应用的关键是及时执行计算任务，这些任务通常驻留在不同的节点上，并相互通信以实现共同的目标。如果没有支持及时传递任务间消息的通信网络，端到端的最后期限保证是不可能的。研究的重点是解决与保证同步消息截止期相关的问题，即无论发生什么情况(网络故障除外)，消息都将在其截止期之前发送。我们选择FDDI(光纤分布式数据接口)网络进行研究，因为它们非常适合硬实时通信，这不仅是因为它们的高带宽，而且因为它们具有有限的令牌轮换时间的特性。然而，仅有有限的令牌轮换时间不足以保证硬实时截止日期。同步容量分配对于实现这一性能目标同样至关重要。在本项目中，我们主要对保证消息截止期的同步容量分配进行设计和分析。该项目由四项相关任务组成：我们首先解决最优化问题。最优方案实现了最坏情况下的最高利用率，因此提供了保证一组同步消息的最佳机会。然后，研究了利用本地信息为节点分配同步容量的局部化分配方案。它们的优点是能够在一个节点上调整参数，而不会干扰其他节点的操作。接下来，我们将扩展我们的基本模型，以考虑实践中需要的变化。例如，有些申请不要求绝对的截止日期保证，即偶尔错过截止日期是可以接受的。我们在设计和分析分配方案时将这些思想形式化，以提高它们的适用性。TTRT(目标令牌轮换时间)的选择也影响到保证最后期限的机会；这是项目中的最后一项任务。

The key to the success in using a distributed system for hard real-time applications is the timely execution of computation tasks which usually reside on different nodes and communicate with one another to accomplish a common goal. End-to-end deadline guarantees are not possible without a communication network which supports the timely delivery of intertask messages. The main focus of the research is to address issues related to guaranteeing synchronous message deadlines, i.e., no matter what happens (except a network failure), the messages will be transmitted before their deadlines. We have selected FDDI (Fiber Distributed Data Interface) networks for this study because they are well suited for hard real-time communications, due not only to their high bandwidth, but also to their property of bounded token rotation time. However, a bounded token rotation time alone is not sufficient to guarantee hard real-time deadlines. Synchronous capacity allocation is equally critical in achieving this performance objective. In this project, we concentrate on design and analysis of synchronous capacity allocation to guarantee message deadlines. The project consists of four related tasks: We first address the issue of optimality. An optimal scheme achieves the highest worst case utilization and hence offers the best chance to guarantee a set of synchronous messages. Then, we study localized allocation schemes which use local information to allocate synchronous capacity to a node. They have the advantage of being able to adjust the parameters on one node without disturbing the operations of others. Next, we will extend our basic model to consider variations needed in practice. For example, some applications do not require an absolute deadline guarantee, i.e., occasionally missing a deadline is acceptable. We formalize these ideas in the design and analysis of allocations schemes in order to improve their applicability. Selection of TTRT (Target Token Rotation Time) also affects the chance of guaranteeing deadlines; this is addressed as the last task in the project.