Design and evaluation of cell scheduling algorithms for atm switches

摘要

An ATM switch is a high speed fixed-size packet switching architecture; it is a basic element for the ATM protocol which has been widely accepted as the ultimate solution for the BISDN. In this paper, we first successfully transform the cell scheduling problem of a window-based input queneing ATM switch to the maximum matching problem on a bipartite graph. An optimal solution can thus be found in O(W x N~2) time, where N is the number of input/output ports, and W is the window size; or in O(W x N~(3/2)) time if the maximum matching problem is further transformed to a maximum network flow problem. Next, we study and exaluate four existing approximation algorithms, including a simple heuristic algorithm and three neural network methods: the Hopfield memory neural network algorithm, the McCulloch-Pitts neural algorithm, and an approximate neural algorithm based on McCuloch-Pitts neural network. Their performance in terms of throughput, mean waiting time, and neuron convergence time, are evaluated using computer simulations. We found that the optimal algorithm provides the highest throughput, and more significantly, a much shorter mean waiting time than the other four approximation schemes.