CAIDA : tools : measurement : iffinder

Download iffinder 1.37

iffinder works by sending a "probe" UDP packet to an unused port on an interface address. Many routers will reply to such a packet with an ICMP PORT UNREACHABLE error with the source address set to that of the interface on the unicast route back to the prober. So probing one interface and getting this error from a different interface proves that the two interfaces belong to the same network node. This method was described in [2] and [3].

Iffinder can also discover new interfaces in several ways. Whenever iffinder discovers a new interface, it adds the interface to its list of probe targets.

IP Record Route [RFC 791]: Iffinder can use the IP RECORD ROUTE option in its probes. Not all routers support this option, and it is only capable of recording 9 addresses along the path, but nevertheless it can result in discovering many new interfaces. And since routers that support Record Route will record the address of the "far" (outgoing) interface on the probe packet's path, and a Port Unreachable probe to this interface will usually find a router's "nearest" interface, this will often result in discovering a pair of interfaces belonging to the same router.
ICMP errors from intermediate routers: If the source of the ICMP error was previously unknown, iffinder saves it. Additionally, since ICMP error packets contain the IP header of the original packet which caused the error, iffinder retrieves Record Route data from both the error packet and the embedded original packet. The original packet contains Record Route data that would have been lost otherwise.
The gateway given in an ICMP REDIRECT error: ICMP REDIRECT errors contain a preferred gateway address. If that address was previously unknown, iffinder saves it.
"/30 mates": Frequently, a link between two internal routers is defined as a /30 subnet, so the interfaces at ether end of the link have the same 30-bit network number and a 2-bit host number; one interface has the host number 1, and the other has host number 2. (Host numbers 0 and 3 are not valid.) Given a valid address within a /30 subnet, we define its "/30 mate" as the other address within that /30 subnet. For every known interface that is a valid /30 address, if iffinder did not already have its /30 mate in its list, iffinder will probe its /30 mate. Since iffinder is only guessing at the existance of this address, if the address does not respond iffinder will discard it (and never probe it again, unless some other means proves it exists).
IP Traceroute [RFC 1393]: When an intermediate node forwards a packet containing the IP Traceroute option, it should send an ICMP TRACEROUTE packet containing its own address back to the source. However, Initial experiments suggest that this option is very rarely supported, and that some hosts will even drop packets containing this option. Also, it reduces by 3 the number of addresses that can be recorded in the Record Route option. Using it would therefore be likely to make iffinder less effective, so we do not use this option in most runs.

When using Record Route or IP Traceroute, some probes result in an ICMP_PARAMPROB response or no reponse at all, if a router is buggy, configured to ignore Record Route, or whatever. In such cases, iffinder will retry the probe without IP options, often resulting in a useful response.

Operational details: To avoid conflicts with traceroute processes and other iffinder processes running on the same host, iffinder chooses its source port in the same way as traceroute, as a function of its process id.

Definitions:

experiment: a series of 1 to 3 probes run on a particular interface
failed experiment: an experiment with no useful result
probe: a single UDP packet sent to an interface
unroutable addrs: IANA reserved, loopback, private (RFC 1918), multicast
noise: ICMP messages received not for iffinder (e.g., for traceroute)
joins: pairs of interfaces that were found to belong to the same node (the current version of iffinder does not report this; instead, it records raw response data, which must be postprocessed)
new interfaces: interfaces not in the input, discovered by iffinder receiving responses
original interfaces: interfaces in the input (i.e., discovered by skitter)

An early versions of iffinder (without Record Route, Traceroute, ICMP REDIRECT, or /30 mating) was run on all0901-19lhrwaisin0801-25.nodest.act.ips, containing 357054 unique routable unicast addresses.

# started:                2000-09-26 18:13:22
# elapsed time:           17:36:47
# experiments:            359668
# failed experiments:     70203
# probes:                 505347
# responses
#  from unroutable addrs: 6
#  good (port unreach):   289465
#  other icmp errors:     35803
#  timeouts:              180073
#  noise:                 382
# joins:                  29893
# new interfaces:         2692
# total interfaces:       359668
# nodes with >1 iface:    18556
#  ifaces on such nodes:  48005
# single interfaces:      311663

About 13% of the interfaces were matched up with other interfaces.

Histogram data for matched interfaces:

# of interfaces	# of nodes with this many interfaces
2	13531
3	2777
4	1058
5	490
6	307
7	150
8	88
9	64
10	38
11	38
12	17
13	17
14	11
15	8
16	6
17	2
18	1
19	1
20	2
21	3
23	4
24	1

iffinder with Record Route support was run again on all0901-19lhrwaisin0801-25.nodest.act.ips. (A previous implementation of Record Route was found to be buggy, making the results previously reported here on the effectiveness of Record Route meaningless.) Summary of results:

# started:                2000-10-03 00:00:46
# elapsed time:           16:11:06
# experiments:            358516
# failed experiments:     228155
# probes:                 495507
# responses
#  from unroutable addrs: 6
#  good (port unreach):   130361
#  other icmp errors:     197572
#  timeouts:              167568
#  noise:                 24164
# joins:                  16676
# total interfaces:       358516
# new interfaces:         1540
#  by port unreachable:   799
#  by other icmp err:     729
#  by record route:       12
# nodes with >1 iface:    10321
#  ifaces on such nodes:  26775
# single interfaces:      331741

Previous experiments indicated that a large fraction of routers support Record Route. If the 9-hop range of Record Route covered a large set of addresses, the fact that Record Route in iffinder discovered only 12 previously unknown interfaces would suggest that skitter did a good job of finding interfaces within that range. However, the first 8 hops between the probing host (mapping-project2.caida.org) and the rest of the Internet are almost always the same, so the number of nodes covered by Record Route in this run was very small. Running this test from other locations (say, every skitter monitor) will hopefully give more useful results.

References

[1]: Daniel McRobb, kc claffy. Skitter. CAIDA, 1998. http://www.caida.org/tools/measurement/skitter/
[2]: J.-J. Pansiot and D. Grad. On routes and multicast trees in the Internet. ACM SIGCOMM Computer Communication Review, 28(1):41-50, January 1998
[3]: R. Govindam and H. Tangmunarunkit. Heuristics for Internet Map Discovery. Proceedings of the 2000 IEEE INFOCOM Conference, March 2000