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

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 = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

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

}