Subject: [homenet] More about lossy links and yo-yo neighbours

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 19 Jul 2016 01:17:07 +0200

Dear all,

We only confirmed the yo-yo issue on Sunday, which caused me to send the
latest version of my slides at the very latest moment.  I therefore cannot
blame the chairs for forcing me to work with an older version of my talk
which didn't contain the explanation -- oh, what the heck, yes, I can ;-)
Please bear with me while I lecture a little.

It has been known since at least the early noughts that in a wireless mesh
network, no matter how well designed, persistently lossy links are
unavoidable.  Consider the following topology, where A, B and C are
wireless routers:

    . . . . .
   .         .
  A --- B --- C

By design, A and B are neighbours, as are B and C.  A and C are not
supposed to be neighbours (they are out of range of each other), but it is
unavoidable that once in a while C will hear a packet coming from A.

In the current version of HNCP, as soon as C receives a multicast
NETWORK-STATE from A, it inserts A in its list of peers, and, MS-Trickle
permitting, floods a new long NODE-STATE throughout the network.  Since it
no longer receives anything from C, it times out A from its list of
neighbours, and floods again.  The result is two long NODE-STATES flooded
across the network for every packet that manages to cross a highly
marginal link.  In a dense mesh, the number of such highly marginal links
is roughly quadratic in the number of routers -- the effect is that with
just 7 routers, we see one spurious reflooding every few seconds.  (Please
see the end of this message for a packet trace.)

HNCP, however, has a number of features that prevent the spurious topology
changes and associated refloodings from having any serious consequences.
First, the "ad-hoc" interface type (Section 5.1 of RFC 7788) is designed
so that a spurious topology change doesn't cause any renumbering -- since
the set of Common Links doesn't change, the PA algorithm is never invoked.
Second, even if the links are mis-configured, the PA algorithm is stable
enough to avoid renumbering outside of the affected link in most cases.
And last, reflooding is controlled by MS-Trickle (an algorithm that is
almost, but not quite, exactly unlike Trickle), which prevents refloodings
from happening too often.

I'm not sure what to do about this.  We could of course ignore the
issue -- after all, it's just a few hundred bytes per second extra control
traffic -- but I'm a little uncomfortable with that, I fear that it might
get us into trouble at some later stage.  Markus has a suggestion that
consists in tweaking the parameters of MS-Trickle.  My intuition is that
it's the wrong level at which to tackle the problem, but I have been wrong
about MS-Trickle before.

Appended below for your enjoyment is a fragment of a packet trace.  At
time 25.897 node ef:36:04:89 floods its node state.  At time 31.359, it
floods its state again, which is almost identical -- the only change is
the addition of the neighbour 9b:18:b7:26.

-- Juliusz

