Reducing cell loss in banyan based ATM switching fabrics

In this paper, we propose a new technique for reducing cell loss in multi-banyan-based ATM switching fabrics. We propose a switch architecture that uses incremental path reservation based on previously established connections. Path reservation is carried out sequentially within each banyan but multiple banyan planes can be concurrently reserved. We use a conflict resolution approach according to which banyans make concurrent reservation offers of conflict-free paths to head of the line cells waiting in input buffers. A reservation offer from a given banyan is allocated to the cell whose source-to-destination path uses the largest number of partially allocated switching elements which are shared with previously reserved paths. Paths are incrementally clustered within each banyan. This approach leaves the largest number of free switching elements for subsequent reservations which has the effect of reducing the potential of future conflicts and improves throughput. We present a pipelined switch architecture based on the above concept of path-clustering which we call path-clustering banyan switching fabric (PCBSF). An efficient hardware that implements PCBSF is presented together with its theoretical basis. The performance and robustness of PCBSF are evaluated under simulated uniform traffic and ATM traffic. We also compare the cell loss rate of PCBSF to that of other pipelined banyan switches by varying the switch size, input buffer size, and traffic pattern.