DISTRIBUTED ROUTING WITH ONLINE MARGINAL DELAY ESTIMATION

Most optimal routing algorithms for packet-switched networks require information about the sensitivity of the performance measure with respect to link flows. This information is generally difficult to obtain for real-time applications, due to the absence of closed-form expressions for performance as a function of flows; in most interesting cases, standard assumptions (exponentially distributed packet lengths, Poisson arrival processes) do not hold. In this paper, we present a procedure for estimating on-line marginal packet delays through links with respect to link flows without making such assumptions, based on a technique known as perturbation analysis (PA). No knowledge of network parameters is required (arrival rates, link capacities). This is used in the context of a minimum delay distributed routing algorithm for real-time implementation. Experimental results are included investigating the effect of the algorithm step-size and observation period parameters, demonstrate the adaptivity of the approach and compare it to well-known analytical approximations. © 1990, IEEE.