Browse Prior Art Database

On the Complexity of Permutation Routing

IP.com Disclosure Number: IPCOM000105428D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 85K

Publishing Venue

IBM

Related People

Raghavan, P: AUTHOR [+2]

Abstract

The Network: We construct a degree d, depth logn over 2logd multibutterfly using &sqrt. d-way m-splitters.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

On the Complexity of Permutation Routing

       The Network:  We construct a degree d, depth logn over
2logd multibutterfly using &sqrt.  d-way m-splitters.

      A &sqrt.  d-way m-splitter has one set of m input nodes and
sqrt d output sets, each with m slr sqrt d nodes.  Each input has
sqrt d edges to each of the sqrt d output sets.  The edges connecting
the input set to each of the output sets define an expander graph
with the following properties:

1.  Even if we arbitrarily erase half of the edges adjacent to each
input of the splitter, each set of k inputs, k lesym m over 10d
connect to at least sqrt dk slr 10 outputs in each output sets.

2.  For a given set of inputs X, let Gamma lpar X, sqrt d slr 4, i)
denote the set of vertices in the i-th output set with at least sqrt
d slr 4 neighbors in X.  We require that for each set X of k inputs,
k lesym m over <10 sqrt d apos> vbar Gamma lpar X, sqrt d slr 4, i
rpar vbar lesym k over sqrt d log d.

      Lemma 1:  There exists an expander graph with the above
properties.

      Proof:  It is enough to show the existence of the desired graph
between the sets of inputs to one set of outputs.  Choose a random
bipartite graph with m vertices in one side, each of degree sqrt d,
and m slr sqrt d vertices on the other side, each with degree d.

      Expansion:

      The bound on the sets Gamma lpar X, sqrt d slr 4, i):

      The algorithm:  Similar to the algorithm for bounded degree
multibutterfy we partition the n messages to 200 batches, such that
no more than m slr 200 messages from each batch traverse any m input
splitter.

      Nodes at odd stages transmit in odd phases, nodes in even
stages transmit in even phases.  A phase has three steps.  In the
first step a node in a transmitting stage sends a request message to
all its neighbors in output sets to which it has message to transmit.
A node that receives less than sqrt d slr 4 messages, and currently
stores less than sqrt d slr 4 messages, replies in the second step
with a ready massage to his neighbors in the previous stage.  On the
third step nodes sends up to one packet to each node that sent them a
ready message.

      The routing of one batch was first analyzed.  Consider one
splitter and a phase in which the inputs of the splitter are
transmitting messages to the outputs.  Let k be the number of inputs
nodes that at the be...