Steady state analysis of balanced‐allocation routing

DOI10.1002/RSA.20071MaRDI QIDQ5311900zbMATH OpenOpenAlexWikidataFDO

Authors Aris Anagnostopoulos, Ioannis Kontoyiannis, Eli Upfal

Publication date 29 August 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0209357

zbMATH Keywords

ATM networksbalanced dynamic alternative routingdynamic alternative routingsteady state analysistelecommunication systems

Mathematics Subject Classification ID

Communication theory (94A05) Communication, information (94A99) Circuits, networks (94C99)

Abstract: 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; 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.

Recommendations

• Balanced routing of random calls
• On-line routing of random calls in networks
• scientific article; zbMATH DE number 786519
• Concurrent threads and optimal parallel minimum spanning trees algorithm
• Analysis of Simple Algorithms for Dynamic Load Balancing

Cites work

• scientific article; zbMATH DE number 3338194 (Why is no real title available?)
• Markov chains and stochastic stability

Cited in

(4)

• On-line routing of random calls in networks
• Balanced routing of random calls
• Euro-Par 2004 Parallel Processing
• LOAD-BALANCED ALGORITHM ON BANDWIDTH CALENDARING PROBLEM

This page was built for publication: Steady state analysis of balanced‐allocation routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311900)