QoS Routing: The Precomputation Perspective

Abstract — A major algorithmic challenge posed by QoS routing is the need to promptly identify a suitable path upon a connection request, while at the same time ensure that the selected path is satisfactory, both in terms of the connection’s QoS requirements, as well as in terms of the global utilization of network resources. In many practical cases, a precomputation scheme offers a suitable solution to the problem: a background process prepares a data base, which enables to identify a suitable path upon each connection request, through a simple, fast, procedure. While much work has been done in terms of path selection algorithms, the precomputation perspective got little attention. Simplistic adaptations of standard algorithms turn to be inefficient. Accordingly, we consider the precomputation perspective, focusing on two major settings of QoS routing. The first is the (practically important) special case where the QoS constraint is of the “bottleneck ” type, e.g. a bandwidth requirement, and network optimization is sought through hop minimization. For this setting, the standard Bellman-Ford algorithm offers a straightforward precomputation scheme. However, we show that, by exploiting the typical hierarchical structure of large-scale networks, one can achieve a substantial improvement in terms of computational complexity. Then, we turn to consider the more general setting of “additive ” QoS constraints (e.g., delay) and general link costs. As the routing problem becomes NP-hard, we focus on ¢-optimal approximations, and derive a precomputation scheme that offers a major improvement over the standard approach. Keywords—QoS, Routing, Precomputation, Hierarchical networks. I