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²*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²*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.