Novel approaches to end-to-end packet reordering measurement

By providing the best-effort service, the Internet Protocol (IP) does not maintain the same order of packets sent out by a host. Therefore, due to the route change, parallelism inside a switch, and load-balancing schemes, IP packets can be received in an order different from the original one. Such packet reordering events could cause serious perfor-mance degradation in TCP and UDP applications. As a re-sult, a number of measurement methods have recently been proposed to enable any Internet host to detect packet re-ordering from itself to another host. However, these meth-ods have encountered a number of practical difficulties, such as rate-limiting and filtering imposed on ICMP and TCP SYN packets. Moreover, some of the methods can-not detect packet reordering in all scenarios. In this paper we present three new methods for end-to-end packet re-ordering measurement. Since these methods are based on the TCP data channel, the probing and response messages will not be affected by any intermediaries on an Internet path. We have validated and tested the methods in 20 most common systems and implemented them in a tool called POINTER. We also present measurement results obtained from 200 websites in the Internet.