HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 3:40:50 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM




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⟩



Record views