New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Suggestion: Predictable selection of RFC6791 addresses #130

Closed
toreanderson opened this Issue Mar 6, 2015 · 2 comments

Comments

Projects
None yet
2 participants
@toreanderson
Copy link
Contributor

toreanderson commented Mar 6, 2015

Currently, Jool will select addresses from its RFC6791 addresses in a random fashion. That's in line with the RFC's recommendations. The rationale for this recommendation is as follows:

Random selection reduces the probability that two ICMP
messages elicited by the same TRACEROUTE might specify the same
source address and, therefore, erroneously present the appearance of
a routing loop.

That's all well and good, but it does cause some funny results from traceroute programs that run continuously, such as MTR. See below for an example, where 10.0.0.0/30 is used for Jool's RFC6791 pool:

$ mtr -c 10 -r --report-wide 185.47.42.202
HOST: login-osl1                        Loss%   Snt   Last   Avg  Best  Wrst StDev
  1.|-- ge-0-0-22.cs1-osl1.n.bitbit.net    0.0%    10    0.8   0.8   0.7   0.9   0.1
  2.|-- xe-1-2-0-31.cr1-osl2.n.bitbit.net  0.0%    10    0.3   0.3   0.3   0.4   0.0
  3.|-- vlan-1.cs1-osl3.n.bitbit.net       0.0%    10    1.2   1.2   1.0   1.6   0.2
  4.|-- bond0.fw2-osl3.n.bitbit.net        0.0%    10    0.4   0.4   0.3   0.4   0.0
  5.|-- ucstest-osl2.i.bitbit.net          0.0%    10    0.7   0.7   0.6   0.7   0.0
  6.|-- 10.0.0.3                           0.0%    10    1.1   1.1   1.1   1.2   0.0
    |  `|-- 10.0.0.0
    |   |-- 10.0.0.1
    |   |-- 10.0.0.2
  7.|-- 10.0.0.0                           0.0%    10    4.1   2.4   2.1   4.1   0.6
    |  `|-- 10.0.0.2
    |   |-- 10.0.0.3
    |   |-- 10.0.0.1
  8.|-- 10.0.0.0                           0.0%    10    1.3   2.1   1.3   9.2   2.5
    |  `|-- 10.0.0.3
    |   |-- 10.0.0.2
    |   |-- 10.0.0.1
  9.|-- 10.0.0.3                           0.0%    10   57.6   7.0   1.3  57.6  17.8
    |  `|-- 10.0.0.1
    |   |-- 10.0.0.2
    |   |-- 10.0.0.0
 10.|-- 10.0.0.2                           0.0%    10    1.5   1.5   1.5   1.6   0.0
    |  `|-- 10.0.0.1
    |   |-- 10.0.0.0
    |   |-- 10.0.0.3
 11.|-- 10.0.0.0                           0.0%    10    1.7   1.6   1.6   1.7   0.0
    |  `|-- 10.0.0.1
    |   |-- 10.0.0.3
    |   |-- 10.0.0.2
 12.|-- 185.47.42.202                      0.0%    10    1.4   1.4   1.4   1.5   0.0

However, I can imagine an even better way to do it, that stays true to the RFC's rationale. The algorithm I propose is to use the Hop Limit field in the inbound ICMPv6 packet modulo the count of addresses in Jool's RFC6791 pool as the index to select a certain address in the pool. In pseudocode:

icmpv4.src_addr = rfc6791_pool[icmpv6.hop_limit % entrycount(rfc6791_pool)];

This means that a traceroute will appear to have a loop (i.e., contain repeating "hops") IFF the number of IPv6 hops is greater than the number of addresses in Jool's RFC6791 pool. But in this case, the random selection approach must necessarily produce repeating hops as well, so it fares no worse.

If the RFC6791 pool contains an equal or greater number of addresses then there are IPv6 hops in the path, the question of whether or not hops will repeat becomes a question of probability - the larger the size of the RFC6791 pool and the smaller number of IPv6 hops, the smaller the probability that repeats will occur - but you can never be certain that they won't. My algorithm would on the other hand guarantee that the traceroute will not contain any repeated hops.

Since Hop Limit is an 8-bit field, using my algorithm, an operator could ascertain that traceroutes will never ever contain repeated hops simply by assigning an IPv4 /24 to the RFC6791 pool. In practise, a /27 would suffice, as most traceroute programs use default a starting TTL of 30.

As an added benefit, using a /24 means that if the ICMPv4's source address is x.y.z.n, then you can immediately deduce that the original ICMPv6's Hop Limit field was n. This is something the operator could then communicate to the user running the traceroute by assigning the addresses in the /24 appropriate DNS IN PTR records, e.g.:

