Name
Abstract | ||
|---|---|---|
ABSTRACT We examine bounds on the locality of routing. A local rout- ing algorithm makes,a sequence of distributed forwarding decisions, each of which is made using only local informa- tion. Specically, in addition to knowing the node for which a message is destined, an intermediate node might also know a) the subgraph corresponding to all network nodes within k hops of itself, for some value of k, b) the node from which the message originated, and c) which of its neighbours last forwarded the message. Our objective is to determine which of these parameters are necessary and/or sucient,to permit local routing as k varies on a network modelled by a con- nected undirected graph. In particular, we establish tight bounds on k for the feasibility of deterministic k-local rout- ing 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). Categories and Subject Descriptors C.2.1 [Computer Systems Organization]: Computer- |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/1582716.1582756 | Distributed computing |
Keywords | Field | DocType |
Distributed algorithms,Local routing,Dilation | Equal-cost multi-path routing,Link-state routing protocol,Multipath routing,Dynamic Source Routing,Computer science,Static routing,Path vector protocol,Theoretical computer science,Routing table,Geographic routing,Distributed computing | Journal |
Volume | Issue | ISSN |
26 | 1 | 0178-2770 |
Citations | PageRank | References |
12 | 0.77 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prosenjit K. Bose | 1 | 2336 | 293.75 |
| Paz Carmi | 2 | 321 | 43.14 |
| Stephane Durocher | 3 | 342 | 42.89 |