ICMP Rate Limiting  Executive Summary Part 2: Detailed Study and List of Candidates

IEPM Home Page  IEPM Site Map  Network Monitoring  PingER  IEPM Papers and Presentations

Part 1 : Introduction : Primary Tools and Techniques

Slope of Number of Successful Packets vs Packet number :

The average slope was found to be 0 which indicated that most sites either did not perform rate-limiting on ICMP or else used a different technique for rate-limiting such as RED which would not be observabable through this technique.

Presented here is the histogram of the slope per month of these sites during the nine month period :
 

Likely Candidates:

Presented below is the list of candidates chosen for further study and their average slopes over the nine month period.

Table 1: Tail-drop slopes for Candidate sites

Node	Tail-drop Slope
concave.cs.wits.ac.za	-59.309
www.lbl.gov	-14.31183333
fnal.fnal.gov	-12.251
www.wits.ac.za	-12.13766667
wwwmics.er.doe.gov	-10.761375
dns1.arm.gov	-10.719625
www.ornl.gov	-10.511375
www.llnl.gov	-10.367875
ping.bnl.gov	-8.967125
eros.cnea.gov.ar	-6.203222222
www.utm.my	-4.6702
df.uba.ar	-4.244555556
www.uzsci.net	-3.7042
sun.ihep.ac.cn	-3.565666667
fisica.edu.uy	-3.32875
main.tirana.al	-3.13475
ffden-1.phys.uaf.edu	-2.335625
sci.am	-2.121142857
www.hepi.edu.ge	-2.105857143
www.bu.ac.th	-1.89375
www.unimas.my	-1.6534
beta.carnet.hr	-1.562
tnp.saha.ernet.in	-1.5574
mail2.starcom.co.ug	-1.5245
www.jinr.dubna.su	-1.521888889
magic.mn	-1.47425
dns1.vn	-1.4208
tifr.res.in	-1.389333333
satsun.sci.kz	-1.3815
www.lu.lv	-1.310857143
www.cs.ui.ac.id	-1.2484
kadri.ut.ee	-1.236285714
www.usm.my	-1.1382
ns.itep.ru	-1.128777778
www.ihep.su	-1.127333333
www.uct.ac.za	-1.096
moon.atomki.hu	-1.068111111
lhr.comsats.net.pk	-0.88625
www.ucr.ac.cr	-0.88625
www.iisc.ernet.in	-0.873
proxy.fm.intel.com	-0.848
bgcict.acad.bg	-0.834714286
cc.metu.edu.tr	-0.828571429
www-ribf.riken.go.jp	-0.823666667
www.hr	-0.8196
ping.lucas.lu.se	-0.814222222
www.dolphinics.no	-0.812222222
cni.md	-0.810428571
chapar.ipm.ac.ir	-0.799142857
if.usp.br	-0.774
dns.edu.cn	-0.757
csg-ippm.net.wisc.edu	-0.737333333
intrans.baku.az	-0.735142857
www.ht.hr	-0.727
nic.uniandes.edu.co	-0.674666667
pinger3.cs.waikato.ac.nz	-0.6665
ns1.waikato.ac.nz	-0.610777778
www.cab.cnea.gov.ar	-0.5835
ping.isnet.is	-0.5746
ns2.sri.ucl.ac.be	-0.571
julius.ktl.mii.lt	-0.540285714
ns.riken.go.jp	-0.5346
gamma.carnet.hr	-0.5162
traceroute.hkt.net	-0.515111111
g.root-servers.net	-0.511666667
www.itb.ac.id	-0.4884

Comparative study of Ping loss and Sting loss

Before discussing the results, we need to introduce a new metric we term Asymmetry.

Asymmetry:

Note that in some cases, Sting reports a negative loss. These results are anomalous and have to be discarded.

The plot below shows the method asymmetries for the selected hosts :

The following diagram shows a plot of the histogram and cumulative frequency of the asymmetry calculated for these sites based on Table 1.

The following is a scatter plot of the tail-drop slope calculated for the month of March ( the most recent data at that point in time, since the plots were generated in April 2000) versus the method asymmetry from the ping-vs-sting results. The likeliest candidates are those that lie in the bottom right-hand quadrant. We see that most of the candidates investigated lie in this plane The site in Malaysia emerges as a very strong candidate for possible rate-limiting on the basis of data above.
img SRC="slope-vs-asymmetry.jpg" height=447 width=563>

Higher Statistics Measurements

Longer Term Measurement

Note:

1. We ignore possible warnings issued by Sting including Route Change since they seem to be very frequent.
2. Both the tables, Table 2 and Table 3 are based on stings of 100 packets each while Table 4 relies on Sting of 1000 packets each. Hence the number of independent Sting measurements are lower for Table 4 even though both Table 3 and Table 4 are based on about the same amount of data (since 1000 packet Stings take longer to run than 100 packet Stings)

The graph below shows the asymmetry distribution for the data in Table 3.

