Efficient QoS partition and routing of unicast and multicast

In this paper, we study problems related to supporting unicast and multicast connections with quality of service (QoS) requirements. We investigate the problem of optimal routing and resource allocation in the context of performance dependent costs. In this context, each network element can offer several QoS guarantees, each associated with a different cost. This is a natural extension to the commonly used bi-criteria model, where each link is associated with a single delay and a single cost. This framework is simple yet strong enough to model many practical interesting networking problems. An important problems in this framework is finding a good path for a connection that minimizes the cost while retaining the end-to-end delay requirement. Once such a path (or a tree, in the multicast case) is found, one needs to partition the end-to-end QoS requirements among the links of the path (tree). We consider the case of general integer cost functions (where delays and cost are integers). As the related problem is NP complete, we concentrate on finding efficient e-approximation solutions. We improve on recent previous results by Ergun et al. Lorenz and Orda, and Raz and Shavitt, both in terms of generality as well as in terms of complexity of the solution. In particular, we present novel approximation techniques that yield the best known complexity for the unicast QoS routing problem, and the first approximation algorithm for the QoS partition problem on trees, both for the centralized and distributed cases.