On Reorder Density and its Application to Characterization of Packet Reordering

A formal approach for characterizing, evaluating and modeling packet reordering is presented. Reordering is, a phenomenon that is likely to become increasingly common on Internet, and it can have an adverse impact on end-toend performance and network resource utilization. Reorder Density (RD) is a comprehensive metric for reordering. Several properties of RD are presented that provide insight into the nature of reordering present in a sequence. Based on measurements of packet reordering, certain basic patterns of reordering that are prevalent on the Internet are identified. By focusing on these basic patterns, a model is developed for reordering in networks involving two parallel paths, using a simple loadbalancing scenario as an example. The model is verified using an emulation testbed. 1