Larger number of probes per sample measurement

Ping Blocking :

Results on Port 80

Results on Port 7:

A Curious Case :

Comparison of Ping vs. SYN/ACK

For each candidate, with an open port, we used oceanus.slac.stanford.edu (a Sun Ultra 5_10 running SunOS 5.6) to send one ping (we used the NIKHEF ping since it allowed us to set the timeout) followed by one synack and recorded the round trip time (RTT) or loss. Each measurement was also timestamped. In both cases the timeout options were set to 10 seconds. When the list of hosts to test was completed a the script slept for a random delay before repeating the cycle. The sleep delay was typically 209 seconds + epsilon, where epsilon was a random number selected from 0 to 199 seconds and the random distribution was flat. Each cycle through the list took about 8 minutes and was typically repeated 20-30 times. We repeated these sets of measurement cycles with different sets of hosts at various times between Thursday June 15, 2000 16:21:44 PDT and August 13, 2000 each time the new measurements being appended to those measured previously. We also extended the measurements cover the 76 PingER Beacon sites. There was some overlap between the hosts chosen above and the Beacons. The total number of hosts that we compared pings with synack was about 111.

The recorded data was then analyzed to generate RTT time series, and synack loss asymmetries:

• For most of the hosts the RTTs measured by ping and synack track one another very well. This suggests that for most of the sites there is no rate limiting that is adversely affecting ping compared to synack.
• The www.iisc.ernet.in.site almost always has 100% ping packet loss but it is accessible much of the time via synack. There is probably some ping blocking going on between SLAC and this site.
• In 9 cases we could not synack the chosen host since it did not respond to any of ports 80 (www), 25 (smtp) or 21 (ftp control), so we chose an alternate host in the same domain that did respond to port 80. The alternates were www.ac.il, www.cs.wisc.edu, www.cs.waikato.ac.nz, www.utexas.edu, www.slac.stanford.edu, www.sanet.sk, www.ethz.ch, www.carnet.hr, and www.ciemat.es.
• We observed (not shown here) that the host lhr.comsats.net.pk would appear to have no synack response for extended periods, yet ping would work fine. Maybe the port was disabled. We tried another port and the difference went away.
• In the case of ns1.waikato.ac.nz (140.200.128.13) the ping losses are much more frequent than the synack losses. This may be caused by some ICMP rate limiting but not outright blocking. To investigate this further we also made measurements with www.cs.waikato.ac.nz (130.217.241.20) and www.waikato.ac.nz (130.217.66.16) in these cases there was minimal difference in the ping and synack measurements. It is also noteworthy that the ping losses were much higher when measured on June 18th than when the measurements were repeated on or after August 12 (the sequence number for the boundary between these two sets of measurements was about 540). It is possible that the cause of the asymmetry has been removed.
• Several of the hosts (e.g. cni.md, concave.cs.wits.ac.za, www.hr, www.wits.ac.za) often have RTTs of > 2 seconds as measured by ping and when this happens the synacks are lost. We ran into a problem with the first synack open always failing if the RTT was > 2 seconds, even though the timeout was set for 10 seconds for both synack and sting. This is particularly illustrated by the time series for cni.md, satsun.sci.kz, sun.ihep.ac.sn, ttip,saha.ernet.in, and www.hr, where one typically sees synack losses when the ping RTT is > 2 second (2000 ms). It is also less apparent for other hosts.
• The reported resolution of the NIKHEF ping RTT reports was was 3 digits (synack reports with microsecond resolution) so quantization in the ping RTTs can be observed in some cases (see for example www.ac.il and www.ethz.ch).
• Some RTT distributions show multi-modal behavior in both the ping and synack measurements that is not caused by the quantization effect mentioned above, see for example www.ph.unimelb.ac.au and www.singnet.com.sg. In the latter case with RTTs usually centered around 202 or 220 msec. We used traceroute to look at the router hops for www.singnet.com.sg, but the route appeared stable and we could see no correlation of the 2 RTTs with different routes reported by traceroute. A typical traceroute is seen below and the bimodal effect seems to start at hop 10 (from the delays this would appear to be the trans-Pacific hop).

  Tue Aug 15 15:03:30 2000(UTC) from flora01 to www.singnet.com.sg
   traceroute: Warning: ckecksums disabled
   traceroute to 165.21.101.31 (165.21.101.31), 30 hops max, 40 byte packets
    1  RTR-CORE1.SLAC.Stanford.EDU (134.79.19.2)  0.770 ms  0.468 ms  0.444 ms
    2  RTR-CGB6.SLAC.Stanford.EDU (134.79.135.6)  0.897 ms  0.812 ms  0.770 ms
    3  RTR-CGB6.SLAC.Stanford.EDU (134.79.135.6)  0.945 ms  0.802 ms  0.826 ms
    4  RTR-DMZ.SLAC.Stanford.EDU (134.79.111.4)  1.849 ms ESNET-A-GATEWAY.SLAC.Stanford.EDU (192.68.191.18)  0.838 ms  0.814 ms
    5  ames1-atms.es.net (134.55.24.19)  6.058 ms  5.508 ms  5.993 ms
    6  mae-west.above.net (198.32.136.31)  10.925 ms  7.234 ms  7.385 ms
    7  core2-mae-west-oc3.sjc.above.net (207.126.96.105)  7.806 ms  6.704 ms  9.349 ms
    8  main3-core2.sjc.above.net (209.249.0.58)  8.638 ms  7.559 ms  7.334 ms
    9  singtel-abovenet.sjc.us.singtel.com.sg (209.249.140.26)  8.792 ms  9.375 ms  10.200 ms
   10  POS0-0.above-core1.ix.singtel.com (202.160.250.41)  203.180 ms  200.765 ms  219.874 ms
   11  POS1-1.tp-core1.ix.singtel.com (202.160.250.33)  218.089 ms  217.446 ms  200.127 ms
   12  202.160.250.170 (202.160.250.170)  216.901 ms  217.422 ms  219.318 ms
   13  202.160.250.154 (202.160.250.154)  218.037 ms  218.126 ms  218.287 ms
   14  FE-2-0-0-eunos.singnet.com.sg (165.21.12.67)  219.083 ms  202.441 ms  203.831 ms
   15  www.singnet.com.sg (165.21.101.31)  222.553 ms  219.096 ms  201.928 ms
  

