Traffic routing for multi-computer 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 on the traffic through the link. The form of this cost function is derived on the basis of the probability of establishing a virtual cut-through route. It is shown that this route selection problem is NP-hard, and so an approximate algorithm that tries to reduce the cost incrementally by rerouting traffic is developed. The performance of this algorithm is evaluated for two popular network topologies: the hypercube and the C-wrapped hexagonal mesh