Permutation Routing and $(\\ell,k)$-Routing on Plane Grids - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Chapitre D'ouvrage Année : 2009

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

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$-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.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

hal-00795414 , version 1 (28-02-2013)

Identifiants

  • HAL Id : hal-00795414 , version 1

Citer

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⟩
32 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More