Optimal Distributed Routing for Virtual Line-Switched Data Networks

An algorithm that provides minimum delay routing in a data communication network using virtual line-switching is presented. The algorithm uses distributed computation in the sense that the nodes of the network update their information in an orderly fashion based on messages received from their neighbors. Receipt of these messages also triggers the various steps of the update and rerouting, so that these operations are performed in appropriate sequencing. For stationary input requirements and fixed topology the algorithm reduces network delay at each step and provides loop-free routing in the network. The method also provides an algorithm for quasi-static routing, when the input flows are slowly changing.