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

1 J. Zerovnik
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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$-centralrouting problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$.Here we survey the results on 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 assume the \\emphstore-and-forward Δ-port model, and we consider both full and half-duplex networks.
Type de document :
Chapitre d'ouvrage
A. Koster and X. Mu~noz. Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks, XXVII, Springer, pp.265-279, 2009, EATCS Texts in Theoretical Computer Science, 978-3-642-02249-4
Liste complète des métadonnées

https://hal.inria.fr/hal-00795414
Contributeur : Alain Monteil <>
Soumis le : jeudi 28 février 2013 - 10:54:09
Dernière modification le : mercredi 14 décembre 2016 - 01:06:35

Identifiants

  • HAL Id : hal-00795414, version 1

Collections

Citation

, J. Zerovnik. Permutation Routing and $(\\ell,k)$-Routing on Plane Grids. A. Koster and X. Mu~noz. Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks, XXVII, Springer, pp.265-279, 2009, EATCS Texts in Theoretical Computer Science, 978-3-642-02249-4. <hal-00795414>

Partager

Métriques

Consultations de la notice

56