We consider routing schemes for connections with end-to-end delay requirements, and investigate several fundamental problems. First, we focus on networks which employ rate-based schedulers and, hence, map delay guarantees into nodal rate guarantees, as done with the guaranteed service class proposed for the Internet. We consider first the basic problem of identifying a feasible route for the connection, for which a straightforward yet computationally costly solution exists. Accordingly, we establish several approximation schemes that offer substantially lower computational complexity. We then consider the more general problem of optimizing the route choice in terms of balancing loads and accommodating multiple connections, for which we formulate and validate several optimal algorithms. We discuss the implementation of such schemes in the context of link-state and distance-vector protocols. Next, we consider the fundamental problem of constrained path optimization. This problem, typical of quality of service routing, is NP-hard. While standard approximation methods exist, their complexity may often be prohibitive in terms of scalability. Such approximations do not make use of the particular properties of large-scale networks, such as the face that the path selection process is typically presented with a hierarchical, aggregated topology. By exploiting the structure of such topologies, we obtain an /spl epsiv/-optimal algorithm for the constrained shortest-path problem, which offers a substantial improvement in terms of scalability.
展开▼
