Collector-based Cell Reordering in Load-Balanced Switch Fabrics

Load-balanced switch fabrics have been extensively studied. We present three new results. First, we consider the well-known cell reordering problem, which arises if different paths through the switch fabric have different delays. We show that this problem problem is relatively easily solved in hardware: we give a tree-based reordering circuit that operates at a rate of a cell per clock cycle. Second, under a reasonably general admissible cell-arrival process, we give a probabilistic analysis of relevant queue occupancies. Third, we provide analysis and simulations of throughput for inadmissible traffic, when some output is overloaded; this last topic has had the least previous attention.