Skip to Content
[CAIDA - Cooperative Association for Internet Data Analysis logo]
The Cooperative Association for Internet Data Analysis
Motu Dealiasing Tool
Motu is a tool for dealiasing pairs of IPv4 addresses. It is based on the IP Prespecified Timestamp dealiasing method described in "Resolving IP Aliases with Prespecified Timestamps", Sherry et al., IMC'10

Download

Motu v1.0.1 was released on October 5, 2011.

Dependencies

Motu depends on both mper and rb-mperio.

Usage

usage: motu [-?fv] [-n concurrency] [-s spacing] [-l logfile]
            [-P probe-method] -p mperport 
            -c candidates | -b suit-results | IPa IPb
    -p, --mper-port=NUM              mper control socket port (REQUIRED)
    -c, --candidates=PATH            file with candidate pair information
    -b, --suitability-results=PATH   file with results of suitability checking
    -n, --concurrency=NUM            max pairs to dealias concurrently (default: unlimited)
    -s, --spacing=NUM                spacing (ms) between probes (default: 0)
    -f, --full                       show full result output
    -v, --[no-]verbose               show detailed progress
    -l, --log=PATH                   mper command/result message log path
    -P, --probe-method=METHOD        the probing method to use - icmp (default) or udp
    -?, --help                       show this message
The tool has three probing modes; full-dealiasing, suitability checking and educated-dealiasing.

The most common, and simple, is full dealiasing, where a pair (or multiple pairs) of candidate addresses are provided and the tool attempts to determine if they are aliases.

The other modes split the algorithm into two pieces; the first of which is referred to as "Suitability Checking". Suitability checking only requires one address and it attempts to determine if the address is a viable candidate for dealiasing using prespecified timestamps. Once an address has been run through the suitability checking logic, it is classified as INELIGIBLE (meaning that it cannot be used at all for dealiasing), or as one of three pass types (two, three or four stamps). These results can be used with some additional heuristics to help determine which pairs should be probed with the remainder of the dealiasing algorithm using the "Educated Dealiasing" mode.

The educated dealiasing mode takes post-processed suitability results and uses them to bypass some of the initial probing usually needed when naively dealiasing a pair of addresses. To make use of this, the suitability results for the desired candidate pair should be combined into the standard output format (as described below) and passed to the tool using the --suitability-results option. This will force the tool to use the given suitability results and move directly to the alias validity check. Note that care should be taken when doing this as the stamping behavior may change over time so the two steps should be done as close together as possible.

There are two ways to provide candidate addresses to the tool; explicitly on the command line, or in a candidate list file.

If providing pairs, the tool accepts two formats; space separated and comma separated. For example, "130.217.250.13 130.217.250.15" or "130.217.250.13,130.217.250.15".

If these are given in a candidate file, there must be one pair per line. If a single address is given per line, the tool will perform only the suitability check as described above.

The tool can also accept space separated and comma separated pairs on the command line, but if space separated pairs are given, the tool will generate candidate pairs by moving left to right. For example, "A B C D" will create two pairs, "A,B C,D". As with the candidate file, if only one address is given it will be used as a suitability-only candidate. There is a subtle difference here when compared to the candidate file; if an odd number of space-separated addresses are given, the last address will only have the suitability check run as the tool cannot determine which address to pair it with.

Normal Output Format

In the normal mode, there is one line of output for each pair of candidate addresses (IPa,IPb), as follows:

<candidate_pair>|<suitability_check>|<alias_validity_check>|<reverse_path>|<alias_check>|<shared_clk>|<distance_loop>|<overall>
For example:
"65.122.236.13,65.122.236.21|P2S5,P2S5|P2S,P2S|-|P2S|PSC|PDI|ALIAS-WEAK"
The structure and possible values in each section are listed below:

Candidate Pair (mandatory)

IPa,IPb e.g. 192.168.1.1,192.168.1.2

Suitability Check (mandatory)

