BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR91-163
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Multipacket Routing on Rings
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Makedon, Fillia
AUTHOR:: Simvonis, Adononios
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1991
ABSTRACT::
	We study multipacket routing problems.  We divide the
multipacket routing problem into two classes, namely, distance limited
and bisection limited routing problems.  Then, we concentrate on rings
of processors.  Having a full understanding of the multipacket routing
problem on rings is essential before trying to attack the problem for
the more general case of r-dimensional meshes and tori.  We prove a
new lower bound of 2n/3 routing steps for the case of distance limited
routing problems.  We also give an algorithm that tightens this lower
bound.  For bisection limited problems, we present an algorithm that
completes the routing in near optimal time.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR91-163.pdf
END::