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

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
Arie Koster; Xavier Muñoz. 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
Domaine :

https://hal.inria.fr/hal-00795414
Contributeur : Alain Monteil <>
Soumis le : jeudi 28 février 2013 - 10:54:09
Dernière modification le : mercredi 30 août 2017 - 01:11:08

### Identifiants

• HAL Id : hal-00795414, version 1

### Citation

Janez Zerovnik. Permutation Routing and $(\\ell,k)$-Routing on Plane Grids. Arie Koster; Xavier Muñoz. 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〉

### Métriques

Consultations de la notice