Browse Prior Art Database

Complexity of Permutation Routing

IP.com Disclosure Number: IPCOM000110913D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 86K

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.

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

      The algorithm:  Similar to the algorithm for bounded degree
multibutterfy we partition the n messages to 200 batches, such that
no 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 divslash 4 messages, and
currently stores less than sqrt d divslash 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 begin...