An approximate solution for the resequencing problem in packet-switching networks

An approximation heuristic is proposed for solving the heterogeneous multi-server queueing problem associated with the analysis of resequencing of packets travelling over multiple physical links in a packet-switching network. Even though a method for obtaining the exact solution exists, its processing time and memory requirements vary exponentially in terms of the number of servers and render it infeasible even for moderately-sized systems. Precision of the proposed approximation which has linear time complexity is demonstrated. The approximation is recommendable in cases when system population and resequencing delays, rather than individual link utilizations, have to be calculated