Proper Linear Interval Routing Schemes

B. ZERROUK, S. TRICOT, B. ROTTEMBOURG

IBP-Masi 1994/29: Rapport de Recherche Masi / Masi research reports
18 pages - Septembre/September 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Proper Linear Interval Routing Schemes

Résumé : L'étiquettage par intervalle est une solution intéressante pour l'implémentation de tables de routage compactes dans un réseau d'interconnexion à passage de messages L'étiquettage linéaire est une sous classe dans ce type de schéma. Dans cet article, nous nous intéressons à un étiquettage linéaire propre sur des graphes non pondérés. Un étiquettage propre est tel qu' une étiquette associée à un noeud donné n'appartient à aucun des intervalles associés aux sorties de ce noeud. Nous donnons des condition nécessaires définissant ainsi une classe de graphes qui semble familiaire.
Le but de ce papier est d'ouvrir le problème suivant : est-ce que la classe de graphes ayant un étiquettage linéaire propre est parfaite, dans le sens où chaque graphe de cette classe est constructible moyennant des opérateurs simple, et qu'il possède un schéma de routage propre optimal qui est formellement non bloquant ?

Abstract : Interval labeling is interesting for the implementation of compact routing tables in message passing interconnexion networks. Linear interval labeling is a subclass in the interval labeling hierarchy. In this paper we consider a proper linear interval labeling on unweighted graphs. A proper interval labeling is a linear interval labeling such that a label of any node is not contained in any interval of an outgoing link of that node. We give necessary conditions for which a graph may admit a proper linear interval scheme. We show that the class of those graphs includes familiar structures.
The aim of this paper is to open the problem that the class of graphs which admit optimal proper linear interval schemes defines an "ideal" class of topologies : any topology of this class is constructible and has an optimal deadlock-free routing function. Constructibility means that any topology of this class can be well described using simple graph operators (or operations).

Publications internes Masi 1994 / Masi research reports 1994