Design and analysis of a packet concentrator

Packet concentrators are used in many highspeed computer communication systems such as fast packet switches. In these systems, the time available for concentration is very short. It is therefore desirable to realize the packet concentrators as hardware chips for fast concentration. The knockout concentrator was proposed for hardware realization. In this paper, we improve this concentrator to reduce the probability of packet loss, and the improved concentrator is called wraparound knockout concentrator. This concentrator has several wraparound paths within it, and it does not require any additional pin per chip. After contention among the packets in a slot, each winner goes to a distinct output, some losers circulate along the wraparound paths for contention in the subsequent slot, and the remaining losers are discarded. In this manner, some losers are not discarded immediately and they still have the chance to go to the outputs in the subsequent slot, thereby reducing the probability of packet loss. We analyze the number of logic gates required and the probability of packet loss. The numerical results show that if the proposed concentrator has a few wraparound paths, the probability of packet loss can already be reduced by orders of magnitude.