28572 articles – 22062 Notices  [english version]

inria-00265297, version 1

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

Omid Amini () 1, Florian Huc 1, Ignasi Sau Valls () a1, Janez Zerovnik b1

(2008)

Résumé : 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.

  • a –  Projet Mascotte - I3S (CNRS/UNSA) and INRIA - Sophia-Antipolis, France
  • b –  University of Maribor, Slovenie
  • 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • Domaine : Mathématiques/Combinatoire
  • Mots-clés : Packet routing – distributed algorithm – $(\ell – k)$-routing – plane grids – permutation routing – shortest path – oblivious algorithm
  • Versions disponibles :  v1 (19-03-2008) v2 (25-03-2008)
 
  • inria-00265297, version 1
  • oai:hal.inria.fr:inria-00265297
  • Contributeur : 
  • Soumis le : Mardi 18 Mars 2008, 16:57:57
  • Dernière modification le : Mercredi 19 Mars 2008, 08:33:16