Bounding the locality of distributed routing algorithms Academic Article uri icon


  • 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).

publication date

  • September 11, 2012