• It is often not possible to find a host at a site that responds to both pings and to one of the TCP ports 80, 25 or 21. For example of 248 hosts monitored by ping from SLAC in December 2000, 115 did not respond to port 80, 107 did not respond to port 25 and 124 did not respond to port 21. In addition, 77 did not respond to any of the 3 ports, 56 responded to only one port, 56 to only two ports and 50 to all 3 ports. Even when one finds such a host and port, it may not continue to respond. For about 100 such hosts that responded in June 2000, by December 2000, 3 of the hosts were no longer responding to the chosen one of the above TCP ports. We were able to find an alternate port in 2 of the cases.

The minimum synack RTT asymmetry:

Comparison of 100 Byte vs 1000 Byte Pings:

To investigate this we took the monthly median ping packet losses measured by PingER from SLAC to about 200 sites from January 1998 through June 2000.

Loss Asymmetry measured from SLAC to all sites.

Summary

1. measuring the slope of the loss as a function of the sequence number in a series of 10 consecutive pings (tail-drop slopes);
2. comparing ping with a non-ICMP based mechanism (sting) for measuring packet loss;
3. comparing ping with a second non-ICMP based mechanism (synack for measuring packet loss;
4. comparing the ping losses for small (100Byte) and larger (1000Byte) packets.

The early results have been somewhat mixed in identifying which sites actually carry out rate-limiting. We ran into problems with pathologies with sting, for example negative packet losses, that reduced the number of candidate sites that sting could be used for comparing losses with ping. Also for both the TCP (non-ICMP) based mechanisms (sting and synack) we were unable to find a suitable open port for about 20% of the candidate sites. In addition, probing such ports can be misinterpreted as a host scan and raise security alerts. Using sting we were able to identify 4 sites which had high tail-drop slopes and anomalously high method (ping vs. sting) asymmetries.

One would imagine that opening a session to a port as is done by synack would take more effort (longer code path etc.) than responding to a simple ping. However, surprisingly it appears that on average the response (RTT) for ping is slower than for synack, however the difference varies from host to host and 41% had ping RTTs < synack RTTs. The ping losses also appear to be larger on average than the synack losses, this might be an indication of ping rate limiting. However again there is a lot of variability from host to host and about 39% of the hosts have lower ping losses than synack losses. By comparing the synack and ping RTT time series we identified:

• one host out of 44 candidates where there is probably ping blocking between it and SLAC;
• one host where there was a much higher ping loss (~35%) compared to synack loss (0.24%), this may be caused by ping rate limiting, and we will follow up with the site's network people.

We also compared the results from the 4 methods to see whether they correlated well with each other. To do this we scatter plotted the sting and size loss asymmetries and the slopes versus the synack asymmetries. The results are shown below. It can be seen that there is a weak positive correlation (R² ~ 0.2) between the synack and sting asymmetries, but no noticeable correlation between the synack asymmetries and the slopes or the size asymmetries. Since it appears that comparing losses from ping with other non-ICMP methods such as synack and sting is more likely to directly identify pathologies that would preferentially affect pings, the lack of correlation between synack and the tail-drop slopes or size asymmetries does not bode well for identifying rate limiting by examining existing PingER data for tail-drop slopes or the difference in losses for 100Byte and 1000Byte pings.

Unfortunately neither Surveyor nor RIPE monitors are situtaed at many, if any of the the candidate sites, so we cannot use Surveyor or RIPE loss measurements to validate the rate limiting conjectures.