Minimum underflow routing for stream-type communication services

The Internet of today supports various types of communication services including not only conventional data communication services but also stream-type communication services. Typical examples of stream-type services include interactive voice such as Voice over IP (VoIP) and live video delivery. Stream services require real-time packet transmission, and the continuous playback of packets at the receiver side. As a result, they are not only sensitive to the absolute value of the delay, but also sensitive to delay variations. This paper addresses the problem of optimal routing for stream-type communication services. Optimality is discussed in terms of the continuous playback of packets. From network observations, we assume that the end-to-end delay statistics conform to a normal distribution. We model a network as a weighted graph with its link weights representing link delays. In the course of the analysis, we show 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. This paper presents an efficient algorithm for finding the optimal point in this coordinate system.