Efficient dynamic routing in wide-area networks.

The tremendous growth of the global Internet has given rise to a variety of applications that require quality-of-service (QoS) beyond what is provided by the current best-effort IP packet delivery service. In addition, traditional static shortest-path routing offers little flexibility in managing the distribution of traffic in the network. Dynamic or QoS routing protocols offer the advantage of choosing paths that meet application QoS requirements and balance the load in the network. These benefits come at the cost, however, of additional consumption of computational and bandwidth resources at levels higher than conventional routing protocols. More specifically, dynamic routing performs poorly when the network state used to compute paths is out-of-date, requiring that network information be distributed very frequently to achieve good results. This dissertation undertakes a detailed study of dynamic and QoS routing with a focus on understanding and controlling the performance-overhead trade-offs inherent in these protocols. We develop a practically motivated model that clearly formulates dynamic routing in terms of a set of route computation algorithms, routing and update policies, and network and traffic configurations. The model is implemented in a custom-designed simulation environment that allows experimentation with a wide variety of configurations. We use the model and simulation environment to perform in-depth experiments that uncover the influences of a variety of policy and configuration parameters on the performance and resulting overheads. In particular, the evaluation focuses on the effects of out-of-date information about network state on routing performance. A significant contribution of this effort is a set of specific guidelines and observations that assist service providers in configuring the network and setting policies for dynamic or QoS routing. With the insights collected from the evaluation effort, the dissertation develops novel algorithms for reducing the computational overheads of QoS routing. These mechanisms allow precomputed QoS routes to efficiently capitalize on the latest state information available. As a result, precomputation is able to offer performance competitive with the much more costly on-demand computation policy. Finally, the dissertation introduces hybrid routing, a new routing scheme for IP networks that limits dynamic routing to a subset of the network traffic. By dynamically routing only long-lived flows, hybrid routing is able to improve the stability and efficiency of load-sensitive routing while also providing automated load-balancing capability that reacts to fluctuations in network traffic.