NDLI: Queuing Delays in Randomized Load Balanced Networks

Content Provider	IEEE Xplore Digital Library
Author	Prasad, R. Winzer, P.J. Borst, S.C. Thottan, M.K.
Copyright Year	2007
Description	Author affiliation: Georgia Tech., Atlanta (Prasad, R.)
Abstract	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.
Starting Page	400
Ending Page	408
File Size	961996
Page Count	9
File Format	PDF
ISBN	1424410479
ISSN	0743166X
DOI	10.1109/INFCOM.2007.54
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-05-06
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Telecommunication traffic Traffic control Routing Delay Load management Robustness Queueing analysis Performance analysis Analytical models Spread spectrum communication
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Paradox of Shortest Path Routing for Large Multi-Hop Wireless Networks

Load-Balanced Routing in Wireless Networks: State Information Accuracy Using OLSR

Queuing Delay and Achievable Throughput in Random Access Wireless Ad Hoc Networks

A distributed network selection mechanism for WCDMA/OFDMA heterogeneous networks

Load-balanced wireless ad hoc routing

Load balanced short path routing in wireless networks

Analysis of active queue management

Performance Modelling of Priority Queuing Discipline under Self-Similar and Poisson Traffic

Load balancing in grid networks

Queuing Delays in Randomized Load Balanced Networks

Similar Documents

Paradox of Shortest Path Routing for Large Multi-Hop Wireless Networks

Load-Balanced Routing in Wireless Networks: State Information Accuracy Using OLSR

Queuing Delay and Achievable Throughput in Random Access Wireless Ad Hoc Networks

A distributed network selection mechanism for WCDMA/OFDMA heterogeneous networks

Load-balanced wireless ad hoc routing

Load balanced short path routing in wireless networks

Analysis of active queue management

Performance Modelling of Priority Queuing Discipline under Self-Similar and Poisson Traffic

Load balancing in grid networks

Queuing Delays in Randomized Load Balanced Networks