Application of the generalised ballot theorem for evaluation of performance in packet buffers with non-first in first out scheduling

Packet scheduling is a vital component to support different classes of service in all-packet networks. In classical queuing systems, the waiting-time performance of non-first in first out buffer scheduling systems could be predicted through the use of analysis. However, all-packet networks feature traffic patterns that do not conform to classical Poisson-like processes, and this greatly complicates the evaluation of their performance. Our novel approach to this problem is through a hybrid combination of analysis and simulation. The authors derive a combinatorial algorithm, using the generalised ballot theorem, which predicts waiting times for low-priority traffic. When this algorithm is combined with prior work on traffic aggregation, the authors achieve a significant reduction in the state space associated with the buffer under study. To numerically test this algorithm, the authors demonstrate its use in simulation, where state space and event count reduction is a fundamental requirement to ensure experiments complete in a timely fashion. Numerical results from these simulations show a very significant reduction in the number of events processed combined with improved state coverage. This is achieved while maintaining a highly accurate representation of packet delays compared with a conventional approach.