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

$(\ell,k)$-Routing on Plane Grids

Omid Amini 1 Florian Huc 1 Janez Zerovnik 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $\ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(\ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the \emph{store-and-forward} $\Delta$-port model, and we consider both full and half-duplex networks. The main contributions are the following: \begin{itemize} \item[1.] Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. \item[2.] Tight $r$-central routing algorithms on triangular and hexagonal grids. \item[3.] Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. \item[4.] Good approximation algorithms (in terms of running time) for $(\ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. \end{itemize} \noindent All these algorithms are completely distributed, i.e. can be implemented independently at each node. Finally, we also formulate the $(\ell,k)$-routing problem as a \textsc{Weighted Edge Coloring} problem on bipartite graphs.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, March 25, 2008 - 4:07:54 PM
Last modification on : Friday, February 4, 2022 - 3:11:26 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 4:22:04 PM


Files produced by the author(s)


  • HAL Id : inria-00265297, version 2
  • ARXIV : 0803.2759



Omid Amini, Florian Huc, Janez Zerovnik. $(\ell,k)$-Routing on Plane Grids. [Research Report] RR-6480, INRIA. 2008. ⟨inria-00265297v2⟩



Record views


Files downloads