A survey on interval routing
---
paper_title: Computer Networks with Compact Routing Tables

paper_content:

The routing problem in computer networks is traditionally solved by providing detailed routing information for all destinations at every node. We consider the problem of routing messages with only a small amount of information at every node. For example, for every connected N-node network a scheme can be devised such that every message can be routed within O(√N) routing decisions. Improving on an observation of Santoro & Khatib [3] for trees we derive a general method of routing messages in arbitrary networks using tables of a size corresponding to the number of links at a node, while utilizing all links in the network.
---
paper_title: Compact Routing Schemes With Low Stretch Factor

paper_content:

This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node network along paths whose stretch factor (namely, the ratio between the length of the routing path and the shortest path) is at most five, and whose average stretch factor is at most three, with routing tables of size O(√n log3/2 n) bits per node. In addition, the route lengths are at most 2D (⌈1.5D⌉ for uniform weights) where D is the weighted diameter of the network. Moreover, it is shown that the PIR strategy can be constructed in polynomial time and can be implemented so that the generated scheme is in the form of an interval routing scheme (IRS), using at most O(√n log n) intervals per link. As a result, the schemes are simpler than previous ones and they imply that the paths followed by messages are loop-free. On the other hand, we show that there is no loop-free routing strategy guaranteeing a memory bound of at most √n bits per node for all networks, regardless of the route lengths.
---
paper_title: An Optimal Lower Bound for Interval Routing in General Networks

paper_content:

Interval routing is a space-efficient (compact) routing method for point-topoint communication networks. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings exist for regular as well as some of the common topologies, but not for arbitrary graphs. It has been shown that it is impossible to find optimal labelings for arbitrary graphs [4]. In this paper, we prove the lower bound of 2D − 3 on the longest routing path for arbitrary graphs, where D = O( √ n) is the graph’s diameter and n is the number of nodes, as well as a lower bound of 2D − o(D) for D = O(n). Our results are very close to the best known upper bound which is 2D.
---
paper_title: The Compactness of Interval Routing

paper_content:

The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4 on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. (A preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)
---
paper_title: A Lower Bound for Linear Interval Routing

paper_content:

Linear Interval Routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of Interval Routing where the routing range associated with every link is represented by an interval with no wrap-around. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For Interval Routing the upper bound and lower bound on this quantity are 2D and 1.75D — 1, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D2) on the length of a path a message traverses under Linear Interval Routing. We further extend the result by showing a connection between the efficiency of Linear Interval Routing and the bi-diameter of the network.
---
paper_title: A lower bound for interval routing in general networks

paper_content:

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7D/40 1 lower bound for interval routing in arbitrary graphs, where D is the diameter—i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7D/40 1. q 1997 John Wiley & Sons, Inc.
---
paper_title: Compact Routing Schemes With Low Stretch Factor

paper_content:

This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node network along paths whose stretch factor (namely, the ratio between the length of the routing path and the shortest path) is at most five, and whose average stretch factor is at most three, with routing tables of size O(√n log3/2 n) bits per node. In addition, the route lengths are at most 2D (⌈1.5D⌉ for uniform weights) where D is the weighted diameter of the network. Moreover, it is shown that the PIR strategy can be constructed in polynomial time and can be implemented so that the generated scheme is in the form of an interval routing scheme (IRS), using at most O(√n log n) intervals per link. As a result, the schemes are simpler than previous ones and they imply that the paths followed by messages are loop-free. On the other hand, we show that there is no loop-free routing strategy guaranteeing a memory bound of at most √n bits per node for all networks, regardless of the route lengths.
---
paper_title: On The Hardness Of Devising Interval Routing Schemes

paper_content:

The k-Interval Routing Scheme (k-IRS) is a compact routing scheme on general networks. It has been studied extensively and recently been implemented on the latest generation of the INMOS transputer router chips. In this paper we investigate the time complexity of devising a minimal space k-IRS and we prove that the problem of deciding whether there exists a 2-IRS for any network G is NP-complete. This is the first hardness result for k-IRS where k is constant and the graph underlying the network is unweighted. Moreover, the NP-completeness holds also for linear and strict 2-IRS.
---
paper_title: Worst case bounds for shortest path interval routing

paper_content:

Considershortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a networkG, let Irs(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes onG. In this paper, we establish tight worst case bounds on Irs(G). More precisely for anyn, we construct a networkGofnnodes with Irs(G)??(n), thereby improving on the best known lower bound of ?(n/logn). We also establish a worst case bound on bounded degree networks: for any ??3 and anyn, we construct a networkG?ofnnodes and maximum degree ? with Irs(G?)??(n/(logn)2).
---
paper_title: The Compactness of Interval Routing

paper_content:

The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4 on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. (A preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)
---
paper_title: Universal routing schemes

paper_content:

In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n2) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(nɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do.
---
paper_title: Interval Routing Schemes

paper_content:

Interval routing was introduced to reduce the size of routing tables: a router finds the direction where to forward a message by determining which interval contains the destination address of the message, each interval being associated to one particular direction. This way of implementing a routing function is quite attractive but very little is known about the topological properties that must satisfy a network to support an interval routing function with particular constraints (shortest paths, limited number of intervals associated to each direction, etc.). In this paper we investigate the study of the interval routing functions. In particular, we characterize the set of networks which support a linear or a linear strict interval routing function with only one interval per direction. We also derive practical tools to measure the efficiency of an interval routing function (number of intervals, length of the paths, etc.), and we describe large classes of networks which support optimal (linear) interval routing functions. Finally, we derive the main properties satisfied by the popular networks used to interconnect processors in a distributed memory parallel computer.
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: Distributed Loop Computer Networks: A Survey

paper_content:

Abstract Distributed loop computer networks are extensions of the ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. We give a survey of recent results on this class of interconnection networks. We pay special attention to the actual computation of the minimum diameter and the construction of loop networks which can achieve this optimal number. Some open problems are offered for further investigation.
---
paper_title: Some Lower-Bound Results on Interval Routing in Planar Graphs

paper_content:

Interval routing is a space-efficient routing method for computer networks. For the method to be practical, the routes it generates must be either shortest paths or not too much longer than the shortest paths. We answer the question of what is the lower bound on the longest path that any interval routing scheme (IRS) may be able to generate for arbitrary planar graphs. In general, the worstcase performance of an algorithm is dependent upon the length of the longest path. We consider the generalized form of IRS in which a link is allowed to have up to M ( ) interval labels. The results we derive cover the range of M values from to p n : (1) a lower bound of M M D on the longest path for M p n , and (2) a lower bound of M M D on the longest path for M up to p n , where D is the diameter and n the number of nodes. The second result also implies a lower bound of p n on the number of labels needed by any optimal IRS (one that generates optimally-short paths).
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: A Tourist Guide through Treewidth

paper_content:

A short overview is given of many recent results in algorithmic graph theory that deal with the notions treewidth, and pathwidth. We discuss algorithms that find tree-decompositions, algorithms that use tree-decompositions to solve hard problems efficiently, graph minor theory, and some applications. The paper contains an extensive bibliography.
---
paper_title: Designing networks with compact routing tables

paper_content:

Classes of network topologies are identified in which shortest-path information can be succinctly stored at the nodes, if they are assigned suitable names. The naming allows each edge at a node to be labeled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy of networks is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.
---
paper_title: Worst case bounds for shortest path interval routing

paper_content:

Considershortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a networkG, let Irs(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes onG. In this paper, we establish tight worst case bounds on Irs(G). More precisely for anyn, we construct a networkGofnnodes with Irs(G)??(n), thereby improving on the best known lower bound of ?(n/logn). We also establish a worst case bound on bounded degree networks: for any ??3 and anyn, we construct a networkG?ofnnodes and maximum degree ? with Irs(G?)??(n/(logn)2).
---
paper_title: Distance routing on series parallel networks

paper_content:

We consider the problem of routing messages on Series Parallel Graphs (SPGs) and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding in the label of each node x some information about a shortest path from the source of the SPG to x, and from x to the terminal node of the SPG. We first compare shortest path Distance Routing and I-interval Routing Schemes on directed SPGs. We then show that Distance Routing can be used to route on bidirectional SPGs, where no general shortest path I-interval Routing Scheme can be applied. We also show the relevance of the study of the time complexity in the choice of a Compact Routing method.
---
paper_title: The Compactness of Interval Routing for Almost All Graphs

paper_content:

Interval routing is a compact way of representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing table. Such groups of addresses are represented by some intervals of consecutive integers. We show that almost all the graphs, i.e., a fraction of at least 1-1/n2 of all the n-node graphs, support a shortest path interval routing with three intervals per outgoing edge, even if the addresses of the nodes are arbitrarily fixed in advance and cannot be chosen by the designer of the routing scheme. In case the addresses are initialized randomly, we show that two intervals per outgoing edge suffice, and, conversely, that two intervals are required for almost all graphs. Finally, if the node addresses can be chosen as desired, we show how to design in polynomial time a shortest path interval routing with a single interval per outgoing edge for all but at most O(log3n) outgoing edges in each node. It follows that almost all graphs support a shortest path routing scheme which requires at most n+O(log4n) bits of routing information per node, improving on the previous upper bound.
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: Algorithmic graph theory and perfect graphs

paper_content:

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
---
paper_title: Adaptive, fault-tolerant, deadlock-free and livelock-free interval routing in mesh networks

paper_content:

An adaptive, deadlock-free and livelock-free routing algorithm for faulty two-dimensional mesh connected multiprocessor interconnection networks based on store-and-forward communication is presented in this paper. Only three virtual networks, VN/sub 0/, VN/sub 1/ and VN/sub 2/, are needed. The algorithm is composed of two parts. Part one implemented in VN/sub 0/ is deadlock-free and allows a packet to use the path with minimum traffic congestion. Part two is fully-adaptive minimal routing. It requires two virtual networks-VN/sub 1/ and VN/sub 2/.
---
paper_title: Interval Routing Schemes

paper_content:

Interval routing was introduced to reduce the size of routing tables: a router finds the direction where to forward a message by determining which interval contains the destination address of the message, each interval being associated to one particular direction. This way of implementing a routing function is quite attractive but very little is known about the topological properties that must satisfy a network to support an interval routing function with particular constraints (shortest paths, limited number of intervals associated to each direction, etc.). In this paper we investigate the study of the interval routing functions. In particular, we characterize the set of networks which support a linear or a linear strict interval routing function with only one interval per direction. We also derive practical tools to measure the efficiency of an interval routing function (number of intervals, length of the paths, etc.), and we describe large classes of networks which support optimal (linear) interval routing functions. Finally, we derive the main properties satisfied by the popular networks used to interconnect processors in a distributed memory parallel computer.
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: Interval Routing Schemes

paper_content:

Interval routing was introduced to reduce the size of routing tables: a router finds the direction where to forward a message by determining which interval contains the destination address of the message, each interval being associated to one particular direction. This way of implementing a routing function is quite attractive but very little is known about the topological properties that must satisfy a network to support an interval routing function with particular constraints (shortest paths, limited number of intervals associated to each direction, etc.). In this paper we investigate the study of the interval routing functions. In particular, we characterize the set of networks which support a linear or a linear strict interval routing function with only one interval per direction. We also derive practical tools to measure the efficiency of an interval routing function (number of intervals, length of the paths, etc.), and we describe large classes of networks which support optimal (linear) interval routing functions. Finally, we derive the main properties satisfied by the popular networks used to interconnect processors in a distributed memory parallel computer.
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: On multi-label linear interval routing schemes

paper_content:

We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [11].
---
paper_title: On Interval Routing Schemes and Treewidth

paper_content:

In this paper, we investigate which processor networks allow k-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k≥1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth.
---
paper_title: Designing networks with compact routing tables

paper_content:

Classes of network topologies are identified in which shortest-path information can be succinctly stored at the nodes, if they are assigned suitable names. The naming allows each edge at a node to be labeled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy of networks is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.
---
paper_title: On Interval Routing Schemes and Treewidth

paper_content:

In this paper, we investigate which processor networks allow k-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k≥1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth.
---
paper_title: Treewidth: Computations and Approximations

paper_content:

and basic terminology.- Preliminaries.- Testing superperfection of k-trees.- Triangulating 3-colored graphs.- Only few graphs have bounded treewidth.- Approximating treewidth and pathwidth of a graph.- Approximating treewidth and pathwidth for some classes of perfect graphs.- Treewidth of chordal bipartite graphs.- Treewidth and pathwidth of permutation graphs.- Treewidth of circle graphs.- Finding all minimal separators of a graph.- Treewidth and pathwidth of cocomparability graphs of bounded dimension.- Pathwidth of pathwidth-bounded graphs.- Treewidth of treewidth-bounded graphs.- Recognizing treewidth-bounded graphs.
---
paper_title: Worst case bounds for shortest path interval routing

paper_content:

Considershortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a networkG, let Irs(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes onG. In this paper, we establish tight worst case bounds on Irs(G). More precisely for anyn, we construct a networkGofnnodes with Irs(G)??(n), thereby improving on the best known lower bound of ?(n/logn). We also establish a worst case bound on bounded degree networks: for any ??3 and anyn, we construct a networkG?ofnnodes and maximum degree ? with Irs(G?)??(n/(logn)2).
---
paper_title: Designing networks with compact routing tables

paper_content:

Classes of network topologies are identified in which shortest-path information can be succinctly stored at the nodes, if they are assigned suitable names. The naming allows each edge at a node to be labeled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy of networks is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.
---
paper_title: Computer Networks with Compact Routing Tables

paper_content:

The routing problem in computer networks is traditionally solved by providing detailed routing information for all destinations at every node. We consider the problem of routing messages with only a small amount of information at every node. For example, for every connected N-node network a scheme can be devised such that every message can be routed within O(√N) routing decisions. Improving on an observation of Santoro & Khatib [3] for trees we derive a general method of routing messages in arbitrary networks using tables of a size corresponding to the number of links at a node, while utilizing all links in the network.
---
paper_title: Characterization Results of All Shortest Paths Interval Routing Schemes

paper_content:

We give complete characterizations for the classes of graphs with uniform cost links that admit optimum all shortest paths 1-SLIRS (strict linear interval routing schemes) and 1-LIRS (linear interval routing schemes). The characterization of all the interval routing schemes with uniform cost links that represent only a single shortest path is known to be NP-complete, For any integer k > 0, we also show that the class of graphs with dynamic cost links that admit optimum all shortest paths L-IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum single shortest path l-IRS (SIRS, LIRS, SLIRS) and also equivalent to the class of graphs with dynamic cost links that admit single paths up to any constant stretch factor k-IRS (SIRS, LIRS, SLIRS). (C) 2001 John Wiley & Sons, Inc.
---
paper_title: The Compactness of Interval Routing

paper_content:

The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4 on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. (A preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)
---
paper_title: Introduction To Distributed Algorithms

paper_content:

From the Publisher: ::: The second edition of this textbook provides an up-to-date introduction both to the topic, and to the theory behind the algorithms. The clear presentation makes the book suitable for advanced undergraduate or graduate courses, whilst the coverage is sufficiently deep to make it useful for practising engineers and researchers." "The author concentrates on algorithms for the point-to-point message passing model, and includes algorithms for the implementation of computer communication networks. Other key areas discussed are algorithms for the control of distributed applications and fault tolerance achievable by distributed algorithms. The two new chapters on sense of direction and failure detectors are state-of-the-art and will provide an entry to research in these still developing topics.
---
paper_title: Universal routing schemes

paper_content:

In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n2) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(nɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do.
---
paper_title: Deadlock-Free Message Routing in Multiprocessor Interconnection Networks

paper_content:

A deadlock-free routing algorithm can be generated for arbitrary interconnection networks using the concept of virtual channels. A necessary and sufficient condition for deadlock-free routing is the absence of cycles in a channel dependency graph. Given an arbitrary network and a routing function, the cycles of the channel dependency graph can be removed by splitting physical channels into groups of virtual channels. This method is used to develop deadlock-free routing algorithms for k-ary n-cubes, for cube-connected cycles, and for shuffle-exchange networks.
---
paper_title: Static and Dynamic Low-Congested Interval Routing Schemes

paper_content:

In this paper we consider Interval Routing Schemes (IRS) that are optimal with respect, to the congestion of the induced path system. We provide a general framework able to deal with the various cougestion issues in IRS. In fact, it is possible to distinguish between static cases, in which the source-destination configurations are fixed, and dynamic cases, where they vary over time. All these situations can be handled in a unified setting, thanks to the notion of competitiveness introduced in this paper. We first give some general results not related to specific traflic demands. Then, in the one-to-all communication pattern, we show that constructing competitive IRS for a given network is an intractable problem, both for the static and the dynamic case, that is respectively when the root vertex is fixed and when it can change along lie time. Finally, both for one-to-all and all-to-all communication patterns, we provide nicely competitive k-IRS for relevant topologies. Networks considered are chains, trees, rings, chordal rings and multi-dimensional grids and tori. We consider both the directed congestion case, in which there are pairwise opposite unidirectional links connecting two neighbor processors, and the undirected congestion case, in which two neighbor are connected by a single bi-directional link.
---
paper_title: On forwarding indices of networks

paper_content:

Abstract A network (G,R) consists in a given undirected graph G of order n and a routing R, that is a collection of n(n-1) simple paths connecting every ordered pair of vertices of G. Chung, Coffman, Reiman and Simon defined the forwarding index ξ(G,R) of a network (G,R) as the maximum number of paths of R passing through any vertex of G. Similarly we define the edge-forwarding index of a network (G,R) as the maximum number of paths of R passing through any edge of G. These parameters might be of interest in different applications concerning communication networks. The forwarding (resp. edge-forwarding) index corresponds to the maximum amount of forwarding done by any node (resp. edge). The edge-forwarding index also corresponds to the maximum load of the network. Therefore it is of interest, for a given graph, to find routings minimizing these indices and we shall define the forwarding (edge-forwarding) index of a graph as the minimum taken over all possible indices of the possible networks. In this paper we give bounds on these forwarding indices, in particular as a function of the connectivity of the graph, and calculate them for products of graphs and for some specific graphs.
---
paper_title: Distributed Loop Computer Networks: A Survey

paper_content:

Abstract Distributed loop computer networks are extensions of the ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. We give a survey of recent results on this class of interconnection networks. We pay special attention to the actual computation of the minimum diameter and the construction of loop networks which can achieve this optimal number. Some open problems are offered for further investigation.
---

Title: A survey on interval routing

Section 1: Introduction
Description 1: This section provides an overview of Interval Routing, highlighting its advantages, early implementations, and a brief roadmap of the paper's organization.

Section 2: The model of interval routing
Description 2: This section presents the basic definitions and notations used in Interval Routing, establishing the foundational concepts necessary for understanding the routing model.

Section 3: Definition of interval routing
Description 3: In this section, the formal definition of Interval Routing Scheme (IRS) is detailed, including necessary conditions for a valid IRS and an example to illustrate these definitions.

Section 4: Compactness, linearity and strictness of interval routing
Description 4: This section explains the notions of compactness, linearity, and strictness within the context of Interval Routing, and introduces related variants such as k-IRS, k-LIRS, and k-SIRS.

Section 5: Coding of interval routing
Description 5: This section delves into the coding methods for implementing Interval Routing Schemes, proving that it can be done with a logarithmic number of bits relative to the graph size and discussing practical implementation issues.

Section 6: Characterizations
Description 6: This section provides various characterization theorems for graphs supporting different types of Interval Routing Schemes, mentioning specific cases and their implications.

Section 7: Efficiency of interval routing: dilation and stretch factor
Description 7: This section discusses the efficiency of Interval Routing in terms of dilation and stretch factor, presenting multiple theorems that establish lower and upper bounds for these measures.

Section 8: Complexity of characterization
Description 8: This section addresses the complexity of determining whether a graph supports a specific type of Interval Routing Scheme, highlighting several NP-completeness results.

Section 9: Specific class of graphs
Description 9: This section surveys the results known about the compactness of various specific classes of graphs, including interconnection networks, chordal rings, planar graphs, and treewidth bounded graphs.

Section 10: Random graphs
Description 10: This section discusses the compactness of random graphs, presenting theorems and probabilities associated with the support of Interval Routing Schemes in random graphs.

Section 11: Other classes of graphs
Description 11: This section reviews results for other classes of graphs, such as complete multipartite graphs and unit interval graphs, also mentioning specific exceptions and counterexamples.

Section 12: Graph operators
Description 12: This section explores the impact of common graph operators, like Cartesian products and graph composition, on the compactness of Interval Routing Schemes.

Section 13: Fixed and dynamic link-cost models
Description 13: In this section, the paper extends the discussion to interval routing on weighted graphs, considering both fixed cost and dynamic cost models.

Section 14: Hierarchy of the IRS classes
Description 14: This section outlines the theoretical hierarchy of the different Interval Routing Schemes, establishing their relationships and containment properties.

Section 15: Non-deterministic interval routing schemes
Description 15: This section investigates non-deterministic Interval Routing Schemes, their flexibility, characterizations, and associated open problems.

Section 16: Deadlock-free interval routing schemes
Description 16: This section addresses the issues of deadlock in interval routing and presents strategies for achieving deadlock-free Interval Routing Schemes.

Section 17: Congestion of interval routing
Description 17: This section examines the congestion characteristics of Interval Routing Schemes and presents results on edge-congestion and arc-congestion in various topologies.

Section 18: Interval routing for distributed problems
Description 18: This section explores the utility of Interval Routing in solving distributed problems more efficiently, discussing specific algorithms and their performance.

Section 19: Summary
Description 19: This section provides a summary of the key results discussed in the paper, encapsulating the insights gained from the survey of interval routing.