16:21:25.897046 IP6 (hlim 64, next-header UDP (17) payload length: 1396) fe80::e246:9aff:fe4e:912a.8231 > fe80::e246:9aff:fe4e:91e4.8231: [udp sum ok] hncp (1388)
	Node endpoint (12) NID: ef:36:04:89 EPID: 00000004
	Node state (1376) NID: ef:36:04:89 seqno: 72968 2.11s hash: c97a0c0c205d9de1
		Peer (16) Peer-NID: 24:1f:49:aa Peer-EPID: 00000002 Local-EPID: 00000004
		Peer (16) Peer-NID: 24:1f:49:aa Peer-EPID: 00000003 Local-EPID: 00000003
		Peer (16) Peer-NID: 75:05:c4:15 Peer-EPID: 00000002 Local-EPID: 00000003
		Peer (16) Peer-NID: 90:d1:74:28 Peer-EPID: 00000003 Local-EPID: 00000004
		Peer (16) Peer-NID: 90:d1:74:28 Peer-EPID: 00000004 Local-EPID: 00000003
		Peer (16) Peer-NID: 9b:18:b7:26 Peer-EPID: 00000002 Local-EPID: 00000004
		HNCP-Version (22) M: 0 P: 4 H: 4 L: 4 User-agent: hnetd/cda52dc
		Assigned-Prefix (18) EPID: 00000001 Prty: 2 Prefix: fd1f:f88c:e207:65::/64
		Assigned-Prefix (18) EPID: 00000002 Prty: 2 Prefix: fd1f:f88c:e207:47::/64
		Assigned-Prefix (18) EPID: 00000004 Prty: 2 Prefix: fd1f:f88c:e207:61::/64
		Assigned-Prefix (20) EPID: 00000001 Prty: 2 Prefix: 2001:660:3301:9209:1e::/80
		Assigned-Prefix (20) EPID: 00000002 Prty: 2 Prefix: 2001:660:3301:9209:41::/80
		Assigned-Prefix (20) EPID: 00000004 Prty: 3 Prefix: 2001:660:3301:9208:61::/80
		Assigned-Prefix (25) EPID: 00000001 Prty: 2 Prefix: 10.219.152.0/24
		Assigned-Prefix (25) EPID: 00000002 Prty: 2 Prefix: 10.191.218.0/24
		Assigned-Prefix (25) EPID: 00000004 Prty: 2 Prefix: 10.0.97.0/24
		Node-Address (24) EPID: 00000001 IP Address: 10.219.152.5
		Node-Address (24) EPID: 00000001 IP Address: 2001:660:3301:9209:1e::5
		Node-Address (24) EPID: 00000001 IP Address: fd1f:f88c:e207:65::5
		Node-Address (24) EPID: 00000002 IP Address: 10.191.218.61
		Node-Address (24) EPID: 00000002 IP Address: 2001:660:3301:9209:41::3d
		Node-Address (24) EPID: 00000002 IP Address: fd1f:f88c:e207:47::3d
		Node-Address (24) EPID: 00000003 IP Address: 10.0.116.30
		Node-Address (24) EPID: 00000003 IP Address: 2001:660:3301:9208:5b::1e
		Node-Address (24) EPID: 00000003 IP Address: fd1f:f88c:e207:dba3::1e
		Node-Address (24) EPID: 00000004 IP Address: 10.0.97.5
		Node-Address (24) EPID: 00000004 IP Address: 2001:660:3301:9208:61::5
		Node-Address (24) EPID: 00000004 IP Address: fd1f:f88c:e207:61::5
		DNS-Delegated-Zone (33) IP-Address: 2001:660:3301:9209:1e::5 lb- lan.r.home
		DNS-Delegated-Zone (35) IP-Address: 2001:660:3301:9208:61::5 lb- wlan1.r.home
		DNS-Delegated-Zone (35) IP-Address: 2001:660:3301:9209:41::3d lb- wlan0.r.home
		DNS-Delegated-Zone (36) IP-Address: 2001:660:3301:9208:5b::1e --- wlan01.r.home
		DNS-Delegated-Zone (43) IP-Address: 2001:660:3301:9208:61::5 --- 97.0.10.in-addr.arpa
		DNS-Delegated-Zone (46) IP-Address: 2001:660:3301:9209:1e::5 --- 152.219.10.in-addr.arpa
		DNS-Delegated-Zone (46) IP-Address: 2001:660:3301:9209:41::3d --- 218.191.10.in-addr.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9208:61::5 --- 1.6.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9209:1e::5 --- 5.6.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9209:41::3d --- 7.4.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9208:61::5 --- 1.6.0.0.8.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9209:1e::5 --- e.1.0.0.9.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9209:41::3d --- 1.4.0.0.9.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		Node-Name (22) IP-Address: 10.0.97.5 Name: "r"
		Node-Name (22) IP-Address: 2001:660:3301:9208:61::5 Name: "r"

[...]