<result_a>,<result_b>
The suitability check is performed on each address.
ResultDefinitionNotes
P4SxPass, 4 Stamps
P3SxPass, 3 Stamps
P2SxPass, 2 Stamps
F1SxFail, 1 Stamp
FNSxFail, No Stamp
FNRxFail, No Reply
FESxFail, Extra Stamp
FVSxFail, Varying StampMultiple stamping behaviours were observed
(where x is the number of probes that were replied to)

Alias Validity Check

<result_a>,<result_b>
The alias validity check is only performed if both IPa and IPb pass the suitability check.

This check issues probes for (A|ABAB) and (B|BABA) and performs per interface analysis.

ResultDefinitionNotes
P4SPass, 4 Stamps
P3SPass, 3 StampsWill likely fail the Alias Check
P2SPass, 2 Stamps
F1SFail, 1 Stamp
FNSFail, No Stamp
FNRFail, No Reply
FESFail, Extra Stamp
FVSFail, Varying StampMultiple stamping behaviours were observed
FRNFail, Reverse path Non-monotonicInterface is on the reverse path, timestamps were non-monotonic (they decreased) (NOALIAS-STRONG)
FRGFail, Reverse path GapInterface is on the reverse path, timestamps increment with >1ms gap between timestamps (NOALIAS-WEAK)
FRUFail, Reverse path UnknownInterface probably on the reverse path, inconclusive timestamps (UNKNOWN-NOALIAS)

Reverse Path Check

The reverse path check is only performed if (IPa==P2S && IPb==F1S) || (IPa==F1S && IPb==P2S)

Works by probing the P2S interface A with (A|BABA) to determine if B is in the return path from A.

Note that a "Pass" in this test is in the context of the overall dealias result. It indicates that a pair has "passed" the reverse path check disproving the hypothesis that one address is in the reverse path. As such, the pair will undergo further testing to determine if they are aliases. A "Fail" indicates that the pair has failed the overall alias check because one address is in the reverse path from the other, and as such are not aliases.

ResultDefinitionNotes
PNSPass, No StampNot on the reverse path. Sent to Distance Check
P1SPass, 1 StampNot on the reverse path. Sent to Distance Check
FNRFail, No Reply
FVSFail, Varying StampMultiple stamping behaviours were observed
F2Nx/F2Gx/F2UFail, 2 StampsB is in the fwd path, but not reverse (see FRN/FRG/FRU above). Where 'x' gives the number of probes that were used to make the determination.
F3Nx/F3Gx/F3UFail, 3 StampsB is in both fwd and reverse path (see FRN/FRG/FRU above). Where 'x' gives the number of probes that were used to make the determination.
F4SFail, 4 StampsUnexpected result (ERROR)

Alias Check

The alias check is only performed if both IPa and IPb pass the validity check. It uses the same probe responses as the Alias Validity Check, but it performs analysis on the pair as a whole.

