next up previous
Next: 4.2 A level-by-level algorithm Up: 4 Establishing many paths Previous: 4 Establishing many paths

4.1 Unshared neighbors

Our circuit-switching algorithm requires the splitters in the multibutterfly to have a special ``unshared-neighbors'' property defined as follows.




By Equation 2.1, we know that randomly-generated splitters have the tex2html_wrap_inline1817 unshared-neighbors property where tex2html_wrap_inline1819 approaches 1 as d gets large and tex2html_wrap_inline1825 gets small. Explicit constructions of such splitters are not known, however. Nevertheless, we will consider only multibutterflies with the tex2html_wrap_inline1827 unshared-neighbors property for tex2html_wrap_inline1829 in what follows.

Remark: The tex2html_wrap_inline1831 expansion property ( tex2html_wrap_inline1833 ) is a sufficient condition for the unshared-neighbors property, but by no means necessary. In fact, we can easily prove the existence of random splitters which have a fairly strong tex2html_wrap_inline1835 unshared-neighbors property for small degree. For such graphs, the routing algorithm we are about to describe is more efficient in terms of hardware required. However, multibutterflies with expansion properties will remain the object of our focus.

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996