Optimal routing in communication networks with delay variations

The authors address the problem of optimal routing in packet switched networks. Optimality is discussed in terms of end-to-end delay. The variance of delay as well as its mean value are taken into account. Achieving optimal routing is necessary for multimedia networks to fully support real-time services. A network is modeled as a weighted graph with its link weights representing link delays. It is assumed that the delay statistics conform to a normal distribution. In the course of analysis, it is shown that this type of routing optimization problem can be formulated as a process of searching for a specific point in a coordinate system defined by the mean and variance of the end-to-end delay. An efficient algorithm is presented for finding the optimal point in this coordinate system