A theoretical foundation, metrics and modeling of packet reordering and methodology of delay modeling using inter-packet gaps

Abstract

Increasing complexity, heterogeneity and variety of traffic in the networks makes it essential to understand the variations in delay, jitter, packet reordering, etc., thus leading to characterization and prediction of networks' performance, suitability to applications, scalability, etc. This research proposes a method for representation of packet reordering, metrics to capture reordering in a packet sequence and models relating traffic load-splitting scenarios to reordering. Delay models are investigated with respect to network conditions and properties of probing streams. Tradeoffs in the use of packet delay versus inter-packet gap for end-to-end characterization are considered to overcome the effects of correlations. Increased parallelism required to handle high link speeds, large routing tables, wireless ad hoc routing, and enhancement features such as QoS and overlay routing, are some of the factors that point to an increase in reordering on Internet. Unchecked, packet reordering will have a significant detrimental effect on the end-to-end performance, while resources required for dealing with reordering will grow significantly. A formal representation of packet reordering is presented based on reorder event, reorder set, reorder segment, and basic patterns. A primary reorder event occurs when a packet is delayed or arrives early, with other affected packets said to have undergone secondary event(s). All the events in a sequence form a reorder set. A principle of conservation is derived for the displacement, demonstrating the conservation of the overall displacement in a sequence, encompassing the interdependence between packet displacements. Furthermore, three basic reordering patterns are identified: independent reordering (IR) with only one primary event, and embedded reordering (ER), and overlapping reordering (OR) with only two entangled primary events. "Reorder Density" (RD) metric is defined for measurement and characterization of packet reordering. Properties of RD are derived. RD maintains the interdependency between the packets using principle of conservation of reordering in a sequence, yet it maps to the probability density function for displacement of an arbitrary packet, allowing its use in systems approach, where subnets can be treated as systems and associated with overall responses to packet streams in terms of reordering. Reorder response, defined as the RD of a received sequence when packets are sent in-order at the sender, captures reordering introduced by a network. Under stationary operating conditions, it is shown that the reorder response of the network formed by cascading two subnets is equal to the convolution of the reorder responses of individual subnets. Recovery from reordering at transport or application levels requires buffering of out-of-order packets. The concept of "Reorder Buffer-occupancy Density" (RBD) is based on the occupancy of a recovery buffer. Measurement approaches that capture such a resource requirement can be considered as useful metrics for packet reordering as well. An ideal metric for packet reordering will capture reordering accurately, provide insight into nature of reordering, and help in analysis and mitigation of its adverse effects. RD, RBD and other proposed metrics for reordering are evaluated using a framework developed for comparison and analysis of reorder metrics. The framework consists of attributes that include capturing reordering, low sensitivity to lost and duplicated packets in reorder measurements, usefulness, simplicity, evaluation complexity, etc. Models for packet reordering in terms of RD and RBD are presented for two-path load splitting, limiting reordering to basic pattern formations. Use of basic patterns is motivated by measurements over the Internet, which shows most of the reordering patterns as basic, i.e., IR, ER and/or OR. In the case of RD, general models of packet reordering are presented for both two-path and multi-path load splitting. All these models are verified using emulated topologies. The end-to-end delay of packets in data streams is characterized with emphasis on effects due to cross traffic, sending rate, and packet size. Measurements indicate that modeling delay of a packet stream with high sending rates, as a fraction of bandwidth, is difficult due to the correlations among the delay values. The correlations among inter-packet gaps (IPG) at these rates, however, are negligible. At lower sending rates, the delay correlations are negligible, and the distribution of delay can be used as a delay model. We exploit the relation between delay and IPG to show how a Markov process can be used to approximate end-to-end delay.