Bounding the locality of distributed routing algorithms

作     者：Bose, Prosenjit Carmi, Paz Durocher, Stephane 

作者机构：Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ Manitoba Dept Comp Sci Winnipeg MB R3T 2N2 Canada 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：2013年第26卷第1期

页      面：39-58页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Natural Sciences and Engineering Research Council of Canada (NSERC) 

主　　题：Distributed algorithms Local routing Dilation 

摘      要：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 hops of itself, for some fixed ), (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 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 for the feasibility of deterministic -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).