Queueing delays in randomized load balanced networks

R. Prasad, P.J. Winzer, S.C. Borst, M.K. Thottan

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)


Valiant's concept of randomized load balancing (RLB), also promoted under the name 'two-phase routing', has previously been shown to provide a cost-effective way of implementing overlay networks that are robust to dynamically changing demand patterns. RLB is accomplished in two steps; in the first step, traffic is randomly distributed across the network, and in the second step traffic is routed to the final destination. One of the benefits of RLB is that packets experience only a single stage of routing, thus reducing queueing delays associated with multi-hop architectures. In this paper, we study the queuing performance of RLB, both through analytical methods and packet-level simulations using ns2 on three representative carrier networks. We show that purely random traffic splitting in the randomization step of RLB leads to higher queuing delays than pseudo-random splitting using, e.g., a round-robin schedule. Furthermore, we show that, for pseudo-random scheduling, queuing delays depend significantly on the degree of uniformity of the offered demand patterns, with uniform demand matrices representing a provably worst-case scenario. These results are independent of whether RLB employs priority mechanisms between traffic from step one over step two. A comparison with multi-hop shortest-path routing reveals that RLB eliminates the occurrence of demand-specific hot spots in the network.
Originele taal-2Engels
TitelProceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007, Anchorage AL, USA, May 6-12, 2007)
Plaats van productiePiscataway, New Jersey, USA
UitgeverijInstitute of Electrical and Electronics Engineers
ISBN van geprinte versie1-4244-1047-9
StatusGepubliceerd - 2007


Duik in de onderzoeksthema's van 'Queueing delays in randomized load balanced networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit