Performance analysis on dynamics of parallel iterative matching in an input-buffered switch

This paper presents a theoretical analysis of the Parallel Iterative Matching (PIM)'s dynamics with multiple iterations used in an input-buffered packet switch. In the past, the formulation on the switching performance was derived by using the Stirling number of the Second Kind, which is a summary the number of different matches under traffic with uniform distribution. However, when traffic has a different ditributions, the frequency of the different matching patterns in PIM can be used to determine the maximum achievable throughput. Therefore, it is of interest to analyze PIM's behavior with multiple iterations by identifying the contribution of the different matching states so a variety of traffic conditions can be considered. This paper presents a detailed analysis of the matching patterns and how they are used to formulate the throughput of PIM with multiple iterations. In our approach, by carefully categorizing all unmatched patterns into several representative patterns after each iteration, probabilities of accumulated matched pairs in a recursive manner are successfully obtained. Numerical evaluation of the analytical formulas are performed.