Efficient frontier formulation for additive and restrictive metrics in hierarchical routing

Abstract

In a hierarchical network, groups of nodes are represented by logical nodes for the purposes of simplifying routing. Each group has a set of ingress-egress nodes, and routing information is conveyed to the outside world in the form of a transition matrix that gives the cost of traversing the network between each ingress-egress node pair. In this paper, we present a minimal logical node representation that has sufficient descriptive power to enable path selection in support of connection admission control for services that have both path (restrictive) and link (additive) constraints. For example, the representation can be used to find a path that maximizes bandwidth subject to a delay constraint or minimizes delay subject to a bandwidth constraint. We present our solution in the form of a matrix whose elements are vectors, each of which specifies the efficient frontier of the solution space, and we specify an efficient procedure for constructing the efficient frontier. We present the least upper bound on the number of elements that must be present in the efficient frontier. We provide numerical examples that illustrate construction of the efficient frontier.