NDLI: Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs

Please wait, while we are loading the content...

Completely fair SFE and coalition-safe cheap talk

Bringing practical lock-free synchronization to 64-bit applications

Lock-free linked lists and skip lists

On the inherent weakness of conditional synchronization primitives

Load balancing and locality in range-queriable data structures

Compact routing on euclidian metrics

Eclecticism shrinks even small worlds

Balanced binary trees for ID management and load balance in distributed hash tables

Byzantine disk paxos: optimal resilience with byzantine shared memory

Competitive on-line paging strategies for mobile users under delay constraints

A note on efficient aggregate queries in sensor networks

Geometrically aware communication in random wireless networks

Gradient clock synchronization

The weakest failure detectors to solve certain fundamental problems in distributed computing

Brief announcement: stretch between nearby peers

Brief announcement: a single enqueuer wait-free queue implementation

Brief announcement: exposing and eliminating vulnerabilities to denial of service attacks in secure gossip-based multicast

Brief announcement: self-stabilizing distance-d distinct labels via enriched fair composition

Brief announcement: randomized rumor spreading with fewer phone calls

Brief announcement: towards a secure indirection infrastructure

Brief announcement: reconfigurable byzantine-fault-tolerant atomic memory

Brief announcement: polygonal broadcast, secret maturity and the firing sensors

Brief announcement: RT oblivious erasure correcting

Brief announcement: degree: optimal deterministic routing for P2P systems

Brief announcement: on the round complexity of distributed consensus over synchronous networks

Brief announcement: the synchronous condition-based consensus hierarchy

Brief announcement: on the inherent cost of generic broadcast

Mechanism design for policy routing

An almost non-blocking stack

Lower bounds for adaptive collect and related objects

Specification faithfulness in networks with rational nodes

Choosing a random peer

When graph theory helps self-stabilization

Analyzing Kleinberg's (and other) small-world Models

Efficient top-K query calculation in distributed networks

How fast can a distributed atomic read be?

A better wake-up in radio networks

Computation in networks of passively mobile finite-state sensors

Communication-efficient leader election and consensus with limited link synchrony

Group membership: a novel approach and the first single-round algorithm

Brief announcement: prefix hash tree

Brief Announcement: constraint-based synchronization and verification of concurrent programs

Brief announcement: spoofing prevention method

Brief announcement: STALK: a self-stabilizing hierarchical tracking service for sensor networks

Brief announcement: an incremental algorithm for calculation of backup-paths in link-state networks

Brief announcement: Trilix: a scalable unstructured lookup system for dynamic environments

Brief announcement: adaptive balancing networks

Brief announcement: optimal asynchronous garbage collection for checkpointing protocols with rollback-dependency trackability

Brief announcement: secret handshakes from CA-oblivious encryption

Brief announcement: efficient clustering in unstructured radio networks

Brief announcement: veto number and the respective power of eventual failure detectors

Brief announcement: efficient implementation of a byzantine data storage system

Brief announcement: on the possibility of consensus in asynchronous systems with finite average response times

Selfish caching in distributed systems: a game-theoretic analysis

Efficient synchronous snapshots

On the expected payment of mechanisms for task allocation

Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game

Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models

Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs

On the design of distributed protocols from differential equations

Signed quorum systems

Broadcast in radio networks tolerating byzantine adversarial behavior

What cannot be computed locally!

Asynchronous group key exchange with failures

Brief announcement: detecting malicious routers

Brief announcement: completing the lock-free dynamic cycle

Brief announcement: concurrent maintenance of rings

Brief announcement: linear time byzantine self-stabilizing clock synchronization

Brief announcement: name-independent compact routing in trees

Brief announcement: virtual mobile nodes for mobile ad hoc networks

Brief announcement: building an adaptive distributed web server system on the fly for handling web hotspots

On spectrum sharing games

Brief announcement: implementing multi-word atomic snapshots on current hardware

Brief announcement: the design of an internet-scale monitoring and assertion-checking infrastructure

Brief announcement: Cataclysm: handling extreme overloads in internet services

Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs

Content Provider	ACM Digital Library
Author	Zhang, Li Gao, Jie
Abstract	A graph has growth rate k if the number of nodes in any subgraph with diameter r is bounded by $O(r^{k}).$ The communication graphs of wireless networks and peer-to-peer networks often have small growth rate. In this paper we study the tradeoff between two quality measures for routing in growth restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load balancing ratio, which measures how evenly the traffic is distributed. We show that if the routing algorithm is required to use paths with stretch factor c, then its load balancing ratio is bounded by $O((n/c)^{1-1/k}),$ where k is the graph's growth rate. We illustrate our results by focusing on the unit disk graph for modeling wireless networks in which two nodes have direct communication if their distance is under certain threshold. We show that if the maximum density of the nodes is bounded by ρ, there exists routing scheme such that the stretch factor of routing paths is at most c, and the maximum load on the nodes is at most O(min(√ρn/c, n/c)) times the optimum. In addition, the bound on the load balancing ratio is tight in the worst case. As a special case, when the density is bounded by a constant, the shortest path routing has a load balancing ratio of O(√n). The result extends to k-dimensional unit ball graphs and graphs with growth rate k. We also discuss algorithmic issues for load balanced short path routing and for load balanced routing in spanner graphs.
Starting Page	189
Ending Page	196
Page Count	8
File Format	PDF
ISBN	1581138024
DOI	10.1145/1011767.1011795
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Wireless networks Growth restricted graphs Routing Load balancing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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