Skip to Main content Skip to Navigation
New interface
Book sections

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.
Document type :
Book sections
Complete list of metadata
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Thursday, February 28, 2013 - 10:54:09 AM
Last modification on : Thursday, March 5, 2020 - 4:53:29 PM


  • HAL Id : hal-00795414, version 1


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⟩



Record views