A survey on interval routing

被引：48
作者：
Gavoille, C [1 ]
机构：
[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France
来源：
THEORETICAL COMPUTER SCIENCE | 2000年 / 245卷 / 02期
关键词：
compact routing; routing tables; interval routing; broadcasting; networks;
D O I：
10.1016/S0304-3975(99)00283-2
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We survey in this paper the classical results, and also the most recent results, in the held of Interval Routing, a well-known strategy to code in a compact way distributed routing algorithms. These results are classified in several themes: characterization, compactness and shortest path, dilation and stretch factor, specific class of graphs (interconnection networks, bounded degree, planar, chordal rings, random graphs, etc.), and the other recent extensions proposed in the literature: dead-lock free, congestion, non-deterministic, and distributed problems related to Interval Routing. For each of these themes we review the state of the art and propose several open problems. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：217 / 253
页数：37
相关论文
共 85 条
  • [1] BAKKER EM, 1994, UNPUB
  • [2] BAKKER EM, 1991, ALGORITHMS REV, V2, P45
  • [3] DISTRIBUTED LOOP COMPUTER-NETWORKS - A SURVEY
    BERMOND, JC
    COMELLAS, F
    HSU, DF
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 24 (01) : 2 - 10
  • [4] On interval routing schemes and treewidth
    Bodlaender, HL
    vanLeeuwen, J
    Tan, R
    [J]. INFORMATION AND COMPUTATION, 1997, 139 (01) : 92 - 109
  • [5] BODLAENDER HL, 1993, RUUCS9212 U UTRECHT
  • [6] BRAUME V, 1993, THESIS U PADERBORN
  • [7] BURHMAN H, 1996, 15 ANN ACM S PRINC D, P134
  • [8] Cicerone S, 1998, LECT NOTES COMPUT SC, V1443, P592, DOI 10.1007/BFb0055087
  • [9] DALLY WJ, 1987, IEEE T COMPUT, V36, P547, DOI 10.1109/TC.1987.1676939
  • [10] DELATORRE P, 1998, 5 INT C STRUCT INF C
123456789