Fast deflection routing for packets and worms

Amotz Bar-Noy, Prabhakar Raghavan, Baruch Schieber, Hisao Tamaki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations

Abstract

We consider deflection routing on the n×n mesh and torus. In deflection routing a message cannot be buffered, and is therefore always moving until it reaches its destination. In addition, routing choices have to be made locally. We give a nearly optimal deterministic algorithm for the permutation routing problem for packets, the first such result for deflection routing. We extend the deterministic algorithm to the case when the messages are worms: a contiguous physical stream of bits that must follow the head of the message uninterrupted through the network. We then give an optimal randomized algorithm for permutation routing for worms of any length up to n.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
PublisherPubl by ACM
Pages75-86
Number of pages12
ISBN (Print)0897916131, 9780897916134
DOIs
StatePublished - 1993
Externally publishedYes
EventProceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing - Ithaca, NY, USA
Duration: Aug 15 1993Aug 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

ConferenceProceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing
CityIthaca, NY, USA
Period8/15/938/18/93

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this