Fast deflection routing for packets and worms

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

doi:10.1145/164051.164062

Fast deflection routing for packets and worms

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

41 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 language	English (US)
Title of host publication	PODC 1993
Subtitle of host publication	Proceedings of the twelfth annual ACM symposium on Principles of distributed computing
Publisher	Publ by ACM
Pages	75-86
Number of pages	12
ISBN (Print)	0897916131, 9780897916134
DOIs	https://doi.org/10.1145/164051.164062
State	Published - Sep 1 1993
Externally published	Yes
Event	12th Annual ACM Symposium on Principles of Distributed Computing, PODC 1993 - Ithaca, NY, USA Duration: Aug 15 1993 → Aug 18 1993

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference	12th Annual ACM Symposium on Principles of Distributed Computing, PODC 1993
City	Ithaca, NY, USA
Period	8/15/93 → 8/18/93

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/164051.164062

Cite this

@inproceedings{41b0444e50124757b6c11937abe03900,

title = "Fast deflection routing for packets and worms",

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.",

author = "Amotz Bar-Noy and Prabhakar Raghavan and Baruch Schieber and Hisao Tamaki",

year = "1993",

month = sep,

day = "1",

doi = "10.1145/164051.164062",

language = "English (US)",

isbn = "0897916131",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Publ by ACM",

pages = "75--86",

booktitle = "PODC 1993",

note = "12th Annual ACM Symposium on Principles of Distributed Computing, PODC 1993 ; Conference date: 15-08-1993 Through 18-08-1993",

}

Bar-Noy, A, Raghavan, P, Schieber, B & Tamaki, H 1993, Fast deflection routing for packets and worms. in PODC 1993: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Publ by ACM, pp. 75-86, 12th Annual ACM Symposium on Principles of Distributed Computing, PODC 1993, Ithaca, NY, USA, 8/15/93. https://doi.org/10.1145/164051.164062

Fast deflection routing for packets and worms. / Bar-Noy, Amotz; Raghavan, Prabhakar; Schieber, Baruch et al.
PODC 1993: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing. Publ by ACM, 1993. p. 75-86 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast deflection routing for packets and worms

AU - Bar-Noy, Amotz

AU - Raghavan, Prabhakar

AU - Schieber, Baruch

AU - Tamaki, Hisao

PY - 1993/9/1

Y1 - 1993/9/1

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

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

UR - https://www.scopus.com/pages/publications/0027846495

UR - https://www.scopus.com/pages/publications/0027846495#tab=citedBy

U2 - 10.1145/164051.164062

DO - 10.1145/164051.164062

M3 - Conference contribution

AN - SCOPUS:0027846495

SN - 0897916131

SN - 9780897916134

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 75

EP - 86

BT - PODC 1993

PB - Publ by ACM

T2 - 12th Annual ACM Symposium on Principles of Distributed Computing, PODC 1993

Y2 - 15 August 1993 through 18 August 1993

ER -

Fast deflection routing for packets and worms

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this