QRP01-1: Optimal Routing of Dynamically Priced Network Services

We have previously proposed the use of dynamically priced network services to provide QoS guarantees within a network. End-to-end QoS can be achieved by concatenating several of these services from different ISPs. In this paper we consider the problem of a single ISP determining the optimal paths on which to route each service within its network, as well as the optimal bandwidth to allocate to each service, in order for the ISP to maximize its revenue. We assume that the ISP can estimate the demand functions for each service. We define three heuristics: service grouping, iterative bottleneck avoidance, and iterative bottleneck avoidance with tabu. We demonstrate that iterative bottleneck avoidance with tabu achieves approximately 98% of an optimal solution.