iffinder

Many topology projects use traceroute-like techniques to discover IP interfaces and how they're connected, including CAIDA's Macroscopic Topology Measurements running scamper on the Ark infrastructure. To create a topology that more accurately reflects the real network, we must also discover which of these interfaces belong to the same router. Iffinder, developed by Ken Keys at CAIDA, is a tool that attempts to do this. Email Ken Keys for comments.

Download

Download iffinder 1.38

About iffinder

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 is a strong suggestion that the two interfaces belong to the same network node. This method was described in J.-J. Pansiot and D. Grad's "On routes and multicast trees in the Internet" and R. Govindam and H. Tangmunarunkit's "Heuristics for Internet Map Discovery".

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 the scamper tool)

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
213531
32777
41058
5490
6307
7150
888
964
1038
1138
1217
1317
1411
158
166
172
181
191
202
213
234
241


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 (the predecessor to scamper) did a good job of finding interfaces within that range. However, the first 8 hops between the probing host in this iffinder run and the rest of the Internet were almost always the same, so the number of nodes covered by Record Route in this run was very small. Running this test from more and better-located hosts (say, every Ark monitor) gives more useful results.

Related Objects

See https://catalog.caida.org/software/iffinder/ to explore related objects to this document in the CAIDA Resource Catalog.
Published
Last Modified