%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "bayb95.ltx",
%%%     date      = "20 November 1995",
%%%     time      = "21:41:34 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "47024 113 510 4245",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%                  
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{BayB95}

\title{Deterministic On-Line Routing on Area-Universal Networks}

\author{Paul Bay \and Gianfranco Bilardi}

\Pages{614--640}

\Month{May}

\Year{1995}

\Volume{42}

\Number{3}

\maketitle

\begin{abstract}

Two deterministic routing networks are presented: the \emph{pruned butterfly}
  and the \emph{sorting fat-tree}. Both networks are area-universal, i e., they
  can simulate any other routing network fitting in similar area with
  polylogarithmic slowdown. Previous area-universal networks were either for
  the off-line problem, where the message set to be routed is known in advance
  and substantial precomputation is permitted, or involved randomization,
  yielding results that hold only with high probability. The two networks
  introduced here are the first that are simultaneously deterministic and
  on-line, and they use two substantially different routing techniques. The
  performance of their routing algorithms depends on the difficulty of the
  problem instance, which is measured by a quantity~$\lambda$ known as the load
  factor. The pruned butterfly algorithm runs in time $O(\lambda \log^2 N)$,
  where $N$ is the number of possible sources and destinations for messages and
  $\lambda$ is assumed to be polynomial in~$N$. The sorting fat-tree algorithm
  runs in $O(\lambda \log N + \log^2 N)$ time for a restricted class of message
  sets including partial permutations. Other results of this work include a
  ``flexible'' sorting circuit that is area-time optimal across a range of
  different input sizes and an area-time lower bound for routers based on
  wire-length arguments.

\end{abstract}

\begin{categories}

C.1.2 [interconnection architectures]; C.2.1 [network communications, network
  topology]; F.1.2 [parallelism and concurrency]; F.2.2 [computation on
  discrete structures]; [routing and layout]; F.2.3

\end{categories}

\begin{terms}

Algorithms, Theory

\end{terms}

\begin{keywords}

Area-universal, fat-tree, general purpose

\end{keywords}

\end{document}
