CUED Publications database

Steady state analysis of balanced-allocation routing

Anagnostopoulos, A and Kontoyiannis, I and Upfal, E (2005) Steady state analysis of balanced-allocation routing. Random Structures and Algorithms, 26. pp. 446-467. ISSN 1042-9832

Full text not available from this repository.


We compare the long-term, steady-state performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a path-selection algorithm based on the "balanced-allocation" principle [Y. Azer, A. Z. Broder, A. R. Karlin, and E. Upfal, SIAM J Comput 29(1) (2000), 180-200; M. Mitzenmacher, Ph.D. Thesis, University of California, Berkeley, August 1996]; we refer to this new algorithm as the Balanced Dynamic Alternative Routing (BDAR) algorithm. While DAR checks alternative routes sequentially until available bandwidth is found, the BDAR algorithm compares and chooses the best among a small number of alternatives. We show that, at the expense of a minor increase in routing overhead, the BDAR algorithm gives a substantial improvement in network performance, in terms both of network congestion and of bandwidth requirement. © 2005 Wiley Periodicals, Inc.

Item Type: Article
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:11
Last Modified: 20 Aug 2020 03:31
DOI: 10.1002/rsa.20071