版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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).