Routing protocols using the distributed Bellman-Ford (DBF) algorithm converge very slowly to the correct routes when link costs increase, and in the case when a set of link failures results in a network partition, DBF simply fails to converge, a problem which is commonly referred to as the count-to-infinity problem. We present the first distance-vector routing algorithm, MDVA, that uses a set of loop-free invariants to prevent the count-to-infinity problem. MDVA, in addition, computes multipaths that are loop-free at every instant. In our earlier work we shows how such loop-free multipaths can be used in traffic load-balancing and minimizing delays, which otherwise are impossible to perform in current single-path routing algorithms.

A major concern with the IETF proposed integrated services (Intserv) architecture for providing quality of service is that the amount of reservation state it stores in the routers and the RSVP protocol it uses to maintain the consistency of reservation state may not be scalable to high-speed backbone networks. Because of the large number of flows in the backbone network, the refresh messages associated with RSVP's soft-state mechanism, apart from consuming memory, bandwidth and computing power, can experience significant queuing delays and prevent correct functioning of the soft-state mechanism. For the refresh mechanism to scale, therefore, the reservation state size must be bounded so that delays of time-sensitive refresh messages can also be bounded through adequate bandwidth allocation. Vutukury and Garcia-Luna-Accves (see. Proc. of ICCCN, 1999) described the scalable multipath aggregated routing architecture (SMART) In which the reservation state size is a function of number of destinations rather than number of flows in the network. In this paper, we describe a reservation protocol (AGREE) to maintain this reservation state aggregated along the multipaths. The AGREE protocol, like RSVP, uses soft-states, but also ensures that the refresh messages experience bounded queuing delays. The SMART architecture combined with AGREE protocol is significantly more scalable compared to the Intserv/RSVP model.

Single-path routing provided by today's interior gateway protocols (IGP) make extremely inefficient usage of network bandwidth, and is evident in the large end-to-end delays flows experience in single-path routing as compared to minimum-delay routing. Enhancement to OSPF such as optimized multipath have not proved adequate to bridge this large delay gap. Practical implementations of minimum-delay routing, on the other hand, have been largely unsuccessful for reasons such as scalability, slow convergence and out-of-order packet delivery. This paper proposes a traffic engineering solution that adapts the minimum-delay routing for a given traffic matrix in a way that is practical and suitable to implement in the differentiated services framework. A simple and scalable packet forwarding technique is described that offers several improvements over OSPF-OMP.

We present a practical approach to routing and anycasting with near-optimum delays taking into account the processing loads at routers and processing elements of a computer network. To accomplish this, the minimum-delay routing problem formulated by Gallager (1977) is generalized into the problem of minimum-delay routing with load-balancing to account for processing delays in network nodes (servers and routers). Gallager's theorem for necessary and sufficient conditions for minimum-delay routing is modified to include processing delays and changes of traffic levels at network nodes. The first distributed algorithm for load-balanced anycasting and routing in computer networks is presented. This algorithm, named MIDAS, provides approximate solutions to the modified necessary and sufficient conditions for minimum-delay routing. Simulations are use to compare the performance of the new algorithm with the performance of a traditional approach to sever load balancing.

We present a practical approach to internet routing that provides near-minimum delays over multiple loop-free paths to destinations. The new protocol, which we call NEAR-OPT, obtains multiple loop-free paths to destinations using long-term delay measures, and allocates destination-oriented flows over such paths using short-term delay measures to minimize delay. We compare the performance of NEAR-OPT with traditional single-path routing and the only known adaptation for dynamic networks of Gallager's minimum-delay routing algorithm. Using actual Internet traffic traces and other traffic source models, we show that NEAR-OPT provides delays comparable to the lower bounds achievable with Gallager's algorithm for static networks, provides lower delays than implementations of Gallager's algorithm in networks subject to fractal traffic, and renders far smaller delays and better use of resources than traditional single-path routing. NEAR-OPT does not depend on any global constant and is completely distributed, making it easy to implement as a loop-free distance-vector protocol similar to Cisco's EIGRP.

The Internet community has proposed the integrated services architecture (Intserv) and the signaling protocol RSVP to provide deterministic guarantees (bandwidth, delay and jitter) to individual flows. However, experience with practical systems has revealed the severe scalability problems of the Intserv model due to the amount of routing and reservation state that is required to he maintained in the routers. A natural approach to improving scalability of the Intserv architecture is through a reduction of the number of states in the routers by using aggregated flow state instead of per-flow state. We present a novel architecture that uses very few states in the routers, while still providing the deterministic guarantees of the Intserv model.

Routing algorithms in the IP Internet provide a single path between each source-destination pair and where more than one path is provided, they are paths of equal length. Single-path routing is inherently slow in responding to congestion and temporary traffic bursts; multiple paths are better suited to handle congestion. Also the paths provided in RIP and OSPF are not free of loops during times of network transition, which can be debilitating to network performance. We present a distributed routing algorithm for computing multiple paths that need not have equal length between each source-destination pair in a computer network such that they are loop-free at every instant - in steady state as well as during network transitions. The algorithm is scalable to large networks as it uses only one-hop synchronization which is unlike diffusing computations that require internodal synchronization spanning multiple hops. The safety and liveness properties of the algorithm are proven and its complexity is analyzed.

The conventional approach to routing in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Single-path routing is very responsive to topological and link-cost changes; however, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase. On the other hand, minimum-delay routing approaches can minimize delays only when traffic is stationary or very slowly changing.We present a "near-optimal" routing framework that offers delays comparable to those of optimal routing and that is as flexible and responsive as single-path routing protocols proposed to date. First, an approximation to the Gallager's minimum-delay routing problem is derived, and then algorithms that implement the approximation scheme are presented and verified. We introduce the first routing algorithm based on link-state information that provides multiple paths of unequal cost to each destination that are loop-free at every instant. We show through simulations that the delays obtained in our framework are comparable to those obtained using the Gallager's minimum-delay routing. Also, we show that our framework renders far smaller delays and makes better use of resources than traditional single-path routing.