$ORIGIN z.y.x.in-addr.arpa.
0 IN PTR rfc6791-icmpv6-hlim-0.mynetwork.net.
1 IN PTR rfc6791-icmpv6-hlim-1.mynetwork.net.
2 IN PTR rfc6791-icmpv6-hlim-2.mynetwork.net.
[...]
255 IN PTR rfc6791-icmpv6-hlim-255.mynetwork.net.

Note that I do not propose that the imminent release of Jool 3.3 should be delayed in order to implement this. Unless it is super easy and super fast to implement, please wait until 3.4! It is absolutely not a important feature in any way, merely a «nice to have».

ydahhrk added a commit that referenced this issue Mar 8, 2015

So I got inspired and fulfilled some whims.
- The names of several --global keys have for a long time bothered me due to their overly shortened names and caps. I'm adding new names and deprecating the old ones. They still work, but maybe not forever.
	- In particular, `errorAddresses` is now named `pool6791` both in the module and the app.
- There were 100+ lines of duplicate code in rfc6791 and route. I refactored them.
- Reviewed the doc and found more annoyances that needed fixing. This includes issue #128.
- #130. See --randomize-rfc6791-addresses in SIIT Jool's userspace app.

@ydahhrk ydahhrk added this to the 3.3.0 milestone Mar 8, 2015

@toreanderson

This comment has been minimized.

Copy link
Contributor

toreanderson commented Mar 9, 2015

After testing current Git master I realise that I made a faulty assumption when I thought that my approach would be able to guarantee that no "loops" would show up by using a /24 as the RFC6791 pool, or indeed as long as the size of the RFC6791 pool was greater than the number of IPv6 hops in the path. Because routing may be asymmetric, there are no guarantee that the HLIM of the ICMPv6 Time Exceeded received by Jool from an IPv6 router will accurately indicate the number of hops in to that router in the outbound direction. Even if it did, it is theoretically possible that the various routers in a path use different initial HLIM values in their ICMPv6 errors, causing them to be identical when received by the Jool box.

In any case, the new --randomize-rfc6791-addresses: OFF does have plenty of value, because it makes continuous traceroute programs like MTR look more sane, and even though the HLIM (and thus the last octet in the translated IPv4 address) doesn't necessarily decrease by exactly 1 for each hop, it does show a generally decreasing trend in general. This, especially if combined with descriptive DNS PTR records, results in less confusing output than the truly random algorithm, in my opinion.

See below for output produced by Git master, using 10.0.0.0/24 as the RFC6791 pool:

$ mtr -n -r -c 10 185.47.42.3
HOST: redpilllinpro02.ring.nlnog. Loss%   Snt   Last   Avg  Best  Wrst StDev
  1.|-- 87.238.39.41               0.0%    11    1.3   1.3   1.0   1.6   0.2
  2.|-- 87.238.62.211              0.0%    10    0.1   0.2   0.1   0.3   0.1
  3.|-- 185.47.41.3                0.0%    10    0.3   0.4   0.3   0.5   0.1
  4.|-- 10.0.0.64                  0.0%    10    0.4   0.6   0.4   0.8   0.1
  5.|-- 10.0.0.63                  0.0%    10    1.8   1.7   1.5   1.8   0.1
  6.|-- 10.0.0.61                  0.0%    10    0.9   4.3   0.7  15.6   5.8
  7.|-- 10.0.0.61                  0.0%    10   17.6   3.0   0.8  17.6   5.3
  8.|-- 10.0.0.61                  0.0%    10    1.0   1.0   1.0   1.1   0.1
  9.|-- 10.0.0.55                  0.0%    10   21.9  22.2  21.8  23.4   0.6
 10.|-- 10.0.0.53                  0.0%    10   21.3  26.6  21.1  73.8  16.6
 11.|-- 10.0.0.48                  0.0%    10  269.7 278.1 263.6 310.0  15.0
 12.|-- 10.0.0.48                  0.0%    10  269.2 272.3 266.2 277.9   5.0
 13.|-- 10.0.0.47                  0.0%    10  276.8 284.3 274.1 300.0   8.2
 14.|-- 10.0.0.46                  0.0%    10  274.0 280.9 270.9 294.4   8.6
 15.|-- 10.0.0.46                  0.0%    10  278.6 278.7 266.7 284.2   5.9
 16.|-- 185.47.42.3                0.0%    10  270.8 270.3 265.7 276.1   4.2
@ydahhrk

This comment has been minimized.

Copy link
Member

ydahhrk commented Mar 9, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment