Skip to Main content Skip to Navigation
Journal articles

The Eulerian stretch of a network topology and the ending guarantee of a convergence routing

Dominique Barth Pascal Berthomé Johanne Cohen 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we focus on convergence packet routing techniques in a network, obtained from an Eulerian routing in the digraph modeling the target network. Given an Eulerian circuit $\cal C$ in a digraph $G$, we consider the maximal number $diamW_{\cal C}$ of arcs that a packet has to follow on $\cal C$ from its origin to its destination (we talk about the {\em ending guarantee} of the routing). We consider the {\em Eulerian diameter of $G$} as defined by ${\cal E}(G)=\min\limits_{{\cal C}\in Eul(G)} diamW_{\cal C}$, where $Eul(G)$ is the set of all the Eulerian circuits in $G$. After giving a preliminary result about the complexity of finding ${\cal E}(G)$ for any digraph $G$, we give some lower and upper bounds of this parameter. We conclude by giving some families of digraphs having good Eulerian diameter.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00108086
Contributor : Publications Loria <>
Submitted on : Thursday, October 19, 2006 - 3:40:50 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

Identifiers

Collections

Citation

Dominique Barth, Pascal Berthomé, Johanne Cohen. The Eulerian stretch of a network topology and the ending guarantee of a convergence routing. Journal of Interconnection Networks, World Scientific Publishing, 2004, 5 (2), pp.93-109. ⟨10.1142/S0219265904001040⟩. ⟨inria-00108086⟩

Share

Metrics

Record views

258