ON ROUTING AND PERFORMANCE EVALUATION OF BUFFERED SPARSE CROSSBAR CONCENTRATORS

Abstract

We investigate the routing and performance of sparse crossbar packet concentrators under a buffered network model. The concentration property in packet switching concentrators is defined with respect to packets instead of input/output ports. This allows such concentrators to function as generalized connectors (with some constraints). This altered functionality for a packet concentrator over its circuit switched counterpart translates into differences in performance measures like complexity and delay. A model for constructing sparse crossbar packet switching concentrators with optimal cross point complexity has been introduced in literature. We use this construction to model the performance of a sparse crossbar packet concentrator and relate performance measures to its complexity, connectivity and buffer requirements. In this thesis, we address issues of routing and performance evaluation over such optimal sparse crossbar fabrics, in particular their relation to complexity and buffer requirements. We present an analysis of the packet loss suffered in such concentrators when excess packets are dropped. We go on to analyze the best performance possible when packets are stored and serviced in FIFO order. These results lead us to formulate a routing algorithm which tries to emulate the best case performance on the sparse crossbar. We present theoretical and simulation results for the best case performance and the algorithm. We find that the algorithm is efficient and allows concentration to be done with negligible loss of performance on the sparse crossbar.