Routing guaranteed quality of service connections in integrated services packet networks

A critical functional component of quality-of-service (QoS) deployment in packet-switched networks is QoS-based routing. In this paper, we present a routing solution for guaranteed quality-of-service connections in integrated services packet networks (ISPN) - the future QoS-capable Internet proposed by the IETF. The problem is in essence a path finding problem with both end-to-end delay and per-node buffer constraints, in networks with heterogeneous intermediate switching nodes. We present a polynomial time algorithm using a capacity plane decomposition technique combined with a per-node constrained shortest path algorithm. We further propose an efficient route computation architecture, based on a novel metric-separation approach, to a slightly restricted version of the problem. The strategy is somewhat similar to 'route caching', but in a new and broader sense.