@TechReport{Dartmouth:TR91-174,
  author = {Fillia Makedon and Antonios Symvonis},
  title = {{Optimal Algorithms for Multipacket Routing Problems on Rings}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR91-174},
  year = {1991},
  URL = {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.
  }
}