Search results
Interval Routing Schemes.
- By: Pierre Fraigniaud , Cyril Gavoille
- Number: RR94-04
- Date: January 19, 1994
- Abstract:
- Interval routing was introduced to reduce the size of the routing tables: a router finds the direction to forward a message by determining the interval that contains the destination address of the message, each interval being associated to one particular direction. This way of implementing routing function is quite attractive but very few was known about the topological properties that should satisfy a network to admit an interval routing function satisfying particular constraints (shortest paths, limited number of intervals associated to each direction, etc). In this paper, we deeply investigate the study of the interval routing functions. In particular we characterize the networks that admit 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 that admit an optimal (linear) interval routing function. Finally, we derive the main properties that satisfy the popular networks used to interconnect the processors of a distributed memory parallel computer.
- Keywords: Routing Function, Intervals, Interconnected Networks, Distributed Memory Parallel Computer.
- Availability: Out of print.
- Citation: Published in proceedings CONPAR'94-VAPP VI, LNCS 854, pp 785-796, 1994 & proceedings 13rd ACM Symp on PODC, ACM Press, pp 216-224, 1994 : short version.
- Size: 2+29p
- Format: Compressed PostScript
- Get it
Worst Case Bounds for Shortest Path Interval Routing.
- By: Cyril Gavoille , Eric Guevremont
- Number: RR95-02
- Date: April 5, 1995
- Abstract:
- Consider shortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a network G, 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 on G. In this paper, we establish tight worst case bounds on IRS(G). More precisely for any n, we construct a network G of n nodes with IRS(G) in Theta(n), thereby improving on the best known lower bound of Omega(n / log n). We also establish a worst case bound on bounded degree networks: for any Delta >= 3 and any n, we construct a network G' of n nodes and maximum degree Delta with IRS(G') in Omega(n/(log n)^2).
- Abstract (in french):
- Nous considérons le problème du routage par intervalles de plus courts chemins, une méthode populaire et distribuée résolvant le problème du routage sur les réseaux arbritraires. Etant donné un réseau G, nous posons Irs (G) le nombre maximum d'intervalles nécessaires pour coder les groupes de destinations sur une arête, minimisé sur tous les routages par intervalles de plus courts chemins sur G. Dans cet article, nous établissons des bornes très étroite sur le pire cas pour Irs (G). Plus précisément, pour tout n, nous construisons un réseau G de n noeuds avec Irs(n) in Theta(n), améliorant par conséquent, la meilleure borne inférieure connue Omega(n/logn). Nous établissons également un pire cas pour les réseaux de degré borné : pour tout Delta >= 3 et tout n, nous construisons un réseau G\Delta de n noeuds et de degré maximum Delta avec Irs-G\Delta) in Omega(n/(log n)2).
- Keywords: Communication on Parallel and Distributed Networks, Compact Routing Tables, Interval Routing, Shortest Path Routing.
- Keywords (in french): Communication sur réseaux parallèles et distribués, tables de routages compactes, routage par intervalles, routages de plus courts chemins.
- Availability: Paper copy available.
- Citation: Not published yet.
- Size: 2+23p
- Format: Compressed PostScript
- Get it
Memory Requirement for Universal Routing Schemes.
- By: Pierre Fraigniaud , Cyril Gavoille
- Number: RR95-05
- Date: March 13, 1995
- Abstract:
- In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In [20], Peleg and Upfal showed that there is no hope to do that with less than a total Omega(n^{1+1/(2s+4)}) memory bits for any stretch factor s >= 1. We improve this bound for stretch factors s < 2 by proving that any near-shortest path routing scheme uses a total of Omega(n^2) memory bits.
- Abstract (in french):
- Dans cet article, nous abordons le problème du routage compact, qui est l'implémentation des stratégies de routages utilisant une taille mémoire minimum pour chaque routeur. Dans [20], Peleg et Upfal on montré qu'il n'y a aucun espoir de la réaliser avec moins de Omega(n^{1+1/(2s+4)}) bits mémoire au total pour tout facteur d'étirement s >= 1. Nous améliorons cette borne pour les facteurs d'étirement s < 2 en prouvant que toute stratégie de routage des presques plus courts chemins utilise un total de Omega(n^2) bits mémoire.
- Keywords: Communication on Parallel and Distributed Networks, Compact Routing Tables, Near-Shortest Path Routing.
- Keywords (in french): Communication sur réseaux parallèles et distribués, tables de routages compactes, routages de plus courts chemins.
- Availability: Paper copy available.
- Citation: To appear in proceedings of 14th ACM PODC, 20-23 August 1995, Ottawa.
- Size: 2+13p
- Format: Compressed PostScript
- Get it
Memory requirement for routing in distributed networks.
- By: Cyril Gavoille , Stephane Perennes
- Number: RR95-46
- Date: December 1995
- Abstract:
- In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node. We prove that for every shortest path routing scheme, for any constant e, 0 < e < 1, and for every integer d such that 3 <= d <= en, there exists a n-node network of maximum degree d that locally requires at least Theta(n logd) bits of memory on Theta(n) nodes. This optimal lower bound means that whatever the routing scheme (interval routing, boolean routing, prefix routing, ...), there exists a network on which one can not do better than routing tables. Moreover, we prove that, for the well-known interval routing scheme, there exists a n-node network of bounded degree d, for every d >= 3, that requires Theta(n) intervals on Theta(n) links to code any shortest path routing function. This tight lower bound shows that, for networks of bounded degree, the interval routing scheme can be worst than the routing tables in term of size.
- Abstract (in french):
- Dans cette étude nous nous intéressons au routage compact dans les réseaux distribués, c'est-à-dire à l'implémentation de fonctions de routage par des plus courts chemins dont le codage est minimal sur chaque routeur. Nous construisons des graphes de taille n et de degré borné par d tel que 3 <= d <= en pour une constante fixée e quelconque, 0 < e < 1, telle que la capacité mémoire nécessaire afin de router soit, sur une fraction constante des routeurs, d'au moins Theta(n log{d}) bits. Ceci signifie que sur ces réseaux, quelque soit le mode de routage (par intervalles, booléen, par préfixes, ...), certains routeurs devront mémoriser quasiment la table de routage in extenso. Enfin, ces graphes sont utilisés pour montrer qu'il existe des réseaux de degré borné par 3 où le routage par intervalles utilise Theta(n) intervalles sur Theta(n) arcs, ce qui nécessite plus de mémoire que les tables de routage.
- Keywords: Communication On Parallel and Distributed Networks, Compact Routing Tables, Interval Routing, Shortest Path Routing.
- Keywords (in french): Communication sur réseaux parallèles et distribués, tables de routages compactes, routage par intervalles, routages de plus courts chemins.
- Availability: Paper copy available.
- Citation: Published in the proceedings of PODC '96 - Best Student Paper Award.
- Size: 2+23p
- Format: Compressed PostScript
- Get it
Local memory requirement of universal routing schemes.
- By: Pierre Fraigniaud , Cyril Gavoille
- Number: RR96-01
- Date: January 1996
- Abstract:
- In this paper, we deal with the compact routing problem, that is the problem of implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all networks. In [13], Peleg and Upfal showed that one can not implement a universal routing scheme with less than a total of Omega(n^{1+1/(2s+4)}) memory bits for any routing scheme satisfying that the maximum ratio between the lengths of the routing paths and the lengths of the shortest paths, that is the stretch factor, is bounded by s. In [6], Fraigniaud and Gavoille improve this bound by proving that universal routing schemes of stretch factors at most 2 use a total of Omega(n^2) memory bits in the worst-case. Recently, Gavoille and Pérennès [9] showed that, in fact, in the worst-case, Theta(n) routers of an n-node network may require up to Omega(n log n) memory bits for shortest path routing. In this paper, we extend this result by showing that, for any constant e, 0 < e < 1, Omega(n^e) routers of an n-node network may require up to Omega(n log n) memory bits even if each routing path is of length up to twice the distance between its source and its destination.
- Abstract (in french):
- Dans cet article, nous abordons le problème du routage compact, qui est la mise en oeuvre des stratégies de routages utilisant une taille mémoire minimum pour chaque routeur. Une stratégie de routage universel est une stratégie qui s'applique à tous les réseaux. Dans [13], Peleg et Upfal ont montré qu'il n'y a aucun espoir de la réaliser avec moins de Omega(n^{1+1/(2s+4)}) bits mémoire au total pour toute stratégie de routage dont le rapport maximum entre la longueur des chemins de routage et la longueur des plus courts chemins, le facteur d' élongation, est borné par s. Dans [6], Fraigniaud et Gavoille améliorent cette borne en montrant que toute stratégie de routage universel de facteur d'élongation au plus 2 utilise un total de Omega(n^2) bits mémoire dans le pire cas. Récemment, Gavoille et Pérennès [9] ont montré, en fait, que Theta(n) routeurs d'un réseau de n noeuds peuvent chacun nécessiter localement de Omega(n log n) bits pour toute fonction de routage de plus courts chemins. Dans cet article, nous étendons ce résultat en montrant que, pour toute constante e, 0 < e < 1, Omega(n^e) routeurs d'un réseau de n noeuds nécessitent jusqu'à Omega(n log n) bits chacun si la longueur des chemins de routage est au plus deux fois plus longue que la longueur des plus courts chemins.
- Keywords: Communication on Parallel and Distributed Networks, Compact Routing Tables, Interval Routing, Shortest Path Routing.
- Keywords (in french): Communication sur réseaux parallèles et distribués, tables de routages compactes, routages de plus courts chemins.
- Availability: Paper copy available.
- Citation: Not published yet.
- Size: 2+8p
- Format: Compressed PostScript
- Get it
Lower Bounds for Shortest Path Interval Routing.
- By: Cyril Gavoille , Stephane Perennes
- Number: RR96-08
- Date: April 1996
- Abstract:
- Interval Routing was introduced to reduce the size of the routing tables: a router finds the direction to forward a message by determining the interval that contains the destination address of the message, each interval being associated to one particular direction. In this paper, we give lower bounds for the minimum number of intervals per edge needed to achieve shortest path routings for the class of 3-regular networks. We prove a tight lower bound of Theta(n) intervals for a 3-regular network of order at most n. Moreover, for the particular case of 3-regular planar networks, we establish a lower bound of Omega(sqrt{n}) intervals.
- Abstract (in french):
- Le routage par intervalles a été introduit pour réduire la taille des tables de routage : un routeur trouve la direction pour communiquer un message en déterminant l'intervalle contenant l'adresse de destination du message, chaque intervalle étant associé à une direction particulière. Dans cet article, nous donnons une borne inférieure du nombre minimum d'intervalles par arête nécessaire pour effectuer un routage de plus courts chemins pour la classe des réseaux 3-réguliers. Nous prouvons une borne inférieure optimale de Theta(n) intervalles pour un réseau 3-régulier d'ordre au plus n. De plus, pour la classe des réseaux 3-réguliers et planaires, nous établissons une borne inférieure de Omega(sqrt{n}) intervalles.
- Keywords: Compact Routing In Distributed Networks, Shortest Path Interval Routing, 3-regular Graphs, Planar Graphs.
- Keywords (in french): Routage Compact Dans Réseaux Distribués, Routage Par Intervalles Et De Plus Courts Chemins, Graphes 3-réguliers, Graphes Planaires.
- Availability: Out of print.
- Citation: Published in the proceedings of SIROCCO'96.
- Size: 2+13p
- Format: Compressed PostScript
- Get it
Back...