16:21:31.359209 IP6 (hlim 64, next-header UDP (17) payload length: 1412) fe80::e246:9aff:fe4e:912a.8231 > fe80::e246:9aff:fe4e:91e4.8231: [udp sum ok] hncp (1404)
	Node endpoint (12) NID: ef:36:04:89 EPID: 00000004
	Node state (1392) NID: ef:36:04:89 seqno: 72974 1.87s hash: 79c431ca9a655adf
		Peer (16) Peer-NID: 24:1f:49:aa Peer-EPID: 00000002 Local-EPID: 00000004
		Peer (16) Peer-NID: 24:1f:49:aa Peer-EPID: 00000003 Local-EPID: 00000003
		Peer (16) Peer-NID: 75:05:c4:15 Peer-EPID: 00000002 Local-EPID: 00000003
		Peer (16) Peer-NID: 90:d1:74:28 Peer-EPID: 00000003 Local-EPID: 00000004
		Peer (16) Peer-NID: 90:d1:74:28 Peer-EPID: 00000004 Local-EPID: 00000003
		Peer (16) Peer-NID: 9b:18:b7:26 Peer-EPID: 00000002 Local-EPID: 00000004
		Peer (16) Peer-NID: 9b:18:b7:26 Peer-EPID: 00000003 Local-EPID: 00000003
		HNCP-Version (22) M: 0 P: 4 H: 4 L: 4 User-agent: hnetd/cda52dc
		Assigned-Prefix (18) EPID: 00000001 Prty: 2 Prefix: fd1f:f88c:e207:65::/64
		Assigned-Prefix (18) EPID: 00000002 Prty: 2 Prefix: fd1f:f88c:e207:47::/64
		Assigned-Prefix (18) EPID: 00000004 Prty: 2 Prefix: fd1f:f88c:e207:61::/64
		Assigned-Prefix (20) EPID: 00000001 Prty: 2 Prefix: 2001:660:3301:9209:1e::/80
		Assigned-Prefix (20) EPID: 00000002 Prty: 2 Prefix: 2001:660:3301:9209:41::/80
		Assigned-Prefix (20) EPID: 00000004 Prty: 3 Prefix: 2001:660:3301:9208:61::/80
		Assigned-Prefix (25) EPID: 00000001 Prty: 2 Prefix: 10.219.152.0/24
		Assigned-Prefix (25) EPID: 00000002 Prty: 2 Prefix: 10.191.218.0/24
		Assigned-Prefix (25) EPID: 00000004 Prty: 2 Prefix: 10.0.97.0/24
		Node-Address (24) EPID: 00000001 IP Address: 10.219.152.5
		Node-Address (24) EPID: 00000001 IP Address: 2001:660:3301:9209:1e::5
		Node-Address (24) EPID: 00000001 IP Address: fd1f:f88c:e207:65::5
		Node-Address (24) EPID: 00000002 IP Address: 10.191.218.61
		Node-Address (24) EPID: 00000002 IP Address: 2001:660:3301:9209:41::3d
		Node-Address (24) EPID: 00000002 IP Address: fd1f:f88c:e207:47::3d
		Node-Address (24) EPID: 00000003 IP Address: 10.0.116.30
		Node-Address (24) EPID: 00000003 IP Address: 2001:660:3301:9208:5b::1e
		Node-Address (24) EPID: 00000003 IP Address: fd1f:f88c:e207:dba3::1e
		Node-Address (24) EPID: 00000004 IP Address: 10.0.97.5
		Node-Address (24) EPID: 00000004 IP Address: 2001:660:3301:9208:61::5
		Node-Address (24) EPID: 00000004 IP Address: fd1f:f88c:e207:61::5
		DNS-Delegated-Zone (33) IP-Address: 2001:660:3301:9209:1e::5 lb- lan.r.home
		DNS-Delegated-Zone (35) IP-Address: 2001:660:3301:9208:61::5 lb- wlan1.r.home
		DNS-Delegated-Zone (35) IP-Address: 2001:660:3301:9209:41::3d lb- wlan0.r.home
		DNS-Delegated-Zone (36) IP-Address: 2001:660:3301:9208:5b::1e --- wlan01.r.home
		DNS-Delegated-Zone (43) IP-Address: 2001:660:3301:9208:61::5 --- 97.0.10.in-addr.arpa
		DNS-Delegated-Zone (46) IP-Address: 2001:660:3301:9209:1e::5 --- 152.219.10.in-addr.arpa
		DNS-Delegated-Zone (46) IP-Address: 2001:660:3301:9209:41::3d --- 218.191.10.in-addr.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9208:61::5 --- 1.6.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9209:1e::5 --- 5.6.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (63) IP-Address: 2001:660:3301:9209:41::3d --- 7.4.0.0.7.0.2.e.c.8.8.f.f.1.d.f.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9208:61::5 --- 1.6.0.0.8.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9209:1e::5 --- e.1.0.0.9.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		DNS-Delegated-Zone (71) IP-Address: 2001:660:3301:9209:41::3d --- 1.4.0.0.9.0.2.9.1.0.3.3.0.6.6.0.1.0.0.2.ip6.arpa
		Node-Name (22) IP-Address: 10.0.97.5 Name: "r"
		Node-Name (22) IP-Address: 2001:660:3301:9208:61::5 Name: "r"

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 19 Jul 2016 07:23:44 +0200

For the record, _within limits of current spec/implementation_ MS-Trickle parameter tuning can make the yo-yo effect arbitrarily rare. However, I think that the correct way of doing this would be either:

- Also not form neighbor links without indicator that the link is relatively stable; based on my experience, this is not 100% solution as some links exhibite loss that is function of time; however, this would limit the refloodings just to those links and they are most likely small subset of the whole.

- Something non-link-statey, notably not having global reachability graph (this implies TTLs, and selective flooding, so it is relatively different from DNCP as it is written now). As 'common link' concept is needed only by non-adhoc links in HNCP, this would work for adhoc networks _with_ same TLV content but different state synchronization algorithm. We discussed this privately in some group earlier and it also seemed workable.

Cheers,

-Markus

---

From: Ray Bellis <[email-masked]>
Date: Tue, 19 Jul 2016 10:21:58 +0200

On 19/07/2016 01:17, Juliusz Chroboczek wrote:
> I therefore cannot blame the chairs for forcing me to work with an
> older version of my talk which didn't contain the explanation -- oh,
> what the heck, yes, I can ;-) Please bear with me while I lecture a
> little.

The correct slides are available at:

<https://www.ietf.org/proceedings/96/slides/slides-96-homenet-1.pdf>

FWIW, I did get Juliusz's new slides, but managed to re-upload the
original set! :p

Ray