Traffic Routing for Multicomputer Networks with Virtual Cut-Through Capability

Abstract

A point-to-point interconnection network can be a good choice for use in distributed real-time systems, since it can provide multiple disjoint paths between nodes to tolerate link and node failures. The major drawback of this type of network has been that full connectivity becomes prohibitively expensive as the number of nodes increases, and partial connectivity implies long store-and-forward delays in the prevalent packet-switching mode of operation. However, this drawback of partially connected point-to-point networks can now be overcome with virtual cut-through, a scheme which is feasible to implement using current VLSI technology. This paper addresses the problem of selecting routes for interprocess communication in a network with virtual cut-through capability, while balancing the network load and minimizing the number of times that a message gets buffered. The problem is important because the message delivery delay depends upon the number of times that a message gets buffered at intermediate nodes on the route. The approach taken here is to formulate the route selection problem as a minimization problem, with a link cost function that depends upon the traffic through the link. The form of this cost function is derived based on the probability of establishing a virtual cut-through route. It is shown that this route selection problem is NP-Hard, so an approximate algorithm is developed which tries to incrementally reduce the cost by re-routing traffic. The performance of this algorithm is evaluated for two popular network topologies: the hypercube and the C-wrapped hexagonal mesh—example networks for which virtual cut-through switching support has been developed. © 1992 IEEE