BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR91-174
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Optimal Algorithms for Multipacket Routing Problems on Rings
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Makedon, Fillia
AUTHOR:: Symvonis, Antonios
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1991
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-174.pdf
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.  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 the lower bound is kn/ 4,k >2, where k is the number of
packets per processor.  The trivial algorithm needs in the worst case
k | n /2| steps to terminate.  An algorithm that completes the routing
in kn /4 + 2.5 n routing steps is given.  We define the class of pure
routing algorithms and we demonstrate that new lower bounds hold if
the routing is to be done by an algorithm in this class.
END:: ncstrl.dartmouthcs//TR91-174