HARTS: A Distributed Real-Time Architecture

Reviewer: Jason Gait

Real-time systems may be tightly coupled to operational problems that are precisely characterized by hard timing constraints, requirements for reliability, and bounded sets of environmental demands. Each problem is constrained differently, hence each leads to a distinct real-time system. It follows that real-time systems are big business: it is hard to reuse old systems for new problems. Real-time systems may also be coupled to a hardware base that maintains and controls the environmental variables; this base is often a distributed computer connected point-to-point. This paper studies a candidate architecture for a distributed computer based on a wrapped hexagonal network. The simplest wrapped hexagonal mesh can be visualized as a hexagonal network with nodes at the vertices and enough extra connections to connect each node to every other node. The advantage is that the routing algorithm is independent of the size of the network. The author compares virtual cut-through and wormhole routing policies in wrapped hexagonal networks. Wormhole routing works by acquiring and keeping resources as messages move through the network, while virtual cut-through releases resources that are no longer needed. Wormhole routing sacrifices latency for guaranteed delivery, so it is useful for short-distance transmissions during periods of low traffic. Virtual cut-through sacrifices delivery guarantees for latency, so it is useful for long-distance transmissions during periods of heavy traffic. In a wrapped hexagonal mesh little distinguishes the two in terms of latency when traffic is low, but virtual cut-through performs better when traffic is heavy. The HARTS system dynamically switches between the two policies. (In fact, the routing algorithm is a real- time system with negative feedback that acts to dampen network congestion.) The HARTS routing algorithm manages faulty links well, with unreachable nodes revealed by cycling messages. It is possible to have false alarm cycles, however, in which the node is actually reachable but the algorithm cannot get there.