New performance bounds of a class off self-routing networks

Conventional bounds for the maximum throughput of an unbuffered banyan network and its topology equivalents are based on the parallel path setup (PPS) assumption, i.e. paths are set up simultaneously. But the bounds derived under the PPS assumption can be surpassed with a slight variation on the path setup scheme. The authors study the maximum throughputs of an unbuffered banyan network and its topology equivalents in an incremental path setup (IPS) environment. The results represent the ultimate bounds for the maximum throughputs of unbuffered banyan networks. Although the exact analysis of this problem involves a combinatorial explosion, an approximate analysis is given in this work to verify the simulation results