ResultDefinitionNotes
P4SPass, 4 StampsIndicates an alias
F3SFail, 3 StampsResults in an error condition as 3 stampers are not understood
P2SPass, 2 Stamps
FIRFail, Insufficient Replies50% total replies are required (this is a criteria from Sherry's algorithm that of the combined set of probes to both targets (10 by default), 50% must respond with at least two stamps

Shared Clock Test

The shared clock test is only performed if the alias check test is passed with the P2S flag, indicating that the replies were stamped twice.

ResultDefinitionNotes
PSCPass, Shared Clock
PMEPass, Midnight/Epoch
FDTFail, Decreasing Timestamp
F90Fail, less than 90% timestamp consistency

Distance Test

The distance test is preformed if the shared clock test is passed with the PSC flag, or the alias validity check results in P2S,F1S (and the reverse path check determines B is not on the reverse path).

ResultDefinitionNotes
PDIPass, DistanceThe two addresses have equal return path lengths
FDIFail, DistanceThe return path length differs between addresses
FNRxFail, No ReplyWhere x is the number of replies
FTVFail, TTL VarianceWithin probes to a single interface

Overall Result (mandatory)

The overall value is the end result of performing the dealias algorithm on the candidate pair.

ResultDefinitionNotes
ALIASConfirmed as aliases
ALIAS-WEAKConfirmed as aliasesA 2 Stamp interface and a 1 Stamp interface which passed the distance check
ALIAS-STRONG-1Confirmed as aliasesBoth interfaces are 4 Stamp
ALIAS-STRONG-2Confirmed as aliasesEither two 2 Stamp interfaces, or a 2 Stamp and a 4 Stamp interface, which passed Shared Clock and Distance checks
NOALIAS-WEAKNot aliasesLow-confidence
NOALIAS-STRONGNot aliasesHigh-confidence
UNKNOWNA determination could not be made
UNKNOWN-REPROBEA determination could not be madeMay be resolved by reprobing the pair
UNKNOWN-ALIASA determination could not be madeIt is likely the pair are aliases
UNKNOWN-NOALIASA determination could not be madeIt is likely the pair are not aliases
INELIGIBLEAt least one candidate interface was not suitable
ERRORUnexpected ResultLikely caused by some stamping behavior not yet understood

Full Output Format

If the --full mode is specified, additional lines will be output by the tool showing the full details for each probe response that is received. The format of these lines is as follows:

"< <targets>|<destination>|<stamps>|<timestamps>|<reply_ttl>|<rtt>"
For example:
"< 65.122.236.13,65.122.236.21|A|ABAB|65.122.236.13=3256451247,65.122.236.21=3256451247|243|27.308"
Note that the leading '<' is an explicit character to indicate this was a reply received by the tool (in keeping with the convention used by mper-ping).

Targets (mandatory)

This is an <IP>,<IP> pair which gives the mapping from IP address to the 'A' and 'B' designations used to describe the probe structure. Note that these do not necessarily match the A and B of the candidate pair.

For example, given a target definition of "130.217.250.13,192.172.226.55", "A" will be used to refer to "130.217.250.13" and "B" will be used to refer to "192.172.226.55".

Destination | Stamps (mandatory)

Indicates which (A or B) address the probe was targeted to, and also the format of the prespecified addresses loaded into the timestamp option.

e.g. for the dealiasing, this could be A|ABAB

Timestamp Values

Gives the stamps that were in the response to the probe. All interfaces and stamps up to the pointer in the option are listed. If mper is able to detect a change in the types of options included in the reply (for example if the timestamp prespecified option is loaded in the outgoing probe, but the incoming reply has no options), then it will append "ALTERED" to the list of timestamps. This is also capable of detecting a change in option types. For example, it can detect the case where a probe is sent with the prespecified timestamp option, and the reply has a "no-op" option instead.

The format for these stamps are as follows:

"<TS IP 1>=<TS STAMP 1>,<TS IP 2>=<TS STAMP 2>,<TS IP 3>=<TS STAMP 3>,<TS IP 4>=<TS STAMP 4>[,ALTERED]"
For example:
"65.122.236.13=3256451247,65.122.236.21=3256451247"
If the timestamp option has been stripped, this field will simply show:
",ALTERED"

Reply TTL (mandatory)

Gives the ttl of the response packet

Reply RTT (mandatory)

Gives the round trip time for the probe

Differences from the original algorithm

The dealiasing process and classification implemented in this tool differs slightly from the original algorithm described by Sherry et al..

As outlined in the above OUTPUT FORMAT section, we provide a total of 11 overall outcomes from dealising whereas the original algorithm only describes three (alias, non-alias and unknown). These come as a result of investigating the causes of the various behaviors, and so we can give more specific results. We split the alias category into ALIAS, ALIAS-WEAK and ALIAS-STRONG. As the names indicate, these are are all aliases, but the tool has been able to give some indication of the confidence of the classification. Similar sub-categories are used for NOALIAS also. The UNKNOWN category is split into UNKNOWN, UNKNOWN-REPROBE, UNKNOWN-ALIAS, UNKNWON-NOALIAS. UNKNOWN indicates that the tool is not able to make any determination of the pair of addresses. UNKNOWN-REPROBE indicates that the results of probing are possibly transient and simply re-running the tool may allow a determination to be made. UNKNOWN-ALIAS indicates that the tool is not able to make a determination whether the addresses are aliases, but it suspects that they may be. Similarly, UNKNWON-NOALIAS indicates an inability to classify the addresses, but they may not be aliases.

There are also additional heuristics we have developed to detect cases where the addresses appear to be aliases, but one is actually on the reverse path from the other. These are the only cases where we declare non-aliases.

In the original description of the algorithm, the reverse path distance check was performed only when one address returned two stamps to (A|ABAB) and the other returned one stamp. We perform this check even when both addresses return two stamps to give an even stronger alias result. A failure of the test will not result in a non-alias being declared (the overall result will be ALIAS), but a pass will result in an overall classification of ALIAS-STRONG.

Overall Statistics (motu-stats)

motu-stats is a script to carry out some basic overall analysis of a dealiasing run.

The script takes the motu results output and generates statistics for each of the sub-components that are described in the "Output Format" section above.

usage: motu-stats [--histogram] motu_output_file

Sample output for a dealiasing run with 1000 pairs is shown below, annotated with descriptions of the tables displayed.

Suitability Check

Total candidate pairs: 1000
Total interfaces tested for suitability: 2000

Suitability Stats:
Probing for (D|DXXX) and (D|DDDD)
Classification	# IPs	% of IPs
======|FAILURE CONDITIONS|======
Unresponsive	791	39.55%
Inconsistent	327	16.35%
Extra Stamp	7	0.35%
Zero Stamps	277	13.85%
One Stamp	286	14.30%
=======|PASS CONDITIONS|========
Two Stamps	156	7.80%
Three Stamps	0	0.00%
Four Stamps	156	7.80%
--------------------------------
TOTAL		2000	100%
================================
Number of pairs which passed suitability check: 73

Probe Response Stats:
Resp/Atmpt	Frequency
------------------------
0/5		779	*
1/5		12	* both included in 'Unresponsive' count above
2/5		9
3/5		16
4/5		22
5/5		1162

Description

The Suitability Check table gives a per-interface break-down of the number of interfaces which exhibit each characteristic. A minimum of five probes, and a maximum of ten have been sent to each interface during this check. The Unresponsive category indicates that for either the (D|DXXX) or (D|DDDD) set of probes (five each), less than two replies were received.

The Probe Response Stats table gives an indication of the distribution of response numbers. Ideally all probe sets would receive 5 responses. Interfaces which are in the middle of the range (2-3 responses) could perhaps be caused by rate limiting; consider increasing the inter-probe spacing time.

Stats LabelRaw Code
UnresponsiveFNR
InconsistentFVS
Extra StampFES
Zero StampsFNS
One StampF1S
Two StampsP2S
Three StampsP3S
Four StampsP4S

Alias Validity Check

Alias Validity Check Stats:
Probing (A|ABAB) for each IP
Classification	# IPs	% of IPs
======|FAILURE CONDITIONS|======
Unresponsive	0	0.00%
Inconsistent	0	0.00%
No Stamp	0	0.00%
One Stamp	12	8.22%
RP TS Decrease	0	0.00%
RP TS Gap	0	0.00%
RP TS Unknown	0	0.00%
=======|PASS CONDITIONS|========
Two Stamp	6	4.11%
Three Stamp	0	0.00%
Four Stamp	128	87.67%
--------------------------------
TOTAL		146	100%
================================
Number of pairs which passed validity check: 67

Description

The Alias Validity Check table gives a per-interface breakdown of the behaviors that are seen when an interface is probed with the prespecified address pattern (A|ABAB).

Stats LabelRaw Code
RP TS DecreaseFRD
RP TS GapFRG
RP TS UnknownFRU

Return Path Check

Return Path Check Stats:
Probing (A|BABA)
Classification	# Pairs	% of Pairs
======|FAILURE CONDITIONS|======
Unresponsive	0	0.00%
Inconsistent	0	0.00%
2 Stamp (N-M)	0	0.00%
2 Stamp (Gap)	0	0.00%
2 Stamp (Unk)	0	0.00%
3 Stamp (N-M)	0	0.00%
3 Stamp (Gap)	0	0.00%
3 Stamp (Unk)	0	0.00%
4 Stamp (ERR)	0	0.00%
=======|PASS CONDITIONS|========
No Stamp	0	0.00%
1 Stamp		0	0.00%
--------------------------------
TOTAL		0	0%
================================

Description

The return path check is executed whenever a two stamp (P2S) address is paired with a one stamp (F1S) address based on (A|ABAB) and (B|BABA) probing. If the results are either two or three stamps, the timestamps are compared to determine how strong the non-alias classification can be. Non-Monotonic timestamps result in a NOALIAS-STRONG classification while a gap (increase) of > 1ms causes a classification of NOALIAS-WEAK. If either no stamps, or one stamp is seen, the pair is sent to the distance check to ascertain whether it can be classified as weak aliases.

Stats LabelRaw Code
1 StampP1S
No StampPNS
2 Stamp (N-M)F2N
2 Stamp (Gap)F2G
2 Stamp (Unk)F2U
3 Stamp (N-M)F3N
3 Stamp (Gap)F3G
3 Stamp (Unk)F3U
4 Stamp (ERR)F4S

Alias Check

Alias Check Stats:
Probing (A|ABAB) and (B|BABA)
Classification	# Pairs	% of Pairs
======|FAILURE CONDITIONS|======
<5 Replies	0	0.00%
Three Stamps	0	0.00%
=======|PASS CONDITIONS|========
Two Stamps	3	4.48%
Four Stamps	64	95.52%
--------------------------------
TOTAL		67	100%
================================

Description

The alias check is performed once the alias validity check has been passed with either two, three or four stamps. It requires that at least 50% (5/10 in the current implementation) of the validity check probes have received replies. For a pair to pass the Alias Check, both interfaces must have stamped probes two or four times. Three stampers are not understood and so are failed with an overall verdict of "ERROR". Two stampers are passed through to the shared clock test and four stampers are declared aliases.

Stats LabelRaw Code
<5 RepliesFIR
Three StampsF3S
Two StampsP2S
Four StampsP4S

Shared Clock Check

Shared Clock Check Stats:
Timestamps from (A|ABAB) and (B|BABA)
Classification	# Pairs	% of Pairs
======|FAILURE CONDITIONS|======
Decreasing TS	0	0.00%
TS Variance	0	0.00%
=======|PASS CONDITIONS|========
Shared Clock	3	100.00%
Midnight/Epoch	0	0.00%
--------------------------------
TOTAL		3	100%
================================

Description

Once a pair has passed the alias check with either two P2S addresses, or one P2S and one P4S interface, it is run through the shared clock check to determine whether both interfaces share the same timestamp clock. If a decreasing clock is ever observed, that is, the timestamp values decrease between stamps for (A|ABAB), then the pair cannot be aliases (unless the clock has been shifted at the exact moment we probed). Otherwise, if the stamps never decrease, we require 90% of probes to be filled with consistent times. That is, all stamp values within a probe must be identical for 90% of probes. The other possibility is a seemingly large increase between stamps for A and B in (A|ABAB). If these are resolved to be a midnight offset for A, and an epoch stamp for B, then we consider this a pass based on additional probes to (B|AAAA) (which must also exhibit this behavior).

Stats LabelRaw Code
Decreasing TSFDT
TS VarianceF90
Shared ClockPSC
Midnight/EpochPME

Distance Check

Distance/Loop Check Stats:
Classification	# Pairs	% of Pairs
======|FAILURE CONDITIONS|======
Unresponsive	0	0.00%
TTL Variance	0	0.00%
Distance	1	33.33%
=======|PASS CONDITIONS|========
Distance	2	66.67%
--------------------------------
TOTAL		3	100%
================================

Description

The distance check is used as a weak test to determine that two addresses are equidistant from the vantage point which is dealiasing them. The distance check is used in two situations; the first is when two addresses pass the alias check with either two or four stamps. The distance check is used in this case to provide a stronger alias classification. The second case that the check is used for is when a pair has one two stamp address and one single stamp address. In this case the distance check is used to ensure that one of the addresses is not on the reverse path from the other. We call this a weaker alias because it is possible for the distance check to be invalidated by asymmetric load balancing on the reverse path.

Stats LabelRaw Code
TTL VarianceFTV
TS VarianceF90
Distance [fail]FDI
Distance [pass]PDI

Overall Verdicts

Overall Verdicts:
Classification		# Pairs	% of Pairs
=========|FAILURE CONDITIONS|=========
Non-Alias Strong	0	0.00%
Non-Alias Weak		0	0.00%
Ineligible		914	91.40%
Unknown			7	0.70%
Unknown Reprobe		13	1.30%
Unknown Alias		0	0.00%
Unknown Non-Alias	0	0.00%
Error			0	0.00%
==========|PASS CONDITIONS|===========
Alias			64	6.40%
Alias Weak		2	0.20%
Alias Strong		0	0.00%
--------------------------------------
TOTAL			1000	100%
======================================

Description

The overall verdicts table shows the distribution of end results that the tool determined for the candidate pairs.

Stats LabelRaw Code
Non-Alias StrongNOALIAS-STRONG
Non-Alias WeakNOALIAS-WEAK
IneligibleINELIGIBLE
UnknownUNKNOWN
Unknown ReprobeUNKNOWN-REPROBE
Unknown AliasUNKNOWN-ALIAS
Unknown Non-AliasUNKNOWN-NOALIAS
ErrorERROR
AliasALIAS
Alias WeakALIAS-WEAK
Alias StrongALIAS-STRONG

Additional Histograms

If the script is called with the --histogram option, it will display three additional histograms which can be useful for determining the causes of various results.

Note that these histograms ignore the ordering of the addresses, so a pair (X,Y) can appear as X -> Y as well as Y -> X. I.e. X can be both A and B in these histograms.

Failure Pairings

Pairs which contain one pass interface and one fail interface:
P2S		150	90.36%
	F1S	90	54.22%
	FNS	35	21.08%
	FNR	17	10.24%
	FVS	8	4.82%

P4S		16	9.64%
	FNR	13	7.83%
	FNS	2	1.20%
	FVS	1	0.60%

Shows the type of address that a passing address was paired with which caused the pair to be rejected after suitability testing.

In this example, the majority of pairs for which one address was suitable but not the other are two stampers paired with a one stamper.

Pass Pairings

Pairings which pass suitability check:
P2S		3	4.11%
	P2S	3	4.11%

P4S		70	95.89%
	P4S	70	95.89%

Similar to the above table, but provides an indication of what an address is usually paired with when they passed the suitability check. In this case we never see a four stamper paired with a two stamper passing suitability checking.

Suitability to AVC Mappings

Mapping from Suitability result to AVC result:
Suit A	AVC A	Suit B	AVC B	Count	%
P2S				6	4.11%
	P2S			6	100.00%
		P2S		6	100.00%
			P2S	6	100.00%

P4S				140	95.89%
	P4S			128	91.43%
		P4S		128	100.00%
			P4S	128	100.00%
	F1S			12	8.57%
		P4S		12	100.00%
			F1S	12	100.00%

Shows the relationship between the stamping behavior for (A|AAAA), (A|ABAB), (B|BBBB) and (B|BABA).

In the example above, an address which stamps four times in suitability checking (A|AAAA), almost always stamps four times in the validity check (A|ABAB), and when it does, the address that it is paired with always stamps four times for both the suitability and validity checks.

The Name

"In Polynesian languages, motu refers to a reef islet formed by broken coral and sand surrounding an atoll. There are countless motus scattered all over the Pacific Ocean." -- http://en.wikipedia.org/wiki/Motu

The idea is that Motu are the pieces of a large under-water land mass which are visible from above the water; similar to the the concept of interfaces on a router which are the pieces of the router that are 'visible' at the IP layer.

  Last Modified: Fri Feb-15-2013 13:03:31 PST
  Page URL: http://www.caida.org/tools/measurement/motu/index.xml