CAM04-3: Optimal Routing Between Alternate Paths With Different Network Transit Delays

We consider the path-determination problem in Internet core routers that distribute flows across alternate paths leading to the same destination. We assume that the remainder of the network transit delay beyond this router are different for the two paths, so a good routing policy can reduce the end-to-end delay by favoring the faster path. Thus, we propose and solve the optimal path-determination problem for a router, which minimizes the average network transit delay for a flow by dynamically assigning each packet to one of the available output ports based on their respective instantaneous queue lengths and on the average network transit delay for the associated path. We assume that all outgoing link speeds at the router are equal, but we generalize the model to allow each output port to serve a link group (such as an optical fiber using WDM) that consists of multiple physical channels running in parallel. By formulating path-selection as a Markov Decision Problem, we show that the optimal algorithm is a threshold-type policy that we call JSQ + b.