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.

Result	Definition	Notes
P4Sx	Pass, 4 Stamps
P3Sx	Pass, 3 Stamps
P2Sx	Pass, 2 Stamps
F1Sx	Fail, 1 Stamp
FNSx	Fail, No Stamp
FNRx	Fail, No Reply
FESx	Fail, Extra Stamp
FVSx	Fail, Varying Stamp	Multiple 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.

Result	Definition	Notes
P4S	Pass, 4 Stamps
P3S	Pass, 3 Stamps	Will likely fail the Alias Check
P2S	Pass, 2 Stamps
F1S	Fail, 1 Stamp
FNS	Fail, No Stamp
FNR	Fail, No Reply
FES	Fail, Extra Stamp
FVS	Fail, Varying Stamp	Multiple stamping behaviours were observed
FRN	Fail, Reverse path Non-monotonic	Interface is on the reverse path, timestamps were non-monotonic (they decreased) (NOALIAS-STRONG)
FRG	Fail, Reverse path Gap	Interface is on the reverse path, timestamps increment with >1ms gap between timestamps (NOALIAS-WEAK)
FRU	Fail, Reverse path Unknown	Interface 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.

Result	Definition	Notes
PNS	Pass, No Stamp	Not on the reverse path. Sent to Distance Check
P1S	Pass, 1 Stamp	Not on the reverse path. Sent to Distance Check
FNR	Fail, No Reply
FVS	Fail, Varying Stamp	Multiple stamping behaviours were observed
F2Nx/F2Gx/F2U	Fail, 2 Stamps	B 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/F3U	Fail, 3 Stamps	B 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.
F4S	Fail, 4 Stamps	Unexpected 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.

Result	Definition	Notes
P4S	Pass, 4 Stamps	Indicates an alias
F3S	Fail, 3 Stamps	Results in an error condition as 3 stampers are not understood
P2S	Pass, 2 Stamps
FIR	Fail, Insufficient Replies	50% 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.

Result	Definition	Notes
PSC	Pass, Shared Clock
PME	Pass, Midnight/Epoch
FDT	Fail, Decreasing Timestamp
F90	Fail, 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).

Result	Definition	Notes
PDI	Pass, Distance	The two addresses have equal return path lengths
FDI	Fail, Distance	The return path length differs between addresses
FNRx	Fail, No Reply	Where x is the number of replies
FTV	Fail, TTL Variance	Within probes to a single interface

Overall Result (mandatory)

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

Result	Definition	Notes
ALIAS	Confirmed as aliases
ALIAS-WEAK	Confirmed as aliases	A 2 Stamp interface and a 1 Stamp interface which passed the distance check
ALIAS-STRONG-1	Confirmed as aliases	Both interfaces are 4 Stamp
ALIAS-STRONG-2	Confirmed as aliases	Either two 2 Stamp interfaces, or a 2 Stamp and a 4 Stamp interface, which passed Shared Clock and Distance checks
NOALIAS-WEAK	Not aliases	Low-confidence
NOALIAS-STRONG	Not aliases	High-confidence
UNKNOWN	A determination could not be made
UNKNOWN-REPROBE	A determination could not be made	May be resolved by reprobing the pair
UNKNOWN-ALIAS	A determination could not be made	It is likely the pair are aliases
UNKNOWN-NOALIAS	A determination could not be made	It is likely the pair are not aliases
INELIGIBLE	At least one candidate interface was not suitable
ERROR	Unexpected Result	Likely 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 Label	Raw Code
Unresponsive	FNR
Inconsistent	FVS
Extra Stamp	FES
Zero Stamps	FNS
One Stamp	F1S
Two Stamps	P2S
Three Stamps	P3S
Four Stamps	P4S

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 Label	Raw Code
RP TS Decrease	FRD
RP TS Gap	FRG
RP TS Unknown	FRU

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 Label	Raw Code
1 Stamp	P1S
No Stamp	PNS
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 Label	Raw Code
<5 Replies	FIR
Three Stamps	F3S
Two Stamps	P2S
Four Stamps	P4S

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 Label	Raw Code
Decreasing TS	FDT
TS Variance	F90
Shared Clock	PSC
Midnight/Epoch	PME

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 Label	Raw Code
TTL Variance	FTV
TS Variance	F90
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 Label	Raw Code
Non-Alias Strong	NOALIAS-STRONG
Non-Alias Weak	NOALIAS-WEAK
Ineligible	INELIGIBLE
Unknown	UNKNOWN
Unknown Reprobe	UNKNOWN-REPROBE
Unknown Alias	UNKNOWN-ALIAS
Unknown Non-Alias	UNKNOWN-NOALIAS
Error	ERROR
Alias	ALIAS
Alias Weak	ALIAS-WEAK
Alias Strong	ALIAS-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.