Iffinder, developed by Ken Keys at CAIDA, is a tool that attempts to do this. Email Ken Keys for comments.
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.
iffinder discovers a new interface, it adds the interface
to its list of probe targets.
- IP Record Route [RFC 791]
Iffindercan 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,
iffindersaves it. Additionally, since ICMP error packets contain the IP header of the original packet which caused the error,
iffinderretrieves 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,
- "/30 mates"
- Frequently, a link between two internal routers is defined as a
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
iffinderdid not already have its /30 mate in its list,
iffinderwill probe its /30 mate. Since
iffinderis only guessing at the existance of this address, if the address does not respond
iffinderwill 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
iffinderless 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.
- a series of 1 to 3 probes run on a particular interface
- failed experiment
- an experiment with no useful result
- a single UDP packet sent to an interface
- unroutable addrs
- IANA reserved, loopback, private (RFC 1918), multicast
- ICMP messages received not for iffinder (e.g., for traceroute)
- 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: 311663About 13% of the interfaces were matched up with other interfaces.
Histogram data for matched interfaces:
|# of interfaces||# of nodes with this many interfaces|
iffinder with Record Route support was run again on
(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: 331741Previous 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.