Minimizing Path Delay in Multipath Networks

One of the most important problems in the field of performance optimization for data networks is the problem of routing to achieve delay minimization. This becomes extremely important in the context of providing Quality of Service while satisfying demand. The problem is classical and was considered three decades ago by a number of authors primarily Gallagher, Bertsekas and Garcia-Luna-Aceves. The models attempt to find multiple flow paths to satisfy demands while minimizing the total delay in the network. Over the years it has become clear that in order to reduce congestion, a multipath approach to routing is needed. Moreover to provide explicit guarantee on QoS the routing needs to provide explicit delay bounds on each flow path. In fact the emergence of voice and video services has highlighted the need for explicit delay bounds. In this paper we propose an iterative algorithm that minimizes the maximum delay for individual flows while meeting demand requirements for multiple source-sink pairs. We assume that the delay on links is a convex function of the demand. We also propose to minimize the gap between the maximum and minimum delay paths so that the buffer required at the destination will be small.