The crossbar-based switch fabric is widely used in today's high performance switches, due to its internally nonblocking and simply implementation properties. Usually there are two main switching architectures for crossbar-based switch fabric: internally bufferless crossbar switch and crosspoint buffered crossbar switch. As internally bufferless crossbar switch requires a complex centralized scheduler which limits its scalability to high speeds, crosspoint buffered crossbar switch has gained more attention because of its simpler distributed scheduling algorithm and better switching performance. However, almost all the scheduling algorithms proposed previously for crosspoint buffered crossbar switch either have unsatisfactory scheduling performance under non-uniform traffic patterns or show poor service fairness between input traffic flows. In order to overcome the disadvantages of existing algorithms, in this paper we propose two novel high performance scheduling algorithms named MCQF_RR and IMCQF_RR for crosspoint buffered crossbar switches. Both algorithms have a time complexity of O(log N), where N is the number of input/output ports of the switch. MCQF_RR takes advantage of the combined weight information about queue length and service waiting time of input queues to perform scheduling. In order to further reduce the scheduling complexity and make it feasible for high speed switches, IMCQF_RR uses the compressed queue length information instead of original queue length information to schedule cells in input VOQs. Simulation results show that our novel scheduling algorithms MCQF_RR and IMCQF_RR can demonstrate excellent delay performance comparable to existing high performance scheduling algorithms under both uniform and non-uniform traffic patterns, while maintain good service fairness performance under severe non-uniform traffic patterns.

The multichannel switch is an architecture widely used for ATM (Asynchronous Transfer Mode). It is known that the fault tolerant characteristic can be incorporated in into the multichannel crossbar switching fabric. For example, if a link belonging to a multichannel group fails, the remaining links can assume responsibility for some of the traffic on the failed link. On the other hand, if a fault occurs in a switching element, it can lead to erroneous routing and sequencing in the multichannel switch. We investigate several fault localization algorithms in multichannel crossbar ATM switches with a view to early fault recovery. The optimal algorithm gives the best performance in terms of time to localization but is computationally complex, which makes it difficult to operate in real time. We develop an online algorithm which is computationally more efficient than the optimal one. We evaluate its performance through simulation. The simulation results show that the performance of the online algorithm is only slightly suboptimal for both random and bursty traffic. There are cases where the proposed online algorithm cannot pinpoint down to a single fault. We explain the causes and enumerate those cases. Finally, a fault recovery algorithm is described which utilizes the information provided by the fault localization algorithm. The fault recovery algorithm adds extra rows and columns to allow cells to detour the faulty element.