Optimal Routing of Dynamically Priced Network Services

Overview

The use of dynamically priced network services was previously proposed to provide QoS guarantees within a network. End-to-end QoS can be achieved by concatenating several of these services from different ISPs. This paper considers 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. It is assumed that the ISP can estimate the demand functions for each service. Three heuristics are defined: Service Grouping, Iterative Bottleneck Avoidance, and Iterative Bottleneck Avoidance with Tabu. The paper demonstrates that Iterative Bottleneck Avoidance with Tabu achieves approximately 98% of an optimal solution.