We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bounding the locality of distributed routing algorithms.
- Authors
Bose, Prosenjit; Carmi, Paz; Durocher, Stephane
- Abstract
We examine bounds on the locality of routing. A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know (1) its local neighbourhood (the subgraph corresponding to all network nodes within $$k$$ hops of itself, for some fixed $$k$$), (2) the node from which the message originated, and (3) the incoming port (which of its neighbours last forwarded the message). Our objective is to determine, as $$k$$ varies, which of these parameters are necessary and/or sufficient to permit local routing on a network modelled by a connected undirected graph. In particular, we establish tight bounds on $$k$$ for the feasibility of deterministic $$k$$-local routing for various combinations of these parameters, as well as corresponding bounds on dilation (the worst-case ratio of actual route length to shortest path length).
- Subjects
ROUTING algorithms; ROUTING (Computer network management); DISTRIBUTED algorithms; COMPUTER networks; DISTRIBUTED computing
- Publication
Distributed Computing, 2013, Vol 26, Issue 1, p39
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-012-0179-3