Packet reordering

Les Cottrell, SLAC
SLAC Home Page


Packer Reordering is Not Pathological Network Behavior, Jon C. R. Bennett, Craig Partridge and Nicholas Shectman, IEEE/ACM Transactions on Networking , Vol. 7, No. 6, December 1999, p789) indicated that reoordering is highly prevalent on many links. The effect of re-ordering can cuase TCP performance issues since it can confuse the TCP congestion window algorithms.

We decided to see how prevalent reordeering is on the links to about 250 hosts that PingER monitors from SLAC.


For each host in turn:
  1. We sent 5 56 bytes pings separated by 1 second to each host. This was to prime caches etc. We looked to see whether any of these pings were successful. If not we noted it and went on to the following host (i.e. we skipped steps 2 and 3 below).
  2. We then sent 50 back to back 56 byte pings using the preload option of the NIKHEF ping and analyzed the response to extract and record the minimum/average/maximum response time, the loss, the inter packet separation, the number of packets out of order (a packet was considered out of order if its sequence number was less than the previous successfully received packet) and any pathologies such as duplicate packets.
  3. Step 2 was then repeated for 50 56 byte ping packets sent with a separation of 1 second and a timeout of 20 seconds.
We repeated the measurements with 1400 byte packets.


Of the ~ 250 hosts, ~6% did not respond to any of the 1st 5 pings (ICMP unreachable, ICMP time out, no response), ~2% did not respond to any flood pings but did respond to pings separated by 1 second and 1 in Poland gave duplicate pings. The table below shows some of the summary statistics of the measurements. F_ refers to the flood ping measurements, P_ refers to the 1 second separation pings. Min, Avg, Max refer to the minimum, average and maximum RTT for the responding hosts. Loss refers to the percentage packet loss. Rcv refers to the number of ping packets received from the 50 sent, Asym is the (F_Loss - P_Loss) / (F_Loss + P_Loss). d_ refers to the difference in the Flood ping and 1 second ping measurements. It is seen that Flood pings took longer RTT (median was 18 msec greater) than the 1 second separation pings. This is to be expected since the flood pings will cause more queuing. The generally positive asymmetry indicates that there is a greater probability of losing packets when using flood pings, again this is to be expected from queueing and overflows. There was little difference in the reordering when one moved from 56byte to 1400byte packets.
Summary statistics

Roughly 25% of the hosts monitored exhibit reordering. For the hosts that exhibited reordering on average 8 of the 50 packets were identified as being out of order. There is little correlation between the number of packets reordered for a host and the asymmetry (R2 ~ 0.011), or with the loss (R2 ~ 0.05) or average RTT (R2 ~ 0.1). The hosts were in 72 different countries, so we looked at the re-ordering by region. This is shown in the table below. It is seen that reordering is high (> 50%) to the developing world and to commercial Internet sites (.com and .net). Eastern Europe and E. Asia also have >: 25% of the hosts monitred exhibiting reordering.
Reorder table

Back to top

Created August 25, 2000, last update september 19,2000.
Comments to