Routing with end-to-end QoS guarantees in broadband networks

We consider routing schemes for connections with end-to-end delay requireme nts, and investigate several fundamental problems. First, we focus on netwo rks which employ rate-based schedulers and, hence, map delay guarantees int o nodal rate guarantees, as done,vith the Guaranteed Service class proposed for the Internet. We consider first the basic problem of identifying a fea sible route for the connection, for which a straightforward yet computation ally costly solution exists. Accordingly, we establish several approximatio n schemes that offer substantially lower computational complexity. We then consider the more general problem of optimizing the route choice in terms o f balancing loads and accommodating multiple connections, for which we form ulate and validate several optimal algorithms. We discuss the implementatio n of such schemes in the context of Link-state and distance-vector protocol s. Next, we consider the fundamental problem of constrained path optimizati on. This problem, typical of quality of service routing, is NP-hard. While standard approximation methods exist, their complexity may often be prohibi tive in terms of scalability. Such approximations do not make use of the pa rticular properties of large-scale networks, such as the fact that the path selection process is typically presented with a hierarchical, aggregated t opology. By exploiting the structure of such topologies, we obtain an E-opt imal algorithm for the constrained shortest-path problem, which offers a su bstantial improvement in terms of scalability.