Reducing Memory Size in Buffered Crossbars with Large Internal Flow Control Latency

A buffered crossbar supporting P priorities and a flow control latency of RT packets between the input adapter and the crossbar requires a memory of order O(N**2 * P * RT) packets in the crossbar to support any traffic pattern without blocking. We propose a new priority elevation mechanism that reduces the memory requirements to O(N**2 * RT) for large values of RT. Our analysis shows that our mechanism has no drawback on the usual performance metrics and that it only introduces a small priority unfairness and worst-case blocking of less than RT packet times. We further show that an optimized system using a crosspoint memory of size 2RT has an unfairness of less than 0.02% affected packets at 95% loading with an average burst size of 30 packets.