Optimal virtual circuit routing in computer networks

Routing for virtual circuit mode services has been identified as a multicommodity network flow problem, and proves to be at least as hard as NP-complete problems. This paper proposes two approaches to this problem. The first is simulated annealing which is known to be time-consuming but suitable to probe the global optimum of combinatorial problems. An annealing method might not be practical to implement routing functions, but it can serve as a way to examine to what degree a routing algorithm can approach the global optimum. The other approach is the flow deviation (FD) method, which can be dated to as early as 1973. However, a new optimal metric is used to steer flow deviation. The metric is simple to calculate but proves to be sufficient for a solution to be a local minimum. With this metric, the FD approach is compared to the annealing method, and previous results found in the literature are also contrasted. Using benchmark test examples, it is shown that numerical experiments of both methods on various networks give satisfactory solutions.<>