Traffic routing for multicomputer networks with virtual cut-through capability

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 is addressed. The approach taken 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, and an approximate algorithm is developed which tries to incrementally reduce the cost by rerouting traffic. The performance of this algorithm is evaluated for the hypercube and the C-wrapped hexagonal mesh, example networks for which virtual cut-through switching support has been developed