A survey on interval routing
type: Item
instance of: scholarly article
title: A survey on interval routing
zbMATH Open document ID: 0946.68002
DOI: 10.1016/S0304-3975(99)00283-2
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
review text: We survey in this paper the classical results, and also the most recent results, in the field 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 classes 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.
Mathematics Subject Classification ID: 68M14
zbMATH DE Number: 1493513
zbMATH Keywords: compact routing
zbMATH Keywords: routing tables
zbMATH Keywords: interval routing
zbMATH Keywords: broadcasting
zbMATH Keywords: networks
author: Cyril Gavoille
MaRDI profile type: Publication
cites work: Q4291429
cites work: On interval routing schemes and treewidth
cites work: Optimal routing tables
cites work: Static and dynamic low-congested interval routing schemes
cites work: Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
cites work: Topology of series-parallel networks
cites work: Compact routing schemes with low stretch factor
cites work: The complexity of the characterization of networks supporting shortest-path interval routing.
cites work: Q4262693
cites work: Deadlock-free interval routing schemes
cites work: Multidimensional interval routing schemes
cites work: Characterization results of all shortest paths interval routing schemes
cites work: Interval routing schemes
cites work: The complexity of interval routing on random graphs
cites work: On the impact of sense of direction on message complexity
cites work: Sense of direction: Definitions, properties, and classes
cites work: Sense of direction in distributed computing
cites work: Universal routing schemes
cites work: Designing networks with compact routing tables
cites work: Space-Efficient Message Routing inc-Decomposable Networks
cites work: A Distributed Algorithm for Minimum-Weight Spanning Trees
cites work: Q4699302
cites work: Worst Case Bounds for Shortest Path Interval Routing
cites work: The compactness of interval routing for almost all graphs
cites work: Memory requirement for routing in distributed networks
cites work: Q3328583
cites work: Q3715120
cites work: On forwarding indices of networks
cites work: Treewidth. Computations and approximations
cites work: Q5317672
cites work: Q4536937
cites work: Lower bounds for compact routing
cites work: Q4023358
cites work: Partial characterizations of networks supporting shortest path interval labeling schemes
cites work: A trade-off between space and efficiency for routing tables
cites work: Q3815249
cites work: On the complexity of multi-dimensional interval routing schemes
cites work: Labelling and Implicit Routing in Networks
cites work: Q4325545
cites work: Q4345573
cites work: Q3711761
cites work: Interval Routing
description: scientific article; zbMATH DE number 1493513