Bounding the Locality of Distributed Routing Algorithms

Paz Carmi, School of Computer Science, Carleton

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 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 sufficient to permit local routing as $k$ varies 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).

Joint work with P. Bose and S. Durocher.