Motu Dealiasing Tool
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 messageThe 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 |
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.