Load-balanced anycast routing in computer networks

Abstract

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.